（计算机应用技术专业论文）免疫算法和模拟退火算法求解tsp问题的研究.pdf

摘要旅行商问题是一个经典的组合优化问题，也是一个n p 难问题。它在实际中的应用却非常广泛。历年来，人们一直努力地寻找一种既有高质量的解，又能快速收敛的近似算法。数学发展的重要手段之一就是用新方法解决老问题。最近二十年，许多仿生计算技术悄然兴起，它随着计算机科学的发展同步成长起来。于是，这个古老问题的研究又重新注入了新的活力；由于模拟退火算法简单易行，从而使它的应用范围极为广泛，并且已在众多领域得到了实际应用，且经常用于解决工程上的寻优；生物免疫系统是一个高度进化的生物系统，它具有高度自适应、高度分布性、自组织等特性。它能够有效识别入侵的抗原并清除抗原，并保持机体的稳定。人工免疫算法正是借鉴生物免疫系统信息处理机制的基础上发展起来的智能信息处理技术。由于人工免疫算法具备模式识别、学习和记忆的能力，因此它成为了一种科学及工程领域中信息处理和问题求解范式，由此也开辟了计算智能研究的新领域。本文的工作主要集中在以下几个方面：介绍了生物免疫的一些基本概念、系统组成、功能及原理；简单分析了人工免疫系统的研究内容、研究现状及基本理论；然后，对现已被提出的一些免疫算法和模拟退火算法的基本结构和流程进行了研究和分析。其次，在深入分析了模拟退火算法基础上，提出一种温度可控的求解t s p问题的模拟退火算法，通过对c h n l 4 4 以及标准的t s p l i b 中不同国家的城市的数据进行测试，测试结果表明：该算法很容易收敛到问题的最优解。然后，在理解和掌握生物免疫系统的基本概念和工作原理后，针对免疫原理提出了求解t s p 问题的免疫算法并进行了实现和实验。实验表明：该算法能够求得很好的解。最后，在深入研究免疫算法和模拟退火算法之后，本文提出了一种新的免疫模拟退火算法，并将其应用于求解典型的n p 问题t s p 问题，同时进行了仿真实验，通过对标准的t s p lib 中的p r l0 0 2 的数据进行测试，该算法具有良好的性能。关键词：旅行商问题；克隆选择；计算机免疫；免疫算法；模拟退火算法a b s t r a c tt r a v e l i n gs a l e s m a np r o b l e m ( t s p ) i sac l a s s i cc o m b i n a t o r i a lo p t i m i z a t i o np r o b l e ma n dn p h a r d b u ti ti sa p p l i e di na b r o a df i e l di np r a c t i c e i nt h ep a s t ，p e o p l eh a v e b e e ns t r a g g l i n gt os e e kan e wm e t h o dt h a th a sn o to n l yh i g hq u a l i t yb u ta l s of a s tc o n v e r g e n c er a t ea l lt h ew h i l e o n eo ft h ei m p o r t a n tm e t h o d si nm a t h e m a t i cp r o c e s s i n gi ss o l v i n gt h eo l dp r o b l e mu s i n gu p d a t i n gs t a n d a r d i nt h ep a s tt w e n t yy e a r s m a n yt e c l m o l o g i e so fb i o n i ca l g o r i t h m ss p r i n gu pq u i e t l y a n dp u l l u l a t ec o m p a n i e dw i t ht h ed e v e l o p i n go fc o m p u t e rs c i e n c es y n c h r o n o u s l y s oak i n do fn e we n e r g yw a se m i t t e dt ot h es t u d yo ft s p t h es i m u l a t e da n n e a l i n ga l g o r i t h mi ss i m p l ea n de a s yt oi m p l e m e n t , s oi th a sb e e nu s e di ne v e r yb r o a df i e l d s i ti su s e di ns o l v i n ge n g i n e e r i n go p t i m a lp m b l e m s t h ev e r t e b r a t ei m m u n es y s t e mi sah i g h l ye v o l u t i o n a r ys y s t e m ，w h i c hi sh i g h l ya d a p t i v e , h i g h l yd i s t r i b u t e da n ds e l f - o r g a n i z i n g i tc a ne f f e c t i v e l yr e c o g n i z et h ea n t i g e n sa n dk i l lt h e mr a p i d l yt op r o t e c tt h es t a b i l i t yo ft h eb o d y t h ea r t i f i c i a li m m u n es y s t e m ( a l s ) i sa ni n t e l l i g e n ti n f o r m a t i o np r o c e s s i n gt e c h n o l o g yt h a ti sb a s e do nt h em e c h a n i s mo ft h ev e r t e b r a t ei m m u n es y s t e m a san o v e lb r a n c ho fc o m p u t a t i o n a li n t e l l i g e n c e ，a i sh a ss t r o n gc a p a b i l i t i e so fp a t t e mr e c o g n i t i o n , l e a r n i n ga n da s s o c i a t i v em e m o r y , h e n c ei ti sn a t u r a lt ov i e wa i sa sap o w e r f u li n f o r m a t i o np r o c e s s i n ga n dp r o b l e m s o l v i n gp a r a d i g mi nb o t ht h es c i e n t i f i ca n de n g i n e e r i n gf i e l d s i nt h i sp a p e r , s o m et o p i c sa r em a i n l yt a l k e da b o u t ：s o m eb a s i cc o n c e p t s , f r a m e w o r k ，f u n c t i o n sa n dp r i n c i p l e so ft h eb i o l o g i c a li m m u n es y s t e ma r ei n t r o d u c e d t h e nt h er e s e a r c hr a n g e ，r e s e a r c hs t a t u sa n db a s i ct h e o r yo ft h ea r t i f i c i a li m m u n es y s t e ma n ds i m u l a t e da n n e a l i n ga l g o r i t h ma r cs i m p l ya n a l y z e d s e c o n d l y ，w ed e e p l ya n a l y z et h em e c h a n i s mo fs i m u l a t e da n n e a l i n ga l g o r i t h m ，t h e nt h ep a p e rp r o p o s e sas i m u l a t e da n n e a l i n ga l g o r i t h mb a s e do nc o n t r o l l a b l et e m p e r a t u r ep a r a m e t e rf o rs o l v i n gt s eb yt e s t i n gt h ed a t ao fc h n l 4 4a n db e n c h m a r kt s p l i b t h ee x p e r i m e n t ss h o wt h a tt h ea l g o r i t h mi se a s yt of m do u tt h eb e s ta n s w e r nt h i r d l y , a f t e ru n d e r s t a n d i n gs o m eb a s i cc o n c e p t sa n ds o m ep r i n c i p l e so ft h ev e r t e b r a t ei m m u n es y s t e m , a ni m m u n ea l g o r i t h mi sp r o p o s e da n dr e a l i z e do nt h eb a s i so fi m m u n ep r i n c i p a l b yt e s t i n gi t ，t h ea l g o r i t h mo b t a i n sag o o ds o l u t i o n f i n a l l y ，w ed ot h er e s e a r c ho ni m m u n ea l g o r i t h ma n ds i m u l a t e da n n e a l i n ga l g o r i t h m ，a n dan e wi m m u n es i m u l a t e da n n e a l i n ga l g o r i t h mf o rt s pi sp r o p o s e do nt h eb a s i so fs i m u l a t e da n n e a l i n ga l g o r i t h ma n di m m u n ea l g o r i t h m b yt e s t i n gt h ed a t ao fp r l 0 0 2 ，t h ee x p e r i e n c e ss h o wt h a tt h ea l g o r i t h mh a sag o o dp e r f o r m a n c e h i独创性声明本人声明，所呈交的论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不包含为获得武汉理工大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。签名：塑蛀慨一粤竺一关于论文使用授权的说明本人完全了解武汉理工大学有关保留、使用学位论文的规定，即学校有权保留、送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部分内容，可以采用影印、缩印或其他复制手段保存论文。( 保密的论文在解密后应遵守此规定)盛鼽j 半武汉理工大学硕士学位论文第1 章绪论1 1 研究的背景及意义组合优化问题的目标是从组合问题的可行解中求出最优解。在现实世界里存在大量组合优化问题，其中许多问题( 如：旅行商问题、图着色问题、分配问题、调度问题、布线问题及路由选择问题等) 至今没有找到有效地多项式算法，这些问题已被证明是n p 完全问题。优化问题有三个基本要素：变量、约束和目标函数。在求解过程中选定的基本参数称为变量，对变量取值的限制称为约束，表示可行方案衡量标准的函数称为目标函数。组合优化问题就是在给定的约束条件下，求目标函数最优值的问题。本文以t s p 问题作为研究对象，正是由于t s p 问题具有求解难度的代表性，激发了人们对优化技术的研究和对t s p 问题本身的挑战，不仅t s p 本身成为人们研究的热点，而且由于t s p 问题的代表性，许多新的算法，理论和思想在被提出后也常常使用t s p 作为测试其自身性能的标准。因此，t s p 成为多种启发式的搜索、优化算法的间接比较标准，已经成为优化技术成功的主要体现之一；对于模拟退火算法，该算法善于搜索复杂地区，从中找出期望值高的区域，但在求解上千规模的t s p 问题时效果并不理想；对于免疫算法，国内的研究者虽然也已经开始重视对人工免疫算法的研究，但是更多的注意力是放在利用免疫机理对进化算法的改进，虽然这些算法大多数被冠以免疫算法的名字，但本质上可以说只是利用了免疫系统的相关机理对遗传算法改良策略的重新命名。1 2 研究现状1 2 1t s p 的研究现状正是由于t s p 问题具有求解难度的代表性，几十年以来，随着对优化技术的深入研究，以及计算机处理速度和内存容量的快速增长，人们取得了一个又一个的纪录。武汉理工大学硕士学位论文1 9 8 0 年c r o w d e r 和p a d b e r g 求解了3 1 8 个城市的问题。1 9 8 7 年p a d b e r g 和r i n a l d i 将这个城市数增加到了2 3 9 2 个。1 9 9 2 年美国r i c e 大学的c r p c 研究小组用5 0 台工作站使用了基于“c u t t i n gp l a n e s ”算法解决了3 0 3 8 个城市的问题，被 评为当年的前5 0 条科学新闻。1 9 9 4 年，a p p l e g a t e ，b i x b y , c h v a t a l 等人使用若干台s p a r c 工作站组成的机群用了3 - 4 年的c p u 时间解决了7 3 9 7 个城市的髑p 问题。1 9 9 8 年，c r p c 研究小组使用三台d i g i t e d a l p h a s e r v e r 4 1 0 0 s ( 1 2 个处理器)组成的集群和3 2 台p e n t i u m 1 1 个人计算机解决了美国1 3 ，5 0 9 个城市组成的t s p 问题。2 0 0 3 年二月，h i s a o t a m a k i 使用了路径融合同l i n k e r n i g h a n 启发( l k h )的变种相结合的方法发现了t s p l i b 中p l a 3 3 8 1 0 的一个次优解。2 0 0 4 年二月，k e l dh e l s g a u n 发现了p l a 8 5 9 0 0 问题的一个次优解。此外，他又于2 0 0 4 年i 2 月发现了7 , 5 1 6 ，3 5 3 ，7 7 9 个节点的世界t s p 问题的一条比较好的解，这是目前为止已知的求解规模最大的t s p 问题。1 2 2 模拟退火算法的研究现状模拟退火算法( s a ) 在理论上已经得到证明，它可以达到全局极小值，所以它受到广大专家与学者的青睐。目前，关于模拟退火算法的研究通常分为两类。第一类是基于有限状态奇异马尔可夫链的有关理论，给出模拟退火算法的某些关于理想收敛模型的充分条件或充要条件，这些条件在理论上证明了当退火三个原则( 初始温度足够高、降温速度足够慢、终止温度足够低) 满足时，模拟退火算法以概率1 达到全局最优解；第二类是针对某些具体问题，给出了模拟退火算法的很多成功应用。事实上，正是由于专家和学者对该算法的钻研，才使该算法从经典的模拟退火算法走到了今天的多样性的模拟退火算法，比如快速模拟退火算法，使得该算法的速度和收敛性都得到较大提高，再比如适应性的模拟退火算法，使得该算法具有一定的智能性；再比如现在有学者提到的遗传模拟退火算法，就是将遗传算法和模拟退火算法二者的优越性结合起来。不能忽略的是，每种算法的提出都与其应用范围紧密结合，这样才使得改进的算法在其应用领域具有较好的适用性。由于模拟退火算法( s a ) 从理论上可以达到全局极小值，所以对该算法的研究才更具有它的实际意义，众多学者正在努力钻研2武汉理工大学硕士学位论文并将其一般化，使其具有普遍适用性。1 2 3 人工免疫算法研究现状随着近年来国际上在生命自然科学领域方面的长足发展，人们对a i s( a r t i f i c i a lg l i l l y l u n es y s t e m s ) 中信息处理机制的模型与相应算法的研究也逐渐活跃起来。1 9 9 6 年1 2 月，在日本首次举行了基于免疫性系统的国际专题讨论会，并首次提出了“人工免疫系统”的概念；1 9 9 7 年，i e e e 的“s y s t e m ，m a na n dc y b e r n e t i c s ( s m c ) ”组织专门成立了“人工免疫系统及应用”的分会组织，并于当年年底在美国的o r l a n d 。召开的年会上开始收录有关a i s 方面的论文。国际会议从1 9 9 7 年开始每年组织专门的人工免疫系统研讨会，还有g e c c o ( g e n e t i ca n de v o l u t i o n a r yc o m p u t a t i o nc o n f e r e n c e ) ，c e c ( c o n g r e s so ne v o l u t i o n a r yc o m p u t a t i o n ) 等国际会议也将人工免疫系统作为讨论的主题之一。2 0 0 2 年9 月在英国k e n t 大学还成功召开了第一届人工免疫系统国际学术会议i c a r i s ( i s ti n t e r n a t i o n a lc o n f e r e n c eo n a r t i f i c i a li m m u n es y s t e m s ) 。由于众多的国际会议，人工免疫算法研究与应用也受到人们的重视，同时掀起了对智能信息、处理系统的研究中继模糊系统、人工神经网络和进化算法等领域之后的又一个研究热点，其成果也开始广泛涉及到自动控制【1 h 4 、故障诊断1 5 ，6 】、模式识别 7 - 9 1 图象识别【1 0 l 、优化设计【1 1 i - 1 5 1 、机器学习【1 6 1 、联想记忆1 1 7 】和网络安全性【1 8 , 1 9 l 等诸多领域。有学者将人工免疫算法与神经网络进行比较，指出了它们之间的相似性和差异性l 刎，差异性使人工免疫系统能够用于人工神经网络不适合的情况。免疫系统由于它所具备的多种特性，使其在优化领域有着广泛的应用前景，为研究新的优化算法及改进现有的优化算法提供了多种新的思路。1 9 7 4 年，美国诺贝尔奖获得者j 啪e 1 2 1 】提出了免疫网络理论而引起人们的关注，之后f a r m e r 、p e r e l s o n 、k e p h a r t 、b e 堪m i 、v a r e l a 等理论免疫学者分别在1 9 8 6 年、1 9 8 9 年和1 9 9 0 年发表了有关论文【2 2 j 刚，在免疫系统启发实际工程应用方面做出了突出贡献，他们的研究工作为建立有效的基于免疫原理的计算机系统和智能系统的发展开辟了道路。目前世界上绝大多数人工免疫系统研究成果出自美国、英国、日本。在人工免疫系统领域取得显著成绩的主要有：巴西c a m p i n a s 大学的d ec a s t r o 博士最早在其博士论文中总结了人工免疫系统，并试图建立人工免疫系统的统一框架结构；日本学者i s h i d a 在1 9 9 0 年利用免疫系统解决传感器网络故障诊断问题，是目前可查的最早的免疫系统在工程领域的研3武汉理工大学硕士学位论文究成果；1 9 9 4 年美国n e wm e x i c o 大学计算机科学系的f o r r e s t 博士将免疫系统理论用于计算机安全病毒检测；研究基于免疫原理的计算机安全和异常检测及工业应用的m i s s o u r i 大学计算机与数学系的d a s g u p t a 博士；研究数据分析的英国k e n t 大学的t t m m i s 博士；研究计算机网络入侵的k i n g s 学院的k i m 博士：威尔士大学h u n te 和d e n s i ec o o k e 领导的i s y s 研究小组等。国内在计算机免疫方面的研究刚刚起步。研究机构主要有武汉大学软件工程国家重点实验室、北方交通大学计算机系、北京理工大学网络安全技术实验室、南京航空航天大学机电工程学院等。武汉大学提出了基于多代理的计算机安全免疫系统检测模型，并在“自我”、“非我”的识别规则上进行研究，提出用演化挖掘的方法提取规则弘”，在基于系统调用的基础上建立了位串识别器，借鉴食物链的一些特征，建立了一种多识别器协同识别模型【冽：武汉大学与北方交通大学合作，提出了基于主机安全扫描的计算机免疫系统检测模型【冽；北方交通大学提出了一种基于免疫的入侵检测模型【3 0 1 ，并将随机过程引入计算机免疫的研究中；国防科技大学提出了一种基于人工免疫模型的入侵检测方法1 3 1 】；南京航空航天大学对利用免疫机理进行抗病毒技术进行了研究【3 2 】；北京邮电大学和西安交通大学分别提出了基于免疫原理的网络入侵检测模型1 3 3 】；四川大学李涛教授领导的小组也提出了自己的免疫算法和模型【3 4 j 。西安电子科技大学的王磊、焦李成等在i c s p 9 8 上首先提出了一种免疫遗传算法并应用于典型的优化问题的求解中。中国科学技术大学的王熙法与曹先彬、刘克胜等也提出了自己设计的免疫算法。1 3 本文的主要工作随着计算机技术的发展和普及，t s p 问题在很多方面得到迅速发展和推广。本文将模拟退火算法和人工免疫算法用于t s p 问题的求解，目前，模拟退火算法善于搜索复杂地区，从中找出期望值高的区域，但在求解上千规模的t s p 问题时效果并不理想，所以还值得进一步的研究；人工免疫系统的研究工作正在如火如荼的进行着。人工免疫系统仍处于研究阶段，尚未形成完善的体系结构，并有许多地方值得研究和探讨，所以基于免疫原理的免疫算法也成为了研究的热点。这也使本文的研究工作存在一定的难度，但同时也带来的巨大的挑战。本文的主要工作包括：4武汉理工大学硕士学位论文1 ) 首先通过收集国内外相关资料，阅读了相关文献的基础上，理解了模拟退火算法的思想及算法；对人工免疫算法的主要思想和理论进行了系统的学习，并对基于人工免疫系统的算法和模型进行较为深入的理解。最后，针对一些基础性的模型和算法进行较为认真的研究和学习。2 ) 在深入分析了模拟退火算法和t s p 问题的基础上，提出一种温度可控的求解t s p 问题的模拟退火算法，并将其应用于求解典型的n p 问题t s p 问题，通过对c 哪l “以及标准的t s p l i b 中不同国家的城市的数据进行测试，测试结果表明：该算法很容易收敛到问题的最优解。3 ) 在了解和掌握生物免疫系统的基本概念和工作原理后，针对t s p 问题，提出了求解t s p 问题的免疫算法，并进行实现和试验。4 ) 在全面了解免疫算法和认真细致地学习了模拟退火算法的基础上，本文提出了将二者结合起来，取二者之长的一种新的免疫模拟退火算法，并将其应用于求解典型的n p 问题髑p 问题，同时进行了仿真实验，通过对c h n l 4 4以及标准的t s p l i b 中的p r l 0 0 2 的数据进行测试，该算法具有良好的性能。1 4 本文的结构第1 章介绍了t s p 的问题，模拟退火算法，人工免疫算法的背景、意义及研究现状，对论文内容进行了概括性综述。第2 章模拟退火算法和t s p 问题进行了简介，并对模拟退火算法进行描述，然后提出一种温度可控的求解t s p 问题的模拟退火算法，并将其应用于求解典型的n - p 问题t s p 问题，同时对c 1 州1 4 4 以及标准的t s p l i b 中不同国家的城市的数据进行测试。第3 章介绍了有关免疫理论的生物学基础，简要介绍了免疫系统中的一些基本概念、基本原理；然后根据上述理论思想，结合t s p 问题，提出了求懈t s p问题的免疫算法，并进行实现和试验；最后，又进一步提出了将免疫算法和模拟退火算法结合起来，取二者之长的一种新的免疫模拟退火算法，并将其应用于求解典型的n - p 问题! i s p 问题，同时进行了仿真实验。第4 章对全文进行了总结和展望，指出了今后应该努力的方向。5武汉理工大学硕士学位论文第2 章求解t s p 问题的模拟退火算法旅行商问题的形象化描述是指一个商人想要到n 个城市推销商品，希望选择一条道路，使得经过所有城市一次且仅一次，最后回到起点。我们的目标是帮助这个商人找到最短的路径。旅行商问题简称t s p ( t r a v e l i n gs a l e s m a np r o b l e m ) 。旅行商问题的实例可分为两类：( 1 ) 对称旅行商问题简称，t s p ：( 2 )非对称旅行商问题，简称d h c 。非对称旅行商问题较难求解，本文限于研究对称旅行商问题。砖p 以图论的形式描述为：在图g = 代e ) 中，v 是点( 城市)的集合，e 是边的集合，e = ( i ，j ) l i , j v 。点i 与j 的欧氏距离为删，设d i j = d j i 。目标是找到一个长度最小的闭合回路，使得访问每个点一次且仅一次，这条闭合回路也称作哈密顿回路。此外，t s p 从组合优化的角度描述，t s p 是一个有限集合下的最优化问题：设有限集合d 是有限个决策变量x 组成的集合，集合f = x d ig ( x ) - - o 称为可行解区域，x f 称为可行解，用f ：d r 表示目标函数，称满足f ( x ) = m j n f ( x ) ix f 的可行解x 是组合优化问题，f , 0 的最优解，而模型( d ，f , 0 表示m i n f ( x ) 一stg ( x ) = o ，x d 因为d 是一个有限集合，因此我们可以用枚举的方法证明最优解x 一定存在，但是我们知道随着问题规模的扩大，用枚举法显然不现实。旅行商问题t s p 是一个典型的组合优化问题，并且是一个n i 完全问题，其可能h a m i l t o n 圈的数目是顶点的数目n 的指数函数，所以一般很难精确地求出其最优解。而很多实际应用问题，如印制电路板问题、网络路由问题、连锁店的货物配送路线等，经简化的处理后，均可转化为旅行商问题。今天，由于电子计算机科学技术的进展，这个古老问题的算法研究又重新注入了新的活力，旅行商问题研究的新思路、新方法、新成果必将丰富n p 完全理论的内涵，促进n p 完全理论的发展。纵观旅行商问题算法研究的发展历史，主要手段是通过设计一些思想性或构造性的启发式的搜索策略来寻求问题的解，由此产生了很多具有代表意义的近似算法，下面重点介绍模拟退火算法在旅行商问题中的应用。6武汉理工大学硕士学位论文2 1 一般模拟退火算法2 1 1 概述模拟退火又称m o n t ec a r l o 退火，是一种常用的全局优化方法，它来源于固体退火原理：将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状态，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小：然而要是迅速冷却或被“碎熄”，那么仅仅能达到其局部能量极小点，该材料处于易碎状态。这就是所谓退火在技术上的定义，同时也表明了确保达到低能量状态所必需的条件。1 9 8 2 年，k i r k p a t r i c k 等将退火思想引入组合优化问题，同时综合了统计物理学和局部搜索方法，提出一种解大规模组合优化问题的方法，特别是n p 完全组合优化问题的有效近似算法一模拟退火算法。采用m e t r o p o l i s 接受准则，并用一组称为冷却进度表的参数控制算法进程，使算法在多项式时间里给出一个近似最优。m e t r o p o l i s 准则是m e t r o p o l i s 等1 9 5 3 年提出的重要性采样法，在模拟退火法中，状态从i 到j 变化的m e t r o p o l i s 准则是相应的转移概率，可以表示为：rl以力墨八f )只( f j - ，) 。l i 善“4以d f 其中，a = f ( i ) 一f ( j ) ，f ( i ) 和f ( j ) 是目标函数在状态i 和j 上的值；t 是退火过程中的温度，表示控制参数：p 。( i = j ) 确定是否接受从当前解i 到新解j 的转移。可以用随机数发生器产生一个 o ，1 范围内随机数，当p 。( i = j ) 随机数时，新状态是重要状态，并把新状态作为当前状态，否则舍弃新状态。然后，重复产生新状态。每次循环，模拟退火法都会扰乱己存在的系统，从中获得新系统状态和新系统的候选途径，算法总是在接受变化。2 1 2 模拟退火算法的描述( 1 ) 初始化：初始温度t ，初始解状态s ( 是算法迭代的起点) ，每个t 值的迭代次数l ；7武汉理工大学硕士学位论文( 2 ) 对k = 1 至l l 次做第( 3 ) 至第6 步；( 3 ) 产生新解s ；( 4 ) 计算增量a t = c ( s ) - c ( s ) ，其中c ( s ) 为评价函数；( 5 ) 若at o ，然后转第2 步。模拟退火算法新解的产生和接受可分为如下四个步骤：第一步是由一个产生函数从当前解产生一个位于可行解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。第三步是判断新解是否被接受，判断的依据是一个接受准则，最常用的接受准则是m e t r o p o l i s 准则：若t 0 则接受s 作为新的当前解s ，否则以概率e x p ( - a t t ) 接受s 作为新的当前解s 。第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。模拟退火算法的应用很广泛，可以求解n p 完全问题，但其参数难以控制，其主要问题有以下三点：( 1 ) 温度t 的初始值设置问题。温度t 的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。8武汉理工大学硕士学位论文( 2 ) 退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的“充分”搜索( 退火) 是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。( 3 ) 温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，通常采用如下所示的降温方式：t ( t + 1 ) = k t ( t ) 式中k 为正的略小于1 的常数，t 为降温的次。2 2 温度可控的求解t s p 问题的模拟退火算法本节在上述算法的基础上，提出了温度可控的求解t s p 问题的模拟退火算法，该算法的基本思想：利用全局变量的作用，将要优化的数据保存到全局变量gp a m l ) 数组中，并定义全局变量t 保存温度，然后将模拟退火算法定义成一个线程函数，这样就可以多次激活模拟退火线程函数，在重新设置温度情况下和上次优化的基础上重新优化。本章算法还利用了f p r i n t f ( ) 函数作用，可以将优化得到的结果写到文件中进行保存。如果需要将保存在文件中数据进行重新优化，则可以利用f s c a n f ( ) 函数将保存在文件中数据读到g _ p a t h 数组中，然后重新激活模拟退火线程函数对其进行优化。根据上述思想，本章提出了一种温度可控的模拟退火算法。通过对c h n l 4 4 以及标准的t s p l i b 测试库1 3 5 j 中不同国家的城市的数据进行测试，结果表明了它很容易收敛到问题的最优解。2 2 1 求解t s p 问题的变换算子产生新解所用到的一些变换算子1 ) 2 变换法任选两个序号u v ，且u q 将这两个及期间所有城市颠倒访问顺序。例如：c n ( u - 1 ) c n ( u ) c n ( u + 1 ) c n ( v - 1 ) c n ( v ) c n ( v + 1 ) ，换后为：c n ( u 一1 )c n ( v ) c n ( v - 1 ) c n ( u + 1 ) c n ( u ) c n ( v + 1 ) 2 ) 3 变换法：任选三个序号u , v , w ，且u v w 将序号为u 和v 及期间所有城市，移到序号为w 的城市之后。例如：c n ( u 一1 ) c n ( u ) c n ( v ) c n ( v + 1 ) c n ( w )c n ( w + 1 ) ，交换后为：c n ( u 一1 ) c n ( v + 1 ) c n ( w ) c n ( u ) c n ( v ) c n ( w + 1 ) 3 ) 除了使用两种变换法之外，还引入二点变换法，增加了产生新解的变化。9武汉理工大学硕士学位论文引入的变换法为：任选两个序号u ，v 交换序号为u 和v 的城市序号，其余的城市保持不变。例如：c n ( u - 1 ) c n ( u ) c n ( u + 1 ) c n ( v - 1 ) c n ( v ) c n ( v + 1 ) ，换后为：c n ( u - i ) c n ( v ) c n ( u + 1 ) c n ( v - 1 ) c n ( u ) c n ( v + 1 ) 2 2 2 温度可控的求解t s p 问题的模拟退火算法设计思路l 本算法用到的相关内容介绍1 ) 目标函数：访问所有城市的路径长度，或称为代价函数。f ( s ) = ed 【c n ( i ) ，c n ( i + 1 ) m o d n 0 = 1 ，2 , 3 n ) 这里d 【c n ( i ) ，c n ( i + 1 ) m o d s 为城市c n ( i ) 与c a ( i + 1 ) m o d s 之间距离。2 ) 代价函数差( d f ) ：新解的代价函数与产生新解之前的代价函数的差3 ) 定义了两个全局变量，因为全局变量能够在整个程序中起作用，所以定义了全局变量g _ p a t h 数组来保存将要优化的数据及其优化后的结果，并定义全局变量t 保存温度数据。4 1 设计一个线程函数，该线程函数的作用是实现上述2 1 所介绍的模拟退火算法。5 ) 介绍2 个重要的函数f p r i n t f ( f p , d t d t d , g _ p a t h i i n d e x ，g _ p a t h i _ x ，g _ p a t h i j ) ：它将g _ p a t h 】中的数据写到f p 指针指向的文件。f s c a n f ( f p ，”，i d d d ”& g _ p a t h 门in d e x ，& g _ p a t h 】- x & g _ p a t h 门- y ) ：它将f p 指针指向的文件中的数据读到& g _ p a t h 中去。2 本章所提出的温度可控的求解t s p 问题的模拟退火算法描述1 ) 设计一个图形用户界面，它拥有文件和优化两个菜单，其中文件菜单下面有载入、保存和退出三个子菜单，优化菜单下面有优化路径和修改温度两个予菜单；2 ) 在修改温度子菜单下设计设置温度，用户可以根据需要设定温度；在优化路径菜单下设计通知操作系统创建一个线程，运行用模拟退火算法实现的线程函数，该线程函数对保存在g _ p a t h q a 数据进行优化，优化完毕后线程函数返回，线程终止运行；上述线程所使用的模拟退火算法的伪程序；p r o c e d u r et s p s a ：b e g i n1 0武汉理工大学硕士学位论文i n i t - o f - t ； t 为初始温度s = 1 ，n ) ； s 为初始值)t e r m i n a t i o n = f a l s e ；w h i l et e r m i n a t i o n = f a l s eb e g i nf o r i - - 1 t o l d ob e g i n对待优化问题采用2 变换法等优化算子；g e n e r a t e ( s f o r ms ) ； 从当前回路s 产生新回路at ：= f ( s7 ) ) 一f ( s ) ； f ( s ) 为路径总长)w ( a t r a n d o m - o f - o , 1 )s = s ；i ft h e - h a l t - c o n d i t i o n - i s - t r u et h e nt e r m i n a t i o n - - t m e ；e n d ；t l o w e r ；e n d ；e n d ；3 ) 如果我们需要再次优化时，则回到第二步，重新设置温度，在上次优化的基础上再次进行优化。4 ) 如果需要对所求得的结果进行保留时，就可以选中文件菜单中的保存项，该保存项则通知操作系统执行用f p r i n f f ( ) 函数实现的程序段，将g _ p a t h 中的数据写到由自己命名的文件中，所以可以将优化得到的结果保存下来。5 ) 如果需要将保存下来结果重新优化时，则可以选中文件菜单下面的载入项，该载入项则通知操作系统执行用f m 既m f ( ) 函数实现的程序段，将指定的文件中的数据读到g _ p a t h 】中，然后回到第二步6 ) 如果需要退出，则选择文件菜单下面退出子菜单即可。3 本算法的特点1 ) 引入一种随机函数：混沌随机函数2 ) 引入二点变换法，增加了产生新解的变化，可以收敛到问题的最优解。3 ) 它与回火退火算法很相似，即能够对优化问题进行多次回火优化。1 1武汉理工大学硕士学位论文4 1 它比回火退火算法更加灵活方便。回火退火算法的回火次数和每次回火的温度是在运行前确定，如果要修改温度和回火次数，则要求程序员重新修改程序，而上述算法可以根据需要由人从键盘多次输入温度的值，然后进行多次优化，而无须修改程序。5 ) 它能够多次保存优化的结果，并可以将保存的结果重新载入和重新优化，从而收敛到问题的最优解。2 2 3 一些重要部分的实现数据结构描述：# d e f i n en城市规模数# d e f i n el ，循环的次数t y p e d e fs t r u c t _ p a t hi n ti n d e x ；u n s i g n e di n t x ，y ； p a t h , * p p a t h ；u n s i g n e di n tg _ c 6 】= 0 ) ；u n s i g n e di n tc i t y f n 【n 】= o 1 ) 二点变换法的实现v o i do n e c h a i n ( i n t n l n d i c c s )p a t hp a t h t v m p ；i f ( n i n d i c e s 1 】( n i n d i c e s 4 )p a t h t e m p = + ( g _ _ p a t h + n i n d i c e s 4 ) ；将n i n d i c e s 1 】一n l n d i c e s 3 】结点后移一位f o r ( i n ti = n l n d i c c s 4 ；i n i n d i c c s 1 ；i - - )。( g _ p a t h4 - i ) = ( g _ p a t h + i - 1 ) ；删每p a t h t c m p 中的数据拷到n l n d i c c s 1 】这个结点中+ ( g _ p a t h4 - n i n d i c c s 1 ) = p a t h t e m p ；e l s e武汉理工大学硕士学位论文* p a t h t e m p = ( g _ p a t h + n l n d i c e s 4 ) ；c o p y ( & p a t h t e m p ，g _ p a t h + n l n d i c e s 4 ) ；将n l n d i c e s 5 卜n l n d i e s 0 】结点前移一位f o r ( i n ti = n l n d i c e s 4 ；i n l n d i c e s o ；i + + 1+ ( g _ p a t h + i ) = ( g _ p a t h + i4 - 1 ) ；c o p y ( g _ p a t h + i ，g _ p a t h + i + 1 ) ；，将p a t h t e m p 中的数据拷到n i n d i c e s o 】结点中。( g _ p a t h4 - n l n d i c e s o ) = p a t h t e m p ；c o p y ( g _ p a t h + n l n d i c e s 0 ，& p a t h t e m p ) ；)2 ) 2 o p t 的实现v o i dt w o c h a i n ( i a t 。n i n d i c e s )u n s