数学建模遗传算法与优化问题

一、问题背景与实验目的

遗传算法（Genetic Algorithm—GA），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的教授于1975年首先提出的．遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显着特点，奠定了它作为21世纪关键智能计算之一的地位．

本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，使读者能够学会利用遗传算法进行初步的优化计算．

1．遗传算法的基本原理

遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程．它把问题的参数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而得到一个由具有不同染色体的个体组成的群体．这个群体在问题特定的环境里生存竞争，适者有最好的机会生存和产生后代．后代随机化地继承了父代的最好特征，并也在生存环境的控制支配下继续这一过程．群体的染色体都将逐渐适应环境，不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解．值得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生物界对此学说尚有争议）．

（1）遗传算法中的生物遗传学概念

由于遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要用到各种进化和遗传学的概念．

首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系．这些概念如下： 序号 遗传学概念 遗传算法概念 数学概念 1 个体 要处理的基本对象、结构 也就是可行解 2 群体 个体的集合 被选定的一组可行解 3 染色体 个体的表现形式 可行解的编码 4 基因 染色体中的元素 编码中的元素 5 基因位 某一基因在染色体中的位置 元素在编码中的位置 6 适应值 个体对于环境的适应程度，可行解所对应的适应函数或在环境压力下的生存能力 值 7 种群 被选定的一组染色体或个体 根据入选概率定出的一组可行解 8 选择 从群体中选择优胜的个体，保留或复制适应值大的可淘汰劣质个体的操作 行解，去掉小的可行解 9 交叉 一组染色体上对应基因段的根据交叉原则产生的一组交换 新解 10 交叉概率 染色体对应基因段交换的概闭区间[0,1]上的一个值，率（可能性大小） 一般为~ 11 变异 染色体水平上基因变化 编码的某些元素被改变 染色体上基因变化的概率开区间(0,1)内的一个值, （可能性大小） 一般为~ 13 进化、 个体进行优胜劣汰的进化，目标函数取到最大值，最适者生存 一代又一代地优化 优的可行解 （2）遗传算法的步骤 遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有三个基本操作（或称为算子）：选择（Selection）、交叉（Crossover）、变异（Mutation）．

遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设的可行解．然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产生更适应环境的新一代“染色体”群．经过这样的一代一代地进化，最后就会收敛到最适应环境的一个“染色体”上，它就是问题的最优解．

下面给出遗传算法的具体步骤，流程图参见图1：

第一步：选择编码策略，把参数集合（可行解集合）转换染色体结构空间； 第二步：定义适应函数，便于计算适应值；

第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、变异概率等遗传参数；

第四步：随机产生初始化群体；

第五步：计算群体中的个体或染色体解码后的适应值；

第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体；

第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返回第五步、或者修改遗传策略再返回第六步．

产生初始群体 12 变异概率 得到结果 是 是否满足终止条件 否 结束程序 计算每个个体的适应值 以概率选择遗传算子 选择一个个体复制到新群体 选择两个个体进行交叉插入到新群体 选择一个个体进行变异插入到新群体 得到新群体 图1 一个遗传算法的具体步骤

遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要步骤，此算法会一直运行直到找到满足条件的最优解为止．

2．遗传算法的实际应用

例1：设f(x)x22x0.5，求 maxf(x), x[1,2]．

注：这是一个非常简单的二次函数求极值的问题，相信大家都会做．在此我们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题．

在此将细化地给出遗传算法的整个过程． （1）编码和产生初始群体 首先第一步要确定编码的策略，也就是说如何把1到2这个区间内的数用计算机语言表示出来．

编码就是表现型到基因型的映射，编码时要注意以下三个原则：

完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体位串）的表现型；

健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解； 非冗余性：染色体和潜在解必须一一对应．

这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个{0，1}二进制串．当然，串长取决于求解的精度．如果要设定求解精度到六位小数，由于区间长度为2(1)3，则必须将闭区间 [1,2]分为3106等分．因为209715222131062224194304 所以编码的二进制串至少需要22位．

将一个二进制串（b21b20b19…b1b0）转化为区间[1,2]内对应的实数值很简单，只需采取以下两步（Matlab程序参见附录4）：

1）将一个二进制串（b21b20b19…b1b0）代表的二进制数化为10进制数：

(b21b20b19b1b0)2(bi2i)10x'

i0212）x' 对应的区间[1,2]内的实数：

2(1)2221

例如，一个二进制串a=<1>表示实数． x'=(1)2=2288967

3x12288967220.63719721

二进制串<0000000000000000000000>，<1>，则分别表示区间的两个端点值-1和2．

利用这种方法我们就完成了遗传算法的第一步——编码，这种二进制编码的方法完全符合上述的编码的三个原则．

首先我们来随机的产生一个个体数为4个的初始群体如下： pop(1)={

<0>， %% a1

<001000010>， %% a2 <000000000>， %% a3

<0>} %% a4（Matlab程序参见附录2） 化成十进制的数分别为：

x1x'pop(1)={ ， ， ， }

接下来我们就要解决每个染色体个体的适应值问题了． （2）定义适应函数和适应值

由于给定的目标函数f(x)x22x0.5在[1,2]内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础．

对于本题中的最大化问题，定义适应函数g(x)，采用下述方法：

f(x)Fmin,若 f(x)Fmin0 g(x)0,其他式中Fmin既可以是特定的输入值，也可以是当前所有代或最近K代中f(x)的最小值，这里为了便于计算，将采用了一个特定的输入值．

若取Fmin1，则当f(x)1时适应函数g(x)2；当f(x)1.1时适应函数

g(x)0．

由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下（Matlab程序参见附录3）：

f [pop(1)]={ , , , }

然后通过适应函数计算出适应值分别如下（Matlab程序参见附录5、附录6）： 取Fmin1，

g[pop(1)]= { , , 0 , } （3）确定选择标准

这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选概率．其计算公式如下：

对于给定的规模为n的群体pop={a1,a2,a3,L,an}，个体ai的适应值为g(ai)，则其入选概率为

Ps(ai)g(ai)g(a)ii1n,i1,2,3,,n

由上述给出的群体，我们可以计算出各个个体的入选概率． 首先可得

g(a)6.478330，

ii14i14然后分别用四个个体的适应值去除以g(ai)，得：

P(a1)= / = %% a1 P(a2)= / = %% a2

P(a3)= 0 / = 0 %% a3

P(a4)= / = %% a4（Matlab程序参见附录7） （4）产生种群

