遗传算法与优化问题
一、问题背景与实验目的
遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的。遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位。 1．遗传算法的基本原理
遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程。它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体。这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代。后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程。群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解。值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）。
（1）遗传算法中的生物遗传学概念
由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念。 首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系。这些概念如下：
1个体——要处理的基本对象、结构，也就是可行解。 2群体——个体的集合，被选定的一组可行解。 3染色体——个体的表现形式，可行解的编码。 4基因——染色体中的元素编码中的元素。
5基因位——某一基因在染色体中的位置元素在编码中的位置。
6适应值——个体对于环境的适应程度，或在环境压力下的生存能力，可行解所对应的适应函数值。
7种群——被选定的一组染色体或个体根据入选概率定出的一组可行解。 8选择——从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉小的可行解。
9交叉——一组染色体上对应基因段的交换，根据交叉原则产生的一组新解。
10交叉概率——染色体对应基因段交换的概率（可能性大小），闭区间[0,1]上的一个值，一般为0.65~0.90。
11变异——染色体水平上基因变化编码的某些元素被改变。
12变异概率——染色体上基因变化的概率（可能性大小），开区间(0,1)内的一个值, 一般为0.001~0.01。
13进化——适者生存个体进行优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行解。 （2）遗传算法的步骤
遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection）、交叉（Crossover）、变异（Mutation）。
遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解。然后，把这些假
设的可行解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群。经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解。 下面给出遗传算法的具体步骤，流程图参见图1：
第一步：选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 第二步：定义适应函数，便于计算适应值；
第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；
第四步：随机产生初始化群体；
第五步：计算群体中的个体或染色体解码后的适应值；
第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体； 第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略再返回第六步．
图1 一个遗传算法的具体步骤
遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要步骤，此算法会一直运行直到找到满足条件的最优解为止． 2．遗传算法的实际应用 例子：设 f (x1, x2) = 21.5 + x1·sin(4p x1) + x2·sin(20p x2)，求max f (x1, x2)。其中 -3.0 <= x1<= 12.1，4.1<=x2<=5.8。
注：这是一个非常简单的二元函数求极值的问题，相信大家都会做。在此我们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题。在此将细化地给出遗传算法的整个过程。
（1）编码和产生初始群体
首先第一步要确定编码的策略，也就是说如何把x1和x2在各自的区间内的数用计算机语言表示出来。编码就是表现型到基因型的映射，编码时要注意以下三个原则：
a完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体位串）的表现型；
b健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解；
c非冗余性：染色体和潜在解必须一一对应。
这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个{0，1}二进制串．当然，串长取决于求解的精度．如果要设定求解精度到六位小数，由于x1和x2区间长度分别为15.1和1.7，因此
所以，m = m1 + m2 = 18 +15 = 33 bits，即如下所示。
将一个二进制串（b32b31b30…b1b0）代表的二进制数化为10进制数：
如上所示：
首先我们来随机的产生一个个体数为10个的初始群体如下： pop(1)={
[000001010100101001101111011111110]， [001110101110011000000010101001000]， [111000111000001000010101001000110]， [100110110100101101000000010111001]， [000010111101100010001110001101000]， [111110101011011000000010110011001]， [110100010011111000100110011101101]， [001011010100001100010110011001100]， [111110001011101100011101000111101]， [111101001110101010000010101101010]， }
化成十进制的数分别为：
pop(1)={ [-2.687969 5.361653]，[ 0.474101 4.170144]，[10.419457 4.661461]，[ 6.159951 4.109598]，[ -2.301286 4.477282]，[11.788084 4.174346]，[ 9.342067 5.121702]，[ -0.330256 4.694977]，[11.671267 4.873501]，[11.446273 4.171908]} 接下来我们就要解决每个染色体个体的适应值问题了． （2）定义适应函数和适应值
由于给定的目标函数f (x1, x2) = 21.5 + x1·sin(4p x1) + x2·sin(20p x2)
在-3.0 <= x1<= 12.1内的值有正有负，而在4.1<=x2<=5.8内的值均为正。所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对
应于适应值增大的方向，也为以后计算各个体的入选概率打下基础。 对于本题中的最大化问题，定义适应函数
既可以是特定的输入值，也可以是当前所有代或最近K代中f(x1,x2)的最小值，这里为了便于计算，将采用了一个特定的输入值，例如：若取x1=-2.687969，则当x2= 5.361653时适应函数eval(v1) = f (-2.687969, 5.361653) =19.805119。V1=(x1=-2.687969, x2= 5.361653)。 由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下（Matlab程序参见附录）： f [pop(1)]={
eval(v1) = f (-2.687969, 5.361653) =19.805119 eval(v2) = f (0.474101, 4.170144) = 17.370896 eval(v3) = f (10.419457, 4.661461) = 9.590546 eval(v4) = f (6.159951, 4.109598) = 29.406122 eval(v5) = f (-2.301286, 4.477282) = 15.686091 eval(v6) = f (11.788084, 4.174346) = 11.900541 eval(v7) = f (9.342067, 5.121702) = 17.958717 eval(v8) = f (-0.330256, 4.694977) = 19.763190 eval(v9) = f (11.671267, 4.873501) = 26.401669 eval(v10) = f (11.446273, 4.171908) = 10.252480 } 从中可以看出v4是最好的下一代，而v3则是最不好的下一代。然后通过适应函数计算出适应值。
（3）确定选择标准
这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率。其计算公式如下： 对于给定的规模为n的群体pop={的适应值为
，则其入选概率为
}，个体
由上述给出的群体，我们可以计算出各个个体的入选概率．首先可得
然后分别用10个个体的适应值去除以F，得：
（4）产生种群
计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群。
要说明的是：为保证收敛性，对算法作了修正，采用了最佳个体保存方法（elitist model），具体内容将在后面给出介绍。
由初始群体的入选概率我们淘汰掉较弱的个体，再加入新的个体补足成与群体同样大小的种群得到newpop(1)如下： newpop(1)={
v1' = [100110110100101101000000010111001] (v4 ) v2' = [100110110100101101000000010111001] (v4 ) v3' = [001011010100001100010110011001100] (v8 ) v4' = [111110001011101100011101000111101] (v9 ) v5' = [100110110100101101000000010111001] (v4 ) v6' = [110100010011111000100110011101101] (v7 ) v7' = [001110101110011000000010101001000] (v2 ) v8' = [100110110100101101000000010111001] (v4 ) v9' = [000001010100101001101111011111110] (v1 ) v10' = [001110101110011000000010101001000] (v2 ) }
（5）交叉
交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体。我们把之前得到的newpop(1)的10个个体两两组成一对，重复的不配对，进行交叉。（可以在任一位进行交叉）
交叉得：
通过交叉得到了10个新个体，得到新的群体jchpop (1)。这里采用的是单点交叉的方法，当然还有多点交叉的方法，不过有些烦琐，这里就不着重介绍了。 （6）变异
变异也就是通过一个小概率改变染色体位串上的某个基因。现把刚得到的jchpop(1)中某个个体中的某一位改变，就产生了变异，得到了新的群体pop(2)。变异过程如下：
变异为：
新的群体pop(2)={
v1' = [100110110100101101000000010111001], f (6.159951, 4.109598) = 29.406122 v2' = [100110110100101101000000010111001], f (6.159951, 4.109598) = 29.406122 v3' = [001011010100001100010110011001100], f (-0.330256, 4.694977) = 19.763190 v4' = [111110001011101100011101000111101], f (11.907206, 4.873501) = 5.702781 v5' = [100110110100101101000000010111001], f (8.024130, 4.170248) = 19.91025 v6' = [110100010011111000100110011101101], f (9.34067, 5.121702) = 17.958717 v7' = [100110110100101101000000010111001], f (6.159951, 4.109598) = 29.406122
v8' = [100110110100101101000000010111001], f (6.159951, 4.109598) = 29.406122 v9' = [000001010100101001101111011111110], f (-2.687969, 5.361653) = 19.805199 v10' = [001110101110011000000010101001000], f (0.474101, 4.170248) = 17.370896} 然后重复上述的选择、交叉、变异直到满足终止条件为止。 （7）终止条件
遗传算法的终止条件有两类常见条件：（1）采用设定最大（遗传）代数的方法，一般可设定为50代，此时就可能得出最优解．此种方法简单易行，但可能不是很精确；（2）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制。 3．遗传算法的收敛性
前面我们已经就遗传算法中的编码、适应度函数、选择、交叉和变异等主要操作的基本内容及设计进行了详细的介绍。作为一种搜索算法，遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索，具体实现见下图2所示。
图2 均衡搜索的具体实现图示
应该指出的是，遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决。目前普遍认为，标准遗传算法并不保证全局最优收敛。但是，在一定的约束条件下，遗传算法可以实现这一点。 下面我们不加证明地罗列几个定理或定义，供读者参考（在这些定理的证明中，要用到许多概率论知识，特别是有关马尔可夫链的理论，读者可参阅有关文献）。 定理1 如果变异概率为
，交叉概率为
，同时采用比例选择法（按个体
适应度占群体适应度的比例进行复制），则标准遗传算法的变换矩阵P是基本的。
定理2 标准遗传算法（参数如定理1）不能收敛至全局最优解。 由定理2可以知道，具有变异概率
，交叉概率为
。
以及按比例选择的标准遗传算法是不能收敛至全局最最优解。我们在前面求解例题时所用的方法就是满足定理1的条件的方法。这无疑是一个令人沮丧的结论。
然而，庆幸的是，只要对标准遗传算法作一些改进，就能够保证其收敛性。具体如下：我们对标准遗传算法作一定改进，即不按比例进行选择，而是保留当前所得的最优解（称作超个体）。该超个体不参与遗传。 最佳个体保存方法（elitist model）的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中。此种选择操作又称复制（copy）。De Jong对此方法作了如下定义： 定义 设到时刻t（第t代）时，群体中a*（t）为最佳个体。又设A（t＋1）为新一代群体，若A（t＋1）中不存在a*（t），则把a*(t)作为A（t＋1）中的第n+1个个体（其中，n为群
体大小）。
采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏．但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解。也就是说，该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索。所以此方法一般都与其他选择方法结合使用。
定理3 具有定理1所示参数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解。 当然，在选择算子作用后保留当前最优解是一项比较复杂的工作，因为该解在选择算子作用后可能丢失。但是定理3至少表明了这种改进的遗传算法能够收敛至全局最优解。有意思的是，实际上只要在选择前保留当前最优解，就可以保证收敛，定理4描述了这种情况。 定理4 具有定理1参数的，且在选择前保留当前最优解的遗传算法可收敛于全局最优解。
根据上面所述，得出程序运行的结果如下：
这里X表示x1，Y表示x2，Z表示f(x1,x2)，根据Matlab中代码编写的简便，将变量做了适当的修改，方便代码的编写。下图即为程序运行的结果图，图中的红圈，即为取得最优解时的点所在的位置。
matlab作业—遗传算法与优化问题
