一種解決早熟收斂的自適應遺傳算法設計-圖文

技術創(chuàng)新中文核心期刊《微計算機信息》(測控自動化2006年第22卷第12-1期360元/年郵局訂閱號:82-946《現(xiàn)場總線技術應用200例》軟件天地一種解決早熟收斂的自適應遺傳算法設計AnAlgorithmDesignforSolvingPrematureConvergenceofAdaptiveGeneticAlgorithm(解放軍信息工程大學陶林波沈建京韓強TAOLINBOSHENJIANJINGHANQIANG摘要:為了解決簡單遺傳算法(SimpleGeneticAlgorithm,SGA易陷入局部最優(yōu)解的問題,及以往自適應遺傳算法只考慮與進化代數相關的交叉與變異概率,而忽略個體分布情況及種群規(guī)模不可變等問題,本文在保留以往自適應遺傳算法優(yōu)點的同時,設計了與種群中個體分布相關的可變交叉概率與變異概率。同時考慮了種群規(guī)模的波動情況,使算法在相對穩(wěn)定的動態(tài)種群規(guī)模中尋找優(yōu)質解。關鍵字:遺傳算法;早熟收斂;改進的自適應遺傳算法;中間區(qū)域中圖分類號:TP301文獻標識碼:AAbstract:Inthisarticleanalgorithmisdesignedtoimprovethesolutionofprematureconvergence.HerewedesignthecrossoverProbabilityandmutationProbabilitynotonlytakingaccountofEvolutionbutalsothepopulationdistribution.Keywords:geneticalgorithm,prematureconvergence,improvedadaptivegeneticalgorithm,middlearea文章編號:1008-0570(200612-1-0268-031引言遺傳算法GA是模擬自然界生物進化過程與機制求解極值問題的一類自組織、自適應人工智能技術,是借鑒生物自然選擇和遺傳機制而產生的一種全局優(yōu)化自適應概率搜索算法。遺傳算法使用群體搜索技術,它通過對當前群體施加選擇、交叉、變異等一系列遺傳操作,從而產生出新一代的群體,并逐步使群體進化到包含或接近最優(yōu)解的狀態(tài)。遺傳算法呈現(xiàn)的是一個通用的框架,該框架不依賴于問題的種類,遺傳算法對求解問題無可微性及其他要求,所以遺傳算法是一類具有較強魯棒性的優(yōu)化算法,特別是對于一些大型、復雜非線性系統(tǒng),它更表現(xiàn)出了比其他傳統(tǒng)優(yōu)化方法更加獨特和優(yōu)越的性能。由于其具有思想簡單、易于實現(xiàn)、應用效果明顯等優(yōu)點而被眾多應用領域所接受,并在自適應控制、組合優(yōu)化、模式識別、機器學習、人工生命、管理決策等領域得到了廣泛的應用。隱含并行性和全局搜索特性是遺傳算法的兩大顯著特性。但是在簡單遺傳算法搜索過程中,進化初期的超常個體可能限制了其他個體進化,從而造成早熟收斂現(xiàn)象。由于經典的遺傳算法不是一個完全遍歷的Markov過程,它存在收斂速度慢、收斂過程中穩(wěn)定性差、可控制性差和早熟收斂等缺陷,阻礙著遺傳算法走向實用。此外,在簡單遺傳算法中,交叉和變異的概率等參數都人為地預先指定,無論解的好壞,其遺傳操作的概率和值的變化范圍都是一樣的。這樣使得遺傳操作的適應性較差,在解決復雜問題或解空間很大時,會發(fā)生收斂速度慢或局部收斂的情況。為此,人們提出了自適應遺傳算法,主要思想是在進化的過程中根據進化的不同階段建立與進化代數相關的交叉概率和變異概率。這種做法在一定程度上改善了算法的搜索能力和收斂速度,但很多具體的問題還沒有考慮,對問題的解決過于固定破壞群體中優(yōu)質解,算法不易收斂到最優(yōu)解.因此對于群體中不同的個體其交叉和變異概率應該不同。-郵局訂閱號:82-946360元/年技術創(chuàng)新軟件天地《PLC技術應用200例》您的論文得到兩院院士關注適應度高的個體的交叉和變異概率應該較小,適應度低的個體的交叉和變異概率應該較大.從另一個角度來講,個體適應度f與最大適應度fmax的差越小,即該個體是最優(yōu)解,對它的變異概率應該取得小才能保護優(yōu)質解.為了在算法穩(wěn)定性的基礎上解決其收斂速度和全局收斂性之間的矛盾,提出了一種新的改進遺傳算法。該改進算法設計了與進化代數相關的交叉概率,與個體適應度相關的變異概率。變異概率可以設定為同理對于交叉概率的設置為k1≤1其中f′是兩個交叉?zhèn)€體中適應度較大的個體的適應度.為防止交叉和變異概率大于1,將交叉和變異概率修改為:其中k1,k2≤1.2.2算法的改進上面我們對簡單遺傳算法及自適應遺傳算法作了簡單的介紹并指出了他們的不足。而這里我們要提到的算法主要是在針對原來自適應遺傳算法的不足,作為本文的一個創(chuàng)新點,我們除了考慮采用動態(tài)的交叉與變異概率外,我們還考慮了每代個體的分布情況,通常的做法是保留優(yōu)秀的個體到下一代,我們也繼承這個原則,同時我們也要考慮父代的去留問題。原因在于人們過多的考慮優(yōu)點比較突出的個體,其實有些個體即使他的適應度接近平均適應度,但它仍有保留的價值,至少有交配到下一代的機會,舉個簡單的例子,很多能考上北大,清華,最后成就一番事業(yè)的人很多父母也只是很一般的人,他們的父母并不是沒有優(yōu)秀的基因,至少有些基因的組合是優(yōu)秀的。所以,我們的任務是如何保留這些模式,并發(fā)現(xiàn)她們優(yōu)秀的組合。同時我們還要考慮這樣一個問題,就是在適應度平均值附近個體的分布情況。如果大部分個體都分布在一個狹長的區(qū)域內,說明這是一個穩(wěn)定的群體,這時我們就要先確定一個大部分個體分布的范圍,我們把它確定為中間區(qū)域。如果要想在這個群體中找到優(yōu)質解是件很困難的事,但如果從中抽取的父代產生的子代適應度已高出中間區(qū)域而接近上界,則說明該父代含有優(yōu)秀的模式,可以將此父代保留到下一代中繼續(xù)進行交配,如果沒有產生明顯的優(yōu)秀子代,則說明他們的子代不會很突出,從而淘汰這樣的父代及他們產生的子代。如果中間個體很少或分布很稀疏,說明他們不是一個穩(wěn)定的集中的群體,他們被考慮的概率要減小,同樣他們被交叉和變異的概率也要減小。相反,如果中間區(qū)域的個體很多或分布比較集中,則說明該群體比較穩(wěn)定,則他們被考慮的概率也要相應增大,即增大該區(qū)域值的選擇概率。同時,我們要從他們中的到突出的解,就必須破壞他們的這種穩(wěn)定性,從而得到優(yōu)質解,就必須采用比較大的交叉概率和變異概率。這里我們首先定義群體的直徑H=fmax-fmin接著我們要定義個體到平均值點的距離。h=|f=f|接下來我們要考慮的是這些點在群體中的分布情況,我們中點要考慮的是這些點在中間區(qū)域的分布情況,那么什么樣的區(qū)域確定中間區(qū)域呢,我們定義一個鄰域半徑δ,這里我們取,而中間鄰域被定義為U(f,δ我們可以通過計算與的關系來確定該點是否在中間區(qū)域,然后我們確定中間區(qū)域點的數量,然后我們定義中間區(qū)域在群體中的密度。我們可以通過得出群體中個體點在群體中的中間區(qū)域的分布情況,因此我們將上面交叉概率和變異概率修改為變異概率可以設定為,,同理對于交叉概率的設置為,k1≤1,k1≤1其中f′是兩個交叉?zhèn)€體中適應度較大的個體的適應度.為防止交叉和變異概率大于1,將交叉和變異概率修改為:其中k1,k2≤1.算法的圖示說明3結論與展望遺傳算法作為一種優(yōu)化算法有著廣泛應用前景,但同時也存在著很多有待解決的問題。每一種新想法的提出都意味著一種進步,至少是一種嘗試。本文在269--技術創(chuàng)新中文核心期刊《微計算機信息》(測控自動化2006年第22卷第12-1期360元/年郵局訂閱號:82-946《現(xiàn)場總線技術應用200例》軟件天地保留以往自適應遺傳算法采取的保留最優(yōu)個體策略的同時,還考慮了個體的分布情況及非突出父代個體的去留情況。本文作為算法的改進設計,他的優(yōu)劣性還需要在實踐中進一步的驗證。本文作者創(chuàng)新點:在保留以往自適應遺傳算法采取的保留的最有個體策略的基礎上。本文充分考慮了每代個體的分布情況及優(yōu)秀個體的父代保留情況。并定義了相關定義及設計了相應的算法。參考文獻:[1]HerreraF.LozanoM.Adaptationofgeneticalgorithmparametersbasedonfuzzylogiccontrollers.In:HerreraF,verdegayJL,eds.GeneticAlgorithmsandSoftComputing.Physica-Verlag(StudiesinFuzzinessandSoftComputing,Vol.8,1996.95-125.[2]AnfelinePJ.Adaptiveandself-adaptiveevolutionarycomputa-tions.In:PalaniswamiM.AttikiouzelY,MarksR,FogelDB,FukudaTeds.ComputationalIntelligence:ADynamicsystemsPerspetive.IEEEPress,1995.152-163.[3]RadfordM.Neal,ProbabilisticInferenceUsingMarkovChainMonteCarloMethods,TechnicalReportCRG-TR-93-11993.36-46[4]周明,孫樹東.遺傳算法原理及應用[M].北京:國防工業(yè)出版社,2002[5]王小平,曹立明.遺傳算法理論、應用與軟件實現(xiàn)[M].西安:西安交通大學,2002[6]金朝紅,吳漢松,李臘梅,王樹人.一種基于自適應遺傳算法的神經網絡學習算法[J].微計算機信息,2005,18,54-56作者簡介:陶林波(1979-,男,遼寧沈陽人,信息工程大學理學院電子信息工程系在讀碩士研究生,主要從事計算智能及語義分析方面的研究E-mail:taotlb@126.com;沈建京(1961-,男,信息工程大學理學院電子信息工程系主任,博士生導師,主要從事人工智能方面的研究;韓強(1980-,男,河南信陽人,信息工程大學理學院電子信息工程系在讀碩士研究生,主要從事分布構件技術。Biography:TaoLinbo,male,bornin1979,Liaoning,Majoredincomputingintelligenceandsemanticanalysis;Shen,Jianjing,male,bornin1961,majoredinartificialintelligence;Han,qiang,male,bornin1980,Henan,master,majoredindistributedcomponentstechnology.(450001河南鄭州市信息工程大學理學院電子信息工程系陶林波沈建京韓強(ElectricInformationEngineeringDepartment,ScienceInsti-tute,InformationEngineeringUniversityTaoLinboShenJian,JingHanQiang通訊地址:(450001河南省鄭州市2201信箱160號數理系研究生隊陶林波(上接第221頁5、應力:顱腦左半球的應力值總體呈現(xiàn)先增大后減小,最顱腦右半球與左半腦基本一致,說明在碰撞中左右腦受力基本一致;顱腦腦干的應力值總體呈現(xiàn)先減少后增大,最后趨于平穩(wěn),對應變化時間和左右半腦一致,應力值變化相反。參考文獻:elingofdirectheadimpact[J].Proc.37thStappCarCrashConf.,SAEPaperNo.933114,1993.[2]楊濟匡,許偉,萬鑫銘.研究汽車碰撞中頭頸部動態(tài)響應的有限元模型的建立和驗證[J].湖南大學學報(自然科學版2005,32(2.[3]馬春生,張海鐘,杜匯良,黃世霖,張金換.具有解剖基下頜的人體頭部有限元模型的建立[J].生物醫(yī)學工程雜志,2005:22(1:53~56.[4]李蘇皖,卜海富,何仿,錢齊榮.CT掃描資料間接法建立股骨上段三維有限元模型[J].臨床骨科雜志,2002:12(1.[5]張彤,劉洪臣,王延榮,蔣建華.上頜骨復合體三維有限元模型的建立[J].中華口腔醫(yī)學雜志,2000,35(5.[6]陳學鵬,張加理,鄭幼洋,顧錫榮.下頜第一恒磨牙I類洞型三維有限元模型的建立[J].口腔醫(yī)學,2005,25(1.[7]劉作廣,趙洪倫,周慧峰。生物組織有限元建模與分析[J]。同濟大學學報。2002.3;30(3[8]張建國,蘆俊鵬,阮世捷,何培,李海巖。以頭部為例的人體國創(chuàng)傷雜志[J].,2004:20(6.作者簡介:張建國(1955~,男,天津人,天津市機械設計授銜專家,天津科技大學教授,博士生導