计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体，并用入选概率最大的个体补入种群，得到与原群体大小同样的种群（Matlab程序参见附录8、附录11）．

要说明的是：附录11的算法与这里不完全相同．为保证收敛性，附录11的算法作了修正，采用了最佳个体保存方法（elitist model），具体内容将在后面给出介绍．

由初始群体的入选概率我们淘汰掉a3，再加入a2补足成与群体同样大小的种群得到newpop(1)如下：

newpop(1)={ <0>， %% a1

<001000010>， %% a2 <001000010>， %% a2 <0>} %% a4 （5）交叉

交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体（Matlab程序参见附录9）．

我们把之前得到的newpop(1)的四个个体两两组成一对，重复的不配对，进行交叉．（可以在任一位进行交叉）

<0 >， <001000010>

交叉得： <0 >， <0>

<0 01000010>， <0>

交叉得： <0 >， <001000010>

通过交叉得到了四个新个体，得到新的群体jchpop (1)如下： jchpop(1)={ <001000010>， <0>， <0>，

<001000010>}

这里采用的是单点交叉的方法，当然还有多点交叉的方法，不过有些烦琐，这里就不着重介绍了． （6）变异

变异也就是通过一个小概率改变染色体位串上的某个基因（Matlab程序参见附录10）．

现把刚得到的jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到了新的群体pop(2)如下：

pop(2)= {

<001000010>， <0>， <0>，

<001000010> }

然后重复上述的选择、交叉、变异直到满足终止条件为止． （7）终止条件

遗传算法的终止条件有两类常见条件：（1）采用设定最大（遗传）代数的方

法，一般可设定为50代，此时就可能得出最优解．此种方法简单易行，但可能不是很精确（Matlab程序参见附录1）；（2）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制．

3．遗传算法的收敛性

前面我们已经就遗传算法中的编码、适应度函数、选择、交叉和变异等主要操作的基本内容及设计进行了详细的介绍．作为一种搜索算法，遗传算法通过对这些操作的适当设计和运行，可以实现兼顾全局搜索和局部搜索的所谓均衡搜索，具体实现见下图2所示．

图2 均衡搜索的具体实现图示

应该指出的是，遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决．目前普遍认为，标准遗传算法并不保证全局最优收敛．但是，在一定的约束条件下，遗传算法可以实现这一点．

下面我们不加证明地罗列几个定理或定义，供读者参考（在这些定理的证明中，要用到许多概率论知识，特别是有关马尔可夫链的理论，读者可参阅有关文献）．

定理1 如果变异概率为Pm(0,1)，交叉概率为Pc[0,1]，同时采用比例选择法（按个体适应度占群体适应度的比例进行复制），则标准遗传算法的变换矩阵P是基本的．

定理2 标准遗传算法（参数如定理1）不能收敛至全局最优解．

由定理2可以知道，具有变异概率Pm(0,1)，交叉概率为Pc[0,1]以及按比例选择的标准遗传算法是不能收敛至全局最最优解．我们在前面求解例1时所用的方法就是满足定理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为群体大小）（Matlab程序参见附录11）．

采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏．但是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能限于局部解．也就是说，该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是多峰性质的空间搜索．所以此方法一般都与其他选择方法结合使用．

定理3 具有定理1所示参数，且在选择后保留当前最优值的遗传算法最终能收敛到全局最优解．

当然，在选择算子作用后保留当前最优解是一项比较复杂的工作，因为该解在选择算子作用后可能丢失．但是定理3至少表明了这种改进的遗传算法能够收敛至全局最优解．有意思的是，实际上只要在选择前保留当前最优解，就可以保证收敛，定理4描述了这种情况．

定理4 具有定理1参数的，且在选择前保留当前最优解的遗传算法可收敛于全局最优解．

例2：设f(x)3x2x，求 maxf(x), x[0,2]，编码长度为5，采用上述定理4所述的“在选择前保留当前最优解的遗传算法”进行．

此略，留作练习．

二、相关函数（命令）及简介

本实验的程序中用到如下一些基本的Matlab函数：ones, zeros, sum, size, length, subs, double 等，以及 for, while 等基本程序结构语句，读者可参考前面专门关于Matlab的介绍，也可参考其他数学实验章节中的“相关函数（命令）及简介”内容，此略．

三、实验内容

上述例1的求解过程为：

群体中包含六个染色体，每个染色体用22位0—1码，变异概率为，变量区间为 [1,2]，取Fmin=2，遗传代数为50代，则运用第一种终止条件（指定遗传代数）的Matlab程序为：

[Count,Result,BestMember]=Genetic1(22,6,'-x*x+2*x+',-1,2,-2,,50) 执行结果为： Count = 50 Result =

BestMember =

图2 例1的计算结果

（注：上图为遗传进化过程中每一代的个体最大适应度； 而下图为目前为止的个体最大适应度——单调递增）

我们通过Matlab软件实现了遗传算法，得到了这题在第一种终止条件下的最优解：当x取时，Max f(x)1.4990．

当然这个解和实际情况还有一点出入（应该是x取1时，，Max f(x)1.5000）但对于一个计算机算法来说已经很不错了．

我们也可以编制Matlab程序求在第二种终止条件下的最优解．此略，留作练习．实践表明，此时的遗传算法只要经过10代左右就可完成收敛，得到另一个“最优解”，与前面的最优解相差无几．

四、自己动手

1．用Matlab编制另一个主程序，求例1的在第二种终止条件下的最优解． 提示：一个可能的函数调用形式以及相应的结果为：

[Count,Result,BestMember]=Genetic2(22,6,'-x*x+2*x+',-1,2,-2,, Count = 13 Result =

BestMember =

可以看到：两组解都已经很接近实际结果，对于两种方法所产生的最优解差异很小．可见这两种终止算法都是可行的，而且可以知道对于例1的问题，遗传算法只要经过10代左右就可以完成收敛，达到一个最优解． 2．按照例2的具体要求，用遗传算法求上述例2的最优解．

3．附录9子程序 中的第3行到第7行为注解语句．若去掉前面的%号，则程序的算法思想有什么变化？

4．附录9子程序 中的第8行至第13行的程序表明，当Dim(1)>=3时，将交换数组Population的最后两行，即交换最后面的两个个体．其目的是什么？ 5．仿照附录10子程序，修改附录9子程序 ，使得交叉过程也有一个概率值（一般取~）；同时适当修改主程序或主程序，以便代入交叉概率． 6．设f(x)x24x1，求 maxf(x), x[2,2]，要设定求解精度到15位小数．

五、附录

附录1：主程序

function

[Count,Result,BestMember]=Genetic1(MumberLength,MemberNumber,FunctionFitness,MinX,MaxX,Fmin,MutationProbability,Gen)

Population=PopulationInitialize(MumberLength,MemberNumber); global Count;

global CurrentBest; Count=1;

PopulationCode=Population;

PopulationFitness=Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength);

