一种改进遗传算法及验证
2022-10-07
来源：欧得旅游网
一种改进遗传算法及验证魏晓玲（广州工商学院计算机科学与工程系，广州510850）摘要院介绍了基本遗传算法的概念及求解过程，为解决遗传算法早熟、收敛慢以及计算复杂度高等问题，对算法的选择方式进行了改进，并使用Matlab工具箱函数对改进遗传算法进行实现。关键词院遗传算法；Matlab软件主流的寻优方法有遗传算法尧单纯形算法尧蚁群尧模拟退化等袁由于每种算法都有其自身的缺陷袁给算法的实际应用造成了一定的局限性袁寻优结果也有待进一步精确袁如单纯形算法容易出现最长边较长袁而体积过早接近于零的情况[1]理想袁易陷入局部最优境况而导致无法寻得最优解曰蚁群算法在收敛速率方面同样不[2]模拟退火算法进入最优区域的速度比较慢袁效率也比较曰低[3]明尧遥新型高效的遗传算子设计针对遗传算法的研究热点主要集中在尧遗传算法与局部优化算院收敛性证法的结合1基本遗传算法尧遗传算法在各领域的应用研究等[4]遥基本遗传算法渊simplegeneticalgorithm袁SGA冤是J.Holland然选择和孟德尔遗传学机理的生物进化过程的计算模教授提出的袁它是模拟达尔文生物进化论的自型袁是一种通过模拟自然进化过程搜索最优解的方法[5]遗传算法使用基本遗传算子袁如选择算子尧交叉算子遥尧变异算子袁对数据集体进行运算袁是其他改进遗传算法的基础[6]遥基本遗传算法的数学模型如图1所示遥编码生成初始种群个体适应度评估结束选择交叉变异图1遗传算法流程图1.1渊1冤遗传算法寻优过程基本遗传算法使用固定长度的二进制符号串表示群编码体中的个体袁初始种群中各个个体的基因可用均匀分布的随机数生成遥设某一参数取值范围[U1为小数点后j位袁即该参数至少被分成,U2(U]袁要求精度2部分袁由此2k-1<(U-U1)*10j个2串位数k袁也就是群体中的个体需要使用-U1)*10j臆2k-1袁可以求得二进制K位二进制数来表示遥对应的个体解码用求得袁其中decimal渊sub鄄stringj渊2冤冤表示变量X的十进制数值遥对于一个个体的适应度评价分为个体适应度评估3个步骤进行院第一步袁将二进制编码串进行反编码袁得到实际数值曰第二步袁评价目标函数f渊xi适应度eval渊U冤曰第三步袁将目标函数转化为i渊3冤冤=f渊1冤选择运算是根据每个个体的选择概率比例于群体累选择运算遗传算子xi冤遥计选择概率的比值来决定个体是否会被保留下来的遥若设种群数量为M袁个体适应度为fi袁那么该个体的选择概率为遥当个体的选择概率确定之后袁产生一个[0,1]之间的随机数袁将大于随机数的所对应的个体保留在下一代种群中袁即完成了一次选择运算遥这个选择过程一般可以采用像轮盘赌的方式进行袁即首先计算出每个个体的适应度值eval渊Ui袁然后计算出每个个体冤袁并计算出群体的适应度的总和于适应度总和F的比值pi袁计算每个个体的累计概率Ui的选择概率相对收稿日期：2019-03-042019.0623随机数r袁渊其中如果j=1,2,3噎冤遥r<=Q随后生成一个[0,1]之间的i否则选择第k个个体袁袁使其满足则将Qi保留到下一代种群中袁Qk-1种群大小冤遥臆Qk渊其中2臆k臆2冤种群在经过选择运算之后交叉运算袁随机选择种群中两个个体袁继续使用单点交叉算子袁随机确定一个交叉点位置袁将两个个体在交叉点位置进行互换编码的操作袁交换之后即形成新的两个个体遥假设该种群的种群数量为10袁个体编码长度为17袁交叉概率为15%袁即种群内平均有15%的个体会进行交叉运算遥随机生成[0,1]之间的10个数字袁从中找到<0.15中发生交叉运算的个体即是的数字袁比如第3个和第U7个数字<0.15袁则种群3和U7一个[1-17]之间的整数袁作为交叉点遥然后再随机生成遥假设生成的随机整数是3袁则两个个体就从第3位开始交叉袁将第3位右端的编码进行交换袁从而生成新的个体遥3冤变异运算一般是采用基本位变异运算或均匀变异运变异运算算遥假设个体U1的第15位发生变异袁该位原来是0袁则变异之后该位变为1遥假设变异概率为P渊二进制数冤基因袁m=0.01袁种群中一共有170个个二进制数渊基因冤采用均匀变异运算的变异概率是相等的袁每个个体中每遥因此袁可以生成[0,1]之间的随机数170个袁筛选出那些<0.01的随机数袁找到他们所在的基因位置袁从而找到他们所在的染色体位置及基因位置袁将对应的二进制编码数字进行兑换遥基本遗传算法为问题寻优提供了一种基本思路袁但在实际操作中往往出现早熟现象袁导致求得的解与最优解还存在较大偏差2改进遗传算法遥针对基本遗传算法存在的问题袁考虑采用以下方式解决院改进选择算子袁弃用轮盘赌的选择方式袁而按照个体适应度大小进行重新进行排序的新的选择算法袁以更好的体现出好的个体的竞争力袁让寻优过程更好地体现优胜劣汰的原则袁以防止适应度较高的个体过快占据种群袁也可以防止后期因个体适应度过于相近而出现种群停止寻优的情况遥这里试先采用第二种方式袁即改变种群的选择方242019.06式袁来对遗传算法做出改进袁按这样的思路进行改进之后袁遗传算法执行的伪代码如下院BEGINk饮0;初始化种群U;计算Ui的适应度Qi曰按适应度大小对QWhile渊不满足停止条件i排序曰冤doifQi排在前面then个体复制2份曰ifQi排在中间then个体复制1份曰ifQi排在后面then个体不复制曰endEND33.1改进遗传算法MatlabMatlab是由美国工具箱Matlab验证科学计算尧可视化及交互式程序设计的高科技计算环mathworks公司发布的主要面对境[7]持遥遥该工具箱包含有大量用传算法工具箱为遗传算法的使用提供了强大的支M文件编写的命令行形式的函数袁是完成遗传算法的程序的集合[8]3.2验证过程遥多个局部最小值和一个最优的全局的最小值Rastrigin函数是一个非常典型的测试函数袁现在利用袁它具有上述改进遗传算法来求解它的全局最小值遥Rastrigin函数具有两个独立变量x1和x2画出Rastrigin函数的图像院袁定义为院遥f=@(x,y)20+x.*x+y.*y-10*(cos(2*pi*x)+cos(2*pi*y));ezsurf(f,[-22])shadinginterp下面是利用Matlab遗传算法工具箱函数实现的关键代码部分说明院规定算法的参数如下院NUM=40曰%numberofindividualsMAXGEN=100;%maximumnumberofgener鄄ationsNVAR=2曰%numberofvarER=25曰%precisionofvariablesGAP=0.9曰%generationgap利用crtbp()函数创建任意离散随机种群院Chrom=crtbp利用(NUM,NVAR*ER)曰bs2rv()函数将初始种群转换成十进制院x=bs2rv(Chrom,FieldID);其中FieldID为创建的区域描述器渊Buildfielddescriptor冤遥计算目标函数值院Oresult=Rastrigin(x(:,1),x(:,2));While基于秩的适应度计算gen