种群优化算法：二进制遗传算法（BGA）。第 I 部分

内容

1. 概述
2. 特征呈现方法：实数和二进制
3. 格雷二进制码表示优势
4. 选择方法
5.“交叠”方法类型
6. “突变”方法类型
7. 总结

1. 概述

在本文中，我们将仔细研究遗传算法中所用的方法和技术，其可作为工具，在自定义解决方案中创建各种优化算法、并构建模块。本文的目的是讲述并提供工具，来研究任何优化算法中的优化问题，而不仅仅是遗传算法。

2. 特征呈现方法：实数和二进制

优化问题的参数通常称为 “特征”，必须以某种方式表示，才可在优化算法的逻辑中所用。在遗传学中，这些特征划分为表现型和基因型。表现型是正被优化的参数的外观，基因型是它在算法中的表示方式。在大多数优化算法中，表现型与基因型相同，并表示为实数。基因是优化参数，反过来，染色体是一组基因，即一组优化参数。

实数数据表示法常用来表示分数。实数可以有十进制部分和分数部分，用小数点分隔。例如，“3.14” 和 “0.5” 是实数。

数据的二进制表示，另一方面，使用二进制数字系统，其数字使用两个符号表示：“0” 和 “1”，每个数位称为比特位（二进制数位）。例如，数字 “5” 可以用二进制形式表示为 “101”。

数据的实数表示和二进制表示之间的主要区别在于数字的编码方式。实数通常使用 IEEE 754 等标准进行编码，IEEE 754 定义了浮点数的表示格式。在 MQL5 语言中，“double（双精度）” 数据类型用于实数。它可以在一个数字中描述总共 16 个有效数位。这意味着总数位量不能超过 16，例如，“9 999 999 999 999 999.0” 和 “9 999 999.999 999 99” 和 “0.999 999 999 999 9” 在小数点前后总共有 16 个 “9”。我稍后会解释为什么这很重要。

实数便于在编写程序和日常生活中所用，而二进制数则用于计算系统，以及执行低级运算，包括逻辑和按位运算。

在优化算法（包括遗传算法）的上下文中，数据可以表示为实数或二进制数，其可用于决策编码，并据其执行操作。

在优化算法中使用实数的优点是能够操控连续参数值。实数表示允许我们用数字针对特征进行编码，并直接用这些数字执行搜索解的操作。例如，如果解是含有数值的向量，则向量的每个元素都可用实数进行编码。

不过，实数表示亦有缺点。优化问题的各个元素都可以是独立的，并表示多维非重叠空间。这在定位全局解时会产生困难，由于空间划分为独立的子空间，故搜索可能很困难。

二进制表示特征的优势在于能够将所有特征组合成一个多维非重叠空间的完整描述。这允许将单个多维空间链接到一个公共搜索空间。二进制表示形式还令执行基本按位运算（如“突变”算子）变得更加容易，这与实数不同，因其需要额外的耗来执行此类操作。

优化算法中二进制表示的缺点是需要转换为实数，其优化任务最终会据其进行操作，以及额外的耗时操作，诸如以足够数组长度的形式存储比特位表示。

因此，实数提供了操控连续值的灵活性，而二进制表示允许将特征组合成一个整体，并更有效地对它们执行按位运算。除了遗传算法之外，优化算法也许会用到这两种表示方法，从而获得两者的优势。

3. 格雷二进制码表示优势

尽管二进制表示拥有所有优点，但它有一个明显的缺点：两个接近的十进制数若用二进制表示竟可能相差若干比特位。例如，在二进制代码中，从 7（0111）移动到 8（1000）会所有四个比特位都会变化。这意味着在不同的接近数字之间需要不同数量的比特位操作，其导致的结局就是搜索空间中的概率不均匀，出现奇特的 “增加概率带” ，与其对比，优化参数中出现 “盲点”。

例如，如果我们想针对两个仅相差一个单位的十进制表示法数字执行算术运算，那么在二进制表示法中也许需要更改若干比特位。结果是，运算后自所需数字获得的概率将是不均匀的，与另一对数字不同，因为每个比特位的变化都会影响最终结果。在执行浮点计算时，这种现象尤其问题重重，因为数字表示的精度非常重要，十进制数字表示的微小变化可能导致其二进制表示发生较大变化，而计算结果亦然。

