遺傳算法綜述

《遺傳算法綜述》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。

1、.........................遺傳算法綜述史俊杰摘要：遺傳算法來源于進(jìn)化論和群體遺傳學(xué)，是計(jì)算智能的重要組成部分，正受到眾多學(xué)科的高度重視。本文主要回顧了遺傳算法的起源和發(fā)展歷程，并對遺傳算法的基本原理及特點(diǎn)作了簡要闡述。進(jìn)一步指出了遺傳算法存在的問題及相應(yīng)的改進(jìn)措施，討論了遺傳算法在實(shí)際中的應(yīng)用，并對遺傳算法的未來的發(fā)展進(jìn)行了探討。關(guān)鍵字：遺傳算法，適應(yīng)度函數(shù)，神經(jīng)網(wǎng)絡(luò)1.遺傳算法的起源遺傳算法(GeneticAlgorithm，GA)是模擬自然界生物進(jìn)化機(jī)制的一種算法，即遵循適者生存、優(yōu)勝劣汰的法則，也就是尋優(yōu)過程中有用的保留，無用的則去除。在科學(xué)和生產(chǎn)實(shí)踐中表現(xiàn)

2、為，在所有可能的解決方法中找出最符合該問題所要求的條件的解決方法，即找出一個最優(yōu)解。這種算法是1960年由Holland提出來的，其最初的目的是研究自然系統(tǒng)的自適應(yīng)行為，并設(shè)計(jì)具有自適應(yīng)功能的軟件系統(tǒng)。2.遺傳算法的發(fā)展過程從二十世紀(jì)六十年代開始，密切根大學(xué)教授Holland開始研究自然和人工系統(tǒng)的自適應(yīng)行為，在這些研究中，他試圖發(fā)展一種用于創(chuàng)造通用程序和機(jī)器的理論。在六十年代中期至七十年代末期，Bagly發(fā)明“遺傳算法”一詞并發(fā)表了第一篇有關(guān)遺傳算法應(yīng)用的論文。1975年豎立了遺傳算法發(fā)展史上的兩塊里程碑，一是Holland出版了經(jīng)典著作“AdaptationinNatureandAr

3、tifieialSystem”，二是Dejong完成了具有指導(dǎo)意義的博士論文“AnAnalysisoftheBehaviorofaClassofGenetieAdaptiveSystem”。進(jìn)入八十年代，隨著以符號系統(tǒng)模仿人類智能的傳統(tǒng)人工智能暫時陷入困境，神經(jīng)網(wǎng)絡(luò)、機(jī)器學(xué)習(xí)和遺傳算法等從生物系統(tǒng)底層模擬智能的研究重新復(fù)活并獲得繁榮。進(jìn)入九十年代，以不確定性、非線性、時間不可逆為內(nèi)涵，以復(fù)雜問題為對象的科學(xué)新范式得到學(xué)術(shù)界普遍認(rèn)同，如廣義進(jìn)化綜合理論。由于遺傳算法能有效地求解屬于、NPC類型的組合優(yōu)化問題及非線性多模型、多目標(biāo)的函數(shù)優(yōu)化問題，從而得到了多學(xué)科的廣泛重視。3.遺傳算法特點(diǎn)遺

4、傳算法作為具有系統(tǒng)優(yōu)化、適應(yīng)和學(xué)習(xí)的高性能計(jì)算和建模方法的研究漸趨成熟。遺傳算法具有進(jìn)化計(jì)算的所有特征，同時又具有自身的特點(diǎn)：專業(yè)資料分享.........................（1）搜索過程既不受優(yōu)化函數(shù)的連續(xù)性約束，也沒有優(yōu)化函數(shù)導(dǎo)數(shù)必須存在的要求。（2）遺傳算法采用多點(diǎn)搜索或者說是群體搜索，具有很高的隱含并行性，因而可以提高計(jì)算速度。（3）遺傳算法是一種自適應(yīng)搜索技術(shù)，其選擇、交叉、變異等運(yùn)算都是以一種概率方式來進(jìn)行，從而增加了搜索過程的靈活性，具有較好的全局優(yōu)化求解能力。（4）遺傳算法直接以目標(biāo)函數(shù)值為搜索信息，對函數(shù)的性態(tài)無要求，具有較好的普適性和易擴(kuò)充性。（5）遺傳

5、算法更適合大規(guī)模復(fù)雜問題的優(yōu)化。4.遺傳算法研究理論在自然界，由于組成生物群體中各個體之間的差異，對所處環(huán)境有不同的適應(yīng)和生存能力，遵照自然界生物進(jìn)化的基本原則，適者生存、優(yōu)勝劣汰，將要淘汰那些最差個體，通過交配將父本優(yōu)秀的染色體和基因遺傳給子代，通過染色體核基因的重新組合產(chǎn)生生命力更強(qiáng)的新的個體與由它們組成的新群體。在特定的條件下，基因會發(fā)生突變，產(chǎn)生新基因和生命力更強(qiáng)的新個體；但突變是非遺傳的，隨著個體不斷更新，群體不斷朝著最優(yōu)方向進(jìn)化，遺傳算法是真實(shí)模擬自然界生物進(jìn)化機(jī)制進(jìn)行尋優(yōu)的。在此算法中，被研究的體系的響應(yīng)曲面看作為一個群體，相應(yīng)曲面上的每一個點(diǎn)作為群體中的一個個體，個體用多

6、維向量或矩陣來描述，組成矩陣和向量的參數(shù)相應(yīng)于生物種組成染色體的基因，染色體用固定長度的二進(jìn)制串表述，通過交換、突變等遺傳操作，在參數(shù)的一定范圍內(nèi)進(jìn)行隨機(jī)搜索，不斷改善數(shù)據(jù)結(jié)構(gòu)，構(gòu)造出不同的向量，相當(dāng)于得到了被研究的不同的解，目標(biāo)函數(shù)值較優(yōu)的點(diǎn)被保留，目標(biāo)函數(shù)值較差的點(diǎn)被淘汰。由于遺傳操作可以越過位壘，能跳出局部較優(yōu)點(diǎn)，到達(dá)全局最優(yōu)點(diǎn)。遺傳算法是一種迭代算法，它在每一次迭代時都擁有一組解，這組解最初是隨機(jī)生成的，在每次迭代時又有一組新的解由模擬進(jìn)化和繼承的遺傳操作生成，每個解都有一目標(biāo)函數(shù)給與評判，一次迭代成為一代。典型的算法的流程圖如圖1所示，步驟有：Step1初始化：采用隨機(jī)法生成個

7、初始串作為初始群體，每個初始串稱為一個個體。Step2計(jì)算適應(yīng)度：根據(jù)適應(yīng)度函數(shù)計(jì)算第代種群每個個體的適應(yīng)值，記具有最高適應(yīng)值的個體為。Step3選擇：由父種群采用適應(yīng)度比例法選出子種群專業(yè)資料分享.........................，其中被選中的概率為。Step4交叉變異：交叉運(yùn)算，從子種群中以相同的概率選出兩個個體，這兩個個體之間以事先給定的概率執(zhí)行重組運(yùn)算，產(chǎn)生兩個新個體，重復(fù)這一過程。變異運(yùn)算根據(jù)一定的變異率P