遗传算法(C++)

1、   遗传算法（Genetic Algorithm，缩写为GA）是一种有效的解决最优化问题的方法。它最先是由John Holland于1975年提出的。从那以后，它逐渐发展成为一种通过模拟自然进化过程解决最优化问题的计算模型。     利用遗传算法解最优化问题，首先应对可行域中的点进行编码（一般采用二进制编码），然后在可行域中随机挑选一些编码组成作为进化起点的第一代编码组，并计算每个解的目标函数值，也就是编码的适应度。接着就像自然界中一样，利用选择机制从编码组中随机挑选编码作为繁殖过程前的编码样本。选择机制应保证适应度较高的

2、解能够保留较多的样本；而适应度较低的解则保留较少的样本，甚至被淘汰。在接下去的繁殖过程中，遗传算法提供了交叉和变异两种算子对挑选后的样本进行交换。交叉算子交换随机挑选的两个编码的某些位，变异算子则直接对一个编码中的随机挑选的某一位进行反转。这样通过选择和繁殖就产生了下一代编码组。重复上述选择和繁殖过程，直到结束条件得到满足为止。进化过程最后一代中的最优解就是用遗传算法解最优化问题所得到的最终结果。从以上介绍可以看出，GA算法具有下述特点： 1)GA是对问题参数的编码组进行进货，而不是直接对参数本身。 21)GA的搜索是从问题解的编码组开始搜索，而不是从单个解开始。 31)GA使用目标函数值（适

3、应度）这一信息进行搜索，而不需导数等其他信息。 4)GA算法使用的选择、交叉、变异这三个算子都是随机操作，而不是确定规则。 实践表明，遗传算法解最优化问题的计算效率比较高、适用范围相当广。为了解释这一现象，Holland给出了图式定理。所谓图式，就是某些码位取相同值的编码的集合。图式定理说明在进化过程的各代中，属于适应度高、阶数低且长度短的图式的编码数量将随代数以指数形式增长。另外，Holland还发现遗传算法具有隐含的并行计算特性。最近的研究则表明，上述遗传算法经适当改进后对任意优化问题以概率1收敛于全局最优解。 将遗传算法用于解决各种实际问题后，人们发现遣传算法也会由于各种原因过早向目标函

4、数的局部最优解收敛，从而很难找到全局最优解。其中有些是由于目标函数的特性造成的，例如函数具有欺骗性，不满足构造模块假说等等；另外一些则是由于算法设计不当。为此，不断有人对遗传算法提出各种各样的改进方案。例如：针对原先的定长二进制编码方案；提出了动态编码、实数编码等改进方案；针对按比例的选择机制，提出了竞争选择、按续挑选等改进方案；针对原先的一点交叉算子，提出了两点交叉、多点交叉、均匀交叉等算子；针对原先遗传算法各控制参数在进化过程中不变的情况，提出了退化遗传算法、自适应遗传算法等。另外，针对不同问题还出现了分布式遗传算法、并行遗传算法等等。 近年来，随着对于遗传算法研究的不断深入完善，有越来越

5、多的人认识了解了遗传算法，并把它应用到越来越广泛的领域，例如机器学习、模式识别、图像处理、神经网络、工业优化控制和社会科学等方面。特别是在解决旅行商问题、煤气管道的最优控制、通信网络链接长度的优化问题、铁路运输计划优化、喷气式收音机涡轮机的设计、VLSI版面设计、键盘排列优化等问题上遗传算法都取得了很大的成功。 目前国际国内有关GA的研究热潮方兴未艾。除从1985年起每两年举办一届GA国际会议外，还有MIT从1993年开始出版的Evolutionary Computatio和Adaptive Behavior两种杂志、IEEE从今年起出版的专门关于进化计算的汇刊。另外，各种AI类的杂志不断出版

6、有关进化计算的专辑。其它有关GA理论和工程应用的文章也在各种不同类型杂志上不断涌现。国内有关GA的研究也正在不断深入地展开。· 遗传算法(Genetic Algorithm, GA)是近几年发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。这一点体现了自然界中"物竞天择、适者生存"进化过程。1962年Holland教授首次提出了GA算法的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面，并奠定了坚实的理论基础。用遗传算法解决问题时，首先要对待解决问题的模型结构和参数进行编码

