2010年第5期(总第77期)
边疆经济与文化
THE BORDER ECONOMY AND CULT URE
No 1512010General 1No 177
10
B I A N J I A N G J I N G J I Y U W EN HUA
【旅游经济】
求解旅行商问题的几种解法
高春涛
(哈尔滨商业大学基础科学学院,哈尔滨150028)
摘 要:旅行商问题(TSP )是一个典型的NP 完全问题,现在还没有找到有效的解法。
目前比较热门的求解TSP 问题的方法主要有四种:神经网络算法;模拟退火算法;遗传算法;蚁群算法。
关键词:旅行商问题;组合优化;解法
中图分类号:F 592 文献标志码:A 文章编号:167225409(2010)0520010202
收稿日期:2010201222作者简介:高春涛(1973
),女,黑龙江拜泉人,讲师,硕士,主要从事混沌神经网络研究。
一、引言
旅行商问题(Traveling Sales man Pr oble m ),是指给定n 个城市,任何两城市之间皆有路连通,其距离为已知,某旅行商从其中某城市出发,要经过每城市一次,且只能一次,最后又必须返回出发城市,要求找出最短的巡回路径。
由于在很多实际问题中,如印刷电路板的铅孔路线方案、连锁店的货物配送路线等问题经过简化处理,均可建模为旅行商问题,因而对旅行商问题求解方法的研究具有重要的应用价值。
旅行商问题是运筹学中有代表性的组合优化问题,也是典型的NP 完全问题。
虽然它陈述起来很简单,但求解却很困难,对于具有n 个城市的TSP 问题,其可能的路径数目为(n -1)!/2,至今尚未找到有效的求解方法,在理论上枚举法可以解决这一问题,但是当n 较大时,解题的时间消耗会使枚举法显得没有任何实际价值。
因此寻求一种求解时间短,能满足实际问题精度要求的解,成为解决该问题的主要途径。
二、TSP 求解方法
求解旅行商问题的方法可以分为两大类,一类是精确算法,目的是要找到理论最优解;另一类是近似算法,其算法简单,计算量小,大多数情况下求得的满意解能满足要求。
1.Hopfield 神经网络算法
1982年,Hopfield 开创性地在物理学、神经生物学和计算机科学等领域架起了桥梁,提出了Hopfield 反馈神经网络模型(HNN )。
Hopfield 网络是典型的全连接网络,通过在网络中引入能量函数以构造动力学系统,并使网络的平衡态与能量函数
的极小解相对应,从而将求解能量函数极小解的过程转化为网络向平衡态的演化过程。
尤其是通过对TSP 问题的成功求解,开辟了神经网络模型在计算机科学应用中的新天地,动态反馈网络从而受到广泛的研究和关注,被广泛应用于优化问题中,且已
设计出了专用的硬件电路。
[1]
Hopfield 网络是一种非线性动力学模型,通过引入类似Lyapunov 函数的能量函数概念,把神经网络的拓扑结构(用连接矩阵表示)与所求问题(用目标函数描述)对应起来,转换成神经网络动力学系统的演化问题。
因此,在用Hopfield 网络求解优化问题之前,必须将问题映射为相应的神经网络。
对TSP 问题的求解,首先将问题的合法解映射为一个置换矩阵,并给出相应的能量函数,然后将满足置换矩阵要求的能量函数的最小值与问题的最优解相对应。
2.模拟退火算法
模拟退火算法最初的思想由Metr opolis 在1953
年提出,[2]
Kirkpatrick 在1983年成功地将其应用在组合最优化问题中。
模拟退火算法的出发点是基于物理中固体物质的退火过程与一般组合优化问题之间的相似性。
模拟退火算法在某一初温下,伴随温度参数的不断下降,结合概率突跳特征在解空间中随机寻找目标函数的全局最优解,即在局部优解能
概率性地跳出并最终趋于全局最优。
[1]
用固体退火模拟组合优化问题,将内能E 模拟为目标函数f,温度T 演化成控制参数t,即得到解组合优化问题的模拟退火算法:有初始解i 和控制参数初值t 开始,对当前解重复“产生新解→计算目标函数差→接受或舍弃”的迭代,并逐步衰减t 值,算法终止时的当前解即为所得近似最优解。
高春涛:求解旅行商问题的几种解法
B I A N J I A N G J I N G J I Y U W EN HUA
11
解决TSP 问题的模拟退火算法的框架为:[3]
给定起、止“温度”T,T 0和退火速度a,初始的一条路径C 0;W hile (T >T 0)do;在C 0的邻域内产生另一条路径C 1;计算两条路径所引起的目标函数(能量)值的变化△E;若△E ≤0,接受新值,若exp (-△E /T )>rand (0,1)(rand (0,1)表示0～1之间的随机数,也接受新值,否则就拒绝;确定新的参数值,若扰动被接受,则C0←C1,否则不变化;若接受新值,降温T ←aT,否则不降温;End 。
模拟退火算法的实验性能具有质量高、初值鲁棒性强、通用易实现的优点。
但是,为寻到最优解,算法通常要求较高的初温、较慢的降温速率、较低的终止温度以及各温度下足够多次的抽样,因而模拟退火算法往往优化过程较长,这也是模拟退火算法最大的缺点。
3.遗传算法
遗传算法(Genetic A lgorith m s 简称G A )是基于生物进化原理的普适性全局优化算法,是美国M ichigan 大学的Holland 教授于1975年受进化论的启发而首次提出的。
它引进生物学中基因遗传和“自然选择,适者生存”的进化思想,将优化问题的求解看成可行解的进化过程。
一般地,遗传算法以一群随机产生的可行解开始,每个解用一串编码表示为个体,由优化目标函数确定个体的适应度对个体进行评价。
通过交叉、变异等遗传算子的操作对种群进行组合产生下一代个体,逐步向优化的种群进化。
与传统的优化方法相比,遗传算法的主要特点是:遗传算法使用参数的编码集,而不是参数本身进行操作;遗传算法不在单点上寻优,而是从整个种群中选择生命力强的个体产生新的种群;遗传算法仅使用问题的目标函数进行工作,不需要其他的先决条件或辅助信息;遗传算法使用随机转换原理而不是确定性规则来工作。
遗传算法在具体实施中有多种变形和修正,其
主要操作思想可描述成:[4]
Step 1问题的染色体表示;Step2初始解组(种群)的生成;Step3计算解组中各个解的适值函数(代价函数);Step4从解组中随机抽取两个解作为父母代;Step5对父母代实施遗传操作(交叉、变异等)以产生一个后代解;
Step6按某种规则,用该后代解替代原解组中的某个解;Step7若当前解组符合停机条件,则算法终止,否则,转Step4。
遗传算法的优点是算法进行全空间并行搜索,并将搜索重点集中于性能高的部分,从而能够提高效率且不易陷入局部极小;算法具有固有的并行性,提高对种群的遗传处理可处理大量的模式,并
且容易并行实现。
其主要缺点是对于结构复杂的组合优化问题,搜索空间大,搜索时间比较长,往往会出现早熟收敛的情况;对初始种群很敏感,初始种群的选择常常直接影响解的质量和算法效率。
4.蚁群算法
蚁群算法(Ant Col ony A lgorithm ,简称ACA )是由意大利学者Dorigo M 等人首先提出来的一种新型的模拟进化算法。
它是从对蚁群行为的研究中产生的。
仿生学家经过大量细致观察与研究发现,原来蚂蚁在寻食的过程中,通过一种称之为信息素的物质相互传递信息。
更具体地说,蚂蚁在运动过程中能够在它所经过的路径上留下信息素,而且在运动过程中感知这种信息素的存在及其强度,并以此指导自己的运动方向。
蚂蚁倾向于朝着信息素强度高的方向前进,因此,由大量蚂蚁组成的蚁群的行为便表现出一种信息的正反馈现象:某一路径上走过的蚂蚁越多,则后来者选择该路径的概率就越大。
蚂蚁群就是通过个体之间这种信息交换机制来彼此协作达到搜索食物的目的。
为了避免蚂蚁两次走上同一条路径,为每个蚂蚁设置一个禁忌表以记录它走过的路径。
蚁群算法的优点在于:它是一种自适应、自组织、本质上并行的方法,而且是一种正向反馈的方法,可以促使整个系统向最优解进化,具有较强的鲁棒性,对蚁群算法模型稍加修改,就可以应用于其他问题,同时它可以与多种启发式算法结合,以改善算法的性能。
但是该算法也具有收敛速度慢、易陷入局部最优等缺点。
此外,算法中的参数设定目前尚无理论的依据,要靠实验来调整和确定。
TSP 问题是组合优化领域中的一个典型问题,解决此问题有较大的现实意义,并且此问题也可作为测试新的算法的标准问题,因此此问题一直是研究的热点。
参考文献:[1] 王 凌.智能优化算法及其应用[M ].北京:清华大学出版社,2001.
[2] M ETROP LO I S N,ROSE NBLUT B A W ,ROSE NBLUT B M N,ET AL.Equati on of State Calculati ons Fast Computing Machines
[J ].J of che m ical physica,1953,21(6):1087-1092.[3] 高 尚.求解旅行商问题的模拟退火算法[J ].华东船舶工业学院学报:自然科学版,2003,17(3):13-16.[4] 马 良.旅行推销员问题的算法综述[J ].数学的实践与认识,2000,30(2):156-165.
〔责任编辑:乙 侻〕。