第21章 遗传算法
遗传算法是基于达尔文进化论和孟德尔遗传学说的模拟生物进化过程的计算模型。遗传算法通过对染色体的选择、交叉和变异3种基本操作，仿效生物遗传过程遗传物质基因的重组、突变和变异3种方式。控制生物遗传的物质单位称为基因，因此，遗传算法是在基因的水平上模拟生物的进化行为。霍兰创立的遗传算法是多种进化计算的基础，已成为许多智能优化算法的重要基石。本章介绍遗传算法及原对偶遗传算法的原理、实现。
21.1 遗传算法的提出
遗传算法（Genetic Algorithm，GA）是1975年由霍兰（J.H.Holland）教授提出的[65]。它是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，其目的：一是抽取和解释自然系统的自适应过程；二是设计具有自然系统机理的人工系统。霍兰被称为“遗传算法之父”，至今遗传算法一直被认为是智能优化算法的基础。
遗传算法已广泛应用于多个领域，如函数优化、组合优化、生产调度问题、自动控制、机器人学、图像处理、多机器人路径规划等。改进的原对偶遗传算法在边坡稳定性分析方面获得了应用。
21.2 遗传算法的优化原理
19世纪上半叶达尔文创立的进化论，曾被作为生物界及人类文明史上的一个里程碑，1859年英国生物学家达尔文（C.R.Darwin）发表了巨著《物种起源》，提出了物竞天择，适者生存、不适者淘汰的以自然选择为基础的生物进化论，指出生物的发展和进化有3种主要形态：遗传、变异和选择。1966年，奥地利植物学家孟德尔（G.Mendel）发表著名论文《植物杂种实验》，阐明了生物的遗传规律。
地球上的生物都是经过长期进化而发展起来的，根据达尔文的自然选择学说：地球上的生物具有很强的繁殖能力，在繁殖过程中大多数通过遗传使物种保持相似的后代，部分由于变异产生差别，甚至产生新物种。由于大量繁殖，生物数目急剧增加，但自然界资源有限，为了生存，生物之间展开竞争，适应环境的、竞争能力强的生物就生存下来，不适应者就消亡，通过不断竞争和优胜劣汰，生物在不断地进化。
遗传算法的基本思想是借鉴生物进化的规律，通过繁殖—竞争—再繁殖—再竞争实现优胜劣汰，使问题一步步逼近最优解；或者说进化算法是仿照生物进化过程，按照优胜劣汰的自然选择优化的规律和方法，来解决科学研究、工程技术及管理等领域用传统的优化方法难以解决的优化问题。
21.3 生物的遗传及遗传算法的基本概念
构成生物体的最小结构与功能单位是细胞。细胞是由细胞膜、细胞质和细胞核组成的。细胞核由核质、染色质、核液三者组成，是遗传物质存储和复制的场所。细胞核位于细胞的最内层，它内部的染色质在细胞分裂时，在光谱显微镜下可以看到产生的染色体。染色体主要由蛋白质和脱氧核糖核酸（DNA）组成，它是一种高分子化合物，脱氧核糖核酸是其基本组成单位。由于大部分在染色体上，可以传递遗传物质，因此，染色体是遗传物质的主要载体。
控制生物遗传的物质单位称为基因，它是有遗传效应的片段。每个基因含有成百上千个脱氧核苷酸在染色体上呈线性排列，这种有序排列代表了遗传信息。生物在遗传过程中，父代的遗传物质（分子）通过复制方式向子代传递遗传信息。此外，在遗传过程中还会发生3种形式的变异：基因重组、基因突变和染色体变异。基因重组是指控制物种性状的基因发生了重新组合；基因突变是指基因分子结构的改变；染色体变异是指染色体结构或数目上的变化。
下面介绍遗传算法的基本概念。
（1）染色体：遗传物质的主要载体，是多个遗传因子的集合。
（2）基因：遗传操作的最小单元，基因以一定排列方式构成染色体。
（3）个体：染色体带有特征的实体。
（4）种群：多个个体组成群体，进化之初的原始群体称为初始种群。
（5）适应度：用来估计个体好坏程度的解的目标函数值。
（6）编码：用二进制码字符串表达所研究问题的过程（除二进制编码外，还有浮点数编码等）。
（7）解码：将二进制码字符串还原成实际问题解的过程。
（8）选择：以一定的概率从种群中选择若干对个体的操作。
（9）交叉：把两个染色体换组的操作，又称重组。
（10）变异：让遗传因子以一定的概率变化的操作。
21.4 遗传算法的基本操作
遗传算法的基本操作过程如图21.1所示。
1. 选择
从种群中按一定标准选定适合做亲本的个体，通过交配后复制出子代。选择首先要计算个体的适应度，再根据适应度不同，有多种选择方法。
（1）适应度比例法：利用比例于各个个体适应度的概率决定于其子孙遗留的可能性。
（2）期望值法：计算各个个体遗留后代的期望值，然后减去0.5。
（3）排位次法：按个体适应度排序，对各位次预先已被确定的概率决定遗留为后代。
（4）精华保存法：无条件保留适应度大的个体，不受交叉和变异的影响。
（5）轮盘赌法：类似于博采中的轮盘赌，按个体的适应度比例转化为选中的概率。
2. 交叉
交叉是把两个染色体换组（重组）的操作，交叉有多种方法，如单点交叉、多点交叉、部分映射交叉（PMX）、顺序交叉（OX）、循环交叉（CX）、基于位置的交叉、基于顺序的交叉和启发式交叉等。
图21.1 遗传算法的基本操作过程
3. 变异
变异是指基因0、1以一定的概率施行0→1、1→0的操作。变异有局部随机搜索的功能，相对变异而言，交叉具有全局随机搜索的功能。交叉和变异操作有利于保持群体的多样性，避免在搜索初期陷于局部极值。
在选择、交叉和变异3个基本操作中，选择体现了优胜劣汰的竞争进化思想，而优秀个体从何而来，还靠交叉和突然变异操作获得，交叉和变异实质上都是交叉。
21.5 遗传算法的求解步骤
下面通过一个求解二次函数最大值的例子来熟悉遗传算法的步骤。
【例21.1】 利用遗传算法求解二次函数f（x）=x2的最大值，设x∈［0，31］。此问题的解显然为x=31，用遗传算法求解步骤如下。
（1）编码。用二进制码字符串表达所研究的问题称为编码，每个字符串称为个体。相当于遗传学中的染色体，在每一遗传代次中个体的组合称为群体。由于x的最大值为31，所以只需5位二进制数组成个体。
（2）产生初始种群。采用随机方法，假设得出初始群体分别为01101、11000、01000、10011，其中x值分别对应为13、24、8、19，如表21.1所示。
表21.1 遗传算法的初始群体
（3）计算适应度。为了衡量个体（字符串、染色体）的好坏，采用适应度（Fitness）作为指标，又称目标函数。本例中用x2计算适应度，对于不同x值，适应度如表21.1所示中的f（xi）。
∑f（xi）=f（x1）+f（x2）+f（x3）+f（x4）=1170
平均适应度
反映群体整体平均适应能力。
相对适应度
反映个体之间优劣性。
显然2号个体相对适应度值最高为优良个体，而3号个体为不良个体。
（4）选择（Selection）又称复制（Reproduction），从已有群体中选择出适应度高的优良个体进入下一代，使其繁殖；删掉适应度小的个体。
本例中，2号个体最优，在下一代中占两个，3号个体最差删除，1号与4号个体各保留一个，新群体分别为01101，11000，11000，10011。对新群体适应度计算如表21.2所示。
由表21.2可以看出，复制后淘汰了最差个体（3号），增加了优良个体（2号），使个体的平均适应度增加。复制过程体现优胜劣汰原则，使群体的素质不断得到改善。
表21.2 遗传算法的复制与交换
（5）交叉（Crossover）又称交换、杂交。虽然复制过程的平均适应度提高了，但不能产生新的个体，模仿生物中杂交产生新品种的方法，对字符串（染色体）的某些部分进行交叉换位。对个体利用随机配对方法决定父代，如1号和2号配对；3号和4号配对，以3号和4号交叉为例：经交叉后出现的新个体3号，其适应度高达729，高于交换前的最大值576，同样1号与2号交叉后新个体2号的适应度由576增加为625，如表21.2所示。此外，平均适应度也从原来的421提高到439，表明交叉后的群体正朝着优良方向发展。
（6）突变（Mutation），又称变异、突然变异。在遗传算法中模仿生物基因突变的方法，将表示个体的字符串某位由1变为0，或由0变为1。例如，将个体10000的左侧第3位由0突变为1，则得到新个体为10100。
在遗传算法中，突变由事先确定的概率决定。一般，突变概率为0.01左右。
（7）重复步骤（3）～步骤（6），直到得到满意的最优解。
从上述用遗传算法求解函数极值过程可以看出，遗传算法仿效生物进化和遗传的过程，从随机生成的初始可行解出发，利用复制（选择）、交叉（交换）、变异操作，遵循优胜劣汰的原则，不断循环执行，逐渐逼近全局最优解。
实际上给出具有极值的函数，可以用传统的优化方法进行求解，当用传统的优化方法难以求解时，甚至不存在解析表达隐函数不能求解的情况下，用遗传算法优化求解就显示出巨大的潜力。
21.6 原对偶遗传算法
遗传算法已广泛应用于求解各类静态优化问题。近年来，许多研究者提出了多种改进策略，将GA用于求解动态优化问题。2003年，Shengxiang Yang提出了原对偶遗传算法（Primal-Dual Genetic Algorithm，PDGA）用于解决动态优化问题[66]。
在PDGA的种群中，直接记录的染色体称为初始染色体，也称原染色体。在给定距离空间中，两个染色体之间的海明距离指的是这两个染色体对应基因位点的值的不同个数。与原染色体最大海明距离的染色体称为对偶染色体，即x′=dual（x）；dual（·）是原对偶映射（Primal-Dual Mapping，PDM）的函数。在PDM运算时，设计为染色体的每一位都要参与计算。
在种群进行遗传运算后，将其中相对较差的个体进行对偶映射。对于任何原染色体，如果它的对偶染色体更优秀，则原染色体将被其对偶染色体替代；否则原染色体保留。这样，种群中一些较差的个体将有机会被较好的新个体替代，而较好的个体也有机会保留在种群中。
在二进制空间中，考虑0-1编码的GA，采用海明距离作为PDM运算函数。这样原染色体x=（x1，x2，…，xL）∈I=｛0，1｝L（L为染色体的长度），它的对偶染色体
，
，其中
。在一对原对偶染色体中，如果对偶染色体优于原染色体，则这样的原对偶映射被称为有效映射，反之称为无效映射。
在PDGA中，当产生一个中间种群P（t）并完成常规的遗传运算（交叉变异运算）之后，再从P（t）中选择一定数量D（t）的个体，并计算它们的对偶染色体。对于任何x∈D（t），如果它的对偶染色体x′适应度值更大，则x将被x′所取代；否则x被保留下来。也就是说，只有有效的PDM运算才能够使好的对偶染色体有机会传递到下一代种群中，从而体现了一种显性机制。这样既有助于增强种群的多样性，保持种群的搜索能力；又不会影响当前种群的迭代过程，保持种群的开发能力。
原对偶遗传算法的伪码描述如下。
