一种基于模拟退火的遗传算法在受约束旅行商问题中的应用

孔令夷

（西安邮电大学管理工程学院，陕西 西安 710061）

0 引言

遗传算法（Genetic Algorithm，GA）借鉴生物进化过程，模拟自然界对生物种群的优选而获取适应度更高的个体，并将其作为最满意解［1］.GA的基本思想是：初始化种群（initialization）、适应度函数构建（Fitness Function）、基于适应度的优选与繁衍（Heredity）、选择若干子代后的最高适应度个体作为最满意解.GA的组成要素有：种群规模、染色体编码方案、交叉算子、变异算子、选择方法、终止条件.鉴于该算法的处理对象并不是问题的决策变量，而是对相关变量转换成的编码，即染色体或位串，因此它对目标问题基本上没有太多限制，对函数类型的限制也很少，这就使得该算法的智能性明显高于规范的运筹学或其他传统的优化手段，尤其是在解决复杂环境下、规模较大、非结构性、高维度问题时，更是表现出强有效性，基本上可以求出最满意解.旅行商问题（Traveling Salesman Problem，TSP）在图论领域是一个经典性问题，呈现出不确定性及多维性，具有高度的计算复杂性［2－3］，是学术界、工业界与相关服务企业长期以来需要应对的难点及重点问题.以“旅行商问题”或“TSP”作为篇名，在中国知网搜索，近10年来刊载于国内期刊的该类研究论文就高达295篇，因此，怎样更好地将当今最成功且适用性最强的智能算法——GA用于解决TSP，早已是人工智能、信息技术、工程应用、交通运输、电子计算机、经济数学、算法理论、统筹法优选法、管理科学等各类前沿领域的大量研究者们关注的焦点［4－8］.

1 受约束TSP的提出

实际的TSP还可能存在其他额外的限定条件，例如旅行商途经的某两个地点中间有天然屏障，如河流、山脉、沼泽、沙漠等，无法直达，迫使旅行商要绕道而行.这类情况下，这两个途经地点就是不联通的，此类TSP就是受约束TSP，也正是本文拟研究的对象.

2 基于模拟退火的遗传算法

针对TSP的一般性运筹方法具有诸多局限：决策变量少，过于理想化的假定使得该问题脱离实际情况，而且较为苛刻地要求函数具有某些优良的数学特性，如若不然，就可能算出大量的不可行解，无法获取真正的最优解，或者也只能求出局部最优解.显而易见，一般性运筹优化方法缺乏对复杂性TSP的解决能力，主要表现为问题描述不客观、建模不理想及寻优性较弱，更不用说受约束情形下了［9］.然而，GA的优点此时却恰恰可以被彰显无遗.首先，该算法的处理对象并不是问题的决策变量，而是对相关变量转换成的编码，即染色体或位串，因此它对TSP基本上不做太多限定.其次，GA对所求函数类型的限制也很少，无论线性或非线性、离散或连续、可微或不可微，这就使得该算法的智能性明显高于规范的运筹学或其他传统的优化手段，基本上可以求出最满意解，这又再次显示出GA在应用研究中的广泛性.第三，运筹优化法通常从初始点着手，不断迭代和调整，路径单调且出错率高，而GA突破常规，从面上群体择优，从上一代（父代）的很多染色体（个体）开始评估选择，择优后再经过交叉变异等基因遗传方式形成下一代（子代），这样就确保优良基因传承以及种群稳定性，筛掉的都是适应度较差的染色体，实现“优胜劣汰，适者生存”，经过足够多次的迭代，获取整体最满意解就会是顺理成章、水到渠成的.第四，GA对个体的选择过程，只遵循适值评判的简易准则，客观性极强，不受其他因素干扰，逼真地再现生物体在大自然中延续生存繁衍的自适应能力及品质.最后，GA采用适中的交叉率作为重要的遗传算子，既最大限度地扩充解空间，允许子代个体性态的持续改进，又能限制搜索工作量而加速计算、缩减染色体收敛时间；同样的，采用合适的变异率不但可以吸收外部的有用基因，而且保留了双亲传递的优质特性，因此，最终得出的最满意解必定有很高的可置信性，而不像传统方法必须给出确定性解，从而也说明GA具有足够的柔性和可改进性.以上优点决定了GA非常适用于解决复杂环境下、规模较大、非结构性、高维度、不连续、不可微分问题［10］，现实世界中很多问题都有这些属性，比如受约束的旅行商问题.

然而，现有GA的求解效率很大程度上受到参量选取及各种遗传算子的影响，普遍呈现早熟现象，迭代冗余问题也会频发.针对于此，研究者们对GA做了很多改造工作，起到了一定的预防和矫正作用［11－14］.而且，算法运行过程中引入确定性策略能确保种群优良基因的稳定性；同时，基于模拟退火思想引入不确定性策略，能实现种群子体的多元化保留，有效提高算法的全局寻优性［15－16］.C.Bierwirth等人通过大量算例研究，认为优先保留交叉（Precedence Preservation Crossover，PPX）方法的交叉比例适中，有助于继承上一代的优质特性，从而较好地抑制现有GA的早熟问题发生［17］.T.Murata等人进行大量数值实验研究，开发设计了平移变异（Shift Change Mutation，SCM）操作，大幅度提升进化质量，同时能缩短CPU在求解过程中的运行时间［18］.

