元启发式算法被用于解决来自经济学、工程学、政治学、管理学等不同领域的实际复杂问题。集中和多样化是元启发式算法的关键元素。在解决实际问题时，需要合理平衡这些元素。大多数元启发式算法都受到生物进化过程、群体行为和物理定律的启发。这些算法广泛分为两类，即基于单解和基于群体的元启发式算法。基于单解的元启发式算法利用单个候选解，并通过局部搜索改进此解。然而，从基于单解的元启发式算法得到的解可能会陷入局部最优。著名的基于单解的元启发式算法包括模拟退火、禁忌搜索（TS）、微正则退火（MA）和引导局部搜索（GLS）。基于群体的元启发式算法在搜索过程中利用多个候选解。这些元启发式算法保持种群中的多样性，避免解在局部最优中停滞。一些知名的基于群体的元启发式算法包括遗传算法（GA）、粒子群优化（PSO）、蚁群算法（ACO）、斑点鬣狗优化器（SHO）、皇帝企鹅优化器（EPO）和海鸥优化（SOA）。

在元启发式算法中，遗传算法（GA）是一种著名的算法，灵感来源于生物进化过程。GA模拟了自然界中的达尔文适者生存理论，由J.H. Holland于1992年提出。GA的基本要素包括染色体表示、适应性选择和生物启发的操作符。

1. 染色体表示（Chromosome Representation）：染色体采用二进制字符串格式。在染色体中，每个位点（染色体上的特定位置）有两种可能的等位基因（基因的变体形式）- 0和1。染色体被视为解空间中的点，这些通过迭代地用遗传操作符（GA算法中的生物启发的操作符）替换其种群来处理。
2. 适应性选择（Fitness Selection）：用于为种群中的所有染色体分配一个值,进行量化表示。
3. 生物启发的操作符（Biological-inspired Operators）：包括选择、变异和交叉。在选择中，染色体根据其适应性值被选中进行进一步处理。在交叉操作符中，选择一个随机位点，改变染色体之间的子序列以创建后代。在变异中，染色体的一些位将根据概率随机翻转。

本文的主要包括如下内容：

1. 阐述了遗传算法（GA）和混合遗传算法的一般框架，并给出了数学表述。
2. 讨论了各种类型的遗传操作符及其优缺点。
3. 探讨了不同变体的遗传算法及其优缺点。
4. 代码实现

本文内容参考于doi: 10.1007/s11042-020-10139-6

遗传算法

经典遗传算法

GA是一种受自然选择启发的优化算法，是一种基于群体的搜索算法，利用了“适者生存”的概思想。通过对种群中的个体迭代使用遗传操作符，生成新的种群。

GA的关键要素包括染色体表示、遗传操作符（选择、交叉、变异）和适应度函数计算。

GA的过程如下：

• 首先，随机初始化一个包含个染色体的种群。计算中每个染色体的适应度。根据适应度值从种群中选择两个染色体，记为和。
• 然后，以交叉概率（）应用单点交叉操作符于和上，产生一个后代。
• 随后，以变异概率（）在产生的后代上应用均匀变异操作符，生成。新的后代被放置在新的种群中。
• 选择、交叉和变异操作将在当前种群上重复，直到新的种群完成。

GA的数学分析如下：

GA通过交叉和变异的概率动态改变搜索过程，并达到最优解，能够评估多个个体并产生多个最优解。因此，GA具有更好的全局搜索能力，交叉公式定义如下：

在上式中，g是代数，G是由种群设定的总进化代数。R在演化代数的增加过程中动态变化并增加。在GA的初始阶段，个体之间的相似性很低，R的值应该很低。在演化的末尾，个体之间的相似性很高，因此 R 的值应该很高。

根据模式定理（Schema theorem），原始模式必须被修改后的模式所取代。为了在种群中保持多样性，在演化的早期阶段，新的模式保留了初始种群。在演化的末尾，将产生适当的模式以防止对优秀遗传模式的任何扭曲 。下面是经典遗传算法的伪代码。

“

输入：

种群大小，。

最大迭代次数，.

输出：

全局最佳解，.

开始

生成包含个染色体的初始种群。

将迭代计数器设为。

计算每个染色体的适应度值。

当时执行以下循环：