PopulationFitnessF=FitnessF(PopulationFitness,Fmin); PopulationProbability=Probability(PopulationFitnessF);

[Population,CurrentBest,EachGenMaxFitness]=Elitist(PopulationCode,PopulationFitness,MumberLength);

EachMaxFitness(Count)=EachGenMaxFitness;

MaxFitness(Count)=CurrentBest(length(CurrentBest));

while CountNewPopulation=Select(Population,PopulationProbability,MemberNumber); Population=NewPopulation;

NewPopulation=Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength);

Population=NewPopulation;

NewPopulation=Mutation(Population,MutationProbability); Population=NewPopulation;

PopulationFitness=Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength);

PopulationFitnessF=FitnessF(PopulationFitness,Fmin); PopulationProbability=Probability(PopulationFitnessF); Count=Count+1;

[NewPopulation,CurrentBest,EachGenMaxFitness]=Elitist(Population,PopulationFitness,MumberLength);

EachMaxFitness(Count)=EachGenMaxFitness;;

MaxFitness(Count)=CurrentBest(length(CurrentBest)); Population=NewPopulation; end

Dim=size(Population); Result=ones(2,Dim(1)); for i=1:Dim(1)

Result(1,i)=Translate(Population(i,:),MinX,MaxX,MumberLength); end

Result(2,:)=PopulationFitness;

BestMember(1,1)=Translate(CurrentBest(1:MumberLength),MinX,MaxX,MumberLength);

BestMember(2,1)=CurrentBest(MumberLength+1); close all subplot(211)

plot(EachMaxFitness) subplot(212) plot(MaxFitness)

【程序说明】主程序包含了8个输入参数：

(1) MumberLength： 表示一个染色体位串的二进制长度．（例1中取22） (2) MemberNumber： 表示群体中染色体的个数．（例1中取6个）

(3) FunctionFitness： 表示目标函数，是个字符串，因此用表达式时，用单

引号括出．（例1中是f(x)x22x0.5）

(4) MinX： 变量区间的下限．（例1中是[1,2]中的）

(5) MaxX： 变量区间的上限．（例1中是[1,2]中的 2）

(6) Fmin： 定义适应函数过程中给出的一个目标函数的可能的最小值，由操作者自己给出．（例1中取Fmin=2）

(7) MutationProbability： 表示变异的概率，一般都很小．（例1中取） (8) Gen： 表示遗传的代数，也就是终止程序时的代数．（例1中取50）

另外，主程序包含了3个输出值： Count 表示遗传的代数；Result 表示计算的结果，也就是最优解；BestMember表示最优个体及其适应值．

附录2：子程序

function Population=PopulationInitialize(MumberLength,MemberNumber) Temporary=rand(MemberNumber,MumberLength); Population=(Temporary>=*ones(size(Temporary)));

【程序说明】子程序 用于产生一个初始群体．这个初始群体含有MemberNumber个染色体，每个染色体有MumberLength个基因（二进制码）．

附录3：子程序

function PopulationFitness=

Fitness(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)

Dim=size(PopulationCode);

PopulationFitness=zeros(1,Dim(1)); for i=1:Dim(1)

PopulationFitness(i)=

Transfer(PopulationCode(i,:),FunctionFitness,MinX,MaxX,MumberLength);

end

【程序说明】子程序用于计算群体中每一个染色体的目标函数值．子程序中含有5个输入参数：PopulationCode表示用0—1代码表示的群体，FunctionFitness 表示目标函数，它是一个字符串，因此写入调用程序时，应该用单引号括出，MumberLength表示染色体位串的二进制长度．MinX和MaxX 分别指变量区间的上下限．

附录4：子程序

function PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength)

PopulationData=0;

Dim=size(PopulationCode); for i=1:Dim(2)

PopulationData=PopulationData+PopulationCode(i)*(2^(MumberLength-i)); end

PopulationData=MinX+PopulationData*(MaxX-MinX)/(2^Dim(2)-1);

【程序说明】子程序 把编成码的群体翻译成变量的数值．含有4个输入参数，PopulationCode, MinX, MaxX, MumberLength．

附录5：子程序

function PopulationFitness=

Transfer(PopulationCode,FunctionFitness,MinX,MaxX,MumberLength)

PopulationFitness=0;

PopulationData=Translate(PopulationCode,MinX,MaxX,MumberLength); PopulationFitness=double(subs(FunctionFitness,'x',sym(PopulationData)));

【程序说明】子程序 Transfer 把群体中的染色体的目标函数值用数值表示出来，它是Fitness的重要子程序．其有5个输入参数分别为PopulationCode, FunctionFitness, MinX, MaxX，MumberLength．

附录6：子程序

function PopulationFitnessF=FitnessF(PopulationFitness,Fmin) Dim=size(PopulationFitness);

PopulationFitnessF=zeros(1,Dim(2)); for i=1:Dim(2)

if PopulationFitness(i)>Fmin

PopulationFitnessF(i)=PopulationFitness(i)-Fmin; end

if PopulationFitness(i)<=Fmin

PopulationFitnessF(i)=0; end end

【程序说明】子程序是用于计算每个染色体的适应函数值的．其输入参数如下：PopulationFitness 为群体中染色体的目标函数值，Fmin为定义适应函数过程中给出的一个目标函数的可能的最小值．

附录7：子程序

function PopulationProbability=Probability(PopulationFitness) SumPopulationFitness=sum(PopulationFitness);

PopulationProbability=PopulationFitness/SumPopulationFitness;

【程序说明】子程序 用于计算群体中每个染色体的入选概率，输入参数为群体中染色体的适应函数值PopulationFitness．

附录8：子程序

function NewPopulation=

Select(Population,PopulationProbability,MemberNumber) CProbability(1)=PopulationProbability(1);

for i=2:MemberNumber

CProbability(i)=CProbability(i-1)+PopulationProbability(i); end

for i=1:MemberNumber r=rand(1); Index=1;

