《遗传算法及优化问题(重要_有代码)(仅供参照)》由会员分享，可在线阅读，更多相关《遗传算法及优化问题(重要_有代码)(仅供参照)（17页珍藏版）》请在金锄头文库上搜索。
1、实验十遗传算法与优化问题一、问题背景与实验目的遗传算法（Genetic Algorithm一GA）,是模拟达尔文的遗传选择和自然淘汰 的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975 年首先提出的.遗传算法作为一种新的全局优化搜索算法，以其简单通用、鲁棒 性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能 计算之一的地位.本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数 最值问题，使读者能够学会利用遗传算法进行初步的优化计算.1. 遗传算法的基本原理遗传算法的基本思想正是基于模仿生物界遗传学的遗传过程.它把问题的参
2、 数用基因代表，把问题的解用染色体代表（在计算机里用二进制码表示），从而 得到一个由具有不同染色体的个体组成的群体.这个群体在问题特定的环境里生 存竞争，适者有最好的机会生存和产生后代.后代随机化地继承了父代的最好特 征，并也在生存环境的控制支配下继续这一过程.群体的染色体都将逐渐适应环 境,不断进化，最后收敛到一族最适应环境的类似个体，即得到问题最优的解.值 得注意的一点是，现在的遗传算法是受生物进化论学说的启发提出的，这种学说 对我们用计算机解决复杂问题很有用，而它本身是否完全正确并不重要（目前生 物界对此学说尚有争议）.（1）遗传算法中的生物遗传学概念由于遗传算法是由进化论和遗传学机理而
3、产生的直接搜索优化方法；故而在 这个算法中要用到各种进化和遗传学的概念.首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系.这些概念如下:序号遗传学概念遗传算法概念数学概念1个体要处理的基本对象、结构也就是可行解2群体个体的集合被选定的一组可行解3染色体个体的表现形式可行解的编码4基因染色体中的兀素编码中的兀素5基因位某一基因在染色体中的位置兀素在编码中的位置6适应值个体对于环境的适应程度， 或在环境压力下的生存能力可行解所对应的适应函数 值7种群被选定的一组染色体或个体根据入选概率定出的一组 可行解8选择从群体中选择优胜的个体， 淘汰劣质个体的操作保留或复制适应值大的可 行解
4、，去掉小的可行解9交叉一组染色体上对应基因段的 交换根据交叉原则产生的一组 新解10交叉概率染色体对应基因段交换的概 率（可能性大小）闭区间0,1上的一个值，一般为0.650.9011变异染色体水平上基因变化编码的某些兀素被改变12变异概率染色体上基因变化的概率 (可能性大小)开区间(0,1)内的一个值，一般为 0.0010.0113进化、 适者生存个体进行优胜劣汰的进化， 一代又一代地优化目标函数取到最大值，最 优的可行解(2)遗传算法的步骤遗传算法计算优化的操作过程就如同生物学上生物遗传进化的过程，主要有 三个基本操作(或称为算子):选择(Selection)、交叉(Crossover)、
5、变异(Mutation).遗传算法基本步骤主要是：先把问题的解表示成“染色体”，在算法中也就 是以二进制编码的串，在执行遗传算法之前，给出一群“染色体”，也就是假设 的可行解.然后，把这些假设的可行解置于问题的“环境”中，并按适者生存的 原则，从中选择出较适应环境的“染色体”进行复制，再通过交叉、变异过程产 生更适应环境的新一代“染色体”群.经过这样的一代一代地进化，最后就会收 敛到最适应环境的一个“染色体”上，它就是问题的最优解.下面给出遗传算法的具体步骤，流程图参见图1：第一步：选择编码策略，把参数集合(可行解集合、转换染色体结构空间；第二步：定义适应函数，便于计算适应值；第三步：确定遗传
6、策略，包括选择群体大小，选择、交叉、变异方法以及确 定交叉概率、变异概率等遗传参数；第四步：随机产生初始化群体；第五步：计算群体中的个体或染色体解码后的适应值；第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一 代群体；第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数， 不满足则返回第五步、或者修改遗传策略再返回第六步.图1 一个遗传算法的具体步骤遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要 步骤，此算法会一直运行直到找到满足条件的最优解为止.2. 遗传算法的实际应用例 1：设 f (x) = -x2 + 2x + 0.5，求 max f
7、 (x), x e -1,2.注：这是一个非常简单的二次函数求极值的问题，相信大家都会做.在此我 们要研究的不是问题本身，而是借此来说明如何通过遗传算法分析和解决问题.在此将细化地给出遗传算法的整个过程.(1)编码和产生初始群体首先第一步要确定编码的策略，也就是说如何把-1到2这个区间内的数用计 算机语言表示出来.编码就是表现型到基因型的映射，编码时要注意以下三个原则：完备性：问题空间中所有点(潜在解)都能成为GA编码空间中的点(染色 体位串)的表现型；健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解； 非冗余性：染色体和潜在解必须对应.这里我们通过采用二进制的形式来解决编码问
8、题，将某个变量值代表的个体 表示为一个0，1二进制串.当然，串长取决于求解的精度.如果要设定求解精 度到六位小数，由于区间长度为2- (-1) = 3，则必须将闭区间-1,2分为3X106 等分因为2097152 = 221 3x 106 222 = 4194304所以编码的二进制串至少需要 22位.将一个二进制串也心少卩耳)转化为区间-1,2内对应的实数值很简单， 只需采取以下两步(Matlab程序参见附录4)：1) 将一个二进制串(b21b20b19-b1b0)代表的二进制数化为10进制数：(b b b .bb ) = b -2i) = x21 20 191 0 2i 10i=0编码，这种
9、二进制编码的2) x对应的区间-1,2内的实数：参考资料页眉页脚可删除0001100111010110000000，% a3% a4 (Matlab 程序参见附录 2)化成十进制的数分别为：pop(1)= 1.523032, 0.574022 , -0.697235 , 0.247238 接下来我们就要解决每个染色体个体的适应值问题了.(2) 定义适应函数和适应值由于给定的目标函数f(x) = -X2 + 2x + 0.5在-1,2内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目 标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率
10、 打下基础.对于本题中的最大化问题，定义适应函数g(x)，采用下述方法:g (x)= f (x) - F ,若 f (x) - Fminmin0,其他式中F既可以是特定的输入值，也可以是当前所有代或最近K代中f (x)的最 min小值，这里为了便于计算，将采用了一个特定的输入值.若取F =-1，则当f (x)二1时适应函数g (x)二2 ；当f (x) =-1.1时适应函数ming (x) = 0 由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下 (Matlab程序参见附录3)：f pop(1)= 1.226437,1.318543 , -1.380607,0.933350 然后
11、通过适应函数计算出适应值分别如下(Matlab程序参见附录5、附录6)： 取 F =-1,mingpop(1)= 2.226437,2.318543 ,0,1.933350 (3) 确定选择标准这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值 比例叫作入选概率其计算公式如下：对于给定的规模为n的群体pop= a ,a ,a ,a ，个体a的适应值为g(a ),123nii则其入选概率为 P (a )=。丿, i = 1,2,3,，nf g(a)ii=1由上述给出的群体，我们可以计算出各个个体的入选概率.首先可得f g (a )= 6.47 8 3 3 0 ii=1然后分别用四
12、个个体的适应值去除以f g(a )，得: iP(a1)=2.226437 / 6.478330 = 0.343675 _% a1P(a2)=2.318543 / 6.478330 = 0.357892% a2P(a3)=0 / 6.478330 =0% a3P(a4)=1.933350 / 6.478330 = 0.298433% a4 (Matlab 程序参见附录 7)(4) 产生种群计算完了入选概率后，就将入选概率大的个体选入种群，淘汰概率小的个体， 并用入选概率最大的个体补入种群，得到与原群体大小同样的种群(Matlab程序 参见附录8、附录11).要说明的是：附录11的算法与这里不完全
13、相同.为保证收敛性，附录11的 算法作了修正，采用了最佳个体保存方法(elitist model)，具体内容将在后面给 出介绍.由初始群体的入选概率我们淘汰掉a3，再加入a2补足成与群体同样大小的 种群得到newpop如下：newpop(1)=1101011101001100011110，% a11000011001010001000010，% a21000011001010001000010，% a20110101001101110010101% a4(5) 交叉交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新 的染色体组，组成新的群体(Matlab程序参见附录9).我们把
14、之前得到的newpop(1)的四个个体两两组成一对，重复的不配对，进 行交叉.(可以在任一位进行交叉)1101011110000110010000110010100，交叉得：1010001000010，/ 01000010，交叉得：/ 、 10010101，通过交叉得到了四个新个体，得到新的群体jchpop (1)如下： jchpop(1)=，1000011001001100011110，这里采用的是单点交叉的方法，当然还有多点交叉的方法，不过有些烦琐， 这里就不着重介绍了.(6) 变异变异也就是通过一个小概率改变染色体位串上的某个基因(Matlab程序参见 附录10).现把刚得到的jchpop(1)中第3个个体中的第9位改变，就产生了变异，得到 了新的群体pop(2)如下：pop(2)= ,1000011001001100011110，
