一種提高遺傳算法全局收斂性的方法-

1、收稿日期:2002-11-22基金項(xiàng)目:教育部高等學(xué)校骨干教師資助計(jì)劃;遼寧省自然科學(xué)基金資助項(xiàng)目(002013作者簡(jiǎn)介:何大闊(1975-,男,遼寧沈陽人,東北大學(xué)博士后研究人員;王福利(1957-,男,遼寧遼陽人,東北大學(xué)教授,博士生導(dǎo)師第24卷第6期2003年6月東北大學(xué)學(xué)報(bào)(自然科學(xué)版Journal of Northeastern U niversity(Natural ScienceVol 24,No.6Jun.2003文章編號(hào):1005-3026(200306-0511-04一種提高遺傳算法全局收斂性的方法何大闊,王福利(東北大學(xué)信息科學(xué)與工程學(xué)院,遼寧沈陽 110004摘 要:通

2、過對(duì)遺傳算法過早收斂原因的分析,認(rèn)為遺傳算法出現(xiàn)過早收斂主要與問題解的分布狀況、種群個(gè)體的分布情況及遺傳算子的應(yīng)用有關(guān),提高算法全局收斂性能的核心就是如何使算法科學(xué)地處理種群多樣性及識(shí)別個(gè)體對(duì)全局收斂性能的作用 提出幾類與遺傳算法全局收斂性能關(guān)系較大的個(gè)體,并結(jié)合小生境進(jìn)化共享函數(shù)思想,形成一種旨在提高遺傳算法全局收斂性、求解全局最優(yōu)解的遺傳算法,仿真結(jié)果驗(yàn)證了這種算法良好的全局收斂性能 關(guān) 鍵 詞:遺傳算法;收斂性;多樣性;遺傳算子;全局最優(yōu);共享函數(shù)中圖分類號(hào):T P 13 文獻(xiàn)標(biāo)識(shí)碼:A遺傳算法以其魯棒性、并行性及高效性等優(yōu)點(diǎn)得到了廣泛的應(yīng)用13但作為一種優(yōu)化算法,遺傳算法也存在一些不足

3、46,收斂于局部極值即過早收斂就是遺傳算法存在的一個(gè)有待解決的問題 開發(fā)一種提高遺傳算法全局收斂性能的全局收斂算法具有重要的理論與現(xiàn)實(shí)意義 本文基于對(duì)算法全局收斂性能影響較大的幾類個(gè)體結(jié)合小生境進(jìn)化思想提出一種提高遺傳算法收斂性能的有效算法1 遺傳算法過早收斂的原因遺傳算法出現(xiàn)過早收斂的原因很多,首先它與問題解的分布有關(guān) 一般說來,尋優(yōu)算法都是向解的改善方向進(jìn)行搜索,而這一搜索方向是否為全局收斂的方向即達(dá)到最優(yōu)解的方向卻無法確定 于是,當(dāng)問題解的分布較為復(fù)雜、特異時(shí),就極易使優(yōu)化算法陷入局部極值 所以,對(duì)于不同的問題,應(yīng)對(duì)優(yōu)化算法進(jìn)行相應(yīng)的調(diào)整以適應(yīng)這類問題的求解,降低局部收斂的可能性 通常,

4、解的分布狀況出現(xiàn)下列情況就極易使算法產(chǎn)生早斂:在最優(yōu)解附近區(qū)域解的分布較為陡峭,個(gè)體的適應(yīng)值跨度較大,靠近最優(yōu)解的個(gè)體的適應(yīng)值可能很差,這樣即使種群中出現(xiàn)了最優(yōu)區(qū)域中的個(gè)體,這些個(gè)體也可能會(huì)因適應(yīng)值較差而遭淘汰使算法失去進(jìn)一步在該區(qū)域搜索的機(jī)會(huì),從而錯(cuò)過最優(yōu)解;解為多峰分布且最優(yōu)峰與次優(yōu)峰距離較近,同時(shí)最優(yōu)解與次優(yōu)解相差不大,這時(shí)極易使算法由于對(duì)最優(yōu)峰沒能搜索到底而陷入次優(yōu)解不能自拔;解為多峰分布且峰與峰之間距離較遠(yuǎn),這時(shí)算法不能確保各算子能將搜索空間擴(kuò)展達(dá)最優(yōu)區(qū)域,也無法保證這一區(qū)域個(gè)體的生存機(jī)會(huì),于是也就無法保證算法搜索到最優(yōu)解 遺傳算法其自身的不完善及缺陷也是造成早斂現(xiàn)象的原因 目前,G

5、A 的全局收斂理論大都是基于初始種群及進(jìn)化代數(shù)無限大為前提,而這實(shí)際上是不可能的,實(shí)際指導(dǎo)意義不大 另外,即使能夠證明算法可以在有限代內(nèi)全局收斂概率為1,但有限的定義是多大卻無法知道,這事實(shí)上也無實(shí)用的價(jià)值 到目前為止,只能對(duì)GA 的全局收斂性能進(jìn)行改進(jìn)或改善,而無法確保其全局收斂另外,遺傳算法初始種群的產(chǎn)生方法與初始種群的規(guī)模對(duì)初始種群的個(gè)體分布狀況有著相當(dāng)?shù)挠绊?而初始種群的個(gè)體分布狀況又直接影響算法的全局收斂性能 由于傳統(tǒng)GA 的初始種群是隨機(jī)選取的,初始種群的覆蓋空間具有很大的不確定性,如果初始種群空間不包含全局最優(yōu)解,而遺傳算子又不能在有限的進(jìn)化代數(shù)內(nèi)將覆蓋空間擴(kuò)延到全局最優(yōu)解所在的

6、區(qū)域,那么過早收斂就不可避免 所以,確保初始種群的多樣性與個(gè)體分布的相對(duì)合理性就是改善GA 全局收斂性首先要解決的問題 由初始種群開始進(jìn)行尋優(yōu)搜索,在進(jìn)化的過程中種群的個(gè)體分布變化的狀況也決定了算法的全局收斂性能 初始種群中沒有的最優(yōu)解的信息可以通過群體的進(jìn)化來得到,從而達(dá)到最優(yōu)解 但如果種群在有限的代數(shù)內(nèi)不能將種群引導(dǎo)到最優(yōu)解所在區(qū)域(即種群個(gè)體的分布無法覆蓋最優(yōu)解區(qū)域并有機(jī)會(huì)搜索該區(qū)域,就會(huì)造成算法早斂 GA尋優(yōu)過程中種群分布的變化幾乎與GA所有的組成部分有關(guān) 各算子的計(jì)算形式、操作方式及操作概率,算法整體的尋優(yōu)結(jié)構(gòu)等都決定了種群中個(gè)體分布的變化 其中,人們已廣泛認(rèn)識(shí)的由于超級(jí)個(gè)體的出現(xiàn)而

7、導(dǎo)致的局部極值問題就是與算法的選擇、交叉、變異都有關(guān)的 實(shí)際上,無論是初始種群的分布狀況、還是進(jìn)化中種群分布的變化狀況,其核心都是希望種群無論是初始還是進(jìn)化過程中都盡可能保持多樣性并在盡可能少的代數(shù)內(nèi)將尋優(yōu)搜索引導(dǎo)到最優(yōu)解區(qū)域7 目前,人們大多是通過對(duì)選擇與變異的改進(jìn)以保持種群在進(jìn)化的過程中始終保持多樣性,從而在一定程度上克服過早收斂 但由于算子本身的隨機(jī)性,僅靠算子是不能確保算法搜索到最優(yōu)解區(qū)域的 比如,變異算子使算法具有爬山能力從而改善算法的全局收斂性能,但其隨機(jī)性無法確保尋優(yōu)過程在有限且盡可能少的進(jìn)化代數(shù)內(nèi)搜索到全局最優(yōu)解所在區(qū)域 同時(shí),保持多樣性的確可以對(duì)算法的全局收斂性能進(jìn)行改善,但

8、這樣做究竟對(duì)全局收斂性有多大貢獻(xiàn)無從考量,片面地強(qiáng)調(diào)多樣性有時(shí)不僅不能防止早斂的發(fā)生,還會(huì)對(duì)算法的穩(wěn)定性、種群的整體收斂性造成很大影響 種群多樣性的保持策略必須具有一定的指導(dǎo)性,使算法在尋優(yōu)過程中的多樣性是一種以一定的原則將群體引導(dǎo)到有利于全局收斂的多樣性 另外,本文認(rèn)為單純保持多樣性是不夠的,因?yàn)樵趯?yōu)過程中群體中不乏最優(yōu)解區(qū)域中的個(gè)體出現(xiàn),不過這些個(gè)體往往由于適應(yīng)值較低而很快被淘汰,問題是如何保護(hù)好這些個(gè)體使算法有機(jī)會(huì)搜索該區(qū)域 所以,如何評(píng)價(jià)個(gè)體尤其是那些適應(yīng)值不大甚至較差的個(gè)體的尋優(yōu)作用并加以保護(hù),對(duì)于改善GA的全局收斂性能也是很重要的 遺傳模擬退火法中的概率接受劣解就是在種群多樣的同

9、時(shí)增加較差解的生存機(jī)會(huì),進(jìn)而達(dá)到全局收斂的目的2 算法的提出與實(shí)現(xiàn)應(yīng)該說要克服過早收斂必須處理好兩大問題:第一,如何保持種群多樣性;第二,如何鑒別個(gè)體對(duì)全局收斂性能的作用并加以保護(hù)與引導(dǎo) 保持種群多樣性的方法很多,如初始種群平均分布與其補(bǔ)碼個(gè)體相結(jié)合、引入個(gè)體間距離的概念以避免近親繁殖等,在此不進(jìn)行詳述 這里主要討論一下如何鑒別個(gè)體對(duì)全局收斂性能的作用并加以保護(hù)與引導(dǎo)的問題 由于傳統(tǒng)GA是采用定向選優(yōu)模式,不接受差解 所以,要對(duì)某些個(gè)體實(shí)施保護(hù)就要對(duì)傳統(tǒng)GA選擇的指導(dǎo)思想及操作策略進(jìn)行改進(jìn) 但完全依靠隨機(jī)性的概率接受劣解是無法保證GA的全局收斂性的 算法本身必須指導(dǎo)算子哪些個(gè)體是應(yīng)該保護(hù)的,而

10、哪些個(gè)體應(yīng)該淘汰,也就是如何評(píng)價(jià)個(gè)體對(duì)全局收斂性能的作用以決定是否接受該個(gè)體 事實(shí)上,給出準(zhǔn)確的定義是很困難的,只能在算法尋優(yōu)過程中,定義哪些個(gè)體應(yīng)提起一定的注意力或重視程度 也就是哪些個(gè)體可能對(duì)全局收斂是有益的甚至是重要的,然后對(duì)這類個(gè)體加以保護(hù)避免其很快遭到淘汰而造成早斂,提高全局收斂的可能性本文認(rèn)為值得注意的個(gè)體有以下幾類:第一類為適應(yīng)值較好但距離當(dāng)前最好解較遠(yuǎn)的個(gè)體,因?yàn)檫@類個(gè)體可能暗示種群搜索到了遠(yuǎn)離群體集中區(qū)域的峰值區(qū)域;第二類為距離當(dāng)前最好解較近個(gè)體而適應(yīng)值較差的個(gè)體,這類個(gè)體可能意味著最好解較近可能還有峰值的存在應(yīng)給適當(dāng)?shù)淖⒁?第三類為經(jīng)算子的尋優(yōu)計(jì)算產(chǎn)生的子代適應(yīng)值較父代個(gè)體

11、適應(yīng)值有很大改進(jìn)的父代個(gè)體,尤其是適應(yīng)值較差的這類個(gè)體,因?yàn)闊o論這類個(gè)體自身的適應(yīng)度如何,其被改進(jìn)的速度很快可能是因?yàn)樵搨€(gè)體所在的區(qū)域解的分布較為陡峭,這類區(qū)域正是早斂易發(fā)的區(qū)域,重視這類個(gè)體首先可以使算法有機(jī)會(huì)在第一時(shí)間搜索可能快速搜索的區(qū)域(即陡峭區(qū)域,同時(shí),對(duì)這類個(gè)體進(jìn)行一定的保護(hù)使其在群體中有機(jī)會(huì)延長(zhǎng)生存的時(shí)間給算法更多的機(jī)會(huì)仔細(xì)搜索該區(qū)域,因此,保護(hù)這類個(gè)體有利于達(dá)到全局最優(yōu)解同時(shí)有利于局部區(qū)域的搜索 這類個(gè)體也是提高全局收斂性的重要環(huán)節(jié) 本文采用算子并行計(jì)算結(jié)構(gòu),即各算子分別對(duì)父代進(jìn)行操作,然后將產(chǎn)生的新個(gè)體以一定比例直接進(jìn)入子代,通過各算子產(chǎn)生的新個(gè)體進(jìn)入子代的比例來調(diào)節(jié)各算子對(duì)

12、GA性能的影響8 在最優(yōu)保持計(jì)算時(shí),應(yīng)用小生境進(jìn)化中共享函數(shù)思想(這里定義海明距離為共享函數(shù),算法優(yōu)先選擇適應(yīng)值超過種群平均值且與當(dāng)前最好值的海明距離高于種群平均值的個(gè)體;對(duì)于與當(dāng)前最好值的海明距離低于種群平均值的個(gè)體,采取拋棄處理不讓其進(jìn)入子代;采用J=f old-f newf ol d作為個(gè)體的自我改進(jìn)系數(shù),其中,f old為變異的父代個(gè)體適應(yīng)值;f ne w為子代個(gè)體適應(yīng)值 子代個(gè)體優(yōu)于父代個(gè)體即f new f o l d,對(duì)于J值達(dá)到一定閾值的512東北大學(xué)學(xué)報(bào)(自然科學(xué)版 第24卷個(gè)體進(jìn)行最優(yōu)保護(hù)9 混合改進(jìn)遺傳算法的計(jì)算過程如下:(1確定尋優(yōu)參數(shù)、產(chǎn)生初始種群;(2對(duì)群體實(shí)施遺傳操

13、作,產(chǎn)生遺傳子代新群體:計(jì)算群體中個(gè)體的適應(yīng)值,將適應(yīng)值超過種群平均值且與當(dāng)前最好值的海明距離高于種群平均值的個(gè)體作為最優(yōu)保持子代個(gè)體;采用線性均勻交叉算子進(jìn)行交叉計(jì)算,產(chǎn)生交叉子代個(gè)體;采用變步長(zhǎng)Gaussian 變異算子進(jìn)行變異計(jì)算,某代變異步長(zhǎng)為:當(dāng)k 4時(shí), (k = 1-f *(k -1-f *(k -3f *(k -1,為常數(shù);當(dāng)k 4時(shí), 取為常數(shù)(其中f *(k 為第k 代時(shí)的最好值計(jì)算群體個(gè)體與當(dāng)前最好解的海明距離并由遠(yuǎn)到近進(jìn)行排序,將海明距離序號(hào)和適應(yīng)值序號(hào)之和最大的n 1個(gè)個(gè)體作為第一類啟發(fā)個(gè)體;將海明距離序號(hào)和適應(yīng)值序號(hào)之和最小的n 2個(gè)個(gè)體作為第二類啟發(fā)個(gè)體;群體中參

14、與變異操作的父代個(gè)體J 值最高的n 3個(gè)個(gè)體作為第三類啟發(fā)個(gè)體;(3檢驗(yàn)收斂條件,若滿足收斂條件則結(jié)束遺傳進(jìn)化過程并輸出結(jié)果;否則,返回(23 仿真研究本文采用文獻(xiàn)10中提供的測(cè)試函數(shù)進(jìn)行仿真研究,并與文獻(xiàn)10的仿真結(jié)果進(jìn)行比較,來驗(yàn)證本文提出的遺傳算法的尋優(yōu)性能 初始種群為50;最優(yōu)保持、交叉、變異及第一、二、三類啟發(fā)個(gè)體的數(shù)量分別為10,15,18,2,2,3 max F 1=0 002+25j =11j +2i=1(x i -a i j 2,-65 536 x i 65 536函數(shù)F 1具有多個(gè)局部極大點(diǎn),一般其函數(shù)值大于1即可認(rèn)為收斂,其中:a 1j =-32,-16,0,16,32,

15、-32,-16,0,16,32,-32,-16,0,16,32,-32,-16,0,16,32,-32,-16,0,16,32;a 2j =-32,-32,-32,-32,-32,-16,-16,-16,-16,-16,0,0,0,0,0,16,16,16,16,16,32,32,32,32,32對(duì)測(cè)試函數(shù)采用本文提出的遺傳算法計(jì)算100次,考察求得全局最優(yōu)解的概率、收斂的平均代數(shù)、所得解與全局最優(yōu)解的平均誤差 同時(shí),將結(jié)果與文獻(xiàn)10中提供的仿真結(jié)果進(jìn)行比較,結(jié)果見表1表1 3種方法仿真結(jié)果比較表Table 1 Com paring of sim ul ati on results bythr

16、ee algorithm s 算法收斂概率/%平均收斂代數(shù)平均誤差/10-4SA GA 32177 1.47GAA 72105 1.45本文98940.57如仿真結(jié)果所示,本文算法在對(duì)存在眾多局部最優(yōu)值的復(fù)雜函數(shù)進(jìn)行尋優(yōu)時(shí),能夠以較高的概率較好地收斂于全局最優(yōu)解,并且求解較為精確4 結(jié) 語在分析遺傳算法收斂性能的基礎(chǔ)上,定義幾類與收斂性能密切相關(guān)的個(gè)體,并在算法中對(duì)這類個(gè)體進(jìn)行處理,使算法的種群分布更為合理,進(jìn)而提高算法全局收斂性能 本文提出的改進(jìn)遺傳算法具有良好的全局收斂性能,并且在精確性及收斂速度方面都有了一定提高 參考文獻(xiàn):1Ozdamar L.A genetic algori thm

17、approach to a general category project scheduling problem J.IEEE Tr ans Syst M an Cyber ,1999,29(1:44-59.2Juidette H,Youlal H.Fuzzy dynamic path planning using genetic algorithms J.Electronics L etters ,2000,36(4:374-376.3S hitomatu.Fuzzy satisficing method for electri c pow er plant coal put chase

18、using genetic algorithms J .Eur opean Jour nal of Operational R esearch ,2000,126(1:218-230.4Li M aojun,Fan Shaosheng,Tong T iaosheng.T he application of partheno -genetic algori thm in pattern clus tering problem J .Engine er ing Ap plications of Artif icial Intelligence ,1999,12(2:175-184.5Correa

19、R C,Ferrei ra A,Rebreyend P.Schedul ing mul tiprocess or tas ks w i th genetic algorithmsJ.IEEE Trans on Parallel and Distributed Systems ,1999,10(8:825-837.6Fumiaki T ,Toshi n i ro N,Sigeruo.Banknote recogniti on by m eans of optimized masks,neural netw ork,and gen etic algorithms J .Engineering Ap

20、p lications of Ar tif icial Intelligence ,1999,12(2:175-184.7何大闊,李延強(qiáng),王福利 并行啟發(fā)式進(jìn)化遺傳算法J 信息與控制,2001,30(7:681-683(He D K,Li Y Q,Wang F L.Paralleled heuristic gen etic algorithmJ.I nf ormation and Con trol ,2001,30(7:681-683.8何大闊,李延強(qiáng),王福利 基于單純形算子的混合遺傳算法J 信息與控制,2001,30(3:276-278(He D K,Li Y Q,Wang F L.Hybr

21、id genetic algori thm based on the operator of pattern search J .Inf or mation and513第6期 何大闊等:一種提高遺傳算法全局收斂性的方法Control,2001,30(3:276-278.9何大闊,王福利 基于可進(jìn)化性的快速遺傳算法J 東北大學(xué)學(xué)報(bào)(自然科學(xué)版,2002,23(7:628-631(He D K,Wang F L.Fast genetic algorithm based onevolvabi li tyJ.Jour nal of Nor theastern Univer sity(Natur al

22、 Science,2002,23(7:628-631.10李紹軍,王惠,姚平經(jīng) 求解全局最優(yōu)化的遺傳(GAAlopex算法的研究J 信息與控制,2000,29(4:304-308(Li S J,W ang H,Yao P J.Study of genetic-algorithms forseeking the global optimizationJ.I nf or mation andControl,2000,29(4:304-308.Improving the Global Convergence of the Genetic AlgorithmH E D a-kuo,WA N G Fu-

23、li(School of Infor matio n Science&Eng ineering,Nor theastern U niv ersity,Shenyang110004,China.Cor respondent:HE Da-kuo,E-mail:hedakuoAbstract:Based o n the analysis of the r eason of the early converg ence o f the genetic algor ithm,it w as shown t hat t he early conver gence of the genetic algor

24、ithm is mainly concerned w ith the distribution of t he solutions to the problem,the distr ibution of t he indiv iduals of t he population and the application of the genetic operators.T he key to impro ve the per for mance of the global conver gence of the genetic algorithms was believed to apply th

25、e algo rithms to deal wit h the diversity of population scientifically and recognize the contribution of t he individuals to the global conv er gence.Sever al kinds of the indiv iduals,which have much to do w ith t he per for mance of the global converg ence,have been proposed and combined with the niche evolutio n shar ing function.A genetic alg orithm is sug ge