7、，一般用字符串表示，这个过程就将问题符号化、离散化了。也有在连续空间定义的GA(Genetic Algorithm in Continuous Space, GACS)，暂不讨论。一个串行运算的遗传算法(Seguential Genetic Algoritm, SGA)按如下过程进行：(1) 对待解决问题进行编码；(2) 随机初始化群体X(0):=(x1, x2, xn)；(3) 对当前群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该个体的性能好坏；(4) 应用选择算子产生中间代Xr(t)；(5) 对Xr(t)应用其它的算子，产生新一代群体X(t+1)，这些算子的目的在于扩展有

8、限个体的覆盖面，体现全局搜索的思想；(6) t:=t+1；如果不满足终止条件继续(3)。GA中最常用的算子有如下几种：(1) 选择算子(selection/reproduction): 选择算子从群体中按某一概率成对选择个体，某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现方法是轮盘赌(roulette wheel)模型。(2) 交叉算子(Crossover): 交叉算子将被选中的两个个体的基因链按概率pc进行交叉，生成两个新的个体，交叉位置是随机的。其中Pc是一个系统参数。(3) 变异算子(Mutation): 变异算子将新个体的基因链的各位按概率pm进行变异，对二值基因链(0,1

9、编码)来说即是取反。上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进GA的某些性能。系统参数(个体数n,基因链长度l,交叉概率Pc,变异概率Pm等)对算法的收敛速度及结果有很大的影响，应视具体问题选取不同的值。GA的程序设计应考虑到通用性，而且要有较强的适应新的算子的能力。OOP中的类的继承为我们提供了这一可能。定义两个基本结构：基因(ALLELE)和个体(INDIVIDUAL)，以个体的集合作为群体类TPopulation的数据成员，而TSGA类则由群体派生出来，定义GA的基本操作。对任一个应用实例，可以在TSGA类上派生，并定义新的操作。TPopulation类包含两

10、个重要过程：FillFitness: 评价函数，对每个个体进行解码(decode)并计算出其适应度值，具体操作在用户类中实现。Statistic: 对当前群体进行统计，如求总适应度sumfitness、平均适应度average、最好个体fmax、最坏个体fmin等。TSGA类在TPopulation类的基础上派生，以GA的系统参数为构造函数的参数，它有4个重要的成员函数：Select: 选择算子，基本的选择策略采用轮盘赌模型（如图2）。轮盘经任意旋转停止后指针所指向区域被选中，所以fi值大的被选中的概率就大。Crossover: 交叉算子，以概率Pc在两基因链上的随机位置交换子串。Mutati

11、on: 变异算子，以概率Pm对基因链上每一个基因进行随机干扰(取反)。Generate: 产生下代，包括了评价、统计、选择、交叉、变异等全部过程，每运行一次，产生新的一代。SGA的结构及类定义如下(用C+编写)：code typedef char ALLELE; / 基因类型typedef structALLELE *chrom;float fitness; / fitness of ChromosomeINDIVIDUAL; / 个体定义class TPopulation / 群体类定义public:int size; / Size of population: nint lchrom; /

12、 Length of chromosome: lfloat sumfitness, average;INDIVIDUAL *fmin, *fmax;INDIVIDUAL *pop;TPopulation(int popsize, int strlength);TPopulation();inline INDIVIDUAL &Individual(int i) return popi;void FillFitness(); / 评价函数virtual void Statistics(); / 统计函数;class TSGA : public TPopulation / TSGA类派生于群

13、体类public:float pcross; / Probability of Crossoverfloat pmutation; / Probability of Mutationint gen; / Counter of generationTSGA(int size, int strlength, float pm=0.03, float pc=0.6):TPopulation(size, strlength)gen=0; pcross=pc; pmutation=pm; ;virtual INDIVIDUAL& Select();virtual void Crossover(I

14、NDIVIDUAL &parent1, INDIVIDUAL &parent2,INDIVIDUAL &child1, INDIVIDUAL &child2);&child1, INDIVIDUAL &child2);virtual ALLELE Mutation(ALLELE alleleval);virtual void Generate(); / 产生新的一代;用户GA类定义如下：class TSGAfit : public TSGApublic:TSGAfit(int size,float pm=0.0333,float pc=0.6):

