第39卷第9期西安交通大學(xué)學(xué)報(bào)Vol.39 No92005年9月JOURNAL OF XI'AN JIAOTONG UNIVERSITYSep. 2005用于函數(shù)優(yōu)化的小世界優(yōu)化算法杜海峰，莊健， 張進(jìn)華，王孫安(西安交通大學(xué)機(jī)械工程學(xué)院，710049, 西安)摘要:借鑒小世界現(xiàn)象的有關(guān)機(jī)理,構(gòu)造了不同的小世界優(yōu)化算子,主要包括局域短連接搜索算子和隨機(jī)長(zhǎng)連接搜索算子.將優(yōu)化過(guò)程視為在搜索空間(網(wǎng)絡(luò))中從候選解向最優(yōu)解的信息傳遞過(guò)程,利用小世界現(xiàn)象有效信息傳遞的有關(guān)機(jī)理實(shí)現(xiàn)了-種新的優(yōu)化算法一小世界優(yōu)化算法.通過(guò)對(duì)復(fù)雜函數(shù)的優(yōu)化問(wèn)題進(jìn)行仿真試驗(yàn),表明與相應(yīng)遺傳算法相比，新算法可以更好地保持解的多樣性,能夠有效地避免陷入局部極小值的問(wèn)題，并在-定程度上克服了早熟和遺傳算法欺騙問(wèn)題,并且收斂速度快，因此具有解決復(fù)雜問(wèn)題的潛力.關(guān)鍵詞:小世界現(xiàn)象;優(yōu)化算法;函數(shù)優(yōu)化中圖分類號(hào): O224文獻(xiàn)標(biāo)識(shí)碼: A文章編號(hào): 0253-987X(2005)09-1011-05Small-World Phenomenon for Function OptimizationDu Haifeng，Zhuang Jian，Zhang J inhua，Wang Sun 'an .(School of Mechanical Engineering, Xi an Jiaotong University, Xi an 710049, China)Abstract: Inspired by the mechanism of small- world phenomenon，some small- world optimization opera-tors, mainly including the local short- range searching operator and random long range searching operator，were constructed. The optimization was considered as a process where information transmits from candi-date solution to optimal solution in search space ( networks). And a new optimization algorithm， smallworld optimization algorithm (SWOA)，was explored on the basis of the effective information transmissionmechanism of the small- world phenomenon. Compared with the corresponding genetic algorithms， thesimulated results of some complex functions optimization indicate that SWOA enables to enhance the diver-sity of the population with a higher convergence rate and avoid the prematurity and genetic algorithm de-ceptive problem to some extent.Keywords: small- world phenomenon; optimization algorithm; function optimization小世界現(xiàn)象源于社會(huì)心理學(xué)家Milgram在20問(wèn)題，也迅速成為人工智能、復(fù)雜性理論探討的熱世紀(jì)60年代有關(guān)追蹤美國(guó)社交網(wǎng)絡(luò)中最短路徑的點(diǎn),其研究成果已經(jīng)在互聯(lián)網(wǎng)控制[3]、愛(ài)滋病傳播預(yù)研究.相關(guān)結(jié)果表明，在社交網(wǎng)絡(luò)中存在著短路測(cè)41和生物學(xué)蛋白質(zhì)網(wǎng)絡(luò)動(dòng)力學(xué)研究[5]等許多領(lǐng)域徑,即人們只要知道自己認(rèn)識(shí)的人,就能很快地把信得到了成功的應(yīng)用，但優(yōu)化領(lǐng)域中有關(guān)小世界現(xiàn)象件轉(zhuǎn)發(fā)到任何遠(yuǎn)方目標(biāo)，這-現(xiàn)象也稱為六度分離的討論和成果還少見報(bào)道.問(wèn)題. Watts和Strogatz1998年在Nature雜志.上發(fā)優(yōu)化變量精度確定以后,優(yōu)化空間就是優(yōu)化變表的論文[2],使得小世界現(xiàn)象逐漸被計(jì)算機(jī)科學(xué)家量組成的網(wǎng)格(絡(luò))空間,因此本文將優(yōu)化過(guò)程視為重視并被迅速上升為網(wǎng)絡(luò)論,并有望成為繼系統(tǒng)論、在搜中國(guó)煤化工解向最優(yōu)解的信息傳遞信息論和控制論之后與計(jì)算機(jī)相關(guān)的重要理論.這過(guò)程YHCNMHQ信息傳遞的有關(guān)機(jī)理一涉及社會(huì)學(xué)、數(shù)學(xué)和計(jì)算科學(xué)問(wèn)題的多學(xué)科交叉來(lái)構(gòu)造新的優(yōu)化搜索算法.本文首先介紹了小世界收稿日期: 2004-11-25.作者簡(jiǎn)介:杜海峰(1972~),男,副教授.基金項(xiàng)目:陜西省自然科學(xué)基金資助項(xiàng)目(2004F29)1012西安交通大學(xué)學(xué)報(bào)第39卷現(xiàn)象的一般原理,并基于小世界原理來(lái)重新描述優(yōu)問(wèn)題的求解精度,由x1-x2組成如圖2所示的搜索化搜索過(guò)程,然后在構(gòu)造小世界局域短連接搜索算空間,x、x2只在圓圈處取值.不失一般性,設(shè)點(diǎn)T子和隨機(jī)長(zhǎng)連接搜索算子的基礎(chǔ)上,探討了一種小是最優(yōu)解,B是初始候選解,優(yōu)化問(wèn)題P的求解過(guò)世界優(yōu)化算法(SWOA) ,最后以函數(shù)優(yōu)化問(wèn)題為例，程就是從B到T的搜索,可以視為圖中虛線示意的對(duì)比了小世界優(yōu)化算法和相應(yīng)遺傳算法的有關(guān)性從B到T的信息傳遞過(guò)程.上述優(yōu)化搜索網(wǎng)絡(luò)與能.Watts和Strogatz構(gòu)造的帶有多個(gè)隨機(jī)連接的二維格點(diǎn)小世界網(wǎng)絡(luò)[2]非常相似,因此如果在搜索過(guò)程1小世界網(wǎng)絡(luò)與優(yōu)化過(guò)程考慮小世界效應(yīng)，即在局部搜索(局域短連接)的基小世界現(xiàn)象揭示了客觀世界許多復(fù)雜網(wǎng)絡(luò)(如礎(chǔ)上,引入全局隨機(jī)搜索(長(zhǎng)距離隨機(jī)連接),并強(qiáng)調(diào)社會(huì)網(wǎng)絡(luò))運(yùn)動(dòng)中最為有效的信息傳遞方式,即一個(gè)局部行為導(dǎo)致的全局性結(jié)果,即可以構(gòu)造具有小世高度聚集的包含了局部連接節(jié)點(diǎn)的子網(wǎng),連同一些界效應(yīng)的優(yōu)化搜索算法一小世 界優(yōu)化算法.隨機(jī)的有助于產(chǎn)生短路徑的長(zhǎng)距離隨機(jī)連接就可以提高信息傳遞效率.小世界現(xiàn)象目前還沒(méi)有精確的。候選解定義,一般認(rèn)為,如果網(wǎng)絡(luò)中兩節(jié)點(diǎn)間的平均距離L隨網(wǎng)絡(luò)節(jié)點(diǎn)數(shù)目N成對(duì)數(shù)增長(zhǎng),即L∞lnN,則稱該網(wǎng)絡(luò)具有小世界現(xiàn)象.Watts和Strogatz的小世界網(wǎng)絡(luò)是從規(guī)則網(wǎng)絡(luò)向隨機(jī)網(wǎng)絡(luò)過(guò)渡的中間網(wǎng)絡(luò)形態(tài)[2].圖1以一維環(huán)狀點(diǎn)陣為例來(lái)說(shuō)明這一網(wǎng)絡(luò)的構(gòu)造方法. 在- -個(gè)有T:最優(yōu)化解; B:初始侯選解N個(gè)節(jié)點(diǎn)環(huán)狀的網(wǎng)絡(luò)中,每個(gè)結(jié)點(diǎn)向與它最近鄰的圖2二維空間搜 索問(wèn)題的節(jié)點(diǎn)網(wǎng)格K個(gè)結(jié)點(diǎn)連接出K條邊(如圖la所示),對(duì)圖la中的每條邊,以概率p改變它的目的節(jié)點(diǎn)來(lái)重新連2基于小世界原理的函數(shù)優(yōu)化算法接,并保證沒(méi)有重復(fù)的邊出現(xiàn).當(dāng)p=0. 05時(shí),上述網(wǎng)絡(luò)的變化如圖1b所示,當(dāng)p=1時(shí),如圖1c所示.社會(huì)網(wǎng)絡(luò)有關(guān)小世界效應(yīng)的試驗(yàn)已經(jīng)證明了在需要特別指出的是，上述構(gòu)造過(guò)程需滿足N》K》局部連接中加入隨機(jī)長(zhǎng)連接時(shí),信息傳遞更加高效lnN》1,其中K>》InN是為了保證隨機(jī)網(wǎng)絡(luò)可以被和實(shí)用，因此構(gòu)造小世界優(yōu)化算法的要點(diǎn)應(yīng)該是合連接.適的局部搜索策略和全局搜索方法.2.1基本定義考慮到算法的有效性和效率以及Milgram相關(guān)社會(huì)學(xué)試驗(yàn)的設(shè)計(jì)[1],算法中參與搜索或信息傳遞的起始點(diǎn)應(yīng)該是一個(gè)候選解的集合而非單點(diǎn). S稱為傳遞節(jié)點(diǎn)集合,簡(jiǎn)稱節(jié)點(diǎn)集,節(jié)點(diǎn)s=s...s.,s∈S,也是x的編碼,記為s=e(x),而x稱為s的解(a)規(guī)則網(wǎng)絡(luò)(b)小世界網(wǎng)絡(luò)(c)隨機(jī)網(wǎng)絡(luò)圖1小世界模型的構(gòu)造過(guò)程(N= 20,K=4)碼,記為x=e -+(s),其中e和e -1分別表示編碼和解碼方式.一般將s位串分為m段,每段長(zhǎng)為l,由圖1可見，小世界網(wǎng)絡(luò)是-個(gè)有局域聚集的l=2I,每段分別對(duì)應(yīng)x;的編碼.在實(shí)踐中,常短連接子網(wǎng)連同一些由長(zhǎng)距離隨機(jī)連接構(gòu)成的網(wǎng)絡(luò).Kleinberg認(rèn)為,小世界問(wèn)題是關(guān)于路由算法的用的節(jié)點(diǎn)編碼形式有二進(jìn)制和十進(jìn)制，本文采用0-效率問(wèn)題,可完全依靠本地信息來(lái)找到到達(dá)目的地中國(guó)煤化工-1-1-0-1-0-0 即表示的有效路徑”.某節(jié)MHCNMHG考慮目標(biāo)函數(shù)f(x) ,d≤x≤u的最小值優(yōu)化問(wèn)小世界搜索空間記為集I,即s∈I;S={s;,s2,題P,其中x=xz....ER”,d= (d,d,.，...為 s的n元組.對(duì)于P,定義信息傳遞的目標(biāo)集dm }和u={u,u,,um }是對(duì)應(yīng)自變量的可行解區(qū)T={s∈I:f(e+(s))=f*=間,即x;西酶數(shù)據(jù),=,2,..,m.當(dāng)m=2時(shí),考慮min(f(x):d≤x≤u)}(1)第9期杜海峰,等:用于函數(shù)優(yōu)化的小世界優(yōu)化算法1013式中:f*是目標(biāo)函數(shù)f的最優(yōu)值.對(duì)于S,0(S)=|S與有效，本文借鑒進(jìn)化計(jì)算中的倒位操作來(lái)構(gòu)造r.∩T|表示S中包含的最優(yōu)解個(gè)數(shù).算法2設(shè)定全局長(zhǎng)連接概率 p和e.定義d(s,s;)=lIs,-s,lI ,為s,,s;∈s間的距begin離,對(duì)于二進(jìn)制編碼-般采用海明距離,而十進(jìn)制編碼多采用歐式距離.把節(jié)點(diǎn)s;的e鄰域節(jié)點(diǎn)集合定repeat義為s;(k)←-s;(k)ζ(s;)= {s,10< |s-s;|I≤l;s,∈S} (2)p←rand(0- 1)并記ζ(s;)|為ζ(s;)的元素?cái)?shù)目;ζ(s;)為s;的非lif pe.ζ(S)= {s,|l< Is,-sll; s,∈S} (3)s,(k)←-s;(k)|",進(jìn)-步地如果s;ET且e(ζ(s;))=|ζ(s)∩T|=0，end if那么一定有i←i計(jì)+10(ζ(s;)=| ζ(s)∩TI≥1(4)until i=n2.2主要算子end局域短連接搜索算子ψ的主要作用是將信息式中:rand(0一1)表示產(chǎn)生0到1之間均勻分布的從s;(k)傳遞給ζ(s;(k))中與T最靠近的節(jié)點(diǎn)s;(k隨機(jī)數(shù);s(k)|"表示顛倒s;(k)中μ位到r位之間的+1),且e比較小,記為s;(k+1)←Y(s;(k)). 實(shí)踐字符順序,例如中,由于Iζ(s;(k))|很大，例如對(duì)于20位二進(jìn)制編s;(k) 1 0101100 1100-110011010100碼的節(jié)點(diǎn)s;(k),Iζ (s;(k))|=19,而|ζ(s;(k))|=ζ (s;(k))|+C器,因此一般隨機(jī)地從ζ(s;(k))中取r中的力相當(dāng)于進(jìn)化算法中倒位操作的倒位n(k)》2004年第9期目錄選登1.懸浮軸承參數(shù)不確定控制的研究.... 劉淑琴,富志宏,陳大融(1009)2.基于廣義密度函數(shù)的隨機(jī)模糊結(jié)構(gòu)廣義可靠性分析胡太彬,陳建軍,馬芳,等(1022)3.基于角色的訪問(wèn)權(quán)限控制在ERP系統(tǒng)中的應(yīng)用中國(guó)煤化工蔡宗琰,王寧生(1025)4.一種新的散亂數(shù)據(jù)邊界點(diǎn)提取方法:MYHCNMH G堯宇,張樹生,等(1037)5.大變形柔順機(jī)構(gòu)的驅(qū)動(dòng)特性研究.............................. 李海燕,張憲民,彭惠青(1040)6.納米氧化物/聚四氟乙烯復(fù)合材料的研究黃岳元,任杰(1051)7.制造系統(tǒng)智能前端的研究..............................陸寶春,張衛(wèi),孫宇(1057)8.間歇性弟屢賺眺機(jī)器人落地沖擊及穩(wěn)定性分析............... 劉壯志,朱劍英,吳洪濤,等(1068) .