混沌遗传算法优化公路运输路径

孔令夷

(西安邮电大学管理工程学院，西安 710061)

1 引 言

公路运输路径问题在图论中具有代表性，已被证明是高维非线性完全问题(NPC，Non-deterministic Polynomial Complete Problem)［1］，具有高度的计算复杂性，多年来都是理论界与企业界面临的难题.如何将智能优化算法中经典的遗传算法、改进遗传算法应用于这一难题的全局优化求解，也成为了众多学者研究的对象.

求解公路运输路径问题的传统方法存在明显的缺陷:设计变量少，与现实不相符;假设较多，对目标函数有可微或连续的诸多限制，否则，在求解中必然会产生非可行解，难以得到全局最优解，或者也只能求出局部最优解.显而易见，传统求解方法不能很好地模拟实际问题的各种复杂情境，尤其是存在非连通图约束的情况下，运筹规划等传统求解方法更是难以应对，无法客观准确地把实际问题转化为数学模型.1967年，Bagley首次提出了遗传算法(Genetic Algorithm，GA)，相比传统的运筹规划方法应用更加广泛，实用价值更高，在处理大多数科学与工程复杂问题时显得游刃有余，几乎都能找到满意解.这主要源于以下四点:第一，GA并不是直接处理运输路径中的显性变量，而是对变量编码，编码之后可以任意组合成串，即染色体，这才是GA后续处理的对象，可见其对运输路径优化等复杂问题几乎没有什么限制;其次，在求最优解的过程中，GA对问题的限制不多，对目标函数的数学特性要求也不严格，能够接受各种类型的目标函数，线性或非线性，离散或连续，可微或不可微，这又再次体现了它的普适性;第三，传统求解方法往往是从一个初始解开始，经过多次迭代的过程求得最优解，求解线路单一，而GA不是沿着一条线，而是基于面上的一代种群求解，从上一代(父代)的很多染色体(个体)开始评估选择，择优后再经过交叉变异等基因遗传方式形成下一代(子代)，这样就容易保留更多优良的个体，而淘汰较劣的个体，实现“优胜劣汰，适者生存”，几代遗传之后就能基本保证得到全局最优解;第四，GA的择优去劣过程，只以个体的适应度值作为判断，不需要补充更多信息，操作简便易行;最后，GA基于概率论的知识而进行遗传操作，求出具有较高可信度的最优解，不排除进一步的改善，而不像传统方法必须给出确定性解，从而也确保了GA的灵活性和可改进性［2］.

众多学者尝试应用GA优化公路运输路径，然而，传统遗传算法(TraditionalGenetic Algorithm，TGA)严重依赖于参数设置和交叉变异算子，存在早熟收敛缺陷［3，4］.为此，学者们设计了各种改进遗传算法.黄永青等设计一种小种群自适应遗传算法，平衡了探测和开发操作，提升了寻优能力［5］.陶林波在保留自适应性的前提下，引入与种群分布相关联的动态交叉、变异算子，实现动态种群中寻找最优解［6］.李锋等研究了动态流量下的路径求解，引入非平稳随机因子，设计出仿真算法，并用算例检验了效果［7］.周辉仁等设计了递阶染色体编码和矩阵解码法［8］.王美华等开发了二进制和整数混合的染色体编码方案，优化了交叉和变异算子，并验证了新算法的有效性［9］.韩丽霞等开发了新的编码及解码规则，引进杂交算子，运用局部搜索加强杂交算子，并验证了其有效性［10］.朱云飞等引入贪婪的复合变异算子、隔代爬山法算子，算例检验了有效性［11］.汪民乐等考虑子代结构及适应度，基于FS理论改进种群成熟度指标，提出早熟预防策略［12］.郏宣耀等基于 Niche思想改进 TGA，既保留子代多样性及优良性，同时提高了求解的可靠性［13］.贺毅朝等研究了TGA中传统贪心变换的局限性，对其改进后与GA结合，得到了更理想的贪心遗传算法，并证实了新算法的优势［14］.田建立等引入混沌搜索技术，以加强GA的寻优能力［15］.Bierwirth等在对各类交叉操作实验对比的基础上，提出优先保留交叉法(Precedence Preservation Crossover，PPX)，在很大程度上克服了TGA的常见缺陷［16］.Murata等通过大量仿真实验研究，提出平移变异(Shift Change Mutation，SCM)操作，并引入局部邻域搜索，使得GA被改进后能在确保子代遗传质量的前提下加快收敛［17］.

