新的混合智能優(yōu)化算法及其多目標優(yōu)化應用

1、1292計算機應用第30卷文章編號:1(X)1- 9081(2010) ()5- 1290- 03新的混合智能優(yōu)化算法及其多目標優(yōu)化應用張漢強，盧建剛，陳金水(浙江人學匸業(yè)控制技術M家巫點實驗空，杭州310027)(1 叩han輕 i|)c zjl hIu rn)摘 要：針對人工魚髀算法后期收效速度較慢、解精度不商的不足，按照分階段尋優(yōu)和變參數(shù)尋優(yōu)的改進策略， 并結合禁忌搜索算法中的相關規(guī)則提出I種新的混合智能優(yōu)化算法。該算法將尋優(yōu)過程分為饋定最優(yōu)解或者局部 解鄰域和求得高精度最優(yōu)解兩 飾段，每 飾段設置不同的參數(shù)并結合禁忌搜索算法以提高收斂速度和最優(yōu)解精 度。典型函數(shù)驗證表明，該算法收斂速度

2、快、精度爲；同時，對于多目標優(yōu)化問題.該算法可以提離Pan-bit優(yōu)解集質 量擴大決炭分布范圍，維持決我多樣性，有利于決罠者作出決策。關鍵詞：人工魚群算法；分階段尋優(yōu)和變參數(shù)尋優(yōu)：禁忌搜索：多目標優(yōu)化中圖分類號：TP273J 5文獻標志碼：ANew hybrid intelligoit optim izatbn algorithmand its applicatbn h multi-objective optim izatimZANG II aii-q iing IE Jiaif-gaiig CH EN Jui-sliui(StileKey Labomt>ryr of Industria

3、lCm trolTerhnolcgy Zhejiang Unwtrsity IIangsiiM Zhejiaig 310027 China)Abstract A fter aiiakz iig ie didvantages of lie sl(w er cciiveigtiice proiMTty and er a(x-ura(y h A rtifk'ial F islt- Sw am Algorihn (AFSA a new hybrid nte Urgent oplin izatkn a(goritlni was p»|)osed based on phased op t

4、in izatbn and varial) le paran eteroptm eat bn as well as sone relevait mlrs h talxi search aoriiiin In th k a lg> ritlin. tie optm izatbn process was(I K iinl iito bvo phases mew as b lock die neiiborfiood of the opt in al so b tbn or partul sohtbix die oiierw as to obtain ir qilinal solutim of

5、h glbprecbidi Ea(h phase set (lifffivnt )araneteis and c(m binl lie talxi s<*anh algorillin to in prove cxinvcigence s|)ee<l aixl ac(n racy of opt in al solutbiix The s inu h tioti results slxis that tlx* profMistl algor ilin cin great k in pmve tie ability of seek hg the g blxi 1 ex cel bn t

6、wsu It convergeiuv speed and acai rary. A s f>r the mu h4-ol>jrctke <j|> tin izatidi pn)b Inu tie pn)|M)seil a ritlin can ak) in pn)ve ie <ualit)of Paretoal sohlimn en brge die <1 is trim ti>n ar<!a of(l(x#isi)ns aixl mail tain(I kersity ii(l(!cibi)irtnak iigKey words .Artifi

7、 ud Fisl>-Swarn A ritlin (AFSA); |>l)as(tl (ptin izaticii ami variiblr paran optin izatim Tabu Searth (IS); mu It+obclke optin izatbn1292計算機應用第30卷1292計算機應用第30卷收稿日期：20)9. 11- 19修回日期：1)10- 01- 11 基金項目：國彖門然科學基金資助項U ( 60736021);國家863計劃以U (2D06AA(MZ184 2007AA041406);浙江省科技計劃資助項目(20)6611066 2OO6C3105

8、1);浙江省fl然科學基金資助項冃(Y4080339).作者簡介：帳漢強(1982-)，黑浙江義烏人，碩上研究生，主要研究方向：復雜系統(tǒng)優(yōu)化計算機智能控制;盧建剛(1968-),男浙江杭 州人教授匸要研究方向：復雜匸程系統(tǒng)的建模.控制與優(yōu)化：陳金水(1970-)臥福建福州人制研究員】浚研究方向：嵌入式系統(tǒng)的軟件 模卑柑再弊2()I2 China Academic Journal Electronic Publishing House. AH rights reserved, http:/ 0引言人們根處牛物系統(tǒng)的特征和一些物埋現(xiàn)彖構適設計出 許多仿生優(yōu)化算法來解決復雜的實際問題，例如模擬退火算

9、 法M、粒子非算法宀和遺傳算法E等.雖然這些優(yōu)化算法具 有某些共同的機制和原理但由于不同的優(yōu)化算法表現(xiàn)出不 同的行為特征和優(yōu)缺點叫因而算法間的相互促進與補足逐 漸成為i種改進算法特性的H然途徑。人工魚 群算法(ArtiTbalF ish Schoo I A 如 ritlin. A FSA)是 李曉需等人21于2002年提出的一種壟于模擬饑群覓食、聚胖 和追尾行為的仿生型優(yōu)化算法該算法具仃口好的克服局部 極伉、取得全局極值的能力，并FL該算法還貝有對初伉不敏 感、魯棒性強、簡單(只使用H標函數(shù)值)、易實現(xiàn)等諸多優(yōu) 點。但足隨著優(yōu)化問題的不斷父雜化，AFS在大規(guī)模父雜 優(yōu)化間題的求解和應用中存在著

10、不足，匸要表現(xiàn)為算法得到 的解將度不高，優(yōu)化就期收斂速度快但后期收斂速度慢等。 針對人工魚胖算法的這些不足,本文提出基于分階段3優(yōu)和 變參數(shù)尋優(yōu)的改進策略，并結合禁忌搜索(Talm Search TS) 算法® !>的禁總規(guī)則、解禁規(guī)則和終止規(guī)則提出一種新的 混介智能優(yōu)化算 ii ( H ybril Intelligent Optin izatioi A Igorilin. HDA),將此優(yōu)化算法應用在多目標優(yōu)化問題中，取得了良好 的效果.1多目標優(yōu)化問題描述在多目標優(yōu)化問題中，以個目標通常是相互制約的關系， 對兀中一個目標進行優(yōu)化往往以Jt他II標的性能降低為代 價因而全局敲

11、優(yōu)值通過各日標平衡達到，其數(shù)學表達式如 下：in nF (X ) -(J( X ) f; i = 1,2 mh t S(X) = (a(X) )T 0 j = L 2 , kA <X < B其中:X = x.(i = L 2，n)為“維決策向St; F(X)= (f,(x)T為多口標優(yōu)化函數(shù)向M；s(X)=為約束條件.表示S.(X) > (¥；= L 2，k);邊界條件A<X<B表 示毎個決策分量須滿足© < X. < bj i = L 2，n)c2人工魚群算法概述2 1人工魚個體相關定義人工魚個體的狀態(tài)X = (xlt x2t ,

12、 x ),其中Xj(i= L 2 ，n)為欲尋優(yōu)的變晝；人工魚當前食物濃度表示為Y = f(X);人工血個體之間的距離為心，=II X. - X II;人工血毎 次移動垠大試探次數(shù)為人匸血的感知距離為 9rvisua I人工魚移動的加人步氏為.$坤,擁擠度因了為d2 2行為描述覓食行為 設人工血當前狀態(tài)為X。在其感知距離內隨 機選擇狀態(tài)X戶求極小值問題中(因為極小值與極大值問題 類似，下面均以極小值問題討論丿，當嶺 > 片時,Xw二X, + Rg|QS®(X廠否則.重新隨機選擇狀態(tài)X戶判 斷Y, >片反復嘗試try num her次后,仍不滿足詢進條件，則隨 機移動一步。

13、聚群行為 設人工仇當前狀態(tài)為X,搜索當前鄰域內 (即J, .< visable)的伙伴數(shù)目兮及中心位置X“如果Y丹< 丹；表明伙伴中心冇ft物較少且不太擁擠，則X,2 = X. + RmMQS"“ (Xt. -XJ /IIX. - X,ll;否則執(zhí)行覓食行為。追尾行為 役人工魚當詢狀態(tài)為X,探索當前鄰域內伙 件小£為垠小的伙伴X,如果Ynt < 6人表明£伙伴的狀態(tài) 具有較低的食物濃度并且其周圍不太擁擠,則xl/nal = xl + 丿S(epX - A,/II X廠X；否則執(zhí)行覓食行為。隨機行為 隨機行為是覓食行為的一個缺省行為.公告板用以記求

14、垠優(yōu)人工血個體狀態(tài)及該人工魚位置 的食物濃度。2 3行為選擇根據(jù)所要解決問題的性質.對人丁饑當詢所處的環(huán)境進 行評價，從而選擇一種介適的行為，-般按照進步顯快脈則。2 4參數(shù)對算法的影響tnnunber越小,人工魚擺脫丿部極值的能力越強，收斂 效率高.山硼/越大.越容易發(fā)現(xiàn)全局極值點 、切越大初始收 斂速度快.后期速度降低.而H.將度卞降；&較大時.覓食行為 和隨機行為突出，有利于全烏搜索，提髙收斂速度.同樣粘度 會降低，人工魚數(shù)H A越多，收斂速度快，但足計算量加大。3禁忌搜索算法禁忌搜索算法足-種應用廣泛的解決組介優(yōu)化問題的啟 發(fā)式全局優(yōu)化算法.禁忌搜索算法的上要規(guī)則有:禁忌規(guī)則、

15、 特赦規(guī)則和終止規(guī)則等。所謂禁忌就是重復前面的匸作，提 髙算法的搜索效率.禁忌搜索算法通過引入一個靈活的存儲 結構和相應的禁忌準則來避免辻冋搜索.并通過特赦準則來 赦免一些被禁忌的優(yōu)良狀態(tài)，保證幺樣性的仃效捜索。同時， 為了使算法具冇優(yōu)良的優(yōu)化性能或時間性能，必須設置-個 合理的終止準則來結束整個搜索過程。4新的混合智能優(yōu)化算法4 1人工魚群算法改進策略為了提髙人工魚聊算法搜索速度以及解粘度，本文結介 分階段尋優(yōu)和變參數(shù)尋優(yōu)的思想對人工魚群算法進行改進. 具體改進策略如下.將人匸魚群算法尋優(yōu)分成兩個階段，分別設置不同的參 數(shù)。第一階段為鎖怎最優(yōu)解或局部解鄰域階段.人丁魚群算 法參數(shù)設置規(guī)則如下

16、：川“山、£他、©較大值以及規(guī)模較大 的人工魚群N f但足相對較小try mtn仏q,此時該算法具有良 好的全局探索俾花屈以姐快算法搜霹速度，很佛鎖産最優(yōu)解© 1994-2(112 C hina Academic Journal nrecfromc Pu 或扃部解所在的鄰域。第：階段為得到垃優(yōu)解階段，參數(shù)設置 相對較小的visua /2» slep2和Q,同時較大的trxnitn ber2用此 時的參數(shù)對第一訐段鎖是鄰應內人匸血重新初始化.忌現(xiàn)信 息交換這樣即維持了詢-階段人匸血的何利特性，乂賦其 新的特性。此時人工魚的參數(shù)設迓冇利于算法進行將密3 優(yōu)可

17、以在顯優(yōu)解或局部解鄰域內找到高裕度眾優(yōu)解或局部 解。該策略充分發(fā)揮了人工血胖算法前期收斂速度快以及比 較容易確定最優(yōu)解或局部解所在鄰域的特點同時克服r ft 群算法荷期收斂速度慢、不能紂到粘確值的缺點。仿真研究 也表明這是一種比較好的人工魚群算法改進策略。42新的混合智能優(yōu)化算法人工魚個體在7優(yōu)的過程中，存在著較多的漫無目的的 蘆機行為,而且人工血會反父搜索全局顯優(yōu)解或者局部最優(yōu) 解所在的鄰域，盡管追尾行為能促使陷入局部垠優(yōu)人I W!向 趨于全前極值的更優(yōu)人工魚方向迅隨而逃離罔部極值域.但 是隨著優(yōu)化過程的不斷進行,必然會有其他的人工色繼續(xù)陷 入局部最優(yōu).這樣的反復搜索尋優(yōu)，降低了算法尋優(yōu)的效

18、率。 為了解決這些問題，將TS燈法的相關規(guī)則與人工魚群算法結 介起來，一冃發(fā)現(xiàn)滿足禁忌規(guī)則的鄰域就將此鄰域移入禁忌 表中禁戌使得剩卜的人1M.無法搜索此鄰域迫使共上搜索 沒仃被禁忌的區(qū)域；同時重新初始化一定數(shù)星的人工魚，碓保 沒冇被禁忌的區(qū)域內冇足夠的人T血來保持搜索速度；'”1禁 總表不耳發(fā)生變化或者達到設宦迭代次數(shù)時將剩卜的IX域 移入禁忌農屮禁忌.但足此區(qū)域不得待赦，這樣可以有效解決 搜索效率的問題。定義禁忌算法的相關規(guī)則如下.禁忌規(guī)則 設人工伯當前狀態(tài)為X*搜索當前鄰域內的 伙伴數(shù)目少及中心位置X*如果Y丹 > 函表明伙伴中心有 作物較少但已擁擠.則此鄰域中存在全局最優(yōu)或

19、者局部最優(yōu). 那么就將/所在的鄰域移入禁忌表禁忌。轉故規(guī)則 如果禁忌農中召在滿總解的鄰域.則特赦該 滿意解的所在鄰域.終止規(guī)則如果算法達到設定的最大迭代次數(shù)或者一定 迭代次數(shù)內禁忌表不變，則算法終止。4 3多目標應用中H DA的步驟力多H標優(yōu)化咸用中滿足禁總規(guī)則的鄰域必然存徃非 劣皿優(yōu)解，那么就可以川II DA公獲取pareloJd優(yōu)解集。算 法步驟如下。步驟1初始化H【)A參數(shù)。人工血群算法兩個階段的 參數(shù)組分別為 £|； (visual sftpr uynumber、, 6)/, Ly (visual step? trnnnber7 6J,初始化公告板以及禁忌表.步辣2初j始花人

20、工血群心其參數(shù)為"設置此階段最 大迭代次數(shù)。步陳3運行HK)第一階段算法，搜索非劣最優(yōu)解所在 的鄰域.步辣4按照禁忌規(guī)則，將非劣瑕優(yōu)解所在的鄰域移入 禁忌表中禁忌，并在未禁忌的可行解域內乘新初始化足數(shù) 量的人工魚。步曝5根據(jù)終止規(guī)則，判斷是否可以終止，如果不可 以跳到步驟$否則，執(zhí)行步驟&步驟6將不存在非劣最優(yōu)解的可行解域移入禁總表禁 忌,并不得解禁。步猱7根據(jù)解禁規(guī)則，解禁存在1F劣最優(yōu)解所在的鄰 域并重新設置各個鄰域內人工血參數(shù).其參數(shù)為g步辣8運行II I)A第二階段算法。L.傘楙9猶笛個鄰域內滿足備件旳II：劣最優(yōu)解放入公管 ningl louse. AU right

21、s reserved. nnp:/板。步朦10劌斷公吿板上的非劣眾優(yōu)解數(shù)就是否璉木穩(wěn) 定或者迭代次數(shù)達到設怎值如果沒有跳到步驟&否則執(zhí) 行下一步。步探11輸出公告板上所冇的非劣嚴優(yōu)解，作為“1. 最優(yōu)解集。5仿真計算研究 5 1 H K)A性能驗證木仿貞實驗采川以下的非線性函數(shù):數(shù)呈為甌則分布性能可用垠近解歐氏距離代的標準差s來表示:$ =d -(I, )2,其中 </, = m in (力 fk (AJ - fL(Af) I ；= I 2."丿為決策i到所冇決策的最短距 離L 2 .» M )為決策向就 7為對短距離的期琨，即 d=令工九。從農達式$可以看出

22、Mfi越小人小決策分竹越 均勻.=2丿決策散布范圍評價函數(shù)。用目標空間中2個極值解的歐氏距離來表示敬布范圍：1292計算機應用第30卷max/% y)北 - io 10/y - 10 10/該函數(shù)的極值點位于(0 0丿,極值為L設置AF從參數(shù)如下D =£ ( ”品(A.) - m 陸 S 丿，值越大表示仍的敬布范囤越廣。表I AF從與HDA所彳I!實驗結果比較1292計算機應用第30卷人工魚數(shù)量 N = 5Q visua I = 2 5= 0 7 8 = 0 618 tnnmi her = 2設W H I)A參數(shù)如卜.人工仮數(shù)量他=50禁 zI忌表長度為 20 L< f vif

23、ualx =38 step、= L 5 Uy number、= L 8, = 0 25/< L2: i isual2 = 1. 2 step2 = 02 In mtn ber2 = a 5> = 0 8/oMathl>7環(huán)境下仿真結果如圖1所示。通過仿真結果分析得出.H DA開始時的尋優(yōu)速度明顯算法解的個數(shù)標準差s散布范國78(1 0062L 26II DA86Q 00343 57仿實實驗結果表明.新的混介智能優(yōu)化算法II DA能夠 獲取PaietoAi優(yōu)解集足一種比較好的求解多H標問題的方 法。山實驗數(shù)據(jù)分析得出，號基本人工魚群算法比較.H K)A 不僅得到較多Pan t,

24、®優(yōu)解集解數(shù)就而J1決策的分布更加 均勻、散布范圍更加廣，顯著提高了 Pareto ft優(yōu)解集的質量, 維持了決策的等樣性何利于決策者作出決策。因此.H K)A 在多口標優(yōu)化過程中效果明顯優(yōu)于AF%6結語針對人工魚群算法的不足之處.運用分階段3優(yōu)和變參 數(shù)尋優(yōu)的策略.對人丁血群粥法進行改進并結合禁忌搜索算 法中的禁忌規(guī)則、解禁規(guī)則和終止規(guī)則提出一種新的混合智1292計算機應用第30卷快丁龍本人工魚群算法,后期的7優(yōu)速度也比準本人工魚胖能優(yōu)化算法。該算法充分發(fā)揮了人工魚非算法前期收斂速度1292計算機應用第30卷算法快，并H H DA得到的全局最優(yōu)解梢度較之有了顯*的 提高基本上可以達

25、到理論最優(yōu)值.由此可以看出,HDA的 收斂速度更快、精度更離。5 2 H KH在多目標優(yōu)化中的驗證本仿貞所用實例說數(shù)如下：n ifx(x) = xb g(x) = 1 1 + x? - 10 cos ( 2H.r2 )fi(x) = g(x)(切蟲"Ds t e(x ) = cos( 0)If2(x) - e/ - sin (0)/)(x)-a | sh (bsin(0)(x) - e) + cosfO (x)e J | > 00=0 2H. a - 026= 10 c = 1, J = 6 e = 1oC Xj C L 0 x 2 C 1以下仿貞均Mai hb 7環(huán)境下編程運

26、行。為了衷明 HDA在解決多Fl標優(yōu)化問題時具冇優(yōu)越性，且便于與AFSA 作出對比將HDA參數(shù)設置如下:禁忌表長度為12Q人工魚 群規(guī)模= 12(1算法第-階段/人迭代次數(shù)為50Q算法第 二階段放大迭代次數(shù)為600 L、: f visual =02 siep t = 0 1 trynifn ber = I 6, = 4 5/. L、: (vutial2 = 0 05 $師2 = Q 025 trymun ber = 2 S, = L 98/ aAFSX參數(shù)設置如下：人工魚數(shù)呈N = 120 visual = Q 15 sltp = 0 075 8 = 2 85 trynum her = 2 最大迭代次數(shù)為 I lOOu 在仿貞實例中.將從解的數(shù)星、決策分布均勻性和決策散布范 圍三個方而作出比較?？臁⑷菀状_定最優(yōu)解或局部解所在鄰域的特點.克服了英后期 收斂速度慢、解將度不高的缺點。仿貞研究也表明H I)A比 AFSA收斂速度更快，垃優(yōu)解粘度更髙，總體性能也更加突 出在多n標優(yōu)化過程中.也取得了比較理想的效果。參考文獻：11 | MURRA、A T CHURCH R L Appng