文档介绍：1 / 32
全局优化报告
——遗传算法和蚁群算法的比较
每个可能的解都被编码成一个 “染色体”，即个体，若干个个体构成了群体（所有可能解）。在遗传算法开始时，总是随机地产生一些个体（即初始解）。根据预定的目标函数对每个个体进行评估，给出了一个适应度值。基于此适应度值，选择个体用来复制下一代。选择操作体现了“适者生存”的原理， “好”的个体被选择用来复制，而“坏”的个体则被淘汰。然后选择出来的个体经
4 / 32
过交叉和变异算子进行再结合生成新的一代。这一群新个体由于继承
了上一代的一些优良性状，因而在性能上要优于上一代，这样逐步朝
着更优解的方向进化。因此，遗传算法可以看成是一个由可行解组成
的群体逐步进化的过程。图给出了简单遗传算法的基本过程。下面介
绍遗传算法的编码及基本遗传操作过程。
编码
利用遗传算法求解问题时，首先要确定问题的目标函数和变量，
然后对变量进行编码。这样做主要是因为在遗传算法中，问题的解是
用数字串来表示的，而且遗传算子也是直接对串进行操作的。编码方
式可以分为二进制编码和实数编码。若用二进制数表示个体，则将二
进制数转化为十进制数的解码公式可以为
Ti
Ri
l
j 1
F(bi 1, bi 2,..., bil) Ri
1
bij2
2l
j 1
其中，( bi 1 , bi 2 ,...,
bil)为某个个体的第 i 段，每段段长都为 l ，每个 bik
都是 0或者 1，
Ti和 Ri是第 i 段分量 Xi的定义域的两个端点。
遗传操作
遗传操作是模拟生物基因的操作，它的任务就是根据个体的适应度对其施加一定的操作，从而实现优胜劣汰的进化过程。从优化搜索的角度看，遗传操作可以使问题的解逐代的优化，逼近最优解。遗传操作包括以下三个基本遗传算子：选择、交叉、变异。选择和交叉基本上完成了遗传算法的大部分搜索功能，变异增加了遗传算法找到最接近最优解的能力。
选择
5 / 32
选择是指从群体中选择优良的个体并淘汰劣质个体的操作。它建立在适应度评估的基础上。适应度越大的个体，被选择的可能性就越大，它的“子孙”在下一代的个数就越多。选择出来的个体被放入配对库中。
目前常用的选择方法有轮赌盘方法（也称适应度比例法）、最佳个体保留法、期望值法、排序选择法、竞争法、线性标准化方法等。
交叉
交叉是指把两个父代个体的部分结构加以替换重组而生成新个
体的操作，交叉的目的是为了能够在下一代产生新的个体。通过交叉操作，遗传算法的搜索能力得以飞跃性的提高。交叉是遗传算法获得新优良个体的最重要的手段。
交叉操作是按照一定的交叉概率Pc在配对库中随机地选取两个
个体进行的。交叉的位置也是随机确定的。交叉概率 Pc 的值一般取得
很大，为 ~。
变异
变异就是以很小的变异概率Pm随机地改变群体中个体的某些基
因的值。变异操作的基本过程是：产生一个[ 0,1] 之间的随机数rand ，
如果 randPm，则进行变异操作。
变异操作本身是一种局部随机搜索，与选择、交叉算子结合在一
起，能够避免由于选择和交叉算子而引起的某些信息的永久性丢失，
保证了遗传算法的有效性，使遗传算法具有局部的随机搜索能力，同
时使得遗传算法能够保持群体的多样性，以防止出现未成熟收敛。变
6 / 32
异操作是一种防止算法早熟的措施。在变异操作中，变异概率不能取
值太大，如果 Pm0. 5 ，遗传算法就退化为随机搜索，而遗传算法的
一些重要的数学特性和搜索能力也就不复存在了。
基本步骤
遗传算法的基本步骤如下：
1）在一定编码方案下，随机产生一个初始种群；
2）用相应的解码方法，将编码后的个体转换成问题空间的决策变量，
并求得个体的适应值；
3）按照个体适应值的大小，从种群中选出适应值较大的一些个体构
成交配池；
4）由交叉和变