以上改进都局限于GA的某个环节，达不到全局优化;或者应用于特定情形，比如小种群、动态或距离对称条件.为此，拟提出全过程改进的混沌遗传算法(Chaos Genetic Algorithm，CGA):综合随机法与贪心法生成初始染色体种群;基于遍历城市次序编码;执行交叉变异、局部邻域及混沌搜索操作;运用赌轮法作出选择，并给出最优解可行判据.

2 问题描述

现实中的公路运输路径问题一般都会有各种约束或限制，比如非连通图就是一个典型的例子，即公路运输路径中要经过的某些目的地(比如城市)之间存在障碍物，比如山川、农田等，不能直接通达，只有绕道而行，通过其他地点而间接到达.这类问题中经过的所有地点将连成一个非连通图，如图1所示的城市1和城市2之间.

图1 非连通图Fig.1 Unconnected graph

本研究的目的就是寻找最短路径，将公路运输成本降到最低.该路径经过所有N个城市，除了起点以外，都要经过且只经过1次，最终回到起点，这也比较符合实际公路运输遍历所有城市实现物流量最大化的实际情形.设有N个城市的集合C=｛c1，c2，…，cN｝，每两个城市之间的距离为 d(ci，cj)∈R+，其中，ci，cj∈C(1≤i，j≤N).

求使目标函数

最小的路径序列｛cП(1)，cП(2)，…，cП(N)｝，其中 П(1)，П(2)，…，П(N)是1，2，…，N 的全排列.

3 混沌遗传算法设计

3.1 编码方式

本研究的编码采用基于公路运输路径需要遍历的所有城市的次序，这也是最常用的编码方式，以有限的城市数量作为搜索范围，有助于提高搜索效率.例如设S=(1，5，4，3，2，6，7)，就可以看成是从城市1 出发，依次经过城市 5、4、3、2、6、7，最终回到起点的公路运输路径.

3.2 初始种群生成

初始种群的质量对后续的优化求解具有关键作用.若按随机方式产生初始种群，难以保证其满足非连通约束，也就容易产生很多非可行解，从而降低了TGA的效率.拟对其改进为综合随机法与贪心法来产生初始染色体种群，从而提高其优良性.

3.3 交叉变异操作

基于城市次序的编码方式，基因存在先后关系.为了不破坏这种关系，拟选用PPX和SCM操作.PPX操作过程是:随机产生两个父代个体，并产生一个等长的{1，2}随机串;扫描随机串，如果第k位是1，则提取第一个父代染色体最左边的城市号作为子代第k位，如果第k位是2，则提取第二个父代染色体最左边的城市号，然后删除两个父代中的该城市号，重复以上操作，直到随机串被扫描完.由上可见，PPX与映射交叉、次序交叉或循环交叉相比，能够更好地继承父代优良基因.

SCM操作是指随机选择插入码和插入点，进行平移操作.比如S=(1，5，4，3，2，6，7)，若随机选取插入码为6，插入点为5与4之间，则S’=(1，5，6，4，3，2，7)，SCM 与对换变异、目标导向变异等相比，更好地保持了基因之间的先后次序，继承了父代的优良性.

3.4 局部邻域搜索及混沌搜索

拟引入局部邻域搜索，加快算法收敛，缩短求解时间.以交叉变异操作产生的子代个体为基体，对每个基因采用右邻基因交换的方法产生新的局部邻域子代个体.例如 S’=(1，5，6，4，3，2，7)，将基因2与其右邻的基因7交换，就能生成一个新个体 S’’=(1，5，6，4，3，7，2).因此，局部邻域搜索能产生N－1个局部邻域子代个体，从中选择具有最大适应度的邻域个体与基体再做比较，以适应度大者为更新后的子代基体.

接着，执行基于幂函数载波的混沌搜索，操作过程如下［15］:

(1)利用混沌向量对初始值的敏感性，对式(2)赋 m 个初始值 zk，l(k=1，2，…，m;l=0)，以此得出m个混沌向量.

初始值不可以是:0，0.25，0.5，0.75，1.

(2)将［0，1］作m 等分，并对分区间编号:1－m.

(3)运用幂函数载波理论，按照z'l=zvl把混沌变量zl载波成新混沌变量z'l

v是分段常函数:

若没有达到条件，则依据式(2)继续迭代生成m个混沌向量，令l=l+1，重新执行第3步.

3.5 选择操作及适应度函数建立

选择操作是对生物进化论的“适者生存”思想的体现，越优良的个体具有越大的概率进入下一代，种群性能就会随着进化而不断优化.采用轮盘赌法(Roulette Wheel Selection)，保证将种群中最优个体随机替换掉下一代的个体，这对于不断寻优具有关键作用.

适应度函数是评价个体优劣的指标，由于本文研究的路径问题是最小化路径长度，因此，适应度函数取线性定标，如式(3)所示.

