遗传算法在数学建模中的应用

华南农业大学数学建模专题讲座遗传算法在数学建模中的应用华南农业大学理学院曾庆茂联系方法：（1）手机：[phone]（2）电子邮箱：[e-mail]1华南农业大学数学建模专题讲座第一部分遗传算法基础理论1．遗传算法的简单原理遗传算法(GeneticAlgorithm,GA)是一种基于自然群体遗传演化机制的高效探索算法，它摒弃了传统的搜索方式，模拟自然界生物进化过程，采用人工进化的方式对目标空间进行随机化搜索。它将问题域中的可能解看作是群体的一个个体或染色体，并将每一个体编码成符号串形式，模拟达尔文的遗传选择和自然淘汰的生物进化过程，对群体反复进行基于遗传学的操作（遗传，交叉和变异），根据预定的目标适应度函数对每个个体进行评价，依据适者生存，优胜劣汰的进化规则，不断得到更优的群体，同时以全局并行搜索方式来搜索优化群体中的最优个体，求得满足要求的最优解。遗传算法主要是用来寻优，它具有很多优点：它能有效地避免局部最优现象，有及其顽强的鲁棒性，并且在寻优过程中，基本不需要任何搜索空间的知识和其他辅助信息等等。利用遗传算法，可以解决很多标准优化算法解决不了的优化问题，其中包括目标函数不连续、不可微、高度非线性或随机的优化问题。我们先通过一个例子来了解遗传算法的原理：假定我们要求函数的极大值，其中2()fxx=，x为自然数，0≤x≤31。现在，我们将每一个数看成一个生命体，通过进化，我们看谁能最后生存下来，谁就是我们所寻找的数。①编码我们将每一个数作为一个生命体，那么必须给其赋予一定的基因，这个过程叫做编码。我们可以把变量x编码成5位长的二进制无符号整数表示形式，比如x=13可表示为01101的形式，也就是说，数13的基因为01101。②初始群体的生成由于遗传的需要，我们必须设定一些初始的生物群体，让其作为生物繁殖的第一代，需要说明的是，初始群体的每个个体都是通过随机方法产生的，这样便可以保证生物的多样性和竞争的公平性。③适应度评估检测2华南农业大学数学建模专题讲座生物的进化服从适者生存，优胜劣汰的进化规则，因此，我们必须规定什么样的基因是“优”的，什么样的基因是“劣”的，在这里，我们称为适应度。显然，由于我们要求2()fxx=的最大值，因此，能使2()fxx=较大的基因是优的，使2()fxx=较小的基因是劣的，因此，我们可以将定义2()fxx=为适应度函数，用来衡量某一生物体的适应程度。④选择（Selection）接下来，我们便可以进行优胜劣汰的过程，这个过程在遗传算法里叫做选择。注意，选择应该是一个随机的过程，基因差的生物体不一定会被淘汰，只是其被淘汰概率比较大罢了，这与自然界中的规律是相同的。因此，我们可以采取赌论的方式来进行选择。⑤交叉操作（Crossover）接下来进行交叉繁殖，随机选出两个生物体，让其交换一部分基因，这样便形成了两个新的生物体，为第二代。⑥变异（Mutation）生物界中不但存在着遗传，同时还存在着变异，在这里我们也引入变异，使生物体的基因中的某一位以一定的概率发生变化，这样引入适当的扰动，能避免局部极值的问题。以上例子的整个过程如下：初始群体01101110000100010011x的值1324819适应度2()fxx=16957664361选择概率0.140.490.060.31选择上的计数（来自赌轮）1201交叉处0110|01100|011|00010|011下一代群体01100110011101110000x的值12252716适应度2()fxx=144625729256…………………………3华南农业大学数学建模专题讲座以上的算法便是最简单的遗传算法，通过以上步骤不断地进化，生物体的基因便逐渐地趋向最优，最后便能得到我们想要的结果。2．遗传算法的步骤从上面的例子中，我们便能得到遗传算法的一般步骤，如下图所示：第二部分MATLAB遗传算法工具箱介绍以MATLAB7.1的遗传算法和直接搜索工具箱（GeneticAlgorithmandDirectSearchToolboxVersion2.0）为例。主要函数有：（1）ga——利用遗传算法求一个函数的最小值；（2）gaoptimget——获得遗传算法中选项的参数值；（3）gaoptimset——设置遗传算法中选项的参数值；（4）gatool——打开遗传算法工具（用户图形界面）。4华南农业大学数学建模专题讲座1遗传算法核心函数（ga）【功能】利用遗传算法求一个函数的最小值。【语法】[x,fval,reason，output，population，scores]=ga(fitnessfcn,nvars,A,b,Aeq,beq,LB,UB,nonlcon,options)【输入参数】（1）fitnessfcn——适应度函数，即所求优化问题的目标函数（2）nvars——适应度函数所含变量的个数（3）A——线性不等式约束Axb≤的系数矩阵A（4）b——线性不等式约束Axb≤的常数项组成的向量（5）Aeq——等式约束Axb=的系数矩阵A（6）beq——等式约束的常数项组成的向量Axb=（7）LB——x的下界（8）UB——x的上界（9）nonlcon——非线性约束函数（10）options——遗传算法相关参数值（通过gaoptimget函数设置）【输出参数】（1）x——所求优化问题的最小值点，优化问题的解（2）fval——适应度函数在最小值点的函数值（3）reason——输出遗传算法停止的原因（4）output——返回遗传算法的结构，主要包括以下信息：randstate:遗传算法开始运行前，随机函数rand的状态randnstate:遗传算法开始运行前，随机函数randn的状态generations:种群的个数funccount:适应度函数值的个数maxconstraint:最大约束超出范围（如果有的话）message:遗传算法终止的原因（与输出参数中的reason一样）population：返回最后的一个种群（5）population——返回最后一个种群的得分（6）scores——返回最后一个种群的得分5华南农业大学数学建模专题讲座2遗传算法设计主函数（gaoptimset）【功能】对遗传算法中的选项结构进行参数设置。【语法】（1）options=gaoptimset('param1',value1,'param2',value2,...)（2）options=gaoptimset(oldopts,'param1',value1,...)（3）options=gaoptimset(oldopts,newopts)（1）options=gaoptimset('param1',value1,'param2',value2,...)该命令创建一个名为options的结构，把参数“param1”设置为“value1”，把参数“param2”设置为“value2”，等等。对于不确定的参数，将设置为初始值。（2）options=gaoptimset(oldopts,'param1',value1,...)该命令复制一个名为oldopts的结构，但是用value1修改原来的参数param1。（3）options=gaoptimset(oldopts,newopts)该命令将一个现存的选项结构oldopts和一个新的选项结构newopts合并，在newopts中，如果参数是非空值，就覆盖旧结构oldopts中的相应参数。下表列出了函数gaoptimset可以设置的主要选项，其中用大括号{}括起来的部分是选现参数的默认值。（你也可以在Matlab命令窗口中输入gaoptimset参看相关的优化参数和默认值。选项描述取值CreationFcn创建初始种群{@gacreationuniform}CrossoverFraction交叉的比例正数{0.8}CrossoverFcn创建杂交子代的函数@crossoverheuristic{@crossoverscattered}@crossoverintermediate@crossoversinglepoint@crossovertwopoint@crossoverarithmeticEliteCount当前一代在下一代存活的数目正整数{2}FitnessLimit当自适应函数值达到FitnessLimit，算法停止标量{inf}6华南农业大学数学建模专题讲座3查看遗传算法选项结构参数值的函数（gaoptimget）【功能】获取遗传算法中选项结构相关参数的值【语法】（1）val=gaoptimget(options,'name')（2）val=gaoptimget(options,'name',default)（1）val=gaoptimget(options,'name')该命令返回遗传算法选项结构中名为name的参数值，如果当该选项中name的值不确定时，就返回值为一个空矩阵。（2）val=gaoptimget(options,'name'，default)该命令返回遗传算法选项结构中名为name的参数值，如果当该选项中name的值不确定时，就返回值为默认值。4打开遗传算法图形用户界面的函数（gatool）【功能】打开遗传算法图形用户界面【语法】（1）gatool（2）gatool(optstruct)第三部分遗传算法的MATLAB实现举例1．无约束优化问题1.1一维变量优化问题求下列函数的最大值：f(x)=x+10*sin(5x)+7*cos(4x)x[0,9]∈（1）写出待优化函数的M文件，代码如下functionf=myfun1(x)f=-x-10*sin(5*x)-7*cos(4*x);保存该代码MATLAB路径的一个目录中，文件名定义为myfun1.m。（注意：本问题是求函数的最大值，故待优化函数取原函数的相反数。）（2）设置选项结构的相关参数%调用函数fplot画出待优化函数的图形fplot('x+10*sin(5*x)+7*cos(4*x)',[0,9]);7华南农业大学数学建模专题讲座%获得默认的选项结构options=gaoptimset;%设置输入适应度函数的数据类型options.PopulationType='doubleVector';%设置种群大小options.PopulationSize=20;%设置交叉概率options.CrossoverFraction=0.95;%设置变异概率options.MigrationFraction=0.08;%设置变异函数（无约束情形）options.MutationFcn=@mutationadaptfeasible;%增加可视化效果函数options.PlotFcns={@gaplotbestf,@gaplotstopping};%调用遗传算法主函数[x,fval,exitflag]=ga(@myfun1,1,[],[],[],[],[0],[9],[],options)运行结果为：x=0.2324fval=13.5954（当x为7.8562时，f（x）取最大值24.8553）应该指出的是：遗传算法一般用来求近似最优解，而不是最优解。另外，遗传算法的收敛性跟其初始值有关，大家运行上面的命令所得到的结果可能跟我的结果不同或是差别很大。但多执行几次上面的命令（实际上是取不同的初始群体）一定可以得到近似最优解。1.2多维变量优化问题已知2212120.20.5*()0.5cos(2)cos(2)12(,)2022.71282xxxxfxxeeππ−++=−−+，[]5,5ix∈−，，1,2i=求解12(,)fxx的最小值。（1）写出待优化函数的M文件，代码如下functionf=myfun2(x)8华南农业大学数学建模专题讲座f=-20*exp(-0.2*sqrt(0.5*(x(1).^2+x(2).^2)))-exp(0.5*(cos(2*pi*x(1))+cos(2*pi*x(2))))+22.71282;保存该代码MA