现代信息技术及其应用作业.docx

船舶工程学院现代信息技术及其应用（遗传算法及在数值求解中的应用）学 号：S316010059专 业：水 利 工 程学生姓名：张 娜任课教师：李 明 伟2017年3月遗传算法及在数值求解中的应用张娜船舶工程学院摘要：遗传算法是一种基于生物自然选择与遗传机理的随机搜索与优化方法，具有较强的鲁棒性。隐含并行性和全局搜索特性是遗传算法的两大显著特征。本文简要概述了遗传算法的基本原理和特点，并结合算例介绍了遗传算法在数值求解中的应用。关键词：遗传算法，数值求解，遗传算子0 前言遗传算法是由美国的Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机搜索算法。遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子（选择、交叉和变异）对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。目前，遗传算法正在迅速发展，它以其很强的解决问题能力和广泛的适应性渗透到研究与工程的各个领域，取得了良好的效果。近年来，在多种问题的解决方法上，遗传算法都得到广泛应用。1 基本原理在自然界，由于组成生物群体中各个体之间的差异，对所处环境有不同的适应和生存能力，遵照自然界生物进化的基本原则，适者生存，优胜劣汰，将要淘汰一些最差个体，通过交配将父本优秀的染色体和基因遗传给子代，通过染色体上基因的重新组合产生生命力更强的新个体，并与他们组成新的群体。在特定的条件下，基因会发生突变，产生新基因和生命力更强的新个体；但突变是非遗传的，随着个体不断更新，群体不断朝着最优方向进化。遗传算法是真实模拟自然界生物进化机制进行寻优的一种优化方法。与传统搜索算法不同，遗传算法从一组随机产生的初始解，称为群体，开始搜索过程。群体中的每个个体是问题的一个解，称为染色体。这些染色体在后续迭代中不断进化，称为遗传。遗传算法主要通过交叉，变异，选择运算实现交叉或便宜运算生成下一代染色体，称为后代。染色体的好坏用适应度来衡量。根据适应度的大小从上一代和后代中选择一定数量的个体，作为下一代群体，再继续进化。这样经过若干代之后，算法收敛于最好的染色体，它很可能就是问题的最优解或次优解。遗传算法中使用适应度来度量群体中的各个个体在计算中有可能达到最优解的优良程度。度量个体适应度的函数称为适应度函数。适应度函数的定义一般与具体求解问题有关。1.1 算法步骤图1 典型算法步骤1.2 编码编码是遗传算法要解决的首要问题。常用的编码方法有二进制编码，格雷码编码，实数编码，符号编码等，针对不同的问题要采用不同的编码方法。1.3 群体设定遗传操作是对众多个体同时进行的，这众多个体组成了群体。在遗传算法处理流程中，继编码设计后的任务是初始群体的设定，并以此为起点，一代代进化直到按某种进化停止准则终止进化过程，由此得到最后一代。关键问题是，群体规模，即群体中包括的个体数目如何确定。其中有两个需要考虑的因素：初始群体的设定：首先根据问题原有知识，设法把握最优解所占空间在整个问题空间的分布范围，然后在此分布范围内设定初始群体。然后先随机生成一定数目的个体，然后从中挑出最好的个体加到初始群体中这种过程不断迭代，直到初始群体中个体数达到了预先确定的规模。进化过程中各代的规模如何维持：群体规模的确定受遗传操作中选择操作的影响很大。一般而言，群体规模越大，群体中个体的多样性越高，算法陷入局部解的危险就越小。所以，从考虑群体多样性出发，群体规模应较大。但是，群体规模太大会带来若干弊病。一是计算效率，群体越大，其适应值评估次数增加，所以计算量也增加，从而影响算法效能；二是群体中个体生存下来概率大多采用和适应值成比例的方法，当群体中个体非常多时，少量适应值很高的个体会被选择而生存下来，但大多数个体却被淘汰，这会影响配对库的形成，从而影响交叉操作，另一方面，群体规模太小，会使遗传算法的搜索空间中分布范围有限，因而搜索有可能停止在未成熟阶段，引起未成熟收敛现象。适应度函数：遗传算法在进化搜索中基本上不用外部信息，仅用适应度函数作为依据。遗传算法的目标函数不受连续可微的约束且定义域可以为任意集合。对目标函数的唯一要求是针对输入值，可计算出能加以比较的非负结果。这一特点使得遗传算法应用范围很广。1.4 遗传操作遗传操作包括3个基本遗传算子，交叉，变异，选择。这3个算子有以下特点：这3个遗传算子的操作都是随机化操作，因此，个体向最优解的迁移也是随机的。遗传操作的效果和上述3个遗传算子所取的操作概率，编码方法，群体大小，初始群体以及适应度函数的设定密切相关。3个基本遗传算子的操作方法或操作策略和个体的编码方式直接有关。1）选择运算选择运算就是对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的个体被遗传到下一代群体中的概率小。它的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。2）交叉运算交叉运算是指两个相互配对的染色体按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它决定了遗传算法的全局搜索能力，是产生新个体的主要方法。常用的交叉算子有：单点交叉。它是指在个体编码串中随机设置一个交叉点，然后在该点后相互交换两个配对个体的部分基因。双点交叉。它的具体操作过程是：在相互配对的两个个体中编码串中设置两个交叉点，交换两个交叉点之间的部分基因。均匀交叉。它是指两个配对个体的每一位基因都以相同的概率进行交换，从而形成两个新个体。3）变异运算所谓变异运算，是指将个体编码串中的某些基因值用其他基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，但必不可少，因为它决定了遗传算法的局部搜索能力。常用的方法有：基本位变异。它是指对个体编码串以变异概率pm随机制定某一位或某几位基因作变异运算。均匀变异。它是指分别用符合某一范围内均匀分布的随机数，以某一较小的概率来替换个体中的每个基因。2 特点1）以决策变量的编码作为运算对象此种编码方式使得我们在优化计算过程中可以借鉴生物学中染色体和基因等概念，可以模仿自然界中生物的遗传和进化等机理，也使得我们可以更加方便的应用遗传算子。2）直接以目标函数值作为搜索信息通过使用由目标函数值变换来的适应度函数值，就可确定进一步的搜索方向和搜索范围，无需求导等其他辅助信息。既避免求导，也使得我们可以把搜索的范围集中到硬度较高的部分搜索空间中，提高了搜索效率。3）概率搜索法遗传算法是一种自适应概率搜索法，其选择、交叉、变异等运算都是以一种概率的方式来进行的，从而增加了其搜索过程的灵活性。尽管也会使群体里产生适应度不高的个体，但随着进化过程的进行，新的群体中总会更多地产生许多优良的个体，时间和理论都已经证明：在一定条件下遗传算法总是以概率1收敛于问题的最优解。4）多个搜索点的搜素信息遗传算法从由很多个体所组成的一个初始群体开始最优解的搜索过程，对这个群体所进行的选择、交叉、变异等运算，产生的是新一代的群体，在这之中包括了很多群体信息，这是遗传算法隐含的一种并行性。3 案例分析3.1 实例1）题目：求函数的全局最大值计算。Max y=-x2 +50x +12s.t. 1x50要求：使用遗传算法对题目进行求解。2）题目分析由题意易得：y=-x2 +50x +12=（x-25）2 +637即：当x=25时，y取到最大值，ymax =637。3.2 遗传算法的构造过程图2 构造步骤图解（1）确定决策变量和约束条件。由y=-x2 +50x +12及s.t.：1x50可得决策变量x及其约束条件。（2）建立优化模型。本题的优化模型为：y=-x2 +50x +12。（3）确定编码方法。本题采用二进制编码，码长（n_code）为8位，二进制编码串对应区间为0，255。最小值：00000000对应十进制为0，最大值sn：11111111对应十进制为28-1=255（4）确定解码方法。将二进制编码串转换为对应的十进制整数代码，记为z。利用公式：x=z*49sn+1（5）确定个体评价方法。由y=-x2 +50x +12可知，函数的值域总是非负的，并且优化目标是求函数的最大值，故这里将个体的适应度值截取为对应的目标函数值，即：F（x）=-x2 +50x +12+FK，式中，FK的作用是为了防止函数值出现负值，本题取FK=0。（6）设计遗传算子a）选择运算使用比例选择算子（轮盘赌法）；比例选择：一种回放式随机采样的方法。其基本思想是：各个个体被选中的概率与其适应度大小成正比。本题先计算出每个个体所对的适应度值及被选中的概率，在叠加求其累计概率，而后利用（0，1）的随机数来判定选择哪一个个体。b）交叉运算使用单点交叉算子；单点交叉：在个体编码串中随机设置一个交叉点，然后在该点后相互交换两个配对个体的部分染色体。本题先通过产生（0，1）随机数及判断是否满足不高于交叉概率的方法选择交叉父本并通过判断语句来保持所选父本个数为偶数；之后随机得到杂交序列及杂交点，将杂交点之后的基因通过赋值语句将其互换，杂交运算完毕。c）变异运算使用基本位变异算子。基本位变异：对个体编码串中以变异概率随机指定的某一位或某几位基因座上的基因值做变异运算。本题先通过产生（0，1）随机数及判断是否满足不高于变异概率的方法选择需要变异的个体并记录其个数，而后通过随机得到变异位置，进行变异运算。（7）确定遗传算法的运行参数。对于本题，设定基本遗传算法的运行参数如下：群体大小：N=20终止代数：T=80交叉概率：pc=0.6变异概率：pm=0.053.3 结果分析依据以上步骤编写代码运行，随机得到运行结果图，如下图所示：a）结果图1b）结果图2 最大值； 平均值；图2 进化过程及运行结果由运行结果图可得，表示最大值的曲线趋于平缓，并且在637上下波动，可见结果收敛性比较好。附录（一）Matlab代码1）初始化及编码%遗传算法%步骤一：生成父本N组，采用二项随机数生成clc;clear;N=20; %群体个数n_code=8; %解的码长sn=2n_code-1; %二进制码中的最大值x_rand=randi(0 sn,1,N); %生成N个随机数，随机区间0-snx_father_pre=dec2bin(x_rand,n_code); %父本初始化编码二进制 T=80; %演化代数 for i_global=1:T x=bin2dec(x_father_pre).*(49/sn)+1; %转换为实数值（两区间之间的转换）2）选择运算%步骤二：轮盘赌选择父本 FK=0; %适应度调整 F_eval=-1*x.2+50*x+12.+FK; %个体适应度 F_eval_top(i_global),POS=max(F_eval); %当前代最大值和位置 x_solution_best(i_global)=x(POS); %最大时x各位多少 F_eval_mid(i_global)=sum(F_eval)/N; %适应度平均值记录 F_s=sum(F_eval); %适应度和 F_p=F_eval/ F_s; %每个染色体的选择概率 F_q(1)=F_p(1); %累积概率 for i=2:N F_q(i)=F_p(i)+ F_q(i-1); end for i=1:N rq(i)= unifrnd(0,1); %产生N个0-1的随机数 for j=1:N if(rq(i)=F_q(j) %是否小于轮盘概率 x_father(i,:)=x_father_pre(j,:); %父本选择 break; end end end3）交叉运算%步骤三：单点交叉 交叉概率pc=0.6 t=0; %交叉父本个数 for i=1:N rc = unifrnd(0,1); %产生N个0-1的随机数 if(rc0) t=t-1; %保证为偶数 end pc_pos=randi(1 n_code-1,1,t); %交叉点的位置生成 pc_sq=randperm(t); %交叉序列随机生成 for i=1:2:t-1 %有t个父本用来交叉，每次挑2，最后的是t-1和t for h=pc_pos(i)+1:n_code %从交叉点的位置后一位到最后开始交换 x_c=x_father(s(pc_sq(i),h); x_father(s(pc_sq(i),h)=x_father(s(pc_sq(i+1),h); %交换之后完成交叉 x_father(s(pc_sq(i+1),h)=x_c; end end4）变异运算%步骤四：变异概率pm=0.05 k=0; %变异个数 for i=1:N rm = unifrnd(0,1); %产生一个0-1的随机数 if (rm=0.05) k=k+1; pm_pos=randi(1,n_code); %变异点的位置生成 if x_father(i,pm_pos)=1 x_father(i,pm_pos)=0; else x_father(i,pm_pos)=1; %变异取反 end end end x_father_pre=x_father;end5）最大值 MAX_value,MAX_POS=max(F_eval_top); %最大值 X_minus=floor(x_solution_best(MAX_POS)-1; %最大时整数x-1（floor向下取整）58.01 X_MAX=X_minus+1; %最大时整数x （58.7考虑57,58,59） X_plus=X_minus+2; %最大时整数x+1 X=X_minus,X_MAX,X_plus; F_evalX=-1*X.2+50.*X+12; MAX_value_N,n=max(F_evalX); X_MAX=X(n); %找到最大时的整数x6）绘制结果图Tn=1:T;plot(Tn,F_eval_top-FK,b);hold on;plot(Tn,F_eval_