式中 α为预先设定的常数;N为城市的数目;M为包含所有城市的最小正方形的边长;Td就是根据式(1)计算得出的实际路径长度，也就是目标和数值.

如果按TGA求解该问题，势必会产生大量非可行解，耗费更多计算程序运行时间与硬件资源，降低了求解效率.拟作如下特殊处理:

记dmax=，按照非连通图约束，设城市cp，cq之间存在障碍物，无法直接到达，则对两者之间的距离进行特殊处理，令d(cp，cq)=N·dmax+1.

解决这一问题，通过对非连通城市间距离的特殊处理，就能保证GA的优良特性不会受到影响，而且可以更容易地找到该问题的可行解.如上文所述，城市cp，cq之间存在障碍物，假设个体S包含基因片段(…，cp，cq，…)或者(…，cq，cp，…)，则有式(4)成立:

因此，在作出了特殊处理后，若个体S中存在非连通城市相邻，则必会出现其适应度值小于，按照GA的选择操作中“适者生存”思想，这些适应度值很小的非可行解必然会随着进化的历程而逐渐被淘汰，因此就排除了非连通城市相邻的情况.反之，若有式(5)成立，则个体S必定为可行解，用反证法可证出，此处从略.

3.6 算法步骤

步骤1 初始化.设置预定常数、最大迭代次数、交叉概率Pc、变异概率Pm等参数.

步骤2 采用遍历城市排序的编码方法，利用随机选取与贪心法相结合的方式来生产初始种群.

While(迭代次数≤最大迭代次数)do

步骤3 按Pc概率执行交叉操作，按Pm概率执行变异操作，再执行局部邻域搜索以及混沌搜索.

步骤4 根据f(S)，基于轮盘赌法执行选择操作，确定子代个体，保证优良染色体能够保留下来.

步骤5 求得最大适应度值的个体作为最终解.

步骤6 检验该解的适应度值是否满足式(5)，如果满足，则可行，否则该解为非可行解.

End While

4 算法检验与分析

使用Matlab R2009a分别对文中CGA和TGA进行编程，在2.53GHz CPU，2.0GB内存的PC上运行，选取我国31个中心城市的地理数据用于算法检验［18］.设 Pc=0.2，Pm=0.5，MaxItr=1000，结果见表1.可见，两种算法的快速寻优能力都较强，运行时间不超过2 min.但是，在求解方面，CGA的最满意值为14268 km(如图2所示)，明显优于TGA的15387 km(如图3所示)，改进程度为7.3%，说明CGA取得了相比TGA更优的解，达到了算法改进的目的.究其原因，主要是由于TGA在初始种群生成方面产生了大量不可行解和在交叉变异过程中缺失局部邻域择优能力.也就是说，正是由于CGA引入局部邻域搜索以及混沌搜索操作，所以确保了子代个体快速持续收敛.

表1 两种算法的检验结果Table.1 Check results of TGA and CGA

图2 CGA的最满意值Fig.2 The most satisfactory solution of CGA

对比两种算法的极差发现，CGA的种群离散程度较小，集聚性较高，收敛性更好.这源于:其一，CGA的初始种群质量优于TGA，其可行染色体比例较高，避免了初期大量不满意染色体的生成;其二，CGA的局部搜索及混沌搜索操作提高了子代个体的收敛性.总之，CGA的求解能力更强，比TGA更高效.

5 研究结论

本研究将GA应用于非连通图公路运输路径问题，更逼真地模拟了现实中各种复杂因素，研究价值较高.首先，利用随机选取与贪心法相结合的方式来产生初始种群，确保了初始种群满足非连通图约束，克服了TGA在随机方式下生成大量非可行解的缺陷.接着执行交叉变异操作、局部邻域搜索及混沌搜索操作，以确保优良基因，加速染色体收敛.最后，给出了经特殊处理的适值函数、经典的选择方法以及解的可行性判据.今后的研究可以着眼于求出的解为非可行解条件下初始种群的再调整，同时设计在更短时间内收敛的CGA.

［1］梁艳春，吴春国，时小虎，等.群智能优化算法理论与应用［M］.北京:科学出版社，2009.［LIANG Y C，WU C G，SHI X H，et al.Group intelligent optimization algorithm theory and application［M］.Beijing:Science press，2009.］

［2］ZHAO X C，Gao X S.Affinity genetic algorithm［J］.Journal of Heuristics，2007，13(2):133-150.

［3］YANG J H，Wu C G，Lee H P et al.Solving traveling salesman problems using generalized chromosome genetic algorithm［J］.Progress in Natural Science，2008，18(7):887-892.

