用于函數優(yōu)化的小世界優(yōu)化算法

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