了Grefenstette编码方法

了Grefenstette编码方法.Grefenstette编码的优点是与解集中的元素具有一一对应的关系,杜绝了不合法的解的存在,容易保证初始群的随机性和多样性.而且采用该编码,交叉算子和变异算子容易实现,体现了遗传算法求解TSP的易操作性,到目前为止仍受到很多学者的青睐[12,14-20].虽然交叉和变异算子具有简单性,但他们对父代基因具有很大的破坏性,交叉和变异后的个体只遗传了一个父代个体改变基因前的基因.这有悖遗传算法的思想,影响了遗传算法的求解效率.基于上述的分析,本文采用Grefenstette编码对遗传算法的初始群进行设置,解码后采用自然编码进行交叉和变异操作,设计了新的交叉算子,运用这种编码策略的遗传算法对TSP问题进行求解.这种策略可以大量应用到工业生产中,用以提高加工和物流运转的效率.4.4.1适应值比例选择适应值比例选择是最基本的方法,其中每个个体被选中的期望与其适应值成正比,通常采用轮盘赌方式实现这种方式首先计算每个个体的适应值,然后计算出此适应值在群体适应值总和中所占比例,表示该个体在选择过程中被选种的概率当群体中个体适应值差异非常大时,最佳个体与最差个体被选择的概率之比会按指数增长最佳个体在下一代的生存机会将显著增加,而最差个体的生存机会将被剥夺当前群体中最佳个体将迅速充满整个群体,导致群体的多样性迅速降低,GA也就过早的失去了进化能力,很容易陷入局部最优解,因此此方法虽然简单,但是要慎用varcitynum=8;//城市数目varx0=30;vary0=30;varw=571;varh=531;//城市放置的区域for(vari=0;icitynum;i++)//从库中导出城市元件放置到随机位置,透明度为50%attachMovie(city,city+i,i,{_x:random(w)+x0,_y:random(h)+y0,_alpha:50,number:i})fuctiondistant(a,b){return(Math.sqrt(Math.pow(_root[city+a]._x-_root[city+b]._x,2)+Math.pow(_root[city+a]._y-_root[city+b]._y,2)))}初始化群体Varn=10For(vari=0;in;i++){f[i]=newArray(citynum);for(varj=0;jcitynum;j++){varflag=ture;while(flag)//保证数组中无重复数字{flag=false;f[i][j]=random(citynum);for(vark=0;kj;k++)if(f[i][j]=f[i][k])flag=ture;}}}