求解多目标最小生成树问题的改进算法

1、E-mail: josfiscas http: wwwjot.oTg cn Tel/Fax： +861062562563ISSN 1000-9825, CODEN RUXUEWJournal of Software, Vol. 17、No.3, March 2006. pp.364-370DOI: 10 1360josl70364C 2006 by Journal of Software. All rights “served.求解多目标最小生成树问题的改进算法陈国龙匕黑文忠1涂翳2,瞅旺】 丄(国防科学技术大学计算机学院湖南长沙410073)福州人学数学打计算机科学学院，福建福州350002

2、)An Improved Algorithm to Solve the Multi-Criteria Minimum Spanning Tree ProblemCHEN Guo-Longk： GUO Wen-Zhong TU Xue-Zhu CHEN Huo-Wang1"School of Computer. National Uiuvcrsity of Defence Technology Changsha 410073. China)(Institute of Mathematics and Computer Science. Fuzhou University. Fuzhou

3、350002. China)+ Corresponding author Phn: +86-591-87893316. Fax +86-591-83713866. E-mail cgl, http Twww.fzu Chen GL Guo WZ, Tu XZ, Chen HV An improved algorithm to solve the multi-criteria minimum spanning tree problem. Journal of Softw are. 2006,17(3):364-370. http:/ .ca 1000-9825/17/364 htm

4、/Abstract: The multi-criteria minimum spanning tree (mc-MST) problem is a typical NP-hard problem An algorithm to enumerate the set of Pareto optimal spanning trees on some mc-MST instances was put foru-ard by Zhou and Gen, but it does not guarantee returning all the Pareto optunal solutions. To set

5、tle this problem. an improved algorithm is developed and also proved to be able to find all the tme Pareto optimal solutions in this paper. The new algorithm adds some conditions in the elimination of subtrees. Simulation results show that the new algorithm can find all the Paieto optimal solutions

6、and also show that the new algorithm has potential usage in practice.Key words:minimum spanning tree: Pareto optimal摘 要 多目标最小生成树问题是典型的NP问越.Zhou和Gen提出了一种用于计数多目标最小生成树问题 的所有非劣最优最小生成树的算法，但该算法无法保证能够找到所有非劣最优最小生成树针对此问題，提出一 种改进的计数算法.并定性说明改进算法能够找到问題的所有非劣最优最小生成树改进算法在进行子树剔除 时增加了 一些条件模拟实脸结果表明.改进后的计数算法能够找到所有的非劣最

7、优解这也说明该算法具有应 用的潜力.关键词：最小生成树:非劣罠优解中图法分类号:TP301文献标识码:A址小生成树问题(minimum spanning tree,简称MST)丿上构造个帯权图的址小代价生成树，在网络优化中JI 冇举足轻匝的作用冃前.图论中已冇吃经典的求解最小牛成树算法.如Kruskal算法、Prim算法等卩】.经典的 Supported by the National Natural Science Foundation of China undei Grant No.60172017 (IH 家【I 然科労农仝)；the Natural Science Foundation

8、 of Fujian Province of China under Grant No A0410010 (福建省I 然科学圧金)；the Natural Science Foundation of Fujian Provincial Educational Commission of China under Grant No.K03012 (福绘教仃厅 J 技二项科硏顶 II)Received 2004-04-15; Accepted 2005-03-101994-2008 China Academic Journal Electronic Publishing House. All rig

9、hts reserved, © MUMUTkttfMHWFr httpww. J(>«. org. cn367Journal of Software 软件学报 Vol. 17, No.3, March 2006垠小生成忖算法，其计算箜杂度为参项式时何.但当给MST増加约束条件或问题日标为女个时，相应的问题称 为姜I标址小生成树问(multi-criteria MST.简称mc-MST),而JL问题本少也变成了 个NP完全问题.W此，近 年来许多启发式算法应运而生.其中最具代农件的算法超Zhou和GeiW所捉出的算法.文献2中的算法址以随机生成的10个50顶点的女II标

10、mc-MST问题作为算法的性能测试问题,并将测 试结果与所捉出的计数图的所冇艰小生成树的方法紂到的“所冇非劣最小生成树"相比较，测试结果称算法找 到J"问题的所冇非劣域优解实际l：,Zhou和Gen捉出的计数算济所求解到的非劣址优解是不轿确的.这个问题 Knowles在其博士论文中进行反证撚而Knowles也没竹给出粘确的算法为此，我们对Zhou和Gen提出的 计数算法作了改进，并定性说明了该改进算法能够找到问题的所冇非劣址优解1 mc-MST 问题1.1 MST设有-个无向图G-(MEW).其中W =为权函数.卄树T-N,Et.Vt)包含门却G的所有顶点.则7称为G的个生

