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