1 引言

  本次学习报告主要介绍基本遗传算法的详细过程以及三种遗传算法的改进算法，旨在回顾和整理这一学期习得的部分知识。在撰写报告的过程中，会在其中增加一些个人的思考，这些思考主要基于过去所学的知识，目的在于寻找知识与知识之间的联系。由于本人能力所限，如有不当之处，恳请读者指正并提出宝贵的意见。

2 基本思想及发展历史

  遗传算法来源于达尔文进化论和群体遗传学，由美国的Holland教授于1975年首先提出。遗传算法既是经典的启发式算法，同时也是非确定性的拟自然算法，它为复杂系统的优化提供了一种新思路，对于诸多NP-Hard问题，遗传算法都有不错的表现。简而言之，我发现，遗传算法参考了生物遗传过程，并用于解决最优化的问题。实际上，这里的“生物遗传”就是高中生物所学的基因学问题。有趣的是，我们目前学到的某些算法均参考了生物学的相关知识，比如西瓜书第五章所介绍的BP神经网络。在链式法则和参数寻优过程中，连接权重w和阈值θ的计算对应正是我们高中所学的神经元部分知识，这可能也体现了跨学科思维。

图1 神经元结构

  又比如我在看过赵军团队的《知识图谱》后，利用放缩的思想，发现整个知识图谱的构建过程，可能类似于学生做英语阅读理解的思维过程。在此举一个可能不太恰当的例子，我在阅读之前需要找定位词（命名实体识别），并且尽可能找到关键词之间的关系（关系抽取），之后在回到原文中找到相关段落句子，并根据一些表达情感的定语做适当的推理得到答案（知识推理），以此类推，当做完整篇文章之后，我也对这片文章的脉络有了一个初步的认知，并在脑中建立起对应的框架。

图2 知识图谱生命周期

  说回遗传算法，它主要借用生物进化中“适者生存”的规律。在遗传算法中，染色体对应的是数据或数组，通常是由一维的串结构数据来表示的。遗传算法处理的是染色体，或者称为基因型个体。一定数量的个体组成了群体。群体中个体的数量称为种群的大小，也叫种群的规模。各个个体对环境的适应程度叫适应度。适应度大的个体被选择进行遗传操作产生新个体，体现了生物遗传中适者生存的原理。选择两个染色体进行交叉产生一组新的染色体的过程，类似生物遗传中的婚配。编码的某一个分量发生变化的过程，类似于生物遗传中的变异。
  遗传算法包含两个数据转换操作，一个是从表现型到基因型的转换，将搜索空间中的参数或解转换成遗传空间中的染色体或个体，这个过程称为编码。另一个是从基因型到表现型的转换，即将个体转换成搜索空间中的参数，这个过程称为解码。图3是总结的遗传算法模拟生物遗传过程的相关环节。

图3 模拟生物进程总结

  表1是整理的遗传算法发展历史。

表1 遗传算法发展历史

时间	人名	研究成果
1965年	Holland	首次提出人工遗传操作的重要性
1967年	Bagley	提出选择、交叉和变异操作；引入适应度定标概念；首次提出遗传算法自我调整概念，即引入交叉和变异的概率
1971年	Hollstien	第一个把遗传算法用于函数优化
1975年	Holland	系统阐述遗传算法基本理论和方法，并提出模式理论

3 基本遗传算法详细步骤

  图4是总结的一次迭代的遗传算法流程，接下来将围绕该图进行算法步骤阐述。

图4 基本遗传算法流程总结

3.1 编码

  由于遗传算法不能直接处理问题空间的参数，因此，必须通过编码将要求解的问题表示成遗传空间的染色体或个体。该部分操作类似于自然语言处理中，词表示成词向量，这样我们就可以在特征空间中处理自然语言。对一个具体的应用问题如何编码是应用遗传算法的首要问题，也是遗传算法应用的难点。实际上，还不存在一种通用的编码方法，特殊的问题往往采用特殊的方法。图5是常见的编码方法的总结。

