全局優(yōu)化的了望算法

第23卷第2期廣東工業(yè)大學(xué)學(xué)報Vol.23 No.22006年6月Joumal of Guangdong University of TechnologyJune 2006全局優(yōu)化的了望算法蔡延光' ,錢(qián)積新”,孫優(yōu)賢2(1.廣東工業(yè)大學(xué)自動(dòng)化學(xué)院,廣東廣州510090;2.浙江大學(xué)工業(yè)控制技術(shù)國家重點(diǎn)實(shí)驗室,浙江杭州310027)摘要:提出求解全局優(yōu)化問(wèn)題的了望算法.了望算法利用了望技術(shù)確定群山最高點(diǎn)的常識,通過(guò)了望管理機制、了望點(diǎn)產(chǎn)生策略、局部問(wèn)題構造與求解機制，能在較短的時(shí)間內求解全局優(yōu)化問(wèn)題.大量的測試表明，了望算法具有較高的收斂率和較強的獲得問(wèn)題全部解的能力,對初始點(diǎn)幾乎沒(méi)有依賴(lài),參數選擇簡(jiǎn)單.了望算法能夠保證在迭代過(guò)程中迭代點(diǎn)的質(zhì)量逐步變好,所提出的三層次記憶機制極大地提高了望算法的收斂速度.大量的對比測試也表明,在收斂率和全局搜索能力等方面了望算法較遺傳算法有一-定的優(yōu)勢,且在大多數情況下了望算法耗時(shí)較少.由于了望算法是根據人類(lèi)的高級行為智能和推理智能提出的一-種智能算法,它為解決全局優(yōu)化問(wèn)題開(kāi)辟了--條新的途徑.關(guān)鍵詞:了望算法;全局優(yōu)化;智能算法中圈分類(lèi)號:0224文獻標識碼:A文章編號:1007-7162(2006)02-000-11引言最近二十多年來(lái),全局優(yōu)化技術(shù)得到了長(cháng)足的發(fā)展,模擬退火算法、遺傳算法神經(jīng)網(wǎng)絡(luò )算法禁忌搜索算法( Tabu Search)、蟻群算法( Ant Colony Agrithm)等智能算法得到了廣泛而深入的研究,在解決全局優(yōu)化問(wèn)題方面獲得了很大的成功.模擬退火算法[14]是基于物理學(xué)中固體物質(zhì)退火過(guò)程所表現出的特性而發(fā)展起來(lái)的一-種智能算法,屬于一種低級的智能,它的計算量雖然較Monte Carlo方法顯著(zhù)減少,但其全局收斂性能仍然很差遺傳算法[s]是基于生物本能的智能算法,是利用生物進(jìn)化論中優(yōu)勝劣汰、適者生存的原理及遺傳機理而提出的-種智能算法,其主要優(yōu)點(diǎn)是并行性和全局空間搜索;但其計算時(shí)間長(cháng),常常出現早熟收斂神經(jīng)網(wǎng)絡(luò )算法[89]是利用基于聯(lián)結的生物神經(jīng)系統協(xié)同工作原理而設計的- -種智能算法,其計算簡(jiǎn)單、快速;但它的參數魯棒性差,容易陷于局部最優(yōu),有時(shí)可能收斂于問(wèn)題的不可行解禁忌搜索算法([042]是對人類(lèi)智能的--種模擬,具有較強的爬山能力和較好的局部改進(jìn)能力;但它對初始解有較強的依賴(lài)性,迭代過(guò)程是串行的,參數的選擇不當可能造成早熟收斂.蟻群算法[4151 是模擬螞蟻群體行為特征而設計的一種基于動(dòng)物智能的智能算法,利用正反饋原理,蟻群算法具有很強的魯棒性和發(fā)現較好解的能力,是-種基于合作的無(wú)監督機制的并行算法;但是蟻群算法計算時(shí)間較長(cháng),參數選擇更多地依靠實(shí)驗和經(jīng)驗、沒(méi)有一一個(gè)程序化的方法來(lái)確定,且容易出現迭代停止現象.以上提及的五大智能算法在解決實(shí)際問(wèn)題時(shí)都容易陷于局部最優(yōu),且在迭代過(guò)程中不能保證迭代點(diǎn)中國煤化工收稿日期:2005-07-11MHCNMHG基金項目:國家自然科學(xué)基金資助項目(60374062);廣東省自然科學(xué)基金項目(04009488);廣東省科技計劃項目(2004B10101038)作者簡(jiǎn)介:蔡延光( 1963-),男,博士,教授,主要研究方向為組合優(yōu)化、智能優(yōu)化智能決策支持系統..廣東工業(yè)大學(xué)學(xué)報第23卷的質(zhì)量逐步變好.本文基于了望技術(shù)確定群山最高點(diǎn)的常識,提出解決全局優(yōu)化問(wèn)題的了望算法.了望算法本質(zhì)上是- -種基于監督的并行算法,在了望管理機制的協(xié)調下,把了望點(diǎn)產(chǎn)生策略和局部尋優(yōu)算法有機地結合起來(lái),能在較短的時(shí)間內求解全局優(yōu)化問(wèn)題.大量的測試表明,了望算法具有較高的收斂率和較強的獲得問(wèn)題全部解的能力,對初始點(diǎn)幾乎沒(méi)有依賴(lài),參數選擇簡(jiǎn)單,能夠保證在迭代過(guò)程中迭代點(diǎn)的質(zhì)量逐步變好.大量的對比測試也表明,在收斂率和全局搜索能力等方面了望算法較遺傳算法有- -定的優(yōu)勢,且在大多數情況下了望算法耗時(shí)較少.為了加快了望算法的收斂速度,引人了望算法的三層次記憶機制,即基點(diǎn)記憶、了望點(diǎn)記憶、局部尋優(yōu)記憶.了望算法模擬了人類(lèi)的高級行為智能一視覺(jué)智 能、以及根據視覺(jué)信息分析問(wèn)題的推理智能,是一種智能算法,與已知的五大智能算法在原理上有明顯的不同,是解決全局優(yōu)化問(wèn)題的一個(gè)新嘗試.為了實(shí)現方便,用C語(yǔ)言風(fēng)格書(shū)寫(xiě)算法.1了望算法研究全局優(yōu)化問(wèn)題[minF(X),X∈RcE"(1)\R={XIg:(X)≥0,i= 1,2,.m},記G(X)=(g;(X),g2(X),",gm(X))".1.1 基本原理為了表述方便,引入幾個(gè)基本概念.定義1對于問(wèn)題(1),設 R'CR,x°∈R',1)把minF(x)(X∈R')稱(chēng)為x°處的局部?jì)?yōu)化問(wèn)題,在不引起混淆時(shí)簡(jiǎn)稱(chēng)為局部問(wèn)題;求局部問(wèn)題的解稱(chēng)為局部尋優(yōu);2)如果在R'上F(X)是(下)單峰函數,則稱(chēng)R'為F(X)的(下)單峰區域,在不引起混淆時(shí)簡(jiǎn)稱(chēng)為單峰區域.定義2對于問(wèn)題(1),1)了望基準點(diǎn)(簡(jiǎn)稱(chēng)基點(diǎn))是可行域R中的-一個(gè)點(diǎn);2)設x∈R是基點(diǎn),基于基點(diǎn)x°的了望點(diǎn)是可行域R中的-一個(gè)點(diǎn),在不引起混淆時(shí)把基于基點(diǎn)的了望點(diǎn)簡(jiǎn)稱(chēng)為基點(diǎn)的了望點(diǎn)或了望點(diǎn);把x的全部了望點(diǎn)按照某種標準(例如歐氏距離、Hamming距離)分類(lèi),稱(chēng)x8的第k類(lèi)了望點(diǎn)為X8的第k階了望點(diǎn).定義3局部尋優(yōu)算法是一 -個(gè)基 于迭代的優(yōu)化問(wèn)題的求解方法,它具有固有特性:尋優(yōu)過(guò)程所產(chǎn)生的迭代點(diǎn)必須在初始點(diǎn)所在的單峰區域內.很早以前,人類(lèi)就知道通過(guò)了望確定群山最高點(diǎn)的常識.為了尋找(多峰)群山的最高點(diǎn),人們- -般在群山中任意選取某座山的一個(gè)點(diǎn)作為出發(fā)點(diǎn),進(jìn)行局部爬高(即向該座山的最高點(diǎn)攀登),到達該座山的最高點(diǎn)(相對于群山而言是局部最高點(diǎn))后.以此局部最高點(diǎn)作為基點(diǎn)進(jìn)行了望,以尋找比基點(diǎn)“更高的點(diǎn)”;再以此“更高的點(diǎn)”所在中國煤化工點(diǎn)(例如,直接以.此“更高的點(diǎn)”作為出發(fā)點(diǎn)),開(kāi)始下一輪的局部爬高,MHCNMH G點(diǎn).那么,如何通過(guò)了望獲得比基點(diǎn)“更高的點(diǎn)”呢?可以利用下面的常識解決這個(gè)問(wèn)題:站得越高,望得越遠;觀(guān)測目標離得越近,看得越清楚,于是可對它的局部進(jìn)行精細的觀(guān)察;觀(guān)測目標離得越遠,可分辨第2期蔡延光,等:全局優(yōu)化的了望算法3的尺寸越大,只能對其進(jìn)行粗略的觀(guān)察.選擇基點(diǎn)的若干個(gè)了望點(diǎn)作為“更高的點(diǎn)”的候選點(diǎn):在基點(diǎn)附近可稠密地取- -些 了望點(diǎn),而在離基點(diǎn)遠的地方了望點(diǎn)可取得稀疏-些.人們站在基點(diǎn)對了望點(diǎn)進(jìn)行目測，當了望點(diǎn)在水平視線(xiàn)的上方,則認為了望點(diǎn)高于基點(diǎn)(如果忽略觀(guān)測者自身的高度),“更高的點(diǎn)”就是該了望點(diǎn).了望算法是利用以上常識而設計的一-種求解全局優(yōu)化問(wèn)題的智能算法.了望算法由了望管理機制(主要負責算法進(jìn)程控制與協(xié)調)、了望點(diǎn)產(chǎn)生策略(負責產(chǎn)生了望點(diǎn))、局部問(wèn)題構造與求解機制3部分組成,其求解全局優(yōu)化問(wèn)題的基本思路是:1)由了望管理機制確定基點(diǎn);2)由了望點(diǎn)產(chǎn)生策略產(chǎn)生基點(diǎn)的了望點(diǎn);3)由了望管理機制按照- -定的標準選擇了望點(diǎn);4)構造所有被選定的了望點(diǎn)的局部問(wèn)題并用局部尋優(yōu)算法求解這些局部問(wèn)題;5)在獲得所有被選定的局部問(wèn)題的解后,由了望管理機制確定下-個(gè)基點(diǎn),進(jìn)行新- -輪的迭代,直至算法終止條件出現,把當前最好可行解作為問(wèn)題的解.針對以上基本思路,1.2節將討論其中第1)、3)、5)項的實(shí)現問(wèn)題(隱含在算法1中),第2節討論其中第2)項的實(shí)現問(wèn)題，第3節討論其中第4)項的實(shí)現問(wèn)題.1.2算法算法1是了望算法的一種實(shí)現形式,用于求解問(wèn)題(1) ,其核心部分是:①外層循環(huán):控制了望算法的進(jìn)程選擇基點(diǎn)x .當基點(diǎn)數超過(guò)預先設定的最大值或者允許了望標志等于False時(shí)，算法終止運行,輸出最優(yōu)解.②第2層循環(huán):通過(guò)調用算法2,產(chǎn)生基于基點(diǎn)x*的各階了望點(diǎn).③內層循環(huán):選擇了望點(diǎn)進(jìn)行局部尋優(yōu)置允許了望標志的值.算法1求解問(wèn)題(1)的了望算法輸人:目標函數F(X)及約束條件G(X)≥0;控制參數設置:Max. Global Oulook =正整數; 1/(允許考慮的基點(diǎn)個(gè)數,即最大基點(diǎn)數,該參數為預先設定.)Max. Local Outlook =正整數; //(基點(diǎn)的了望點(diǎn)的最大階數, Max Local Oulloo應該取得足夠大,使得對于該基點(diǎn)，在R中不存在(或者可以忽略)基于它的大于Max .Local Oullook階的了望點(diǎn).) .初始:給定初始可行解x°∈R;x*=x°; //基點(diǎn)X咖= x8 ;/到 目前為止的最好可行解Oldxm*n= x"; //臨時(shí)變量LocalXn= x"; //局部問(wèn)題的解Outook _Flg= True; /允許了望標志，= True允許了望, = False不允許了望.Global. Outlook = 0; //基點(diǎn)計數Local. Outlolok=0; /門(mén)望階數While Outlook Flg = True且Global, Outlook < Max .Global .01中國煤化工^YHCNMHGOldX*m= xi;Outlook. Flg = False;4廣東工業(yè)大學(xué)學(xué)報.第23卷如果Global _Outlook =0則Local Oullook =0,否則Local Outlook=1; 1(初始時(shí)因為 x#=x0 ,故需要求解x*處的局部問(wèn)題;但以后的x8本身是前面某個(gè)局部問(wèn)題的解,因此不必求解x°處的局部問(wèn)題.)While Local, Outlook≤Max. Local Outlok //第 2層循環(huán)開(kāi)始Set. Outlook. Points= 中;Generate. Outlook Point( x8 ,Local. Outlook, Set Outlook. Points); //(產(chǎn)生了望點(diǎn),見(jiàn)第2節 .)While Set _Outlook. Points≠φ //內層循環(huán)開(kāi)始取集合Set Outlook. Points 中的第- -個(gè)元素x°;如果F(X°)≤F(x),則//片段 1,選擇了望點(diǎn)進(jìn)行局部尋優(yōu)LocalX"in = Local Search(x"); /(片 段2. Local, Search( X):局部尋優(yōu)算法.其功能是尋找X處的局部問(wèn)題的解(通常把X作為初始點(diǎn)),返回值為局部問(wèn)題的解.見(jiàn)第3節的討論.)如果F(LocalX*)≤F(X")且LocalXmn≠0ldXin //片段 3X咖= Localxmi;Outlook. Flg= True;};在集合Set Oulok Points中刪除x";}; //內層循環(huán)結束Local, Oullook= Local Outlook+1; /1 處理更高階的了望點(diǎn)}; 1/第2層循環(huán)結束Global. .Outlook = Global, Outlook+ 1;x=xin; 11 X咖作為新的基點(diǎn)}; 1/外層 循環(huán)結束輸出最優(yōu)解xmn;結束.2、了望點(diǎn)產(chǎn)生策略1.1節所描述的關(guān)于獲得了望點(diǎn)的常識(即在基7望點(diǎn)，而在離基點(diǎn)遠的地方了望點(diǎn)可取得稀疏一些)可以有多種實(shí)現中國煤化工三種了望點(diǎn)產(chǎn)生策THCNMH略.本節僅討論產(chǎn)生了望點(diǎn)的兩個(gè)策略:方體了望點(diǎn)產(chǎn)土束略相你面」里瓜廠(chǎng)生策略.設x=(x想,x是,，x)"是基點(diǎn),下面討論在x處產(chǎn)生第k階了望點(diǎn)的方體了望點(diǎn)產(chǎn)生策略和球面了望點(diǎn)產(chǎn)生策略..第2期蔡延光，等:全局優(yōu)化的了望算法52.1方體了 望點(diǎn)產(chǎn)生策略方體了望點(diǎn)產(chǎn)生策略是在以x*為中心的棱長(cháng)為2r的n維立方體表面和可行域R的交集中選取x8的第k(k=0,1,2,-.)階了望點(diǎn),其中r=H(h,k,x",F,G),它是h、k、X*、F、G的函數, h( > 0)為預先設定的-一個(gè)常數(稱(chēng)為基本了望步長(cháng)),且ro=0< r< r2<.;當k=0時(shí)，x$是唯一的了望點(diǎn).以n=2為例說(shuō)明由方體了望點(diǎn)產(chǎn)生策略所產(chǎn)生的第k階了望點(diǎn)的幾何意義.例如,第h階了望點(diǎn)取自于{(x+r,x土r)" ,(x士廠(chǎng),程士r)"li=0,1,2,,h;j=0,1,2,-,k-1I∩R(見(jiàn)圖1).下面討論rn 的構造.主要考慮re是h、k的函數的情形,可以用等距法算術(shù)增距法、Fibonacci增距法、幾何增距法確定T.1)等距法當可行域較小時(shí),取r= kh,k=0,1,..(2)此時(shí)τλ1-η=h(k≥0),即rxi-r:(k=0,1,2,")是相等的.2)算術(shù)增距法圖1用方體了望點(diǎn)產(chǎn)生當可行域較大時(shí),取策略產(chǎn)生了望點(diǎn)n,= k(h+1h,k=0,1,2,-.(3)此時(shí)r+1-r=(k+ 1)h(k≥0),即{rx+1-re}是-一個(gè)公差為h的算術(shù)級數.3) Fibonacci 增距法當可行域很大時(shí),取，ro=0,rs=Fa_h+ Tn-_,k=1,2,..(4)F其中F.是 Fibonaci 數,F。=1,F=1,F:= F-1+ F-2.易見(jiàn)，rk+1_τ=p(r- _)=Fk-1F:h(k≥1),即{(r.1- rn)/h }是一個(gè)Fibonaeci級數.4)幾何增距法當可行域很大時(shí),取Tk=°: (1+8)°-1h,k=0,1,2,-.(5)其中δ>0是預設的常數.易見(jiàn)τ+1-n=(1+δ)(r?！鷕n_1)=h(1+δ)*(k≥1),即{rn+1-r}是一個(gè)公比為1 + δ的幾何級數.周知F +1+V5(m→∞)=(1+0.618),如果取δ =0.618, Fibnacai法就可近似地歸結為2幾何增距法的一種特殊形式.5) rn與x有關(guān)中國煤化工例如,當| X II ≠0時(shí),取ro=0,r= |x* (1+8)*CNMH G(6)其期δ>0是預設的常數,1|x* |是x"的范數(例如取X如I =1宮xX ,或者取x =6廣東工業(yè)大學(xué)學(xué)報第23卷21x9I).易見(jiàn),r-n=δ|x* |(1+δ)* =(1+8)(r-r-)(k≥2).如果| x II =0,則式(6)中的| x II用一個(gè)較小的正數代替.根據以上討論,可獲得方體了望點(diǎn)產(chǎn)生策略產(chǎn)生了望點(diǎn)的算法.算法2:用方體了望點(diǎn)產(chǎn)生策略產(chǎn)生了望點(diǎn)Function Generate. .Outlook. Point( x8 , Local, Oullook , Set. .Outlook. Points)1*功能與參數說(shuō)明:以x*為基點(diǎn)產(chǎn)生其第Local Outloloo階的全部了望點(diǎn),了望點(diǎn)保存在集合Set. Outlook. Points 中. *1. {for(i= - Local _Outlook; in≤Local, Outlook;iq ++ ){x= x + sigm(i)riqj; /sigp(x)為符 號函數for (i= - Local, Oullook; i≤Local. Oullook;i + ){ x2=是+sign(iz)rigy;for (ig= - Local Outlook; is ≤Local Outlook;ijz ++ ){ x3= x3+ sigm(iz)rig1;for (in = - Local Outlok; i,≤Local Outlook;in ++ ){x= x +sign(in)ri,i;如果lil,1i,-,1in I中至少有一個(gè)等于Local Outlook,且(x,x,", x)°∈R,則Set Outlook. Points = Set Outoo Points U{(x,x,., x,)"I;};|;2.2球面了望點(diǎn)產(chǎn)生策略球面了望點(diǎn)產(chǎn)生策略是在n維球面(x1-好)*+(xz- 媽)尸 +...+(x。-劃)=了和可行域R的交集中選取x8的第k(k=0,1,2,-.)階了望點(diǎn),其中r與方體了望點(diǎn)產(chǎn)生策略的意義及確定方法完全相同.因為ro=0< r< r2<..., 故在球面了望點(diǎn)產(chǎn)生策略下,同階了望點(diǎn)與X的距離相等,較高階了望點(diǎn)離x較遠.以n=2為例說(shuō)明由球面了望點(diǎn)產(chǎn)生策略所產(chǎn)生的第k階了望點(diǎn)的幾何意義.如果希望至多取q個(gè)第k階了望點(diǎn),則不妨在x出發(fā)的q條射線(xiàn)(q條射線(xiàn)- -般是均勻分布的)與圓周(一好)2 +(xz-始) =芹的交點(diǎn)中選取可行點(diǎn)作為了望點(diǎn)(見(jiàn)圖2).這里.n=a(h,h,X° ,F,G).類(lèi)似于算法2,可獲得球面了望點(diǎn)產(chǎn)生策略產(chǎn)生中國煤化工不再寫(xiě)出。YHCNMHG3局部問(wèn)題構造與局部尋優(yōu)算法了望算法的提出也受到下面設想的推動(dòng):為了求解目標函數是多峰函數的全局優(yōu)化問(wèn)題，第2期蔡延光,等:全局優(yōu)化的了望算法7先把R劃分為數量盡量少的兩兩互不相交的單峰區域(或者,把R .劃分為兩兩互不相交的單峰區域,并使每個(gè)單峰區域盡量大),每個(gè)單峰區域對應- - 個(gè)局部問(wèn)題,這樣把全局優(yōu)化問(wèn)題分解為一系列目標函數是單峰函數的子問(wèn)題(即局部問(wèn)題) ;然后用目標函數是單峰函數的優(yōu)化問(wèn)題的求解方法獲得局部問(wèn)題的解;最后通過(guò)簡(jiǎn)單地比較各局部問(wèn)題的解就可獲得全局優(yōu)化問(wèn)題的解.但是,以上設想直接實(shí)現起來(lái)非常困難.了望算法充分地利用局部尋優(yōu)算法的固有特性構造并求解局部問(wèn)題,既不需要明確地界定單峰區域也不需要準確地劃分R,結合了望點(diǎn)產(chǎn)生策略,解決全.圖2用球面了望點(diǎn)產(chǎn)生局優(yōu)化問(wèn)題,是以上設想的一個(gè)改良.根據局部尋優(yōu)算法的固有特策略產(chǎn)生了望點(diǎn).性,顯然只要給出局部尋優(yōu)的初始點(diǎn)(為了節約計算時(shí)間,通常把了望點(diǎn)作為初始點(diǎn)),就可以獲得局部問(wèn)題的解;只要給出局部尋優(yōu)的初始點(diǎn),局部問(wèn)題隨之確定. .局部尋優(yōu)算法可以通過(guò)對求解目標函數是單峰函數的優(yōu)化問(wèn)題的方法(如一維無(wú)約束優(yōu)化的黃金分割法、成功-失敗法牛頓法,多維無(wú)約束優(yōu)化的擬牛頓法、共軛梯度法、DFP法,以及有約束優(yōu)化問(wèn)題罰函數法、SWIFT法、可行方向法、線(xiàn)性逼近法等)作-些必要 的改造得到,使其最大限度滿(mǎn)足局部尋優(yōu)算法的固有特性.按照這個(gè)思路,我們對以上提及的一- 些算法進(jìn)行了改造.例如局部牛頓法是在牛頓法的基礎上增加了對邊界和拐點(diǎn)等的特別處理而獲得的局部尋優(yōu)算法,局部DFP法是在DFP法的基礎上增加了對邊界等的特別處理而獲得的局部尋優(yōu)算法.限于篇幅,改造過(guò)程從略.4了望算法的記憶機制為了避免在搜索過(guò)的區域進(jìn)行重復搜索,提高算法的收斂速度，現引入了望算法的三層次記憶機制,即基點(diǎn)記憶(第- -層)了望點(diǎn)記憶(第二層)、局部尋優(yōu)記憶(第三層).1)基點(diǎn)記憶基點(diǎn)記憶(MB)記憶全部基點(diǎn).初始,MB= φ;如果x°為基點(diǎn),則MB= MB∪{x}.如果實(shí)行基點(diǎn)記憶,則將算法1的片段3所對應的條件改為:如果F(oalxX*")≤F(xi)且LocalXrin eMB.這樣,可以避免在迭代過(guò)程中重復地把一個(gè) 點(diǎn)作為基點(diǎn).2)了望點(diǎn)記憶了望點(diǎn)記憶(M0)記憶全體構造過(guò)局部問(wèn)題并實(shí)施過(guò)局部尋優(yōu)的了望點(diǎn).初始,MO= φ;如果x是某個(gè)基點(diǎn)的了望點(diǎn),且求解過(guò)x°處的局部問(wèn)題，則MO= MOU{x0}.如果實(shí)施了望點(diǎn)記憶，則將算法1的片段1所對應的條件改為:如果F(x0 )≤F(X")且不存在X'∈MO使|lX'-x° 1l≤e(ε≥0為預設的精度).這樣,對任意點(diǎn)及其附近的點(diǎn)總共至多只能構造- -次局部問(wèn)題.3)局部尋優(yōu)記憶局部尋優(yōu)記憶(ML)記憶局部尋優(yōu)過(guò)程所經(jīng)歷的部分迭代點(diǎn).初始, ML= φ;如果x是局部尋優(yōu)過(guò)程所獲得的一-個(gè)迭代點(diǎn)，且不存在X'∈ML滿(mǎn)足X' = x≤e(e≥0為預設的精度)，則ML= MLU{xk };否則終止此局部尋優(yōu),因為如果F中國煤化工變性,繼續進(jìn)行局部尋優(yōu)的話(huà),則所得到的迭代點(diǎn)的質(zhì)量-般不會(huì )比以TMCHC N M H G當有局部尋優(yōu)記憶時(shí),算法1的片段1所對應的條件也可改為:如果F(x°)≤F∈x")且不存在X'∈ML使|X' - x0 II≤ε(ε≥0為預設的精度).8廣東工業(yè)大學(xué)學(xué)報第23卷MB、MO、ML體現了了望算法3個(gè)層次的記憶,顯然有MBcML,MOcML,根據需要選擇其中-一個(gè)或多個(gè)記憶.為了實(shí)現對MB、MO、ML中的元素進(jìn)行快速查找(如二分查找),在迭代過(guò)程中應該同時(shí)對它們的元素進(jìn)行排序(如二分插人排序).5測試結果與評述用了望算法對一些著(zhù)名的基準問(wèn)題( Benchmark Problem, 如見(jiàn)文獻[ 16])進(jìn)行大量的反復測試,結果令人滿(mǎn)意.為了進(jìn)一一步了解了望算法的性能,我們用遺傳算法做對比測試.限于篇幅,這里僅列出對4個(gè)著(zhù)名的基準問(wèn)題所作的對比測試結果,并進(jìn)行了簡(jiǎn)要的評述.所有算法使用C語(yǔ)言編程實(shí)現,并在賽揚2.4G臺式機上執行. .問(wèn)題1 F,(x)=x +3x2-9x,x∈[-5,5].該問(wèn)題的解有兩個(gè):x=1,x= -5.min FI(x)= -5.周知,非智能算法如成功-失敗法、0.618法很難獲得該問(wèn)題的解.問(wèn)題2 Rosenbrock 函數:F2(x,x2)=10(x2- x)*+(1- x)",x∈[- 10,10],i=1,2.最優(yōu)解(1,1)" ,min F2(x,x2)=0.問(wèn)題3六駝峰- 駝背(Six Hump Camel- Back)函數: F;(x),x2)=4x-2.1項+ 9/3+ x-4x經(jīng)+4xi,x∈[-5,5],i=1,2.該問(wèn)題的解有兩個(gè):(0.089842, - 0. 712656)",(- 0.089842,0.712656)" ,min F3(x,xz)=- 1.0316285.問(wèn)題4球體模型(Sphere Mode):F(xn,*,.",xn)=對+垃+...+ x起,x∈[- 100, 100],i=1,2,,n.取n=8.最優(yōu)解x; =0(i=1,2,",n),min F4(x],x2)=0.了望算法的參數設置見(jiàn)表1.表1了望算法的參數設置問(wèn)題參數設置1)最大基點(diǎn)數:[4,6]中的隨機整數.2)基點(diǎn)的了望點(diǎn)的最大階數:11.3)初始解:可行域中的隨機數.4)了望點(diǎn)產(chǎn)生策略:方體了望點(diǎn)產(chǎn)生策略,其中基本了望步長(cháng)為[0.9,1.1 ]中的隨機數, r用等距法確定.5)局部尋優(yōu)算法:局部牛頓法,精度為[ 10~4 , 10-6 ]中的隨機數.6)記憶機制:基點(diǎn)記憶、了望點(diǎn)記憶.21)基點(diǎn)的了望點(diǎn)的最大階數:22.2)局部尋優(yōu)算法:局部DFP法,精度為[ 10~*, 10~°]中的隨機數.3)其余參數同問(wèn)題1的設置.31)基點(diǎn)的了望點(diǎn)的最大階數:11.2)其余參數同問(wèn)題2的設置.4 1)最大基點(diǎn)數:[2,4]中的隨機整數. 2)基點(diǎn)的了望點(diǎn)的最大階數:4.3)了望點(diǎn)產(chǎn)生策略:球面了望點(diǎn)產(chǎn)生策略,其中基本中國煤化工數,每階了望點(diǎn)的數目為[4,6]中的隨機整數(在對應的球面上近似均YHCNMHG定.4)局部尋優(yōu)算法:局部DFP法,精度為[10-* , 10-°]中的5)其余參數同問(wèn)題1的設置.第2期蔡延光,等:全局優(yōu)化的了望算法遺傳算法的參數設置:二進(jìn)制編碼方法,種群數為80,交叉概率為0.6,變異概率為0.001.收斂準則:4個(gè)問(wèn)題的遺傳代數分別為200、1003002000(實(shí)際上,我們對這4個(gè)問(wèn)題中的每一個(gè)分別做了1002003005001000、2000、5000代的遺傳算法運行測試，從時(shí)間耗費和收斂率方面綜合考慮,前述所列遺傳代數于相應問(wèn)題為最有利的配置) .測試結果及評述見(jiàn)表2,其中:收斂率=收斂次數/測試次數.表2了望算法和遺傳算法的對比測試結果 與評述測試平均耗收斂問(wèn)題算法次數時(shí)/s 率/%評述1了望算法3000.23 100了望算法平均耗時(shí)只有遺傳算法的12,兩個(gè)算法的收斂率接近.遺傳算法500 0.44 99 但是, 了望算法每次測試都能同時(shí)獲得兩個(gè)解,而遺傳算法只有66%的概率同時(shí)獲得兩個(gè)解.22.36 100了望算法平均耗時(shí)較多,大約是遺傳算法的4倍.主要原因是作為遺傳算法3003.1940局部尋優(yōu)算法的局部DFP法在解該問(wèn)題的局部問(wèn)題時(shí)效率不高統計表明,每次測試執行局部尋優(yōu)算法的次數是問(wèn)題1的4.6倍左右;這就是說(shuō),若該問(wèn)題的局部尋優(yōu)效率達到問(wèn)題1的局部尋效率的1/3,則平均耗時(shí)應與遺傳算法接近.遺傳算法收斂率太低,不到了望算法的1/2.3了望算法3000.93 100了望算法的平均耗時(shí)稍少,兩個(gè)算法的收斂率接近.了望算法同時(shí)遺傳算法5001.0598獲得兩個(gè)解的概率為99.6%;而遺傳算法所有收斂測試都只能獲得-個(gè)解,且每個(gè)解單獨出現的機會(huì )相等.40.82100了望算法平均耗時(shí)只有遺傳算法的1/5,了望算法的收斂率比遺傳遺傳算法3004.1583算法高17%.下面結合測試結果,對了望算法作--些簡(jiǎn)要的討論.1)已知的測試表明,了望算法在取最大基點(diǎn)數4時(shí)能夠求解最優(yōu)解的個(gè)數至多為2的所有測試問(wèn)題(包括本文的4個(gè)基準問(wèn)題).顯然,最大基點(diǎn)數設置得越大,獲得全部解的可能性就越大.然而,大量的測試表明,最大基點(diǎn)數增大到一定程度后,其繼續增大并不會(huì )導致算法的平均耗時(shí)的明顯增大.例如，問(wèn)題1取最大基點(diǎn)數4和最大基點(diǎn)數6的平均耗時(shí)相差只有1毫s左右.事實(shí)上,通過(guò)分析算法1就會(huì )發(fā)現:獲得了問(wèn)題的全部解后到算法結束的一段運 行所耗時(shí)間很少.2)在表1中,基點(diǎn)的了望點(diǎn)的最大階數的值是照顧到基點(diǎn)、了望點(diǎn)產(chǎn)生策略及基本了望步長(cháng)的所有組合情況而設定的,故在大多數情況下稍嫌大了一些.為了減少算法1的第2層循環(huán)的循環(huán)次數、提高算法的收斂速度,根據該參數的含義,可以對算法1稍作修改:在第2層循環(huán)開(kāi)始的前1行,根據基點(diǎn)、了望點(diǎn)產(chǎn)生策略、基本了望步長(cháng)和可行域的結構動(dòng)態(tài)設置基點(diǎn)的了望點(diǎn)的最大階數為一-個(gè)盡可能小的值(這一點(diǎn)不難做到，而且動(dòng)態(tài)設置的值大多數情況下比表1設置的值要小).3)基本了望步長(cháng)越小,了望算法對可行域將搜索中國煤化工版之,耗時(shí)減少,但可能遺漏重要的搜索區域因此需要對基本了望步長(cháng)MHCNMHG望步長(cháng)設置原則:當可行域較小時(shí),基本了望步長(cháng)應取得較小(如問(wèn)題1~3),反之應取得較大(如問(wèn)題4).當然,也可以在算法執行過(guò)程中對每個(gè)基點(diǎn)動(dòng)態(tài)地確定基本了望步長(cháng).10廣東工業(yè)大學(xué)學(xué)報第23卷4)在同一精度下對了望算法和遺傳算法進(jìn)行時(shí)間耗費比較似乎更加客觀(guān).但是,我們的測試結果表明,遺傳算法有些測試進(jìn)行了10多個(gè)小時(shí)而最好解仍未達到事先預定的精度要求,實(shí)際上陷入局部最優(yōu),造成無(wú)法確定該測試的時(shí)間耗費.本節所列的4個(gè)問(wèn)題都曾出現過(guò)這種久不收斂的測試.6結論了望算法的原理和大量的測試表明,它具有如下特點(diǎn):1)收斂率高.已知的測試表明,了望算法收斂率接近100% ,高于遺傳算法.2)全局搜索能力強.已知的測試表明,了望算法獲得問(wèn)題全部解的概率超過(guò)0.99,較遺傳算法有一-定的優(yōu)勢.了望算法利用了望點(diǎn)產(chǎn)生策略使迭代進(jìn)程逃出局部最優(yōu),保證搜索的多樣性,進(jìn)而實(shí)現全局搜索,能保證迭代過(guò)程中所得到的迭代點(diǎn)的質(zhì)量逐步變好.3)速度快.在大多數情況下,了望算法的時(shí)間耗費比遺傳算法要少.特別是了望算法的記憶機制的應用能極大地減少時(shí)間耗費.4)魯棒性.了望算法的魯棒性表現在3個(gè)方面:首先是它所能解決的問(wèn)題的廣泛性,只要問(wèn)題形如式(1);其次是它對初始點(diǎn)幾乎沒(méi)有依賴(lài)性;最后是它的控制參數選擇簡(jiǎn)單.5)并行性.了望算法并行化非常容易,例如用某個(gè)處理機(作為主處理機)對算法進(jìn)程進(jìn)行控制和協(xié)調產(chǎn)生了望點(diǎn)等,而其它處理機構造了望點(diǎn)處的局部問(wèn)題并用局部尋優(yōu)算法求解之.6)經(jīng)過(guò)一些簡(jiǎn)單的改造,了望算法能有效地利用目標函數是單峰函數的優(yōu)化問(wèn)題的方法進(jìn)行局部尋優(yōu),而后者經(jīng)過(guò)半個(gè)多世紀的研究獲得了不少的快速算法.這-優(yōu)勢是基本遺傳算法所不具有的.，致謝:感謝鄒谷山同志所作的部分測試工作.參考文獻:[1]Metropolis N, Rosenbluh A w, Rosenbluth M N, Teller A H, Teller E. Equations o state calulations by fast computingmachines[J]. J Chemical Physics, 1953, 23: 1087-1091.[]irkpatrick s, Celatt C D, Vecchi M P. Optumization by similated anealing[J]. Science, 1983, 220: 671-680.[3]蔡延光,錢(qián)積新，孫優(yōu)賢.多重運輸調度問(wèn)題的模擬退火算法[J].系統工程理論與實(shí)踐，198,， 18(10): 11-15.[4]i M, Tang H. Aplication of chaos in simulated anelingJ]. Chaos, Solions and Fracals, 2004, 21(4): 933-941.[S]olland J H. Adapation in Nature and Arifciad Systems[ M] .Ann Arbor MI: University of Michigan Pess, 1975.[6]蔡延光,錢(qián)積新，孫優(yōu)賢.多重運輸調度問(wèn)題的遺傳算法與遺傳局部搜索[J].系統工程理論與實(shí)踐，1997,17(12): 101-107.[7]Baker B M, Ayechew M A. A genetic algihim for the vehicle routing prblem[J]. Computers andOPerations Research,2003,30(5):787-800.[8]HopfieldJJ, Tamk D w. Neural coputaion of decision in opimizaion poblems[J]. Biological Cybemetis, 1985, 52:141-152.[9]Zhang Y. Global exponential convergence of recurent neural netwr cretical Computer Soi-中國煤化Ience, 2004, 312(23): 281-293.[ 10]Glover F. Heritic for integer programming using surrogate conslTYHCNMH Gr7, 8: 156166.6[11]蔡延光，錢(qián)積新,孫優(yōu)賢.帶時(shí)間窗的多重運輸調度問(wèn)題的自適應Tabu Search算法[J].系統工程理論與實(shí)踐，2000, 20(12): 42-50.第2期蔡延光,等:全局優(yōu)化的了望算法[12]Caricato P, Chiani G, Grieco A, Gueriero E. Parallel tabu search for a pickup and delivery problem under track cont-ention[J]. Parallel Computing, 2003, 29(5) :631-639.[13]Ho s C, Haugland D. A tabu search heunstic for the vehicle routing problem with time windows and split deliveries[J].Computers & Operations Research, 2004, 31(12): 1947-1964.[14]Colormi A, Dorigo M, Maniezo V. Distributed optimization by ant colonies[ C]/Proc. of the Fist European Conf. OnArificial Life, Paris: Elsevier Publishing, 1991: 134-142.[15]Badr A, Fahmy A. A proof of convergence for ant algorithms[J]. Information Sciences, 2004, 160(14): 267-279.[ 16]王凌.智能優(yōu)化算法及其應用[M].北京:清華大學(xué)出版社, 2001.Outlook Algorithm for Global OptimizationCAI Yan-guang' ,QIAN Ji-xin2 , SUN You-xian2(1. Faculty of Automation, Guangdong University of Technology, Guangzhou 510090, China2. National Labonatory of Industrial Control Technology , Zhejiang University, Hangzhou 310027, China)Abstract: Outlook algorithm is presented to solve global optimization problems in this paper. Based onommon knowledge that one decides the highest point of mountains by outlook, by employing supervisionmechanism of outlook, strategies of generating outlook points and mechanisms of constructing and solvinglocal problems, outlook algorithm can solve any global optimization problem in a relatively short time. Alarge number of tests show that outlook algorithm is of higher convergence ratio, stronger capacity to obtainall solutions of global optimization problems, litle dependence on initial solution and simplicity in decidingits control parameters. It can be ensured that the quality of iterative points will gradually improve in the it-erative process of outlook algorithm. The three-level memory mechanism of outlook algorithm greatly in-creases its convergence rate. A large number of contrast tests also show that outlook algorithm has advan-tage over genetic algorithm in convergence ratio and capacity of global search, and spends less time thangenetic algorithm in most cases. Since outlook algorithm simulates human behavioral and inferential itell-gence, it exploits a brand new way to solve global optimization problems.Key words:outlook algorithm; global optimization; itelligent algorithm中國煤化工MYHCNMHG