第23卷第2期廣東工業(yè)大學(xué)學(xué)報(bào)Vol.23 No.22006年6月Joumal of Guangdong University of TechnologyJune 2006全局優(yōu)化的了望算法蔡延光' ,錢積新”,孫優(yōu)賢2(1.廣東工業(yè)大學(xué)自動(dòng)化學(xué)院,廣東廣州510090;2.浙江大學(xué)工業(yè)控制技術(shù)國(guó)家重點(diǎn)實(shí)驗(yàn)室,浙江杭州310027)摘要:提出求解全局優(yōu)化問題的了望算法.了望算法利用了望技術(shù)確定群山最高點(diǎn)的常識(shí),通過了望管理機(jī)制、了望點(diǎn)產(chǎn)生策略、局部問題構(gòu)造與求解機(jī)制，能在較短的時(shí)間內(nèi)求解全局優(yōu)化問題.大量的測(cè)試表明，了望算法具有較高的收斂率和較強(qiáng)的獲得問題全部解的能力,對(duì)初始點(diǎn)幾乎沒有依賴,參數(shù)選擇簡(jiǎn)單.了望算法能夠保證在迭代過程中迭代點(diǎn)的質(zhì)量逐步變好,所提出的三層次記憶機(jī)制極大地提高了望算法的收斂速度.大量的對(duì)比測(cè)試也表明,在收斂率和全局搜索能力等方面了望算法較遺傳算法有一-定的優(yōu)勢(shì),且在大多數(shù)情況下了望算法耗時(shí)較少.由于了望算法是根據(jù)人類的高級(jí)行為智能和推理智能提出的一-種智能算法,它為解決全局優(yōu)化問題開辟了--條新的途徑.關(guān)鍵詞:了望算法;全局優(yōu)化;智能算法中圈分類號(hào):0224文獻(xiàn)標(biāo)識(shí)碼:A文章編號(hào):1007-7162(2006)02-000-11引言最近二十多年來,全局優(yōu)化技術(shù)得到了長(zhǎng)足的發(fā)展,模擬退火算法、遺傳算法神經(jīng)網(wǎng)絡(luò)算法禁忌搜索算法( Tabu Search)、蟻群算法( Ant Colony Agrithm)等智能算法得到了廣泛而深入的研究,在解決全局優(yōu)化問題方面獲得了很大的成功.模擬退火算法[14]是基于物理學(xué)中固體物質(zhì)退火過程所表現(xiàn)出的特性而發(fā)展起來的一-種智能算法,屬于一種低級(jí)的智能,它的計(jì)算量雖然較Monte Carlo方法顯著減少,但其全局收斂性能仍然很差遺傳算法[s]是基于生物本能的智能算法,是利用生物進(jìn)化論中優(yōu)勝劣汰、適者生存的原理及遺傳機(jī)理而提出的-種智能算法,其主要優(yōu)點(diǎn)是并行性和全局空間搜索;但其計(jì)算時(shí)間長(zhǎng),常常出現(xiàn)早熟收斂神經(jīng)網(wǎng)絡(luò)算法[89]是利用基于聯(lián)結(jié)的生物神經(jīng)系統(tǒng)協(xié)同工作原理而設(shè)計(jì)的- -種智能算法,其計(jì)算簡(jiǎn)單、快速;但它的參數(shù)魯棒性差,容易陷于局部最優(yōu),有時(shí)可能收斂于問題的不可行解禁忌搜索算法([042]是對(duì)人類智能的--種模擬,具有較強(qiáng)的爬山能力和較好的局部改進(jìn)能力;但它對(duì)初始解有較強(qiáng)的依賴性,迭代過程是串行的,參數(shù)的選擇不當(dāng)可能造成早熟收斂.蟻群算法[4151 是模擬螞蟻群體行為特征而設(shè)計(jì)的一種基于動(dòng)物智能的智能算法,利用正反饋原理,蟻群算法具有很強(qiáng)的魯棒性和發(fā)現(xiàn)較好解的能力,是-種基于合作的無監(jiān)督機(jī)制的并行算法;但是蟻群算法計(jì)算時(shí)間較長(zhǎng),參數(shù)選擇更多地依靠實(shí)驗(yàn)和經(jīng)驗(yàn)、沒有一一個(gè)程序化的方法來確定,且容易出現(xiàn)迭代停止現(xiàn)象.以上提及的五大智能算法在解決實(shí)際問題時(shí)都容易陷于局部最優(yōu),且在迭代過程中不能保證迭代點(diǎn)中國(guó)煤化工收稿日期:2005-07-11MHCNMHG基金項(xiàng)目:國(guó)家自然科學(xué)基金資助項(xiàng)目(60374062);廣東省自然科學(xué)基金項(xiàng)目(04009488);廣東省科技計(jì)劃項(xiàng)目(2004B10101038)作者簡(jiǎn)介:蔡延光( 1963-),男,博士,教授,主要研究方向?yàn)榻M合優(yōu)化、智能優(yōu)化智能決策支持系統(tǒng)..廣東工業(yè)大學(xué)學(xué)報(bào)第23卷的質(zhì)量逐步變好.本文基于了望技術(shù)確定群山最高點(diǎn)的常識(shí),提出解決全局優(yōu)化問題的了望算法.了望算法本質(zhì)上是- -種基于監(jiān)督的并行算法,在了望管理機(jī)制的協(xié)調(diào)下,把了望點(diǎn)產(chǎn)生策略和局部尋優(yōu)算法有機(jī)地結(jié)合起來,能在較短的時(shí)間內(nèi)求解全局優(yōu)化問題.大量的測(cè)試表明,了望算法具有較高的收斂率和較強(qiáng)的獲得問題全部解的能力,對(duì)初始點(diǎn)幾乎沒有依賴,參數(shù)選擇簡(jiǎn)單,能夠保證在迭代過程中迭代點(diǎn)的質(zhì)量逐步變好.大量的對(duì)比測(cè)試也表明,在收斂率和全局搜索能力等方面了望算法較遺傳算法有- -定的優(yōu)勢(shì),且在大多數(shù)情況下了望算法耗時(shí)較少.為了加快了望算法的收斂速度,引人了望算法的三層次記憶機(jī)制,即基點(diǎn)記憶、了望點(diǎn)記憶、局部尋優(yōu)記憶.了望算法模擬了人類的高級(jí)行為智能一視覺智 能、以及根據(jù)視覺信息分析問題的推理智能,是一種智能算法,與已知的五大智能算法在原理上有明顯的不同,是解決全局優(yōu)化問題的一個(gè)新嘗試.為了實(shí)現(xiàn)方便,用C語言風(fēng)格書寫算法.1了望算法研究全局優(yōu)化問題[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對(duì)于問題(1),設(shè) R'CR,x°∈R',1)把minF(x)(X∈R')稱為x°處的局部?jī)?yōu)化問題,在不引起混淆時(shí)簡(jiǎn)稱為局部問題;求局部問題的解稱為局部尋優(yōu);2)如果在R'上F(X)是(下)單峰函數(shù),則稱R'為F(X)的(下)單峰區(qū)域,在不引起混淆時(shí)簡(jiǎn)稱為單峰區(qū)域.定義2對(duì)于問題(1),1)了望基準(zhǔn)點(diǎn)(簡(jiǎn)稱基點(diǎn))是可行域R中的-一個(gè)點(diǎn);2)設(shè)x∈R是基點(diǎn),基于基點(diǎn)x°的了望點(diǎn)是可行域R中的-一個(gè)點(diǎn),在不引起混淆時(shí)把基于基點(diǎn)的了望點(diǎn)簡(jiǎn)稱為基點(diǎn)的了望點(diǎn)或了望點(diǎn);把x的全部了望點(diǎn)按照某種標(biāo)準(zhǔn)(例如歐氏距離、Hamming距離)分類,稱x8的第k類了望點(diǎn)為X8的第k階了望點(diǎn).定義3局部尋優(yōu)算法是一 -個(gè)基 于迭代的優(yōu)化問題的求解方法,它具有固有特性:尋優(yōu)過程所產(chǎn)生的迭代點(diǎn)必須在初始點(diǎn)所在的單峰區(qū)域內(nèi).很早以前,人類就知道通過了望確定群山最高點(diǎn)的常識(shí).為了尋找(多峰)群山的最高點(diǎn),人們- -般在群山中任意選取某座山的一個(gè)點(diǎn)作為出發(fā)點(diǎn),進(jìn)行局部爬高(即向該座山的最高點(diǎn)攀登),到達(dá)該座山的最高點(diǎn)(相對(duì)于群山而言是局部最高點(diǎn))后.以此局部最高點(diǎn)作為基點(diǎn)進(jìn)行了望,以尋找比基點(diǎn)“更高的點(diǎn)”;再以此“更高的點(diǎn)”所在中國(guó)煤化工點(diǎn)(例如,直接以.此“更高的點(diǎn)”作為出發(fā)點(diǎn)),開始下一輪的局部爬高,MHCNMH G點(diǎn).那么,如何通過了望獲得比基點(diǎn)“更高的點(diǎn)”呢?可以利用下面的常識(shí)解決這個(gè)問題:站得越高,望得越遠(yuǎn);觀測(cè)目標(biāo)離得越近,看得越清楚,于是可對(duì)它的局部進(jìn)行精細(xì)的觀察;觀測(cè)目標(biāo)離得越遠(yuǎn),可分辨第2期蔡延光,等:全局優(yōu)化的了望算法3的尺寸越大,只能對(duì)其進(jìn)行粗略的觀察.選擇基點(diǎn)的若干個(gè)了望點(diǎn)作為“更高的點(diǎn)”的候選點(diǎn):在基點(diǎn)附近可稠密地取- -些 了望點(diǎn),而在離基點(diǎn)遠(yuǎn)的地方了望點(diǎn)可取得稀疏-些.人們站在基點(diǎn)對(duì)了望點(diǎn)進(jìn)行目測(cè)，當(dāng)了望點(diǎn)在水平視線的上方,則認(rèn)為了望點(diǎn)高于基點(diǎn)(如果忽略觀測(cè)者自身的高度),“更高的點(diǎn)”就是該了望點(diǎn).了望算法是利用以上常識(shí)而設(shè)計(jì)的一-種求解全局優(yōu)化問題的智能算法.了望算法由了望管理機(jī)制(主要負(fù)責(zé)算法進(jìn)程控制與協(xié)調(diào))、了望點(diǎn)產(chǎn)生策略(負(fù)責(zé)產(chǎn)生了望點(diǎn))、局部問題構(gòu)造與求解機(jī)制3部分組成,其求解全局優(yōu)化問題的基本思路是:1)由了望管理機(jī)制確定基點(diǎn);2)由了望點(diǎn)產(chǎn)生策略產(chǎn)生基點(diǎn)的了望點(diǎn);3)由了望管理機(jī)制按照- -定的標(biāo)準(zhǔn)選擇了望點(diǎn);4)構(gòu)造所有被選定的了望點(diǎn)的局部問題并用局部尋優(yōu)算法求解這些局部問題;5)在獲得所有被選定的局部問題的解后,由了望管理機(jī)制確定下-個(gè)基點(diǎn),進(jìn)行新- -輪的迭代,直至算法終止條件出現(xiàn),把當(dāng)前最好可行解作為問題的解.針對(duì)以上基本思路,1.2節(jié)將討論其中第1)、3)、5)項(xiàng)的實(shí)現(xiàn)問題(隱含在算法1中),第2節(jié)討論其中第2)項(xiàng)的實(shí)現(xiàn)問題，第3節(jié)討論其中第4)項(xiàng)的實(shí)現(xiàn)問題.1.2算法算法1是了望算法的一種實(shí)現(xiàn)形式,用于求解問題(1) ,其核心部分是:①外層循環(huán):控制了望算法的進(jìn)程選擇基點(diǎn)x .當(dāng)基點(diǎn)數(shù)超過預(yù)先設(shè)定的最大值或者允許了望標(biāo)志等于False時(shí)，算法終止運(yùn)行,輸出最優(yōu)解.②第2層循環(huán):通過調(diào)用算法2,產(chǎn)生基于基點(diǎn)x*的各階了望點(diǎn).③內(nèi)層循環(huán):選擇了望點(diǎn)進(jìn)行局部尋優(yōu)置允許了望標(biāo)志的值.算法1求解問題(1)的了望算法輸人:目標(biāo)函數(shù)F(X)及約束條件G(X)≥0;控制參數(shù)設(shè)置:Max. Global Oulook =正整數(shù); 1/(允許考慮的基點(diǎn)個(gè)數(shù),即最大基點(diǎn)數(shù),該參數(shù)為預(yù)先設(shè)定.)Max. Local Outlook =正整數(shù); //(基點(diǎn)的了望點(diǎn)的最大階數(shù), Max Local Oulloo應(yīng)該取得足夠大,使得對(duì)于該基點(diǎn)，在R中不存在(或者可以忽略)基于它的大于Max .Local Oullook階的了望點(diǎn).) .初始:給定初始可行解x°∈R;x*=x°; //基點(diǎn)X咖= x8 ;/到 目前為止的最好可行解Oldxm*n= x"; //臨時(shí)變量LocalXn= x"; //局部問題的解Outook _Flg= True; /允許了望標(biāo)志，= True允許了望, = False不允許了望.Global. Outlook = 0; //基點(diǎn)計(jì)數(shù)Local. Outlolok=0; /門望階數(shù)While Outlook Flg = True且Global, Outlook < Max .Global .01中國(guó)煤化工^YHCNMHGOldX*m= xi;Outlook. Flg = False;4廣東工業(yè)大學(xué)學(xué)報(bào).第23卷如果Global _Outlook =0則Local Oullook =0,否則Local Outlook=1; 1(初始時(shí)因?yàn)?x#=x0 ,故需要求解x*處的局部問題;但以后的x8本身是前面某個(gè)局部問題的解,因此不必求解x°處的局部問題.)While Local, Outlook≤Max. Local Outlok //第 2層循環(huán)開始Set. Outlook. Points= 中;Generate. Outlook Point( x8 ,Local. Outlook, Set Outlook. Points); //(產(chǎn)生了望點(diǎn),見第2節(jié) .)While Set _Outlook. Points≠φ //內(nèi)層循環(huán)開始取集合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處的局部問題的解(通常把X作為初始點(diǎn)),返回值為局部問題的解.見第3節(jié)的討論.)如果F(LocalX*)≤F(X")且LocalXmn≠0ldXin //片段 3X咖= Localxmi;Outlook. Flg= True;};在集合Set Oulok Points中刪除x";}; //內(nèi)層循環(huán)結(jié)束Local, Oullook= Local Outlook+1; /1 處理更高階的了望點(diǎn)}; 1/第2層循環(huán)結(jié)束Global. .Outlook = Global, Outlook+ 1;x=xin; 11 X咖作為新的基點(diǎn)}; 1/外層 循環(huán)結(jié)束輸出最優(yōu)解xmn;結(jié)束.2、了望點(diǎn)產(chǎn)生策略1.1節(jié)所描述的關(guān)于獲得了望點(diǎn)的常識(shí)(即在基7望點(diǎn)，而在離基點(diǎn)遠(yuǎn)的地方了望點(diǎn)可取得稀疏一些)可以有多種實(shí)現(xiàn)中國(guó)煤化工三種了望點(diǎn)產(chǎn)生策THCNMH略.本節(jié)僅討論產(chǎn)生了望點(diǎn)的兩個(gè)策略:方體了望點(diǎn)產(chǎn)土束略相你面」里瓜廠生策略.設(shè)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*為中心的棱長(zhǎng)為2r的n維立方體表面和可行域R的交集中選取x8的第k(k=0,1,2,-.)階了望點(diǎn),其中r=H(h,k,x",F,G),它是h、k、X*、F、G的函數(shù), h( > 0)為預(yù)先設(shè)定的-一個(gè)常數(shù)(稱為基本了望步長(zhǎng)),且ro=0< r< r2<.;當(dāng)k=0時(shí)，x$是唯一的了望點(diǎn).以n=2為例說明由方體了望點(diǎn)產(chǎn)生策略所產(chǎn)生的第k階了望點(diǎn)的幾何意義.例如,第h階了望點(diǎn)取自于{(x+r,x土r)" ,(x士廠,程士r)"li=0,1,2,,h;j=0,1,2,-,k-1I∩R(見圖1).下面討論rn 的構(gòu)造.主要考慮re是h、k的函數(shù)的情形,可以用等距法算術(shù)增距法、Fibonacci增距法、幾何增距法確定T.1)等距法當(dāng)可行域較小時(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)生當(dāng)可行域較大時(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ù)級(jí)數(shù).3) Fibonacci 增距法當(dāng)可行域很大時(shí),取，ro=0,rs=Fa_h+ Tn-_,k=1,2,..(4)F其中F.是 Fibonaci 數(shù),F。=1,F=1,F:= F-1+ F-2.易見，rk+1_τ=p(r- _)=Fk-1F:h(k≥1),即{(r.1- rn)/h }是一個(gè)Fibonaeci級(jí)數(shù).4)幾何增距法當(dāng)可行域很大時(shí),取Tk=°: (1+8)°-1h,k=0,1,2,-.(5)其中δ>0是預(yù)設(shè)的常數(shù).易見τ+1-n=(1+δ)(r?！鷕n_1)=h(1+δ)*(k≥1),即{rn+1-r}是一個(gè)公比為1 + δ的幾何級(jí)數(shù).周知F +1+V5(m→∞)=(1+0.618),如果取δ =0.618, Fibnacai法就可近似地歸結(jié)為2幾何增距法的一種特殊形式.5) rn與x有關(guān)中國(guó)煤化工例如,當(dāng)| X II ≠0時(shí),取ro=0,r= |x* (1+8)*CNMH G(6)其期δ>0是預(yù)設(shè)的常數(shù),1|x* |是x"的范數(shù)(例如取X如I =1宮xX ,或者取x =6廣東工業(yè)大學(xué)學(xué)報(bào)第23卷21x9I).易見,r-n=δ|x* |(1+δ)* =(1+8)(r-r-)(k≥2).如果| x II =0,則式(6)中的| x II用一個(gè)較小的正數(shù)代替.根據(jù)以上討論,可獲得方體了望點(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*功能與參數(shù)說明:以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)為符 號(hào)函數(shù)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)生策略的意義及確定方法完全相同.因?yàn)閞o=0< r< r2<..., 故在球面了望點(diǎn)產(chǎn)生策略下,同階了望點(diǎn)與X的距離相等,較高階了望點(diǎn)離x較遠(yuǎn).以n=2為例說明由球面了望點(diǎn)產(chǎn)生策略所產(chǎn)生的第k階了望點(diǎn)的幾何意義.如果希望至多取q個(gè)第k階了望點(diǎn),則不妨在x出發(fā)的q條射線(q條射線- -般是均勻分布的)與圓周(一好)2 +(xz-始) =芹的交點(diǎn)中選取可行點(diǎn)作為了望點(diǎn)(見圖2).這里.n=a(h,h,X° ,F,G).類似于算法2,可獲得球面了望點(diǎn)產(chǎn)生策略產(chǎn)生中國(guó)煤化工不再寫出。YHCNMHG3局部問題構(gòu)造與局部尋優(yōu)算法了望算法的提出也受到下面設(shè)想的推動(dòng):為了求解目標(biāo)函數(shù)是多峰函數(shù)的全局優(yōu)化問題，第2期蔡延光,等:全局優(yōu)化的了望算法7先把R劃分為數(shù)量盡量少的兩兩互不相交的單峰區(qū)域(或者,把R .劃分為兩兩互不相交的單峰區(qū)域,并使每個(gè)單峰區(qū)域盡量大),每個(gè)單峰區(qū)域?qū)?yīng)- - 個(gè)局部問題,這樣把全局優(yōu)化問題分解為一系列目標(biāo)函數(shù)是單峰函數(shù)的子問題(即局部問題) ;然后用目標(biāo)函數(shù)是單峰函數(shù)的優(yōu)化問題的求解方法獲得局部問題的解;最后通過簡(jiǎn)單地比較各局部問題的解就可獲得全局優(yōu)化問題的解.但是,以上設(shè)想直接實(shí)現(xiàn)起來非常困難.了望算法充分地利用局部尋優(yōu)算法的固有特性構(gòu)造并求解局部問題,既不需要明確地界定單峰區(qū)域也不需要準(zhǔn)確地劃分R,結(jié)合了望點(diǎn)產(chǎn)生策略,解決全.圖2用球面了望點(diǎn)產(chǎn)生局優(yōu)化問題,是以上設(shè)想的一個(gè)改良.根據(jù)局部尋優(yōu)算法的固有特策略產(chǎn)生了望點(diǎn).性,顯然只要給出局部尋優(yōu)的初始點(diǎn)(為了節(jié)約計(jì)算時(shí)間,通常把了望點(diǎn)作為初始點(diǎn)),就可以獲得局部問題的解;只要給出局部尋優(yōu)的初始點(diǎn),局部問題隨之確定. .局部尋優(yōu)算法可以通過對(duì)求解目標(biāo)函數(shù)是單峰函數(shù)的優(yōu)化問題的方法(如一維無約束優(yōu)化的黃金分割法、成功-失敗法牛頓法,多維無約束優(yōu)化的擬牛頓法、共軛梯度法、DFP法,以及有約束優(yōu)化問題罰函數(shù)法、SWIFT法、可行方向法、線性逼近法等)作-些必要 的改造得到,使其最大限度滿足局部尋優(yōu)算法的固有特性.按照這個(gè)思路,我們對(duì)以上提及的一- 些算法進(jìn)行了改造.例如局部牛頓法是在牛頓法的基礎(chǔ)上增加了對(duì)邊界和拐點(diǎn)等的特別處理而獲得的局部尋優(yōu)算法,局部DFP法是在DFP法的基礎(chǔ)上增加了對(duì)邊界等的特別處理而獲得的局部尋優(yōu)算法.限于篇幅,改造過程從略.4了望算法的記憶機(jī)制為了避免在搜索過的區(qū)域進(jìn)行重復(fù)搜索,提高算法的收斂速度，現(xiàn)引入了望算法的三層次記憶機(jī)制,即基點(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所對(duì)應(yīng)的條件改為:如果F(oalxX*")≤F(xi)且LocalXrin eMB.這樣,可以避免在迭代過程中重復(fù)地把一個(gè) 點(diǎn)作為基點(diǎn).2)了望點(diǎn)記憶了望點(diǎn)記憶(M0)記憶全體構(gòu)造過局部問題并實(shí)施過局部尋優(yōu)的了望點(diǎn).初始,MO= φ;如果x是某個(gè)基點(diǎn)的了望點(diǎn),且求解過x°處的局部問題，則MO= MOU{x0}.如果實(shí)施了望點(diǎn)記憶，則將算法1的片段1所對(duì)應(yīng)的條件改為:如果F(x0 )≤F(X")且不存在X'∈MO使|lX'-x° 1l≤e(ε≥0為預(yù)設(shè)的精度).這樣,對(duì)任意點(diǎn)及其附近的點(diǎn)總共至多只能構(gòu)造- -次局部問題.3)局部尋優(yōu)記憶局部尋優(yōu)記憶(ML)記憶局部尋優(yōu)過程所經(jīng)歷的部分迭代點(diǎn).初始, ML= φ;如果x是局部尋優(yōu)過程所獲得的一-個(gè)迭代點(diǎn)，且不存在X'∈ML滿足X' = x≤e(e≥0為預(yù)設(shè)的精度)，則ML= MLU{xk };否則終止此局部尋優(yōu),因?yàn)槿绻鸉中國(guó)煤化工變性,繼續(xù)進(jìn)行局部尋優(yōu)的話,則所得到的迭代點(diǎn)的質(zhì)量-般不會(huì)比以TMCHC N M H G當(dāng)有局部尋優(yōu)記憶時(shí),算法1的片段1所對(duì)應(yīng)的條件也可改為:如果F(x°)≤F∈x")且不存在X'∈ML使|X' - x0 II≤ε(ε≥0為預(yù)設(shè)的精度).8廣東工業(yè)大學(xué)學(xué)報(bào)第23卷MB、MO、ML體現(xiàn)了了望算法3個(gè)層次的記憶,顯然有MBcML,MOcML,根據(jù)需要選擇其中-一個(gè)或多個(gè)記憶.為了實(shí)現(xiàn)對(duì)MB、MO、ML中的元素進(jìn)行快速查找(如二分查找),在迭代過程中應(yīng)該同時(shí)對(duì)它們的元素進(jìn)行排序(如二分插人排序).5測(cè)試結(jié)果與評(píng)述用了望算法對(duì)一些著名的基準(zhǔn)問題( Benchmark Problem, 如見文獻(xiàn)[ 16])進(jìn)行大量的反復(fù)測(cè)試,結(jié)果令人滿意.為了進(jìn)一一步了解了望算法的性能,我們用遺傳算法做對(duì)比測(cè)試.限于篇幅,這里僅列出對(duì)4個(gè)著名的基準(zhǔn)問題所作的對(duì)比測(cè)試結(jié)果,并進(jìn)行了簡(jiǎn)要的評(píng)述.所有算法使用C語言編程實(shí)現(xiàn),并在賽揚(yáng)2.4G臺(tái)式機(jī)上執(zhí)行. .問題1 F,(x)=x +3x2-9x,x∈[-5,5].該問題的解有兩個(gè):x=1,x= -5.min FI(x)= -5.周知,非智能算法如成功-失敗法、0.618法很難獲得該問題的解.問題2 Rosenbrock 函數(shù):F2(x,x2)=10(x2- x)*+(1- x)",x∈[- 10,10],i=1,2.最優(yōu)解(1,1)" ,min F2(x,x2)=0.問題3六駝峰- 駝背(Six Hump Camel- Back)函數(shù): F;(x),x2)=4x-2.1項(xiàng)+ 9/3+ x-4x經(jīng)+4xi,x∈[-5,5],i=1,2.該問題的解有兩個(gè):(0.089842, - 0. 712656)",(- 0.089842,0.712656)" ,min F3(x,xz)=- 1.0316285.問題4球體模型(Sphere Mode):F(xn,*,.",xn)=對(duì)+垃+...+ x起,x∈[- 100, 100],i=1,2,,n.取n=8.最優(yōu)解x; =0(i=1,2,",n),min F4(x],x2)=0.了望算法的參數(shù)設(shè)置見表1.表1了望算法的參數(shù)設(shè)置問題參數(shù)設(shè)置1)最大基點(diǎn)數(shù):[4,6]中的隨機(jī)整數(shù).2)基點(diǎn)的了望點(diǎn)的最大階數(shù):11.3)初始解:可行域中的隨機(jī)數(shù).4)了望點(diǎn)產(chǎn)生策略:方體了望點(diǎn)產(chǎn)生策略,其中基本了望步長(zhǎng)為[0.9,1.1 ]中的隨機(jī)數(shù), r用等距法確定.5)局部尋優(yōu)算法:局部牛頓法,精度為[ 10~4 , 10-6 ]中的隨機(jī)數(shù).6)記憶機(jī)制:基點(diǎn)記憶、了望點(diǎn)記憶.21)基點(diǎn)的了望點(diǎn)的最大階數(shù):22.2)局部尋優(yōu)算法:局部DFP法,精度為[ 10~*, 10~°]中的隨機(jī)數(shù).3)其余參數(shù)同問題1的設(shè)置.31)基點(diǎn)的了望點(diǎn)的最大階數(shù):11.2)其余參數(shù)同問題2的設(shè)置.4 1)最大基點(diǎn)數(shù):[2,4]中的隨機(jī)整數(shù). 2)基點(diǎn)的了望點(diǎn)的最大階數(shù):4.3)了望點(diǎn)產(chǎn)生策略:球面了望點(diǎn)產(chǎn)生策略,其中基本中國(guó)煤化工數(shù),每階了望點(diǎn)的數(shù)目為[4,6]中的隨機(jī)整數(shù)(在對(duì)應(yīng)的球面上近似均YHCNMHG定.4)局部尋優(yōu)算法:局部DFP法,精度為[10-* , 10-°]中的5)其余參數(shù)同問題1的設(shè)置.第2期蔡延光,等:全局優(yōu)化的了望算法遺傳算法的參數(shù)設(shè)置:二進(jìn)制編碼方法,種群數(shù)為80,交叉概率為0.6,變異概率為0.001.收斂準(zhǔn)則:4個(gè)問題的遺傳代數(shù)分別為200、1003002000(實(shí)際上,我們對(duì)這4個(gè)問題中的每一個(gè)分別做了1002003005001000、2000、5000代的遺傳算法運(yùn)行測(cè)試，從時(shí)間耗費(fèi)和收斂率方面綜合考慮,前述所列遺傳代數(shù)于相應(yīng)問題為最有利的配置) .測(cè)試結(jié)果及評(píng)述見表2,其中:收斂率=收斂次數(shù)/測(cè)試次數(shù).表2了望算法和遺傳算法的對(duì)比測(cè)試結(jié)果 與評(píng)述測(cè)試平均耗收斂問題算法次數(shù)時(shí)/s 率/%評(píng)述1了望算法3000.23 100了望算法平均耗時(shí)只有遺傳算法的12,兩個(gè)算法的收斂率接近.遺傳算法500 0.44 99 但是, 了望算法每次測(cè)試都能同時(shí)獲得兩個(gè)解,而遺傳算法只有66%的概率同時(shí)獲得兩個(gè)解.22.36 100了望算法平均耗時(shí)較多,大約是遺傳算法的4倍.主要原因是作為遺傳算法3003.1940局部尋優(yōu)算法的局部DFP法在解該問題的局部問題時(shí)效率不高統(tǒng)計(jì)表明,每次測(cè)試執(zhí)行局部尋優(yōu)算法的次數(shù)是問題1的4.6倍左右;這就是說,若該問題的局部尋優(yōu)效率達(dá)到問題1的局部尋效率的1/3,則平均耗時(shí)應(yīng)與遺傳算法接近.遺傳算法收斂率太低,不到了望算法的1/2.3了望算法3000.93 100了望算法的平均耗時(shí)稍少,兩個(gè)算法的收斂率接近.了望算法同時(shí)遺傳算法5001.0598獲得兩個(gè)解的概率為99.6%;而遺傳算法所有收斂測(cè)試都只能獲得-個(gè)解,且每個(gè)解單獨(dú)出現(xiàn)的機(jī)會(huì)相等.40.82100了望算法平均耗時(shí)只有遺傳算法的1/5,了望算法的收斂率比遺傳遺傳算法3004.1583算法高17%.下面結(jié)合測(cè)試結(jié)果,對(duì)了望算法作--些簡(jiǎn)要的討論.1)已知的測(cè)試表明,了望算法在取最大基點(diǎn)數(shù)4時(shí)能夠求解最優(yōu)解的個(gè)數(shù)至多為2的所有測(cè)試問題(包括本文的4個(gè)基準(zhǔn)問題).顯然,最大基點(diǎn)數(shù)設(shè)置得越大,獲得全部解的可能性就越大.然而,大量的測(cè)試表明,最大基點(diǎn)數(shù)增大到一定程度后,其繼續(xù)增大并不會(huì)導(dǎo)致算法的平均耗時(shí)的明顯增大.例如，問題1取最大基點(diǎn)數(shù)4和最大基點(diǎn)數(shù)6的平均耗時(shí)相差只有1毫s左右.事實(shí)上,通過分析算法1就會(huì)發(fā)現(xiàn):獲得了問題的全部解后到算法結(jié)束的一段運(yùn) 行所耗時(shí)間很少.2)在表1中,基點(diǎn)的了望點(diǎn)的最大階數(shù)的值是照顧到基點(diǎn)、了望點(diǎn)產(chǎn)生策略及基本了望步長(zhǎng)的所有組合情況而設(shè)定的,故在大多數(shù)情況下稍嫌大了一些.為了減少算法1的第2層循環(huán)的循環(huán)次數(shù)、提高算法的收斂速度,根據(jù)該參數(shù)的含義,可以對(duì)算法1稍作修改:在第2層循環(huán)開始的前1行,根據(jù)基點(diǎn)、了望點(diǎn)產(chǎn)生策略、基本了望步長(zhǎng)和可行域的結(jié)構(gòu)動(dòng)態(tài)設(shè)置基點(diǎn)的了望點(diǎn)的最大階數(shù)為一-個(gè)盡可能小的值(這一點(diǎn)不難做到，而且動(dòng)態(tài)設(shè)置的值大多數(shù)情況下比表1設(shè)置的值要小).3)基本了望步長(zhǎng)越小,了望算法對(duì)可行域?qū)⑺阉髦袊?guó)煤化工版之,耗時(shí)減少,但可能遺漏重要的搜索區(qū)域因此需要對(duì)基本了望步長(zhǎng)MHCNMHG望步長(zhǎng)設(shè)置原則:當(dāng)可行域較小時(shí),基本了望步長(zhǎng)應(yīng)取得較小(如問題1~3),反之應(yīng)取得較大(如問題4).當(dāng)然,也可以在算法執(zhí)行過程中對(duì)每個(gè)基點(diǎn)動(dòng)態(tài)地確定基本了望步長(zhǎng).10廣東工業(yè)大學(xué)學(xué)報(bào)第23卷4)在同一精度下對(duì)了望算法和遺傳算法進(jìn)行時(shí)間耗費(fèi)比較似乎更加客觀.但是,我們的測(cè)試結(jié)果表明,遺傳算法有些測(cè)試進(jìn)行了10多個(gè)小時(shí)而最好解仍未達(dá)到事先預(yù)定的精度要求,實(shí)際上陷入局部最優(yōu),造成無法確定該測(cè)試的時(shí)間耗費(fèi).本節(jié)所列的4個(gè)問題都曾出現(xiàn)過這種久不收斂的測(cè)試.6結(jié)論了望算法的原理和大量的測(cè)試表明,它具有如下特點(diǎn):1)收斂率高.已知的測(cè)試表明,了望算法收斂率接近100% ,高于遺傳算法.2)全局搜索能力強(qiáng).已知的測(cè)試表明,了望算法獲得問題全部解的概率超過0.99,較遺傳算法有一-定的優(yōu)勢(shì).了望算法利用了望點(diǎn)產(chǎn)生策略使迭代進(jìn)程逃出局部最優(yōu),保證搜索的多樣性,進(jìn)而實(shí)現(xiàn)全局搜索,能保證迭代過程中所得到的迭代點(diǎn)的質(zhì)量逐步變好.3)速度快.在大多數(shù)情況下,了望算法的時(shí)間耗費(fèi)比遺傳算法要少.特別是了望算法的記憶機(jī)制的應(yīng)用能極大地減少時(shí)間耗費(fèi).4)魯棒性.了望算法的魯棒性表現(xiàn)在3個(gè)方面:首先是它所能解決的問題的廣泛性,只要問題形如式(1);其次是它對(duì)初始點(diǎn)幾乎沒有依賴性;最后是它的控制參數(shù)選擇簡(jiǎn)單.5)并行性.了望算法并行化非常容易,例如用某個(gè)處理機(jī)(作為主處理機(jī))對(duì)算法進(jìn)程進(jìn)行控制和協(xié)調(diào)產(chǎn)生了望點(diǎn)等,而其它處理機(jī)構(gòu)造了望點(diǎn)處的局部問題并用局部尋優(yōu)算法求解之.6)經(jīng)過一些簡(jiǎn)單的改造,了望算法能有效地利用目標(biāo)函數(shù)是單峰函數(shù)的優(yōu)化問題的方法進(jìn)行局部尋優(yōu),而后者經(jīng)過半個(gè)多世紀(jì)的研究獲得了不少的快速算法.這-優(yōu)勢(shì)是基本遺傳算法所不具有的.，致謝:感謝鄒谷山同志所作的部分測(cè)試工作.參考文獻(xiàn):[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]蔡延光,錢積新，孫優(yōu)賢.多重運(yùn)輸調(diào)度問題的模擬退火算法[J].系統(tǒng)工程理論與實(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]蔡延光,錢積新，孫優(yōu)賢.多重運(yùn)輸調(diào)度問題的遺傳算法與遺傳局部搜索[J].系統(tǒng)工程理論與實(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-中國(guó)煤化Ience, 2004, 312(23): 281-293.[ 10]Glover F. Heritic for integer programming using surrogate conslTYHCNMH Gr7, 8: 156166.6[11]蔡延光，錢積新,孫優(yōu)賢.帶時(shí)間窗的多重運(yùn)輸調(diào)度問題的自適應(yīng)Tabu Search算法[J].系統(tǒng)工程理論與實(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)化算法及其應(yīng)用[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中國(guó)煤化工MYHCNMHG