遺傳算法的作用

1、遺傳算法的應用一、什么是遺傳算法？遺傳算法是一種全局概率搜索優(yōu)化算法。遺傳算法（GnectciAlgortihms），是一種模擬自然界生物進化過程的全局隨機搜索算法，由美國Mcihigna大學的Hollnad教授于60年代首先提出。它將計算機科學與進化論思想有機結合起來，借助于生物進化機制與遺傳學原理，根優(yōu)勝劣汰和適者生存的原則，通過模擬自然界中生物群體由低級、簡單到高級、復雜的生物進化過程，使所要解決的問題從初始解逐漸逼近最優(yōu)解或準最優(yōu)解。作為一種新的全局優(yōu)化搜索算法，遺傳算法因其簡單易用，對很多優(yōu)化問題能夠較容易地解出令人滿意的解，適用于并行分布處理等特點而得到深入發(fā)展和廣泛應用，已在科學

2、研究和工程最優(yōu)化領域中展現(xiàn)出獨特魅力.二、遺傳算法的發(fā)展：從20世紀40年代，生物模擬就成為了計算科學的一個組成部分；20世紀50年代中期創(chuàng)立了仿生學；進入60年代后，美國密切根大學教授Holland及其學生創(chuàng)造出遺傳算法。三、遺傳算法的特點：遺傳算法作為具有系統(tǒng)優(yōu)化、適應和學習的高性能計算和建模方法的研究漸趨成熟。遺傳算法具有進化計算的所有特征，同時又具有自身的特點：（1）搜索過程既不受優(yōu)化函數(shù)的連續(xù)性約束，也沒有優(yōu)化函數(shù)導數(shù)必須存在的要求。（2）遺傳算法采用多點搜索或者說是群體搜索，具有很高的隱含并行性，因而可以提高計算速度。（3）遺傳算法是一種自適應搜索技術，其選擇、交叉、變異等運算都是

3、以一種概率方式來進行，從而增加了搜索過程的靈活性，具有較好的全局優(yōu)化求解能力。（4）遺傳算法直接以目標函數(shù)值為搜索信息，對函數(shù)的性態(tài)無要求，具有較好的普適性和易擴充性。（5）遺傳算法更適合大規(guī)模復雜問題的優(yōu)化。四、遺傳算法的原理和方法：（1）編碼：編碼是把一個問題的可行解從其解空間轉換到GA所能處理的搜索空間的轉換方法。而解碼是由GA解空間向問題空間的轉換。編碼機制直接影響著算法的整體性能，也決定了種群初始化和各種遺傳算子的設計等各種過程。常用的編碼方案有：二進制編碼、Gray編碼和實數(shù)編碼等。（2）種群的初始化：種群的初始化是指如何生成第一代初始種群。對于二進制編碼機制，初始化就是生成多個二

4、進制數(shù)串；對于實數(shù)編碼機制，初始化是指生成多個實數(shù)數(shù)串。（3）適應度函數(shù)：適應度是用來衡量群體中各個個體在優(yōu)化計算中能達到或接近于或有助于找到最優(yōu)解的優(yōu)良程度。適應度較高的個體遺傳到下一代的概率就較大；反之遺傳到下一代的概率就相對較小。度量個體適應度的函數(shù)稱為適應度函數(shù)，是根據(jù)目標函數(shù)確定的，用于區(qū)分群體中個體好壞的標準，是算法演化過程的驅動力。（4）選擇算子：選擇算子是從一個舊種群選擇生命力頑強的個體位串進行復制，從而產(chǎn)生新種群的過程。不同的選擇操作會導致不同的選擇效果，較大的選擇壓力將會使當前種群中的最優(yōu)個體具有較高的復制數(shù)目，算法會以較快的速度收斂，容易出現(xiàn)“早熟”問題。相反，較小的選擇

5、壓力能使種群的保持多樣性，有利于跳出局部最優(yōu)，收斂于全局最優(yōu)點，但缺點是收斂速度慢，效率低下。常用的選擇算子有：輪盤賭選擇、基于排序的選擇、局部競爭選擇、最佳個體保存選擇和Boltzmann選擇等。（5）交叉算子：交叉算子是指兩個相互配對的染色體按照某種方式相互交換自身的部分基因片，從而構成兩個新個體的過程。交叉算子不僅要考慮生成更多不同的個體，保持種群的多樣性；還要避免破壞種群中的優(yōu)良個體，加快種群的收斂速度，才能使種群的多樣性和收斂性達到和諧的統(tǒng)一。常用的交叉算子有：單點交叉、多點交叉、均勻交叉和算術交叉等。（6）變異算子：變異是指父代染色體中的某些基因片，以相對較小的概率發(fā)生隨機改變的操

