用蚂蚁算法解决多目标TSP问题.doc

《用蚂蚁算法解决多目标TSP问题.doc》由会员分享，可在线阅读，更多相关《用蚂蚁算法解决多目标TSP问题.doc（5页珍藏版）》请在三一文库上搜索。

1、维晋资讯 劭肌卷第10期小型微型计算机系竦Vol. 24 No. 102003 年 1。月MINI-MICRO SYSTEMSOct. 2003用蚂蚁算法解决多目标TSP问题游道明*陈坚I上海瓷通大学.±W 200030)M 要：事析了萝目标冋题的桂履，提由一种在萝个国标间杖菊的许价柑标.用一种鞍斷的进化算诧*駁算塞来齋决 f R JTSP何题"对算*的宾现选籽了讨论.芸词：蚂戴算法卜審目标能行商冋题中圈分类号：TPO22丈 itt 标 iR«EAJt * « 号 1lOOOa22Q<2O03nO-lBO&-O4Application of

2、 Ant System Algorithm in Multi-object Traveling Salesman ProblemYOU Dao-mm&» CHEN Jian(Stangfuii JiaTwig U Shetfighai 2000 30 Chi na)Abstract ： This paper analyze the property of multi-object problem and put forward a criteria to evaluate the total cost between multi-objects Based on the cr