［4］Bhatia A K，Basu S K.Tackling 0/1 knapsack problem with gene induction［J］.Soft Computing，2003，8(1):1-9.

［5］黄永青，梁昌勇，张祥德，等.一种小种群自适应遗传算法研究［J］.系统工程理论与实践，2005，25(11):92-97.［HUANG Y Q，LIANG C Y，ZHANG X D，et al.Research on adaptive genetic algorithm with small population［J］.Systems Engineering-Theory＆ Practice，2005，25(11):92-97.］

［6］陶林波，沈建京，韩强.一种解决早熟收敛的自适应遗传算法设计［J］.微计算机信息，2005，22(12):268-270.［TAO L B，SHEN J J，HAN Q.An algorithm design for solving premature convergence of adaptive genetic algorithm ［J］. Microcomputer Information，2005，22(12):268-270.］

［7］李锋，魏莹.基于仿真的遗传算法求解动态旅行商问题［J］.系统管理学报，2009，18(5):591-595.［LI F，WEI Y.A simulation-based genetic algorithm for dynamic traveling salesman problem ［J］.Journal of Systems ＆ Management，2009，18(5):591-595.］

［8］周辉仁，唐万生，牛犇.基于递阶遗传算法的多旅行商问题优化［J］.计算机应用研究，2009，26(10):3754-3757.［ZHOU H R，TANG W S，NIU B.Optimization of multiple traveling salesman problem based on hierarchical genetic algorithm ［J］.Application Research of Computers，2009，26(10):3754-3757.］

［9］王美华，田绪红，廖鸿翔.求解广义旅行商问题的混合染色体遗传算法［J］.计算机工程与应用，2009，45(27):59-61.［WANG M H，TIAN X H，LIAO H X.Mixed chromosomes genetic algorithm for solving the generalized traveling salesman problem ［J］.Computer Engineering and Applications，2009，45(27):59-61.］

［10］韩丽霞，王宇平.解旅行商问题的一个新的遗传算法［J］.系统工程理论与实践，2007，(12):145-150.［HAN L X，WANG Y P.A novel genetic algorithm for traveling salesman problem ［J］. Systems Engineering-Theory ＆ Practice， 2007，(12):145-150.］

［11］朱云飞，蔡自兴，袁琦钊，等.求解多目标旅行商问题的混合遗传算法［J］.计算机工程与应用，2011，47(7):52-56.［ZHU Y F，CAI Z X，YUAN Q Z，et al.Hybrid genetic algorithm for multiple-objective TSP［J］.Computer Engineering and Applications，2011，47(7):52-56.］

［12］汪民乐，高晓光，刘刚.遗传算法早熟问题的定量分析及其预防策略［J］.系统工程与电子技术，2006，28(8):1249-1251.［WANG M L，GAO X G，LIU G.Quantitative analysis and prevention of genetic algorithm premature convergence［J］. Systems Engineering and Electronics， 2006， 28(8):1249-1251.］

［13］ 郏宣耀，王芳.一种改进的小生境遗传算法［J］.重庆邮电学院学报(自然科学版)，2005，17(16):721-723.［JIA X Y，WANG F.Improved niching genetic algorithm［J］.Journal of Chongqing University of Posts and Telecommunications(Natural Science)，2005，17(16):721-723.］

［14］贺毅朝，刘坤起，张翠军，等.求解背包问题的贪心遗传算法及其应用［J］.计算机工程与设计，2007，28(11):2655-2657［HE Y C，LIU K Q，ZHANG C J，et al.Greedy genetic algorithm for solving knapsack problems and its applications［J］. Computer Engineering and Design， 2007， 28 (11):2655-2657.］

［15］田建立，晁学鹏.求解0-1背包问题的混沌遗传算法［J］.计算机应用研究，2011，28(8):2838 －2839.［TIAN J L， CHAO X P. Novel chaos genetic algorithm for solving 0-1 knapsack problem ［J］.Application Research of Computers，2011，28(8):2838-2839.］

［16］Bievwirth C，Mattfeld D，Kopfer H.On permutation representations for scheduling problems［C］//Proceedings of the 4th International Conference on Parallel Problem Solving from Nature. Berlin，Germany:Springer，1996:310-318.

［17］Murata T，Ishibuchi H，Tanaka H.Genetic algorithms for flowshop scheduling problem［J］.Computers＆Industrial Engineering，1996，30(4):1061-1071.

［18］ 康立山，谢云，尤矢勇，等.模拟退火算法［M］.北京:科学出版社，1994:150-151.［KANG L S，XIE Y，YOU S Y et al.Simulated Annealing Algorithm［M］.Beijing:Science Press，1994:150-151.］