在格雷码二进制表示形式（也称为反射二进制码）中，每个数字都表示为一组比特位，但每个后续数字与前一个仅相差一个修改的比特位。这确保了数字序列的平滑过渡，该属性称为 “单位距离属性”。

之前，我提到过 “double（双精度）” 数字仅由 16 位有效数位表示。我们看一个示例，以更好地明白这可能产生的影响。

假设我们有一个数字，有 15 个有效 “0”，且在第 16 位为 “1”："0.0000000000000001"。现在我们来给这个数字加上 1.0，得到 "1.0000000000000000"。注意，第 16 位数字中的 “1” 已消失，小数点后只剩下 15 位有效数字。当新数字被添加到双精度的整数部分时，有效数字将向左移动。因此，如果我们有一个非零整数部分，我们不能保证精确到小数点后第 16 位。

在二进制表示中，特别是在使用格雷码时，如果我们设定了这样的目标，或者在特定任务的框架内需要，我们可以避免数字精度损失的问题。我们更详尽地探讨这方面。

计算机以二进制表示方式操控程序和数字，因为这是机器处理信息的最有效和最自然的方式。不过，为了便于理解和编写顶级优化算法，我们需要一些额外的努力来操控二进制形式的数字，尤其是在负数和含有小数部分数字的情况下。

为了在最高级别的编程中操控二进制形式的数字，有各种函数库和工具可以更轻松地处理和表示负数和含有小数部分的数字。但我们利用 MQL5 实现所有内容，作为优化算法的一部分。

附加码方法用于表示二进制系统中的负数。它允许我们显示负数，这是通过在结果中加 1，并反转数字的所有比特位实现。但是我们将使用一个小技巧，通过简单地摆脱它们，避免额外的运算来操控负数。假设其中一个优化参数具有边界：

最小值 = -156.675 且最大值 = 456.6789

那么 “最大值” 和 “最小值” 之间的距离为：

距离 = 最大值 - 最小值 = 456.6789 - (-156.675) = 613.3539

因此，优化问题中所需的数字将始终为正数。它将位于数字线上 0.0 的右侧，最大值等于 613.3539。现在的任务是确保实数的编码。为此，我们将该数字拆分为整数和小数部分。整个部分将用格雷码表示如下（表示方法在括号中表示）：

613（十进制）= 1 1 0 1 0 1 0 1 1 1（二进制格雷）

那么小数部分将如下所示：

3539（十进制）= 1 0 1 1 0 0 1 1 1 0 1 0（二进制格雷）

我们可以将整数和小数部分存储在一个字符串当中，同时记住用于这两个部分的字符数，这令我们可以轻松地进行逆向转换。因此，实数将如下所示（“:” 符号有条件地分隔整数和小数部分）：

613.3539（十进制）= 1 1 0 1 0 1 0 1 1 1  :  1 0 1 1 0 0 1 1 1 0 1 0（二进制格雷）

因此，我们可以转换十进制整数部分 16 位以内的任何实数，以及 16 位双精度型数字。甚至，这允许我们在总位数中拥有超过 16 位有效数字，甚至高达 32 位或更多有效数字（受制于将整数十进制数转换为格雷码的函数中所用的 ulong 数长度的限制，反之亦然）。

为确保小数部分精确到第 16 位数字，我们需要转换数字 “9,999,999,999,999”（最大可能的小数）：

9999999999999999 (十进制) = 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (二进制格雷)

那么我们的数字 613.99999999999999999（有 16 位十进制）的最终记录将如下所示：

613.9999999999999999 (十进制) = 1 1 0 1 0 1 0 1 1 1  :  1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (二进制格雷)

正如我们所见，用户可以在 ulong 类型长度内设置小数点后的任何精度。

我们看看将十进制整数转换为格雷码的函数，反之亦然。对于格雷码编码和解码，使用附加函数转换到规则的二进制码。

DecimalToGray 函数取 “decimalNumber”，以及参数中指向存储转换结果的数组链接。它将数字从十进制转换为格雷码。为此，它首先使用 “decimalNumber” 及其向右移动一位之间的 XOR 按位运算来计算 “grayCode” 值。然后，它调用 IntegerToBinary 函数将生成的 “grayCode” 值转换为二进制表示形式，并将其存储在数组当中。按 char 类型最节省整数存储数组。

