（机械工程专业论文）蚁群算法及其在广义旅行商问题求解中的应用.pdf

蚁群算法及其在广义旅行商问题求解中的应用 摘要 旅行商问题是一个经典的图论名题，广义旅行商问题则更具有重要的工程 应用价值。对于旅行商问题，已有许多较成熟的求解方法，但对于广义旅行商 问题，这方面的报道却较少。 本文在深刻理解蚁群算法的算法原理、充分剖析蚁群算法程序的基础上， 分析了已有的各种广义旅行商问题求解策略和方法的优缺点，将用于求解旅行 商问题的蚁群算法扩展用于求解广义旅行商问题。 m ( 蚂蚁数量) 、q ( 信息启发式因子) 、1 3 ( 期望值启发式因子) 、p ( 信 息素残留系数) 、q ( 总信息量) 是蚁群算法的重要控制参数，这五个参数对算 法性能有很大影响，不仅影响算法的求解效率，而且影响算法的求解精度。本 文通过大量算例分析研究了它们对算法求解效率和求解精度的影响，用于指导 算法参数的最优选择 论文最终通过一个工程应用实例验证了所开发的广义旅行商问题蚁群算法 程序的正确性和实用性。 关键词：广义旅行商问题，蚁群算法，图论 a n tc o l o n yo p t i mi z a t i o n a p p l i e di ng e n e r a l i z e dt r a v e l i n gs a l e s m a np r o b l e m a b s t r a c t 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 lt h e s i si ng r a p ht h e o r y , b u tg e n e r a l i z e dt r a v e l i n g s a l e s m a np r o b l e m ( g t s p ) i sm o r ev a l u a b l ei ne n g i n e e r i n gp r a c t i c e f o rt s pt h e r ea r es o m ee f f e c t i v e m e t h o d st os o l v ei t ，b u tf o rg t s pt h e r ei so n l yf e wr e p o r ta b o u ti t a n tc o l o n yo p t i m i z a t i o n ( a c o ) c a n b eu s e df o rs o l v i n gt s p , i nt h i st h e s i si tw a se x t e n d e dt os o l v eg t s p , a n di t se f f i c i e n c yw a st e s t i f i e db y s o l v i n gat y p i c a lg t s pe x a m p l e m ( n u m b e ro fa n t s ) 、q ( h e u r i s t i cf a c t o ro fi n f o r m a t i o n ) 、b ( h e u r i s t i cf a c t o ro fa s p i r a t i o n ) 、 p ( p h e r o m o n e t r a i lp e r s i s t e n c e ) 、q ( q u a n t i t yo f t r a i l ) a r et h ei m p o r t a n t p a r a m e t e r so f a c o t h e yh a v e ag r e a ti n f l u e n c en o to n l yu p o nt h ee f f i c i e n c yo ft h ea l g o r i t h m ，b u ta l s ou p o nt h ea c c u r a c y c a l c u l a t i o n l o t so fe x a m p l e s ，t h er e l a t i o nb e t w e e nt h e s ef i v ep a r a m e t e r sa n dt h ec h a r a c t e r i s t i c so ft h ea l g o r i t h mw a s d i s c u s s e di nt h i st h e s i s ，i no r d e rt oc h o i c et h ec o r r e c tv a l u e so f t h e s ef i v ep a r a m e t e r s a tl a s t ，t h ea c op r o g r a md e v e l o p e di nt h i st h e s i sw a su s e dt os o l v eag t s pe x a m p l e ，w h i c hc o m e s f r o mt h ee n g i n e e r i n gp r a c t i c e ，a n di t sv a l i d i t yw a st e s t i f i e d k e y w o r d s ：g e n e r a l i z e dt r a v e l i n gs a l e s m a np r o b l e m ，a n tc o l o n yo p t i m i z a t i o n ，g r a p ht h e o r y 独创性声明 本人声明所呈交的学位论文是本人在导师指导下进行的研究一j ：作及取得的研究成果。据我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也不包含为获得 盒8 巴：! ：些厶堂 或其他教育机构的学位或证寸而使川过的材料。与我一同1 二 作的同志对本研究所做的任何贡献均己在论文中作了明确的说明并表示谢意。 神做作者魏铬聋镍签字吼坼，蝴彳日 签字日期：五缈年，蝴冲日 学位论文版权使用授权书 本学位论文作者完全了解盒蟹些r 火堂有关保留、使用学位论文的规定，有权保留劳向国 家有关部门或机构送交论文的复m i t - 和磁盘，允许论文被查阅和借阅。本人授权盒壁】：些厶堂可 以将学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手 段保存、汇编学位论文。 ( 保密的学位论文在解密后适用本授权书) 学位论文作者虢绀缘 导师签名： 签字日期：弘加一7 年j 瑚1 日 学位论文作者毕业后去向： 工作单位：合肥j 【：业人学机械与汽下 稃学院 通讯地址：安徽省合肥市合肥一r 业人学机汽学院 签字日期：妒7 年，l 月7 日 电话：2 9 01 3 3 9 8 4 0 5 i l i 口编：2 3 0 0 0 9 致谢 本论文是在我尊敬的导师吕新生教授悉心指导下完成的。吕新生教授严谨 求实的科学态度、渊博的专业知识、忘我的工作热情以及丰富的实践经验使我 受益匪浅，终身难忘。还有导师的正直、率性和朴实无华的作风在我心中留下 了不可磨灭的印象。我在攻读硕士学位期间所取得的每一点进步都离不丌导师 的指导和帮助。在这两年多时问内，导师不仅在学业上给予了我精心指导，而 且在生活上也给予了我无微不至的关怀。值此论文完成之际，谨向我的导师表 示衷心的感谢和崇高的敬意! 感谢c a d c a m 中心的陈科老师、王晓枫老师和曹文钢老师在我研究生期 问所给予的指导与关怀! 尤其是张晔老师扎实的理论基本功和丰富的实践经验 让我终身难忘! 感谢我的父母和爱人，感谢他们这么多年来对我无微不至的关怀，感谢他 们对我精神和物质上的支持，感谢他们为我无私奉献的一切! 作者：徐东镇 2 0 0 7 年12 月 第一章广义旅行商问题及其工程应用的背景 1 1 旅行商问题的描述及算法 1 1 1 什么是旅行商问题 旅行商问题( 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 ) 是一个经典的图论问题，也是 计算复杂性理论、运筹学、最优化理论等领域中的一个经典问题。 旅行商问题最早是在2 0 世纪2 0 年代由数学家兼经济学家k a r lm e n g e r 提出的。 t s p 的一般描述为：给定n 个城市及它们两两之间的旅行代价( 时间或距离) ，一个 旅行商从某一城市出发，访问各城市一次且仅有一次后再回到原出发城市，要求找出 一条最短的巡回路径，即：以旅行代价为距离，给定城市有限集c = c l ，c 2 ，c 3 ，c 。) ， 以及两两城市之间的距离氐( c i ，c i ) ，i j ，寻找一条经过所有城市并且只经过一次 的最短哈密尔顿( h a m i l t o n ) 圈。 旅行商问题( t s p ) 的描述虽然简单，解决起来却很困难。比如最简单思路是用 穷举法把所有可能的巡回路径全部列出来，最短的一个就是最优解，但这样只能处理 很小规模的问题。旅行商问题属于n p c o m p l e t e 问题，是n p ( 不定多项式， n o n d e t e r m i n i s t i cp o l y n o m i a l ) 题中最难的一类。如果有n 座城市，那么巡游路径共有 ( n 1 ) ! 2 条，计算的时间和( n 1 ) ! 成正比。当城市数n = 2 0 ，巡回路径有1 2 x1 0 博 种，n - - 1 0 0 ，巡回路径就有多达4 6 x1 0 1 5 5 种，而据估计宇宙中基本粒子数“仅仅只 有”1 0 8 7 个。由此可见，就现有的人类计算技术，对城市数达几十以上的旅行商问题 用这种精确计算的穷举法是不可能实现的。 1 1 2 旅行商问题实际意义和工程应用背景 旅行商问题具有重要的实际意义和工程应用背景。它最初是为交通运输而提出的， 比如飞机航线安排、送邮件、快递服务、设计校车行进路线等等，实际上其应用范围 可扩展到许多其它领域，例如：印制电路板钻孔是t s p 应用的经典例子，在一块电路 板上打成百上千个孔，钻头在这些孔之间移动，相当于对所有的孔进行一次巡游。把 这个问题转化为t s p ，孔相当于城市，孔到孔之问的移动时间就是距离。此外，旅行 商问题还有电缆和光缆布线、晶体结构分析、数据串聚类等多种用途。更重要的是， 它提供了一个研究组合优化问题的理想平台。很多组合优化问题，比如背包问题、分 配问题、车问调度问题，和t s p 同属n p c o m p l e t e 类，它们都是同等难度的，如果其 中个能用多项式确定性算法解决，那么其它所有的n p - c o m p l e t e 类问题也能用多项 式确定性算法解决1 1 1 1 2 。 随着算法研究的逐步深入和计算机技术飞速提高，对t s p 问题的研究不断取得进 展。现在已有的t s p 求解方法可以分为两大类，一类是精确算法，目的是要找到理论 最优解；另一类是近似算法，不强求最优解，只要找到“足够好”的满意解就可以了。 1 1 3 旅行商问题精确算法 如前面所述，穷举法和全局搜索算法属于精确算法，穷举法计算量太大不可能实 现。1 9 5 4 年，g e o r g ed a n t z i g 等人用线性规划【3 】的方法取得了历史性的突破，解决了 美国4 9 个城市的巡回问题。这就是割平面法和分枝限界法，它们在整数规划问题中 也得到广泛运用。 ( 1 ) 割平面法【4 】。 割平面法是由高莫瑞( r e g o m o r y ) 提出的，故又称为g o m o r y 的割平面法。它的 基本思想是：不断增加线性约束条件( 几何术语称为割平面) 将原规划问题的可行域切 割掉一部分，使其切割掉的部分只包含非整数解，没有切割掉任何整数可行解，直到切 割后得到的可行域有一个整数坐标的极点恰好是问题的最优解为止。 ( 2 ) 分枝限界法【5 】。 分枝定界法是由l a n dd o i g 和d a k i n 等人提出的。该方法灵活且便于用计算机求 解。可用于解纯整数或混合的整数规划问题。其核- t l , 是“分枝”和“定界”。它的基 本思路是：设最大化的整数规划问题为a ，相应的不含整数约束的线性规划为b ，若 b 的最优解不符合a 的整数条件，那么b 的最优目标函数值必为a 的最优目标函数值 z 的一个上界，记作z ；而a 的任意可行解的目标函数值将是z 的一个下界，记作z 。 对b 的非整数解的相邻整数作附加条件，从而形成两个分枝，即两个子问题，两个子 问题的可行域中包含原整数规划问题的所有可行解。不断分枝，逐步减小z ，增大量， 最终求得z 。 总的来说，精确算法比较复杂，要写很长的代码，而且计算量仍然很大。 1 1 4 旅行商问题近似算法 大多数情况下只要能求得满意解就可以满足要求了。用近似算法得到的满意解和 最优解往往只差几个百分点，和精确算法相比，近似算法比较简单，计算量减少很多， 大致可分为三类： ( 1 ) 巡回路径构造算法【6 】。 这种算法是把城市一个一个地加入到路径中去，全部加进去以后就得到了一条巡 回路径。最简单的巡回路径构造算法是贪婪算法，每次选择最小的一条边，但是最后 要把起点和终点连起来，最后这条边往往会很长，所以找到的是一个很“粗糙”的解。 此外，还有插入法【7 】、双最小生成树法 8 1 、c l a r k & w r i g h t 法等。 ( 2 ) 巡回路径优化算法【9 j 。 也就是局部搜索算法，搜索一个解空问邻域里的最优值，先产生一条初始巡回路 径，再改变其中某些城市的顺序，使路径优化，逐渐接近最优解。 ( 3 ) 智能算法。 所谓智能算法，是指2 0 世纪以来借助自然界的规律，根据其原理设计的算法，如 模拟退火u o 、遗传算法 i h 、神经网络u 2 、蚁群算法等u 3 1 。 模拟退火算法( s a ) ，它是局部搜索算法的一种扩展，根据复杂组合优化问题与固 体退火过程之间的相似之处，在它们之间建立联系。退火过程中，固体最终达到能量 最小的状态，对应于模拟退火算法找到最优解。与局部搜索算法不同的是，模拟退火 算法随机接受一些劣解，这样就有希望从局部最优解中跳出，找到全局最优解。 遗传算法( g a ) 是根据自然界的“物竞天择，适者生存”现象提出的一种随机搜索 算法。把一定数量的解作为一个群体，通过选择、交配和变异把适应性强的染色体( 对 应为t s p 中较好的一些边) 遗传下来，使解进化( 优化) 。 人工神经网络( a n n ) 是对人脑神经系统的仿真，具有并行性、容错性、学习能力、 知识存储等优点。 蚁群算法( a c a ) 是模拟蚁群行为的一种仿生算法。蚂蚁个体能力很低，却可以协 同工作，集中食物，建筑蚁穴，依靠群体智能发挥出超出个体的智能。每只蚂蚁单独 完成巡游，并通过信息素交流，最终都聚集到一条局部最优路径上来。 1 2 广义旅行商问题及其工程应用背景 1 2 1 广义旅行商问题的描述 上世纪六十年代，h e n r y - l a b o r d e r e 、s a k s e n a 和s r i v a s t a v a 又几乎同时提出了广义 旅行商i b 题 1 4 l ( g e n e r a l i z e dt r a v e l i n gs a l e s m a np r o b l e m ，简称g t s p ) ：给定m 个城 市集合( 每个城市集合中包含数量不等的城市) 以及两两城市之间的距离，一个旅行 商从某一城市出发，在每个城市集合中只访问其中一个城市后再回到原出发城市，要 求找出一条最短的巡回路径，即：给定由i t l 个子集组成的城市集v = v 1u v 2 u v 3 u - v m ，且v i n v j = 中，i j ，寻找只经过每一城市子集中一个城市的最短h a m i l t o n 圈 ( 图1 1 ) 。 图1 1 广义旅行商问题图示 1 2 2 广义旅行商问题工程应用价值 广义旅行商问题具有更为重要的工程应用价值，例如在数控板材切割下料过程中， 将不同形状的料片安排在同一块板材上套裁，每个料片的轮廓上具备有限个节点可以 作为切割起始点( 由于待切割轮廓的封闭性，因此同时也是该料片的切割终止点) ， 那么，切割过程中的空走刀路径优化就构成一个广义旅行商问题。这一问题同样存在 于皮革行业的下料和服装业的裁剪。此外，还可用于客户寻求服务的行程安排问题、 循环物流系统设计、随机车辆调度、路径规划、邮箱取信问题、三方服务代理问题等。 1 2 3 现有的广义旅行商问题求解方法 对于旅行商问题，前面已提到有许多较成熟的求解方法，但对于广义旅行商问题， 这方面的报道却较少。文献 1 4 】中提出一种将广义旅行商问题转化为旅行商问题求解 的方法；还有将基于广义染色体的遗传算法用于广义旅行商问题的求解【1 5 】；本文则直 接将用于求解旅行商问题的蚁群算法扩展成为可以成功求解广义旅行商问题的算法。 4 第二章蚁群算法的基本原理及其在t s p 问题中的应用 2 1 蚁群算法( a n tc o l o n yo p t i m i z a t i o n ，a c o ) 的由来 为什么小小的蚂蚁能够找到食物? 它们具有智能么? 如果我们要为蚂蚁设计一 个人工智能的程序，那么这个程序要多么复杂呢? 首先，你要让蚂蚁能够避丌障碍物， 就必须根据地形编制指令让它们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物， 就需要让它们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路径，那么需要 计算所有可能的路径并且比较它们的大小，这是多么不可思议的复杂程序! 恐怕 没人能够完成这样繁琐冗余的程序。 2 1 1 协调蚁群复杂运动的六条简单规则 然而，事实上并没有那么复杂，每只蚂蚁并不是像我们想象的那样需要知道整个 世界的信息，它们其实只关心很小范围内的眼前信息，而且根据这些局部信息利用几 条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。 这些简单规则有如下六条： ( 1 ) 、范围： 蚂蚁观察到的范围是一个用速度半径为定义参数的方格世界，如果速度半径为 3 ，那么它能观察到的范围就是3 * 3 个方格世界，并且能移动的距离也在这个范围之 内。 ( 2 ) 、环境： 蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素， 信息素有两种，一种是找到食物的蚂蚁撒下的食物信息素，一种是找到窝的蚂蚁撒下 的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息，而环境又以一定的速率 让信息素逐渐消失。 ( 3 ) 、觅食规则： 在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有 信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的 地方走；同时，每只蚂蚁又多会以小概率犯错误，因而有时并不是往信息素最多的点 移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素作出反应，而对食物信息 素不作反应。 ( 4 ) 、移动规则： 每只蚂蚁都朝向信息素最多的方向移，当周围没有信息素指引的时候，蚂蚁会按 照自己原来运动的方向惯性的运动下去，并且在运动的方向有一个随机的小的扰动。 为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经 在最近走过了，它就会尽量避开。 ( 5 ) 、避障规则： 如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，如果有信息 素指引的话，它会按照觅食的规则行为。 ( 6 ) 、播撒信息素规则： 每只蚂蚁在刚找到食物或者窝的时候播撒的信息素最多，并随着它走远的距离， 播撒的信息素越来越少。 。 2 1 2 关联蚂蚁的信息素 根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互， 通过信息素这个纽带，实际上把各个蚂蚁关联起来了。 比如，蚂蚁究竟是怎么找到食物? 在没有蚂蚁找到食物的时候，环境没有有用的信息素，那么蚂蚁为什么会相对有 效地找到食物呢? 这要归功于蚂蚁的移动规则，尤其是在没有信息素时的移动规则。 首先，它要能尽量保持某种惯性，这样使得蚂蚁尽量向前方移动( 开始，这个的方是 随机确定的一个方向) ，而不是原地无谓的打转或者摆动；其次，蚂蚁要有一定的随 机性，虽然有了固定的方向，但它也不能像粒子一样直线运动下去，而是有一个随机 的干扰。这样就使得蚂蚁运动具有了一定的目的性：尽量保持原来的方向，但又有新 的试探，尤其当碰到障碍物的时候它会立即改变方向，这可以看成一种选择的过程。 这就解释了为什么单个蚂蚁在复杂的诸如迷宫的地图中仍然能找到隐蔽得很好的食 物。 然后，在有一只蚂蚁找到了食物的时候，它并没有直接告诉其它蚂蚁这儿有食物， 而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在， 进而根据信息素的指引找到了食物。 再比如，蚂蚁如何找到最短路径的? 这要归功于信息素，另外要归功于环境。信息素多的地方显然经过这早的蚂蚁会 6 多，因而会有更多的蚂蚁聚集过来。假设有两条路从窝通向食物，开始的时候，走这 两条路的蚂蚁数量同样多( 或者较长的路上蚂蚁多，这也无关紧要) 。当蚂蚁沿着一 条路到达终点以后会马上返回来，这样，短的路蚂蚁来回一次的时i 、日j 就短，这也意味 着重复的频率就快，因而在单位时间罩走过的蚂蚁数目就多，撒下的信息素自然也会 多，自然会有更多的蚂蚁被吸引过来，从而撒下更多的信息素：而长的路j 下相反， 因此，越来越多地蚂蚁聚集到较短的路径上来，最短的路径就近似找到了。 当然，这会有局部最短路径和全局最短路径的问题，实际上蚂蚁会逐渐接近全局 最短路径的，这源于蚂蚁会犯错误，也就是它会按照一定的概率不往信息素高的地方 走而另辟蹊径，这可以理解为一种创新，这种创新如果能缩短路途，那么根据刚才叙 述的原理，更多的蚂蚁会被吸引过来。 2 2 蚁群算法的描述 2 2 1 蚁群算法基本原理图示的描述 基于上述蚁群活动的原理，d o f i g o ，m e n i 和c o l o n u 等人于2 0 世纪9 0 年代提出 了蚁群算法，其基本原理如图2 一l 所剥1 6 】。 蒯d - - - i c 蒯j _ i 1 5 触5 如l c h d 峨5 d t l 1 5 d - - 0 3 示仍 伽o 时弼弘0 时封 图2 1 蚁群系统示意图 设a 是蚂蚁的巢穴，e 是食物源，h c 为一障碍物。由于存在障碍物，蚂蚁只能 绕经h 或c 由a 到达e ，或由e 到达a 。各点之间的距离如图2 所示。假设每个单 位时间有3 0 只蚂蚁由a 到达b ，又有3 0 只蚂蚁由e 到达d 点，蚂蚁过后留下的信 息素为1 ( 假设信息素的停留时间为1 ) 。在初始时刻，由于路径b h ，、b c 、d h 、d c 上均无信息存在，位于b 和d 的蚂蚁可以随机选择路径。从统计学的角度可以认为 它们以相同的概率选择b h ? b c ，d h ，d c 。经过一个时问单位后，在路径b c d 上的信息 量是路径b h d 上的信息量的2 倍。在t = l 时刻，将有2 0 只蚂蚁由b 和d 到达c ，有 7 1 0 只蚂蚁由b 和d 到达h 。随着时间的推移，蚂蚁将会以越来越大的概率选择路径 b c d ，最终完全选择路径b c d ，从而找到由蚁巢到食物源的最短路径。 2 2 2 解决t s p 问题的蚁群算法数学模型 由于蚁群寻食的过程与旅行商问题( t r a v e l i n gs a l e s m e np r o b l e m ，t s p ) i 拘求解非常 相似，所以蚁群算法最早的应用就是t s p 问题的求解，下面以求解n 个城市的t s p 问题对蚁群算法的数学模型进行描述，先引入如下符号： m ：蚁群中蚂蚁的数量； d i i ：城市i 、j 之间的距离( i ，j = 1 ，2 ，n ) ： t 1 i i ：蚂蚁由城市i 转移到城市j 的期望度，可以由某种启发式算法确定。在 t s p 问题中，ni j = 1 d i i ，称之为能见度； 下i i ( t ) ：t 时刻在i j 连线的路径上残留的信息量； p k i i ( t ) ：t 时刻蚂蚁k 由城市i 转移到城市j 的概率； t 时刻，蚂蚁k ( k = 1 ，2 ，m ) 在城市i 处选择路径时按概率p k i i ( t ) 决定转移 方向，即： 当i 属于蚂蚁k 下一步允许选择的城市时： p k i j ( t ) 2 器 当i 属于蚂蚁k 下一步不允许选择的城市时： p k i i ( t ) 2o 其中：指数q 表示残留信息的相对重要程度；指数1 3 表示期望度的相对重要程度； 在初始时刻各条路径上的信息量相等，设ti i ( 0 ) = c ，经过n 个时刻蚂蚁完成 一次循环后，各条路径上的信息量根据下式进行调整： to ( t + n ) = ( 1 一p ) t u ( t ) + ti j ( 2 ) at0 = z t 。i i( 3 ) 其中：ti i 表示本次循环中所有经历过路径( i 、j ) 的蚂蚁留在该路径上的信息 量的增量，用参数卜p 表示信息素的消逝程度，为防止信息的无限积累，通常设置 0 一 oo 一一 卜 廷 寸n 割 u 、。 n 寸 n一 竖 c , l心口 剥 昏昏口心 t l n 心心 一 v 、 t q一 一 t - i 一 一 心 寸n口 竖 卜v 、o 割 全noo nv 1 nn一 一 竖 nnn 剖 西卜卜西 n舍西 i nn no 。o呐 n 一 一寸 卜 v 、 竖 卜、寸n 一 v 、 口h 剥 n o 。v 、 o 一 一 p qnl ，、 t 4n一n 竖 口西 仉 口 no寸 口 i n nno 。 n 一 寸 一 岔 一 口卜 一 口口 一 n卜卜卜nn 剖 n岔nu 、 n卜n n 中 一 卜卜口n寸口o一n卜卜n心 n卜。气r v 、 口寸onoo寸 o o口 o 。n no o o卜o 。小n 一一一 nn口u 、n寸n卜j c 、 一 v 、nnc - - 1t - - , if - 1f qno - , 寸- 卜 卜 卜 nn口口 卜卜、卜卜 寸 十 中 n卜 一小 坚 n r 、寸t nf _ - - 1卜u 、 u 、nv 、 寸 nr - 一 f - , i ，寸 寸i n寸o0 0on o 。 割 o卜 口 口岔 ooooo卜口 口o o全 。心 n卜 一口一 n一o 。o 。 i no也 口口 一 。o 。 寸。o口口寸o 一n口 。n 寸 、n n n一 一一一一 nn nt , - , lo 。n nn n一n寸 一 f - i 竖 c - i心呐口nn o寸n nt q“ 一 斟 o寸口 一 口 一 口口 卜 一 口、中 n口 n。 卜卜t - -n卜 o卜 n卜n小。 卜卜 卜口 hn心 nv 、 t 寸o oo - , 卜卜卜 n口 n卜o弋r口寸onoo寸。o 口口 n no o o卜。on卜 一一 t nnc 、j口no on寸nc , lc 、jn一nt - nnt nt - - 4nc - in口 n 坚 r _ 1卜卜岔n n卜卜寸寸卜仉n 中l nn口 卜nnv 、t - - 中“n寸 中t 寸f - - i口v 、口n nn一n 一 割o岔 o o 。 一 卜an o口口岫n卜r 、nmo - , 于n卜nnc - io o no 。 no oov 、o 。 凸o一 一 n寸寸 n 中o 。o一r 、 寸卜 寸h寸t 寸- 一 nnr 一、nn n no 。t t 寸 寸n n寸nn n 竖 c _ - - 1 f - i心 小t - inn一n“ 口 割 on口r 、。o口口口口凸寸卜、rn 、on卜 卜 一 卜 寸 n 卜o 。 on no 。 卜 岔 口 一 n o 一 r 、卜o o。卜卜小卜 一 口口 口 们 一 一 o o口o oo n o卜o口口 一 t qno 。o寸 r 、nn口 一n n一 一一 o 。帆 一一 “n一 一 i ，、n一 一n nn 1 口 t - , l 竖 卜卜卜岔mn卜r - -寸t r卜n n nnn n 中i nn n口 刮 n nnu 、r 、寸o 。nf - - 1寸寸寸寸口n口n nn n、onc - i 一 口 一 卜凸n o口小。n卜r 、寸、n寸o nh卜 一 n o。 n ono 。口o一 一 o 。o寸p 、寸o n一心c - , int 十 十 n寸 寸 一 一 nn np n n n一寸寸 中 hn寸nt - in一 竖 全on岭口o全r q沿 u - 3 一 谚o、o 一 onr 、口 口小寸卜 口 一 v 、 n心口 口 割 口n n。o nc - i 一 o 。 一 。r 、卜。o 。o 。 卜卜 一 n一 口on 一 n o一 oo口 o oon or 、o口 一 n nt - , in寸r 、o o一 一 n n一 一一 一一 f 、qc , l一 一n n 一nc - i寸 1 寸 。 竖 卜卜 卜 卜 ，、r q心口o崞卜卜n n n卜寸寸n 中 卜 心口n岔 剥 n中 一 nr 、n仉t n们 寸川 r 、卜寸n中寸nl n寸r 、nv 、o 一 t - -口 口口o o oo。 卜 凸口口 n小 口o仉 卜ono 。一 v 、 口 o心 一 o oa 。oa口o一 一 f - , i口v 、n 寸nn“ 一一 一一 p 1nt - - ic - - 1 一 mnnnnht t 一n 。n n寸 n口卜、 om寸l ，、 nf 寸n口卜 o o昏 一 - 一一 一 一 一 - 一 一 n nnn“ n o 鼍爵#芒h喜姑 一认懈 n- n卜n口 卜nn口 一 o 。小 中n n n o一 o卜 n呐n卜卜 口 一 n寸 一 卜 一 n卜西n一岔 o 。u 1 口口 u 。o n时 口 一 n 一n卜 n o卜n卜口寸 v 、 中t 寸口 凸onf 、|r 、卜o 。nnl nno on on一卜 一 nn。 n 一n卜 nn nn n nn一 岔 n n n nn一 一 一 n n nn岔n口心no o。n口寸 n卜 口 v 1 n o寸nn口寸。口n o口i ，、n口n寸寸寸n n。o心n n o心 卜 口口no口寸o n 十 一 no口 一 卜口口o nt 中 、 一 ot 中 o寸 一 n oni ，、 一 寸n n nni - no o n n卜 一一 一 n n寸 寸 t 中寸寸寸寸寸中 t 中n一 一 一 o 。n 岔西 卜 卜 口凸 、n 寸 一 n岔n口 蝤卜寸卜nn凸 一 n卜o口。口口nn一- n寸 n n卜f - i口 o 。v 、n口 o 。 一n o一 n n卜 n o卜 卜 寸 oon卜卜口 i n卜 n、on nnoo口n o o一寸口凸 f - , 1n。n n n nnt - in一 一 o 。 一 nn寸 n寸 一一一一一n 口 口一 也岔t - , l寸寸口 一 口卜寸n一 v 、 寸n口 岔卜、寸口nn一、n一i - , 1 一 口卜 一一 寸 o 。 l ，、n一西口t - - q o口 一 十on寸n 一 口 一 卜oo 。n n寸岔t 中n n 一 n一寸寸n口 n 一 n。 n寸ot tnnc , ln卜o o n 卜 一一 一一 nt - - - in寸十寸寸寸寸 寸 寸甘n一 卜 一一 卜h nf - i口凸n卜岔o 。 v 、 寸 一 卜v 、n口卜 岔o寸 口 n一 寸o卜 卜 一 口 no 。n non n n卜 口 卜 n 口o 中ono寸口 。卜 n卜 一 v 、 o一n n n。o岔中nv 、n n岔n岔 卜口 一 c - 4n 一 寸 中o。t - , in卜o nt - i卜n nt - - in nn nt - i 一一 口 一 n一、 中n一 一一一一 寸 口 岔n小 凸 一 口no on卜口 一一n n 一 口卜 一 寸寸r 、 一 寸凸寸 o o n口n寸n nc - - i寸 。o口 n凸 no岔n n卜、 nn卜 一 o n卜卜n n oo n一no o卜n一 o 中n寸 一 n 中onnn hn寸 n n ， n 一一一 一 一 n n 寸寸 中 寸 寸 寸寸 寸 t 寸 t - , i 一 o 。 口西 卜卜n o 。 n凸、on 也 岔 n一 一 n口 一 n 一 n一 o一一 o卜nv 、 一一 oi nn口 一 口 一咕 v 、 t 寸 一一 寸卜 口卜 o 卜卜 岔 口岔 卜口卜 一一 卜 口 f - - i。 口口 卜。 o一 十nn卜n口寸寸寸n一 一 o寸。口1 寸 一o一 n口口n n ni ，、nn n n ni - - in( - 1一 一一 n一 一 v 、 卜 一一 一一n n1 - - 1n凸n一 卜n n n卜寸弋卜 口 寸 n t t 。口 口卜 o寸oo 。口n呐 十口卜寸n n n nt 中 o崞o口o n n o 一一 v 、n o o o n一 卜。on卜 一 f 、口 n nnn 卜 oc - innn n弋ro n一n寸 n o寸 v 、 寸岔 一 一 一一 nt - i 寸 寸寸 中t 寸寸 寸- 寸 寸寸n一 卜o oo卜n n n 中n卜昏 n一 n口 心 一 口 一 卜寸 寸n卜 一 。on口oo 。寸 p 、 口中t - q口l ，1寸 一 卜卜 西 卜 。 寸口o卜卜 nr 、n卜 n 一一 o卜 一 i m。 岔o寸on卜也 - n寸 寸n一 一 o寸。 一 卜 一 岔n寸卜口寸 一 ni nn nr - , in nf - inf - i 一一一 n n一n寸卜西 一一一一 t - - i n n nn全 n岔 一 卜n寸卜n 中口 n口寸n n 口 。o卜口卜 o o寸1o n卜卜n西寸卜 寸 一 o 。 o心。o口or t m t 十o 一 n n o一 on o。o n n。 nn i nn寸ho 。卜口nn一o。n n一寸 一 寸o n一n 中口 一一一 n一寸寸 中寸寸寸寸寸寸 中n一 一一 口 卜 n 寸“n口n卜寸n小n卜寸n 凸小t -寸n n卜n一 no卜寸 l ，、 一 o 。 气r卜v 、 nn卜 o 。 一 卜 口 n 崞 卜 卜 口 卜口。n口口n一n卜n o一 。o岔寸 口o。o n卜卜 non仉 n n口n on卜 n卜 一 nv 、 卜 o 一 卜n n nnn nn n一 一 口 一 n nn n n西 一一 一一n 寸寸n岔 一 nt 十nv 、寸卜n一 岔 n 中 一 口nn寸 卜 v 、 卜卜卜o一口nn一n卜h口n一r 、卜凸n 。 o 寸o。岔n寸 寸 一 o 。 o hn寸 卜 - n 一 寸 一 on一 卜。寸o。 一 一 。寸 一 not l 叽 一 寸 一n 十 寸 卜 卜。 一 寸 卜 一 一 一一 n n寸寸寸 中 寸中寸弋r寸寸n一 一 o 。 口 一 。n 崞 r 、o 。凸 on 寸nr 、o 。 凸o一 nn寸n 卜 口 o一 n n nn n h n n nn n、n，、十寸寸寸寸寸寸 寸寸寸n 第六章总结与展望 6 1 完成的工作 旅行商问题是一个经典的图论名题，上世纪六十年代提出的广义旅行商问题则更 具有重要的工程应用价值，例如数控板材切割下料、皮革行业的下料和服装业的裁剪， 以及客户寻求服务的行程安排问题、循环物流系统设计、随机车辆调度、路径规划、 邮箱取信问题、三方服务代理问题等，在一定条件下都可以抽象为广义旅行商问题。 对于旅行商问题，已有许多较成熟的求解方法，例如动态规划法、分支定界法、 遗传进化法、蚁群算法、模拟退火法、神经网络法等。但对于广义旅行商问题，这方 面的报道却较少，已知的有如将广义旅行商问题通过顶点转换变为旅行商问题来解 决；还有如用数次蚁群搜索加数次最近邻迭代取得优解；再有如用基于广义染色体的 遗传算法来求优解。 本文分析了已有的各种广义旅行商问题求解策略和方法的优缺点，在深刻理解蚁 群算法的算法原理、充分剖析蚁群算法程序的基础上，将基本蚁群算法扩展成为可以 成功求解广义旅行商问题的算法，以得到一个相对简洁和有较高精度及效率的解决方 案；并通过大量算例分析研究了m 、q 、1 3 、p 、q 这五个参数对算法求解效率和求 解精度的影响，用于指导算法参数的最优选择；最后通过一个工程应用实例验证了所 开发的广义旅行商问题蚁群算法程序的正确性和实用性。同样，这一算法也适用于旅 行商问题的求解。 6 2 存在的问题与工作展望 由于广义旅行商问题广泛的实际应用背景，在未来相当长时间内，g t s p 仍将是 算法研究领域的一个热点问题。但是除非有新的解决组合优化问题的算法框架出现， 各种仿自然的算法结合局部优化的算法思想仍将是研究的热点。结合实际问题设计适 当的操作算子和局部优化策略以构造混合算法仍将是解决g t s p 的重要途径。 同时在研究中我们发现，蚁群算法( a c o ) 作为模拟生物习性、自组织的算法， 它具有正反馈性，较强的鲁棒性，而且本质上是并行的算法，但现在进行的研究还停 留在仿真阶段，关于算法的严格数学解释和完整的理论体系尚未正式形成。而且也存 在一些缺陷，首先算法需要较长的搜索时间，其次蚁群算法的解易于陷入局部而非全 局晟优之中。 本文的主要解决方式除了对算法的优化外，还要对1 1 1 、a 、1 3 、p 、q 五个参数 进行优化设置，其不同的参数值对算法的精度和效率影响很大，而其参数的设置没有 理论上的依据和一种有效的数学分析方法，使不同情况下的蚂蚁系统都能生成最优的 参数，通常是根据经验和实验而定。这种方式在对不同规模和要求的广义旅行商问题 进行解决时，其局限性也是显而易见的。 要解决这些问题，我们认为下一步的研究主要包括以下几个方面： ( 1 ) 、进一步研究真实蚁群的行为特征，对真实蚁群的深入研究有助于发展和改 进a c o 算法。 ( 2 ) 、a c o 算法应用领域的拓展和其它相关学科的交叉研究，应将该算法引入 更多的应用领域，并与相关学科进行深层次的交叉研究。 ( 3 ) 、基于a c o 算法的蚂蚁智能体硬件的研究，随着对a c o 算法研究的丌展， 对实现算法功能的硬件研究应有突破。 ( 4 ) 、研究a c o 算法的并行实现，如何实现蚁群之间的通讯以及蚁群的调度是 并行实现的关键。 参考文献 【1 】旅行商问题概述【j 】大众科技，2 0 0 6 ，( 0 8 ) 2 陈文兰，戴树贵旅行商问题算法研究综述 j 】滁州学院学报，2 0 0 6 ，( 0 3 ) 【3 】c a r p a n e t og ，t o t hp s o m e n e w b r a n c h i n ga n db o u n d i n gc r i t e r i af o rt h ea s y m m e t r i c t r a v e l i n gs a l e s m a np r o h l e m j m a n a g e m e n ts c i e n c e ，19 8 0 ，( 2 6 ) 【4 】4d a n t z i ggb s o l u t i o no fal a r g es c a l et r a v e l i n gs a l e s m a np r o b l e m j o p e r a t i o n s r e s e a r c h ，19 5 4 ，( 2 ) 5 】b e l l m a nr 。d y n a m i cp r o g r a m m i n g t r e a t m e n to f t h e t r a v e l i n g s a l e s m a n p r o h l e m j ，j a c m ，1 9 6 2 ，( 9 ) 6 李祚泳等：基于蚁群算法的两地之间的最佳路径选择【j 】，系统工程，2 0 0 4 年第7 期 7 】陈继业，张君，求解旅行商问题的一种改进算法 j 邵阳学院学报( 自然科学版) ， 2 0 0 6 ，( 0 1 ) 【8 】姚建华，杨成涛用最小生成树解决t s p 问题 j 】湖北师范学院学报( 自然科学版) ， 2 0 0 4 ，( 0 4 ) 9 】刘剑平，关于旅行商问题的若干启发式算法的性能比分析 j 】华东理工大学学报， 2 0 0 5 ，( 0 6 ) 1 0 谢秉韶，李良，郭耀煌求解配送集旅行商问题的模拟退火算法 j 系统工程理论 方法