一种混合遗传模拟退火算法及其应用
第 4 卷 第 2 期
2005 年 4 月
广州大学学报(自然科学版)
Journal of Guangzhou University(Natural Science Edition)
Vol. 4 No. 2
Apr. 2005
收稿日期 : 2004 - 10 - 30 ; 修回日期 : 2004 - 12 - 14
作者简介 : 刘怀亮(1976 - ) ,男 ,硕士 ,主要从事分布式人工智能、数据挖掘、数据库的研究.
文章编号 :167124229(2005) 0220141205
一种混合遗传模拟退火算法及其应用
刘怀亮 , 刘 淼
(广州大学 信息与机电工程学院 , 广东 广州 510405)
摘 要 : 分析了遗传算法和模拟退火算法的优缺点 ,提出了一种混合遗传模拟退火算法 ,对其进行优化 ,并将
该算法应用于 TSP 问题的求解之中. 理论分析和实验结果表明了这种混合遗传模拟退火算法优于普通的遗传
算法和模拟退火算法.
关键词 : 模拟退火算法 ;遗传算法 ;TSP 问题
中图分类号 : TP 301. 6 文献标识码 : A
0 引 言
旅行商问题 (Traveling Salesman Problem ,简记
为 TSP) 是一种典型组合优化问题 (Combinatorial
Optimization Problem) ,并且也是一种 NP 完全问题
(Nondeterministic Polynomial Complete Problem) . TSP
问题可以描述为 :有 n 个城市 ,它们相互之间距离
是已知的 ,有一商人从某一城市出发旅行完所有
的 n 个城市 ,要求每一个城市只能经过一次 ,且最
后回到出发点 ,求该旅行商所经过的最短路程和
相应路线.
TSP 问题研究的重要性在于 :TSP 问题是许多
最难 NP 完全问题中的一个 ,所有 NP 完全问题在
数学上都等价于 TSP 问题 ,它的研究对于科学和
工程技术领域中大量组合优化问题 ,尤其是其中
的 NP 完全问题的求解有着极为重要的价值.
NP 完全问题求解时间随问题规模呈指数级
增长 ,当规模稍大时就会因时间限制而失去可行
性 (Feasibility) . TSP 问题求解也是如此 ,例如 ,对
于 n 个城市的 TSP ,存在可能的路径数为 ( n - 1) !
2
条 ,要从 ( n - 1) !
2 个可能解中找出最优者 ,需要进
行 ( n - 1) !
2 - 1 次比较. 当 n 较大时 ,其数量是惊
人的. 若用运算速度为 1G FLOPS 次的 Cray Ⅱ型计
算机进行搜索 , n = 7 时 ,需要01000 025秒 , n = 15
时需要 118 小时 , n = 20 时猛增到 350 年 , n = 50
时则需要 5 ×1048年 ! 显然 ,如此求 TSP 问题的方
法是不可行的.
最初求 TSP 问题的近似解是采用一些局部搜
索方法 ,如最近邻法、最近插入法等 ,但这些算法
在最坏情况下得到的解很不理想. 由于这一类问
题的复杂性 ,又有人提出了一些优化技术 ,如模拟
退火[1] 、模拟进化[2 ,3]和神经计算[4]等. 但这些算
法或因过于注意个别问题的特征而缺乏通用性 ,
或因所得解强烈地依赖初始解的选取而缺乏实用
性. 遗传算法和模拟退火算法都是起因于大自然
的某些规律 ,考虑到两种算法的本质特点 ,本文将
这两种算法相互结合 ,提出了一种混合遗传模拟
退火算法 ,并将其用于 TSP 问题的求解.
1 遗传算法
遗传 算 法 ( Genetic Algorithms , 简 称 GA) 是
J1Holland 于 1975 年受生物进化论的启发而提出
的 ,它是模拟生物在自然环境中的遗传和进化过
程而形成的一种自适应全局优化概率搜索法[5] .
遗传算法模拟自然进化中“优胜劣汰、适者生存”
的原理进行自学习和寻优 ,它将问题的求解通过
编码表示成染色体 ,由计算机随机产生一群染色
体 ,每个染色体在问题的“环境”中对应着其本身
的适应度 ,根据适者生存的原则 ,从中挑选适应度
高的个体进行杂交、变异等基因操作产生出新一
代个体 ,不断迭代进化最终收敛到适应度最高的
个体上 ,此个体经过解码后就是问题的最优解. 遗
传算法求解问题的具体实现过程为 :用某种编码
技术作用于输入量以形成数串 ,模拟由数串组成
的群体的进化过程. 通过复制、交叉、变异过程有
组织地 ,然而又是随机地由信息交换来重新组合
那些适应性好的数串 ,在每一代中 ,利用上一代数
串结构中适应性好的位和段来生成一个新的数
串 ,并偶尔也在数串结构中尝试用新的位和段来
替代原来的部分.
遗传算法用简单的编码技术和繁殖机制来表
现复杂的现象 ,不受搜索空间的限制性假设的约
束 ,不必要求诸如连续性、导数存在和单峰的假
设 ,并且具有内在的并行性 ,收敛速度快[6] ,所以
比较适合用来解决非常困难的寻优问题. 遗传算
法具有良好的全局搜索能力 ,可以快速地将解空
间中的全体解搜索出 ,而不会陷入局部最优解的
快速下降陷阱. 利用它的内在并行性 ,可以方便地
进行分布式计算 ,加快求解速度. 但是遗传算法的
局部搜索能力较差 ,这就导致了单纯的遗传算法
比较费时.
2 模拟退火算法
模拟退火算法 (Simulated Annealing ,简称 SA)
又称为模拟冷却法、统计冷却法、Monte2Carlo 退火
法、随机松弛法和概率爬山法等. 模拟退火算法是
一种 新 的 统 计 优 化 方 法 , 其 思 想 最 早 是 由
N1Metropolis 等人借鉴统计力学中物质退火方法而
提出的. 1983 年 Kirkpatrick 等人开展了一些富有
成效的工作 ,成功地将该思想引入组合优化理论.
模拟退火算法源于对固体退火过程的模拟 ,采用
Meteropolis 接受准则 ,并用一组称为冷却进度表的
参数控制算法进程 ,使算法在多项式时间里给出
一个近似最优解.
模拟退火算法特别适合于解决大型组合优化
问题 ,算法的核心在于模拟热力学中液体的冻结
与结晶或金属溶液的冷却与退火过程. 它能够以
随机搜索技术从概率的意义上找出目标函数的全
局最小点. 模拟退火算法可以用马尔柯夫链的遍
历理论来给它以数学上的描述. 在搜索最优解的
过程中 ,模拟退火算法除了可以接受优化解外 ,还
用一个随机接受准则 (Metropolis 准则) 有限度地接
受恶化解(ill2conditioned) ,并且接受恶化解的概率
慢慢趋向于零 ,使得算法执行过程中即便落入局
部最优的陷阱中 ,理论上经过足够长的时间后也
可跳出来从而收敛到全局最优解 ,这是模拟退火
算法的最大特点. 但是由于模拟退火算法对整个
搜索空间的状况了解不多 ,不便于使搜索过程进
入最有希望的搜索区域 ,从而使得模拟退火算法
的运算效率不高.
3 遗传算法与模拟退火算法的混合
策略
311 遗传算法与模拟退火算法分析
仔细分析遗传算法和模拟退火算法的基本原
理可以发现 :遗传算法和模拟退火算法各自都有
很多的优点 ,但也存在着很多不足之处 ,两种优化
算法有很强的互补性.
遗传算法是模拟生物遗传和进化过程中选
择、交叉、变异机理而形成的一种自适应全局优化
概率搜索算法 ,遗传算法最为严重的缺陷是“过早
收敛”问题. 所谓“过早收敛”是指在搜索的初期 ,
由于优良个体急剧增加使种群失去多样性 ,从而
造成程序陷入局部 ,达不到全局最优解的现象.
模拟退火算法是基于金属退火的机理而建立
起的一种全局最优化方法 ,虽然它能够以随机搜
索技术从概率意义上找出目标函数的全局最优
点 ,但它本身也有很多缺陷. 模拟退火算法的不足
之处主要是 :尽管理论上只要计算时间足够长 ,模
拟退火法就可以保证以概率 110 收敛于全局最优
点 ,但是在实际算法的实现过程中 ,由于计算速度
和时间的限制 ,在优化效果和计算时间之间存在
矛盾 ,因而难以保证计算结果为全局最优点 ,优化
效果不甚理想. 为得到一个好的近似最优解 ,需要
进行反复迭代运算 ,当问题的规模不可避免地增
大时 ,缺乏可行的解决途径.
遗传算法和模拟退火算法的直接互补性体现
在 :遗传算法把握总体的能力较强 ,但局部搜索能
241 广州大学学报(自然科学版) 第 4 卷
力较差 ;模拟退火算法具有较强的局部搜索能力 ;
因此可以将遗传算法和模拟退火算法相互结合 ,
取长补短. 为了克服遗传算法和模拟退火算法各
自的缺点 ,发挥它们的优势 ,本文将遗传算法和模
拟退火算法混合起来 ,设计了混合遗传模拟退火
算法.
312 混合遗传模拟退火算法
混合遗传模拟退火算法的基本思想是将遗传
算法与模拟退火算法相结合而构成的一种优化算
法. 与基本遗传算法的总体运行过程相类似 ,遗传
模拟退火算法也是从一组随机产生的初始解 (初
始群体) 开始全局最优解的搜索过程 ,它先通过选
择、交叉、变异等遗传操作来产生一组新的个体 ,
然后再独立地对所产生出的各个个体进行模拟退
火过程 ,以其结果作为下一代群体中的个体. 这个
运行过程反复迭代地进行 ,直到满足某个终止条
件为止. 遗传模拟退火算法将遗传算法和模拟退
火算法的优点充分结合起来 ,大大提高了算法的
效率. 本文构造的混合遗传模拟退火算法的求解
过程如下 :
Step 1. 初始化 :进化代数计数器 k 初始值为
0 ,给出种群 F(k) 初始值 ,给定初始退火温度 t0.
Step 2. 评价当前群体 F(k) 的适应度.
Step 3. 执行个体交叉操作 ,同时在交叉之后
可以附带保优操作 :F′(k) ←Crossover[ F (k) ].
Step 4. 执行个体交叉变异操作 ,根据变异结
果可以附带保优操作 :F″(k) ←Mutation[ F′(k) ].
Step 5. 由模拟退火状态函数产生新个体.
Step 6. 以概率接受新个体 ,执行个体的模拟
退火操作 :F′″(k) ←SimulatedAnnealing[ F″(k) ].
Step 7. 判断模拟退火抽样是否稳定. 若不稳
定则返回步骤 5 (Step 5) ;若稳定则往下执行退温
操作 t ←t′.
Step 8. 个体复制操作 :由择优选择模型保留
最佳种群 :F(k + 1) ←Reproduction[ F(k) ∪F′″(k) ].
Step 9. 终止条件判断. 若不满足终止条件 ,
则 k ←k + 1 ,转到步骤 2(Step 2) ;若满足终止条件 ,
则输出当前最优个体 ,结束算法.
3. 3 混合遗传模拟退火算法的编码操作
本文提出的混合遗传模拟退火算法在具体实
施过程中编码和相关的优化操作如下.
(1) 适配值函数
适配值函数用于对各状态的目标值作适当的
变换 ,用以体现各状态性能的差异. 本文取 f ( x)
= exp ( - d x) 为适配值函数 ,其中 d x 为状态 x 的回
路长度.
(2) 选择算子
选择算子其作用是从当前群体中选择一些比
较优良的个体 ,并将其复制到下一代群体中. 选择
操作是建立在群体中个体的适应度评估基础上
的 ,模型的拟合残差平方和越小 ,该个体被遗传到
下一代群体中的概率也就越大.
本文采用比例选择方法 ( Proportional Model) ,
目的是使适配值高的个体有更高的生存概率. 该
方法的基本思想是 :各个个体被选择的概率与其
适应度大小成正比. 具体操作是产生随机数ε∈
[0 ,1] ,若
∑
i =1
j =1
f j ∑
P- size
j =1
f j < ε ≤ ∑
i
j =1
f j ∑
P- size
j =1
f j
则选择状态 i 进行复制.
尽管比例选择方法带有很大的随机性 ,但是
由于在遗传算法中溶入了模拟退火这一快速局部
收敛的算法 ,因此可以避免由随机性而带来的收
敛速度慢的缺陷.
(3) 交叉算子
交叉算子作用是产生一些较好的新个体模
式 ,寻优的搜索过程主要通过它来实现. 交叉操作
算子主要有 Non2ABEL 群置换操作、次序交叉、循
环交叉以及 PMX 交叉等. 本文采用常用的单点交
叉算子 ,即在个体编码串中随机设置一个交叉点 ,
然后在该点以概率交叉构成两个配对个体的编码
串基因. 通过对交叉概率等参数的设定 ,可以做到
既能产生一些较好的新个体 ,又使子串能够很好
地继承父串的优良基因 ,有利于对有效模式的保
留.
(4) 变异算子
变异算子目的是改善遗传的局部搜索能力 ,
维持群体的多样性 ,防止出现早熟现象. 本文的变
异操作对基本变异 (Simple Mutation) 作了一些改
动 ,即当确定某个变异基因位置后 ,不是以变异概
率 pm 随机指定某一位或几位作变异操作 ,而是以
变异概率 pm 在它的作用域[Llow , Lupper ]范围内随
机产生一个数来代替这个基因值. 这样尽管会带
有很大的随机性 ,但是由于结合了模拟退火算法 ,
因此可以实现快速局部搜索.
341 第 2 期 刘怀亮等 :一种混合遗传模拟退火算法及其应用
(5) 退火过程新个体的接受
本文的混合遗传模拟退火算法是独立地对选
择、交叉、变异等遗传操作所产生的一组新个体进
行模拟退火过程. 这里通过选择、交叉、变异等遗
传操作所产生的一组新个体独立地随机选择各个
个体中的两个基因作为扰动点 ,经扰动后的个体
所得的适应度增强则一定接受这个新个体 ,而新
个体所得的适应度减小时 ,以某一概率接受这个
新个体. 这里采用 min{1 ,exp ( - △/ t) } > random
[0 ,1]作为接受新状态的条件 ,其中 △为新旧状态
的目标值差 ,t 为退火温度.
(6) 运行过程中的基本参数控制
初始群体 P 大小由实际情况决定 ,运行时对
于不同的输入量 ,群体的变化范围不一样 ;终止代
数也可根据实际情况来设定 ,本文取 T = 10 000左
右 ;交叉和变异概率也需要由实际情况而定 ,本文
交叉 概 率 pc 值 设 为 015 , 变 异 概 率 pm 设 为
01000 5.
(7) 温度修改和算法终止准则
这里采用了阈值法作为温度修改和算法终止
两准则的设计 ,因为这样可以适应算法性能的动
态变化 ,较好地兼顾算法的优化性能和时间性能.
4 混合遗传模拟退火算法用于解决
TSP 问题
混合遗传模拟退火算法兼具遗传算法和模拟
退火算法两者的优点 ,较为适合于解决 TSP 这种
组合优化问题 ,能够做到很好的寻优. 下面是用混
合遗传模拟退火算法对 TSP 问题的求解过程.
(1) 问题定义 :设 n 为城市数目 , D = [d ij ]为 n
×n 阶距离矩阵 ,d ij代表从城市 i 到城市 j 的距离
( i , j = 1 ,2 ,3 , ?, n) . 则问题是要找出遍访每个城
市恰好一次的一条回路 ,且其路径长度为最短.
(2) 解空间 :解空间 S 可表示为 1 , ?, n 的所
有循环排列的集合 , 即 S = [ S ij ]为 1 ?n 的排列 ,
S i 表示第 i 个城市第 Si 个被访问.
(3) 目标函数 :目标函数为访问所有城市的路
径长度或称为代价函数 ,需求其最小值 ,选为 d =
∑
n =1
k =1
D[ S k , Sk +1 ] 为最小.
表 1 是用混合遗传模拟退火算法 ( GASA) 、遗
传算法和模拟退火算法进行求解 TSP 问题过程中
试验结果的比较 :
表 1 试验结果比较
Table 1 Comparison of experiment result
城市数 算法 最优率( %) 方差 迭代次数
25 GASA 95 1. 5 8 000
GA 84 5. 7 8 000
SA 73 5. 9 8 000
40 GASA 81 8. 5 10 000
GA 71 11. 9 10 000
SA 63 12. 7 10 000
说明 :其中最优率为求得最优值的次数占据
总求解计算次数的比例 ;迭代总次数为求解转移
迭代总次数. 方差计算公式为 :
δk = ( f ( k) - fopt) / fopt
f ( k) 是最终目标 k 的函数值 , fopt是最优目标函数
值.
使用混合遗传模拟退火算法 ,将中国 31 个首
府城市(北京、上海、拉萨、昆明、?、台北) 之间的
距离作为已知条件输入后 ,求得最短路径为15 408
km. 具体的路径为 :北京 →呼和浩特 →银川 →兰
州 →西宁 →乌鲁木齐 →拉萨 →成都 →昆明 →贵阳
→南宁 →海口 →广州 →长沙 →武汉 →南昌 →福州
→台北 →杭州 →上海 →南京 →合肥 →郑州 →西安
→太原 →石家庄 →济南 →天津 →沈阳 →长春 →哈
尔滨 →北京.
从实验结果看 ,可以看出本文提出的混合模
拟退火算法在实际的求解 TSP 问题中是有效的 ,
混合遗传模拟退火算法在性能上要优于单纯的遗
传算法和模拟退火算法.
5 结果分析
理论上 ,遗传算法和模拟退火算法两种算法
均属于基于概率分布机制的优化算法. 模拟退火
算法的优化机制是通过赋予搜索过程一种时变和
最终趋于零的概率突变性 ,来避免陷入局部极小
而达到全局最优 ;遗传算法则通过概率意义下的
“优胜劣汰”思想的群体遗传操作实现优化. 作为
两种优化机制的融合 ,本文提出的混合遗传模拟
退火算法不但可以丰富和优化整个过程 ,而且可
以增强全局和局部意义下的搜索能力和效率.
从对于 TSP 问题解决的实验结果可以看出 ,
441 广州大学学报(自然科学版) 第 4 卷
本文提出的混合遗传模拟退火算法比传统的遗传
算法和模拟退火算法要优. 分析该算法主要有如
下特点 :
(1) 优化行为增强
混合遗传模拟退火算法兼具有遗传算法的优
化时间性能和模拟退火算法可以最终趋于全局最
优的特点 ,克服了遗传算法“过早收敛”问题和模
拟退火算法优化时间性能较差的缺点.
(2) 优化效率提高
混合遗传模拟退火算法是一种并行而且具有
自动保优功能的算法 ,该算法把遗传算法和模拟
退火算法两种不同邻域搜索的结构相结合 ,使得
算法在解空间中搜索能力大为增强 ,优化效率得
到提高.
(3) 鲁棒性提高
混合遗传模拟退火算法中多点搜索削弱了模
拟退火算法对初值的依赖性 ,同时混合遗传模拟
退火算法利用遗传算法不影响平稳分布的特性 ,
提高了整个算法的鲁棒性.
参考文献 :
[1] Garrison W Greenwood , Ajay Gupta. Scheduling task in multiprocessor system using evolutionary strategies[A]. The International
Joint Conference on Neural Networks[C]. Japan : Nagoya , 1993. 216 - 224.
[2] Fogel D B. System identification through simulated evolution : a machine learning approach to modeling[M]. America : Ginn Press ,
1991.
[3] Grefenstelle J J , Gopal R , Rosmaita B , et al. Genetic algorithms for the traveling salesman[A]. International Conf of genetic algo2
rithm and their applications[C]. America : Pittsburgh , 1985. 359 - 371.
[4] Hopfield J J , Tank D W. Neural computation of decisions in optimization problems[J ]. Biological Cybern , 1985 , 52 :249 - 260.
[5] 周 明 ,孙树栋. 遗传算法原理及应用[M]. 北京 :国防工业出版社 ,1999.
ZHOU Ming , SUN Shu2dong. The principle and application of genetic algorithm[M]. Beijing: National Defence Industrial Press ,
1999.
[6] Goldberg D E. Genetic algorithms in search ,optimize and machine learning[M]. New York :Addiso Wes2ley ,1993. 372 - 385.
A mixed genetic simulated annealing algorithm and its application
LIU Huai2liang , LIU Miao
(School of Information and Mechanical Electronics Engineering ,
Guangzhou University , Guangzhou 510405 , China)
Abstract : This paper analyzes the advantages and disadvantages of genetic algorithm and simulated annealing , brings
forward a mixed genetic and simulated annealing algorithm , and optimizes its implementation. This paper also gives
the result and example of using the mixed genetic simulated annealing algorithm to solve TSP problem. From the anal2
ysis and experiment result , it is concluded that this algorithm is superior to Genetic Algorithm and Simulated Anneal2
ing.
Key words : simulated annealing ; genetic algorithm; TSP problem
【责任编辑 : 方碧真】
541 第 2 期 刘怀亮等 :一种混合遗传模拟退火算法及其应用
一种混合遗传模拟退火算法及其应用.pdf
