2遗传算法(3)

河北大学吴彬([e-mail])12遗传算法(3)遗传算法技术介绍河北大学2吴彬([e-mail])2.5连续性遗传算法实数编码123(,,,,)nxxxx河北大学3吴彬([e-mail])二进制数编码的不足100个变量，[-250,250]，精度0.00001100×26＝2600长的二进制串表示染色体。此时的遗传算法的搜索空间大约为22600。2526500233554432500000006710886420.00001河北大学4吴彬([e-mail])实数编码的优越性适合于在遗传算法中表示范围较大的数。适合于精度要求较高的问题。便于与经典优化方法混合使用。便于处理含约束条件的问题。河北大学5吴彬([e-mail])设计遗传算法须注意问题适应度，复制，不依赖于问题的编码方法。选择，变异，运行后要保证个体在约束范围内。一些参数，本质上都可以使得它随着遗传代数的不同而变化。河北大学6吴彬([e-mail])2.5连续性遗传算法适应度线性变换Ranking适应度分配复制比例选择法（轮盘选择）随机一致选择竞技选择法交换线性交换中间交换启发式交换突变均匀变异非均匀变异河北大学7吴彬([e-mail])约束条件的处理－惩罚策略惩罚技术是遗传算法解约束优化问题中最常用的技术。本质上它是通过惩罚不可行解将约束问题转化为无约束问题。河北大学8吴彬([e-mail])约束条件的处理－惩罚策略河北大学9吴彬([e-mail])约束条件的处理－惩罚策略21max()..()0;1,2,,()()()()(())0()()imiiiifxstgximxXfxfxpxpxdxxdxgxxX为可行解其他河北大学10吴彬([e-mail])约束条件的处理－惩罚策略惩罚策略的主要问题是如何设计一个惩罚函数，从而能有效地引导遗传搜索达到解空间的最好区域。()px河北大学11吴彬([e-mail])约束条件的处理－惩罚策略惩罚项的评估函数加法形式对于极大化问题，取()()()fxfxpx()0x()0pxpx若可行其他河北大学12吴彬([e-mail])约束条件的处理－惩罚策略惩罚项的评估函数乘法形式对于极大化问题，取()()*()fxfxpx()1x0()1pxpx若可行其他河北大学13吴彬([e-mail])约束条件的处理－惩罚策略惩罚项的评估函数不带参数的惩罚项带参数的惩罚项带参数的惩罚策略主要用于在遗传算法运行的不同阶段惩罚项对目标函数的惩罚的大小不同。一般来说，希望初期惩罚小些，后期惩罚大些。河北大学14吴彬([e-mail])约束条件的处理－惩罚策略21max()..()0;1,2,,()0;1,,()()()()(())0x()|()|1|()|m+1iiniiiiifxstgximhximnxXfxfxpxpxdxdxgxhxn若可行imi不带参数的惩罚项河北大学15吴彬([e-mail])约束条件的处理－惩罚策略带参数的惩罚项21max()..()0;1,2,,()0;1,,()()()()(())0x()|()|1|()|m+1iiniiiiifxstgximhximnxXfxfxpxpxdxdxgxhxn若可行imi河北大学16吴彬([e-mail])约束条件的处理－惩罚策略21(0)0.1,()(1)*0.1()()()(,)(())0x()|()|1|()|1()m+1niiiiittfxfxpxptxdxdxgxhxnt若可行imi初期惩罚小后期惩罚大河北大学17吴彬([e-mail])谢谢参考文献GEATbx_Intro_Algorithmen_v33a，遗传算法与工程设计，[日]玄光男，程润伟著，科学出版社演化程序——遗传算法和数据编码的结合，[美]Z.米凯利维茨著，科学出版社河北大学19吴彬([e-mail])线性交换需要注意：防止染色体超出约束范围112221[,1],0'*(1)*'*(1)*.[0,251]xaxaxxaxaadddxa河北大学20吴彬([e-mail])线性交换河北大学21吴彬([e-mail])中间交换需要注意：防止染色体超出约束范围112221'*(1)*'*(1)*[,1],0.25,1,2,,iiiiiiiiiiixaxaxxaxaxadddiL河北大学22吴彬([e-mail])中间交换河北大学23吴彬([e-mail])启发式交换r为[0,1]间随机数不比差，即对最大值问题特点使用了目标函数值以确定搜索方向。只生成一个后代它可能根本不产生解3212*()xrxxx21()()fxfx2x1x河北大学24吴彬([e-mail])启发式交换此算子有可能产生不可行解，此时产生另一个随机数r以及另一个后代。如果尝试w此后仍失败，算子终止。2x1x3x河北大学25吴彬([e-mail])启发式交换主要作用微调朝一个最有希望的方向搜索河北大学26吴彬([e-mail])均匀变异1212minmaxmin(,,,,,)(,,,',,)'*()[0,1]knknkxxxxxxxxxuruur河北大学27吴彬([e-mail])均匀变异依次指定个体编码串中的每个基因座为变异点。对每一个变异点，以变异概率pm从对应基因取值范围内取一随机数来替代原有基因值。河北大学28吴彬([e-mail])非均匀变异1212maxmin(,,,,,)(,,,',,)'(,)'(,)(,)**(1)[0,1],knknkkkkkkbxxxxxxxxxxtuxorxxtxuttyyrTrT最大代数,b参数kxmaxuminu河北大学29吴彬([e-mail])非均匀变异表示产生[0,y]中的一个数。随着代数t增加，靠近0的概率增加，也就是，在初期算子可均匀搜索空间（t比较小时），在后期，局部搜索。(,)ty(,)ty