论文部分内容阅读
摘要：本文介绍了遗传算法的流程及几个算子，给出了在matlab 语言环境下实现编码、译码、选择、重组和变异各算子的编程方法，最后用一个实例来说明遗传算法在寻找全局最优解中的应用。
关键词：遗传算法 ；matlab ；程序设计
中图分类号：TP312文献标识码：A 文章编号：1009-3044(2007)04-11049-03
遗传算法（GA）是借鉴生物界自然选择和群体进化机制而形成的一种全局寻优算法，其本质上是一种基于概率的随机搜索算法 。与其它的优化算法相比较，遗传算法具有以下优点：（1）通用性；（2）并行性；（3）简单性和可操作性；（4）稳定性和全局性。
1 遗传算法概述
在遗传算法中，首先将空间问题中的决策变量通过一定的编码表示成遗传空间的一个个体，它是一个基因型串结构数据；然后将目标函数转换成适应度值，用来评价每个个体的优劣，并将其作为遗传操作的依据。遗传操作包括三个算子：选择、重组和变异 。选择是从当前群体中选择适应值高的个体以生成交配池的过程，交配池是当前代与下一代之间的中间群体。选择算子的作用是用来提高群体的平均适应度值。重组算子的作用是将原有的优良基因遗传给下一代个体，并生成包含更复杂基因的新个体，它先从交配池中的个体随机配对，然后将两两配对的个体按一定方式相互交换部分基因。变异算子是对个体的某一个或几位按某一较小的概率进行反转其二进制字符，模拟自然界的基因突变现象。
遗传算法的基本程序实现流程如下：
（1）先确定待优化的参数大致范围，然后对搜索空间进行编码；
（2）随机产生包含各个个体的初始种群；
（3）将种群中各个个体解码成对应的参数值，用解码后的参数求代价函数和适应度函数，运用适应度函数评估检测各个个体适应度；
（4）对收敛条件进行判断，如果已经找到最佳个体，则停止，否则继续进行遗传操作；
（5）进行选择操作，让适应度大的个体在种群中占有较大的比例，一些适应度较小的个体将会被淘汰；
（6）随机交叉，两个个体按一定的交叉概率进行交叉操作，并产生两个新的子个体；
（7）按照一定的变异概率变异，使个体的某个或某些位的性质发生改变；
（8）重复步骤（3）至（7），直至参数收敛达到预定的指标。
使用遗传算法需要确定的运行参数有：编码串长度、交叉和变异概率、种群规模。编码串长度由问题的所要求的精度来决定。交叉概率控制着交叉操作的频率，交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率通常应取较大值，但如果交叉概率太大的话又可能反过来会破坏群体的优良模式，一般取0.4－0.99 。变异概率也是影响新个体产生的一个因素，如果变异概率太小，则产生新个体较少；如果变异概率太大，则又会使遗传算法变成随机搜索，为保证个体变异后与其父体不会产生太大的差异，通常取变异概率为0.0001－0.1以保证种群发展的稳定性。种群规模太大时，计算量会很大，使遗传算法的运行效率降低，种群规模太小时，可以提高遗传算法的运行速度，但却种群的多样性却降低了，有可能找不出最优解，通常取种群数目20－100。从理论上讲，不存在一组适用于所有问题的最佳参数值，随着问题参数的变化，有效问参数的差异往往是十分显著的。
2 用Matlab 语言来实现遗传算法
Matlab是一个高性能的计算软件，配备有功能强大的数学函数支持库，适用范围大，编程效率高，语句简单，功能齐备，是世界上顶级的计算与仿真程序软件 。利用Matlab来编写遗传算法程序简单而且易于操作。
2.1 编码
编码就是把一个问题的可行解从其解空间转换到遗传算法能够处理的搜索空间的转化方法，编码形式决定了重组算子的操作。遗传算法是对编码后的个体作选择与交叉运算，然后通过这些反复运算达到优化目标。遗传算法首要的问题是通过编码将决策变量表示成串结构数据。我们常用的是二进制编码，即用二进制数构成的符号串来表示每个个体。通常根据搜索精度(sca_var)、决策变量上界(range(2)) 的和下界(range(1))来确定各个二进制字符串的长度(bit_n)，搜索精度为sca_var=(range(2)－range(1))./(2^bit_n—1),然后再随机产生一个的初始种群(be_gen),其规模为popusize。下面用encoding 函数来实现编码和产生初始的种群：
function [be_gen , bit_n]=encoding(sca_var,range(1) , range(2), popusize)
bit_n=ceil(log2 (( range(2)－range(1))./sca_var));
be_gen= randint( popusize, sum(bit_n));
2.2 译码
决策变量经过编码之后，各个个体构成的种群be_gen要通过解码才能转换成原问题空间的决策变量构成的种群vgen，这样才能计算其相应的各个适应度值。另外，译码首先要求出二进制数对应的十进制数decimal,然后根据下面的公式求出实际决策变量X: X=range(1)+decimal*sca_dec .通常可以用decoding函数来实现译码的过程：
function[vgen,fitness]=decoding(fcn , be_gen,bit_n,range(1),range(2))
popusize=size(be_gen,1);
n_var=length(bit_n);
sca_dec=(range(2)－range(1))./(2^bit_n－1);
bit_n=cumsun(bit_n);
bit_n=[0 bit_n];
for i=1:n_var
be_var(i)=be_gen(:,bits(i)+1:bit_n(i +1));
var(i)= range( 1)( i )+sum(ones(popusize,1)*2.^(size(be_var(i),2)
－1:－1:0).*be_var(i),2).*sca_dec(i);
end
vgen=[var(1,:)];
for i=1:popusize
fitness(i )=eval([fcn,’(var_gene(i,:))’] );
end
2.3 选择
选择就是利用码后求得的各个个体的适应度的大小，从中选出一些适应度高的个体，并淘汰一些适应度较小的个体以生成交配池的过程。然后再对优良的个体进行交叉和变异操作。在选择算子中，先找出当前群体中适应度最高和最低的个体，将最佳个体bes_ind保留并替换最差个体，直接进入下一代，将剩余个体evol_gen按适应值比例选择法进行操作，即采用轮盘赌（roulette wheel）方式来实现。这种方式首先计算每个个体的适应值，然后计算出该适应值在群体适应值总和中所占的比例，来表示该个体被选中的概率 ，这样既能保证最佳个体的适应度值不会减小，最佳个体不会被交叉变异操作所破坏，也能不断提高该群体的平均适应度值。比例选择法体现了生物进化过程中“优胜劣汰，适者生存”的思想，并且保证将优良的基因遗传给下一代。
我们可以用下面的函数来实现选择算子：
function [evol_gen, bes_ind,max_fitness]=selection(old_gen, fitness)
[min_fitn,expo(b)]=min(fitn); [max_fitn,expo(a)]=max_(fitn);
popusize=length(fitness);
bes_ind=old_gen(expo(a),:);
expo=[1:popusize];expo(expo(a))=0;expo(expo(b))=0;
expo=nonzeros(expo);
evol_gen=old_gen(expo,:);
evol_fitness=fitness(expo,:);
evol_popusize=popusize－2;
posel=evol_fitness/sum(evol_fitness);
poselcum=cusum(posel);
r=rand(1,evol_popusize);
selected=1+sum(poselcum*ones(1,evol_popusize) evol_gen=evol_gen(selection,:);
2.4 重组
重组算子是产生新个体的主要方法，它决定了遗传算法的全局搜索能力。重组操作的作用是将原有的优良基因遗传给下一代个体，并生成包含更优良基因的新个体。通常使用的遗传算子是一点交叉法，就是按交叉概率pc(0 function [new_gen]=recombination(old_gen,pc)
[nouse,match]=sort(rand(size(old_gen,1),1));
match_gen=old_gen(match,:);
pairs=size(match-gen,1)/2;
bit_n=size(match_gene,2);
string=rand(pairs,1) crossp=randint(string,1,[1,bit_n]);
crossp=string.*crossp;
for i=1:pairs
new_gen([2* i－12* i],: )=[match_gen([2* i－12* i] ,
1:crossp(i) ) match_gen([2* i 2* i －1],crossp(i)+1:bin_n)];
end
另外，一点交叉法操作的信息比较小，交叉点的位置的选择可能会带来较大的偏差，一点交叉算子不利于长距离的保留和重组。
2.5 变异
变异算子是模拟自然界生物进化的中染色体的基因突变现象，从而改变染色体的结构和物理性状。变异算子是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力。变异操作通过按照变异概率(mp)随机反转某位等位基因的二进制字符的值来实现。程序如下：
function [new_gen]=mutation(old_gen, pm )
mpoints=find(rand(size(old_gen)) new_gen=old_gen;
new_gen(mpoints)=1－old_gen(mpoints);
end
当重组操作发生早熟收敛时，这时引入变异算子会有很好的效果。一方面，变异算子可以使群体进化中丢失的等位基因信息得以恢复，保持群体基因中的差异性，防止发生早熟收敛；另一方面，当种群规模较大时，在重组操作基础上引入适度的变异，也能够提高遗传算法的局部搜索效率。
3 实际应用例子
在这里我们以一个函数为例来验证遗传算法程序的全局搜索能力，设函数为z =3*(1－x)^2*exp(－(x^2)－(y+1)^2)－10*(x/5－x^3 －y^5)*exp(－x^2-y^2) － 1/3*exp(-(x+1)^2 - y^2), x∈[－3，3]，y∈[－3，3]。
图1 函数图形示意图 图2 最佳适应度值示意图
如果取种群的规模popusize=20，搜索精度sca_var=0.000001,交叉率pc=0.98,变异概率mp＝0.01。图1是函数图形示意图，图2 中给出了遗传generation=30代之后的适应度值。另外，由于采用了每一代的最优个体直接进入下一代的方法，所以不会出现最佳适应度值减小的情况，可以发现在第12代以后，最佳适应度值变换就很小了，到26代之后，最佳适应度值已经不再发生变化，这时可以认为已经找到了全局最优解：x=0.011765,y=1.588235,z=8.101909。
4 结束语
用matlab 语言编写了遗传算法程序，并通过了调试，用一个实际例子来对问题进行了验证，这对在matlab环境下用遗传算法来解决优化问题有一定的意义。
参考文献：
[1].李敏强,寇纪松,林丹，李书全.遗传算法的基本理论与应用[M].北京：科学出版社，2004.
[2].张志涌,徐彦琴,matlab教程[M]，北京航空航天大学出版社.北京，2003.
[3].Coello Carlos A Coello Cortes Nareli Cruz Hybirdizing A Genetic Algorithm with Artificial Inmune SystemforGlobalOptimization.[J].EngineeringOptimization.2004,36(5):607-634.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。
关键词：遗传算法 ；matlab ；程序设计
中图分类号：TP312文献标识码：A 文章编号：1009-3044(2007)04-11049-03
遗传算法（GA）是借鉴生物界自然选择和群体进化机制而形成的一种全局寻优算法，其本质上是一种基于概率的随机搜索算法 。与其它的优化算法相比较，遗传算法具有以下优点：（1）通用性；（2）并行性；（3）简单性和可操作性；（4）稳定性和全局性。
1 遗传算法概述
在遗传算法中，首先将空间问题中的决策变量通过一定的编码表示成遗传空间的一个个体，它是一个基因型串结构数据；然后将目标函数转换成适应度值，用来评价每个个体的优劣，并将其作为遗传操作的依据。遗传操作包括三个算子：选择、重组和变异 。选择是从当前群体中选择适应值高的个体以生成交配池的过程，交配池是当前代与下一代之间的中间群体。选择算子的作用是用来提高群体的平均适应度值。重组算子的作用是将原有的优良基因遗传给下一代个体，并生成包含更复杂基因的新个体，它先从交配池中的个体随机配对，然后将两两配对的个体按一定方式相互交换部分基因。变异算子是对个体的某一个或几位按某一较小的概率进行反转其二进制字符，模拟自然界的基因突变现象。
遗传算法的基本程序实现流程如下：
（1）先确定待优化的参数大致范围，然后对搜索空间进行编码；
（2）随机产生包含各个个体的初始种群；
（3）将种群中各个个体解码成对应的参数值，用解码后的参数求代价函数和适应度函数，运用适应度函数评估检测各个个体适应度；
（4）对收敛条件进行判断，如果已经找到最佳个体，则停止，否则继续进行遗传操作；
（5）进行选择操作，让适应度大的个体在种群中占有较大的比例，一些适应度较小的个体将会被淘汰；
（6）随机交叉，两个个体按一定的交叉概率进行交叉操作，并产生两个新的子个体；
（7）按照一定的变异概率变异，使个体的某个或某些位的性质发生改变；
（8）重复步骤（3）至（7），直至参数收敛达到预定的指标。
使用遗传算法需要确定的运行参数有：编码串长度、交叉和变异概率、种群规模。编码串长度由问题的所要求的精度来决定。交叉概率控制着交叉操作的频率，交叉操作是遗传算法中产生新个体的主要方法，所以交叉概率通常应取较大值，但如果交叉概率太大的话又可能反过来会破坏群体的优良模式，一般取0.4－0.99 。变异概率也是影响新个体产生的一个因素，如果变异概率太小，则产生新个体较少；如果变异概率太大，则又会使遗传算法变成随机搜索，为保证个体变异后与其父体不会产生太大的差异，通常取变异概率为0.0001－0.1以保证种群发展的稳定性。种群规模太大时，计算量会很大，使遗传算法的运行效率降低，种群规模太小时，可以提高遗传算法的运行速度，但却种群的多样性却降低了，有可能找不出最优解，通常取种群数目20－100。从理论上讲，不存在一组适用于所有问题的最佳参数值，随着问题参数的变化，有效问参数的差异往往是十分显著的。
2 用Matlab 语言来实现遗传算法
Matlab是一个高性能的计算软件，配备有功能强大的数学函数支持库，适用范围大，编程效率高，语句简单，功能齐备，是世界上顶级的计算与仿真程序软件 。利用Matlab来编写遗传算法程序简单而且易于操作。
2.1 编码
编码就是把一个问题的可行解从其解空间转换到遗传算法能够处理的搜索空间的转化方法，编码形式决定了重组算子的操作。遗传算法是对编码后的个体作选择与交叉运算，然后通过这些反复运算达到优化目标。遗传算法首要的问题是通过编码将决策变量表示成串结构数据。我们常用的是二进制编码，即用二进制数构成的符号串来表示每个个体。通常根据搜索精度(sca_var)、决策变量上界(range(2)) 的和下界(range(1))来确定各个二进制字符串的长度(bit_n)，搜索精度为sca_var=(range(2)－range(1))./(2^bit_n—1),然后再随机产生一个的初始种群(be_gen),其规模为popusize。下面用encoding 函数来实现编码和产生初始的种群：
function [be_gen , bit_n]=encoding(sca_var,range(1) , range(2), popusize)
bit_n=ceil(log2 (( range(2)－range(1))./sca_var));
be_gen= randint( popusize, sum(bit_n));
2.2 译码
决策变量经过编码之后，各个个体构成的种群be_gen要通过解码才能转换成原问题空间的决策变量构成的种群vgen，这样才能计算其相应的各个适应度值。另外，译码首先要求出二进制数对应的十进制数decimal,然后根据下面的公式求出实际决策变量X: X=range(1)+decimal*sca_dec .通常可以用decoding函数来实现译码的过程：
function[vgen,fitness]=decoding(fcn , be_gen,bit_n,range(1),range(2))
popusize=size(be_gen,1);
n_var=length(bit_n);
sca_dec=(range(2)－range(1))./(2^bit_n－1);
bit_n=cumsun(bit_n);
bit_n=[0 bit_n];
for i=1:n_var
be_var(i)=be_gen(:,bits(i)+1:bit_n(i +1));
var(i)= range( 1)( i )+sum(ones(popusize,1)*2.^(size(be_var(i),2)
－1:－1:0).*be_var(i),2).*sca_dec(i);
end
vgen=[var(1,:)];
for i=1:popusize
fitness(i )=eval([fcn,’(var_gene(i,:))’] );
end
2.3 选择
选择就是利用码后求得的各个个体的适应度的大小，从中选出一些适应度高的个体，并淘汰一些适应度较小的个体以生成交配池的过程。然后再对优良的个体进行交叉和变异操作。在选择算子中，先找出当前群体中适应度最高和最低的个体，将最佳个体bes_ind保留并替换最差个体，直接进入下一代，将剩余个体evol_gen按适应值比例选择法进行操作，即采用轮盘赌（roulette wheel）方式来实现。这种方式首先计算每个个体的适应值，然后计算出该适应值在群体适应值总和中所占的比例，来表示该个体被选中的概率 ，这样既能保证最佳个体的适应度值不会减小，最佳个体不会被交叉变异操作所破坏，也能不断提高该群体的平均适应度值。比例选择法体现了生物进化过程中“优胜劣汰，适者生存”的思想，并且保证将优良的基因遗传给下一代。
我们可以用下面的函数来实现选择算子：
function [evol_gen, bes_ind,max_fitness]=selection(old_gen, fitness)
[min_fitn,expo(b)]=min(fitn); [max_fitn,expo(a)]=max_(fitn);
popusize=length(fitness);
bes_ind=old_gen(expo(a),:);
expo=[1:popusize];expo(expo(a))=0;expo(expo(b))=0;
expo=nonzeros(expo);
evol_gen=old_gen(expo,:);
evol_fitness=fitness(expo,:);
evol_popusize=popusize－2;
posel=evol_fitness/sum(evol_fitness);
poselcum=cusum(posel);
r=rand(1,evol_popusize);
selected=1+sum(poselcum*ones(1,evol_popusize)
2.4 重组
重组算子是产生新个体的主要方法，它决定了遗传算法的全局搜索能力。重组操作的作用是将原有的优良基因遗传给下一代个体，并生成包含更优良基因的新个体。通常使用的遗传算子是一点交叉法，就是按交叉概率pc(0
[nouse,match]=sort(rand(size(old_gen,1),1));
match_gen=old_gen(match,:);
pairs=size(match-gen,1)/2;
bit_n=size(match_gene,2);
string=rand(pairs,1)
crossp=string.*crossp;
for i=1:pairs
new_gen([2* i－12* i],: )=[match_gen([2* i－12* i] ,
1:crossp(i) ) match_gen([2* i 2* i －1],crossp(i)+1:bin_n)];
end
另外，一点交叉法操作的信息比较小，交叉点的位置的选择可能会带来较大的偏差，一点交叉算子不利于长距离的保留和重组。
2.5 变异
变异算子是模拟自然界生物进化的中染色体的基因突变现象，从而改变染色体的结构和物理性状。变异算子是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力。变异操作通过按照变异概率(mp)随机反转某位等位基因的二进制字符的值来实现。程序如下：
function [new_gen]=mutation(old_gen, pm )
mpoints=find(rand(size(old_gen))
new_gen(mpoints)=1－old_gen(mpoints);
end
当重组操作发生早熟收敛时，这时引入变异算子会有很好的效果。一方面，变异算子可以使群体进化中丢失的等位基因信息得以恢复，保持群体基因中的差异性，防止发生早熟收敛；另一方面，当种群规模较大时，在重组操作基础上引入适度的变异，也能够提高遗传算法的局部搜索效率。
3 实际应用例子
在这里我们以一个函数为例来验证遗传算法程序的全局搜索能力，设函数为z =3*(1－x)^2*exp(－(x^2)－(y+1)^2)－10*(x/5－x^3 －y^5)*exp(－x^2-y^2) － 1/3*exp(-(x+1)^2 - y^2), x∈[－3，3]，y∈[－3，3]。
图1 函数图形示意图 图2 最佳适应度值示意图
如果取种群的规模popusize=20，搜索精度sca_var=0.000001,交叉率pc=0.98,变异概率mp＝0.01。图1是函数图形示意图，图2 中给出了遗传generation=30代之后的适应度值。另外，由于采用了每一代的最优个体直接进入下一代的方法，所以不会出现最佳适应度值减小的情况，可以发现在第12代以后，最佳适应度值变换就很小了，到26代之后，最佳适应度值已经不再发生变化，这时可以认为已经找到了全局最优解：x=0.011765,y=1.588235,z=8.101909。
4 结束语
用matlab 语言编写了遗传算法程序，并通过了调试，用一个实际例子来对问题进行了验证，这对在matlab环境下用遗传算法来解决优化问题有一定的意义。
参考文献：
[1].李敏强,寇纪松,林丹，李书全.遗传算法的基本理论与应用[M].北京：科学出版社，2004.
[2].张志涌,徐彦琴,matlab教程[M]，北京航空航天大学出版社.北京，2003.
[3].Coello Carlos A Coello Cortes Nareli Cruz Hybirdizing A Genetic Algorithm with Artificial Inmune SystemforGlobalOptimization.[J].EngineeringOptimization.2004,36(5):607-634.
本文中所涉及到的图表、注解、公式等内容请以PDF格式阅读原文。