2.1 染色体编码的方案选择

文中拟设计适合TSP的专属编码，即根据旅行商途径的全部地点的顺序，来得到识别所有个体身份信息（ID）的唯一位串，这种编码方案较为常见，具有合理性和穷举性.如此设计可以使得搜寻最优解在极为有限的解空间（即该问题所涉及的全部地点的各种排列的集合）内展开，必将大大提升算法运行速度及有效性.例如S＝（2，1，3，4，6，5，7），则意味着旅行商的行进路线是从起点2开始，分别途经地点1－3－4－6－5－7，最后返回地点2.

2.2 种群初始化

遗传算法的效能不仅受制于各类算子，也对染色体初值较为敏感［1］.性能较劣的父代群体会对紧接着的迭代过程及进化质量产生不可低估的负面影响.如果随意产生第一代群体，就无法确保其质量的优良性，也未必符合最初问题中所要求的某些地点之间的不联通条件，以此为基础不断迭代后求得的“最满意解”的可行性就会大打折扣，致使算法效率较差.因此，将现有GA优化为：在现有随机方法的基础上，混合贪心转换法以得到最初的第一代种群，从而提高其优良性［19－20］.贪心转换法就是每次都追求实现局部的优化，而未必考虑全局的系统优化.

2.3 适值函数构建

解决TSP是要求出最短的总路程，所以，适值应该与旅行商的穿越总路程成反比，令α是常量，则可得出适值

即S的适值在种群中将是很小的，甚至是最小的，按照GA的选择操作中“适者生存”的思想，这种适应度值很小的不可行染色体S必然会筛除，从而较早且较为容易地舍掉不可行解.

2.4 基于模拟退火的交叉变异操作

本算法选择PPX［17，22］及SCM［18］.PPX操作过程基于2个已有染色体串和1个相同长度的｛1，2｝随机数字串.若数字串的第i个码是1，就取第1个染色体最左侧的地点编号，放入新染色体的第i位；反之就从第2个染色体中取得，删掉现有2个染色体中已选地点，继续读取数字串其余码，直至完毕.研究发现，PPX相比映射交叉、次序交叉或循环交叉，子串能更多地保留双亲的好特性.

交叉操作后，对于新的子体接纳决策可引入确定性策略［15－16］，确保优良基因的保留及种群稳定性得以较好的延续.设S，T是两个父代个体，S1与T1是对S与T 执行交叉操作后的子代个体，即［S1，T1］＝crossover［S，T］，那么执行下述条件语句：

可见，确定性策略就是通过对新老个体的适值比较而保留适值更高的一组个体.

接着，执行SCM，即任选插入点及码位，实施平移，以产生新串.设S＝（1，5，4，3，2，6，7），插入第6位码，即地点6，插入点为第3位，就有S1＝（1，5，6，4，3，2，7）.类似于PPX，SCM 相比对换或目标导向变异，其遗传效能更高，可将上一代的优良特性丢失控制在最低限度.

为了实现种群多元化，在变异操作中引入不确定性策略，即对变异后的子体实施模拟退火算法，做出子体是否接纳的决策［15－16］.设S是父代个体，S1是对S执行变异操作后的子体，即［S1］＝mutation［S］；初始温度T足够大且逐渐降低，从而不断被更新，最终趋近于0；a略小于1，令其取值范围是［0.90，0.99］.先算出Δt＝f（S1）－f（S），若Δt＞0则接纳新子体S1作为新解；否则，也同样能以概率exp（Δt／T）接纳S1作为新解.若满足终止条件则输出当前解，终止条件设定为连续若干个子体都不能被接纳.具体而言，就是执行下述条件语句：

结合上述的确定性策略和基于模拟退火的不确定性策略，本研究的交叉变异操作就能实现对现有GA更好的优化效果，表现为追求种群稳定性与多样性的兼容、抑制种群早熟、确保向全局最优解收敛.而且，上述的算法设计适用性较强，基本上不存在局限和缺陷，可以顺利推广到TSP以外的各类NPC问题.

2.5 选择策略

根据进化论思想，选择就是保留适应能力强的个体，舍弃较差生存能力者，使得种群渐渐朝着适应于生存环境的方向发展演化.依据上文所设计的适值高低对应的概率分布进行选择，就能体现自然选择的客观规律.本算法仍采纳多见的轮赌法（roulette wheel selection），有利于全局性、可持续优化［23］.

3 算法检验与分析

使用Matlab 2012b对现有GA［1，21］与本文的模拟退火遗传算法编程，引用文献［16］的TSP算例.取值Pc＝0.2，Pm＝0.5，MaxItr＝1000，运行结果见表1、图1—2.可见，两种算法的快速寻优能力都较强，运行时间不超过2min.但是，对解进行比较，可知本文的算法更优，起到对现有GA优化的效果.现有GA处于劣势，根由在于：在初始种群生成方面产生了大量不可行解，交叉变异过程中遗传进化质量不高，也缺乏种群多样性.

