遗传算法精编课件精编ppt.ppt

*第三章遗传算法*(Scaling)*:用1到N的自然数的不同顺序来编码,此种编码不允许重复,即且,又称自然数编码。该法适用范围很广:指派问题、旅行商问题和单机调度问题等等。合法性问题:(1)*实数编码:,R为实数集特征:方便运算简单,但反映不出基因的特征整数编码类似于顺序编码,但编码允许重复适用于:新产品投入,时间优化,伙伴挑选例:3212345对顺序编码来说是不合法的,而对整数编码来说是合法的;010200不合法的01编码;(2)* 在顺序编码遗传运算的过程中会遇见不合法的编码,应战的策略有二:拒绝或修复。例如:经双切点交叉后,后代编码不合法21¦345¦6721¦125¦6743¦125¦7643¦345¦76我们采用下面的修复策略使以上的编码合法。(3)*顺序编码的合法性修复:交叉修复策略,分为以下几种:(4)*部分映射交叉(PMX)(PartiallyMappedCrossover):用特别的修复程序解决简单的双切点交叉引起的非法性,步骤:⑴选切点X,Y;⑵交换中间部分;⑶确定映射关系;⑷将未换部分按映射关系恢复合法性。(5)*PMX例题:(6)映射关系:3-1,4-2,5-5则:43¦125¦6721¦345¦7621¦345¦67¦125¦43¦125¦76¦345¦XY*顺序交叉(OX)OrderCrossover:可看做是带有不同修复程序的部分映射交叉的变形。OX步骤:⑴选切点X,Y;⑵交换中间部分;⑶从切点Y后第一个基因起列出原顺序,去掉已有基因;⑷从切点Y后第一个位置起,按顺序填入。(7)*OX例题:(8)列出基因:672**********则:34¦125¦6712¦345¦7621¦345¦67¦125¦43¦125¦76¦345¦XY