计算机算法

3.3.4适应度函数在本算法中，适应度函数被选择为哈密顿圈（Hamilton）的长度的倒数，这主要是由于其在可行解群体的交叉操作、初始化和变异操作中都含有TSP问题的合法性约束条件[5,21]。适应值可以使用路径倒数是Glodberg.D.E.在研究的基础上提出的[4]。适应度函数能够用路径长度（即哈密顿圈长）dT的倒数表示，也就是)(/1)(iTiFitnessd（3.7）在上式中，)(iTd也就是第i个解所表示的遍历城市的路径长度，公式表示如下：1111),(),()(jnnjjdvvdvvdiT（3.8）3.3.5选择算子在遗传算法中，往往使用最优保存方法、赌轮法和期望等对算子方法进行选择。关于赌轮选择个体法，第一步将群体中的每个个体的适应值根据相应的比例转化成选中概率iP，分解轮盘成popsize个扇区；进而形成[0,1]之间的随机数r，逐渐累加第一个个体的选中概率，如果累加概率之和iq不低于r，则需要将被累加选中概率的个体选择出来，同时将其复制到子代中。在执行遗传算法的过程中，popsize个较优的个体需要一直作为样本群体，用于后续的选择。可是，这并不适用于赌轮选择算子，这主要是因为随机操作的使用造成其具有比较大的误差，甚至遗漏掉适应度较高的个体。根据遗传算法理论，赌轮法选择算子无法对全局最优解进行收敛，和以上算法相比，最优保存方法能够对全局最优解进行收敛。在遗传算法中，“早熟”收敛现象的防止至关重要。为了防止有效基因的遗漏，需要对个体的多样性进行保证，进而能够为遗传算法的全局收敛性提供一定的保证。所以，本文引入最优选择策略保证算法能够具有全局的收敛。和其他算法相比，最优保存选择方法在进化过程中某一代的最优解不会被变异操作或者交叉所影响。可是，其同样存在着一定的缺点，最优选择策略的选择也会导致局部最优个体的遗传基因的量显著地增加，进而引起局部解的出现。因此，综合使用选择方法比较重要[5]。所以，笔者在本文中对遗传算法的选择算子进行改进，综合使用最优保存策略、赌轮选择策略，现在简要描述如下：Stepl：对pop（t）中适应度最大的1个个体进行计算，记为best，下一代的个体也就是best，也即是说，最优个体肯定会遗传到下一代。Step2：用p(k)表示个体k的轮转法选择概率，也就是1112Nip(k)f(k)/f(i),k,N（3.9）Step3：令q(0)=0，q(k)=q(1)＋q(2)+…+q(k),k=1,2,…,NStep4：出现N-1个［0,1）中的均匀分布的随机数ir，i=1,2,…,N-1，依次判断这N-1个随机数，如果1iqkrqk，那么个体k就是下一代的个体。3.3.6交叉算子算法思想：采用赌轮策略在父代中选择两个个体，采用如下操作在一个亲体中挑选一城市子序列，同时将其保存另一个亲体的城市相对次序，形成两个新的个体，接着将这两个新个体添加到子代中去。以基因片段为基础的保序在求解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交配区域后和交配区相同的城市码，终的两子串也就是：newp1=765412389，newp2＝345698721这种方法和其它方法相比在两父串相同的情况可以获得具有差别的效果，通过这种方法，能够对群体的多样性进行维持。3.3.7变异算子该算子的算法思想如下：根据赌轮策略从父代中选择两个个体，接着采用随机的方式对个体中的两个元进行选择，并对其进行交换。鉴于使用对最佳样本进行保留的选择机制，同时，还对“进化逆转”操作技术进行引用，连续多次对换的变异技术也能够为群体内个体的多样化提供了一定的保证。一般来说，变异操作出现的可能性是比较小的，变异操作的出现，需要使用随机方式对两个交换的点进行选择，并进行对换。3.3.8进化逆转操作通过使用“进化逆转”，能够对遗传算法的局部搜索能力进行改善与提高。关于局部搜索，一般是指以邻域为基础的试探搜索方法。通过对基本遗传算法操作研究发现，在可行解空间中，交叉操作具有比较大的步伐和比较宽的动作方位；在选择压力的作用下，变异操作无法起着局部搜索的作用。所以，局部搜索机制能够对遗传算法框架进行完善，进而能够形成一种局部搜索、全局搜索综合的优化搜索算法，能够对搜索效率进行提高。“逆转”广泛存在于进化与自然遗传中。在自然生物遗传中，“逆转”现象的作用还不明确。通过优化，交叉、变异等遗传操作可以优化子代趋向更优质的基因型，包括逆转、对换等在内的遗传操作就能够使后代获得更好的基因型。“逆转”在TSP问题的遗传算法中属于“变异”技术的一种，而“进化逆转”属于单方向的、连续多次的“逆转”操作，针对给定的串，“逆转”能够提高串的适应度，逆转操作就能够被执行，不是这样的话，逆转就会无效。这样的操作一直进行下去，直到逆转操作不存在结束。通过这样的操作，串就会被优化到它的局部极点，在实验室的条件下，综合使用局部爬山能力、全局搜索能力效果比较明显。可是，和其他操作相比，该逆转操作需要比较长的运行时间，因此，需要结合城市数目对逆转判断长度进行选择，进而对计算效率、质量进行优化。