1、基于混合遗传算法的车辆路径问题摘 要：遗传算法可以很好的解决路径选择问题，但简单的遗传算法存在过早收敛问题。在自然界中远亲交配具有更好的遗传优势，本文据此理论改进车辆路径选择问题中的遗传算法，提高求解性能。 关键词：混合遗传算法；车辆路径选择，远亲交叉策略 中图分类号：U27 文献标识码：A 遗传算法简称 GA(Genetic Algorithm)是一种模拟自然界中遗传和选择机制的寻找最优解的方法。他的基本原理源自达尔文的生物进化论和盂德尔的基因学说。遗传算法模拟自然界的遗传，变异和进化法则，逐步修订解决问题的方案使之接近完美。 遗传算法的优势在于将搜索过程作用在编码后的字符串上不直接作用在优
2、化问题的具体变量上，这样可以绕过复杂的数学推演而采用最直接的方式在有限的结果集中搜索更优的结果。遗传算法通过设定一个初始种群，即一个预设的结果。并对这个初始种群进行基因突变和杂交，留下好的基因，改变不好的基因，使种群不停的进化，最后得到一组最优的或趋进于最优的结果，给人更大的选择余地。遗传算法有很好的易修改性和可并行性，在处理大规模复杂问题上更有优势。 但普通的遗传算法存在“早熟”问题，即容易收敛于局部最优解，在自然界中远亲交配具有更好的遗传优势，本文据此理论改进车辆路径选择问题中的遗传算法，并以有车载限制单配中心 VRP 的求解加以说明。这种交叉策略虽然使遗传算法的收敛速度稍有减缓，但使算法
3、具有很好的求解性能。具体步骤如下： (1)混合遗传算法的编码规则 应用遗传算法求解的首要问题是对所求问题解的编码。一个解的编码称为一个染色体，组成编码的元素称为基因。混合遗传算法采用路径编码方法。每个染色体由区间1,m+n-1中互不相同的自然数序列构成，其中 n 为客户数目，m 为运输车数量，前面 1n 为客户编号，n+1n+m-1 表示配送中心。例如，若有 3 辆运输车和 12 个客户，则一个染色体为2,1,3,13,5,4,6,10,14,8,7,9,11,12，其中 13，14 表示配送中心以区分开 3 辆车所运输的客户编组。三辆车的配送路径分别为:第一辆车:配送中心21 3配送中心;第
4、二辆车:配送中心54610 一配送中心;第三辆车:配送中心8 7 911 12配送中心。 (2)客户编号 由于车辆行驶路径的迂回将大大增加目标函数式的值，为减少迂回造成行驶路径的增加，混合遗传算法将根据客户的位置对客户按方向编号:首先任意取一个客户并将其编号为 1，然后以配送中心为极点、以配送中心和该客户的连线为极轴将所有客户的平面坐标转化成极坐标，最后以各客户的极角大小对客户依次进行编号。基于客户的编号，混合遗传算法将对车辆的行驶方向进行优化，从而尽量使车辆按一定的方向行驶。 (3)构造个体产生初始种群 由于初始种群的多样性将影响遗传算法的求解性能，因此，为了使初始种群具有较好的多样性，混合
5、遗传算法采用以下 3 种方式依次产生一部分个体来构成初始种群(其中 K 为种群大小)。它们之间没有任何联系，可以看作是远亲关系。 首先分别以每个客户为起始点，按客户编号顺序即极角顺序遍历一周，在遍历所得的客户序列中，按约束条件把表示配送中心的基因(即n+1，n+m-1)插入到序列中，构成一个个体。这样可以产生 n 个个体，为子种群一。 然后重复(K-n)/2 次以下操作，产生(K-n)/2 个个体组成子种群二:随机产生 n 个区间1,n上互不重复的自然数序列，然后按约束式把n+1，-n+m-1 插入到序列中，构成一个个体。若该个体满足所有约束，则该个体为有效个体，否则为无效个体，重新产生该个体
6、。 最后使用贪心算法产生剩下的(K-n)/2 个个体，为子种群三。即以配送中心为起点，选择一个距其近、没有车辆提供服务且将其加入路径后约束式能满足的客户加入路径，然后以该客户为起点继续以上操作。若以上客户不存在，且还有未加个体的客户，则插入配送中心，并以配送中心为起点重复以上操作。若所有客户均已加入个体，则一个个体构造完成。 (4)适应度函数。 本文研究的单配送中心 VRP 问题的目标函数是关于最短路径的，一般来说，若目标函数为最小问题，适应度函数可以建立为: （11） 式中 Cmax 为 f(x)的最大估值。 (5)交叉、选择与变异。 在交叉个体的选择上，简单遗传算法通常直接采用随机选择两个
7、个体进行交叉操作。这种交叉操作很大程度上导致了早熟现象的发生。混合遗传算法基本思想是:在选择交叉个体时，要求两个个体之间有一定的距离以保持种群的多样性，本例中以上述 3 个子种群相互交叉。选定两个交叉位置将每个个体分成三个部分，首先交换两个个体的中间部分;然后分别在第一部分和第三部分删除己经在中间部分出现的基因;最后，从另一个个体的第一个基因位置开始，依次选取未在该个体中出现的基因插入到该个体的第一部分末尾和第三部分的开头，以保持个体的第一部分和第二部分长度不变且每个客户在个体中只出现一次。例如:对个体324 | 5768| 19 和 514 | 8372 | 96(“|”表示交叉位置 )，则
8、交叉后形成的两个个体分别是 456 | 5372 | 19 和 143 | 5765 |29。 以上交叉操作中，交叉个体的选择策略可以很好地解决简单遗传算法的早熟问题。但是，它会使种群进化速度减慢，导致算法执行时间增加。为了解决这一问题，混合遗传算法采用优良个体保存策略，即在产生下一代种群时，将上一代种群中一定数量的较优个体直接复制到下一代种群中。由于在种群进化早期，种群的多样性较好，可以复制较多的优良个体到下一代种群中，而到种群进化后期，种群逐渐收敛，复制较多的优良个体会使种群快速趋向单一化，因此可以复制较少的优良种群到下一代种群中。为此，混合遗传算法中定义的优良个体数函数，如(3-2 )式
9、所示。 （12） 其中:P 为初始设定的优良个体占种群中总个体数的百分比，K 为种群大小，i 为进化代数。第 0 代向第 1 代种群中复制 PK 个体。当lni1 时，P K/lni小于 PK，因此，随着进化代数逐渐增加，lni逐渐减小，直到每代仅复制一个优良个体到下一代种群。 变异操作用以调换同一个个体的两个不同位置的基因。混合遗传算法中，首先根据变异概率 pv 和种群大小 K 产生需要进行变异操作的个体个数，然后对于随机选定的每个个体调换两个位置的基因。例如，一个个体为 456837219,随机产生的两个位置为 3 和 6，则变异的结果产生的新个体为 4578362190 (6)优化策略。基于行驶方向的优化策略的基本思想是:由于车辆迂回行驶会增加路径长度，可以通过使车辆按一定方向行驶来减少车辆迂回，从而减少车辆路径长度。因此，本优化使车辆在两个客户之间按一定方向行驶，并按车辆行驶方向依次为两个客户之间的客户提供服务。本优化在一个个体的两个相邻基因所对应的客户间，按极角顺序插入位于这两个客户间的客户，并从其它位置删除表示相应客户的基因。
