下载掌阅APP，畅读海量书库
立即打开
自然选择学说认为，生物要存活下去，就必须进行生存斗争，包括种内斗争、种间斗争及生物与环境之间的斗争三个方面。在生存斗争中，具有有利变异的个体更容易存活下来，并有更多的机会将有利变异传给后代，具有不利变异的个体则容易被淘汰，也将很少获得产生后代的机会。因此，凡是在生存斗争中获胜的个体都是对环境适应性比较强的个体。达尔文把这种在生存斗争中适者生存、不适者淘汰的过程叫作自然选择。
达尔文的自然选择学说表明，遗传和变异是决定生物进化的内在因素。遗传是指父代与子代之间在性状上存在的相似现象。变异是指父代与子代之间及子代的不同个体之间，在性状上存在的差异现象。在生物体内，遗传和变异的关系十分密切。一个生物体的遗传性状往往会发生变异，而变异的性状有的还可以遗传。生物的遗传特性能够把生物的性状不断地传送给后代，使生物界的物种能够保持相对稳定。生物的变异特性使生物个体产生新性状，从而更加适应新环境，甚至生成新物种，推动着生物的进化发展。
生物的各项生命活动都有它的物质基础。根据现代细胞学和遗传学知识可知，遗传物质的主要载体是染色体，基因是有遗传效应的片段，它储存着生物物种的遗传信息，可以准确地复制（Reproduction），也能够发生突变。生物通过对基因的复制和交叉（Crossover），使其性状的遗传得到选择和控制。同时，通过基因重组、基因变异和染色体在结构和数目上的突变，产生丰富多彩的变异现象。由于生物在繁殖过程中可能发生基因交叉和变异，引起了生物性状的连续微弱改变，为外界环境的定向选择提供了物质条件和基础，使生物的进化成为可能。生物遗传和进化的规律如下：
（1）生物的所有遗传信息都包含在其染色体中，染色体决定了生物的性状。染色体是由基因及其有规律的排列构成的。
（2）生物的繁殖过程是由其基因的复制过程来完成的。同源染色体的交叉或变异会产生新的个体，使生物呈现新的性状。
（3）对环境适应能力强的染色体或基因，比适应能力差的染色体或基因有更多的机会遗传到下一代。
遗传算法使用群体搜索技术，用染色体种群代表优化问题的一组解，通过对当代种群施加选择、交叉和变异等一系列遗传操作来产生下一代种群，并逐步使种群进化到包含近似最优解的状态。由于遗传算法是自然选择学说、细胞学说、遗传学与计算机科学相互渗透而形成的计算方法，所以在遗传算法中经常会使用一些有关自然进化的术语，遗传学与遗传算法的术语对应关系如表2-1所示。
表2-1 遗传学与遗传算法的术语对应关系
（续表）
1.群体和个体
群体有时也被称为种群，是生物进化过程中的一个集合，表示问题的可行解集。个体是组成群体的单个生物体，由NP个个体组成的种群可记为 X =[ X 1 ， X 2 ，…， X NP ] T ，每个个体又可用一个向量来表示，记为 X i =[ x i 1， ， x i 2， ，…， x i ， N ]， i =1，2，…，NP，其中 N 可能是二进制编码的长度，也可能是多维优化问题的维数。每个个体 X i 既是一个染色体，也是种群中的一个个体、一个由优化问题的决策变量构成的向量、搜索空间中的一个位置和可行解集中的一个解。
2.染色体和基因
染色体是包含生物所有遗传信息的化合物，表示可行解的编码，一般用向量表示。基因是控制生物体某种性状（遗传信息）的基本单位，表示可行解编码向量的分量。
3.遗传编码
遗传编码是将优化变量转化为染色体的基因组合表示形式。根据求解问题的实际情况，优化变量的编码方式有二进制编码、实数编码（十进制编码）、顺序编码（自然数编码）等不同形式。
（1）二进制编码。二进制编码（Binary Encoding）位串的每一位只能用“0”或“1”来表示。如果优化变量为实数区间[ x min ， x max ]，需要先将优化变量进行编码，形成染色体位串，再对位串进行遗传操作。
假设使用长度为 L 的位串表示变量 x ，编码从“00······0”到“11······1”，共有2 L 个不同的位串，对应的十进制整数为0，1，…，2 L -1。位串“000······0”对应 x min ，“111······1”对应 x max ，由于二进制位串表示的数是不连续的，相邻两个编码的阶跃值为
式中，Δ x 称为编码步长或编码精度。
如果要将二进制编码 x B = a L -1 a L -2 … a 0 ，对应到实数区间[ x min ， x max ]内的 x R ，需要进行解码，先将其转换成十进制整数 x D = a L -1 2 L -1 + a L -2 2 L -2 +…+ a 1 2 1 + a 0 2 0 ，然后代入式（2-2），即
通过以上分析可知，编码长度 L 越大，在给定实数区间[ x min ， x max ]内的编码个数就越多，相邻两个编码之间的阶跃值Δ x 就越小，相应的编码精度就越高，求得最优解的精度也会越高。但同时编码长度越大，也意味着遗传操作所需的编码转换计算量越大，算法耗时也将越长。因此，编码长度要根据优化问题求解精度的实际情况来确定。
尽管二进制编码方式操作方便，计算简单，但也存在一些难以克服的困难而无法满足所有优化问题的求解要求。例如，对于多维连续优化问题，从一个连续量离散化为一个二进制量本身就存在误差，使得算法求解精度降低，而要提高求解精度又必须提高位串的编码长度，编码和解码用时较长，算法效率下降。同时，二进制编码方式也不利于反映所求问题的特定知识，对问题信息和知识利用不充分也会阻碍算法效率的进一步提高。
（2）实数编码。人们在求解一些多维数值优化问题时，为了克服二进制编码产生的问题，经常采用实数编码（Real-Number Encoding）方式。实数编码的优点是计算精确度高，便于和经典连续优化算法结合，非常适合多元连续函数优化问题的求解。
（3）顺序编码。顺序编码（Order Encoding）有着广泛的适用性，可以解决旅行商问题、任务排序问题等优化问题。顺序编码采用1～ N 个自然数编码，此种编码不允许重复，又称为自然数编码。例如，对于7个城市的TSP问题，城市序号用1，2，…，7表示，用长度为7的顺序编码表示行走路线 X =[2，3，5，4，1，7，6]和 Y =[5，2，4，3，7，6，1]都是可以的。但 Z =[2，3，5，4，2，7，6]这种编码就是不符合要求的，因为出现了两个基因位编码相同的情况，城市“2”出现了重复，而城市“1”没有出现，这就违背了TSP问题中“所有城市都要访问到”和“每个城市只能访问一次”的要求。采用顺序编码常见的方式又包括以下几种：
①随机产生法。随机产生法是求解TSP问题时使用最多的一种方法，随机产生1～ N 之间的不重复的随机整数，按照产生的先后顺序组成一条路径。这种随机产生的初始种群可以保证初始解的多样性和分散性，但也容易因初始解的质量较差，算法收敛速度较慢。
②最近邻法。在城市集合中随机选取一个城市作为首发城市，在剩余城市中选择距首发城市距离最近的城市作为第二个访问城市，再在剩余城市中选择距第二个访问城市距离最近的城市作为第三个访问城市。以此类推，将剩余城市全部访问到后产生一条路径。由最近邻法生成的初始种群具有较好的启发性，可加快算法收敛速度。但用最近邻法产生初始种群中的不重复路径十分有限，当种群规模较大时，由于初始种群多样性不足，很容易陷于局部最优，不一定能够获得满意的最优解。
③概率近邻法。在城市集合中随机选取一个城市作为首发城市，依据剩余城市距首发城市的距离构建选择概率，距离越短的城市被选中的概率越大，用“轮盘赌”的方式从中来选择某个城市作为第二个访问城市。以此类推，将剩余城市全部访问到后产生一条路径。概率近邻法是对最近邻法的一种改进，以距离为参照，按一定的概率来选择下一个访问城市，可以提高初始种群的多样性。
④环路插入法。在城市集合中随机选择2个不重复的城市，组成向量 X =[ x i ， x j ]，然后在未访问的城市中随机选择城市 x k 插入 X 中，插入位置不同，得到的路径也不相同，分别计算三种插入方式[ x k ， x i ， x j ]、[ x i ， x k ， x j ]、[ x i ， x j ， x k ]的路径距离，取距离最短的作为城市 x k 的最终插入位置。以此类推，将未被访问的城市全部插入 X 中即可得到一条完整路径。这种路径产生方法在确定城市顺序时是一种启发式插入方法，插入城市是随机选择的，在较大程度上保障了初始种群的多样性，但该方法需要多次试探性插入，必然会带来较大的计算量。
4.适应度函数
在遗传算法中，适应度函数表征生物群体中个体适应生存环境的能力，用来评价个体位置或问题解的优劣。个体的适应度函数与其目标函数相关联，越接近目标函数的最优解，其适应度函数值越大；反之，适应度函数值越小。
在遗传算法的进化搜索中基本不用其他外部信息，仅用适应度函数作为选择父辈个体和个体竞争的依据。适应度函数的设计直接影响算法的性能，要结合求解问题本身的具体情况确定，但针对每个个体必须能够计算出可进行比较的结果。
5.遗传操作
遗传操作是选择、交叉、变异三种操作的统称。在生物进化过程中，一个种群中生物特性的保持是通过遗传来继承发展的，把当代父辈种群的基因信息遗传到下一代种群。与此对应，遗传算法中最优解的搜索过程也模仿生物的这一进化过程，使用遗传算子来实现，包括选择算子、交叉算子、变异算子。
（1）选择算子。根据个体的适应度函数值，按照一定的规则或方法，从第 t 代种群 X （ t ）中选出一些优良个体遗传到下一代种群 X （ t +1）中。常用的父辈个体选择方法是“锦标赛”选择法和“轮盘赌”选择法。“锦标赛”选择法是每次从种群中随机取出一定数量的个体（放回抽样），然后选择其中最优的个体（相当于小组赛的获胜者）作为父辈个体。该方法涉及从种群中随机选择几个个体（相当于小组赛参赛队伍的数量），选择多少次（相当于需要几场小组赛）。“轮盘赌”选择法是由Holland教授提出的，原理简单、实用性强、应用广泛。
“轮盘赌”选择法是一种比例选择（Proportional Selection）策略，利用各个个体适应度函数值所占种群中所有个体适应度函数值总和的比例大小来决定其被选中的可能性。个体适应度越大，则被选中的机会也越大；反之亦然。若染色体种群数量为NP，某个体 X i 的适应度函数值为fit i =fit（ X i ），则它被选中的概率可表示为
例如，当NP=5时，整个轮盘根据个体被选中的概率，划分为5个圆心角大小不同的扇形区域，适应度较大的个体对应扇面的圆心角较大，适应度较小的个体对应扇面的圆心角较小，当旋转轮盘时，其最终停靠的扇面区域与其圆心角成正比，如图2-1所示。这样通过转动轮盘，观察指针的停靠区域来选取对应的个体。个体 X 5 的适应度最小，轮盘停靠在其扇形区域的概率 P 5 也最小，被选中机会也最小；个体 X 4 的适应度最大，轮盘停靠在其扇形区域的概率 P 4 也最大，被选中的机会也最大。因此， X 4 作为相对优良的个体，将有更大的机会进入下一代的遗传操作中。
图2-1 比例选择示意图
在实际应用中，种群数量较大时，如果采用产生一个范围[0，1]内的均匀分布随机数，直接通过判断其落在哪个区域来确定被选个体，还是较为烦琐的。当需要选择的父辈个体较多时，多次转动轮盘更是如此。为此，基于“轮盘赌”的选择法通常按照如下思路实现：按照式（2-3）得到每个个体 X i 的选择概率 P i ，再计算每个个体的累积选择概率为
即每个个体之前所有个体的选择概率之和，相当于概率论中的概率分布函数，也相当于轮盘上的“跨度”。如果只需选择一个个体，则可产生rand∈[0，1]的均匀分布随机数，找到首次满足
条件的个体就是被选中的个体。如果需要选择多个个体，则可以重复上述方法。
（2）交叉算子。将群体中选中的个体组对，以某一概率（交叉概率 P c ）交换它们之间的部分基因位或基因片段。交叉操作的基本过程是根据位串长度 L ，随机选取配对个体的一个或多个交叉位置，根据交叉概率 P c 实施交叉操作，相互交换各自的部分基因。交换部分既可以是一个基因位，也可以是若干个基因位组成的基因片段，从而产生一对新的个体。常用的交叉方法有以下几种。
①单点交叉。单点交叉是由Holland教授提出的最基础、最简单的一种交叉方式之一，如图2-2所示。从两个父辈个体 X i 和 X j 中，选择某个基因位置作为交叉点，将交叉点两侧分别作为两个子串，根据交叉概率 P c 相互交换右侧的子串，得到两个新个体 Y i 和 Y j 。
②两点交叉。两点交叉是指随机选择两个不重合的交叉点，然后交换两个交叉点之间的子串，得到两个新的个体的一种交叉方式。如图2-3所示，从两个父辈个体 X i 和 X j 中，根据交叉概率 P c 将交叉点1和交叉点2之间的子串进行交换，得到两个新个体 Y i 和 Y j 。
图2-2 单点交叉示意图
图2-3 两点交叉示意图
当然，根据需要，还可以设置更多的交叉点，进行更为复杂的交叉操作，甚至根据交叉概率 P c 进行逐点交叉操作。对于采用实数编码方式的多维变量优化问题，交叉操作也是按照上述方法互换其中的一个或多个分量。
③启发式交叉。在求解TSP问题时，通常使用城市序号进行顺序编码，在使用互换方式交叉时一定要注意避免交叉操作后出现城市重复的情况。这里重点提出一种基于就近原则的启发式交叉算子，由路径 X 和 Y 通过启发式交叉操作产生新路径 Z 的方法，具体实现如下。
A.随机选择一个城市 c 作为路径 Z 的第一个城市，也是旅行商所在的当前城市，找到城市 c 在路径 X 和 Y 中的位置。
B.将路径 X 和 Y 当作一个圆环对待，路径末尾城市的下一个城市就是该路径的首发城市，沿逆时针方向在路径 X 和 Y 中找到路径 Z 当前城市 c 下一个未走过的城市 c X 和 c Y 。
C.假设城市 c X 和 c Y 与路径 Z 当前城市 c 的距离分别为 d X 和 d Y ，如果 d X ≤ d Y ，则将 c X 加入路径 Z 中作为旅行商所在的当前城市；否则，将 c Y 加入路径 Z 中作为旅行商所在的当前城市。
D.重复过程A和B，直到路径 X 和 Y 中只剩下同一个未走过的城市后，直接将该城市也加入路径 Z 中。
为了提高产生新路径的多样性，在对两条路径启发式交叉时，路径按环形对待，既可以沿逆时针方向确定下一个城市，也可以沿顺时针方向确定下一个城市。如果要沿顺时针方向进行操作，只需在交叉前将路径 X 和 Y 进行倒序即可。因此，在启发式交叉之前，可按照等概率的原则来随机选择启发式交叉的方向。
在此说明：本书后文在求解TSP问题中，如果没有特殊说明，两条路径的启发式交叉操作均按此交叉方法进行。
（3）变异算子。染色体交叉之后产生的新个体，可能会以很小的概率发生变异。变异算子就是以某一概率将染色体位串中的某个或某些基因值用其他基因值替换，以增加种群的多样性。在遗传算法收敛到某个局部解时，种群中的染色体趋于一致，采取变异操作有助于使搜索跳出局部最优。常用的变异方法主要有以下几种。
①二进制翻转变异。染色体二进制翻转变异就是在某个或某些基因位取逻辑非进行位值翻转。一个基因位和两个基因位二进制翻转变异如图2-4所示。
图2-4 一个基因位和两个基因位二进制翻转变异
②位置互换变异。染色体的变异可以通过将编码中两个位置的取值进行互换实现。在求解TSP问题时，如果使用城市序号进行顺序编码，也可以将编码中两个位置的城市序号进行互换。
③实值替换变异。对于采用实数编码的多维变量优化问题，染色体的变异可以用在搜索范围内随机生成的实数来替换其中的一个或多个分量。
④倒序变异。染色体的变异可以通过将编码中两个位置中间的编码倒序实现。在求解TSP问题时，如果使用城市序号进行顺序编码，也可以采用倒序变异。对于由 N 个城市组成的路径 X ，倒序变异的实现方法是：随机产生不相等的两个位置 p ， q ∈[1， N ]，且 p ≠ q ，如果 p ＜ q ，则进行中间倒序，即[ p ， q ]之间的城市进行倒序，而两端的城市位置保持不变；否则，进行两端倒序，即[1， q ]之间和[ p ， N ]之间的城市进行倒序，而中间的城市位置保持不变。当 N =10个城市时的TSP问题顺序编码的路径倒序变异如图2-5所示。
图2-5 当 N =10个城市时的TSP问题顺序编码的路径倒序变异
在此说明：本书后文在求解TSP问题中，如果没有特殊说明，路径的倒序变异操作均按此变异方法进行。
遗传算法是模拟生物在自然环境中的进化过程而形成的一种并行、高效、全局搜索方法，主要有以下特点。
（1）遗传算法以决策变量的编码作为运算对象。这种对决策变量的编码处理方式，使得在优化计算过程中可以借鉴生物学中染色体和基因等概念，模仿自然界中生物的进化机理，方便应用选择、交叉和变异等遗传操作。特别是对一些只有代码概念而无数值概念或很难有数值概念的优化问题，编码处理方式更显示出其独特的优越性。
（2）遗传算法直接以目标函数或由目标函数变换而来的适应度函数作为个体评价依据，不需要目标函数的导数值等其他辅助信息就可确定进一步的搜索方向和搜索范围。在实际应用中，很多函数无法或很难求导，甚至根本不存在导数，遗传算法避开了函数求导这个障碍，显示出对于这类目标函数的优化问题及组合优化问题的优越性。
（3）遗传算法可以实现多点并行搜索。遗传算法的搜索过程是从一个由很多个体组成的初始种群开始的，而不是从单一个体开始的。对当代种群进行的选择、交叉、变异等遗传操作产生出新一代种群，相当于搜索了更多的点，获得了更多的搜索信息，这是遗传算法具有的一种隐含并行性。
（4）遗传算法采用基于概率的搜索技术，属于一种自适应随机型优化算法，其选择、交叉、变异等遗传操作都是以概率的方式进行的，从而增加了其搜索的灵活性。虽然这种概率特性也会使群体中产生一些适应度不高的个体，但随着种群的不断进化，新的群体中总会产生出更多的优良个体。
（5）遗传算法使用群体搜索技术，通过对当代群体开展选择、交叉、变异等一系列遗传操作产生新一代群体，并逐步使群体进化到包含最优或接近最优解的状态。遗传算法具有较高的鲁棒性，使得算法参数对其搜索效果的影响较小。
（6）遗传算法具有自组织、自适应和自学习等特性。当遗传算法利用进化过程获得的信息自行组织搜索时，适应度函数值大的个体获得了适应环境能力更好的基因结构，具有更高的生存概率。同时，遗传算法具有可扩展性，易于与其他算法相结合，得到综合各自优势的混合优化算法。
本书后续研究的其他群智能优化算法在某种程度上都伴有遗传算法处理问题的思想，因此学好遗传算法对学习理解其他群智能优化算法的原理与实现具有很好的借鉴价值。