根据适应度从初始种群中选择一对染色体。

使用交叉概率对所选的染色体对进行交叉操作。

使用变异概率对产生的后代进行变异操作。

用新生成的种群替换旧种群。

将当前迭代次数增加。

循环结束后，返回最佳解。

结束

”

遗传操作符

遗传算法在搜索过程中使用了多种运算符。这些运算符包括编码方案、交叉、变异和选择。

编码Encoding:

• 二进制编码Binary Encoding
• 八进制编码Octal Encoding
• 十六进制编码Hexadecimal Encoding
• 排列编码Permutation Encoding
• 值编码Value Encoding
• 树编码Tree Encoding

选择Selection:

• 轮盘赌选择Roulette Wheel selection
• 等级选择Rank Selection
• 锦标赛选择Tournament Selection
• 波尔兹曼选择Boltzmann selection
• 随机通用采样Stochastic Universal Sampling

交叉Crossover:

• 单点交叉Single Point Crossover
• K点交叉K-Point Crossover
• 均匀交叉Uniform Crossover
• 部分映射交叉Partially mapped Crossover
• 顺序交叉Order Crossover
• 优先级保持交叉Precedence preserving Crossover
• 洗牌交叉Shuffle Crossover
• 缩减替代交叉Reduced Surrogate Crossover
• 循环交叉Cycle Crossover

变异Mutation:

• 位移变异Displacement Mutation
• 反转变异Inversion Mutation
• 打乱变异Scramble Mutation
• 位翻转变异Bit Flipping Mutation
• 颠倒变异Reversing Mutation

Encoding编码

对于大多数计算问题，编码方案（即，将信息转换为特定形式）起着重要作用。给定的信息必须以特定的位串进行编码。编码方案根据问题域的不同而有所区别。著名的编码方案包括二进制、八进制、十六进制、排列、基于值的和树形编码。

二进制编码是常用的编码方案。每个基因或染色体都被表示为一串1或0 。在二进制编码中，每个位表示解的特征。它提供了更快的交叉和变异操作的实现。然而，将其转换为二进制形式需要额外的工作，算法的准确性取决于二进制转换。位串根据问题的不同而改变。由于存在上位遗传和自然表示，二进制编码方案不适用于一些工程设计问题。

在八进制编码方案中，基因或染色体以八进制数（0-7）的形式表示。在十六进制编码方案中，基因或染色体以十六进制数（0-9，A-F）的形式表示 。排列编码方案通常用于排序问题。在这种编码方案中，基因或染色体由表示位置的数字串表示。在值编码方案中，基因或染色体使用一些值的串表示。这些值可以是实数、整数或字符。这种编码方案在解决使用更复杂值的问题时可能很有帮助，而二进制编码在这些问题中可能会失败。它主要用于神经网络以找到最佳权重。

在树形编码中，基因或染色体由函数或命令的树表示。这些函数和命令可以与任何编程语言相关。这与树状格式中的抑制的表示非常相似]。这种类型的编码通常用于演化程序或表达式。如下是GA的不同编码方案的比较。

Selection选择

选择是遗传算法中的重要步骤，它决定特定的字符串是否参与繁殖过程。选择步骤有时也被称为繁殖操作符。遗传算法的收敛速率取决于选择压力。著名的选择技术包括轮盘赌、排名、锦标赛、波尔兹曼和随机通用采样。

轮盘赌选择将所有可能的字符串映射到一个轮盘上，轮盘的一部分根据它们的适应度值分配给它们。然后随机旋转轮盘以选择参与形成下一代的特定解。然而，它存在许多问题，如其随机性引入的错误。排名选择是轮盘赌选择的修改形式，它使用排名而不是适应度值。根据适应度值给予它们排名，以便每个个体有机会根据它们的排名被选中。排名选择方法降低了过早收敛到局部最小值的可能性。

锦标赛选择技术于1983年由Brindle提出。根据它们的适应度值，从随机轮盘中选择成对的个体。选择后，具有较高适应度值的个体被添加到下一代的池中。在这种选择方法中，如果达到解的最终种群，每个个体将与其他 个体进行比较。随机通用采样（SUS）是对现有轮盘赌选择方法的扩展。它在一代个体的列表中使用一个随机起始点，并以均匀间隔选择新个体 。它为所有个体在参与下一代交叉的机会上平等机会。尽管在旅行商问题的情况下，SUS表现良好，但随着问题规模的增加，传统的轮盘赌选择表现相对较好。