11、成树或支撐树=为M，为丁的权图G的生成树并不啡,权址小的生成树相应地称为G的最小 生成树在实际匸程问题中.慎终町以转化为求解图的最小半成树的那类问题称为MST问题.1.2 Mc-MST设有个连通的无向图G=(V.E),其中V=vl.v,.'，”是个有限集合代农图G的顶点、E-gm，卜lfV/，V之间冇边(1,2，,”-1尸汁1,.,“),为图G的边集合.若边e,j存在侧冇m个0. otherwise值为正数的属性与之相对应，用忆虬，吃_屹农示实际问题中皿伙.12,加)可以是距离、代价密令x口和' if % = 111皱选小ip,片1"汁1丿衣示图G的棵生成树主 0.

12、otherwise为所有x的集合.则mc-MST问题描述为：t”111111 齐(*) = 2：血；.mm人=工吃切；'*(1)其中为问题中需雯最小化的第i个冃标.2 Zhou和Gen提出的计数算法及其分析Zhou和Gen捉出了 种求解赛FI标最小牛成树问题的遗传篦法该算法中的染色休编码采用Phifer数编 码.而选择策略则是用Snmvas和Deb提出的个体非劣性样序方法国为J评价该算法的有效性.Zhou和Gen相 应地给出了 种计数算法，用丁计数mc-MST中的所仃作劣加优解丽篇幅所限,Pnifer编码过程和计数算法过 程省略.貝体可见参考文献2定义帆Priifer给出f n个节点的

13、生成树和长度为n-2的串之间的一个对应关系而习惯地用数字来标志 这些节点,所形成的数宁小称为Prufer数.定义2【町.非劣性扌II序过程的威本思想定:在选择过程中.采用随机选择方法加强较优的个体和小生境方法 维持较优的个体的了种群的稳定性相应地.称采用此思想的方法为非劣性卅序方法.定义 3(优劣tl,doniinance/inferiority)61.称 H 标向彊解优 F i(vbv:,.,vn),k!为 “pG,如果 u部分小于儿也就是V/ e 1,2,.,"" S vt A 3/ 1.2Y片.反过来,称目标向量解v劣于"，记为vp<u.定义4(非劣最