15、TSGA(size,24,pm,pc);void print(); /code由于GA是一个概率过程，所以每次迭代的情况是不一样的；系统参数不同，迭代情况也不同。在实验中参数一般选取如下：个体数n=50-200，变异概率Pm=0.03, 交叉概率Pc=0.6。变异概率太大，会导致不稳定。核心函数： (1)function pop=initializega(num,bounds,eevalFN,eevalOps,options)-初始种群的生成函数 【输出参数】  pop-生成的初始种群 【输入参数】  num-种群中的个体数目  bounds-代表变量的上下界的矩

16、阵  eevalFN-适应度函数  eevalOps-传递给适应度函数的参数  options-选择编码形式(浮点编码或是二进制编码)precision F_or_B,如     precision-变量进行二进制编码时指定的精度     F_or_B-为1时选择浮点编码，否则为二进制编码,由precision指定精度) (2)function x,endPop,bPop,traceInfo = ga(bounds,evalFN,evalOps,startPop,opts,.      

17、60;  termFN,termOps,selectFN,selectOps,xOverFNs,xOverOps,mutFNs,mutOps)-遗传算法函数 【输出参数】     x-求得的最优解     endPop-最终得到的种群     bPop-最优种群的一个搜索轨迹 【输入参数】     bounds-代表变量上下界的矩阵     evalFN-适应度函数     evalOps-传递给适应度函数的参数     startPop-初始种

18、群     optsepsilon prob_ops display-opts(1:2)等同于initializega的options参数，第三个参数控制是否输出，一般为0。如1e-6 1 0     termFN-终止函数的名称,如'maxGenTerm'     termOps-传递个终止函数的参数,如100     selectFN-选择函数的名称,如'normGeomSelect'     selectOps-传递个选择函数的参数,如0.08  

19、   xOverFNs-交叉函数名称表，以空格分开，如'arithXover heuristicXover simpleXover'     xOverOps-传递给交叉函数的参数表，如2 0;2 3;2 0     mutFNs-变异函数表，如'boundaryMutation multiNonUnifMutation nonUnifMutation unifMutation'     mutOps-传递给交叉函数的参数表,如4 0 0;6 100 3;4 100 3;4 0 0 注意】ma

20、tlab工具箱函数必须放在工作目录下 【问题】求f(x)=x+10*sin(5x)+7*cos(4x)的最大值，其中0<=x<=9 【分析】选择二进制编码，种群中的个体数目为10，二进制编码长度为20，交叉概率为0.95,变异概率为0.08 【程序清单】    %编写目标函数      functionsol,eval=fitness(sol,options)        x=sol(1);        eval=x+10*sin(5*x)+7*co