while r>CProbability(Index) Index=Index+1; end

NewPopulation(i,:)=Population(Index,:); end

【程序说明】子程序 根据入选概率（计算累计概率）在群体中按比例选择部分染色体组成种群，该子程序的3个输入参数分别为：群体Population，入选概率PopulationProbability，群体中染色体的个数MemberNumber．

附录9：子程序

function NewPopulation=

Crossing(Population,FunctionFitness,MinX,MaxX,MumberLength)

%%PopulationFitness=

%% Fitness(Population,FunctionFitness,MinX,MaxX,MumberLength); %%PopulationProbability=Probability(PopulationFitness); %%[SortResult,SortSite]=sort(PopulationProbability); %%Population=Population(SortSite,:); Dim=size(Population); if Dim(1)>=3

Temp=Population(Dim(1),:);

Population(Dim(1),:)=Population(Dim(1)-1,:); Population(Dim(1)-1,:)=Temp; end

for i=1:2:Dim(1)-1

SiteArray=randperm(Dim(2)); Site=SiteArray(1);

Temp=Population(i,1:Site);

Population(i,1:Site)=Population(i+1,1:Site); Population(i+1,1:Site)=Temp; end

NewPopulation=Population;

【程序说明】子程序 用于群体中的交叉并产生新群体．其输入参数为：Population, FunctionFitness，MinX，MaxX，MumberLength．

附录10：子程序

function NewPopulation=Mutation(Population,MutationProbability)

Dim=size(Population); for i=1:Dim(1)

Probability=rand(1); Site=randperm(Dim(2));

if Probabilityif Population(i,Site(1))==0 Population(i,Site(1))=1; end end end

NewPopulation=Population;

【程序说明】子程序用于群体中少量个体变量并产生新的群体．输入参数为：群体Population和变异概率MutationProbability．

附录11：子程序

function [NewPopulationIncludeMax,CurrentBest,EachGenMaxFitness]= Elitist(Population,PopulationFitness,MumberLength)

global Count CurrentBest;

[MinFitness,MinSite]=min(PopulationFitness); [MaxFitness,MaxSite]=max(PopulationFitness); EachGenMaxFitness=MaxFitness; if Count==1

CurrentBest(1:MumberLength)=Population(MaxSite,:);

CurrentBest(MumberLength+1)=PopulationFitness(MaxSite); else

if CurrentBest(MumberLength+1)CurrentBest(MumberLength+1)=PopulationFitness(MaxSite); end

Population(MinSite,:)=CurrentBest(1:MumberLength); end

NewPopulationIncludeMax=Population;

【程序说明】子程序用到最佳个体保存方法（“优胜劣汰”思想）．输入参数为：群体Population, 目标函数值PopulationFitness和染色体个数MumberLength．

“遗传算法”专题

一、遗传算法的主要特征：

我们的目的是获得“最好解”，可以把这种任务看成是一个优化过程。对于小空间，经典的穷举法就足够了；而对大空间，则需要使用特殊的人工智能技术。遗传算法(Genetic Algorithm)是这些技术中的一种，它是一类模拟生物进化过程而产生的由选择算子、杂交算子和变异算子三个基本算子组成的全局寻优算法。它从一个初始族出发，由选择算子选出性状好的父本，由杂交算子进行杂交运算，变异算子进行少许变异，在一定概率规则控制下随机搜索模型空间。一代代进化，直到最终解族对应的误差泛函值达到设定的要求。

遗传算法的结构：

Procedure Genetic Algorithm begin

t0

initialize P(t) evaluate P(t)

while (not termination-condition) do begin

tt1

select P(t) from P(t1) alter P(t) evaluate P(t) end

end

图1. 遗传算法的结构

