使用遗传算法的数字目标游戏 AI

• 下载包含遗传算法库的源代码 - 259 KB
• 下载演示应用程序 - 125 KB
• 最新遗传算法库发布
• 遗传算法库在线文档

目标数字游戏

在这个游戏中，玩家的任务是使用基本运算和一组预定义的数字，找到一个数学表达式，其值最接近一个随机选择的值。游戏还有其他限制：所有中间结果和最终结果必须是正整数。对选定数字和目标数字也施加了额外限制。玩家会得到四个介于1到9之间的随机数，一个来自 { 10, 15, 20 } 集合的数字，以及一个来自 { 25, 50, 75, 100 } 集合的数字。目标数字是从区间 [100,999] 中随机选择的。玩家只能使用选定的数字一次。谁的表达式最接近目标数字，谁就赢。如果打平，则选择数字的玩家获胜。

可能表达式的数量

在实现解决此问题的实际算法之前，看看使用选定数字和基本运算可以构建多少个表达式会很有趣。对于给定数量的叶子（表达式中使用的数字），可能表达式树的数量由卡特兰数  定义，其中 n 应该是叶子数减1。

可能表达式的数量也受执行的操作数量和所选数字的组合数量的限制。组合数量由二项式系数  定义，其中 n 是所选数字的数量，k 是我们实际在表达式中使用的数字数量（表达式树叶子）。

假设我们只使用基本数学运算 { +, -, *, / }，使用 n 个数字可以构造的表达式数量的最终公式是 ，其中 n 是我们能使用的选定数字的数量。使用暴力算法我们应该搜索的实际表达式数量可以减少到 ，因为不使用所有选定数字的表达式已经由最长可能表达式（使用所有数字的表达式）的子树表示。这个公式对于6个数字大约产生600,000个表达式，但其中许多表达式是无效的（它们可能包含除零或不产生整数结果的除法运算），或者它们与其他表达式没有显著区别，因此实际数量可以进一步减少。

遗传算法

在本例中，使用遗传算法而不是暴力算法。遗传算法库用于实现该算法。有关实现自定义遗传操作的详细信息在参考文章中提供，此处不再讨论。

染色体

首先应该考虑的是如何在GA中用染色体表示表达式，使其适合执行各种遗传操作，并能让它们将良好特征保留并传播给后代。

表示

本例将使用表达式的树形表示，这将方便地实现交叉和变异操作。另一点需要考虑的是，遗传算法可能会产生许多不稳定的表达式，向表达式中引入无用的操作，或者为本质上相同的表达式构建许多具有不同表达式树的染色体。这些问题的解决方案将在接下来的两节中讨论。

表达式树的节点由 TngNode 结构表示。

struct TngNode
{

  TngNodeType _type;
  int _value;

  /* structure of the tree */
  TngNode* _left;
  TngNode* _right;
  TngNode* _parent;

  /* ... */

};

_type 字段存储节点的类型（节点是数字还是操作，如果是操作，是哪个操作）。如果节点类型是数字，_value 字段存储节点中存储的所选数字的索引；否则，此字段不使用。

染色体由 TngChromosome 类表示。选定的数字和目标数字存储在由 TngConfigBlock 表示的染色体配置块中。

class TngConfigBlock : public Chromosome::GaChromosomeOperationsBlock
{

private:

  int _numbers[ TNG_NUMBER_COUNT ];
  int _targetNumber;

public:

  TngConfigBlock(Chromosome::GaCrossoverOperation* crossoverOperation,
    Chromosome::GaMutationOperation* mutationOperation,
    Chromosome::GaFitnessOperation* fitnessOperation,
    Chromosome::GaFitnessComparator* fitnessComparator,
    Chromosome::GaChromosomeParams* parameters);

  TngConfigBlock(const int* numbers,
    int targetNumber,
    Chromosome::GaCrossoverOperation* crossoverOperation,
    Chromosome::GaMutationOperation* mutationOperation,
    Chromosome::GaFitnessOperation* fitnessOperation,
    Chromosome::GaFitnessComparator* fitnessComparator,
    Chromosome::GaChromosomeParams* parameters);