3、iteria using ant system algorithm to solving the multl-Ghject TSP problem,. The algorithm is dliscussed in detail.Key words iant colony system i multi-ob ject( traveling salesman problem维晋资讯 维晋资讯 1引 «1. J蓦本蝎蚁鼻谖的喙理妈JK算怯量受到人们对自然界中其实的蚁群集体行为的 研究成果的启发而提出的一种基于蚂蚁的模扭进化葬法厲 于品机搜索启发式算准由:ft大利学者M. Dcrigo轸人首

4、先 提出一生物学研究理明一群互相协柞的蚂戴能醪找到食物 源和巢之间的最短踣径，而承只蚂蚁则不能*餌蚁间相互协作 的方袪是它们在所籃过的路上囲下一定数量的信息議，谨信 息索能铁其它蚂蚊检测出乘.一条踣上的信息索划多"其它鈞 蚁将以建高的此路径*从而谨路径上的信息素会被 加强“因此*由大盘蚂鞍组成的載群的集悴杆为便衰现出一种 信息正反愤现顒某一時桓上走过的妈戢越雾则后来者选择 谏踣轻的概率就越大对此过程*在文献"中曾用图承方式 形象地描述这一过程*这里不再费述.1.2 务目蛭TSP在科学管理与经挤决簞的许茅应用领城中.都有大的 雾目标优化同题.对于很雾决憾来说需要忧化的目标往往

5、不 止一亍如何在多小目标中寻找折中最优解是一牛比较厦杂 的冋题-对于具聲的TSP问題.实际中常需拮聲考点；跆程 屡短.时间堆少、峪用堆雪、风睑最小寻等多方面的ES索.问 题可描述如下：对于一牛全连接图+若各边弧上有R牛权值目标是梗 得Hamilton回路上相应的R个目标值都尽可能小“由于事 目掠嵐义下的所谓豪优解垦一种“折中解”严非翁解化因此 參目标TSP#的言文为：假罡有一HRiniha n回胳解H.若收蒂日期12001-11-12 怦者管斧游il明"碩土研究生* 囲蜡监控杲就硏究工柞”不存在任何其它回路解G,便得.厶（丹）"=12丄R其中至少有一牛不等式严格 虑立（L.

6、肯相应的吕标函数值则H肯Pareto最优壽.由PaTeto解的定义可知+对于塞昌标问题，其Pareto最 优解不是唯一的.而是由许車”非劣解"組成的解H多目标优 化问题中的審牛目标不可能同时达到最优、有时甚至是相反 的.因此不同决探者由于对各个目标的值好不同*会得到不 局的最优解.因此对务目标间題寻优也具有一宝的特殊性.传统的优化技术本島并不能厳接处理寒吕标优化问题. 般是将事目标同题的黑亍目标裁数通,过适当的方註如加权 怯、妁束法等转化为一亍目标函数的翠目标优化问题进厅处 理，传统的优化技术一股毎次都只得到PE/to解集申的一 个.或是相对于Pareto jft优解的一个折中幫.而

7、由于Paritc 解是多目标优化问题的一个解集*因此群徉援索策略是非常 合适的解决方寰其每秋的捜索的第果是一群可厅解+因此可 H更好的運近Pareto最优解解集.侖用的詳体撞竄算法是遗 传算祛通过对一代群悴按照寻优目标进行一系列的墟择、交 更，变异而使其下一试群体从滩悴上更接近俎优解.然而将遗 传算法运用于TSP问题有一定的限制因为将可行解表示为 遗佚因子并不是赧方便”貢观.而且对于有约束的TSP问题 也福难处理.2 特餌蚁算法运用于參目标TSP问題帶目标T5F问題的符号描述如T 已知H个城市.甜两 个城市之间的略径间有尺个代价值.多目标TEF问题优化目 标就是寻找一条嫌过n牛城市各一次且靈后

8、回到出发点的路 帶工业杲蜒控制硏究工作I鮮竖，高锻_L程讯.主與从事过程控制及辭道聘等：用蚂戟算法解决君目掠TSP问題180S径，在此路锂上所冇的的R亍代的値都翼尽可能的小.2.1理有的誘法在文就嗣中提岀了 一种妈敢葬法用于解决备貝标T5P 问题.在算法中妈敢的蒋动概率中y采用其中r是 随机选取的.这样蚂蚁在请应阶團选择下一T目标城帀时是 概率性前选取一 T优化指标这样得出的解在不同的优化指 标间徘拥*載乏方向性*可能得不出优化解.而且此算袪的结果是Parew解集、对于工程应用而盲- 拮要最终结果是能个的量优Pareto量优解往注是有多个 的*不可能给出所有的Pareto最优癖，让系统任选一个

9、柞为 堆賞鬻.任一牛单于的Pareto堆优解也许井不适症工程实 际，觀为福可能此Pareto最优解对某个目标优化结果福好. 但是其他目标却抿差.因此帚耍一种评枷指标在霉午目拯同 权循*荻得一种瀟意解.22 摇目标评窑揩标本文且提出了 一秤櫛单、却实用的评枷指标可H处理实 权值问题.住此基础上结合Pareio *?的寻优提出一种改善的 用于歩目标TSF问题的蚂蚁算法.我们由已得刮的最优解得出一种理想解“九 L；）.假设共有m只蚂蚁进行寻优：L： =min（乙）*=1L m. S为群休中第k貝蚂蚊在 完威路轻后的讓彳于揩标的总代价值.2 为所有蚂載中第i 个指揃的总代枷值量小的值，这样理規解（对心

10、”厶- '就 很可能不是可冇解但是这井不影响我们的寻优过程*满意解 的琨取是基于此理想解的.衽此，采用下列耦憲懈的评价指 掠：定文uit=iLaL： "L：为第k只妈蚁在第i牛目标上的 倔离度.第k只婀蚊所得到的解相对与理想解的偏离度3T= 工（门询T个不同目标间的拥对权值.最满嗣- 1懈展岛离度側堆小的解.关于理炬解的选取.有不同的方祛可民先計对每个单目 标进行忧化求得各TJft优解然后将单个目标的最忧解结令 起来”形屈理想解只是这样需要做匚次寻优.增加了彝怯的 复杂度.采用蚂載算法可用送代的方法选取理想解、对于斑次算 袪迭代的末尾找出迄今为止的所有已形成可行糖中母牛单 目

11、标最忧结樂组合这些结果形虑理想解.理想棉長随看寻优 的进行而蚕步更新的.而且只需一次寻扰简化了算檯.2-3算注描述酉先引入一些符号*设m是蚂蚁中蚂缎曲数童胡"儿仃 j = l ,2、表示城市i和城市i之间的第r亍代价值*可 “）表示T时刻在胞径灯莎上残団曲信息就.初始时刻各条 路径上信恳危相尊设（f）=rfl=C（C揃常败）”尬为可见 援.表示某种启投武规则、在这里可采用 U1 * <?3）“+乂 峙/（1几匸:.個&） u 说竝 才 “HgMg掛r个不同的冃标在 g）之间的代枷值 认门为r个不同包标间的相对权值*蚂蚁k<k =1 ,2 .在运动过程中.提据善条路

12、径 上的信息最决定转移方向示在丄时刻妈蚁上由位贏】 转移到位置j的概率寿（° 畴_ e cani£idate t LtHifr-ilriuM0j 总 candidate其中沁豪为环严巾（门的相对粗要性+为常谊-eidid&te=' Oa.-»-l*vWtedk表示蚂蚁k下一步允许选择的城市.人工妈蚁泵统具有记忆功能visittdk（k=l .2m）用以 记录蚂載k当丽所違£1的城市.宴合visitedk随着进优过程 忤动态调St.在完感一个究整的路径后+妈蚁会在所轻过的路径中留 下信息切"+1）=芦“"）+（1小4小称

13、为全局信息常更 新4险表示朋有玛蚁在路世询）上留下的伯息lb2去召也说衰示蚂蚁k在路径ij上留下的信息量， h直云三.Q为一固宦常魁*为总代价相对于了 £ Ljk+ui偏差值的重要性/表示每次迭代后信息素残留的比側程 度，可将1-段理解为信恵素挥发度.完威站径后”信息蠹的更 新使得蚂城所婭过的跑胫上的信息素有所加强而较忧的解 得劃較君加强、同时每邃一涉妈蚁也会在经过的路径上更新 信息蠹*盒卫+ = Pz5门+ U - pz、5称为局部信息鴛更 篇.巧为初始信总察设gg为每前进一步后信息囂残留 的比例程度*如果路轻（ii）没有被访何过则略更靳 后 6<£十】）=九

14、74;信息素盘保持不变，如果畴径® D被访间 过，幅据上面的规则gW）A玩.更新后TrPJ（f+l><r.Xf）信息 竄的娘金减少也就足说*一条路径被访问过，它在此次迭代 周期内的剩余歩数中再被便用的可能性就会降低”这样可以 使牧少狀访问的略径得到更爭的访问机会捜索的范15会更 価广”防止算怯过早收叙到次优解或单个的Pareto最优解. 其实全局更新与局那更新是矛盾的全局更新是一种学习正 反慷*使较优解中的路径更具吸引力，而局部更新却是墓抑制 不同路桎间差距进一歩扩大.怡当的调搭拳数丹他w可使痔 算法在快理性和有號性间权衡*参数中了可设为可变的*在寻优刚幵始时，设为比较大

15、的 值这拝旳可忽略不计*相当于在寻找Pareto ft优解当寻忧 进打到一定程度雾摄收散到Pareto* ft 得到最聽的 理患解空开蜡逐斷减小至奪"这时只有靳起作用，这样相对 于理想幫的较优满議帳的略径上会碍到超睾越參的信息素* 于是算法堆终会收敵到基于已给定的评阶持様的最满意解. 2.4蚂蝕尊法怙码Begin初塘胎t*' 0UerAtilffi4- 0 （iteration 为迭优步数】 将m于妈戴趣机于n帯H,克上* Loop£将所冇妈戴出发点置于当nrwft中；for H- 0 to n-1 do维晋资讯 1810小型徽型计算机廉统2003 年(0T k-

16、1 IO m da按療率神人昨选择顶点" 移勖蚂蚊k至頂点jt 将M点 >氏于蚂蚊k的当和霹集 rM(r+l) -(1 end fortT+Iend Fortf尊各乌取的J 6目标歯蠱價 更新当前的盟想鮮什聲客个的秣jtat吗 坯仃+ 1 7(f>4-(l Arjj K t t + l 所有AW- CtterftTicii iteratiati-1 若 LterptiOn<fl(定的 刚 gOTD Loop辑出目的的峨欄虑解End算搖问星杂度为 O(ileralEun * m * n1 * fi).3 算法測例举一牛简单的例子皋用文献叮中的例子0ai72帛】0S72

17、305544&7819773"4021Dl55448?06?2581977B?093-3402125930,-o52141443肩820617629钟14610293151D2147629Q7S6743293178023L47475167280_两摒标枚重相等3. J 戴设定書照经<TSP间題，我们设#=加应=0氣心将适当的 倍息箕遗忘度来动态调节略径.通过测试，我幻对y值釆用逐 斯減小的第略或采用在收敛到一定程度跳哑到0的簞略进行 比较.发现采用眺变到0的輩略做果更好一些，同时.如果在 y跳变到o的同时对各条路径上的信息索霾新恢廈劃初始 值*也会对效果有所改善.这样相

18、当于寻优过程分咸了两都 分.第一部骨负灾寻找Pareto最优解集"第二部分负最寻找 基于Parero ft扰堺集的最構畫解.立下甘别对这两阶段进杼 讨论.在雾洙寻找Parflto最优解的过程中，因为优优冃棕与靳 段尊优指导方向足一致的*阶段寻优指导值y与信息素值t 之阖枚贡相養不多径试验测试，取(3与a之比值为15左右 比较合适.蚂載数書照经典TSP问題的经验*便之与城市 数囊相尊，对于是让所有玛賊都可以更新所经过踣径上前信 息还是只让堰优的蚂竝更新信息素屋圈试发现让所有 妈戟都可見新信息素町心有处的提高算誌性能.阂为鼻誌寻 优的目的B Pareto豪忧挪集合'如果只让最忧的

19、蛰蚁更新信 息嘉算搖会很快收敛到第一个找到的Pareto A优解.所有 的蚂載不停柱此路径上盧复.而让所有的蚂牧都可更新信息 索可让其他的賂程的佶息聚不致与堆优蚂載的路径上的相差 太话.这样可有散的扩大算法的捜索空间不至于过早的收敛 于一个Pareto jft优解.此阶段的義数设室为尸=刊二08沁 = l*p=L5.m=nT让所有蚂戟都更新畤径上的値息羸”而在算袪寻找最満意曙的过程中，优优目标却是可行解 相对于欄意解的接近度，此时我们就需骥人为的蛤休现扰化 目标的I较离的权童将月与乜的比值设为5-7+这样葬法锲 用更多的是各个蚂載的协作信息1如果已与a比值设賣得较 小，则由于代价优化值y得到相

20、对较多的权亶算挂發报快收 Pareto M优解.而不是我们所钢电得相对于理想欄的猜 意解至于蚂鞍的数我们发现取妈栽数舒于赠市的嫂 柱此阶段往往不能得列很好的性施而取蚂蚊数尊于城市 B* L 5倍可使性髓得到很大的提离*之所以取城市数的 1.5倍.是因为在此阶段主要是依靠各个乌戟之间的协作来 达到葬栓的收飲而在y中萍现的寒个目标忧化只占很 小的权置.因此増加相互协作的妈牧嫂可以更好的利用各 个乌靛的历史搜蠶信息.而对于全府优化策略+与第一阶段相 似.让所有的妈載都更新踣径上的信息素会得到更好的性能. 理由与上面的幷析类似.最后我们得出第二阶国的鑫数设定 为、p=pz* = J1SfHi- 1.

21、5 * n+让所有蚂蚁解更新路径上的信息素.3-1离试皓果将此葬穗与其他的常用TSP携累算底想比较：各进行10 此迭代.运算结果如表1所示-叢1 Pareto Jft忧解Table 1 Optimal pareto solution本算議址尊法横拟退火算袪2 opt尊淮158 280158 280158 2BDLSD 2S02?1 197250 208208 27fi150 28&150 280209 248194 ?65结果表明、我们采用此方法能发现更多的Pareto jfttft 解.而且由此改进的玛JK雾挂可得到Pareio最优解(吗齐 2弱八其関个优化指标都小于由檯拟退火算怨算

22、出的Pato 最优»<2087&),因此此解其实并不是Pareto最优裤+由理 想倍的定文可求出(159.197).相对于理想解的満備解的寻 优结果如表2所示表2 相对于瀚意懈的僅离度Table 2 The saiiirying iolution208 276ISA 2B0SSO 208昨 4 2120,717D- 4210. 6380 »36这时滿竄解为15氛280)*它相对于理想M(158p197>® 离度騷小，为6 4213.采用前面的鑫戳设定在5亍迭代之内+ r« -维晋资讯 10期辭道明寻：用蚂載算袪熔决君目标丁5F问题lf

23、ill算袪可以收敛到溝意MC158.280).经测试算袪的结果是令人 灌遐的.4 结论妈蚁算法可以很好的解决经典TSP冋题*但是对于其它 有限制的TSP问题缺少进一歩的讨论.半文分析了案目标 TSP问题井针对此阿题的特殊性对经典算法进冇了相应的 改进对于參数配章也给出了指导性的原则.最后测试结果衰 明针对此问题*故进过的蚂蚊算袪的结果要好于巴有的算祛. 并且给出一种多目标的満意解评价策崎，和基于此策略的蚂 鞍算祛聲敷配，凰试结果是令人厲It的*Rererences«1 Porigo M, Mknicuci V and Cdorni A. The ant system optimiu-

24、 tionby a colony of caoperating agents IEEE Trani. Syst,Mun, Cybern. B.1996* 26(2),2941.2 Dorigo M. Lucb Maria. Gkit!bB.rdellaF Ant colony system & cooperative learning approach to the traveling val-eaman problemCJJ. IEEE Trsniaetjon on Evolutionary Compuuiiun. April 1997 】 (Di5366.3 St T. uttlc

25、 and Hoos H. The MAX-MIN ant system »nd local search for the traveling salesman prchlem C3- Ing Proc* ICEC* 97-1997 IEEE 4th Iftt. Cartf, EvoLutianiry Computation, 1997 T 309714.4 Mb Li«ng Jiang Fut Solving multi-cnieri* travelling sale*man problemby an< fllgorithmCJJ. 1999t fl(.4) i23 27.姻中文甜文4马良蒋曲.多目掠確行商害箕员问題的勢败算祛求霹口人摹疑 工程理论方抚应用.】999, 8(4>t2327*