IntegerToBinary 函数接受 “number”，以及指向 “array” 的链接作为参数，转换结果将存储在其中。它将数字从十进制数字系统转换为二进制数字系统。在循环中，它获取 “number” 除以 2 的余数，并将其添加到 “array” 之中。然后，它将 “number” 除以 2，并增加 “cnt” 计数器。只要 “number” 大于 0，循环就会继续。循环之后，“array” 被翻转，从而获得正确的比特位顺序。

GrayToDecimal 函数接受指向 “grayCode” 数组的链接、“startInd” 初始索引、和 “endInd” 结束索引作为参数。它将数字从格雷码转换为十进制数字系统。它首先调用 BinaryToInteger 函数，将 “grayCode” 数组转换为二进制表示形式，并将其存储在 “grayCodeS” 变量之中。然后，它用 “grayCodeS” 值初始化 “result” 变量。然后，它执行循环，将 “grayCodeS” 向右移动一比特位，并与 “result” 应用按位 XOR 运算。只要 “grayCodeS” 右移后大于零，循环就会继续。最后，该函数返回 “result” 值。

BinaryToInteger 函数接受指向 “binaryStr” 数组的链接、“startInd” 初始索引、以及 “endInd” 结束索引作为参数。它将数字从二进制数系统转换为十进制数字系统。该函数用 0 初始化 “result” 变量。然后它执行一个循环，将 “result” 向左移动一位，并将 “binaryStr[i]”（比特位） 的值添加到 “result” 之中。循环从 “startInd” 持续到 “endInd”。最后，该函数返回 “result” 值。

注意，从格雷码转换回来时，会用初始位置和最终位置的索引。这允许从存储所有优化参数的 “行” 中仅提取一定数量的优化参数。我们知道字符串的总长度，包括整数和小数部分，因此我们可以确定数字在染色体的一般字符串中的具体位置，包括整数和小数部分的交界处。

//——————————————————————————————————————————————————————————————————————————————
//Converting a decimal number to a Gray code
void DecimalToGray (ulong decimalNumber, char &array [])
{
  ulong grayCode = decimalNumber ^(decimalNumber >> 1);
  IntegerToBinary(grayCode, array);
}

