matlab实用教程实验十遗传算法优化问题

1、matlab 实用教程 实验十 遗传算法与优化问题matlab实用教程实验十遗传算法与优化问题一、问题背景与实验目的二、相关函数 命令）及简介三、实验内容四、自己动手 一、问题背景与实验目的遗传算法 GeneticAlgorithm GA ），是模拟达尔文的遗传选择和自然淘汰的生物进化过程的计算模型，它是由美国Michigan大学的J.Holland教授于1975年首先提出的.遗传算法作为一种新的全局优化搜索算法 ，以其简单通用、鲁棒性强、适于并行处理及应用范围广等显著特点，奠定了它作为21世纪关键智能计算之一的地位.本实验将首先介绍一下遗传算法的基本理论，然后用其解决几个简单的函数最值问题，

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

3、用，而它本身是否完全正确并不 重要 目前生物界对此学说尚有争议）.1）遗传算法中的生物遗传学概念 因为遗传算法是由进化论和遗传学机理而产生的直接搜索优化方法；故而在这个算法中要 用到各种进化和遗传学的概念.首先给出遗传学概念、遗传算法概念和相应的数学概念三者之间的对应关系.这些概念如 下：序号遗传学概念遗传算法概念数学概念1 个体要处理的基本对象、结构也就是可行解 2群体个体的集合被选定的一组可行解 3染色体个体的表现形式可行解的编码 4基因染色体中的元素编码中的元素 5基因位某一基因在染色体中的位置元素在编码中的位置 6适应值个体对于环境的适应程度，或在环境压力下的生存能力可行解所对应的适应

4、函数值 7种群被选定的一组染色体或个体根据入选概率定出的一组可行解 8选择从群体中选择优胜的个体，淘汰劣质个体的操作保留或复制适应值大的可行解，去掉 小的可行解9交叉一组染色体上对应基因段的交换根据交叉原则产生的一组新解 10交叉概率染色体对应基因段交换的概率可能性大小）闭区间 0,1上的一个值，一般为 0.650.9011变异染色体水平上基因变化编码的某些元素被改变 12变异概率染色体上基因变化的概率可能性大小）开区间 （0,1 内的一个值 , 一般为 0.0010.01 13进化、 适者生存个体进行优胜劣汰的进化，一代又一代地优化目标函数取到最大值，最优的可行 解<2）遗传算法的步骤

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

6、染色体 ”上，它就是问题的最优解. 下面给出遗传算法的具体步骤，流程图参见图 1：第一步：选择编码策略，把参数集合<可行解集合）转换染色体结构空间；第二步：定义适应函数，便于计算适应值； 第三步：确定遗传策略，包括选择群体大小，选择、交叉、变异方法以及确定交叉概率、 变异概率等遗传参数；第四步：随机产生初始化群体； 第五步：计算群体中的个体或染色体解码后的适应值； 第六步：按照遗传策略，运用选择、交叉和变异算子作用于群体，形成下一代群体； 第七步：判断群体性能是否满足某一指标、或者是否已完成预定的迭代次数，不满足则返 回第五步、或者修改遗传策略再返回第六步.图1 一个遗传算法的具体步骤

7、遗传算法有很多种具体的不同实现过程，以上介绍的是标准遗传算法的主要步骤，此算法 会一直运行直到找到满足条件的最优解为止.2.遗传算法的实际应用 例1：设，求 注：这是一个非常简单的二次函数求极值的问题，相信大家都会做.在此我们要研究的不 是问题本身，而是借此来说明如何通过遗传算法分析和解决问题. 在此将细化地给出遗传算法的整个过程.<1）编码和产生初始群体 首先第一步要确定编码的策略，也就是说如何把 到2这个区间内的数用计算机语言表示出来. 编码就是表现型到基因型的映射，编码时要注意以下三个原则： 完备性：问题空间中所有点 < 潜在解）都能成为GA编码空间中的点 < 染色体位

8、串）的表现 型；健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解； 非冗余性：染色体和潜在解必须一一对应. 这里我们通过采用二进制的形式来解决编码问题，将某个变量值代表的个体表示为一个0，1 二进制串.当然，串长取决于求解的精度.如果要设定求解精度到六位小数，因为区 间长度为，则必须将闭区间分为等分因为所以编码的二进制串至少需要22位将一个二进制串 <b21b20b19b1b0 ）转化为区间内对应的实数值很简单，只需采取以下两步 <Matlab 程序参见附录 4）：1） 将一个二进制串<b21b20b19b1b0代表的二进制数化为 10进制数：2）对应的区间内