14、优解Pareto optimal).决策变最呎*称为多H标问题的非劣瑕优解，当1丄仅当不存在决0Fig.l A graph of five vertexes 图1含有5个顶点的完全图策变量才“ 使得相应的目标向fit八/(%*) = (%忖几)优于 " =(5"一上刀中,作者利用计数算法计数些较小规模的mc-MST问瘪并用 文中所提出的遗传算法求解到的非劣瑕优牛成树的数冃与用计数算法找到 的非劣址优生成树数I I的比咧來评价算法的性能然1(11 Knowles在其即I: 论文中举例反证了该计数过程的不精确件其中的个反例及分析如图1 和衣1所示.Knowles的反例育力地说明

15、文献2提出的计嗷个无向连通图G 的所有非劣最优住成树的方法不但不能保证找到所有非劣巌优解，而11找 到的生成树还町能不是非劣最优的我们统过研究发现，文献2的计数方法 不能保证找到的是所仃屮劣故优解，问题出在f树剔除上例如.Ti和门为两 棵2条边的生成树如果八<门,并不能就此认为由门派生的生成树就一定不会是非劣最优牛成树从向把门从犷树集介中刪除抻.Table 1 The procedure and result for algorithm of Zhou and Gen表1 Zhou和Gen方法的求解过程01(356,979严01(943.1二04广0-2(587,285)1-2(1513

16、,423)0-3(225&648)i4(3ii5879产"34(226&92 矿07(2394026广13(2339 96刃w0-3(1332,510)* 0(613888产1994-2008 China Academic Journal Electronic Publishing House. All rights reserved, ki.nci©Jo«. org. cn#Journal of Software 软件学报 Vol. 17, No.3, March 20061- 4(2370,654)2- 3(1888.7467?3(9里鯉厂丁2

17、沖00999少04(77128)“ 1-3(1571,7723(1110 54/0-2(1342,785)03(745,225)14(2199、101尸13(1581JO邛严3-4(755,500)1-4(1612,731)2-3(1130.823)0?(耳906广12(2056 96 13(1?辿.1今尸14(1987053厂1994-2008 China Academic Journal Electronic Publishing House. All rights reserved, ki.nci©Jo«. org. cn#Journal of Software 软件

18、学报 Vol. 17, No.3, March 20062-4(1177.12117申里、§§§产"0-3(771828)*0-4(26,603)1«4(663小34)"24(44SJJ11广!34(36,878)0-1(392,1857)0?(9?9f 卜?(38 1?岁尸 23(7672180)24(814 二 56SJ"1994-2008 China Academic Journal Electronic Publishing House. All rights reserved, ki.nci©Jo

19、1;. org. cn369Jou ma I of Software 软件学报 Vol. 17. No.3, March 2006续表1O-1(979.2142)R0-2(6234163)1-2(1549,1301)(7)l3(1449J709广1-4(14804 394)e13(862424)"02(1480.1394)1-4(893.1109)1-2(1819.1247)(8丿2-3(1268.1432)(9)2-4(1315,1820)ee0-l(767.21S0)R2-3(411.1201)1-2(1337,1339)(10)13(1237,1747)）1-4( 126&am

20、p; 1432)R3算法的改进山上所述，我们根据生成树的特点，在进行两棵生成广树的Puet。优劣性比较时丿曽加r 些条件，只育两棵 生成J'树满足以下条件时才将其中的劣解剔除.否则认为不能从两棵丫成（树Z间的Pareto优劣性关系来确 定由它们生长成的最终生成树之间的Pareto优劣关系.引理假设无向连通图G二（/£丿.!1屮芒=九匕.心.£=“心，e/,S为闷用文献2中的计数纭生的生成了树集合，其中的每个牛成J'树I JI仃k条边对于任意的“心皿阿小岭创吩 为*J E1：郴连的顶心如如果*七H.满足以卜条件Z-M由比牛K成的牛成树 淀不会 Pareto优于

21、由Sj生长成的生成树.I -力,两犷树具冇相同的顶点集合；两子树都只有条边且有一个共同顶点；Illg 为同一 f树增加条边后的生成/树或者叫厂匚2且只有-个非共同顶点.证明：I 令Vn-Vi门心-vJ,Vn-V-V12JUlV：X献2的计数恥丿、过用血次都肚“II分別与 Vn中的个顶点相连的边.$卜$2 J1有相同的顶点集合.如果能够海加边vpv</.pe汁1J亠2 n.qei2i到s2中不构成回路，则同样能够将边吩s澹加到6中.、 *因为卩厂冬-勺,巾，,v,. 、"所以= （V：, E；人，叫5% ，尽=耳5八，'驾（*£）.* % 5邙疋；耳 5忖PW1

22、,2,. J/汁 1,汁2,.丿,乂因为所以同理，对任山s；潦加条边后生成的/树 定劣flh J；再泾加该条边后生成的广树.II-不妨设yi-（Vz1,E1）-（vi，v2,v1V2）,52-（V:,E2）-（v1,v3,v1v3）.由上不断生K成生成树的过程为:每次添加-条分别与力，匚中的个顶点相连的边到5中，同时把与该 边相连的兀中的那个顶点海加到V2中再从V2中删除假设增加顶点七前飞的边集为5M-W2WV-52 VU（W'W3）（1）如果正姜添加的边为vps,即S；=（咛E；） = （匕5叫,鸟5片叫）.显然，35； = （V；.E；） V；=V：.E；= Ex oE, = vp

23、JoE： = E，即 s； = s；.如果正要添加的边为vpV2，per1）若巾到旳的路不经过VpW sz =（V：EI）=（V, k>v,.£:.peV',则根据牛成树的件质，可知玉;=（*,£；） =（y：,Et u（E:-帕） 又因为勺 Y s2，所以 s； Y s；.2）若v2 flj 1，3的路经过Vx,不妨（IV设v：到珥的路彳0 I：经过的顶点、依次-为匕->Vpf -»r4-.令$3（“3 £） -lvbV4,vlv4）.如果町y$3，则玉;=（%：&） （V；,耳5冬-曲），使得$； YS；;否则35； =

24、（V；,E'） = （V：,E3 5比-%） = （V：,E：»，即该生成子树可由$3派生出来.III.令 Vl“2U%M-Vi2U%M2-5，V2”.M,ElE】2U% 巾同样,由 $2 不断生长 成生成树的过程为:每次添加条分别与冬.兀中的个顶点相连的边到6中,同时把与该边相连的兀中的 躺个顶点潦加到力中再从几中删除，则向卩2增加顶点巾后，広=（«,尽）=（匕5忤齐2%:&）化y（u-x- vp ）,根据生成树的性质，新增加的边的另端点必定不属J-匕，因此，玉；=（V；,£；）=（叫,（耳-叩 J2 叭）又因为Y$,，所以本文所提出的计数图的所

25、有Pareto最优生成树的改进算法具体步骤是：步骤1.任盘选择个顶点作为出发点，不妨假设选择勺作为开始顶点-检任所仃号心相连的边，将这些边 中的Pareto仗优边加入到f树集S中；步骤 2. for each subtree 5eS;逐检査所有与$中的任顶点相连的边弘如果加入边旬不会使$存在回路，则把山$和匕构成的新的 棵P树放入S，中；步骤3.对于s中任意两棵生成f树如果（S<$2）&&（叫岭川伙-1匕|-1）|丫厂心MI-M-i）.则把$2 从S中删除；步骤 4. S«-SS*<-0;步骤5.如果S中的树边数小于“L1.则转步骤2.否则返冋S.Know

26、les列举例予反证了文献2中计JR算法的不精确性,图1所示的是其中个例C为进步说明木文攻进算汰的有效性，本文给出文献刀中计数算法和本文改进算法求解片1的勺、果，见衣1、ft 2.衣中5”农示该了树劣于其他了树派生岀来的了树.而“"”我示了该了树劣于同-了树派生出来的子树从 求解结果我们可以看IlkZhou和Gen的方法得到11个解;本文方法找到r 12个解一比较两个农中的解，显然Zhou 和Gen的方法只找到了 10个真正的非劣最优解，其中第4个解并不是非劣最优解，而本文算法找到了 12个解, 町用穷举法验证这12个解都是非劣虽优解.而H.找到r全部非劣最优解经典的址小生成树算法的算

27、法复杂度 为篡项式时间，而女LI标般小生成树却楚个NP完全问题，即对F 个完全图G,过n个顶点的树的数H为 川宀,其畀法复杂度相应为O（厂）.、. * *为此.本文改进算法的II的绘修止Zhou和Gen的计数算法所存在的问题.以期取代原有算法作为 种评价 其他心发式算法性能的工具. Table 2 The procedure and result for the new algontlim 表2本文改进算法的求解过程0l(356979)“0-2(587,285)0l(943264 丿"0.3(1332,510)*0-4(613,888)e1-2(1513,423)0-3(2258,6

28、48)0-4(2284,1251)14(3115,879尸24(2680359)3-4(226&923)(1)0-4(1539,1026)0-3(2284,125 l)e1.3(2365,1572)“23(1914,1349)"34(1549.1301 )R13(2339969)"1A(237O,654)“2-3(188&746)0-4(1914,1349)e*1.4(2745,977广© 1994-2008 China Academic Journal Electronic Publishing House. All rights reserve

29、d, © WIH*V?紀飲fl駢伽Jos. org. cn陈国龙茅:求解*目标最小生成树问题的改进算法371续表23-4(1898,1071)2-3(962.608)2-4(1935,1134)01(131&158讦0(98&1211严12(188&746尽2-4(1354,1319)13(178815 乔73»4(972883)01328,18621-21898,10211-4(1829,1114)0-3(745,225)24(1009996丿“ 0(1101204严 02(1332.510)“ 04<771828广匸 b3(1571J71)

30、 24(1120,54S 戶3-4(755.500)0 11J479)*0-2(1342,785)13(1581,1046)»1-4(1612,731)UJ(2199JU16广1225北飞69)24(203丄14辽产2-3(1130,823)01(1486辺尸l2(2U6,901)1-3(1956,1369)*1-4(187,1054)*QJ0-4(26.603)01(382582)"0-2(613.888)03(771,828)*"14<883,834)"24(448314广3-4(36.878)0-1(392,1857)0-2(623,1163

31、)13(8621424)“1«4(893109 丿2-3(411.1201)2二(45&1589)1- 2(1315 l j95?23(%7 二(7)2- 4(814.2568? *0-1(979.2142)K悝"？刃.14门80394沪1-2(1819.1247)24 13i、131237747) 治1(26S1J3JR4结束语本文订先在Knowles的分析基础上指出 Zhou和Gen 出的计数算法所心在的问逆，继而捉出了 种用 于计数多冃标最小生成树问题的所仃II劣最优最小定成树的改进算決片定性证明了该算法能够找到问题的 所有非劣最优绘小牛成树址后刈改进算法进行

32、测试测试结呆农明该算法是有效和町行的.References:1 Yan WM. Wu WM. Data Structure 2nd cd Beijing Tsmghua University Press. 1992. 168-174 (in Chinese)2 Zhou GG. Gen M Genetic algorithm approach on muiti-cntena mmimum spanning tree problem European Journal of Operational Research. 1999.114(1):141-1523 Knowles JD. Local-S

33、earch and hybrid evolutionary algorithms for Pareto optmuzauon Ph D. Thesis. University of Reading, RG6 6AY. 2002.4 Sruuvas N, Deb K. Multiobjcctive optinuzation using dominated sorting ui genetic algorithms. Evolutionary Computation, 1995.2(3):221-24&5 Gottlieb J, Julstrom BA, Raxdl GR. Rothlauf F. Prufcr numbers: A poor rcpiescntation of spanning trees for evo