tt,,xn}。在第t次迭代，遗传算法维持一个潜在解的群体p(t){x1t,x2每个解xit用其“适

应值”评价。然后通过选择更合适个体（t1次迭代）形成一个新的群体。新的群体的成员通过杂交和变异进行变换，形成新的解。杂交组合了两个亲体染色体（即待求参数的二进制编码串）的特征，通过交换父代相应的片断形成了两个相似的后代。例如父代染色体为

(a1,b1,c1,d1,e1)和(a2,b2,c2,d2,e2)，在第二个基因后杂交，产生的后代为(a1,b1,c2,d2,e2)和(a2,b2,c1,d1,e1)。杂交算子的目的是在不同潜在解之间进行信息交换。变异是通过用一个等于变异率的概率随机地改变被选择染色体上的一个或多个基因（染色体中的一个二进制位）。变异算子的意图是向群体引入一些额外的变化性。

遗传算法的特点：

(1). 它不是直接作用于参变量集上，而是作用于参变量的某种编码形成的数字串上。

(2). 它不是从单个点，而是从一个解族开始搜索解空间，与传统的“点对点”式的搜索方法

不同。

(3). 它仅仅利用适应值信息评估个体的优劣，无须求导数或其它辅助信息。 (4). 它利用概率转移规则，而非确定性规则。

优势：

(1). 不容易陷入局部极值，能以很大的概率找到全局最优解。 (2). 由于其固有的并行性，适合于大规模并行计算。

二、遗传算法的运行步骤：

1. 一般性描述：

不失一般性，考虑求最大值的问题。问题：

求一个有k个变量的函数f(x1,x2,,xk): RkR的f的最大值。假设每个变量xi为域Di[ai,bi]R内的一个值，且对所有的xiDi，f(x1,,xk)0。假定以某个要求的精度优化函数f：这里取自变量小数点后第6位。

1） 编码和解码：

要达到要求的精度，每个域Di应该被分割为(biai)106个等尺寸的区间。用mi表示使(biai)1062m1成立的最小整数。这样，对每个变量xi，由串长为mi的二进

i制编码表达可以满足精度要求。以下的公式对应于每个串的自变量的值：

biai m21其中decimal(string2)表示二进制串的十进制值。 代表一个潜在解的染色体被长度为mik1mi的二进制串表达；前m1位对应区间[a1,b1]里的一个值，随后的m2位对应区间[a2,b2]里的一个值，等等；最后的mk位对应区间[ak,bk]里的一个值。

xiaidecimal(10010012)2） 产生潜在解初始群体：

简单地以位的方式随机地设定pop_size个染色体。如果确实有一些关于最优分布的知识，可以使用这些信息来设定初始潜在解的集合。 3） 根据适应值评价解的适应程度并据此生成新群体：

通常使用一个根据适应值调节刻度宽度的轮盘。按照如下方法构造轮盘（假设这里

的适应值时正值，否则可以使用一些比例机制调整）：

● ●

计算每个染色体vi(i1,,pop_size)的适应值eval(vi)； 计算群体的总适应值：

pop_size F●

eval(v)

ii1计算每个染色体vi(i1,,pop_size)的选择概率pi： 计算每个染色体vi(i1,,pop_size)的累计概率qi：

i1i qieval(vj)pi

Fj1j1 pieval(vi)/F

●

● ●

对轮盘转动pop_size次，每次按照下面的方法为新群体选择一个单个的染色体： 产生一个在区间[0，1]里的随机数；

如果rq1，则选择第一个染色体v1；否则选择使qi1rqi成立的第i个染色体

vi(2ipop_size)。

这样做的效果是：好的染色体得到多个拷贝，中等染色体保持平稳，最差染色体死

亡。

4） 杂交(crossover)和变异(mutation)——决定新群体的性状：

设杂交概率为pc，此概率给出预计要进行杂交的染色体个数pcpop_size。对于新群体中的每个染色体：

● ●

产生一个在区间[0，1]里的随机数r； 如果rpc，则选择给定的染色体进行杂交。

随机地对被选择的染色体配对：对染色体中的每一个，产生一个在区间[1, m1]（m为总长，即染色体位数）里的随机整数pos。pos表示杂交点的位置。两个染色体

(b1b2bposbpos1bm) 和 (c1c2cposcpos1cm)

被他们的子代

(b1b2bposcpos1cm) 和 (c1c2cposbpos1bm)

所替代。

下一步的变异，是在一位一位(bit-by-bit)的基础上进行的。另一个遗传系统参数，变异率pm，给出了我们预计的变异位数：pmmpop_size。整个群体中所有染色体的每一位都有均等的机会经历变异，即从0到1或者相反：

● ●

产生一个在区间[0，1]里的随机数r； 如果rpm，变异此位。

随着选择、杂交和变异的进行，新群体就为下一次的评价做好了准备。该评价是用

来为下一次选择过程建立概率分布的，即建立一个根据当前适应值构造宽距的轮盘。其它的部分只是上述步骤的循环重复，见图1。

2. 例子：

问题：求下列函数的极大值：

f(x1,x2)21.5x1sin(4x1)x2sin(20x2)，

其中3.0x112.1及4.1x25.8。假定对每个变量要求的精度是小数点后第4位。

图2. 函数f(x1,x2)21.5x1sin(4x1)x2sin(20x2)的图

按上面介绍的步骤求解此问题：

1） 解码和解码：

变量x1的定义域长度为，所要求的精度意味着区间[, ]至少要被分为×10000个等距区间。由于217151000218，因此染色体的第一部分需要18位。

变量x2的定义域长度为，所要求的精度意味着区间[, ]至少要被分为×10000个等距区间。由于21417000215，因此染色体的第一部分需要15位。

因此染色体的总长度为m181533位，前18位为x1，后15位为x2。 例如，染色体

(0000010)

的前18位00000表示

x13.0decimal(0100010010110100002)后15位10表示

12.1(3.0)1.052426； 18215.84.15.755330；

2151所以该染色体对应于x1,x21.052426,5.755330，该染色体的适应值为

f(1.052426, 5.755330)20.252640。

x24.1decimal(1111100101000102)2） 产生潜在解初始群体：

设pop_size20，随机产生一个初始化的20个染色体组成的群体，并计算相应的适应函数值：

很明显，染色体v15是最好的，v2是最差的。 3） 根据适应值评价解的适应程度并据此生成新群体：

现在系统为选择过程建立一个轮盘。群体的总适应值为

Feval(v)387.776822

ii120对每个染色体vi(i1,2,,20)，选择概率pi为：

每个染色体vi(i1,2,,20)的累计概率qi为：

现在，准备转动轮盘20次，每次为新群体选择一个单个的染色体。假定在区间[0, 1]里的20个数的一个随机序列是：

第一个数r0.513870大于q10而小于q11，意味着染色体v11被选择；第二个数r0.175741大于q3而小于q4，意味着染色体v4被选择，等等。最后，新群体由以下染色体组成：

4） 杂交(crossover)和变异(mutation)——决定新群体的性状：

设杂交概率pc0.25，所以预计染色体中平均有25%（即20个中的5个）将经历杂交。杂交按照下面的方法进行：对新群体中的每个染色体，产生一个在区间[0, 1]里的随机数r，如果r0.25，则选择一个给定的染色体进行杂交。假定随机序列为：

、v13和v18被选择杂交。这里很幸运，给选择的染色体数是偶数，可这说明染色体v2、v11以很容易地配对；如果选择的染色体数为奇数，可以加入一额外的染色体或者移走一被选择

）染色体，这种选择同样是随机的。对被选择染色体随机进行配对：设为前两个（即v2和v11和v18）被配对。对这两对中的每一对，产生区间[1, 32]（33为染色体总长和后两个（即v13度）里的一个随机整数pos。数字表示杂交点的位置。第一对染色体是：

产生的数为pos9。这对染色体在第9位后的部分互换，生成新的一对染色体：

第二对染色体是：

产生的数为pos20。这对染色体在第20位后的部分互换，生成的新的染色体对为：

群体的当前版本为：

下一步操作——变异是在一位一位基础上进行的。变异概率pm0.01，所以我们预计平均将有1%的位经历变异。整个群体共有mpop_size3320660位；可以预计平均每代有次变异。因为每一位都有均等的机会被变异，所以对群体中的每一位可以产生区间[0, 1]里的一个随机数r，如果r0.01，则变异此位。这说明我们必须产生660个随机数。在运行的例子中，共产生5个小于的数：变异位号和产生的随机数如表所示：

表把染色体中的位号翻译成染色体中的位数：

这就意味着有四个染色体通过变异而改变；其中一个染色体（第13个）有两位基因发生变化。

变异位以黑体表示。对修正的染色体去掉撇号，最新的染色体群体vi如下：

这里只完成了图1中的遗传过程while循环中的一次迭代（即一代）。检查一下新群体的评价过程，对每个染色体进行解码，并计算解码后的(x1,x2)的适应函数值，得到：

注意新群体的总适应值F为，高于先前群体的总适应值。同时，当前最好染色体v11的现在准备再运行以此选择过程：应用遗传算子及评价下一代等。经过1000代后，群体评价值要好于先前群体的最好染色体v15的评价值。 及其适应值为：

但是，仔细检查整个运行过程，可以发现早期代中的某些染色体的适应值要好于经过1000代后的最好染色体值。例如，第396代中的最好染色体的值为。这是由于取样的随机误差造成的。跟踪进化过程中的最好个体是容易的。在遗传算法的实现中，通常在一独立出来的位置保存“曾经最好”的个体；用这种方法，算法将报告整个过程的最好值，而不只是最终群体的最好值。

三、遗传算法的理论基础：

遗传算法的理论基础是遗传算法解的二进制表达式及模式的含义。模式是能对染色体之间相似性进行解释的模板。一个模式是通过引入通配符(*)到基因字母表中来建立的。一个模式代表所有的除“*”外与所有位置都匹配的所有串（搜索空间的子集）。例如，考虑长度为10的串和模式。模式(*)与两个串匹配：{(00), (00)}。而模式(*1*1100100)与四个串匹配：{(00), (00), (00), (00)}。显然，模式(01)只代表一个串，而模式(**********)代表所有长度为10的串。很明显，每种模式精确地代表2r个串，这里r为通配符(*)在模式模板中的个数。另一方面，每个长度为m的串匹配2m个模式（每位上可以为原数码和*两种可能）。

不同的模式有不同的特性。注意到：在一个模式中通配符*的数目决定了匹配该模式的模式S的阶（由o(S)表示），为串中0和1的数目，即固定位而非通配位的数目。换句串数。有两个重要的模式性质：阶和定义长度。模式定理是在这些性质的基础上表达的。 话说，它是模板长度减去通配符(*)的数目。一个模式的阶定义了模式的特殊性。如下面三个长度为10的模式：

S1(***001*110)，S2(****00**0*)，S3(11101**001)

的阶为：o(S1)6，o(S2)3及o(S3)8。其中模式S3是最特殊的一个。模式的阶对计算变异操作种模式的存活概率时很有用的，随后将讨论。 模式的定义长度（由(S)表示），为第一个和最后一个固定串位之间的距离。它定义了

(S1)1046，(S2)954和(S3)1019。包含在模式中的信息的致密度。如，

注意，只有单个固定点的模式的定义长度为零。模式的定义长度在计算模式杂交的存活概率时很有用，随后讨论。 遗传算法模拟进化过程包括四个不断重复的步骤： tt1

select P(t) from P(t1) recombine P(t) evaluate P(t)

第一步（tt1）简单地将演化时钟向前移动一个单位；最后一步（evaluate P(t)）只是对当前群体进行评价。发生在进化周期其余两个阶段的主要现象是选择和重组。这里将

讨论这两步作用在群体中预定数目的模式上的效果。首先从运行一个例子开始来说明所有的定理。

1． 选择：

仍然采用上一节的例子，群体规模pop_size20，模式模板的长度m33。假定在时刻t，群体为原先初始化的结果（见P4的v1~v20）。(S,t)表示时刻t时群体中匹配模式S

的串数，如对于一个给定模式：S0(****111**************************)，

(S0,t)3，因为有3个串v13，v15和v16匹配模式S0。注意模式S0的阶o(S0)3，其定义长度(S0)752。

模式在时刻t的适应值eval(S,t)定义为群体中和模式S匹配的所有串的平均适应值。假定在时刻t，群体中匹配模式S的串有p个{vS1,,vSp}，则

eval(S,t)eval(vj1pSj)/p

在选择过程中，中间群体是这样产生的：对pop_size20个单个串进行选择。每个串根据其适应值被拷贝零次、一次或多次。如在先前的例子中看到的那样，在一个单个串的选择中，串vi被选择的概率pieval(vi)/F(t)，其中F(t)为整个群体在时刻t的总适应值。

设经过选择步骤，有(S,t1)个串被模式S匹配。因为：(1) 对一个被模式S匹配的一般串，在一个单个串的选择中，其选择概率约等于eval(S,t)/F(t)；(2) 被模式S匹配的串数为(S,t)；(3) 单个串的选择数目为pop_size，很明显，

(S,t1)(S,t)pop_sizeeval(S,t)/F(t)

因为群体的平均适应值F(t)F(t)/pop_size，所以上式可写为

(S,t1)(S,t)eval(S,t)/F(t)(1)

这就意味着一个适应值在平均值之上的模式在下一代中的串数会增加，一个适应值低于平均的模式在下一代中的串数会减小，而一个中庸的模式将保持不变的水平。

上述规则的长期效果是明显的。如果假定模式S高出平均，即

eval(S,t)F(t)F(t)，

那么 (S,t)(S,0)(1)t， 且 (eval(S,t)F(t))/F(t)，

其中，0相应于平均值之上的模式；0相应于平均值之下的模式。

这是一个几何级数方程：一个平均值之上的模式不仅在下一代中串数增长，而且是几何增长。

把方程（1）称为复制模式增长方程。 回到模式S0，因为在时刻t有3个串v13，v15和v16匹配模式S0，模式的适应值eval(S0)为：

eval(S0,t)(27.31670230.06020523.867227)/327.081378 同时，整个群体的平均适应值为： F(t)20eval(v)/pop_size387.776822/2019.388841

ii1模式S0的适应值与群体平均适应值的比例为：

eval(S0,t)/F(t)1.396751

这就意味着如果模式S0保持在平均之上，那么它将在下一代中保持串数的几何增长。特别地，如果模式S0保持在平均值之上的因子为，在时刻t1，预计可以得到3*= 个串（可能有4个或5个）被模式S0匹配；在时刻t2，有3*= 个串，即可能有6个串，等等。根据直觉，S0的模式定义了搜索空间中极有希望的一部分，并且它以几何增长的方式被复制。

~v可以用以前的实例检验对S0的预测。在时刻t1，新的群体见P5下方的v120。可见，

模式S0在时刻t1匹配5个串：v7、v11、v18、v19和v20。

然而，选择本身不能产生新的潜在解，只能从中间群体中复制一些串。所以在进化周期的第二步（重组）中向群体中引入了新个体。这是通过杂交和变异两个算子完成的。以下依次讨论两个算子作用于群体中模式的效果。

2． 杂交：

： 考虑下面的例子：如在前面讨论的，群体中一个单独个体的串，设为v18

(111011111010001000110000001000110)

被233种模式匹配；该串同时被下面两个模式匹配：

S0(****111**************************) S1(111****************************10)

和v13被选择进行杂 进一步假定上述串被选择用来杂交。根据上一节的例子（个体v18交），假定杂交位置为pos20。很明显，模式S0生存下来，即有一个后代仍然匹配S0。因为杂交在一个后代串上保存了第5，6，7位上的序列“111”。 杂交前

(11101111101000100011|000001000110) v18(00010100001001010100|1010111111011) v13杂交后

(11101111101000100011|1010111111011) v18(00010100001001010100|0000001000110) v13

另一方面，模式S1遭破坏：子代不与它匹配。因为在模板开始的固定位“111”和结尾很明显，模式的定义长度对其生存和损坏的概率起着很重要的作用。注意模式S0的定通常，杂交位是在m1中可能的位置上被唯一地选择的。这就意味着模式S的最大消的固定位“10”分布在不同的子代上。

义长度为(S0)2，而模式S1的定义长度为(S1)32。 亡概率为

pd(S)因此，该模式的最小存活概率为

m1实际上，我们的例子中的模式S0和S1的存活概率和消亡概率分别为：

pd(S0)2/32， ps(S0)30/32 pd(S1)32/32， ps(S1)0

所以结果是可以预测的。

注意实际上只有一些染色体经历杂交，并且杂交的选择性概率为pc。这说明一个模式的最小存活概率实际上为：

(S)m1

ps(S)1(S) m1再一次参考前面例子中的模式S0(pc0.25)：

pd(S0)10.252/3263/640.984375

注意，尽管杂交位置是在一个模式的固定位置之间选择的，该模式仍然有机会存活。例

和v13都是以“111”开始，如，如果串v18“10”结尾，模式S1将杂交存活，当然，这种可

能性非常小。因此，模式的存活概率为

(S) ps(S)1pcm1 所以，选择和杂交的结合给出了一个新的形式的复制模式生长公式：

ps(S)1pc(S)(S,t1)(S,t)eval(S,t)1pc(2)

(S)/F(t)m1

公式(2)告诉我们在下一代中匹配模式S的预测串数是实际匹配模式串数、模式的相对适应值及模式的定义长度的函数。显然，在平均之上，短的定义长度的模式将按照几何增长的速率被复制。对模式S0：

这说明短的、平均值之上的模式S0将在下一代中出现几何增长的串数：在时刻t1，预测有3*= 个串被模式S0匹配；在时刻t2，将有3*= 个串被模式S0匹配。

3． 变异：

变异算子以概率pm随机地改变一个染色体中的某一位。其变化为从0到1或者相反。很明显，如果模式经过变异还存活，该模式上的所有固定位应保持不变。再一次考虑群体中

： 的一个串，设为v19

(111011101101110000100011111011110)

经历变异，即至少有一位发生变异。根据前一节的结果，v19在和模式S0。进一步假定串v19第9位变异，其子代为

(111011100101110000100011111011110) v19仍然被模式S0匹配。如果被选择变异的位置是从1到4，或者8到33，那么所生成的子代仍然被模式S0匹配。这里只有3位（第5，6和7位，即模式S0的固定位）是很重要的：变异其中之一将破坏模式S0。很明显，这些重要位的数目等于模式的阶，即固定位的数目。 因为单个位变异的概率为pm，所以单个位存活的概率为1pm。单个变异是和其它变异相互独立的，所以模式S经过单点变异后的存活概率为

ps(S)(1pm)o(S)

由于pm1，所以此概率可以被近似为

ps(S)1o(S)pm

再一次参考例子中的模式S0(pm0.01): ps(S)130.010.97 选择、杂交和变异的组合给出了复制生长公式的新形式：

(S,t1)(S,t)eval(S,t)1pc(3)

(S)o(S)pm/F(t)m1

正如简单公式(1)和(2)，公式(3)告诉我们在下一代中，预测匹配模式S的串数是匹配模

式的实际串数、模式的相对适应值和定义长度以及阶的函数。很明显，在平均值之上的、短

的定义长度和低阶的模式将按照几何增长的速率被复制。

对模式S0：

(S)eval(S,t)1pco(S)pm/F(t)1.3967510.9543751.333024

m1这就意味着短的、低阶、平均之上的模式S0将在下一代中产生几何增长的串数：在时刻t1预计有3*=个串被模式S0匹配（稍小于——只考虑选择的结果，或——值考虑选择和杂交的结果），在时刻t2，有3*=个这样的串（仍小于或）。

注意，公式是基于适应值函数返回f正值的假定：当用遗传算法优化可能返回负值的

优化函数时，需要附加一些适应值函数和优化函数之间的映射。

概括起来，生长公式(1)显示：选择增加了平均之上的模式的复制率，并且这种变化是指数型的。复制本身并不能增加新的模式（初始时刻的复制除外）。这就是为什么要引入杂交算子的原因——能以结构化的方式随机地交换信息。另外，变异算子向群体引入了较大的变化性。如果一个模式是短的且低阶的，这些算子作用在该模式上的组合分裂效果是不大的。生长公式(3)的最终结果可以用下面的定理和假设表示：

这一定理的直接结果是：遗传算法通过短的、低阶模式的杂交信息交换过程探求了搜索空间。

假设1 基因块假设(Building Block Hypothesis)： 遗传算法是通过并列短的、低阶、

高效模式（称之为基因块）来寻求接近最优的执行效果。

虽然已有一些研究来证明此假设，但是多数重要的应用还是依赖于实验结果。遗传算法在众多问题领域中的应用支持基因块假设。毫无疑问，基因块假设说明遗传算法的编码问题对其执行效果来说是至关重要的，并且这种编码应该符合短基因块的思想。

定理1 模式定理(Schema Theorem)： 短的、低阶、平均之上的模式在遗传算子的后

续代中将按几何级数增长。

四、遗传算法实现中的若干问题和讨论：

前面已给出了遗传算法运行步骤的一般描述，通过一个实例具体地考察了它的运行步骤，并给出了遗传算法的理论基础。在具体实现过程中，仍有一些问题值得重视：

1． 选择策略：

选择策略是指复制算子按照什么方式进行操作。总的原则是让适者生存，即适应值大的串生存概率要大。常用的选择方法有以下几种：

(1). 确定性选择方法：

对群体中每个串vi计算生存概率pifi/F（其中F为总适应值），从而得到vi的期望拷贝数e*(piN)。按e*的整数部分值，分配给该串一个拷贝数。显然，总的拷贝数小于N。剩余部分的填充方法是：把每个串对应的e*的小数部分进行排队，按从大到小的顺序选择对应的串，直到填满。 (2). 赌盘选择方法：

即前面采用的方法，此处不在赘述。由于赌盘选择不能保证把最好的个体保留下来，因此又提出最优选择：设*(t)是直到第t代最好的个体，按赌盘产生P(t1)后，若*(t)不在P(t1)中，则把*(t)加入P(t1)中，并随机舍弃一个个体。 (3). 有退还和无退还剩余随机选择：

首先计算期望拷贝数ei*，整数部分决定拷贝数。对余下的小数部分：

a. 有退还剩余随机选择：把ei*的小数部分作为赌盘选择的权，利用赌盘选择决定取舍； b. 无退还剩余随机选择：把ei*的小数部分视为概率，一个一个地进行贝努利试验，其

中小数部分作为成功概率。

2． 控制参数的选择：

在使用遗传算法时，首先要给定一组控制参数，如群体规模，杂交率和变异率等，控制参数的不同选择会对遗传算法的性能产生很大的影响，要想发掘执行的最优性能，必须确定最优的参数设置。事实上，参数设置本身也是个优化问题。这里仅讨论一些原则。

遗传算法的参数空间包括：群体规模、杂交率、变异率、代间隙、选择策略和适应值变换等。

●

群体规模N：它影响到遗传算法的最终性能和效率。规模太小，群体中所含的模式太

少，对基因块采样增长速率小，且代表性差，最终解的质量不高；规模大的群体包含大量有广泛代表性的基因块，可以阻止算法过早地收敛到局部最优解。然而群体规模越大，每一代所需要的计算量就越大，这会导致收敛过程太慢；

●

杂交率pc：杂交率控制杂交算子的应用频率。杂交率越高，群体中的串的更新就越快，

算法对解空间的搜索能力越强。若杂交率过高，高性能的串被破坏的速度也加快了；若杂交率过低，算法搜索解空间的能力下降，有蜕变成局部随机搜索算法的危险。

●

变异率pm：变异是增加群体多样性的搜索算法。一个低水平的变异率足以防止整个群代间隙G：它被引入算法中是允许出现群体重叠的情形，G定义在0到1之间，控制

体中任一给定位保持永远收敛于单一的值；高水平的变异率产生的实际上是随机搜索。

●

每一代群体被替换的百分率。G1时，表示全部替换；0G1时，表示部分替换。P(t)中有N(1G)个个体被随机地保留到下一代P(t1)中。

● ●

选择策略：前面已经讨论过，用的较多的是赌盘选择。

适应值变换：目的时提高算法对适应值变化的敏感度。因为适应值是算法唯一利用的信

息，对适应值变化是否敏感是很重要的。

3． 适应值变换：

注意到赌盘选择要求适应值是正的，而目标函数不一定为正，因此需要对目标函数做变换，即：

Cmaxf(x) 对于 f(x)CmaxF(x)

0 否则其中Cmax选取一个适当大的数。

进行适应值比例变换的目的是调节遗传算法执行过程中串的复制数目，以提高算法的性能。通俗地讲就是希望放大串的适应值的间隔，不因适应值非常接近而无法选择适应值更好的串。另外，还可压制某些适应值非常大的串控制选择过程。 (1) 线性变换

设原适应函数为F，比例适应函数为u，则 u(F)aFb 称为线性比例变换。

系数a和b的选择必须满足以下两个条件：1. 平均比例适应值等于原平均适应值；2. 最大

的比例适应值是平均适应值的指定倍数，即umaxCFavg，一般C取2，这两个条件保证平均群体个体最好的个体的期望复制数分别为1和C。 (2) 幂比例变换

幂比例变换是比例适应值取为原适应值的某个指定幂： U(F)F，值一般是依赖于具体问题的，在算法执行中需要变化以满足要求的伸缩范围，即是代t的函数。 (3) 指数比例变换

指数比例满足关系式：u(F)exp(F)。

指数比例既可让非常好的串保持较多的复制机会，同时又限制了其复制数目，以免很快控制整个群体。同时对于适应值相近的串也提高了竞争性。参数的值决定了选择的侧重，

越小，选择强制越趋向于那些具有最高适应值的串，值随着代的演化而增大。

4． 遗传算法的困难：

(1). “编码困难”：

“表达是遗传算法的主要问题。因为表达方案严重地限制了系统观察世界的窗口。”(Koza, 1990)

“在我看来有时确实如此，我们不能用二进制表达和只由二进制杂交和二进制变异组成的算子集来处理多数真实世界的问题。”(Davis, 1989)

遗传算法传统上使用的二进制编码当用于多维、高精度数值问题时会有一些障碍。例如，对于一个有100个变量、域区间[-500, 500]、精度要求精确到小数点后第6位的问题，二进制解向量的长度是3000。这本身会产生一个大约是101000的搜索空间。对这样的问题，遗传算法执行得很不好。编码应该具有这样的性质：在表达空间里相互靠近的两个点也必须在问题空间里靠近，反之亦然。而二进制方法并不总是这样。一个可能的解决途径是采用浮点编码，目的是使遗传算法更接近问题空间。通过利用真实空间的一些特征，这样的移近强制算子更与问题的特殊性有关。 (2). “有限困难”：

遗传算法理论解释了为什么对一个给定的问题表达，能收敛到欲求的最优点。但不幸的是，实际的应用并不总遵循这一理论。主要的原因除了上面的“编码困难”之外，还有“有限困难”，即：理论假定迭代次数是无限的，而实际上有限制；理论上也假定群体规模是无限的，实际上也有限制。这说明遗传算法在某种条件下不能找到最优解：这种失败是由于过早地收敛到局部最优造成的。过早收敛问题是所有优化算法共同的问题。如果收敛发生的太快，包含在群体中的有价值的信息常常会失去。而遗传算法的执行趋向于在找到最优解之前过早地收敛。有一些避免过早收敛的策略，比如：(1) 配对策略(mating strategy)，又称为近亲预防(incest prevention)； (2) 使用均匀杂交(uniform crossover)；(3). 检测群体中的重复串。

参考文献：

Michalewicz, Z. (2000). 演化程序——遗传算法和数据编码的结合 (中译本). 科学出版社. 杨文采 (1997). 地球物理反演的理论与方法. 地质出版社.