求解最小Steiner树的蚁群优化算法及其收敛性

第29卷第2期 应用数学学报 V01．29No．2 2006年3月 ACTAMATHEMATICAEAPPLICATAESINICAMarch，2006 求 Steiner树的蚁群 法及其收敛性半 杨文国， 郭田德 (中国科学院研究生院数学系，北京100049) (1E-mail：yangwg@mails．gucas．ac．cn) 摘要最小Steiner树问题是NP难问题，它在通信网络等许多实际问题中有着广泛的应用． 蚁群优化算法是最近提出的求解复杂组合优化问题的启发式算法．本文以无线传感器网络中的 核心问题之一，路由问题为例，给出了求解最小Steiner树的蚁群优化算法的框架．把算法的迭 代过程看作是离散时间的马尔科夫过程，证明了在一定的条件下，该算法所产生的解能以任意 接近于1的概率收敛到路由问题的最优解． 关键词蚁群优化；最小Steiner树；算法；收敛性 MR(2000)主题分类68W40 中图分类0221．7 1 引言 蚁群算法是模拟自然界中蚂蚁搜索食物行为而提出的一种启发式智能进化算法， 该算法由意大利学者DorigoM等人作为求解著名的旅行商问题(TSP)的启发式算法而 提出的[1]．虽然单只蚂蚁的行为非常简单，但是蚂蚁间可以通过一种叫做信息素的分泌 物作为媒介进行信息交流，通过合作来实现复杂的计算．蚁群优化(ACO)算法是在蚁 群算法的基础上发展起来的能有效地求解各种组合优化问题的算法框架，包括蚂蚁系 统[2】'蚁群系统阱]，最大一最小蚁群系统[5l和树的非确定近似搜索[6]等．蚁群优化算 法具有正反馈性，即问题的解越优，通过调整其上标志信息素参数的值，其被找到的概 率就会加强；反之，其被找到的概率减小．蚁群优化的另一个固有特点是适合于分布式 环境，因而能用来求解基于分布式网络的最优路径计算，例如路由、负载平衡和计算机 网络中的多路传输等． 尽管ACO在求解各种组合优化问题时得到了很好的实际效果，但对其理论方面的 研究却相对较少． f7]给出了基于图的蚂蚁系统的收敛性证明，指出在一定的条件下， 算法迭代产生的解能以任意接近于l的概率收敛到问题的最优解； [8，9】对[7】的结果 进行了推广，在动态逐次更新信息素挥发率或信息率的下界的条件下，算法迭代产生的 解能以概率1收敛到问题的最优解． [10】对一类ACO算法得到了类似的收敛结果，并 且分析了找到最优解后信息素的性质．然而以上结果都是针对TSP而建立的，而且用 蚁群优化算法求解TSP相对容易实现．[11]把ACO成功地应用到了无线传感器网络 本文2004年9月10日收到． +中国高技术研究和发展3TNet(863项目，2002AAl03061号)，国家自然科学基金(60241006号)和中国科学 院院长基金(YZJJ200503号)资助项目． ～， -=|r小算动讹犀T尤隔优 万方数据 2期 杨文国、郭田德：求解最小Steiner树的蚁群优化算法及其收敛性 353 中的路由问题，并且得到了满意的实际结果，但文中并未对算法的收敛性进行分析．本 文对求解Steiner树问题的AC0算法进行了收敛性分析，在通常都能满足的假设条件 下，算法迭代产生的解能以任意接近于1的概率收敛到路由问题的最优解． 本文的结构如下：第2节给出了最小Steiner树问题的模型及相应的蚁群优化求解 算法；第3节给出了收敛性结果及证明；最后在第4节给出了结论． 2 最小Steiner树问题及其蚁群优化求解算法 2．1最小Steiner树问题 图的Steiner树是一棵连接所有给定节点子集的子树，Steiner树问题就是指挑出 具有最小费用的Steiner树[12,13】．最小Steiner树问题在无线通信网络和计算机网络等 实际问题中有着广泛的应用，许多实际问题都可以抽象为求解最小Steiner树问题，例 如无线传感器中的路由问题、计算机网络中的多路传输问题等．求解Steiner树是著名 的NP一完全问题[14]，因此除非P--NP[15】，得到最小Steiner树需要指数复杂度的算法 [16,17】，但在实际应用中，这通常是不可接受的．因而设计求解Steiner树的快速启发式 算法并进行收敛性分析，具有非常重要的实际意义．本节以下以无线传感器网络中的核 心问题之一，路由问题为例，介绍最小Steiner树问题． 处理器技术的发展能够廉价地大量生产具有感知和交流功能韵传感器节点，在特 定的区域内大量的撒播这些传感器节点就形成了无线传感器网络．由于无线传感器网 络中节点能够感知和跟踪工作环境、交通系统和医疗卫生等方面的不同内容，无线传 感器网络技术在今后将有广阔的应用前景．随着无线传感器网络的布置和无线传感器 网络应用的发展，急需相应的控制和管理算法，这是无线传感器网络的发展所提出的挑 战，其核心问题之一就是无线传感器网络中的路由问题．本文仅就无线传感器网络中的 多源单汇路由问题进行描述，对其它问题(如：单源多汇、多源多汇路由问题等)可进 行类似讨论． 无线传感器网络中的多源单汇路由问题就是寻找无线传感器网络中从多个探测或 跟踪点(也可以是小的探测区域)到检测控制中心的最优路径，以便检测控制中心及时 获取探测或跟踪区域的信息并进行相应的处理．假设用带权重的连通图G=G(KE，u) 表示给定的无线传感器网络，其中y是节点集，E是边集，u：E—R+为E中的每条 边赋一个费用值．y中的每个节点表示一个传感器，对于Vk，Vl∈V，ekl=(吼，U1)∈E 当且仅当传感器V％和Vz能够进行信息交换．由于能量的限制，并非任意的两个传感器 之间都可以进行信息交换，由于发射半径的限制，通常每个传感器只能和它附近的几个 传感器进行信息交换，可见G并不是完全图．设ScV是源的集合，d∈V是无线传感 器网络中唯一的汇点．这样多源单汇路由问题可以看作在图G中寻找一个包含Su{d} 中所有节点的树￡s，使得树的费用 u(ts)∑u(e) eEts 最小．可见无线传感器网络中多源单汇路由问题实际上是一个最小Steiner树问题． 对于图G=G(VE，u)所表示的给定无线传感器网络，S={u1，V2，⋯，us)CV 是给定的s个源节点，d∈V是唯一的汇点．包含su{d)的Steiner树ts可表示为 ts=U6(“，其中b(8)=u5sju；“⋯"铆，s=1，2，⋯s是构成树ts的s个树枝且满足： s=1 (1)u58’=u。，u￡?=d； (2)Vi‘纠"出∈E，i=o，1，2，⋯n。一1； (3)若尼≠f，则u：s’≠u}3’； (4)对于不同的树枝，若u?’=uf¨，则"肄。="薄，，u肄。=u肄：，⋯，u粤=u黝．用 万方数据 354 应 用 数 学 学 报 29卷 T表示满足上述条件及其它约束条件(例如传感器节点的能量约束等，具体根据无线传 感器网络设计而定)的Steiner树的集合，则无线传感器网络中的多源单汇路由问题可 表示为： 船删2三晰 (2) 2．2最小Steiner树问题的蚁群优化算法 与求解TSP的蚁群优化算法不同，通常采用多只蚂蚁合作来共同找到一棵Steiner 树，每只蚂蚁在一次迭代中只需生成一个树枝即可．在每个源节点V。上各放，只蚂蚁， 在每次迭代中，按顺序依次从各个源节点上放出一只蚂蚁，直到放完J只蚂蚁为止，此 时能产生J棵树，然后进行信息素的更新，进入下一次迭代．下面分别介绍蚂蚁在移动 过程中的转移概率和信息素的更新规则． 2．2．1蚂蚁在移动过程中的转移概率 为方便记，用南表示y中的节点％，(k，f)表示E中的弧(％，仇)．设在第m次迭 代中从源节点s发出的第i只蚂蚁A：8’的当前位置为忌，本次迭代中由前s一1个源节 点出发的第i只蚂蚁产生的部分树为tyl(i)，由s源节点出发的蚂蚁A：8’产生的部分树 枝为拶)，则当k聋t芗1(i)时，A：8’选择下一个位置l的概率为 ％∽∥㈤，_{一l隹拶’且(后，f)∈E否则而当k∈tyl(i)时 晰州踟=B翁。J『机r柏后继节氐 其中Tkg(m)是第m次迭代时，弧(k，f)上的信息素的量，2．2．2节将对此进行详细的说 明；讯f是节点f对节点南的吸引度，通常简单地取为吼2=可b． 2．2．2信息素的更新规则 信息素是蚁群算法中至关重要的一个参数，其初值设计及更新规则的选取直接影 响着算法的性能．本文采用模化处理的均匀设置信息素的方法和信息素的精英更新策 略，即算法开始时，对E中的任意弧(k，f)赋信息素的初值亿f(1)=丽1，这里IEI表示 E中弧的个数；信息素的精英更新策略是指：在第m次迭代结束之后，在E中所有弧 上的信息素进行挥发的同时，仅对前仇次所找到的最优树上的弧进行信息素的加强． 设t扩是前m次迭代所找到的最优树，则 亿zcm+·，=<：：二宝：：：i；，+p△亿“芸蛊．∈t扩’ c5， 这里00．这是为了保证能够探索到所有可能的解． 假设4max{恬I：ts∈T}，即T中树￡s的弧的个数的最大值有限． 对于实际无线传感器网络中的多源单汇路由问题，以上假设通常是满足的． 定理在假设l一4之下，令Pm表示第m次迭代找到最优树的概率，那么 1．对于E>o和固定的参数P和卢，通过在每个源节点上放置足够多的蚂蚁，即充 分大的J，存在正整数mo=mo(s)，使得Pm≥1一￡对所有的m芝mo成立． 2．对于g->0和固定的参数』和卢，通过选择足够小的信息素挥发率P，存在正整数 mo=mo(￡)，使得Pm之1一￡对所有的m≥mo成立． 为了给出定理的证明，把迭代求解过程看作离散时间的马尔科夫过程．这个马尔科 夫过程的状态是三元组： (丁(m)，￡s(m)，u+(m))，m=1，2， 这里丁(m)是由第m次迭代时E中弧(k，f)上信息素的值7kt(m)组成的向量；ts(m) 是第m次迭代中各源节点u。，⋯，us上的I×S只蚂蚁随机移动所生成的，棵树 S t§(m)=(U6∽仇))， 忙1，2，⋯，f s=1 组成的向量；u+(m)是在前m次迭代中找到的最优树的目标值 命题1状态变量 (丁(m)，ts(m)，∽+(m))，m=l，2， 万方数据 356 应 用 数 学 学 报 29卷 构成马尔科夫过程． 证只需证明第m次迭代的状态 (丁(m)，￡s(m)，u+(m))，m=l，2， 的分布仅依赖于第m一1次迭代的状态 事实上， (1)根据信息素的更新规则，丁(m)由丁(m一1)，ts(m一1)和u+(m—1)确定； (2)由于讯f的值是固定的，所以ts(m)的概率分布依赖于丁(m)，从而由第m一1 次的迭代状态所确定； (3)u+(m)由￡s(m)和u+(m一1)所确定，进而由第m一1次迭代的状态所确定． 故命题成立． 下面给出定理证明中采用的一些符号： t*s是最小Steiner树，￡；=U6≯’)618’是从源节点％到汇点d的最优树枝；Ⅳ是 最小Steiner树￡冬上的弧的个数；Pr是上述马氏过程中的概率测度；毯8’(m)表示事件 b：(m)=618’即在第m次迭代中，从源节点s出发的第i只蚂蚁走过第s个最优树枝； E嚣’=n尉刚(m)，即在第m次迭代中，第i组蚂蚁产生了最优树培；B。=n毯叫即 、7 s=l i：1m1 第m次迭代中，没有产生最优树t与；Fm=(nB。)n砺即在第m次迭代中首次找到最 n=1 oo 优树￡；，显然Fl，F2，⋯是互斥的；A=UFm表示最优树培被找到，即存在迭代次数 mo和从各个源节点出发的某组蚂蚁找到了最优树．此外7=min{陬2川(k，z)∈t§}>0． F=max‰f]卢0，由(5)式可得 亿z(m)2(1一P)，7-kz(m一1) 重复(6)式进一步得 Tm(m)≥(1一p)m--1亿z(1) 第8个树枝6(8)上蚂蚁i的转移概率 ％(州烈跏=专器犰(m)[砌n当㈣一z譬啦埘 r和驴’ 当忌∈￡扩1时，由式(4)知，蚂蚁在树枝6(5)上的转移概率同样满足以上不等式． 万方数据 2期 杨文国、郭田德：求解最小Steiner树的蚁群优化算法及其收敛性 357 于是 设618)=(u5“⋯～n(8s)、}，则 Pr(毯8’) 7”3(1一p)”sב⋯一1’II亿，2(1) (k，z)ebl8) Pr(E旨’)=ⅡPr(磅3’(m))≥I-I{，y”8(1一p)”sבm一1’II亿z(1)) s=l s=l (k，2)印∥ ≥，yp(1一)‘叫一E“IIP 亿。(1)≥，ys一 (1一) 一· 亿z(1) (％，z)et； =7Ⅳ(1一户)‘m一1’ⅣII亿f(1)≥c“1P， 其中C=(1一p)Ⅳ，P=7Ⅳ兀 亿，f(1)．于是Pr(B。)S(1一Cm-1p)7．进而引理得证． (k，z)et*s 由于以上证明与前m一1次的状态无关，故有如下推论： 推论1在前m一1次迭代中没有找到最优树的条件下，至少有一组蚂蚁在第m次 迭代中找到最优树的条件概率Pr(磊f男l¨-％一，)之l一(1一cm-1p)。． 引理2设在第m次迭代中找到了t§，则对所有的(k，f)∈t菪，有 1． ， ，、 1 早m亿f(rn‘J2丙m’_o。 』V 而对于(k，1)岳培有 1．im亿2(m7)=0 m’—+。。 这里N=峪I是最优树上弧的总数目． 证根据信息素的更新规则(5)，在第仇次找到最优树以后的每次迭代中，都要对 培中的弧进行信息素的加强，即对(k，f)∈￡§，有 7-kz(m7)=△亿f+[亿2(m)一△亿2](1一P)⋯Lm 其中△亿f=丙1．由于0一0扣S n ＼三二一+R¨Ⅱ㈤ ¨Ⅱ脚 n 7>一 np+砖亿 ¨Ⅱ㈣ 7>一 万方数据 358 应 用 数 学 学 报 29卷 于是lim仉2(m)=0．引理得证． "z，—}o。 引理3令oss-1，+表示由前s—1个最优树枝组成的部分最优树，则对￡>0和 mEN，存在d7(￡，m)EN，使得转移概率 Pr{R，l(m7，tsS--1'+)≥1一￡对所有的(尼，f)E培lFm)≥1一￡ 对所有的m7≥m+d7(E，m)成立． 证由引理2知，在第m次迭代找到最优解的条件下，V手>0，刍d(im)，使得 m7≥m+d(im)时，有 丙1+F≥亿f(m7)芝丙1一E对所有(尼，2)∈￡+S 和 亿z(m7)SⅣ巨对所有(k，1)隹t； 成立． 从s节点出发的蚂蚁在第s个最优树枝6≯’上的选择概率为 亿z(m，)[吼2r ∑ 亿，(m，)[叩％，】p r曲簿，(％，r)EA 1／Ⅳ一砀 1一NF 。Ⅳ手+(1／N+习卵l+虱Ⅳ2／叼+N) ≥(1一Ⅳ刁(1一虱Ⅳ2／叩+Ⅳ))[因为(1+z)_1≥l—z】 之1一(2N+N2／叩)F≥1一(2N+N2／一y)Z 这里6培是部分最优树枝．取F=E／(2N+N2／7)即可得证． 推论2用引理3的符号，令ym，=II Pkt(_7Tttt8s--1’+)．那么V￡>0和mEN (尼，f)∈t； 存在d“(￡，m)∈N使得 Pr(ym，≥l—EI，1m)之l—E，Vm7≥m+d“(E，m) 成立． 证由(3)，(4)和引理3直接可得． 引理4对￡>0，存在整数d，，，(￡，m)EN，使得对任意一组蚂蚁i，有 Pr(E捃㈡Fm)芝1一￡，对所有m7≥m+d”7(E，m)成立． 证E器7’表示事件：在第仇7次迭代中，第i组蚂蚁产生了最优树￡§．对于马氏过 程第m7—1次迭代中给定的状态，这个概率就是推论2中ym，的值，而‰，本身也是 随机变量，有一定的概率分布．因此为了得到E器7’和以前状态无关的(条件)概率，需 要求出关于ym，分布的期望值．具体的，由引理3的推论2知： Pr(‰，≥1一司F1m)≥1一iVm7≥m+d”(巨m) 万方数据 2期 杨文国、郭田德：求解最小Steiner树的蚁群优化算法及其收敛性 359 因此对相同的；n7， Pr(Ef孑7’IFm)≥Pr{E{孑7’n(ym，≥1一习IFm} =Pr{E辫㈡(Yrm，≥1一习nFlm)Pr{Y麓，≥1一司F'm) ≥(1一刁(1一习≥l一2Z 取F=E／2即得证明． 定理的证明记Pm=Pr(E册’)一·=Pr(E箔’)，由乘法公式知：． Pr(B1n···nB。)=Pr(B1)Pr(B2lBi)-··Pr(B‰IBln··-nJEi。一1) 根据引理1的推论1知 P。(B1n⋯NBm)≤(1-p)，(1-cp)，⋯(1一cm一·)，：[Ⅱm(1一c¨p)]7 令e(p，c，J)=[兀(1一ci--Ip)]1 o。 7 t=1 因为事件A可表示为A=(BinB2n⋯)，所以 Pr(A)=1一。l。im。。Pr(B1n⋯nBm)≥1—0粤匕[II(1一ci一1p)J1=1一e(p，c，J)m—÷。。竹t——+。oL J 另一方面，通过选择充分大的J或足够小的P，e(p，c，I)可以任意小．这是因为：对于 0Pr(A)=Pr(F1uF2U．．·)=∑Pr(Fm)． 。"t=1 k o。 故部分和∑Pr(Fm)当k一。o时是收敛的，即jk=忌(￡)使∑Pr(％)<￡／4． m=l"i2kq-l 所以Pr(F1u⋯u凡)=∑Pr(Fm)≥Pr(A)一￡／4≥1一E／2，根据引理4，对所有的 m7≥m+d“7(￡／2，m)有 Pr(E}嚣㈡Fm)≥1一E／2 成立．令 d(￡)=max{d”7(￡／2，1)，⋯，d”7(E／2，忌)) 和m0=mo(E)=忌q-d(￡)，那么对m≤惫，上述不等式对所有m7≥m0成立． 万方数据 360 应 用 数 学 学 报 29卷 所以对所有m7≥mo =Pr(Ef写7’)=Pr(Ef写7’IFl)Pr(F1)+··-+Pr(E5写7’IFk)Pr(凡)+Pr(Ef∽而百丽)．Pr(面百丽) ≥Pr(Ef写7’IFl)Pr(F1)+·-·+Pr(E5写7’IFk)Pr(R) ≥(1一￡／2)(Pr(F1)+···+Pr(Fk)) ≥(1一E／2)(1一E／2)≥1—2(￡／2)=1一￡． 定理得证． 由以上定理证明可以看出，当假设2进一步放宽到模型(2)的最优解集非空时，收 敛性结论仍然成立．此时，只需用N+=max{恬ll￡§是最优解)代替引理3．1中的N， 并且在引理2中相应地取△亿2=1／N7，其中Ⅳ7是算法找到的第一棵最优树中弧的个 数．在实际的ACO算法设计中，这是容易实现的． 4 结论， 最小Steiner树问题在实际问题中有着广泛而重要的应用．无线传感器网络的研究 近几年来刚刚兴起，作为其核心问题之一的路由问题，可以看作是最小Steiner树问题． 由于最小Steiner树问题是NP一完全问题，因而设计相应的具有收敛性保证的启发式智 能求解算法具有十分重要的实际意义和理论意义．本文结合最小Steiner树和蚁群优化 算法的特点，设计了求解最小Steiner树的ACO算法；在通常都能满足的假设条件下， 给出了算法的收敛性证明． 应该指出，虽然ACO算法在各种实际问题中的应用相对较多，并且也收到了较好 的实际效果，但对其理论性的研究却相对较少．建立ACO算法完善的理论基础和完整 的理论体系具有重要意义；同时，建立基于ACO的操作性强的最小Steiner树求解算法 也具有重要的理论和应用价值，对于这些问题的探讨与研究是我们今后努力的方向． 参 考 文 献 【1]ColorniA，DorigoM，ManiczzoV．DistributedOptimizationbyAntColonies．Proceedingsof ECAL’91，EuropeanConferenceonArtificialLife．Amsterdam：ElsevierPublishing，1991，134142 [2]DorigoM，ManiezzoV，ColorniA．TheAntSystem：anAutocatalyticOptimizingProcess，Technical ReportTR91—016，PolitecnicodiMilano，1991 [3]DorigoM，GambardellaLM．AntColonySystem：aCooperativeLearningApproachtotheTraveling SalesmanProblem．IEEETransactiononEvolutionaryComputation，1997，1：53—66 【4】GambardellaLM，DorigoM．SolvingSymmetricandAsymmetricTSPsbyAntColonies．Proceedings oftheIEEEConferenceonEvolutionaryComputation，ICEC96，Nagoya，Japan，May20—22，1996， 622-627 『51 StuetzleT，HoosHH．TheMax-minAntSystemandLocalSearchfortheTravelingSalesmanProblem． Proceedingsofthe1997IEEEInternationalConferenceonEvolutionarycomputation(ICEC’97)，NJ： IEEEPress，1997，309—314 [6]ManiezzoA．ExitandApproximateNondeterministicTree—searchProceduresfortheQuadratic AssignmentProblem．INFORMSJournalofComputing，1999，11(4)：358369 [7]GutjahrWJ．AGraph—basedAntSystemandItsConvergence．FututreGener．Comput．Syst．， 2000，16(8)：873—888 [8]GutjahrWJ．AGeneralizedConvergenceResultfortheGraph-basedAntSystemMetaheuristic． ProbabilityintheEngineeringandInformationalSciences，2003，17：545569 万方数据 2期 杨文国、郭田德：求解最小Steiner树的蚁群优化算法及其收敛性 361 [9】GutjahrWJ．ACOAlgorithmswithGuaranteedConvergencetotheOptionalSolution．1nfo．PrD— cessingLett．，2002，82(3)：145—153 [10】StuetzleT，DorigoM．AShortConvergenceProofforaClassofACOAlgorithms．晒EETransactions onEvolutionaryComputation，2002，6(4)：358-365 [11】SinghG，DasS，GosaviSV，PujarS．AntColonyAlgorithmsforSteinerTrees：anApplicationto RoutinginSensorNetworks．In：L．N．deCastroandF．J．yonZubenEds．RecentDevelopmentsin BiologicallyInspiredComputing，2004，181—206(Chapter6) 【12]GilbertEN，PollakHO．SteinerMinimalTrees．s埘MJournalonAppliedMathematics，1966，16： 1-29 【13】WinterP．SteinerProbleminNetworks：aSurvey．Networks，1987，17：129-167 【14】GareyMR，GrahamRL，JohnsonDS．TheComplexityofComputingSteinerMinimalTrees．肌M JournalonAppliedMathematics，1977，32：835-859 【15】GareyMR，JohnsonDS．ComputersandIntractability：aGuidetotheTheoryofNP·Completeness． NewYork：Freeman，1979 [16】BoyceWM．AnImprovedProgramfortheFullSteinerTreeProblem．AGMTransactionson MathematicalSofeware，1977，3：359-385 【17】GanleyJL，CohoonJP．ImprovedComputationof0ptimalRectilinearSteinerMinimalTrees． InternationalJournalofComputationalGeometryandApplications，1997 AnAntColonyOptimizationAlgorithmsfortheMinimum SteinerTreeProblemanditsConvergenceProof YANGWENGUOGUOTIANDE (DepartmentofMathematics，GraduateUniversityoft^eChineseAcademyofSciences，Beijin9100049) (E-mail：yangwg@mails．gucas．ac．cn) AbstractTheminimumSteinertreeproblemisoneoftheNP—hardproblems．whichhas extensiveapplicationsinmanyreal—worldproblem．suchascommunicationsnetwork．Ant colonyoptimizationalgorithmsisarecentlyproposedmetaheuresticapproachforsolving complexcombinatorialoptimizationproblem．Takenoneofthemostimportantissuestothe wirelesssensornetwork，routingproblem，asanexample，theSteinertreemodeliSpresented inthispaper．Ageneralframeworkofantcolonyoptimizationalgorithmsfortheminimum SteinertreeproblemiSdevelopedandtheiterativeprocessofthealgorithmsiSinterpreted asaMarkovprocessindiscretetime．Itisshownthatundercertainconditions．thesolutions generatedineachiterationconvergewithaprobabilitythatcanbemadearbitrailycloseto 1totheOptimalsolutionoftheroutingproblem． Keywordsantcolonyoptimization；minimumSteinertree；algorithms；convergence MR(2000)SubjectClassification68W40 ChineseLibraryClassification0221．7 万方数据 求解最小Steiner树的蚁群优化算法及其收敛性 作者： 杨文国， 郭田德， YANG WENGUO， GUO TIANDE 作者单位： 中国科学院研究生院数学系,北京,100049 刊名： 应用数学学报 英文刊名： ACTA MATHEMATICAE APPLICATAE SINICA 年，卷(期)： 2006,29(2) 被引用次数： 15次 参考文献(17条) 1.Gutjahr W J ACO Algorithms with Guaranteed Convergence to the Optional Solution[外文期刊] 2002(03) 2.Gutjahr W J A Generalized Convergence Result for the Graph-based Ant System Metaheuristic[外文期刊 ] 2003 3.Gutjahr W J A Graph-based Ant System and Its Convergence[外文期刊] 2000(08) 4.Maniezzo A Exact and Approximate Nondeterministic Tree-search Procedures for the Quadratic Assignment Problem[外文期刊] 1999(04) 5.Stuetzle T;Hoos H H The Max-min Ant System and Local Search for the Traveling Salesman Problem 1997 6.Ganley J L;Cohoon J P Improved Computation of Optimal Rectilinear Steiner Minimal Trees 1997 7.Boyce W M An Improved Program for the Full Steiner Tree Problem[外文期刊] 1977 8.Garey M R;Johnson D S Computers and Intractability:a Guide to the Theory of NP-Completeness 1979 9.Garey M R;Graham R L;Johnson D S The Complexity of Computing Steiner Minimal Trees 1977 10.Winter P Steiner Problem in Networks:a Survey 1987 11.Gilbert E N;Pollak H O Steiner Minimal Trees 1966 12.Singh G;Das S;Gosavi S V;Pujar S Ant Colony Algorithms for Steiner Trees:an Application to Routing in Sensor Networks 2004 13.Stuetzle T;Dorigo M A Short Convergence Proof for a Class of ACO Algorithms[外文期刊] 2002(04) 14.Gambardella L M;Dorigo M Solving Symmetric and Asymmetric TSPs by Ant Colonies[外文会议] 1996 15.Dorigo M;Gambardella L M Ant Colony System:a Cooperative Learning Approach to the Traveling Salesman Problem[外文期刊] 1997(1) 16.Dorigo M;Maniezzo V;Colorni A The Ant System:an Autocatalytic Optimizing Process 1991 17.Colorni A;Dorigo M;Maniczzo V Distributed Optimization by Ant Colonies 1991 引证文献(15条) 1.许洪.王华.伊善文 生长森林的蚁群优化算法在Steiner树问题上的应用[期刊论文]-小型微型计算机系统 2010(4) 2.许洪.王华.伊善文 生长森林的蚁群优化算法在Steiner树问题上的应用[期刊论文]-小型微型计算机系统 2010(4) 3.郝婕宇.杨宗霄 基于可视化试验的Exp-Geo算法[期刊论文]-通信技术 2010(1) 4.丁雪枫.马良.丁雪松 基于模拟植物生长算法的求解MCCS问题的研究[期刊论文]-计算机工程与设计 2010(7) 5.李志宇.史浩山 基于最小Steiner树的无线传感器网络数据融合算法[期刊论文]-西北工业大学学报 2009(4) 6.王东.张金荣 大面积森林防火监测中的传感器网络能量均衡路由算法[期刊论文]-重庆工学院学报（自然科学版 ） 2009(10) 7.顾一中.孙亚民.王华.王刚 基于北斗定位系统的新型无线传感器网络路由算法[期刊论文]-兵工学报 2009(3) 8.杨文国.郭田德 时变挥发率条件下求解Steiner树蚁群优化算法的收敛性[期刊论文]-应用数学学报 2008(2) 9.刘群.黄朔 基于遗传优化的WSNs多源单汇路由算法[期刊论文]-辽宁工程技术大学学报（自然科学版） 2008(5) 10.李志宇.史浩山 基于MMAS的无线传感器网络数据融合算法[期刊论文]-计算机应用研究 2008(11) 11.杨宗霄.GAO Yan-ping.程传业.FENG Zhi-qiang.张祖俊 求解最小Steiner树的可视化试验方法[期刊论文]-系统 工程理论与实践 2008(7) 12.黄翰.郝志峰.吴春国.秦勇 蚁群算法的收敛速度分析[期刊论文]-计算机学报 2007(8) 13.杨文国.郭田德.赵彤 基于动态规划的无线传感器网络的路由算法[期刊论文]-计算机研究与发展 2007(5) 14.吴红红.杨文国.赵彤 传感器网络中单源单汇路由问题的模型与算法[期刊论文]-计算机工程与应用 2006(27) 15.王东 无线传感器网络系统设计与应用[学位论文]博士 2006 本文链接：http://d.g.wanfangdata.com.cn/Periodical_yysxxb200602016.aspx