波尔兹曼选择基于熵和蒙特卡洛模拟中使用的采样方法。它有助于解决过早收敛的问题。选择最佳字符串的概率非常高，同时执行时间很短。然而，存在信息丢失的可能性，可以通过精英主义来管理。精英主义选择由 K. D. Jong（1975年）提出，用于改进轮盘赌选择的性能。它确保一代中的精英个体总是传递到下一代。如果在正常选择过程后具有最高适应度值的个体不存在于下一代中，则精英个体也会自动包含在下一代中。

“

Jebari K (2013) Selection methods for genetic algorithms. Abdelmalek Essaâdi University. International Journal of Emerging Sciences 3(4):333–344

”

如下是GA的不同选择方法的比较。

交叉Crossover

交叉操作符用于通过组合两个或更多父代的遗传信息来生成后代。著名的交叉操作符包括单点、双点、k点、均匀、部分匹配、顺序、保持优先级的交叉、洗牌、缩减替代和循环。

在单点交叉中，选择一个随机的交叉点。超过该点的两个父代的遗传信息将互相交换，下图中替换了两个父代的尾部数组位，以得到新的后代。

在双点和k点交叉中，选择两个或更多随机交叉点，并根据已创建的段交换父代的遗传信息。下图是在交叉点之间交换遗传信息的过程。父代的中间段被替换以生成新的后代。

在均匀交叉中，父代不能被分解成段。父代可以被视为每个基因单独处理。我们随机决定是否需要将基因与另一个染色体相同位置的基因交换。下图描述了在均匀交叉操作下的个体交换过程。

部分匹配交叉（PMX）是最常用的交叉操作符之一。它是一种性能比大多数其他交叉操作符更好的操作符。部分匹配（映射）交叉由 D. Goldberg 和R. Lingle 提出，选择两个父代进行交配。一个父代捐赠一部分遗传物质，而另一个父代相应的部分参与形成子代。完成此过程后，剩下的等位基因将从第二个父代复制。

顺序交叉（OX）由Davis于1985年提出。OX从选定的切点将一个（或多个）父代的一部分复制到子代，并用除复制部分之外的值填充剩余空间。针对不同类型的问题，不同的研究人员提出了OX的变体。OX对于排序问题很有用，然而，在旅行商问题的情况下发现OX效率较低。保持优先级的交叉（PPX）在交叉应用之前保留了个体解的顺序。子代初始化为一串随机的1和0，决定是否选择来自两个父代的个体。

洗牌交叉由Eshelman等人提出，以减少其他交叉技术引入的偏差。它在交叉之前洗牌个体解的值，并在执行交叉操作后将其还原，以使交叉点不引入任何偏差。然而，在近年来，这种交叉的利用非常有限。减少替代交叉（RCX）在父代具有相同基因序列的解表示的情况下，减少了不必要的交叉。RCX的基本假设是，如果父代在基因组成上足够多样，GA将产生更好的个体。然而，对于具有相同组成的父代，RCX无法产生更好的个体。循环交叉由Oliver提出。它尝试使用父代生成子代，其中每个元素都占据其父代位置的位置。在第一个循环中，它从第一个父代中获取一些元素。在第二个循环中，它从第二个父代中获取剩余元素，如下图所示。

“

参考文献：

Soon GK, Guan TT, On CK, Alfred R, Anthony P (2013) "A comparison on the performance of crossover techniques in video game," 2013 IEEE international conference on control system. Computing and Engineering, Mindeb, pp 493–498

Mudaliar DN, Modi NK. Unraveling travelling salesman problem by genetic algorithm using m-crossover operator. Image Processing & Pattern Recognition, Coimbatore: International Conference on Signal Processing; 2013. pp. 127–130.

”

如下是GA的不同交叉方法的比较。

变异Mutation

突变是一种操作符，它保持了一代到下一代的遗传多样性。著名的突变操作符包括位移、简单反转和混淆突变。位移突变（DM）操作符在给定个体解内部移动一个子串。位移的位置从给定的子串中随机选择，使得生成的解既有效又具有随机的位移突变。DM的变体有交换突变和插入突变。在交换突变和插入突变操作符中，个体解的一部分分别与另一部分进行交换或插入到另一位置。