  TngConfigBlock(const TngConfigBlock& rhs);
  inline void GACALL SetNumbers(const int* numbers);
  inline int* GetNumbers();
  inline const int* GetNumbers() const;
  inline void GACALL SetTargetNumber(int number);
  inline int GACALL GetTargetNumber() const;

};

class TngChromosome : public Chromosome::GaDynamicOperationChromosome
{

private:

  TngNode* _root;
  TngNode* _backup;

public:

  TngChromosome(TngConfigBlock* configBlock) ;
  TngChromosome(const TngChromosome& c, bool setupOnly);
  virtual ~TngChromosome();
  virtual Chromosome::GaChromosomePtr GACALL MakeCopy(bool setupOnly) const;
  virtual Chromosome::GaChromosomePtr GACALL MakeNewFromPrototype() const;
  virtual void GACALL PreapareForMutation();
  virtual void GACALL AcceptMutation();
  virtual void GACALL RejectMutation();
  inline void GACALL SetRoot(TngNode* root);
  virtual int GACALL GetCodeSize(void) const;
  inline TngNode* GACALL GetRoot();
  inline const TngNode* GACALL GetRoot() const;
  virtual bool GACALL operator ==(const Chromosome::GaChromosome& c) const;

};

表达式值的计算通过表达式树的顺序遍历，计算每个节点的值来执行。

int GACALL TngAdd(int a, int b) { return a + b; }
int GACALL TngSub(int a, int b) { return a - b; }
int GACALL TngMul(int a, int b) { return a * b; }
int GACALL TngDiv(int a, int b) { return !b || a % b ? a : a / b; }

typedef int (GACALL *TngOp)(int, int);
TngOp TngOps[] = { TngAdd, TngSub, TngMul, TngDiv };

inline int GACALL TngOpExec(TngNodeType nodeType,
  int a,
  int b) { return TngOps[ nodeType - 1 ]( a, b ); }

int GACALL TngCalculateValue(const TngNode* node,
  const int* values)
{
  if( node->_type == TNT_NUMBER )
    return values[ node->_value ];

    return TngOpExec( node->_type,
      TngCalculateValue( node->_left, values ),
      TngCalculateValue( node->_right, values ) );
}

请注意，除法运算对无效操作数有特殊情况。为什么这样处理这种情况在下一节中解释。

表达式树的化简

化简操作的目的是从表达式中移除无用和不稳定的操作。将触发化简的情况包括：

• 除以零，
• 不能产生整数结果的除法，以及
• 产生与其某个子表达式相同结果的操作（即，乘以或除以值为1的表达式，以及加或减值为0的表达式）。

如果存在这样的子表达式，此操作会将表达式替换为其产生相同结果的子表达式。正如前一节所解释的，无效的除法操作返回的结果就像没有执行该操作一样，从而有效地将其从表达式中消除。

加法操作的化简	乘法操作的化简
无效除法操作的化简	化简为等效子树

化简由 TngReduceTree 函数实现。

表达式树的规范化

规范化通过改变连续的+和*操作的执行顺序及其操作数的顺序来转换编码。这些操作的操作数或子表达式按其值递增排序。这样，我们可以将许多看似不同的表达式转换为单一形式。

加法和乘法操作的规范化

类似的转换也可以应用于连续的减法和除法操作，但在此示例中未实现。

虽然化简操作的动机非常明确，但规范化操作的必要性却不那么明显。允许不同的编码表示相同的解决方案，会削弱隐式并行性的效果，而隐式并行性是遗传算法最强大的特点之一，其性能会严重降低。执行此转换可确保编码遵循约定，从而减少重复编码的数量，有效地缩小搜索空间并提高算法的性能。

规范化由 TngNormalizeTree 函数实现。

适应度分配

适应度操作计算表达式的值与目标数字的偏差。实际的适应度函数是 ，其中 t 是目标数字，n 是表达式的计算值。这意味着适应度值在 (0,1] 范围内，值越大表示染色体越接近目标数字。当找到适应度值为1的染色体时，算法可以停止。

交叉