//Converting a decimal number to a binary number
void IntegerToBinary (ulong number, char &array [])
{
  ArrayResize(array, 0);
  ulong temp;
  int cnt = 0;
  while (number > 0)
  {
    ArrayResize (array, cnt + 1);
    temp = number % 2;
    array [cnt] = (char)temp;
    number = number / 2;
    cnt++;
  }

  ArrayReverse (array, 0, WHOLE_ARRAY);
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Converting from Gray's code to a decimal number
ulong GrayToDecimal (const char &grayCode [], int startInd, int endInd)
{
  ulong grayCodeS = BinaryToInteger(grayCode, startInd, endInd);
  ulong result = grayCodeS;

  while ((grayCodeS >>= 1) > 0)
  {
    result ^= grayCodeS;
  }
  return result;
}

//Converting a binary string to a decimal number
ulong BinaryToInteger (const char &binaryStr [], const int startInd, const int endInd)
{
  ulong result = 0;
  if (startInd == endInd) return 0;

  for (int i = startInd; i <= endInd; i++)
  {
    result = (result << 1) + binaryStr [i];
  }
  return result;
}
//——————————————————————————————————————————————————————————————————————————————

4. 选择方法

在优化算法中，选择是从种群或一组候选者中选择最佳解，以便创建下一代的过程。它在优化方法中起着关键作用。选择具体选择选项不仅会影响算法的搜索能力，还会影响其收敛速度。所有选择方法都有其优点和缺点，在某些算法中可能更有效，而在其它算法中可能效果较低。它们中的每一个，运用时都要取决于特定的搜索策略。

有若干种主要类型的选择用于选择亲本独体，并形成新一代。我们来详研一下它们中的每一个：

• 统一选择是一种亲本选择方法，其中每个独体都有相等的机会被选中。在该方法中，种群中的每个独体被选中进行繁殖的概率相同。平等选择的好处是它确保所有独体都有平等的机会被选中。然而，这种方法没有考虑独体的适应性，因此在找到最佳解方面可能不太有效，尤其是当某些独体的适应性明显高于其它的情况下。在某些情况下，统一选择可能很实用，譬如，当您想要探索解空间的不同区域、或保持种群的高度多样性时。

• 在 排位选择 的情况下，独体根据它们的适应性进行排名，而选择独体的概率取决于其等级。独体的等级越高，被选中的可能性就越大。等级选择可以是完全成比例的，其中选择独体的概率与其等级（序数）成正比，也可以是部分成比例的，其中根据非线性定律，选择独体的概率随着等级的增加而增加。排位选择有很多优点。首先，它有助于保持种群的多样性，因为适应性较差的独体也有机会被选中。其次，它避免了收敛过早的问题，即种群过快收敛到局部最优值。排位选择有助于保持多样性，并探索更广泛的解空间。排位选择类似于统一选择，但更强调选择最适者，且为弱适者也留有选择的机会。
  

• 在 竞胜选择 中，随机选择一个小的独体子集（称为“竞胜”）。从该子集中，选择适应性最高的独体。竞胜的规模判定每场竞赛将有多少独体参与。竞胜选择可以保持种群的多样性，因为即便适应性较差的独体也可由于偶然性而被选中。竞胜选择有若干优势。首先，它允许在亲本选择中考虑随机性，从而促进后代的多样性。其次，它允许从种群的任何领域中选择亲本，包括适应性最好和最差两方的独体。竞胜选择是进化算法中主要的亲本选择方法之一，经常与交叠和突变等其它算子结合使用，从而创建新的后代，并继续种群的进化。
  

• 在 “轮盘选择” 中，每个独体都按其适应性成正比地显示在一个假想的轮盘上。轮盘“旋转”，且选择“指针”指向的独体。独体的适应性越高，它在轮盘中占据的扇区就越大，被选中的机会就越大。轮盘选择允许以与它们的适应性成正比的概率来选择亲本。适应性较高的独体被选中的机会更大，但适应性较差的独体被选中的概率也并非为零。这样就允许保留种群的遗传多样性，并探索解空间的不同区域。然而，轮盘选择可能存在过早收敛的问题，尤其是在独体的适应性差异很大的情况下。适应性强的独体被选中的机会要大得多，这可能导致遗传多样性的丧失，即类似解会“堵塞”种群，并陷入局部最优态。

“精英主义”方法可以与任何选择方法结合使用，作为附加措施。它包括保留当前种群中最好的独体，并将它们原封不动地传给下一代。使用“精英主义”方法可以将最优秀的独体代代相传，这有助于维持高度适应性，并防止有用信息的遗失。这有助于加快算法的收敛速度，并提升求解的品质。

然而，应该考虑到，使用“精英主义”会导致遗传多样性的丧失，特别是当精英主义被设定在较高等级。因此，选择相应的精英值，以便在保留最佳独体和探索解空间之间保持平衡非常重要。

5. “交叠”方法类型

交叠是遗传算法中主要的重要操作之一，它模仿自然进化中的杂交育种。它由两个亲本独体的遗传信息结合组成，创造后代，并将遗传特征传承给子体。交叠不仅作为一种传承信息的方式有意义，而且对算法的组合品质也有巨大影响。

交叠在基因型层级起作用，并允许结合亲本独体的基因，从而产生新的后代。

交叠方法的一般原理如下：

1. 选择亲本独体：从种群中选择两个或若干个独体进行杂交。
   
2. 判定交叠点 ：交叠点决定了亲本染色体分离的位置，以便产生后代。
3. 后代创生：亲本的染色体在交叠点分离，亲本双方的部分染色体结合在一起，产生后代的新基因型。交叠导致一个或多个后代也许拥有来自亲本双方的基因组合。

图例 1. 交叠法的一般原理

我们列出二进制交叠的主要类型：

• 单点交叠 - 两条染色体在随机点分离，在该点之后通过交换亲本染色体的片段产生两个后代。
• 多点交叠 - 类似于单点交叠，但有多个断点，染色体片段在断点之间交换。
  
• 均匀交叠 - 所选择每个子比特位都以相等的概率独立于其亲本那个比特位。
  
• 轮回交叠 - 定义位置轮回将在亲本之间交换，从而保留元素的纯粹性。
• PMX（部分映射交叠）- 保留亲本染色体中元素的相对顺序和位置，针对顺序很重要的问题所用，例如旅行推销员问题。
• ОX（顺序交叠） - 通过保留一个亲本基因的顺序，并按它们出现的顺序从另一个亲本源继承缺失的基因来创建后代。
  

交叠不仅用于二进制表示，还用于实数。实数交叠的主要类型包括：

• 混合交叠（BLX-α） - 创建子项，其值是从由亲本的值、以及扩展该范围的 “α” 参数定义的范围内随机选择的。
• 对称混合交叠（SBX） - 采用不同的概率分布来生成子项，其值位于亲本值之间，同时考虑亲本之间的差异程度。
  
• 实数码交叠 - 针对实数应用算术运算，例如通过对亲本值进行平均或加权求和。
  
• 差分交叠 - 用于不同进化样本，其中把两个独体之间的加权差，添加到第三个向量，从而生成新向量。
  
• 插值交叠 - 通过在亲本值之间进行插值来创建子项，这可能涉及线性或非线性插值。
  
• 正态分布交叠 - 子项是使用围绕亲本值的正态分布生成的，从而允许围绕亲本点探索解空间。
  

6. “突变”方法类型

突变算子是遗传算法中的主要操作之一，针对种群中独体的遗传信息进行随机更改。它有助于探索新的解，并避免陷入局部最优态。

在生物学中，突变极为罕见，通常对后代的影响有限。自然界中每个物种的独体数量达数百万，因此种群的遗传物质非常多样化，当然，除非我们所说的濒危物种（甚至有“瓶颈”项 — 独体的最小数量，低于该值则物种走向灭绝）。与现实自然界不同，在遗传算法的大多数实现中，突变也是一种罕见现象，约为 1-2%。这在遗传算法中尤其重要，因为种群规模通常很小，近亲繁殖可能是一个问题，故此比之物种进化，进化走入死胡同更普遍。在生物学中，我们通常谈论由数百万独体组成的种群，而在遗传算法（以及常见的优化算法）中，我们只处理数十或数百个独体，突变是往种群的基因库里添加新信息的唯一途径。

因此，如果种群中缺少一些遗传信息，突变就提供了引入它的机会。

如此，突变起着若干重要的作用：

1. 研究新的解 - 这允许算法探索问题的潜在新解，而这也许会超出由交叠探索的解空间。突变允许算法在解空间中 “跳跃”，并发现新的选项。
2. 维护遗传多样性 - 若无突变，算法可能会遇到收敛到局部最优态的问题，其中所有独体都有相似的遗传信息。突变允许随机变化，这有助于避免过早收敛，并维持种群的多样性。
3. 克服进化走入死胡同 - 在进化过程中，遗传算法有时会卡在进化的死胡同之中，解空间耗尽，无法达到更佳解。突变可引入随机变化来帮助克服走入死胡同，这样能够开辟新的可能性，并允许算法前行。

突变概率太高会导致算法退化为随机搜索，而概率太低又会导致收敛问题、和多样性的丧失。

对于由二进制表示的算法，可以区分以下类型的突变方法：

• 单点突变 - 二进制字符串中一个随机选择比特位的值被翻转。例如，如果我们有字符串 “101010”，那么单点变化可以将其更改为 “100010”。
• 多点突变 - 选择二进制字符串中的多个随机位置，并将这些位置的值翻转。例如，如果我们有字符串 “101010”，那么多点变化可以将其更改为 “100000” 或 “001010”。
  
• 基于概率的（随机）突变 - 突变时，每个比特位都有一定的变化概率。
  
• 完全翻转 - 二进制字符串中比特位完全翻转。例如，如果我们有字符串 “101010”，则翻转会将其更改为 “010101”。
• 点翻转 - 随机选择基因序列中的一个断点，染色体于该点被切分为两部分，而后各部分互换。  

图例 2. 基于概率的突变

以下类型的突变在具有实数表示的优化算法中被区分。我不会详细讨论它们：

• 随机突变算子。
• 高斯突变算子。
• 算术实数蠕变算子。
• 几何实数蠕变算子。
• 幂突变算子。
• Michalewicz 的非均匀算子。
• 动态突变算子。

一般来说，在所有优化算法中，如果个体（独体）之间没有信息交换，则任何旨在改变搜索空间组成部分的操作都可以称为突变。根据算法的某种搜索策略，它们通常非常具体。

7. 总结

这是关于《二进制遗传算法》文章的第一部分，其中我们不仅研究了该算法中所用的几乎所有方法，还研究了其它种群优化算法中用到的几乎所有方法，即使它们没有使用术语“选择”、“交叠”、和“突变”。通过很好地研究和理解这些方法，我们将能够更有意识地处理优化问题，并且也许会引发实现和修改已知算法、以及创建新算法的新思路。我们还研究了在优化算法中表示信息的不同方式，它们的优点和缺点，这也许会导致新的思路和全新的方式。