下载掌阅APP，畅读海量书库
立即打开
1.算法基本思想
遗传算法（Genetic Algorithm，GA）是由Holland最早于1962年提出的一种用于求解优化问题的随机自适应的全局搜索算法，吸收了生物学中的达尔文进化理论和孟德尔的遗传学说等重要理论成果。达尔文的进化论提出自然界“自然选择”和“优胜劣汰”的进化规律，在进化过程中，种群中的个体对环境的资源短缺、灾害等具有不同的适应能力，适应能力不足的个体会被淘汰，而适应能力较强的个体则得以保留，并通过繁衍产生新的种群。孟德尔的遗传学说则提出了遗传信息的重组模式。染色体作为遗传信息即基因的载体，在父代交叉产生子代时，通过交叉、变异实现遗传信息的重新组合，与环境共同决定子代的性状。
生物遗传基本要素与遗传算法中的基本要素对应如下。
●种群（population）：问题搜索空间内的一组有效解，规模为 N 。
●染色体（chromosome）：种群中的个体（individual），问题的一个合法解的编码串。
●基因（gene）：染色体的一个编码单元。
Holland给出的模式定理（schema theory）和Goldberg提出的积木块假设（building block hypothesis）解释了遗传算法的基本原理，为遗传算法的全局搜索能力提供了理论支持。模式定理指的是，在连续的迭代中，高于平均适应值的短小的、低阶的模式串（schemata）的出现频率会呈指数级上升。可以把模式串理解成一个有相似性的字符串子集，这些字符串在某些特定位置上有相似性。积木块假设指的是，遗传算法会选择编码有显著特征的短基因串，因为短基因串比长基因串更不容易受到变异和交叉的破坏，长基因串有更多容易受到破坏的选点。这些短且有价值的基因串成为进化的“积木块”，使特征层面的组合得以实现。
对应于生物遗传中的过程，遗传算法操作中的6个要素如下。
1）染色体的编码 （representation）：问题的解的表示，对染色体的交叉和变异操作构成影响，需要既简单又达到一定的算法性能，例如非冗余性、完备性、合法性、因果性等，常见的编码方法有二进制编码、整数编码和实数编码等。
2）种群初始化 （population initialization）：遗传算法在一个给定的初始种群中进行迭代搜索，基本的初始化方法是随机数方法，即对染色体的每一维变量进行随机赋值，初始化的染色体需要注意染色体是否满足优化问题对有效解的定义。由于一个较为优良的初始种群能提高算法找到全局最优解的能力，在保证搜索空间完备性的基础上，通过特定方法使初始化得到更好的种群（平均适应值相对较高）已被证明能使遗传算法获得更好的效果。
3）适应值评估 （fitness evaluation）：适应值代表问题的优化目标，遗传算法通过评估函数来评估各染色体的适应值，以区分染色体的优劣。在遗传算法中，一般情况下规定适应值越大的染色体越优，对于需要求解目标函数最大值的优化问题，则评估函数直接套用目标函数的形式即可，而对于需要求解目标函数最小值的优化问题，则要对目标函数 f （ X ）进行一定的转换以得到评估函数Eval（ C ），例如Eval（ C ）= -f （ X ），其中 X 和 C 分别代表问题的一个有效解和对应的染色体。
4）选择算子 （selection）：从种群中选择较优的个体进入新种群，并保持多样性的操作。适应值较高的个体被选择的概率更大，但为了保持种群多样性，适应值低的个体也有一定的生存空间。常用的选择算子包括轮盘赌选择（roulette wheel selection）算法、锦标赛选择（tournament selection）算法。
轮盘赌选择算法的基本思想是根据个体的适应值确定其被选择的概率，首先根据种群中所有个体的适应值得到适应值的总和，再计算每个个体的适应值与种群适应值总和的比值，可以划分得到图1-1所示的NP个扇区（NP是种群规模，图1-1中NP=4），则每个扇区的大小与个体对应的适应值比值成正比，每转动一次轮盘，则转盘停止时指针指向的扇区对应的个体即被选中进入新种群，依次进行NP次即可得到规模为NP的新种群。
图1-1 轮盘赌选择算子示意图
上述轮盘赌选择算法基于适应值的占比来选择个体，由于缺乏选择压力（selective pressure），容易导致搜索缺乏方向性，效率低下，将搜索局限于具有接近于种群适应值平均值的个体上。而图1-2所示的锦标赛选择算法，通过持续对种群中随机选择的 N ts 个个体进行锦标赛来选择进入新种群的个体，使新种群中的个体是NP次锦标赛中的胜利者，从而使新种群中的个体平均适应值高于原种群中的平均适应值，因而具有选择压力，驱使遗传算法倾向于提高种群适应值。
图1-2 锦标赛选择算子示意图
5）交叉算子 （crossover）：按照交叉概率 P c （一般取值为0.5～1.0），从新种群中选择成对的染色体作为父代进行交叉，产生子代，如图1-3所示，每两个父代染色体交换部分基因产生两个新的子代染色体，两个子代染色体取代两个父代染色体进入新种群，没有进行交叉的染色体则直接复制进入新种群。典型的交叉算子包括单点交叉（one-point crossover）、两点交叉（two-point crossover）、多点交叉（multi-point crossover）、部分匹配交叉（partially matched crossover）、均匀交叉（uniform crossover）、算术交叉（arithmetic crossover）等，在实际应用中根据问题和具体的染色体编码方式的不同进行选择。
图1-3 交叉算子示意图
交叉后产生的子代染色体应满足问题对有效解的定义。若产生的子代染色体不满足有效解的定义，则需要对其进行修复，例如将其中不满足约束的变量修改为约束区间的边界，或将无效解映射到距离其最近的有效解的位置。
6）变异算子 （mutation）：如图1-4所示，按照变异概率 P m （一般取值为0.005～0.05）对新种群中的染色体的基因进行变异操作，改变相应基因的值，变异后的染色体取代原有染色体进入新种群，未发生变异的染色体直接复制进入新种群。典型的变异算子包括简单变异（simple mutation）、均匀变异（uniform mutation）、边界变异（boundary mutation）、高斯变异（gaussian mutation）、非均匀变异（non-uniform mutation）等。变异后的染色体也应满足问题对有效解的定义。
图1-4 变异算子示意图
2.算法流程
遗传算法的流程图和伪代码如图1-5所示，其具体步骤如下。
图1-5 遗传算法的流程图和伪代码
1）初始化种群 ：初始化规模为 N 的种群，其中每个染色体的每个基因采用随机数生成等方式生成满足问题约束范围值。当前进化代数 t =0。
2）评估适应值 ：采用评估函数对种群中的所有染色体进行适应值评估，保存适应值最大的个体为Best。
3）选择算子 ：采用轮盘赌选择算子或其他选择算子对种群中的染色体进行选择，产生规模同样为 N 的新种群。为了保留种群中最优的个体，直接选择Best进入种群。
4）交叉算子 ：按照概率 P c 从新种群中选择成对的染色体作为父代进行交叉产生子代，每两个父代染色体交换部分基因产生两个新的子代染色体，两个子代染色体取代两个父代染色体进入新种群，没有进行交叉的染色体则直接复制进入新种群。
5）变异算子 ：按照概率 P m 对新种群中的染色体的基因进行变异操作，改变相应基因的值，变异后的染色体取代原有染色体进入新种群，未变异的染色体直接复制进入新种群。
6）适应值评估与最优个体更新 ：新种群取代原有种群，重新对种群中的染色体进行适应值评估。如果种群中适应值最大的个体的适应值大于Best的适应值，则更新Best为种群中适应值最大的个体；否则，可以使用Best个体替代种群中适应值最小的个体。
7）进化结束条件判断 ：当前进化代数 t = t +1。如果 t 达到了规定的最大进化代数或Best达到了规定的误差要求，则算法结束；否则返回步骤3。