图5 编码方法总结

  其中，位串编码是将问题空间的参数编码为一维排列的染色体的方法，称为一维染色体编码方法。一维染色体编码中最常用的符号集是二值符号集{0,1}，即采用二进制编码。实际上，整理之后发现，其余的方法都是在解决二进制编码的不足之处。
  比如，二进制编码的缺点有二：一是相邻整数的二进制编码可能具有较大的Hamming距离（例如，15和16的二进制表示为01111和10000，因此算法从15改进到16必须改变所有的位），这种缺陷造成了Hamming悬崖，降低了遗传算子的搜索效率；二是在求解高维优化问题时，二进制编码将非常长，从而使得算法的搜索效率很低。
  针对缺点一，可以采用Gray编码，也就是说将二进制编码通过一次异或变换进行转换，这样会克服二进制编码的Hamming悬崖。针对缺点二，可以采用实数编码，即用若干实数表示一个个体，然后在实数空间上进行遗传操作。

3.2 初始群体设定

  由于遗传算法是对群体进行操作的，所以，必须为遗传操作准备一个由若干初始解组成的初始群体。群体设定主要包括两个方面：初始种群的产生和种群规模的确定。

图6 群体设定步骤总结

  初始种群的个体是随机产生的，但最好采用如下策略设定：一是根据问题固有知识，设法把我最优解所占空间在整个空间中的分布范围，然后，在此分布范围内设定初始群体；二是先随机产生一定数目的个体，然后从中挑选最好的个体（类似于种子实体）加入到初始群体中，这种过程不断迭代，直到初始群体中个体数目达到了预先确定的规模。针对于策略二这种反复迭代的描述，我认为类似于Bootstrapping策略。
  种群规模影响遗传优化的结果和效率。当种群规模太小时，遗传算法的优化性能一般不会太好，容易陷入局部最优解。实际上，在学习完整个算法后，我发现针对于算法优化的一个关键环节就是在于如何“跳出”局部最优，进而“逼近”全局最优。这就让我联想到BP神经网络关于参数寻优部分的三种“跳出”策略，也可以说是启发式搜索策略。图7是总结的“跳出”策略。

图7 “跳出”策略

  而种群规模太大也会带来弊端：一是群体越大，其适应度评估次数增加，所以计算量也增加，从而影响算法效率；二是群体中个体生存下来的概率大多采用和适应度成比例的方法，当群体中个体非常多时，少量适应度很高的个体会被选择而生存下来，但大多数个体却被淘汰，这会影响配对库的形成，从而影响交叉操作。

3.3 设计适应度函数

  遗传算法遵循自然界优胜劣汰的原则，在进化搜索中基本不用外部信息，而是用适应度值表示个体的优劣，作为遗传操作的依据。适应度函数是用来区分群体中的个体好坏的标准，是算法演化过程的驱动力，是进行自然选择的唯一依据。

图8 适应度函数设计方法

  一般而言，适应度函数是由目标函数变换得到的。最直观的方法就是将待求解优化问题的目标函数作为适应度函数。
  在遗传算法中，将所有妨碍适应度值高的个体产生，从而影响遗传算法正常工作的问题统称为欺骗问题。比如，如果群体中出现超级个体，即该个体的适应值大大超过群体的平均适应值，则按照适应值比例进行选择时，该个体很快就会在群体中占有绝对的比例，从而导致算法较早地收敛到一个局部最优点，这一现象称为过早收敛。这就是一种欺骗问题。
  对适应度函数值域的某种映射变换称为适应度函数的尺度变换（定标）。尺度变换分为线性变换和非线性变换，这里重点介绍线性变换。
  设原适应度函数为f，定标后的适应度函数为f’，则线性变换可采用下式表示为

$$f^{‘}=af+b$$

  系数a和b可以有多种途径设定，但要满足两个条件：

• ①　变换后的适应度的平均值要等于原适应度平均值，以保证适应度为平均值的个体在下一代的期望复制数为1；
• ②　变换后适应度函数的最大值要等于原适应度函数平均值的指定倍数（相当于最小公倍数），以控制适应度最大的个体在下一代中的复制数。

$$\begin{gathered} f_{avg}=a{f}_{avg}+b \\ {C}_{mult}{f}_{avg}=a{f}_{max}+b \end{gathered}$$

  根据上述条件得出的推导公式，通过简单的联立方程组求解即可得出线性变换的系数a和b。
  线性变换法变换了适应度之间的差距，保持了种群的多样性。如果种群里某些个体适应度远远低于平均值时，甚至出现负数，为满足最小适应度非负的条件，可以满足进行如下变换：

