一種解決早熟收斂的自適應(yīng)遺傳算法設(shè)計-圖文

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