交叉操作通过复制其中一个父代的表达式树来创建一个子代染色体，但它会从副本中移除一个随机子树，并插入另一个父代的随机子树来代替被移除的子树。交叉必须确保插入的子树不包含子代树其余部分已使用的数字。为此，它选择一对不会产生比允许的数字更多的表达式树的子树；之后，如果它检测到表达式使用的数字次数超过允许的次数，该操作会简单地将其替换为未使用的数字。交叉后，执行化简和规范化。

交叉由 TngCrossover 类实现。

变异

对染色体执行两种类型的突变。第一种是交换两个随机子树的位置，第二种是随机翻转操作或数字。每种类型的突变都有相同的执行机会。执行突变后，染色体会被化简和规范化。

突变类型 I

突变类型 II

突变由 TngMutation 类实现。

算法设置

在每一代中，算法使用轮盘赌选择选择八个父代，并使用简单耦合产生八个子代，该耦合使用前面描述的自定义交叉和变异操作。算法用产生的子代替换适应度最差的染色体。群体中已经存在的子代染色体不会被插入。

CpuPlayer 封装了遗传算法，并为应用程序的其他部分提供接口。该类的构造函数初始化遗传算法的参数和配置，Start 方法创建一个算法实例并启动它。

CpuPlayer::CpuPlayer(CStatic* cpuStatus,
  CListCtrl* populationContent) : _result(0), _cpuStatus(cpuStatus),
  _populationContent(populationContent), _algorithm(NULL),
  _chromosomeParams( 0.3f, 1, false, 0.8f, 1 ),
  _configBlock( &_crossover, &_mutation,
    &_fitnessOperation, GaFitnessComparatorCatalogue::Instance().GetEntryData(
    "GaMaxFitnessComparator" ), &_chromosomeParams ),
  _populationParams( 32, false, true, false, 0, 0 ),
  _populationConfig( _populationParams, &_configBlock.GetFitnessComparator(),
    GaSelectionCatalogue::Instance().GetEntryData( "GaSelectRouletteWheel" ),
    &Population::SelectionOperations::GaSelectDuplicatesParams( false, 8 ),
    GaReplacementCatalogue::Instance().GetEntryData( "GaReplaceWorst" ),
    &Population::GaReplacementParams( 8 ),
    GaCouplingCatalogue::Instance().GetEntryData( "GaSimpleCoupling" ),
    &Population::GaCouplingParams( 8 ),
    NULL, NULL),
  _algorithmParams( 2 ) { } 

算法参数
变异概率	30%
变异大小	1个基因
只接受能提高适应度的变异	是
交叉概率	80%
交叉点	1
种群大小	32条染色体
已排序种群	是
适应度排序	最大化
选择类型	轮盘赌
选择大小	8
耦合类型	简单耦合
要产生的后代数量	8
替换类型	替换最差的
要替换的染色体	8
工作线程数	2

void CpuPlayer::Start(const NumberGenerator& numbers)
{
  _populationContent->DeleteAllItems();

  _configBlock.SetNumbers( numbers.GetGenerated() );
  _configBlock.SetTargetNumber(
    numbers[ NumberGenerator::NUMBERS_TO_GENERATE - 1 ] );

  TNG::TngChromosome prototype( &_configBlock );
  Population::GaPopulation population( &prototype, &_populationConfig );
  Algorithm::SimpleAlgorithms::GaIncrementalAlgorithm algorithm( &population,
                              _algorithmParams );

  _algorithm = &algorithm; 

  TNG::TngStopCriteriaParams criteriaParams( GAME_TIME - 2 );
  algorithm.SetStopCriteria( &_stopCriteria, &criteriaParams);

  algorithm.SubscribeObserver( this );

  algorithm.StartSolving( false );
  algorithm.WaitForThreads();
}

自定义停止条件由 TngStopCriteria 类实现。当找到适应度值为1的染色体或时间即将到期时，它会使遗传算法停止。此停止条件的参数由 TngStopCriteriaParams 处理，它们存储算法开始的时间和游戏的持续时间。

支持类

数字的生成由 NumberGenerator 类管理。计时在 Timer 类中实现。InputManager 类管理、解析和计算玩家的输入。Results 结构存储游戏结束后的状态。游戏流程由 Master 类实现。这些类位于 Game 命名空间中。