6、作過程。變異的概率決定了種群中個體發(fā)生變異的機會大小，如果制定過高，容易破壞種群中已有的優(yōu)良個體結構；如果制定過低，則產(chǎn)生新個體的速度慢，收斂速度慢，甚至可能陷入局部最優(yōu)。常用的變異算子有：倒位變異、交換變異和插入變異等。研究表明，將多種變異算子在交叉使用或者按照一定的概率進行分配使用，會帶來較好的效果。五、遺傳算法實現(xiàn)的基本流程：遺傳算法的早期研究，其基本實現(xiàn)步驟如下：（1）確定種群規(guī)模、交叉概率、變異概率以及算法終止條件（2）以一定的方式產(chǎn)生初始種群（3）計算種群中個體的適應度（4）對當前種群實施選擇、交叉、變異操作、產(chǎn)生新種群（5）進化終止條件判斷，若滿足終止條件，則進化終止，輸出優(yōu)化結

7、果，否則轉到步驟3）。具體流程如下圖1所示。圖1遺傳算法基本流程圖六、遺傳算法的三種基本操作：1、選擇選擇即是在種群中選擇一個個體，它是隨機映射：T:SnTS.s特別地，按照概率：Pa(X)=Xfa(X)/丈fa(X)siikk=1其中N為種群規(guī)模，f(X)表示個體X的適應值，為選擇壓，適應值大的選中概率ii越大，復制多，反之相反。常見選擇方法的優(yōu)劣比例選擇的問題：記p仗)為第t代個體x出現(xiàn)的概率，其中x為任一個體，i+1則P(X)=P(X)上衛(wèi)i+1tf其中f為種群平均適應值。f一般不是常數(shù)，種群平均適應值是隨時間變化的量。從而實際計算中的常值計算存在偏差。比例選擇應用廣泛，但存在一些不合理

8、之處。1.對選擇函數(shù)有要求。2.容易過早收斂而得到局部最優(yōu)解。3.對于較平均的現(xiàn)象，則會出現(xiàn)算法變慢的現(xiàn)象。比例選擇的常見問題還是選擇壓的問題。另外，如其他選擇，排序選擇具有一致的、可控的選擇壓。聯(lián)賽選擇操作既能使好的個體得到較多繁殖的機會，又能防止其繁殖過多的個體。穩(wěn)態(tài)選擇比起線性排序選擇來說有較高的增長率，這容易導致早熟。穩(wěn)態(tài)選擇一般適用大種群規(guī)?；蚨喾N群進化策略。2、交叉交叉是母體的操作，是母體空間到母體空間的映射，記做T:S2TS2c單點交叉：等概率地隨機確定一個基因位置作為交叉點，再把一對母體從交叉點分為前后兩部分，交換兩個個體的后部分，得到兩個新個體。若以概率p交換兩個個體的c后半

9、部分，得到兩個新個體，稱為單點隨機交叉，稱p為交叉概率。如果確定兩個基因位c置將一對母體分成三部分，交換中間部分，則稱為兩點交叉。同樣有兩點交叉與兩點隨機交叉之分。致隨機交叉：獨立地以概率p把母體的一個個體想要分量交換為第二母體相應c分量，從而得到交叉結果。其數(shù)學表述如下：對于長度為l的兩個個體X、XeS，設置長度為l的二值交叉串tgS，定義：12x=x,x=x,ift=0i=1,2,，lv1i1i2i2iix=x,x=x,ift=12i2i2i1ii當交叉字串t以一定概率p選取，上式的交叉也以一定概率發(fā)生時，稱為一致隨機交c叉，記為Q,X）二c（X,X）。12t123、變異變異是個體空間到個

10、體空間的隨機映射T:STS，其獨立地以概率p改變個體分量mm的取值，p稱作變異概率。m單點變異：等概率地隨機確定一個基因，改變個體分量的取值。單點隨機變異：等概率地隨機確定一個基因，以概率P改變個體分量的取值。m一致變異：等概率地對個體的每一個基因，改變個體分量的取值。一致隨機變異：等概率地對個體的每一個基因以概率p改變個體分量的取值。數(shù)學表達式如下：m對于個體XgS，設置二進制變異字串tgS，則X的一致變異X二m（X）定義為：tx=xft=0,l1；1i=1,2.,lx=|x-1|,ft=1,Jiii其中x,x分別表示個體X、X的第i位基因值，t.表示二進制變異字串t的第i位iii值。當變異

11、字串一定概率p選取，上式的變異也以一定的概率發(fā)生時，稱為一致隨機變異。m變異模仿自然界匯總的基因突變，保證算法能搜索到問題解空間的每一點，從而使遺傳算法具有全局尋優(yōu)能力。七、遺傳算法應用實例遺傳算法在可靠性中的應用如圖：A受力示意圖廠iz各單元截面面積與慣性矩的關系為IA2(i=i,2),彈性模量均為E=2X106KN/m2,iii單元截面積A,A以及外荷載P為隨機變量。如果節(jié)點3的水平控制位移u為最大變形控12制，允許的最大位移：Z二g(A,P,lu1)二10u(A,P)=olu=10mm3求解該框架結構的可靠度指標。變量編碼采用3個9位二進制編碼串表示框架結構的3個變量A,A,P。其中，A