$$\begin{gathered} f_{avg}=a{f}_{avg}+b \\ 0=a{f}_{min}+b \end{gathered}$$

  这是我根据书上结果反推得出的推导公式。通过简单的计算即可得出适应值非负条件下的系数a和b。与基础条件不同之处在于将可能为负值的变换后的适应度置为0.

3.4 遗传操作

3.4.1 选择

  选择操作也称为复制操作是从当前群体中按照一定概率选出优良的个体，使他们有机会作为父代繁殖下一代子孙。判断个体优良与否的准则是各个个体的适应度值。
  在遗传算法中，哪个个体被选择进行交叉是按照概率进行的。适应度大的个体被选择的概率大，但不是说一定能够被选上。同样，适应度小的个体被选择的概率小，但也可能被选上。这体现了遗传算法的随机性的特点。
  适应度比例方法非常容易理解，就是按个体适应度在整个种群总适应度的所占比例分配概率。而排序方法根据适应度大小顺序对群体中个体进行排序，然后把事先设计好的概率按排序分配给个体，作为各自的选择概率。选择概率仅仅取决于个体在种群中的序位，而不是实际的适应度值。

图9 选择流程及方法总结
表2 选择个体方法总结

选择个体方法	概述
轮盘赌选择	先按个体的选择概率产生一个轮盘，轮盘每个区的角度与个体的选择概率成比例，然后产生一个随机数，它落入转盘的哪个区域就选择相应的个体交叉
锦标赛选择	从群体中随机选择k个个体，将其中适应度最高的个体保存到下一代。这一过程反复执行，直到保存到下一代的个体数达到预先设定的数量为止
最佳个体保存方法	把群体中适应度最高的一个或者多个个体不进行交叉而直接复制到下一代中，保证遗传算法终止时候得到的最后结果一定是历代出现过的最高适应度的个体

3.4.2 交叉

  当两个生物体配对或者复制时，它们的染色体相互混合，产生一个由双方基因组成的全新的染色体组。这一过程称为重组或者交叉。这里的交叉操作就是高中生物中的AB和Ab进行交配产生新的基因型的过程。

图10 交叉算子总结

  简单描述部分匹配交叉PMX。先依据均匀随机分布产生两个交叉点，定义两点之间的区域为一匹配区域，并使用位置交换操作交换两个父串的匹配区域。现在举例说明：

A = 9 8 4 | 5 6 7 | 1 3 2 B = 8 7 1 | 2 3 9 | 5 4 6

  首先交换A和B的两个匹配区域，得到

A = 9 8 4 | 2 3 9 | 1 3 2 B = 8 7 1 | 5 6 7 | 5 4 6

  显然，根据出现的重复任务，这就是非法调度。解决方法是将匹配区域外出现的重复任务，按照匹配区域内的位置映射关系进行交换，进而使排列成为可行调度。进一步解释，根据匹配区域的位置位置映射关系，即“2-5、3-6、9-7”，先对A中出现的重复任务“2、3”和“9”进行替换（不存在顺序关系，“3，2”也是重复的），即替换成“5，6，7”，然后将替换掉的字符“2，3，9”补到对应的B中所出现空缺的位置。最后结果即为

A = 7 8 4 | 2 3 9 | 1 6 5 B = 8 9 1 | 5 6 7 | 2 4 3

  实验表明交叉概率通常取值为0.7左右是理想的。每次从群体中选择两个染色体，同时生成0和1之间的一个随机数，然后根据这个随机数确定这两个染色体是否需要交叉。如果随机数低于交叉概率，就进行交叉。

3.4.3 变异

  对于变异操作，可以理解为高中生物中的加一段染色体或者替换染色体中的某一基因段等操作。在遗传算法中，变异是将个体编码的一些位进行随机变化。变异算子的基本内容是对群体中的个体串的某些基因座上的基因值作变动。变异操作是按位进行的，即把某一位的内容进行变异。变异概率是在一个染色体中按位进行变化的概率。主要的变异方法如图11所示。