解析用户表达式

解析和计算用户表达式由位于 Parsing 命名空间中的 Lexer 和 Parser 这两个类实现。

Lexer 从输入中读取标记并将其提供给解析器。标记由 LexSymbol 结构表示。

struct LexSymbol
{
  LexSymbolType _type;
  int _value;
  int _position;

  /* ... */
};

_type 存储标记类型，_value 字段存储取决于标记类型的信息，_position 存储标记在输入中的第一个字符的位置。

LexSymbolType 定义了允许的标记类型

enum LexSymbolType
{
  LEX_ST_PARENS_OPEN,
  LEX_ST_PARENS_CLOSE,
  LEX_ST_NUMBER,
  LEX_ST_OPERATOR,
  LEX_ST_END
};

对于 LEX_ST_NUMBER 标记，值字段存储实际数字；对于 LEX_ST_OPERATOR，字段存储运算符类型

enum LexOperatorType
{
  LEX_OT_PLUS,
  LEX_OT_MINUS,
  LEX_OT_TIMES,
  LEX_OT_OVER
};

Lexer 类的 Get 方法实现了输入字符串的标记化并返回下一个标记。如果输入结束，该方法返回 LEX_ST_END 标记。当检测到无效字符时，它会抛出 SyntaxException。

LexSymbol Lexer::Get()
{
  int c = GetChar();
  switch( c )
  {
  case '(': return LexSymbol( LEX_ST_PARENS_OPEN, GetPosition() );
  case ')': return LexSymbol( LEX_ST_PARENS_CLOSE, GetPosition() );
  case '+': return LexSymbol( LEX_ST_OPERATOR, LEX_OT_PLUS, GetPosition() );
  case '-': return LexSymbol( LEX_ST_OPERATOR, LEX_OT_MINUS, GetPosition() );
  case '*': return LexSymbol( LEX_ST_OPERATOR, LEX_OT_TIMES, GetPosition() );
  case '/': return LexSymbol( LEX_ST_OPERATOR, LEX_OT_OVER, GetPosition() );
  case -1: return LexSymbol( LEX_ST_END, GetPosition() );

  default:
    if( !IsDigit( c ) ) throw SyntaxException( GetPosition() );

    int pos = GetPosition(), num = ToNum( c );
    while( IsDigit( PeekChar() ) )
      num = num * 10 + ToNum( GetChar() );

    return LexSymbol( LEX_ST_NUMBER, num, pos );
  }
}

Parser 类的 Parse 方法分析标记并计算用户表达式的值。此方法将抛出以下异常之一：SyntaxException、InputException 或 ArithmeticException，或者如果没有错误，它将返回表达式的值。如果将允许的数字列表作为参数提供给该方法，则如果用户输入中检测到非法数字，它将抛出 InputException；否则，所有数字都允许。当检测到非法算术运算（例如除以零）时，会抛出 ArithmeticException；最后，当用户输入中存在语法错误时，会抛出 SyntaxException。

int Parser::Parse(int count/* = 0*/,
       const int* allowedNumbers/* = NULL*/)
{
  for( int i = count - 1; i >= 0; i-- )
    _allowedNumber[ allowedNumbers[ i ] ]++;

  while( 1 )
  {
    LexSymbol symbol = _lexer.Get();

    switch( symbol._type )
    {

    case LEX_ST_END: return Calculate( symbol._position );
    case LEX_ST_PARENS_OPEN: OpenParens( symbol._position ); break;
    case LEX_ST_PARENS_CLOSE: CloseParens( symbol._position ); break;
    case LEX_ST_NUMBER: StoreNumber( symbol._value, symbol._position ); break;
    case LEX_ST_OPERATOR: StoreOperator( symbol._value, symbol._position ); break;

    }
  }

  throw SyntaxException( -1 );
}

StoreOperator、StoreNumber、OpenParens 和 CloseParens 存储应执行的操作，并计算其执行顺序（优先级）。Calculate 方法根据其优先级执行存储的操作并计算表达式的值。