12、的取值為0.2001210.400m2,A2的取值為0.1000.300m2,P的取值為10.0050.00KN,均用二進制編碼串000000000111111111對應表示。將編碼串連成一個27位長的二進制編碼串，構成了框架結構的軟色體編碼,則解空間和遺傳算法的搜索空間具有一一對應關系。變量解碼解碼和編碼的過程是互逆的。所以解碼時,應先將二進制編碼串根據(jù)編碼時所表示的設計變量個數(shù)切斷為若干個二進制編碼串，然后將其轉換為十進制代碼y,最后用解碼公式算出i變量X。編碼為x=bbb.bb的個體，十進制代碼為y=b2i-1,其解碼公式ii1i221iii1X二U+mfiny。其中U,Umin分別表示

13、參數(shù)的最大值和最小值。min2i1imax因此可得到：結構的設計變量Al,A2,p通過上式可計算得到。利用MATLAB根據(jù)改進遺傳算法的優(yōu)化程序，對框架結構的可靠度進行編程，可得到可靠性結果。遺傳算法正日益和神經(jīng)網(wǎng)絡、模糊推理以及混沌理論等其他智能計算方法相互滲透和結合,起到取長補短的作用。這對開拓新的智能計算技術將具有重要意義。八、遺傳算法的應用：(l)函數(shù)優(yōu)化：是GA的經(jīng)典應用領域，也是對GA進行性能評價的常用算例，對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解，GA卻可以得到較好的結果。(2)組合優(yōu)化：隨問題規(guī)模的擴大，搜索空間急劇擴大，對這類復雜問題，實踐證明，G

14、A對于組合優(yōu)化的NP完全問題非常有效。生產(chǎn)調度問題：GA已成為解決復雜調度問題的有效工具，在單件生產(chǎn)車間調度、流水線生產(chǎn)車間調度、生產(chǎn)規(guī)模、人物分配等方面都得到了有效的應用。自動控制：GA在自動控制領域中的應用日益增加，并顯示了良好的效果。如在參數(shù)辨識、人工神經(jīng)網(wǎng)絡的結構優(yōu)化設計和權值學習，都顯示了GA的應用優(yōu)勢。機器人智能控制：GA是源自于對人工自適應系統(tǒng)的研究，已經(jīng)在移動機器人路徑規(guī)劃、關節(jié)機器人運動軌跡規(guī)律、機器人逆運動學求解、細胞機器人的結構優(yōu)化和行動協(xié)調等方面得到研究和應用。圖像處理和模式識別在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免的會產(chǎn)生一些誤差。目前,GA已在圖像恢

15、復、圖像邊緣特征提取、幾何形狀識別等方面得到了應用。人工生命人下生命是用計算機、機械等人下媒體模擬或構造出的具有自然生物系統(tǒng)特有行為的人造系統(tǒng)。自組織能力和自學習能力是人下生命的兩大主要特征。人下生命與遺傳算法有著密切的關系?；谶z傳算法的進化模型是研究人下生命現(xiàn)象的重要基礎理論。雖然人下生命的研究尚處于啟蒙階段，但遺傳算法已在其進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應用能力，并且必將得到更為深入的應用和發(fā)展。人工生命與遺傳算法相輔相成，遺傳算法為人下生命的研究提供一個有效的下具，人下生命的研究也必將促進遺傳算法的進一步發(fā)展。遺傳編程l989年，美國Standford大學

16、的Koza教授發(fā)展了遺傳編程的概念,其基木思想是:采用樹型結構表示計算機程序,運用遺傳算法的思想,通過自動生成計算機程序來解決問題。雖然遺傳編程的理論尚米成熱,應用也有一此限制,但它已成功地應用于人工智能、機器學習等領域。目前公開的遺傳編程實驗系統(tǒng)有十多個。例如，Koza開發(fā)的ADF系統(tǒng)，While開發(fā)的GPELST系統(tǒng)等。機器學習學習能力是高級自適應系統(tǒng)所具備的能力之一，基于遺傳算法的機器學習，特別是分類器系統(tǒng)，在很多領域中都得到了應用。例如，遺傳算法被用于學習模糊控制規(guī)則，利用遺傳算法來學習隸屬度函數(shù)，從而更好地改進了模糊系統(tǒng)的性能；基于遺傳算法的機器學習可用來調整人工神經(jīng)網(wǎng)絡的連接權，也

17、可用于人工神經(jīng)網(wǎng)絡結構優(yōu)化設計；分類器系統(tǒng)也在學習式多機器人路徑規(guī)劃系統(tǒng)中得到了成功的應用。（10）數(shù)據(jù)挖掘數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術，它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應用價值的知識和規(guī)則。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。因此，應用遺傳算法在數(shù)據(jù)庫中進行搜索，對隨機產(chǎn)生的一組規(guī)則進行進化直到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。Sunil已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘下具。利用該工具對兩個飛機失事的真實數(shù)據(jù)庫進行了數(shù)據(jù)挖掘實驗，結果表明遺傳算法是進行數(shù)據(jù)挖掘的有效方法之一。參考文獻1.人工智能專著（日）溝口理一郎,石