而且，极差的比较也会给出一些启示：基于模拟退火的新遗传算法的个体离散性弱，收敛性强.其原因在于：其一，新算法的初始染色体质量较优，贪心法屏蔽了很多不可行个体；其二，在交叉变异操作之后实施的模拟退火算法，兼顾了种群优良基因保留以及种群子体多样性存在，基于模拟退火的子体接纳决策从子体适值入手，这对于提升子代整体遗传质量大有裨益，不但能有限地抑制染色体早熟，而且加速了向全局最优解的收敛.

表1 算法运行结果

图1 基于模拟退火的新型遗传算法的最满意解

图2 现有GA的最满意解

4 结束语

本研究集成模拟退火算法及遗传算法，应用于解决受约束TSP，更逼真地模拟了现实中各种复杂因素，研究价值较高.首先，利用随机选取与贪心法相结合的方式来生产初始种群，确保了初始种群满足不联通约束，克服了现有GA的主要缺陷；接着，选择并实施了效能更高的PPX及SCM，以确保优良基因；再者，分别接继交叉以及变异操作之后的确定性策略以及基于模拟退火算法的不确定性策略，两种策略能够确保新一代子体接纳的最优决策，实现了优良基因稳定性与种群多样性的兼容，抑制种群早熟，而且确保向全局最优解收敛；最后，给出了基于不联通约束而经特殊处理的适值函数，还采纳了经典有效的选择方法.本算法设计适用性较强，基本上不存在明显局限和缺陷，可以顺利推广到TSP以外的各类NPC问题，当然具体情况还有待今后相关研究的不断证实.

［1］雷德明，严新平.多目标智能优化算法及其应用［M］.北京：科学出版社，2009：1－10.

［2］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.

［3］吴春国.广义染色体遗传算法与迭代式最小二乘支持向量机回归算法研究［D］.长春：吉林大学数学学院，2006.

［4］YU HONG，YANG DACHUN.An incremental rule acquisition algorithm based on rough set［J］.The Journal of China Universities of Posts and Telecommunications，2005，12（1）：47252.

［5］贺毅朝，寇应展，陈致明.求解多选择背包问题的改进差分演化算法［J］.小型微型计算机系统，2007，（9）：1682－1685.

［6］韩伟一，王铮.负权最短路问题的新算法［J］.运筹学学报，2007，11（1）：111－120.

［7］黄永青，梁昌勇，张祥德，等.一种小种群自适应遗传算法研究［J］.系统工程理论与实践，2005，25（11）：92－97.

［8］郏宣耀，王芳.一种改进的小生境遗传算法［J］.重庆邮电学院学报：自然科学版，2005，17（16）：721－723.

［9］BHATIA A K，BASU S K.Tackling 0／1knapsack problem with gene induction［J］.Soft Computing，2003，8（1）：1－9.

［10］ZHAO X C，Gao X S.Affinity genetic algorithm［J］.Journal of Heuristics，2007，13（2）：133－150.

［11］CHENG R，GEN M，TSUJIMURA Y.A tutorial survey of Job－shop scheduling problems using genetic algorithms Part II：hybrid genetic search strategies［J］.Computers ＆Industrial Engineering，1999，36（2）：343－364.

［12］王涛，付宜利.一种改进的遗传算法在车间调度中的应用［J］.计算机集成制造系统，2002，8（5）：392－420.

［13］张超勇，饶运清，李培根，等.求解作业车间调度问题的一种改进遗传算法［J］.计算机集成制造系统，2004，10（8）：966－970.

［14］张国辉，高亮，李培根.基于遗传规划的作业车间调度算法研究［J］.控制与决策，2008，23（8）：924－928.

［15］赵新超，韩宇，艾文宝.求解背包问题的一种改进遗传算法［J］.计算机工程与应用，2011，47（24）：34－36.

［16］康立山，谢云，尤矢勇，等.模拟退火算法［M］.北京：科学出版社，1994：150－151.

［17］BIERWIRTH 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：Springer，1996：310－318.

［18］MURATA T，ISHIBUCHI H，TANAKA H.Genetic algorithms for flowshop scheduling problem［J］.Computers ＆Industrial Engineering，1996，30（4）：1061－1071.

［19］贺毅朝，刘坤起，张翠军，等.求解背包问题的贪心遗传算法及其应用［J］.计算机工程与设计，2007，28（11）：2655－2657.

［20］贺毅朝，刘建芹，曲文龙，等.求解广义背包问题的贪心 DS＿BPSO算法［J］.计算机应用与软件，2008，25（4）：230－232.

［21］梁艳春，吴春国，时小虎，等.群智能优化算法理论与应用［M］.北京：科学出版社，2009：34－43.

［22］晏鹏宇，杨乃定，车阿大.自动化制造单元最小完工时间调度问题的混合启发式算法［J］.计算机集成制造系统，2010，16（4）：847－854.

［23］晏鹏宇，车阿大，李鹏，等.具有柔性加工时间的机器人制造单元调度问题改进遗传算法［J］.计算机集成制造系统，2010，16（2）：404－410.