文档介绍：,适应度函数被选择为哈密顿圈(Hamilton)的长度的倒数,这主要是由于其在可行解群体的交叉操作、初始化和变异操作中都含有TSP问题的合法性约束条件[5,21]。[4]。适应度函数能够用路径长度(即哈密顿圈长)的倒数表示,也就是()在上式中,也就是第i个解所表示的遍历城市的路径长度,公式表示如下: (),往往使用最优保存方法、赌轮法和期望等对算子方法进行选择。关于赌轮选择个体法,第一步将群体中的每个个体的适应值根据相应的比例转化成选中概率,分解轮盘成popsize个扇区;进而形成[0,1]之间的随机数r,逐渐累加第一个个体的选中概率,如果累加概率之和不低于r,则需要将被累加选中概率的个体选择出来,同时将其复制到子代中。在执行遗传算法的过程中,popsize个较优的个体需要一直作为样本群体,用于后续的选择。可是,这并不适用于赌轮选择算子,这主要是因为随机操作的使用造成其具有比较大的误差,甚至遗漏掉适应度较高的个体。根据遗传算法理论,赌轮法选择算子无法对全局最优解进行收敛,和以上算法相比,最优保存方法能够对全局最优解进行收敛。在遗传算法中,“早熟”收敛现象的防止至关重要。为了防止有效基因的遗漏,需要对个体的多样性进行保证,进而能够为遗传算法的全局收敛性提供一定的保证。所以,本文引入最优选择策略保证算法能够具有全局的收敛。和其他算法相比,最优保存选择方法在进化过程中某一代的最优解不会被变异操作或者交叉所影响。可是,其同样存在着一定的缺点,最优选择策略的选择也会导致局部最优个体的遗传基因的量显著地增加,进而引起局部解的出现。因此,综合使用选择方法比较重要[5]。所以,笔者在本文中对遗传算法的选择算子进行改进,综合使用最优保存策略、赌轮选择策略,现在简要描述如下:Stepl:对pop(t)中适应度最大的1个个体进行计算,记为best,下一代的个体也就是best,也即是说,最优个体肯定会遗传到下一代。Step2:用p(k)表示个体k的轮转法选择概率,也就是()Step3:令q(0)=0,q(k)=q(1)+q(2)+…+q(k),k=1,2,…,NStep4:出现N-1个[0,1)中的均匀分布的随机数,i=1,2,…,N-1,依次判断这N-1个随机数,如果,那么个体k就是下一代的个体。:采用赌轮策略在父代中选择两个个体,采用如下操作在一个亲体中挑选一城市子序列,同时将其保存另一个亲体的城市相对次序,形成两个新的个体,接着将这两个新个体添加到子代中去。以基因片段为基础的保序在求解TSP问题中的应用[21],笔者在本文中使用了一种新的交叉操作,类似于OX法[19],现在简要介绍其具体操作:在串中采用随机的方式对交配区域进行选择,假如两父体、交配区域能够被选定为:oldp1=12|3456|789,oldp2=98|7654|321(2)将oldp2的交配区域加到oldp1的前面,同时,oldp1的交配区域加到oldp2的前面,也即是:oldp12=7654|123456789,oldp21=3456|987654321(3)删除oldp12、oldp21交配区域后和交配区相同的城市码,终的两子