9、的实数：例如，一个二进制串 表示实数0.637197.二进制串 <>， ，> 则分别表示区间的两个端点值-1 和2.利用这种方法我们就完成了遗传算法的第一步 编码，这种二进制编码的方法完全符合上述的编码的三个原则. 首先我们来随机的产生一个个体数为 4个的初始群体如下： pop（1>=， % a1， % a2， % a3<> % a4<Matlab 程序参见附录 2）化成十进制的数分别为：pop（1>= 1.523032 ， 0.574022 ， -0.697235 ， 0.247238 接下来我们就要解决每个染色体个体的适应值问题了.<2

10、）定义适应函数和适应值 因为给定的目标函数 在内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应 值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入 选概率打下基础.对于本题中的最大化问题，定义适应函数，采用下述方法：式中既可以是特定的输入值，也可以是当前所有代或最近K代中的最小值，这里为了便于计算，将采用了一个特定的输入值.若取，则当时适应函数；当时适应函数由上述所随机产生的初始群体，我们可以先计算出目标函数值分别如下<Matlab 程序参见附录 3 ）：f pop（1>= 1.226437 , 1.318543 , -1.

11、380607 , 0.933350 然后通过适应函数计算出适应值分别如下 <Matlab 程序参见附录 5、附录 6）： gpop(1>= 2.226437 , 2.318543 , 0 , 1.933350 <3)确定选择标准 这里我们用到了适应值的比例来作为选择的标准，得到的每个个体的适应值比例叫作入选 概率其计算公式如下：对于给定的规模为n的群体pop= ，个体 的适应值为，则其入选概率为 由上述给出的群体，我们可以计算出各个个体的入选概率首先可得然后分别用四个个体的适应值去除以，得：P(a1>=2.226437 / 6.478330 = 0.343675 % a

12、1P(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的算法与这里不完全相同为保证收敛性，附录11的算法作了修正，采用了最佳个体保存方法 <eliti

13、st model )，具体内容将在后面给出介绍由初始群体的入选概率我们淘汰掉a3，再加入a2补足成与群体同样大小的种群得到newpop(1> 如下：newpop(1>=， % a1， % a2， % a2 <> % a4<5)交叉 交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组， 组成新的群体 <Matlab 程序参见附录 9)我们把之前得到的newpop(1>的四个个体两两组成一对，重复的不配对，进行交叉.<可以在任一位进行交叉)<110101110 10>， 交叉得：<100001100 10&

14、gt;， <100 01000010>， 交叉得：<>， <> 通过交叉得到了四个新个体，得到新的群体 jchpop (1> 如下：jchpop（1>= ， ， ， <> 这里采用的是单点交叉的方法，当然还有多点交叉的方法，不过有些烦琐，这里就不着重 介绍了<6）变异 变异也就是通过一个小概率改变染色体位串上的某个基因 <Matlab 程序参见附录 10） 现把刚得到的 jchpop（1> 中第 3个个体中的第 9位改变，就产生了变异，得到了新的群体 pop（2 >如下：pop（2>= ， ， ， <

15、;> 然后重复上述的选择、交叉、变异直到满足终止条件为止<7）终止条件 遗传算法的终止条件有两类常见条件： <1）采用设定最大 <遗传）代数的方法，一般可设 定为50代，此时就可能得出最优解此种方法简单易行，但可能不是很精确<Matlab程序参见附录 1）； <2）根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因 位相似程度来进行控制.3 遗传算法的收敛性 前面我们已经就遗传算法中的编码、适应度函数、选择、交叉和变异等主要操作的基本内 容及设计进行了详细的介绍作为一种搜索算法，遗传算法通过对这些操作的适当设计和 运行，可以实现兼顾全局搜索和局部

16、搜索的所谓均衡搜索，具体实现见下图2所示.图2 均衡搜索的具体实现图示 应该指出的是，遗传算法虽然可以实现均衡的搜索，并且在许多复杂问题的求解中往往能 得到满意的结果，但是该算法的全局优化收敛性的理论分析尚待解决目前普遍认为，标 准遗传算法并不保证全局最优收敛但是，在一定的约束条件下，遗传算法可以实现这一 占八、下面我们不加证明地罗列几个定理或定义，供读者参考<在这些定理的证明中，要用到许多概率论知识，特别是有关马尔可夫链的理论，读者可参阅有关文献）定理 1 如果变异概率为 ，交叉概率为，同时采用比例选择法 <按个体适应度占群体适应度的比例进行复制），则标准遗传算法 的变换矩阵P是

17、基本的.定理 2 标准遗传算法 <参数如定理 1）不能收敛至全局最优解 由定理 2可以知道，具有变异概率，交叉概率为 以及按比例选择的标准遗传算法是不能收敛至全局最最优解我们在前面求解例1时所用的<称作方法就是满足定理 1的条件的方法这无疑是一个令人沮丧的结论 然而，庆幸的是，只要对标准遗传算法作一些改进，就能够保证其收敛性具体如下：我 们对标准遗传算法作一定改进，即不按比例进行选择，而是保留当前所得的最优解超个体）该超个体不参与遗传 最佳个体保存方法 elitistmodel）的思想是把群体中适应度最高的个体不进行配对交叉而直接复制到下一代中.此种 选择操作又称复制copy）.

18、De Jong对此方法作了如下定义： 定义设到时刻t第t代）时，群体中a*t）为最佳个体又设 At + 1）为新一代群体，若 At + 1 ）中不存在a*t），则把a*（t作为At + 1）中的第n+1个个体 其中，n为群体大小）Matla b程序参见附录11）.采用此选择方法的优点是，进化过程中某一代的最优解可不被交叉和变异操作所破坏.但 是，这也隐含了一种危机，即局部最优个体的遗传基因会急速增加而使进化有可能限于局 部解.也就是说，该方法的全局搜索能力差，它更适合单峰性质的搜索空间搜索，而不是 多峰性质的空间搜索.所以此方法一般都与其他选择方法结合使用.定理3具有定理 1所示参数，且在选择

19、后保留当前最优值的遗传算法最终能收敛到全局最优解. 当然，在选择算子作用后保留当前最优解是一项比较复杂的工作，因为该解在选择算子作 用后可能丢失.但是定理 3至少表明了这种改进的遗传算法能够收敛至全局最优解.有意思 的是，实际上只要在选择前保留当前最优解，就可以保证收敛，定理4描述了这种情况.定理4 具有定理 1参数的，且在选择前保留当前最优解的遗传算法可收敛于全局最优解. 例2：设，求，编码长度为 5，采用上述定理 4所述的 “在选择前保留当前最优解的遗传算法 ”进行二、相关函数 命令）及简介本实验的程序中用到如下一些基本的Matlab函数：on es, zeros, sum, size,

20、le ngth, subs, double等，以及for,while等基本程序结构语句，读者可参考前面专门关于Matlab的介绍，也可参考其他数学实验章节中的 “相关函数 命令）及简介 ”内容，此略.三、实验内容上述例 1 的求解过程为： 群体中包含六个染色体，每个染色体用22位01码，变异概率为 0.01 ，变量区间为，取 Fmin=，遗传代数为50代，则运用第一种终止条件指定遗传代数）的Matlab程序为：Count,Result,BestMember=Genetic1（22,6,'-x*x+2*x+0.5',-1,2,-2,0.01,50执行结果为：Count =50Re

21、sult =1.0316 1.0316 1.0316 1.0316 1.0316 1.03161.4990 1.4990 1.4990 1.4990 1.4990 1.4990BestMember =1.03161.4990图2 例1的计算结果 注：上图为遗传进化过程中每一代的个体最大适应度； 而下图为目前为止的个体最大适应度 单调递增）我们通过 Matlab 软件实现了遗传算法，得到了这题在第一种终止条件下的最优解：当 取1.0316时，当然这个解和实际情况还有一点出入 <应该是取1时， ），但对于一个计算机算法来说已经很不错了我们也可以编制 Matlab 程序求在第二种终止条件下的最优解此略，留作练习实践表明 ，此时的遗传算法只要经过 10代左右就可完成收敛，得到另一个“最优解 ”，与前面的最优解相差无几四、自己动