（电路与系统专业论文）蚂蚁算法在TSP问题中的应用与研究[电路与系统专业优秀论文].pdf

蚂蚁算法在t s p 问题中的应用与研究 蚂蚁算法在t s p 问题中的应用与研究 电路与系统专业 研究生廖兴新指导教师王勇 摘要 组合优化是运筹学的重要分支，主要通过对数学方法的研究寻找离散事件 的最优编排、分组、次序或筛选等。大多数这类问题通常在多项式时间里无法 求解，属予n p 完全问题“1 。随着问题规模的扩大，问题空间呈现组合爆炸特征， 无法用常规的方法求解。旅行商问题( t s p ) ”3 就是一个经典的组合优化问题，属 于n p 完全问题。此类问题目前只能用启发式算法进行求解。 自从上世纪5 0 年代中期创立仿生学以来，人们不断地从生物进化的机理中 得到启发，提出了许多用于解决复杂优化0 1 问题的新方法，比如神经网络0 1 、遗 传算法。1 、模拟退火算法、进化规划等，并成功应用于解决实际问题。由意大利 学者 1 d o r i g o ，v m a n i e z z o ，a c o l o r n i 于1 9 9 2 年首先提出的蚂蚁系统( a n t c o l o n ys y s t e m ，a c s ) “1 ，是一种新颖的仿生进化算法，适用求解复杂组合优化 问题。蚂蚁优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) “1 是一种随机搜索算法， 它基于对自然界真实蚂蚁的集体觅食行为的研究，模拟真实的蚂蚁协作过程。 算法由若干个蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解 的质量，进而达到优化的目的。目前，蚂蚁系统己成功应用于求解旅行商问题 ( t s p ) 、二次分配问题和j o b s h o p 调度问题，取得了很好的实验效果。受其影 响，蚂蚁系统的研究已经逐渐引起了更多学者和专家的关注。虽然，该研究方 法处于研究的初级阶段，但是一些研究成果已经显示出蚂蚁系统在求解复杂优 化问题方面的优越性。 a c o 的主要特征是正反馈和隐并行性。正反馈机制可以快速发现优化解。隐 四 大学硕士学位论文 并行性通过多个个体之间的并行交换信息素可防l f ：算法陷入局部最优解，并可 使算法收敛于解空间的个子集，有利于对解空蛳进行进一步搜索，发现较好 解。蚂蚁算法在处理大舰模优化问题时效率很低。为此我们本文中对蚂蚁算法 提出了一些改进和对影响解的参数进行了分析，得出了一些有益的结论。 ( 1 ) 引入选路优化策略，减少了算法中蚂蚁的选路次数，显著提高了算法 的执行效率。尤其对于以往较难处理的大规模t s p 问题，改进算法在执行效率 上有明显的优势。 ( 2 ) 引入了蚂蚁个体差异，使得蚂蚁选路策略具有多样性。模拟实验结果 表明改进算法的收敛速度和解的质量都有明显提高。 ( 3 ) 分析在求解t s p 问题中参数对解的影响，试图找到一些规律，对同类 问题进行简化处理。 关键词：蚂蚁算法，组合优化，旅行商问题，信息激素 l 【 蚂蚁算法在f s p 问题中的压用与研究 a p p l i c a t i o na n dr e s e a r c ho f a n tc o l o n ya l g o r i t h m i nt r a v e l l i n gs a l e s m a np r o b l e m c i r c u i ta n ds y s t e m p o s t g r a d u a t e ：l i a ox i n g x i nt u t o r ：w a n gy o n g a b s t r a c t c 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 mi sa ni m p o r t a n te m b r a n c h m e n to f o p e r a t i o n a lr e s e a r c h 。t h em a t h e m a t i c a lm e t h o d sc a nb eu s e dt os e a r c h o p t i m i z a t i o na r r a n g e ，g r o u p i n g ，s e q u e n c eo rr i d d i n go f t h ed i s c r e t e e v e n t s t h e s ep r o b l e m sb e l o n gt ot h en o n p o l y n o m i a l c o m p l e t e ( n p c ) q u e s t i o n s ， w h i c hc a n tb es o l v e di np o l y n o m i a lt i m e 。w i t ht h ee n l a r g e m e n to ft h e s c a l eo fq u e s t i o n t h eq u e s t i o ns p a c em a k e st h ec h a r a c t e r i s t i co f e x p l o d i n gu p ，i su n l i k e l ys o l v e dw i t hg e n e r a lm e t h o d s 。 a san p cp r o b l e m ，t 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 c a l c o m b i n a t o r i a lo p t i m i z a t i o nq u e s t i o n ，w h i c hn o wc a no n l yb es o l v e db y m e t a - h e u r i s t i c st og e tt h ea p p r o x i m a t es o l u t i o n 。 s i o c ec r e a t i n gb i o n i c si nm i d d l ep e r i o do f1 9 5 0 s ，p e o p l ea r eb e i n g i n s p i r e df r o mt h em e c h a n i s mo ft h eb i o l o g i c a le v o l u t i o nc o n s t a n t l y 。 m a n yn e wm e t h o d sh a db e e na p p l i e dt os o l v et h ec o m p l i c a t e do p t i m i z a t i o n p r o b l e m sa r ep r o p o s e d 。s u c h a sn e u r a ln e t w o r k ，g e n e t i ca l g o r i t h m ， s i m u l a t e da n n e a l i n g ，a n de v o l u t i o nc o m p u t a t i o n 。t h e s en e wm e t h o d sh a d b e e ns u c c e s s f u l ya p p l i e dt os o l v et h ep r a c t i c ep r o b l e m s 。a n tc o l o n y n l 四j j5 赶学硕士学位论文 s y s t e m ( a s ) w a sf i r s tp r o p o s e db yi t a l ys c h o l a rm ，d o r i g o ，v m a n i e z z o ， a c ( ) l o r n ii n1 9 9 2a san o v e lb ic h i ce v o l u t i o n a r ya t g o r i t h mf o rs o l v i n g c o m p 1 c a t e dc o m b i n a t o rj a lo p t i m iz a t i o np r o b l e m s ，l i k et h et s p ，t h e q u a d r a t i ca s s i g n m e n tp r o b l e m ( q a p ) a n dj o b s h o pp r o b l e m ，e t c 。a tp r e s e n t ， t h er e s e a r c hw o r ka b o u ta sa l r e a d ya r o u s et h ea t t e n t i o nf r o mm o r es c h o l a r s a n de x p e r tg r a d u a l l y 。t h o u g h ，t h i sr e s e a r c ha p p r o a c hl i e sa tp r i m a r y s t a g e ，b u ts o m er e s e a r c h r e s u l t sh a v ea l r e a d yd e m o n s t r a t e dt h e s u p e r i o r i t yo fa s 。 t h em a j o rf e a t u r e so fa c oisp o s i t i v ef e e d b a c k i n ga n dp a r a l l e l n a t u r e t h ep o s i t i v ef e e d b a c k i n gc a nm a k ea c oq u i c k l yt of i n da n s w e r sa n d t h ep a r a ll e ln a t u r ec a nm a k eitm o r ea c c u r a t e t h ep a r a l l e ln a t u r ec a n e x c h a n g et h ei n f o r m a t i o nf o r ma l1t h ec o m p o n e n t st op r o v e n tt h ea c o f a l l i n si n t ol o c a lb e s tc o n d i t i o n a n di ta l s oc a ns o f t e na 1 1t h ek e y s i n t ot h ea n s w e r r o o m i nc a s eo ft h ea c oh a v i n gas l o ws p e e do fs o l v i n g t h e t s pp r o b l e m s ，w ed os o m ee f f i c i e n to p t i m i z a t i o no nt h ea c o ( i ) i n t r o d u c t i o no ft h e r o a do p t i m i z a t i o ns t r a t e g y ，ar e d u c t i o n a l g o r i t h m ，a n te l e c t i o nl un u m b e r so fa l g o r i t h m ss i g n i f i c a n t l yi n c r e a s e t h ee f f i c i e n c yo fe n f o r c e m e n t p a r t i c u l a r l y ，i th a sag r e a ti m p r o v e m e n t i nd e a l i n gw i t ht h el a r g e s c a l et s pp r o b l e m s ( 2 ) i n t r o d u c i n gt h ea n t s i n d i v i d u a ld i f f e r e n c e ss ot h a tt h ea n t s h a v ead i v e r s i t ys t r a t e g yr o a d s i m u l a t i o ne x p e r i m e n t ss h o w e dt h a tt h e a l g o r i t h mt h e m s e l v e st oi m p r o v et h eq u a l i t yo fr e c o n c i l i a t i o nh a s i m p r o v e dm a r k e d l y ( 3 ) a n a l y s i s i n go ft h ep a r a m e t e r so ft h e i rf e l l o wt s pi s s u e si m p a c t ， t r y i n gt of i n ds o m el a w st od e a lw i t hs i m i f a ri s s u e ss i m p l i f i e d k e yw o r d s ：a n tc o l o n ya l g o r i t h m ，c o m b i n a t o r i a lo p t i m i z a t i o n ，t s p ， p h e r o m o n e i v 蚂蚁筚法在r s p 问题中的应用与研完 第一章绪论 1 1 蚂蚁算法基本原理 蚂蚁优化算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 是一种随机搜索算法， 它基于对自然界真实蚂蚁的集体觅食行为的研究，模拟真实的蚂蚁协作过程。 算法由若干个蚂蚁共同构造解路径，通过在解路径上遗留并交换信息素提高解 的质量，进而达到优化的目的。该算法最早由意大利的m d o r i g o 等人在1 9 9 1 年提出。a c o 的主要特征是正反馈和隐并行性。正反馈机制可以快速发现优化 解。隐并行性通过多个个体之间的并行交换信息素可防止算法陷入局部最优解， 并可使算法收敛于解空间的一个子集，有利于对解空间进行进一步搜索，发现 较好解。 由上述可知，蚂蚁算法优化过程的本质在于：( 1 ) 选择机制。信息量越大 的路径，被选择的概率越大；( 2 ) 更新机制。路径上面的信息量会随蚂蚁的经 过而增长，同时也随着时间的推移逐渐减小；( 3 ) 协调机制。蚂蚁之间实际上 是通过信息量来互相通信、协同工作的。这样的机制使得蚂蚁算法具有很强的 发现较好解的能力。在过去的1 0 多年，蚂蚁算法( a c o ) 的研究和应用取得了 很大的进展，大量结果证明了算法的有效性和在某些领域的优势。但是，蚂蚁 算法也有一些缺陷。例如，由于蚂蚁中多个个体的运动是随机的，当群体规模 较大时，要找出一条较好的路径需要较长的搜索时间。为此，吴庆洪等人提出 了具有变异特征的蚂蚁算法【1 1 ，有机地结合了2 - o p t 方法，提高了算法的性能。 m d o r i g o 等人在基本的蚂蚁算法的基础上提出称为a n t qs y s t e m 2 l 的更一般的 蚂蚁算法，每次让信息量最大的路径以较大的概率被选中，以充分利用学习机 制，强化最优信息的反馈。为了克服在a n t q 中可能出现的停滞现象，t s t u t z l e 等人提出了m a x m i n 蚂蚁系统【3 】，允许各个路径上的信息量在一个限定的范 围内变化。吴斌、史忠植提出了基于蚂蚁算法的分段求解算法【4 1 ，提高了蚂蚁搜 索的速度，为蚂蚁算法的并行化奠定了基础。由于在蚂蚁算法构造解的过程中， 四川走学硕士学位论天 选择策略一般是随机的，进化速度较慢。张纪会等人提了自适应的蚂蚁算法| 5 i ， 采用确定性选择和随机选择相结合的策略，在搜索的过程中动态地调整选择的 概率，实现了选择概率的自适应，提高了算法的速度和性能。 1 2 t s p 问题简介 所谓组合最优化问题f 6 】，就是在给定约束条件下，求出使目标函数极小( 或 极大) 的变量组合问题。由于神经网络是并行计算的，其计算量不随维数的增 加而出现“组合爆炸”现象，因而对于优化问题的高速计算特别有效。采用 h o p f i e l d 功地解决了旅行商问题【8 】，就是一个很好的例证。 组合最优化是通过对数学方法的研究去寻找离散事件的最优编排、分组、 次序或筛选等，是运筹学的一个经典且重要的分支，所研究的问题涉及信息技 术、经济管理、工业工程、交通运输、通信网络等诸多领域。该问题的数学模 型为： m i n f ( x ) s , t g ( x ) 0 x d ( 1 1 ) 其中，f ( x ) 为目标函数，g ( x ) 为约束函数，x 为决策变量，d 为有限个点组 成的集合。 一个组合优化问题可用三参数( d ，f ，f ) 表示，其中d 表示决策变量的 定义域，f 表示可行解区域f = xj x d ，g ( x ) o ，f 中的任意元素称为该问题 的可行解，f 表示目标函数。满足f ( x * ) - - - m i n f ( x ) x f 的可行解妒称为该问题 的最优解。组合最优化问题的特点是可行解的集合为有限点集。由直观可知， 只要将d 中有限点逐- - 笋f j 定是否满足g ( x ) 的约束和比较目标值的大小，该问题 的最优解一定存在和可以得到。因为现实生活中的大量优化问题是从有限个状 态中选取最好的，所以大量的实际优化问题是组合最优化问题。 在计算机学科中，存在多项式时间的算法的一类问题，称之为p 类问题 7 1 ； 而像梵塔问题、推销员旅行问题、( 命题表达式) 可满足问题这类，至今没有找 到多项式时间算法解的一类问题，称之为n p 类问题| 7 l 。 为了研究问题的复杂性，我们必须将问题抽象，为了简化问题，我们只考 虑一类简单的问题，判定性问题，即提出一个问题，只需要回答y e s 或者1 1 0 的 问题。任何一般的最优化问题都可以转化为一系列判定性问题，比如求图中从 a 到b 的最短路径，可以转化成：从a 到b 是否有长度为l 的路径? 从a 到b 蚂蚁算法在f s p 蛹题中的压用与研究 是否有长度为2 的路径? 从a 到b 是否有长度为k 的路径? 如果问到了k 的时 候回答了y e s ，则停止发问，我们可以说从a 到b 的最短路径就是k 。 如果个判定性问题的复杂度是该问题的一个实例的规模n 的多项式函数， 则我们说这种可以在多项式时间内解决的判定性问题属于p 类问题。p 类问题 就是所有复杂度为多项式时间的问题的集合。然而有些问题很难找到多项式时 间的算法( 或许根本不存在) ，比如找出无向图中的哈密尔顿回路问题，但是我 们发现如果给了我们该问题的一个答案，我们可以在多项式时间内判断这个答 案是否正确。比如说对于哈密尔顿回路问题，给一个任意的回路，我们很容易 判断他是否是哈米尔顿回路。这种可以在多项式时间内验证一个解是否正确的 问题称为n p 问题。显然，所有的p 类问题都是属于n p 问题的，但是现在的问 题是，p 是否等于n p ? 这个问题至今还未解决。注意，n p 问题不一定都是难 解的问题，比如简单的数组排序问题是p 类问题，但是p 属于n p ，所以也是 n p 问题，现在还不知道是否有p = n p 或者p n p ，但是后来人们发现还有一系 列的特殊n p 问题，这类问题的特殊性质使得很多人相信p n p ，只不过现在 还无法证明。 t s p ( t r a v e l i n gs a l e m a np r o b l e m ) 删问题可描述如下： 旅行商欲到n 个城市推销商品，每两个城市“j 之间的距离为d ”如何选 择一条道路使商人走一遍后回到起点且所走路径最短。t s p 问题可细分为对称 和非对称距离两大类问题。 用图论的术语来说，假设有一个图g = ( v ，e ) ，其中v 是顶点集，e 是边集， 设d = ( d i j ) 是由顶点i 和顶点i 之间的距离所组成的距离矩阵，旅行商问题就是求 出- 一条通过所有顶点且每个顶点只通过一次的具有最短距离的回路。这个问题 可分为对称旅行商f q 题( d i j = d i j ，任意i ，j = 1 ，2 ，3 ，n ) 和非对称旅行商问题 ( d i j ：# d j i ，任意i ，j = 1 ，2 ，3 ，n ) 。若对于城市v = v i ，v 2 ，v 3 ，v 。 的一 个访问顺序为t = ( t l ，t 2 ，t 3 ，t i ，t 。) ，其中t i v ( i = l ，2 ，3 ，n ) ，且 h s t + 。= ，则旅行商问题的数学模型为：d ( i ，f + 1 ) + d ( n ，1 ) t s p 问题，又称旅行商问题，是一卞典型的组合优化问题，并且是一个 n p 难问题，其可能的路径数目与城市数目n 是成指数型增长的，所以一般很难 精确地求出其最优解。目前，对t s p 问题的研究主要是通过一些启发式算法， 如遗传算法、禁忌搜索算法、模拟退火算法等，且都取得了一定的成果。本文 四j j ：弋学硕士擘住论文 中我们采用蚂蚁算法求其近似最优斛 1 。3 论文各部分主要内容 本文共分为六章，第二章介绍组合优化问题，并对当前常见的几种仿生优 化算法进行了简要的对比，同时给出了智能计算的简要介绍。第三章介绍了基 本蚂蚁算法的算法模型，着重介绍了基本蚂蚁算法的原理、系统学模型和数学 模型，并针对基本蚂蚁算法的具体实现提出了改进模型。第四章对基本蚂蚁算 法进行了分析，着重分析了算法中主要参数对算法性能的影响，算法的时空复 杂度，以及算法的收敛性。第五章给出了基本蚂蚁算法的几种改进思路。最后 第六章总结全文并对蚂蚁算法的应用前景进行了展望。本文的重点集中在第三 章和第四章。 蚂蚁算法在r s p 问题中6 应用与研究 第二章组合优化问题与仿生优化算法 2 1 组合优化问题与t s p 问题分析 伴随计算机技术的飞速发展，计算机正日益成为人们解决问题的不可或缺 的重要工具。但在实践中人们发现，存在这样一类问题，运用精确的算法在多 项式时间内无法找到问题的最优解，这类问题称为组合优化问题。这类问题通 常随着问题规模的扩大，问题空间呈现组合爆炸特征，求解问题的空间、时间 复杂度将呈指数级增长，使用常规的方法求解，在现有条件下是无法实现的， 属于n p 完全问题。旅行商问题就是其中最经典的问题之一。因此利用仿生进 化算法，在较短的时间内，求得问题的满意解，就成为许多学者研究的重点。 自然界一直是人类创造力的源泉，人类认识事物的能力就来源于与自然界 的相互作用之中。因此，仿生一直是人类创新的基本方式之一，而仿生进化算 法正是在这种认知方式下被提出来的。事实上，仿生算法模拟的正是自然界的 趋优机制，其目的在于利用自然界的高效优化方法解决工程实际问题。比如， 对人脑神经细胞结构与功能的抽象模拟构成的人工神经网络，寄希望通过人脑 处理复杂思维的高效性，获得处理复杂事务的方法。模拟生物遗传进化过程的 遗传算法，希望借鉴生命进化过程的复杂性来解决复杂现象中的优化问题。而 蚂蚁算法，则通过模拟现实世界中蚂蚁觅食的行为来求解复杂的组合优化问题。 总之，仿生进化算法是生物趋优机制的体现，是一种高效的趋优算法，应 用在一些复杂的优化问题上，取得了很好的结果，显示出其强大的生命力和美 好的发展潜力。 组合优化问题的目标是从组合问题的可行解中求出最优解。在现实世界里 存在大量组合优化问题，其中许多问题如旅行商问题、图着色问题、分配问题、 调度问题、布线问题及路由选择问题等，至今没有找到有效的多项式算法，这 些问题己被证明是n p 完全问题。 优化问题有三个基本要素：变量、约束和目标函数。在求解过程中选定的 基本参数称为变量，对变量取值的限制称为约束，表示可行方案衡量标准的函 数称为目标函数。组合优化问题就是在绘定的约束条件下，求目标函数最优值 5 四川大学硕士学位论文 的问题。组合优化问题的。个实例可以表示为一个对偶( ( s ，f ) ，其中解空间s 为可行解，目标函数f 是。个映射，定义为： f s 专r 求目标函数最小值问题称为最小化问题，记为： m i n 厂( f ) ，i s( 2 - 1 ) 求目标函数最大值问题称为最大化问题，记为： m a x 厂( f ) ，i s( 2 - 2 ) 显然，只要改变目标函数的符号，最小化问题与最大化问题就可以等价转 换。 使目标函数最优值的解称为最优解( 整体最优解) 。设( s ，d 是是组合优化问 题的一个实例。0 s ，称0 为最小化问题m i n f ( i ) ，i e s 的最优解，若： ( i o ) f ( i ) ，对所有的i s 成立 ( 2 3 ) 优化问题在工程中有着广泛的应用，其涉及的问题是在一组限制条件下求 解问题的最好( 或最优) 解的问题。按照人类认知问题的特点，最优化问题很自然 的被划分为两类：一类是连续变量的问题，另一类是离散变量的问题。对于离 散变量问题来说，一般是寻找离散事件的最优编排，分组，次序或筛选等。不 难看出，这些问题的解的个数是有限的。通常把这类问题称为组合最优化问题， 而研究用数学方法来求解这些问题就被称为组合最优化，它是运筹学的重要分 支之一。 一个算法的有效性可以用执行该算法所需要的各种计算资源的量来衡量， 最主要的两个资源就是所需的运行时间和存贮空间。算法或问题的复杂性一般 是问题规模r l 的函数，时间复杂性记为t ( n ) ，空间复杂性记为s ( n ) 。 算法执行期间占用的存贮单元定义为算法的空间复杂性1 8 】。但在算法分析和 设计中，人们通常总是将最快的算法与最有效的算法等同起来，这是因为时间 需求常常是决定某一算法在实际中是否真正有效的决定性因素。因此，在算法 复杂性研究中，衡量一个算法的效果，最广泛采用的标准是在产生最终结果前 它所花费的时间，并常称复杂性为时间复杂性。在组合优化问题中，比较和搜 索常被指定为基本操作。基本操作的执行次数随问题规模的增长以一定的方式 增长。 6 蚂蚁算法在l - 5 ；p 问题中6 应用与研究 在分析算法或问题的复杂性时，i i 以求出算法的复杂性函数f ( n ) ，也可以 方便的用复杂性函数主要项的阶o ( f ( n ) ) 表示。若算法a 的时间复杂性是 t a n ) = 0 ( j d ) ) ，p ( n ) 是n 的多项式函数，则称算法a 为多项式时间算法。 j e d m o n d s 称之为好的算法；时间复杂性不能囿于多项式的算法称为指数时间算 法。 算法的时间复杂性对计算机的解题能力( 速度和规模) 有重大的影响，以旅行 商问题为例，对此问题的直观的求解方法是穷举法，我们来考察需要的计算时 间。假设城市规模是n ，旅行商在起点时，可以选择( n 一1 ) 个城市进行访问，当他 访问完这个城市后，他可以选择剩下的( n 一2 ) 个城市进行访问，依此类推，当他 访问完第i 个城市后，他可以选择( n l - i ) 个城市进行访问，因此，需要进行( n 1 ) ! 的计算，每次计算，需要累加n 条访问路线的费用总和，所以，总的计算时间 是( n ! ) 。用运算能力为每秒一百万次浮点运算的计算机求解，在n = 1 0 时只需 0 1 8 s 。而在n = 2 0 时，需用1 9 2 9 年才能找到最优解。 按照计算复杂性理论研究问题求解的难易性，可把问题分为p 类、n p 类和 n p 完全类。 定义一：对于判定问题d ，存在一个多项式p ( r ) ，使得对其每一输入规模 为n 的实例，可以在p ( n ) 时间内求得最优解，此类问题称为p ( p o l y n o m i a l ) l h 题。 其它的则是n p ( n o n p o l y n o m i a l ) 问题。 假如一个问题是p 问题，我们通常认为它是“简单的”，而n p 问题，通常 认为它是“复杂的”。n p 问题是指可在多项式时间里检验的问题，至今尚未找 到多项式时间算法。在6 0 年代后期，人们认为大部分组合优化问题是属于n p 类问题。 7 定义二：若问题l e n p ，所有n p 问题都可以经过多项式计算时间转化为l 。 则l 称为n p 完全问题。 由于n p 完全竭题不太可能存在多项式计算时间内的算法，因此，近年来， 对n p 完全问题的研究逐渐向两个方向演化：一是寻求在多项式时间内求得具 有上确界解的算法；二是探索启发式的搜索算法，如仿生进化算法。而启发式 搜索算法已经应用在许多实际问题上，并取得了令人满意的结果。 旅行商问题是研究最为广泛的组合优化问题，它是最早被证明的n p 完全 问题之一。 四川大学硕士学位论乏 定义三：旅行商问题指一个旅行推销员，要到n 个城市去推销产品( 包括他 所在的城市) ，每个城市能且只能访问一次，然后返回出发点。从一个城市到另 外一个城市需要一定的旅行费用，应该如何选择访问的路线，才能使总的旅行 费用最低。 t s p 虽然是一个求最短环路的问题。但是在现实生活中，有很多实际问题 可以归结为t s p 问题。例如邮路问题就是一个t s p 问题。假定有一辆邮车要到 n 个不同的地点收集邮件，这种情况下就可以用n + 1 个结点的图来表示。一个 结点表示此邮车出发并要返回的那个邮局，其余的n 个结点表示要收集自5 件的n 个地点。由地点i 到地点j 的距离则由边( i ，j ) 上所赋予的成本来表示。邮车所 行经的路线是一条周游路线，希望求出具有最小长度的周游路线。 第二个例子是在一条装配线上用一个机械手去紧固待装配部件上的螺帽问 题。机械手由其初始位置( 该位置在第一个要紧固的螺帽上方) 开始，依次移动到 其余的每一个螺帽，最后返回到起始位置。机械手移动的路线就是以螺帽为结 点的一个图中的一条周游路线。一条最小成本周游路线将使这机械手完成其工 作所用的时间为最小值。 第三个例子是集成电路制造，在一块集成电路板上，往往容纳成千上万个 电器元件，在制造过程中，从一个元件移动到另一个元件需要消耗一定的能量， 应当如何安排制造的顺序，才能消耗最少的能量。这显然也可以转化为一个旅 行商问题来求解。 此外，像交通网络的线路分布、旅游线路的选择、城市规划及工程建设中 的管道网的铺设等问题都与寻找一个图的最短路径问题密切相关，因此对最短 路径问题的研究具有重要意义和实用价值。 2 2 仿生优化算法概述与比较 目前较为常用的仿生进化算法主要包括动态规划、人工神经网络【9 ( a r i t i f i c a l n e u r a ln e t w o r k ，即a n n ) 、遗传算法嘲( g e n e t i ca l g o r i t h m s ，即g a s ) 、模拟退 火( s i m u l a t ea n n e a l ，即s a ) 、禁忌搜索( t a b us e a r c h i n g ，即t s ) ，以及最近开发 出的蚂蚁算法t 9 1 ( a n tc o l o n yo p t i m i z a t i o n ，即a c o ) 等等。 研究表明，很多组合优化问题( 如旅行商问题) 都是n p 完全问题。这揭示了 蚂蚁算法在t s p 问题中的应用与研究 用多项式算法求解组合优化问题总是失败这一事实的深刻数学根源。对于n p 完全问题都有着这样的一个特征，就是其问题解空间是随着问题规模的扩大成 指数级数增长的。这种情况被形象的称为“组合爆炸”，它导致了求解该类问题 的多项式算法需要指数级的时间，这在实际中是不可行的。因此，对于组合优 化问题来说，只能借助启发式算法来求解，牺牲求解结果的精确性，换来求解 问题在时间上的可行性。 仿生算法是高效的启发方式算法，对求解组合优化问题是有效的。因此， 对仿生算法的研究在工程实际中也是有应用价值的。 在实际生活中，有这么一类问题，它们的活动过程可以分为若干个阶段， 而且在任一阶段后的行为都仅依赖于i 阶段的过程状态，而与i 阶段之前的过程 如何达到这种状态的方式无关，这样的过程就构成一个多阶段决策过程。2 0 世 纪5 0 年代，贝尔曼等人根据这类问题的多阶段决策的特性，提出了解决这类问 题的“最优性原理”，从而创建了最优化问题的一种新的算法设计方法一动态规 划。 在多阶段决策过程的每一阶段，都可能有多种可供选择的决策，但必须从 中选取一种决策。一旦各个阶段的决策选定之后，就构成了解决这一问题的一 个决策序列。决策序列不同，所导致的问题的结果也不同。动态规划的目标就 是要在所有容许选择序列中选取一个会获得问题最优解的决策序列，即最优决 策序列。最优性原理指出，过程的最优决策序列具有如下性质：无论过程的初 始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构 成一个最优决策序列。如果所求解的最优性原理成立，则说明用动态规划方法 有可能解决该问题。 从2 0 世纪6 0 年代起，随着人们对生物进化和基因的不断了解，一些学者 受到启发，提出了遗传算法。遗传算法其思想基础来源于生物进化论和群体遗 传学，是基于自然选择和基因遗传学原理的一种群体寻优搜索算法，具有良好 的鲁棒性和高度的并行性，特别适用于处理传统搜索方法难于解决的复杂和非 线性问题。如今其广泛应用于函数优化、模式识别、机器学习等各个方面，进 而扩展到生物、计算机、化学工程、工程力学、机械科学、系统工程等等多个 领域。其理论和应用的研究是目前人工智能领域的热门，大量的研究表明了其 在解决一些用常规解法难以求解的问题时具有不可替代的作用。 四1 1 i 大学硕士掌位论丈 遗传算法是一种借鉴生物界自然选择和自然进化机制的高度并行、随机的、 自适应性的搜索算法，其基本思想为：对求解的问题解空间实行遗传编码( 对应 于生物进化中的携带遗传基因的染色体) ，对编码进行选择交叉变异操作( 对应于 生物体的繁殖) ，用一个适度函数( 对应外界对生物进化的约束) 引导进化的过程， 直到成功获得问题的优良解。遗传算法是一种并行优化算法，尤其具有很大的 隐含并行性，在码空间以一定概率通过对种群的不断选择、交叉和变异操作达 到群体并行进化目的。遗传算法中，新状态或种群的产生是通过并行化遗传操 作实现的。其常用的遗传操作包括三个基本算子：复制、交叉、变异。这些操 作使得所要解决的问题从初始解一步步的逼近最优解。复制操作用于避免基因 的损失以提高全局收敛性和计算效率；交叉操作是g a s 区别于其它进化算法的 重要特征，用于组合产生新个体以实施解空问的有效搜索，并降低对有效模式 的破坏概率；变异操作用于增加釉群的多样性。这种方法求解优化问题，最主 要的特征就是：不在单点上寻优，而是从整个种群中选择生命力强的个体产生 新的种群；使用随机转换原理而不是确定性规则来工作。这神方法开创了在解 空间中从多出发点搜索问题最优解的先河。遗传算法在具体实施中有多种变形 和修正，可依照问题背景进行灵活运用。 遗传算法中参数的选取和设定比较复杂，而参数的选择和确定又对求解结 果有很大的影响。种群数影响算法的有效性，太d , n 不能提供足够的采样点而 导致较差的优化性能，反之则会增加计算量以致搜索时间过长；交叉操作的概 率太大会破坏高配值的个体，反之则使搜索停止不前；变异用以加大种群的多 样性，其概率太小难以产生新个体，太大则导致随机搜索。求解结果依赖于初 始参数的设定，这正是遗传算法在使用中存在的不足之处。 神经网络【l ”( n e u r a ln e t w o r k ) 是近年来再度兴起的一个高科技研究领域，是 信息科学、脑科学、神经心理学等多种学科近年来研究的一个热点。人工神经 网络是指模拟人脑神经网络的结构和功能，运用大量的处理部件，由人工方式 建立起来的网络系统。它是在生物神经网络研究的基础上建立起来的，人脑是 人工神经网络的原型，人工神经网络是对脑神经系统的模拟。 人工神经网络是由人脑的结构得到启发而建立的种仿生算法的模型。从 1 9 4 3 年心理学家w s m c c u l l o c h 和数学家w p i t t s 所提出的m p 模型【i ”开始， 经历了漫长的探索过程，在理论上不断的完善，在实际应用上也得到了进一步 o 蚂蚁算法在t s p 问题中的应用与研究 的扩展。实际上，神经网络的研究已有几十年的历史，但它的发展很不平衡， 直至1 9 8 2 年，美旧物理学家h o p f i e l d 提出人工神经网络模型，爿有力的推动了 神经网络的研究。他引入了“计算能量函数”的概念，给出了网络稳定性判据。 这种方法通过对神经网络引入适当的能量函数，使之与问题的目标函数相一致 来确定神经元之间的联结权，随着网络状态的变化，其能量不断减少，最后到 达平衡时，即收敛到一个局部最优解。 神经网络由一组基本元素或神经元构成，它们定向连接，并被赋予权重， ( 一般w ，。) 。在初始网络中，每个神经元i 要计算以下两个数值：( 1 ) 活跃水 平u 。= y w , x ，一0 。( 来自其它神经元的输入的权重总量减去一个初始数值 谚) ：( 2 ) 薯的输出：它通过一个有约束的、非减的、非线性函数而取决于活跃 水平“。网络根据转移规则经过连续的循环而进化。网络状态的计算是由每个 神经元局部的和独立的进行。当网络的状态不再发生变化时，网络就处于稳定。 并行性是神经网络模型的一个基本特征，最主要的特征是局部决策者( 神经元) 的单一行为和它们之间的连接结构( 网络的拓扑结构) 产生了复杂的、从某种意义 上说是“智能”的行为。 在组合优化问题中，神经网络可以近似的解决问题，它只需要对变量空间、 约束、目标函数的描述，而不需要任何清楚明确的代码程序。实质上，尽管a n n 只是人脑神经系统的一种简化，抽象和模拟，但它具有人脑神经网络处理问题 的特点，即分布存储，容错性和鲁棒性等等。正是这些特点使得其广泛应用于 模式识别、优化计算、智能控制、知识处理等多个领域的多个具体问题。实践 证明a n n 是一种良好的分布式并行处理算法，其应用大大推动了人工智能的发 展。 模拟退火算法是一种基于m e n t ec a r l o 迭代求解的全局概率型搜索算法，源 于5 0 年代，它首先是被用于在计算机上模拟固体的退火过程，8 0 年代才开始应 用于组合优化领域。这种模拟固体退火过程对算法进行迭代的组合优化算法， 称为“模拟退火算法”。 设组合优化问题的一个解i 及其目标函数f ( i ) 分别与固体状态i 及其能量邑 等价，令随算法进程递减其值的控制参数t 担当固体退火过程的温度t 的角色， 则对于控制参数t 的每一取值，算法持续进行“产生新解一判断一接受舍弃” 的迭代过程就对应着固体在某一恒定温度下趋于热平衡的过程。模拟退火算法 四川大学硕七擘住论文 从某个初始解出发，经过大量解的变换后，可以求得给定控制参数值时组合优 化问题的相对最优解。然后减少控制参数t 的取值，重复执行算法，就可以在 控制参数t 趋于零时，最终求得组合优化问题的整体最优解。模拟退火算法有 与m e t r o p o l i s 准则对应的转移概率p ，： 只( f j ) ( 2 】) e x p ( ：! ! ：- ! ! ：；业) 。历e n w 西e 确定是否接受从当前解i 到新解i 的转移。 模拟退火算法是一种串行优化算法，每步仅随机尝试当前状态邻域中的一 个状态，同时通过控制“温度”来控制状态更新概率，从而在搜索过程中具有 避免局部极小的能力并最终趋于全局最优。它的概率性的扰动能使之跳出局部 极值点，故而得到的解常常较好。 但模拟退火算法所得到的结果与初始温度、退温函数、状态产生方式、抽 样稳定准则以及在一定温度下邻域状态生成次数的函数形式等有关，在应用中 其往往受时间的限制仅能得到一个近似最优解，因此，为使这种近似解的优化 程度有所提高，近年来提出了与遗传算法、蚂蚁算法相结合的混合型启发式算 法。 蚂蚁算法是受到自然界中的蚂蚁行为的启发而提出的，是一种用于求解组 合优化问题的新型仿生进化算法。最初蚂蚁算法的思想来自蚂蚁寻找食物的行 为，最先提出的蚂蚁算法被称为蚂蚁系统( a n t s y s t e m ，a s ) ，它是d o r i g o ，c o l o m i ， m a n i e z z o 在意大利的米兰理工学院合作研究组合优化问题计算机智能解决方法 时的研究成果。 1 9 9 5 年g a m b a r d e l l a 和d o f i g q 提出了a n t q p 】算法。该算法建立了a s 与 o l e a r n i n g 的联系。模拟表明a n t - q 是一个非常有效的算法。 此后，d o r i g o 和g a m b a r d e l l a 提出了蚂蚁系统( a n tc o l o n ys y s t e m ，a c s ) f ”】， s t u t z l e 和h o o s 提出了最大最小蚂蚁系统( m a x - m i na n ts y s t e m ，m m a s ) 1 2 1 。 这两种扩展的蚂蚁算法都被用于解决对称旅行推销员问题( t s p ) 以及非对称型 的旅行推销员闻题( a t s p ) ，并取得了比较满意的结果。 1 2 蝎蚁算法在t s p 问题中的应用与研究 1 9 9 9 年，d o r i g o ，d i c a r o 和g a r n b a r d e l l a 把先前各种蚂蚁算法进行归纳总 结，提出蚂蚁优化元启发式算法( a n tc o l o n yo p t i m i z a t i o nm e t a h e u r i s t i ca c o ) t ”l 的概念，把此前各种基于a s 演化而得的算法归结到一个统一的框架中，并提 供了抽象而规范的算法描述，后来人们把它统称为蚂蚁优化算法。作为一种新 型的启发式算法，蚂蚁优化算法近年来受到了广泛关注。 自然界的蚂蚁在觅食过