图11 变异算子总结

  在遗传算法中，变异属于辅助性的搜索操作（在做高中生物时，变异也属于题目需要特别提示的内容，并非必须）。变异概率一般不能大，以防止群体中重要的、单一的基因可能被丢失。实际上，变异概率太大将使得遗传算法趋于纯粹的随机搜索。

4 基本遗传算法总结

  图12为基本遗传算法的流程图。遗传算法是一个利用随机技术来指导对一个编码的参数空间进行高效率搜索的方法，而不是无方向的随机搜索。许多传统搜索方法都是单解搜索方法，遗传算法采用群体搜索策略，即采用同时处理群体中多个个体的方法，同时对搜索空间中的多个解进行评估，从而使遗传算法具有较好的全局搜索性能，减少了陷于局部优解的风险，但不能保证每次都得到全局最优解。显而易见，遗传算法本身十分易于并行化。
  在基本遗传算法中，基本上不用搜索空间的知识或其他辅助信息，而仅仅用适应度函数值来评估个体，并在此基础上进行遗传操作，使种群中个体之间进行信息交换。特别是遗传算法的适应度函数不仅不受连续可微的约束，而且其定义域也可以任意设定。对适应度函数的唯一要求就是能够算出可以比较的正值。

图12 基本遗传算法流程图

5 遗传算法改进

  接下来的遗传算法改进，实际上就是针对与图12的基本遗传算法流程进行改进。下面将简述三种改进算法在哪一环节进行了改进。

5.1 双倍体遗传算法

  上文阐述的基本遗传算法属于单倍体遗传，每个基因型由一条染色体（也就是基因型AB，分别只有一个等位基因A和B）。显然，大多数动物和高级植物都采用双倍体遗传（也就是AaBb），即每个基因型由一对染色体决定。这势必会出现显隐性遗传问题。
  那具体在图12的哪一部分作出调整呢？须知双倍体遗传算法采用显性遗传，并且提供了一种记忆以前有用的基因块功能。
  进一步而言，在选择操作中，按照显性染色体的选择概率将个体复制到下一代群体中；同时，在交叉操作中，两个体的显性染色体和隐形染色体分别进行交叉操作；在变异操作中，显性染色体按照正常的变异概率执行操作，隐形染色体按照较大的概率进行操作。
  与基本遗传算法的一个显著区别在于，执行完上述操作后，会再增加一个显隐性重排操作，因为每一轮迭代之后，并不能确定显性和隐性的在下一轮划分，有了显隐性重排操作，增加了算法的随机性，也提高了隐性染色体里优良基因的存活概率。具体来说，个体中适应度较大的染色体设定为下一轮的显性染色体，适应度较小的染色体设定为下一轮的隐性染色体。

5.2 双种群遗传算法

  双种群遗传算法意在突破平衡态——长时间进化后某些特征处于相对优势的状态，实际上，这再次体现出算法在接近全力“逼近”全局最优，是一个具有优秀扩展性的启发式搜索算法。
  对比图12，主要区别在于双种群同时进行图中操作，但在执行完上述操作后，增加一步杂交操作，即交换种群之间优秀个体所携带的遗传信息，以打破种群内的平衡态以达到更高的平衡态，有利于算法跳出局部最优。
  杂交算子，具体来说，设种群A和种群B，当两种群均完成了选择、交叉和变异操作后，产生一个随机数num，随机选择A中num个个体与A中最优个体，随机选择B中num个个体与B中最优个体，交换两者，打破平衡态。“产生随机数num”又一次体现了算法的随机性。

5.3 自适应遗传算法

  自适应遗传算法的改进关键点在于交叉概率和变异概率，使两概率能随适应度变化自动改变。这样即可保证算法可以跳出局部最优情况，也可以利于优良个体的生存。所以，自适应遗传算法在保持群体多样性的同时，保证遗传算法的收敛性。
  对比图12，区别在于交叉算子中，要使用自适应公式计算交叉概率，然后产生随机数，如果小于计算后的概率，那么交叉该对染色体对；同理，在变异算子中，也使用自适应公式计算变异概率，并产生随机数，若小于计算后的概率，那么变异该染色体。

6 参考文献

• 王万良.人工智能导论(第4版)[M]: 高等教育出版社, 2017.