简单反转突变操作符（SIM）反转个体解中两个指定位置之间的子串。SIM是一个反转操作符，它反转随机选择的字符串并将其放置在随机位置。混淆突变（SM）操作符以随机顺序放置个体解中指定范围的元素，并检查最近生成的解的适应度值是否有所改善。如下是GA的不同变异方法的比较。

如下是编码方案、突变和交叉技术的最佳组合。均匀和单点交叉可以与大多数编码和突变操作符一起使用。部分匹配交叉与反转突变和排列编码方案一起提供了最佳解决方案。

GA变体

遗传算法的变体主要分为五大类别，即实值编码和二进制编码、多目标、并行、混沌和混合遗传算法。

实值编码和二进制编码的遗传算法

基于染色体的表示方式，遗传算法分为两类，即二进制编码和实值编码的遗传算法。

使用二进制编码来表示GA，被称为二进制遗传算法（BGA）。遗传算法的操作符也经过修改，以执行搜索过程。实值编码的遗传算法（RGA）在各种实际应用中得到了广泛使用。染色体的表示与实际问题密切相关。RGA的主要优势在于其稳健性、效率和准确性。然而，RGA容易过早收敛。研究人员正在致力于改进RGA的性能。大多数RGA是通过修改交叉、变异和选择操作符来开发的。

Multiobjective GA

MOGA是遗传算法的改进版本。MOGA在适应度函数分配方面与GA不同。其余步骤与GA相似。Multiobjective GA的主要目标是以这样的方式在目标空间中生成最优的帕累托前沿，即在不干扰其他适应度函数的情况下，任何适应度函数都不能进一步提高。收敛性、多样性和覆盖性是多目标GA的主要目标。Multiobjective GA大致分为两类，即基于帕累托的和基于分解的多目标GA。

并行遗传算法（GA）

并行遗传算法的动机是通过分布式个体提高计算时间和解决方案质量。并行GA分为三个主要类别，即主从并行GA、细粒度并行GA和多群体粗粒度并行GA。在主从并行GA中，适应度函数的计算分布在多个处理器上。在细粒度GA中，使用并行计算机解决实际问题。遗传算法的基因操作符被限制在其邻域内。然而，个体之间允许相互作用。在粗粒度GA中，个体在子群体之间进行交换，并行GA面临的主要挑战是最大化内存带宽并安排线程以利用GPU的强大性能。

混沌遗传算法

遗传算法的主要缺点是过早收敛，为了解决这个问题，混沌系统被引入到GA中，混沌遗传算法的多样性消除了过早的收敛，交叉和变异操作符可以被混沌映射替代。

融合遗传算法

遗传算法（GA）可以轻松与其他优化方法混合，以提高其性能，例如图像去噪方法、化学反应优化等。将GA与其他方法混合的主要优势包括更好的解质量、更高的效率、可行解的保证以及优化的控制参数。从文献中可以看出，GA的采样能力受到种群大小的极大影响。为了解决这个问题，局部搜索算法，如记忆算法、巴尔德温算法、拉马克算法和局部搜索，已与GA集成。这种集成提供了强化和多样化之间的适当平衡。GA中的另一个问题是参数设置。找到合适的控制参数是一项繁琐的任务。此外，其他元启发式技术可以与GA一起用于解决这个问题。

GA算法的应用

遗传算法（GAs）以其在解决多个NP难问题方面的高准确性而著称。它们在几个领域都取得了成功的应用。

代码实现：图片着色问题

在图论中，图着色是图标记的一种特殊情况；它是对图的元素传统上称为“颜色”的标签的分配，受到一定约束的影响。在其最简单的形式中，它是对图的顶点进行着色的一种方式，使得相邻的两个顶点不具有相同的颜色；这被称为顶点着色。同样，边着色将颜色分配给每条边，以确保相邻的两条边不具有相同的颜色，而平面图的面着色将颜色分配给每个面或区域，以确保共享边界的两个面没有相同的颜色。

代码获取方式：关注本公众号，回复“遗传算法”免费获取