下载掌阅APP，畅读海量书库
立即打开
遗传算法（Genetic Algorithms，GA）是一种新近发展起来的搜索最优解方法，它模拟生命进化机制，即模拟自然选择和遗传进化中发生的繁殖、交配和突变现象，从任意一个初始种群出发，通过随机选择、交叉和变异操作，产生一群新的更适应环境的个体，使群体进化到搜索空间中越来越好的区域。这样一代一代不断繁殖、进化，最后收敛到一群最适应环境的个体上，求得问题的最优解。遗传算法对于复杂的优化问题无须建模和进行复杂运算，只要利用遗传算法的三种算子就能得到最优解。
遗传算法进化过程的基本流程如下：
种群初始化（随机分布个体）→交叉（更新个体）→变异（更新个体）→适应度计算（评价个体）→选择（群体更新）。
经典遗传算法的一次进化过程示意图如图2-2所示，该图给出了第 n 代群体经过选择、交叉、变异，生成第 n +1代群体的过程。
从图2-2可见，遗传算法涉及一些基本概念，下面对这些概念进行解释。
图2-2 遗传算法的一次进化过程
个体（Individual）：遗传算法所处理的基本对象、结构。
群体（Population）：个体的集合。
位串（Bit String）：个体的表示形式，对应于遗传学的染色体（Chromosome）。
基因（Gene）：位串中的元素，表示不同的特征，对应于生物学中的遗传物质单位，以DNA序列形式把遗传信息译成编码。
基因位（Locus）：某一基因在染色体中的位置。
等位基因（Allele）：表示基因的特征值，即相同基因位的基因取值。
位串结构空间（Bit String Space）：等位基因任意组合构成的位串集合，基因操作在位串结构空间进行，对应于遗传学中的基因型的集合。
参数空间（Paremeters Space）：位串空间在物理系统中的映射，对应于遗传学中的表现型的集合。
适应值（Fitness）：某一个体对于环境的适应程度，或者在环境压力下的生存能力，取决于遗传特性。
选择（Selection）：在有限资源空间上的排他性竞争。
交叉（Crossover）：一组位串或染色体上对应基因段的交换。
变异（Mutation）：染色体水平上的基因变化，可以遗传给子代个体。
为了说明这些术语的含义，对个体进行形象化表示，则个体结构如图2-3所示。
图2-3 个体结构（由位串或染色体组成）
采用遗传算法进行问题求解的基本步骤如下。
① 编码：遗传算法在求解之前，先将问题解空间的可行解表示成遗传空间的基因型串结构数据，串结构数据的不同组合构成了不同的可行解。
② 生成初始群体：随机产生 N 个初始串结构数据，每个串结构数据成为一个个体， N 个个体组成一个群体，遗传算法以该群体作为初始迭代点。
③ 适应度评估检测：根据实际标准计算个体的适应度，评判个体的优劣，即该个体所代表的可行解的优劣。
④ 选择算子：从当前群体中选择优良的（适应度高的）个体，使它们有机会被选中进入下一次迭代过程，舍弃适应度低的个体，体现了进化论的“适者生存”原则。
⑤ 交叉算子：遗传操作，下一代中间个体的信息来自父辈个体，体现了信息交换的原则。
⑥ 变异算子：随机选择中间群体中的某个个体，以变异概率 P m 的大小改变个体某位基因的值。变异为产生新个体提供了机会。
经典的遗传算法流程图如图2-4所示，算法完全依靠三个遗传算子进行求解，当停止运算条件满足时，达到最大循环次数，同时最优个体不再进化。
图2-4 遗传算法流程图
所谓编码，就是指将问题的解空间转换成遗传算法所能处理的搜索空间。进行遗传算法求解前，必须对问题的解空间进行编码，以使它能够被遗传算法的算子操作。例如，用遗传算法进行模式识别，将样品标识后，各个样品的特征及所属的类别构成了聚类问题的解空间。编码是应用遗传算法时要解决的首要问题，也是关键问题。它决定了个体染色体中基因的排列次序，也决定了遗传空间到解空间的变换解码方法。编码的方法也影响到了遗传算子（选择、交叉、变异）的计算方法。好的编码方法能够大大提高遗传算法的效率。
如何确定编码没有统一的标准，Dejong曾给出两条参考原则。
有意义积木块编码原则：易于产生与所求问题相关，且具有低阶、短定义、长模式的编码方案。模式是指具有某些基因相似性的个体集合，而具有最短定义长度、低阶、确实硬度较高的模式称为构造优良个体的积木块或基因块。可以将该原则理解为应采用易于生成高适应度个体的编码方案。
最小字符集编码原则：能使问题得到自然表示，或其描述具有最小编码字符集的编码方案。
这两条仅仅是指导原则，并不一定适应于所有场合。在实际应用中，对编码方法、遗传算子等应统一考虑，以获得一种描述方便、计算效率高的方案。
常用的编码方法有以下几种。
（1）二进制编码
二进制编码是遗传算法编码中最常用的方法。其编码符号集是二值符号集 {0，1}，其个体基因是二值符号串。
二进制编码中符号串的长度与问题的求解精度相关。设某一参数 x 的变化范围是[ a ， b ]，编码长度为 n ，则编码精度为（ b-a ） / （2 n -1）。
二进制编码、解码操作简单易行，遗传操作便于实现，符合最小字符集编码原则。
（2）符号编码方法
符号编码方法是指个体染色体串中的基因值取自一个无数值意义、只有代码含义的符号集。这个符号集可以是一个字母表，如 {A，B，C，…}，也可以是一个序号表 {1，2，3，…}，其优点是符合有意义的积木块原则，便于在遗传算法中利用所求问题的专门知识。
（3）浮点数编码
浮点数编码方案中个体的每个基因值是一个浮点数，一般采用决策变量的真实值。该方法适合在遗传算法中表示较大的数，应用于高精度的遗传算法，搜索空间较大，改善了算法的复杂性。
在遗传算法中，模拟自然选择的过程主要是通过评估函数CalculateObjectValue()和适应度函数CalculateFitnessValue()来实现的。前者计算每个个体优劣的绝对值，后者计算每个个体相对于整个群体的相对适应性。个体适应度的大小决定了它继续繁衍还是消亡。适应度高的个体被复制到下一代的可能性高于适应度低的个体。
适应度函数是整个遗传算法中极为关键的一部分。好的适应度函数能够指导我们从非最优的个体进化到最优个体，并且能够用来解决一些遗传算法中的问题，比如过早收敛与过慢结束的矛盾。
如果个体的适应度值很高，大大高于个体适应度均值，它将得到更多的机会被复制，所以有可能在没有达到最优解甚至没有得到可接受解的时候，就因为某个或某些个体的副本充斥整个群体而过早地收敛到局部最优解，失去了找到全局最优解的机会。这就是所谓的过早收敛问题。要解决过早收敛问题，就要调整适应度函数，对适应度值的范围进行压缩，防止那些“过于适应”的个体过早地在整个群体中占据统治地位。
与之相对应，遗传算法中还存在着结束缓慢的问题。也就是说，在迭代许多代以后，整个种群已经大部分收敛，但是还没有稳定的全局最优解。整个种群的平均适应度值较高，而且最优个体的适应度值与全体适应度均值间的差别不大，这就导致没有足够的力量推动种群遗传进化找到最优解。解决该问题的方法是扩大适应度函数值的范围，拉大最优个体适应度值与群体适应度均值的距离。解决该问题的方法还有适应度函数缩放方法、适应度函数排序法、适应度窗口技术、锦标赛选择等方法。
遗传算法中的“选择”算子用来确定如何从父代群体中按照某种方法，选择哪些个体作为子代的遗传算子。选择算子是建立在对个体适应度进行评价的基础上的，目的是避免基因损失，提高全局收敛性和计算效率。常用选择算子的操作方法有以下几种。
（1）赌轮选择方法
赌轮选择方法又称比例选择方法，其基本思想是个体被选择的概率与其适应度值大小成正比。由于选择算子是随机操作，这种算法的误差比较大，有时适应度最高的个体也不会被选中。各个样品按照其适应度值占总适应度值的比例组成面积为1的一个圆盘，指针转动停止后，指向的个体将被复制到下一代，适应度高的个体被选中的概率大，但是适应度低的个体也有机会被选中，这样有利于保持群体的多样性。
（2）排序选择法
排序选择法是指，在计算每个个体的适应度之后，根据适应度大小对群体中的个体排序，再将事先设计好的概率表分配给各个个体，所有个体按适应度大小排序，选择概率与适应度无关。
（3）最优保存策略
最优保存策略的基本思想是：适应度最高的个体尽量保留到下一代群体中。其操作过程如下：
① 找出当前群体中适应度最高和最低的个体；
② 用迄今为止最好的个体替换最差的个体；
③ 若当前个体适应度比总的迄今为止最好的个体适应度还要高，则用当前个体替代总的最优个体。
该策略保证最优个体不被破坏，能够被复制到下一代，是遗传算法收敛性的一个重要保证条件。另一方面，它也会使一个局部最优解不易被淘汰而迅速扩散，导致算法的全局搜索能力不强。
在进化计算中，交叉是遗传算法保留原始性特征所独有的。遗传算法交叉算子模仿自然界有性繁殖的基因重组过程，其作用在于将原有的优良基因遗传给下一代个体，并生成包含更复杂结构的新个体。交叉操作一般分为以下几个步骤：
① 从交配池中随机地取出要交配的一对个体；
② 根据位串长度 L 对要交配的这对个体，随机地选取一个或多个整数作为交叉位；
③ 根据交叉概率 P c （0＜ P c ≤1）实施交叉操作，配对个体在交叉位置相互交换各自的部分内容，从而形成一个新的个体。
通常使用的交叉算子有一点交叉、两点交叉、多点交叉和一致交叉等。
（1）一点交叉
一点交叉指在染色体中随机地选择一个交叉点，如图2-5（a）所示，交叉点在第五位，然后第一个父辈交叉点前的位串和第二个父辈交叉点及其以后的位串组成一个新的染色体，第二个父辈交叉点前的位串和第一个父辈交叉点及其以后的位串组合成另一个新的染色体，如图2-5（b）所示。
图2-5 一点交叉示意图
（2）两点交叉
两点交叉就是在父代的染色体中随机选择两个交叉点，如图2-6（a）所示，然后交换父代染色体中交叉点间的基因，得到下一代个体，如图2-6（b）所示。
图2-6 两点交叉示意图
（3）一致交叉
在这种方法中，子代的每一位随机地从两个父代中的对应位取得。
变异操作模拟自然界生物体进化中，染色体上某位基因发生的突变现象，从而改变染色体的结构和物理性状。变异是遗传算法中保持物种多样性的一个重要途径。它以一定的概率选择个体染色中的某一位或几位，随机地改变该位的基因值，以达到变异的目的。
在遗传算法中，由于算法执行过程中的收敛现象，可能使整个种群染色体上的某位或某几位都收敛到固定值。如果整个种群所有的染色体中有 n 位取值相同，则单纯的交叉算子所能够达到的搜索空间只占整个搜索空间的（1 / 2） n ，大大降低了搜索能力，所以，引进变异算子改变这种情况是必要的。生物学家一般认为变异是更为重要的进化方式，并且认为只通过选择与变异就能进行生物进化的过程。
在遗传算法的运行过程中，存在着对其性能产生重大影响的一组参数，这组参数在初始阶段和群体进化过程中需要合理地选择和控制，以使遗传算法以最佳的搜索轨迹达到最优解。主要参数有染色体位串长度 L 、群体规模 N 、交叉概率 P c 和变异概率 P m 。
（1）位串长度 L
位串长度的选择取决于特定问题解的精度。要求精度越高，位串越长，但需要更多的计算时间。为了提高运行效率，可采用变长位串的编码方法。
（2）群体规模 N
大群体含有较多的模式，为遗传算法提供了足够的模式采样容量，可以改善遗传算法的搜索质量，防止成熟前收敛。但是大群体增加了个体适应性的评价计算量，从而降低了收敛速度。一般情况下专家建议 N =20～200。
（3）交叉概率 P c
交叉概率控制着交叉算子使用的频率，在每一代新的群体中，需要根据交叉概率 P c 进行交叉操作。交叉概率越高，群体中结构变化的引入就越快，已获得的优良基因结果的丢失速度也相应地提高，而交叉概率太低则可能导致搜索阻滞。一般取 P c =0.6～1.0。
（4）变异概率 P m
变异操作是保持群体多样性的手段，交叉结束后，中间群体中的全部个体位串上的每位基因值按变异概率 P m 随机改变，因此每代中大约发生 P m × N × L 次变异。变异概率太小，可能使某些基因位过早地丢失信息，无法恢复；变异概率过高，则遗传算法将变成随机搜索。一般取 P m =0.005～0.05。
实际上，上述参数与问题的类型有着直接的关系。问题的目标函数越复杂，参数选择就越困难。从理论上讲，不存在一组适应于所有问题的最佳参数值，随着问题特征的变化，有效参数的差异往往非常显著。如何设定遗传算法的控制参数，以使遗传算法的性能得到改善，还需要结合实际问题深入研究。
遗传算法中，主要的个体操作算子是交叉算子和变异算子。在遗传算法中，交叉算子是不同的父代个体之间进行基因位的交换，从而达到扩充种群多样性和优化种群的作用。使用交叉算子表明遗传算法注重个体之间的信息交互，具有个体之间进行信息交互的机制。
使用变异算子进行自身位置的局部更新，采用均匀变异算子属于完全随机的一种变异行为，是随机搜索的一类智能算法，没有考虑到自身信息，容易丧失优秀个体的先进性，不利于算法的快速收敛。因此，通常采用较小的变异概率，保证其在小范围内具有局部搜索的能力。
在遗传算法中，群体更新机制是依靠选择算子实现的。选择算子的对象是父代经过交叉、变异后生成的子代个体，在生成子代后，父代个体即被抛弃。由于是随机搜索的一类智能算法，通过交叉、变异后的个体，不可避免地会出现一些退化现象，而相对较为优秀的父代个体的信息将无法得到保留，这影响了算法的收敛。为了扩充种群的多样性，在每一代个体中，选择算子不仅要让适应度高的个体被选中，而且应该确保适应度差的个体也有被选中的机会。
一幅图像中含有多个物体，在图像中进行聚类分析需要对不同的物体分割标识，如图2-7所示，手写了（1 2 3 4 4 2 3 3 3 4 4 4）共12个待分类样品，要分成4类，如何让计算机自动将这12个物体归类呢？
图2-7 待分类的样品数字
这就是聚类算法所要解决的问题，即将相同的物体归为一类。聚类问题的特点是事先不了解一批样品中每一个样品的类别或其他的先验知识，而唯一的分类根据是样品的特性，利用样品的特性来构造分类器。聚类算法的重点是寻找特征的相似性。许多学科要根据所测得的相似性数据进行分类，把探测数据归入到各个聚合类中，并且在同一个聚合类中的模式比不同聚合类中的模式更相似，从而对模式间的相互关系做出估计。聚类分析的结果可以被用来对数据提出初始假设，分类新数据，测试数据的同类型及压缩数据。
传统的优化算法往往直接利用问题中参数的实际值本身进行优化计算，通过调整参数的值找到最优解。但是遗传算法通过将参数编码，在求解问题的决定因素和控制参数的编码集上进行操作，因而不受函数限制条件（如导数的存在、连续性、单调性等）的约束，可以解决传统方法不能解决的问题。遗传算法求解是从问题的解位串集开始搜索，而不是单个解开始搜索，遗传算法的三个遗传算子（选择、交叉、变异）是随机的，搜索空间范围大，降低了陷入局部最优的可能性。算法仅使用目标函数来进行搜索，不需要其他辅助信息，隐含并行性、可扩展性，易于同别的技术结合。这使遗传算法大大扩展了应用范围。本节以图像中的物体聚类分析为例，介绍用遗传算法解决聚类问题的仿生计算方法。
对图2-7所示的12个物体进行编号，样品编号如图2-8所示，在每个样品的右上角，不同的样品编号不同，而且编号始终固定。
图2-8 待测样品的编号
采用符号编码，位串长度 L 取12位，基因代表样品所属的类号（1～4），基因位的序号代表样品的编号，基因位的序号是固定的，也就是说某个样品在染色体中的位置是固定的，而每个样品所属的类别随时在变化。如果基因位为 n ，则其对应第 n 个样品，而第 n 个基因位所指向的基因值代表第 n 个样品的归属类号。
每个个体包含一种分类方案。设初始某个个体的染色体编码为（2，3，2，1，4，4，2，3，1，3，2，3），其含义为：第1、3、7、11个样品被分到第2类；第2、8、10和12个样品被分到第3类；第4、9个样品被分到第1类；第5、6个样品属于第4类。这时还处于假设分类情况，不是最优解，如表2-1所示。
表2-1 初始某个个体的染色体编码
经过遗传算法找到的最优解如图2-9所示。遗传算法找到的最优染色体编码如表2-2所示。通过样品值与基因值对照比较，会发现相同的数据被归为一类，分到相同的类号，而且全部正确。
图2-9 经过遗传算法找到的最优解
表2-2 遗传算法找到的最优染色体编码
评估函数CalObjValue()的结果为评估值，代表每个个体优劣的程度。
对初始群体中的每个染色体计算其评估值m_pop(i).value，实现步骤如下。
① 通过人工干预获得聚类类别总数，centerNum为聚类类别总数（2＜=centerNum＜= N -1， N 是总的样品个数）。
② 找出染色体中相同类号的样品， X （ i ） 表示属于第 i 个类的样品。
③统计每一个类的样品个数
n
，
n
i
是第
i
个类别的个数，样品总数为
。
④ 计算同一个类的中心
C
，
C
i
是第
i
个类的中心，
，（
i
=1，2，…，centerNum）。
⑤ 同一个类内计算每一个样品到中心的距离，并将它们累加求和。
采用K-均值模型为聚类模型。计算公式如下：
显然当聚类类别总数centerNum= N 时，累加和∑ D i 为0。因此，当聚类数目centerNum不定时，必须对目标函数进行修正。实际上，式（2-1）仅为类内距离之和，因此，可以使用类内距离与类间距离之和作为目标函数，即
其中， w 是权重，反映决策者的偏爱。
⑥ 将不同类计算出的 D i 求和赋给m_pop( i ).value，以m_pop( i ).value作为评估值。
m_pop( i ).value越小，说明这种分类方法的误差越小，该个体被选择到下一代的概率也就越大。
适应度函数是整个遗传算法中极为关键的一部分。好的适应度函数能够从非最优个体进化到最优个体，能够解决早收敛与过慢结束的矛盾。
适应度函数CalFitnessValue()的结果代表每个个体相对于整个群体的相对适应性。个体适应度的大小决定了它继续繁衍还是消亡。适应度高的个体被复制到下一代的可能性高于适应度低的个体。
以m_pop( i ).value作为适应度，其选择机制在遗传算法中存在两个问题：
群体中极少数适应度相当高的个体被迅速选择、复制遗传，引起算法提前收敛于局部最优解。
群体中个体适应度彼此非常接近，算法趋向于纯粹的随机选择，使优化过程趋于停止。
这里不以m_pop( i ).value直接作为该分类方法的适应度值，采用的方法是适应度排序法。不管个体的m_pop( i ).value是多少，被选择的概率只与序号有关。这样避免了一代群体中过于适应或过于不适应个体的干扰。
适应度函数的计算步骤如下。
① 按照原始的m_pop( i ).value由小到大排序，依次编号为1，2，…， N 。index是排序序号。
② 计算适应度值：
a 的取值范围是（0，1），取 a =0.6。
（1）选择算子
建立选择数组cFitness [ N ]，循环统计从第1个个体到第 i 个个体适应度值之和占所有个体适应度值总和的比例cFitness( i )，以cFitness( i )作为选择依据。
式中，
循环产生随机数rand，当rand＜cFitness( i )时，对应的个体复制到下一代中，直到生成 n 个中间群体。例如，由4个个体组成的群体， a =0.6，cFitness( i )计算方式如表2-3所示。
表2-3 选择依据计算方式
（2）交叉算子
以概率 P c 生成一个“一点交叉”的交叉位point，随机不重复地从中间群体中选择两个个体，对交叉位后的基因进行交叉运算，直到中间群体中的所有个体都被选择过。
（3）变异算子
对所有个体，循环每一个基因位，产生随机数rand，当概率rand＜ P m 时，对该位基因进行变异运算，随机产生1～centerNum的一个数赋值给该位，生成子代群体。
变异概率一般很小， P m 在0.001～0.1之间，如果变异概率过大，则会破坏许多优良品种，也可能无法得到最优解。
① 设置相关参数。
初始化初始人群总数popSize、交叉概率0.6，变异概率0.05。从对话框得到用户输入的最大迭代次数MaxIter，聚类中心数centerNum。
② 获得所有样品个数及特征。
③ 群体初始化。
④ 计算每一个个体的评估值m_pop( i ).value。
⑤ 计算每一个个体的适应度值m_pop( i ).fitness。
⑥ 生成下一代群体。
选择算子：建立适应度数组cFitness[popSize]，计算cFitness(
i
)。循环产生随机数
p
，当
p
＜cFitness(
i
)时，对应的个体复制到下一代中，直到生成popSize个中间群体。
交叉算子：以概率
P
c
=0.6生成一个“一点交叉”的交叉位point，随机从中间群体中选择两个个体，对交叉位后的基因进行交叉运算，直到中间群体中的所有个体都被选择过。
变异算子：对所有个体，循环每一个基因位，产生随机数rand，当概率rand＜
P
m
=0.05时，对该位基因进行变异运算，随机产生1～centerNum的一个数赋值给该位，生成子代群体。
⑦ 再次调用EvaPop()函数对新生成的子代群体（popSize个）进行评估。
⑧ 调用FindBW()函数保留精英个体，若新生成的子代群体中的最优个体 D 值低于总的最优个体 D 值（相互之间距离越近， D 越小），则用当前最好的个体替换总的最好的个体，否则用总的最好个体替换当前最差个体。
⑨ 若已达到最大迭代次数，则退出循环，否则到第⑥步“生成下一代群体”继续运行。
⑩ 将总的最优个体的染色体解码，返回给各个样品的类别号。
遗传算法应用于聚类分析的程序总体流程图如图2-10所示。
编程代码见作者撰写的《模式识别与智能计算——Matlab技术实现》一书。
这里给读者提供两个实例效果图，一个是基于数字聚类的结果图，如图2-11所示，另一个是基于图形聚类的结果图，如图2-12所示。这两个图也比较复杂，但从结果可以看出，应用遗传算法解决聚类问题的效果非常好。（注意：图右上角显示样品编号，左下角显示该样品所属类别）
图2-10 基于遗传算法的聚类分析程序总体流程图
图2-11 遗传算法应用于数字聚类分析结果图
图2-12 遗传算法应用于图形聚类分析结果图