21、s(4*x);    %把上述函数存储为fitness.m文件并放在工作目录下        initPop=initializega(10,0 9,'fitness');%生成初始种群，大小为10    x endPop,bPop,trace=ga(0 9,'fitness',initPop,1e-6 1 1,'maxGenTerm',25,'normGeomSelect',.      0.08,'arithX

22、over',2,'nonUnifMutation',2 25 3) %25次遗传迭代 运算借过为：x =    7.8562 24.8553(当x为7.8562时，f（x）取最大值24.8553) 注：遗传算法一般用来取得近似最优解，而不是最优解。 遗传算法实例2 【问题】在5<=Xi<=5,i=1,2区间内，求解        f(x1,x2)=-20*exp(-0.2*sqrt(0.5*(x1.2+x2.2)-exp(0.5*(cos(2*pi*x1)+cos(2*pi*x2)+22.71282

23、的最小值。 【分析】种群大小10，最大代数1000，变异率0.1,交叉率0.3 【程序清单】    源函数的matlab代码       function eval=f(sol)         numv=size(sol,2);         x=sol(1:numv);         eval=-20*exp(-0.2*sqrt(sum(x.2)/numv)-exp(sum(cos(2*pi*x)/numv)+22.7

24、1282;   %适应度函数的matlab代码       function sol,eval=fitness(sol,options)         numv=size(sol,2)-1;         x=sol(1:numv);         eval=f(x);         eval=-eval;   %遗传算法的matlab代码      

25、; bounds=ones(2,1)*-5 5;       p,endPop,bestSols,trace=ga(bounds,'fitness') 注：前两个文件存储为m文件并放在工作目录下，运行结果为    p =    0.0000 -0.0000 0.0055 大家可以直接绘出f(x)的图形来大概看看f（x）的最值是多少，也可是使用优化函数来验证。matlab命令行执行命令：  fplot('x+10*sin(5*x)+7*cos(4*x)',0,9) evalops是传递

26、给适应度函数的参数，opts是二进制编码的精度，termops是选择maxGenTerm结束函数时传递个maxGenTerm的参数，即遗传代数。xoverops是传递给交叉函数的参数。mutops是传递给变异函数的参数。 遗传算法(Genetic Algorithm, GA)是近几年发展起来的一种崭新的全局优化算法，它借用了生物遗传学的观点，通过自然选择、遗传、变异等作用机制，实现各个个体的适应性的提高。这一点体现了自然界中"物竞天择、适者生存"进化过程。1962年Holland教授首次提出了GA算法的思想，从而吸引了大批的研究者，迅速推广到优化、搜索、机器学习等方面，并奠

27、定了坚实的理论基础。 用遗传算法解决问题时，首先要对待解决问题的模型结构和参数进行编码，一般用字符串表示，这个过程就将问题符号化、离散化了。也有在连续空间定义的GA(Genetic Algorithm in Continuous Space, GACS)，暂不讨论。 一个串行运算的遗传算法(Seguential Genetic Algoritm, SGA)按如下过程进行： (1) 对待解决问题进行编码； (2) 随机初始化群体X(0):=(x1, x2, xn)； (3) 对当前群体X(t)中每个个体xi计算其适应度F(xi)，适应度表示了该个体的性能好坏； (4) 应用选择算子产生中间代Xr

28、(t)； (5) 对Xr(t)应用其它的算子，产生新一代群体X(t+1)，这些算子的目的在于扩展有限个体的覆盖面，体现全局搜索的思想； (6) t:=t+1；如果不满足终止条件继续(3)。GA中最常用的算子有如下几种： (1) 选择算子(selection/reproduction): 选择算子从群体中按某一概率成对选择个体，某个体xi被选择的概率Pi与其适应度值成正比。最通常的实现方法是轮盘赌(roulette wheel)模型。 (2) 交叉算子(Crossover): 交叉算子将被选中的两个个体的基因链按概率pc进行交叉，生成两个新的个体，交叉位置是随机的。其中Pc是一个系统参数。 (3

29、) 变异算子(Mutation): 变异算子将新个体的基因链的各位按概率pm进行变异，对二值基因链(0,1编码)来说即是取反。 上述各种算子的实现是多种多样的，而且许多新的算子正在不断地提出，以改进GA的某些性能。系统参数(个体数n,基因链长度l,交叉概率Pc,变异概率Pm等)对算法的收敛速度及结果有很大的影响，应视具体问题选取不同的值。GA的程序设计应考虑到通用性，而且要有较强的适应新的算子的能力。OOP中的类的继承为我们提供了这一可能。 定义两个基本结构：基因(ALLELE)和个体(INDIVIDUAL)，以个体的集合作为群体类TPopulation的数据成员，而TSGA类则由群体派生出来

30、，定义GA的基本操作。对任一个应用实例，可以在TSGA类上派生，并定义新的操作。 TPopulation类包含两个重要过程： FillFitness: 评价函数，对每个个体进行解码(decode)并计算出其适应度值，具体操作在用户类中实现。 Statistic: 对当前群体进行统计，如求总适应度sumfitness、平均适应度average、最好个体fmax、最坏个体fmin等。 TSGA类在TPopulation类的基础上派生，以GA的系统参数为构造函数的参数，它有4个重要的成员函数： Select: 选择算子，基本的选择策略采用轮盘赌模型（如图2）。轮盘经任意旋转停止后指针所指向区域被选中

31、，所以fi值大的被选中的概率就大。 Crossover: 交叉算子，以概率Pc在两基因链上的随机位置交换子串。 Mutation: 变异算子，以概率Pm对基因链上每一个基因进行随机干扰(取反)。 Generate: 产生下代，包括了评价、统计、选择、交叉、变异等全部过程，每运行一次，产生新的一代。 SGA的结构及类定义如下(用C+编写)： codetypedef char ALLELE; / 基因类型 typedef struct ALLELE *chrom; float fitness; / fitness of Chromosome INDIVIDUAL; / 个体定义 class TPopulation / 群体类定义 public: int size; / Size of population: n int lchrom; / Length of chromosome: l float s