遺傳算法學習心得體會

遺傳算法概念遺傳算法是模仿自然界生物進化機制發(fā)展起來的隨機全局搜索和優(yōu)化方法，它借鑒了達爾文的進化論和孟德爾的遺傳學說。其本質(zhì)是一種高效、并行、全局搜索的方法，它既能在搜索中自動獲取和積累有關(guān)空間知識，并自適應(yīng)地控制搜索過程以求得最優(yōu)解遺傳算法操作使用適者生存的原則，在潛在的解決方案種群中逐次產(chǎn)生一個近視最優(yōu)方案。在遺傳算法的每一代中，根據(jù)個體在問題域中的適應(yīng)度值和從自然遺傳學中借鑒來的再造方法進行個體選擇，產(chǎn)生一個新的近視解。這個過程導致種群中個體的進化，得到的新個體比原個體更適應(yīng)環(huán)境，就像自然界中的改造一樣。應(yīng)用遺傳算法在人工智能的眾多領(lǐng)域具有廣泛應(yīng)用。例如，機器學習、聚類、控制（如煤氣管道控制）、規(guī)劃（如生產(chǎn)任務(wù)規(guī)劃）、設(shè)計（如通信網(wǎng)絡(luò)設(shè)計、布局設(shè)計）、調(diào)度（如作業(yè)車間調(diào)度、機器調(diào)度、運輸問題）、配置（機器配置、分配問題）、組合優(yōu)化（如tsp、背包問題）、函數(shù)的最大值以及圖像處理和信號處理等等。遺傳算法多用應(yīng)與復雜函數(shù)的優(yōu)化問題中。原理遺傳算法模擬了自然選擇和遺傳中發(fā)生的復制、交叉、和變異等現(xiàn)象，從任一初始種群出發(fā)，通過隨機選擇、交叉、變異操作，產(chǎn)生一群更適合環(huán)境的個體，使群體進行到搜索空間中越來越好的區(qū)域，這樣一代一代地不斷繁衍進化，最后收斂到一群最適合環(huán)境的個體求得問題的最優(yōu)解。算法流程1.編碼：解空間中的解數(shù)據(jù)X,作為作為遺傳算法的表現(xiàn)型形式。從表現(xiàn)型到基本型的映射稱為編碼。遺傳算法在進行搜索之前先將解空間的解數(shù)據(jù)表示成遺傳空間的基本型串結(jié)構(gòu)數(shù)據(jù),這些串結(jié)構(gòu)數(shù)據(jù)的不同的組合就構(gòu)成了不同的點。初始種群的形成：隨機產(chǎn)生n個初始串數(shù)據(jù)，每個串數(shù)據(jù)稱為一個個體，n個串數(shù)據(jù)構(gòu)成了一個群體。遺傳算法以這n個串結(jié)構(gòu)作為初始點開始迭代。設(shè)置進化代數(shù)計數(shù)器t0;設(shè)置最大進行代數(shù)t；隨機生成m個個體作為初始群體p（0）。適應(yīng)度檢測：適應(yīng)度就是借鑒生物個體對環(huán)境的適應(yīng)程度,適應(yīng)度函數(shù)就是對問題中的個體對象所設(shè)計的表征其優(yōu)劣的一種測度。根據(jù)具體問題計算p（t）的適應(yīng)度。選擇：將選擇算子作用于群體。選擇的目的是把優(yōu)化的個體直接遺傳到下一代或通過配對交叉產(chǎn)生新的個體再遺傳到下一代。選擇操作是建立在群體中個體的適應(yīng)度評估基礎(chǔ)上的。交叉：將交叉算子作用于群體。所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。遺傳算法中起核心作用的就是交叉算子。變異：將變異算子作用于群體。即是對群體中的個體串的某些基因座上的基因值作變動。群體p（t）經(jīng)過選擇、交叉、變異運算之后得到下一代群體p（t+1）。終止條件判斷:若t<=t,則t=t+1，轉(zhuǎn)到第3步，否則以進化過程中所得到的具有最大適應(yīng)度個體作為最優(yōu)解輸出，終止計算。遺傳算法流程圖如下圖所示：遺傳算法下幾種：適應(yīng)度比例方法、隨機遍歷抽樣法、局部選擇法。其中輪盤賭選擇法是最簡單也是最常用的選擇方法。在該方法中，各個個體的選擇概率和其適應(yīng)度值成比例。設(shè)群體大小為n,其中個體i的適應(yīng)度為，則i被選擇的概率，為遺傳算法2、交叉：在自然界生物進化過程中起核心作用的是生物遺傳基因的重組(加上變異)。同樣，遺傳算法中起核心作用的是遺傳操作的交叉算子。所謂交叉是指把兩個父代個體的部分結(jié)構(gòu)加以替換重組而生成新個體的操作。通過交叉，遺傳算法的搜索能力得以飛躍提高。交叉算子根據(jù)交叉率將種群中的兩個個體隨機地交換某些基因，能夠產(chǎn)生新的基因組合，期望將有益基因組合在一起。根據(jù)編碼表示方法的不同，可以有以下的算法：b)二進制交叉(binaryvaluedcrossover)單點交叉(single-pointcrossover)多點交叉(multiple-pointcrossover)均勻交叉(uniformcrossover)洗牌交叉(shufflecrossover)縮小代理交叉(crossoverwithreducedsurrogate)。3、變異變異算子的基本內(nèi)容是對群體中的個體串的某些基因座上的基因值作變動。依據(jù)個體編碼表示方法的不同，可以有以下的算法：實值變異二進制變異。一般來說，變異算子操作的基本步驟如下：對群中所有個體以事先設(shè)定的編譯概率判斷是否進行變異對進行變異的個體隨機選擇變異位進行變異。例：簡單一元函數(shù)優(yōu)化求下面函數(shù)的最大值：f(x)=xsin(10*pi*x)+2.0, -1<=x<=2;程序：figure(1);fplot(variable.*sin(10*pi*variable)+2.0,[-1,2]); %畫出函數(shù)曲線%定義遺傳算法參數(shù)nind=40; %個體數(shù)目(numberofindividuals)maxgen=25; %最大遺傳代數(shù)(maximumnumberofgenerations)preci=20; %變量的二進制位數(shù)(precisionofvariables)ggap=0.9; %代溝(generationgap)trace=zeros(2,maxgen); %尋優(yōu)結(jié)果的初始值fieldd二[20;T;2;1;0;1;1]; %區(qū)域描述器(buildfielddescriptor)chrom=crtbp(nind,preci); %初始種群gen=0; %代計數(shù)器variable=bs2rv(chrom,fieldd); %計算初始種群的十進制轉(zhuǎn)換objv=variable.*sin(10*pi*variable)+2.0; %計算目標函數(shù)值whilegen<maxgenfitnv二ranking(-objv); %分配適應(yīng)度值(assignfitnessvalues)selch=select(sus,chrom,fitnv,ggap); %選擇selch=mut(selch); %變異variable=bs2rv(selch,fieldd); %子代個體的十進制轉(zhuǎn)換objvsel=variable.*sin(10*pi*variable)+2.0; %計算子代的目標函數(shù)值[chromobjv]=reins(chrom,selch,1,1,objv,objvsel);%重插入子代的新種群variable=bs2rv(chrom,fieldd);gen=gen+1; %代計數(shù)器增加%輸出最優(yōu)解及其序號，并在目標函數(shù)圖像中標出，y為最優(yōu)解,i為種群的序號[y,i]=max（objv）;holdon;plot（variable（i）,y,bo）;trace（1,gen）=max（objv）;%遺傳算法性能跟蹤trace（2,gen）=sum（objv）/length（objv）;endvariable二bs2rv（chrom,fieldd）;%最優(yōu)個體的十進制轉(zhuǎn)holdon,grid;plot（variable,objv,b*）;figure（2）;plot（trace（1,:））;holdon;plot（trace（2,:）,-.）;gridlegend（解的變化，種群均值的變化）篇二：遺傳算法學習心得基本概念遺傳算法（geneticalgorithms,ga）是一類借鑒生物界自然選擇和自然遺傳機制的隨機化搜索算法。它模擬自然選擇和自然遺傳過程中發(fā)生的繁殖、交叉和基因突變現(xiàn)象，在每次迭代中都保留一組候選解，并按某種指標從解群中選取較優(yōu)的個體，利用遺傳算子（選擇、交叉和變異）對這些個體進行組合，產(chǎn)生新一代的候選解群，重復此過程，直到滿足某種收斂指標為止。ga的組成:（1） 編碼（產(chǎn)生初始種群）（2） 適應(yīng)度函數(shù)（3） 遺傳算子（選擇、交叉、變異）（4） 運行參數(shù)編碼基因在一定能夠意義上包含了它所代表的問題的解?；虻木幋a方式有很多，這也取決于要解決的問題本身。常見的編碼方式有：（1） 二進制編碼，基因用0或1表示（常用于解決01背包問題）如：基因a：00100011010（代表一個個體的染色體）（2） 互換編碼（用于解決排序問題，如旅行商問題和調(diào)度問題）如旅行商問題中，一串基因編碼用來表示遍歷的城市順序，如：234517986，表示九個城市中，先經(jīng)過城市2，再經(jīng)過城市3，依此類推。（3） 樹形編碼（用于遺傳規(guī)劃中的演化編程或者表示）如,問題：給定了很多組輸入和輸出。請你為這些輸入輸出選擇一個函數(shù)，使得這個函數(shù)把每個輸入盡可能近地映射為輸出。編碼方法：基因就是樹形結(jié)構(gòu)中的一些函數(shù)。（4） 值編碼（二進制編碼不好用時，解決復雜的數(shù)值問題）在值編碼中，每個基因就是一串取值。這些取值可以是與問題有關(guān)任何值：整數(shù)，實數(shù)，字符或者其他一些更復雜的東西。適應(yīng)度函數(shù)遺傳算法對一個個體（解）的好壞用適應(yīng)度函數(shù)值來評價，適應(yīng)度函數(shù)值越大，解的質(zhì)量越好。適應(yīng)度函數(shù)是遺傳算法進化過程的驅(qū)動力，也是進行自然選擇的唯一標準，它的設(shè)計應(yīng)結(jié)合求解問題本身的要求而定。如tsp問題，遍歷各城市路徑之和越小越好，這樣可以用可能的最大路徑長度減去實際經(jīng)過的路徑長度，作為該問題的適應(yīng)度函數(shù)。遺傳算子——選擇遺傳算法使用選擇運算來實現(xiàn)對群體中的個體進行優(yōu)勝劣汰操作：適應(yīng)度高的個體被遺傳到下一代群體中的概率大；適應(yīng)度低的個體，被遺傳到下一代群體中的概率小。選擇操作的任務(wù)就是按某種方法從父代群體中選取一些個體，遺傳到下一代群體。sga（基本遺傳算法）中采用輪盤賭選擇方法。輪盤賭選擇又稱比例選擇算子，基本思想：各個個體被選中的概率與其適應(yīng)度函數(shù)值大小成正比。設(shè)群體大小為n，個體i的適應(yīng)度為fi,則個體i被選中遺傳到下一代群體的概率為：遺傳算子——交叉所謂交叉運算，是指對兩個相互配對的染色體依據(jù)交叉概率按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉運算在ga中起關(guān)鍵作用，是產(chǎn)生新個體的主要方法。單交叉點法（用于二進制編碼）選擇一個交叉點,子代在交叉點前面的基因從一個父代基因那里得到,后面的部分從另外一個父代基因那里得到。如：交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000|0000011111100010111100|01110000000010000雙交叉點法（用于二進制編碼）選擇兩個交叉點,子代基因在兩個交叉點間部分來自一個父代基因,其余部分來自于另外一個父代基因.如：交叉前：01|0010|1111|0111|01交叉后：11|0010|0101|0111|11基于“與/或”交叉法（用于二進制編碼）對父代按位與”邏輯運算產(chǎn)生一子代a;按位”或”邏輯運算產(chǎn)生另一子代b。該交叉策略在解背包問題中效果較好.如：交叉前：0100101111011101交叉后：0100100111011111單交叉點法（用于互換編碼）選擇一個交叉點，子代的從初始位置出發(fā)的部分從一個基因復制，然后在另一個基因中掃描，如果某個位點在子代中沒有，就把它添加進去。如：交叉前：87213|0954698356|71420交叉后：87213|9564098356|72104部分匹配交叉（pmx）法（用于互換編碼）先隨機產(chǎn)生兩個交叉點，定義這兩點間的區(qū)域為匹配區(qū)域，并用交換兩個父代的匹配區(qū)域。父代a：872|130|9546父代b：983|567|1420 變?yōu)椋簍empa:872|567|9546tempb:983|130|1420對于tempa、tempb中匹配區(qū)域以外出現(xiàn)的數(shù)碼重復，要依據(jù)匹配區(qū)域內(nèi)的位置逐一進行替換。匹配關(guān)系：l< >53< >67< >0子代a：802|567|9143子代b：986|130|54276?順序交叉法（ox）（用于互換編碼）從父代a隨機選一個編碼子串，放到子代a的對應(yīng)位置；子代a空余的位置從父代b中按b的順序選?。ㄅc己有編碼不重復）。同理可得子代b。父代a:872|139|0546父代b:983|567|1420交叉后：子代a:856|139|7420子代b:821|567|39047?循環(huán)交叉（ex）法（用于互換編碼）cx同ox交叉都是從一個親代中取一些城市，而其它城市來自另外一個親代，但是二者不同之處在于：ox中來自第一個親代的編碼子串是隨機產(chǎn)生的，而ex卻不是，它是根據(jù)兩個雙親相應(yīng)位置的編碼而確定的。父代a：123456789|||||父代a：546923781可得循環(huán)基因：1->5->2->4->9->1用循環(huán)的基因構(gòu)成子代a,順序與父代a—樣12 45 9用父代b剩余的基因填滿子代a：126453789子代b的編碼同理。（循環(huán)基因5->1->9->4->2->5）遺傳算子——變異變異是指依據(jù)變異概率將個體編碼串中的某些基因值用其它基因值來替換，從而形成一個新的個體。ga中的變異運算是產(chǎn)生新個體的輔助方法，它決定了ga的局部搜索能力，同時保持種群的多樣性。交叉運算和變異運算的相互配合，共同完成對搜索空間的全局搜索和局部搜索。注：變異概率pm不能太小，這樣降低全局搜索能力；也不能太大，pm>0.5，這時ga退化為隨機搜索。篇三：計算智能學習心得體會計算智能學習心得體會本學期我們水利水電專業(yè)開了“計算智能概論”這門課，有我們學院的金菊良教授給我們授課，據(jù)說這門課相當難理解，我們課下做了充分的準備，借了計算智能和人工智能相關(guān)方面的書籍，并提前了解了一點相關(guān)知識，我感覺看著有點先進，給我們以往學的課程有很大區(qū)別，是一種全新的概念和理論，里面的遺傳算法、模糊集理論、神經(jīng)網(wǎng)絡(luò)更是聞所未聞，由于課前讀了一些書籍，我以為課堂上應(yīng)該能容易理解一點，想不到課堂上聽著還是相當玄奧，遺傳算法還好一點，因為高中學過生物遺傳，遺傳算法還能理解一點。像模糊集理論神經(jīng)網(wǎng)絡(luò)便不知所云了。雖然金老師講課生動形象，幽默風趣，而且舉了好多實際的例子，但有一些理論有點偏難。多關(guān)于ci的解釋。雖然有好多計算智能理論還不太清楚，但是我對新知識還是相當渴望的，因為我本身比較愛學習，且喜歡讀書。我感覺學到了許多知識：計算智能是一門經(jīng)驗科學，它研究自然的或人工的智能行為形成之原理以“推理即計算”為基本假設(shè)，開發(fā)某種理論、說明某項智能可以算法化，從而可以用機器模擬和實現(xiàn)；尋求和接受自然智能之啟迪，但不企圖完全仿制人類智能，其中心工程目標是研究設(shè)計和建立智能計算系統(tǒng)的方法。由于我們只有16課時，所以我們學的面并不廣，金老師主要教了一些計算智能方面的經(jīng)典理論，我們所學的計算智能所涉及的領(lǐng)域主要包括以下三方面：遺傳算法、人工神經(jīng)網(wǎng)絡(luò)方法和模糊集理論。遺傳算法最早由美國michigan大學johnh.holland教授提出，按照生物進化過程中的自然選擇(selection)、父代雜交(crossover)和子代變異(mutation)的自然進化(naturalevolution)方式，編制的計算機程序，能夠解決許多復雜的優(yōu)化問題，這類新的優(yōu)化方法稱之為遺傳算法(geneticalgorithm,ga)[7]。ga模擬生物進化過程中的主要特征有：(1)生物個體的染色體(chromosomes)的結(jié)構(gòu)特征，即基因碼序列(seriesofgeneticcode)決定了該個體對其生存環(huán)境的適應(yīng)能力。(2)自然選擇在生物群體(population)進化過程中起著主導作用，它決定了群體中那些適應(yīng)能力(adaptability)強的個體能夠生存下來并傳宗接代，體現(xiàn)了“優(yōu)勝劣汰”的進化規(guī)律。(3)個體繁殖(雜交)是通過父代個體間交換基因材料來實現(xiàn)的，生成的子代個體的染色體特征可能與父代的相似，也可能與父代的有顯著差異，從而有可能改變個體適應(yīng)環(huán)境的能力。(4)變異使子代個體的染色體有別于其父代個體的染色體，從而也改變了子代個體對其環(huán)境的適應(yīng)能力。(5)生物的進化過程，從微觀上看是生物個體的染色體特征不斷改善的過程，從宏觀上看則是生物個體的適應(yīng)能力不斷提高的過程。作為利用自然選擇和群體遺傳機制進行高維非線性空間尋優(yōu)的一類通用方法，遺傳算法(ga)不一定能尋得最優(yōu)(optimal)點，但是它可以找到更優(yōu)(superior)點，這種思路與人類行為中成功的標志是相似的。例如不必要求某個圍棋高手是最優(yōu)的，要戰(zhàn)勝對手只需他(她)比其對手更強即可。因此，ga可能會暫時停留在某些非最優(yōu)點上，直到變異發(fā)生使它遷移到另一更優(yōu)點上。遺傳算法隨編碼方式、遺傳操作算子的不同而表現(xiàn)為不同形式，因此難以象傳統(tǒng)的共軛梯度法那樣從形式上給以明確定義，它的識別標志在于它是否具有模擬生物的自然選擇和群體遺傳機理這一內(nèi)在特征。目前國內(nèi)外普遍應(yīng)用的實施方案是標準遺傳算法(simplegeneticalgorithm,sga)。bp神經(jīng)網(wǎng)絡(luò)bp神經(jīng)網(wǎng)絡(luò)是用反向傳播學習算法(back-propagationalgorithm,bp算法)訓練的一種多層前饋型非線性映射網(wǎng)絡(luò)，網(wǎng)絡(luò)中各神經(jīng)元接受前一級的輸入，并輸出到下一級，網(wǎng)絡(luò)中沒有反饋聯(lián)接。bp神經(jīng)網(wǎng)絡(luò)通?？梢苑譃椴煌膶?級)，第j層的輸入僅與第j-1層的輸出聯(lián)接。由于輸入層節(jié)點和輸出層節(jié)點可與外界相連，直接接受環(huán)境的影響，所以稱為可見層，而其它中間層則稱為隱層(hiddenlayer)。決定一個bp神經(jīng)網(wǎng)絡(luò)性質(zhì)的要素有三個：網(wǎng)絡(luò)結(jié)構(gòu)、神經(jīng)元作用函數(shù)和學習算法，對這三個要素的研究構(gòu)成了豐富多彩的內(nèi)容，尤其是后者被研究得最多。bp算法是目前應(yīng)用最為廣泛且較成功的一種算法，它解決了多層前饋網(wǎng)絡(luò)的學習問題，從而使該網(wǎng)絡(luò)在各方面獲得了廣泛應(yīng)用。它利用梯度搜索技術(shù)(gradientsearchtechnique)使代價函數(shù)(costfunction)最小化。bp算法把一組樣本的輸入輸出問題歸納為一非線性優(yōu)化問題，它使用了最優(yōu)化方法中最常用的負梯度下降算法。用迭代運算求解網(wǎng)絡(luò)權(quán)重和閾值對應(yīng)于網(wǎng)絡(luò)的學習記憶過程，加入隱層節(jié)點使得優(yōu)化問題的可調(diào)參數(shù)增加，從而可得到更精確的解。模糊集理論模糊集理論(又稱模糊數(shù)學，fuzzymathematics)就是應(yīng)用模糊集這一模擬人腦模糊思維的數(shù)學工具，來描述、分析、識別、分類、判斷、推理、決策和控制各種模糊事物所形成的一門現(xiàn)代應(yīng)用數(shù)學分支學科。經(jīng)典數(shù)學僅考慮現(xiàn)實世界的數(shù)量而拋棄現(xiàn)實世界的質(zhì)量，而模糊集理論則反映了現(xiàn)實世界數(shù)量與質(zhì)量的統(tǒng)一性，是對經(jīng)典數(shù)學的一種補充和完善。定義模糊集、模糊關(guān)系的不同運算(目前主要是代數(shù)運算)，就可得到相應(yīng)的不同模糊數(shù)學方法。目前已研究成熟并廣為應(yīng)用的模糊數(shù)學方法主要有模糊模式識別、模糊聚類分析、模糊綜合評價、模糊推理、模糊控制等方法。在現(xiàn)代科學技術(shù)體系中定性因素和主觀因素定量化處理的方法至今仍很少，而模糊數(shù)學方法正是其中的典型代表，目前已在各科學和工程領(lǐng)域得到了廣泛的成功應(yīng)用，其主要原因在于它異于其它方法的一些顯著特點：(1)模糊集的引入改善了二值邏輯中硬性的分類方法，是普通集合的推廣，使模糊數(shù)學方法更加接近于廣泛存在模糊性和不精確性的現(xiàn)實世界，也更加接近于人類思維方式。這些真實性使得模糊數(shù)學方法能很好地平衡系統(tǒng)的復雜性與描述系統(tǒng)的精確性，也有助于模糊數(shù)學方法充分提取各種專家經(jīng)驗信息和其它人類語言信息。(2)當系統(tǒng)為多輸入多輸出、強非線性、定性信息與定量信息混雜的動態(tài)系統(tǒng)時，系統(tǒng)的數(shù)學模型非常復雜或根本就不存在確定性數(shù)學模型，常規(guī)方法難以或不能有效處理這樣的復雜系統(tǒng)，而模糊數(shù)學方法可以用建立在語言型經(jīng)驗之上的模糊集及其運算就可以簡便有效地處理，有時甚至不需要輔以確定的數(shù)學模型。(3)模糊數(shù)學方法可以直接利用人類語言型概念及其運算，篇四：遺傳算法總結(jié)遺傳算法總結(jié)遺傳算法是借鑒生物的自然選擇和遺傳進化機制而開發(fā)出的一種全局自適應(yīng)概率搜索算法。一、 遺傳算法流程圖圖1遺傳算法流程圖二、 遺傳算法的原理和方法染色體編碼把一個問題的可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就稱為編碼。dejong曾提出了兩條操作性較強的實用編碼原則：編碼原則一：應(yīng)使用能易于產(chǎn)生與所求問題相關(guān)的且具有低階、短定義長度模式的編碼方案；編碼原則二：應(yīng)使用能使問題得到自然表示或描述的具有最小編碼字符集的編碼方案。編碼方法主要有以下幾種：二進制編碼方法、格雷碼編碼方法、浮點數(shù)編碼方法、符號編碼方法、參數(shù)級聯(lián)編碼方法、多參數(shù)交叉編碼方法。2)適應(yīng)值計算由解空間中某一點的目標函數(shù)值f(x)到搜索空間中對應(yīng)個體的適應(yīng)度函數(shù)值fit(f(x))的轉(zhuǎn)換方法基本上有一下三種：直接以待解的目標函數(shù)值f(x)轉(zhuǎn)化為適應(yīng)度函數(shù)值fit(f(x)),令?f(x)目標函數(shù)為最大化函數(shù)fit(fx())=???f(x)目標函數(shù)為最小化函數(shù)?cmax?f(x)f(x)?cmax對于最小值的問題，做下列轉(zhuǎn)化fit(f(x))??,其中cmax是0 其他?f(x)的最大輸入值。若目標函數(shù)為最小值問題，fit(f(x))?1, c?0,c?f(x)?01?c?f(x)1, c?0,c?f(x)?01?c?f(x)若目標函數(shù)為最大值問題，fit(f(x))?3)選擇、交叉、變異遺傳算法使用選擇算子來對群體中的個體進行優(yōu)勝劣汰操作：根據(jù)每個個體的適應(yīng)度值大小選擇。適應(yīng)度較高的個體被遺傳到下一代群體中的概率較大；適應(yīng)度較低的個體的被遺傳到下一代群體中的概率較小。其中選擇的方法有：輪盤賭選擇、隨機競爭選擇、最佳保留選擇、無回放隨機選擇、確定式選擇等。遺傳算法中的所謂交叉運算，是指對兩個相互配對的染色體按某種方式相互交換其部分基因，從而形成兩個新的個體。交叉操作主要有單點交叉、兩點交叉與多點交叉、均勻交叉和算數(shù)交叉四種。遺傳算法中的變異運算，是指將個體染色體編碼串中的某些基因座上的基因值用該基因座的其他基因來替換，從而形成一個新的個體。主要有基本位變異、均勻變異、邊界變異等幾種變異操作方法。4)控制參數(shù)選擇交叉概率pcpm三、算例minf(x1,x2)?(x1?3)2?(x2?2)22?g1(x1,x2)?x12?x2?5?s.t.?h1(x1,x2)?x1?2x2?4?0?x,x?10，x?n121?(1)三種不同的遺傳方法方法一：原模型中x1、x2均為決策變量，操作如下。a.采用混合整數(shù)編碼，對x1進行十進制編碼，x2進行二進制編碼；b.適應(yīng)度函數(shù)值采用fit(f(x1,x2))?1計算，其中c?f(x1,x2)c???max{0,g1(x1,x2)?5}???max{0,|h1(x1,x2)?4|}，?=?=10000；采用賭輪盤選擇、單點交叉和基本位變異；pc=0.8,pm=0.1,遺傳代數(shù)為200，種群中個體數(shù)100；e.終止條件為連續(xù)十次最優(yōu)個體保持不變或遺傳代數(shù)到達200。方法二：已知等式約束hl(xl,x2),可得x2?(4?xl)/2,則原問題可化為minf(x1)?(x1?3)2?((4?x1)?2)22(2)4?x12?2g(x)?x?()?5111? 2?s..t?0?x1?10,x1?n?4?x1?0??102?xminf(x1)?(x1?3)2?(1)22即等式約束簡化后的模型為4?x12?2g(x)?x?()?5?1s..t?112??0?x1?4,x1?n其中a~b的操作如下，而c~e的操作同方法一。a.對x1進行十進制編碼;b.適應(yīng)度函數(shù)值采用fit(f(xl,x2))?(3)1計算,其中c?f(x1,x2)c???max{0,g1(x1,x2)?5},?=10000方法三：在方法二的基礎(chǔ)上，改變x1的編碼方法，對x1進行二進制編碼。由于0?xl?4,且為自然數(shù),則二進制編碼至少為3位,但3位的二進制可以表示0~7的整數(shù),所以存在冗余編碼。則通過懲罰來排除冗余編碼，即適應(yīng)度函數(shù)值采用fit(f(x1,x2))?1計算。c?f(x1,x2)其中c???max{0,gl(xl,x2)?5}???max{0,xl(i)?4},?=10000。x1(i)表示個體解碼后的x1。三種方法的計算結(jié)果方法一可得到三個不同的解：解1：xl?2,x2?l,fit(f(xl,x2))?0.4646,f(x)?2.0000,適應(yīng)度趨勢圖如下：圖2方法一解1的適應(yīng)度趨勢圖解2：x1?0,x2?2,fit(f(x1,x2))?0.1075, f(x)?9.0000,適應(yīng)度趨勢圖如下：篇五：遺傳算法學習作業(yè)遺傳算法學習總結(jié)概述遺傳算法是一類借鑒生物界的進化規(guī)律(適者生存,優(yōu)勝劣汰遺傳機制)演化而來的自適應(yīng)概率性隨機化迭代搜索算法。1962年霍蘭德(holland)教授首次提出了ga算法的思想，它的基本思想是基于darwin進化論和mendel的遺傳演說。darwin進化論最重要的是適者生存的原理,它認為每一代種群總是向著前進方向發(fā)展,越來越適應(yīng)環(huán)境。每一個個體都有繼承前代的特性,但不是完全繼承,會產(chǎn)生一些新特性。最終只有適應(yīng)環(huán)境的特征才能被保留下來。mendel遺傳學說最重要的是基因遺傳原理,它認為遺傳以密碼方式存在細胞中,并以基因形式包含在染色體內(nèi)。一條染色體中存在很多基因,每個基因有自己的位置并控制著外部特征；基因的產(chǎn)生和變異直接影響到個體的特性是否能適應(yīng)環(huán)境。經(jīng)過存優(yōu)去劣的自然淘汰，適應(yīng)性高的基因結(jié)構(gòu)得以保存下來。遺傳算法正是借用了仿真生物遺傳學和自然選擇機理，通過自然選擇、遺傳、變異等作用機制，實現(xiàn)各個個體的適應(yīng)性的提高。與自然界相似，遺傳算法對求解問題的本身一無所知，從代表問題可能潛在解集的一個種群(population)開始，每一個種群則由經(jīng)過基因(gene)編碼(coding)的一定數(shù)目的個體(individual)構(gòu)成。每個個體實際上是染色體(chromosome)帶有特征的實體。把問題的解表示成染色體，并基于適應(yīng)值來選擇染色體，遺傳算法所需要的僅是對算法所產(chǎn)生的每個染色體進行評價，使適應(yīng)性好的染色體有更多的繁殖機會。在算法中也就是以二進制編碼的串。并且，在執(zhí)行遺傳算法之前，給出一群染色體，也就是假設(shè)解。然后，把這些假設(shè)解置于問題的“環(huán)境”中，也即在一個適應(yīng)度函數(shù)中來評價。并按適者生存的原則，從中選擇出較適應(yīng)環(huán)境的染色體進行復制，淘汰低適應(yīng)度的個體，再通過交叉，變異過程產(chǎn)生更適應(yīng)環(huán)境的新一代染色體群。對這個新種群進行下一輪進化，直到最適合環(huán)境的值。遺傳算法的基本原理和特點1.2.1算法原理在遺傳算法中，通過隨機方式產(chǎn)生若干個所求解問題的數(shù)字編碼，即染色體，形成初始種群；通過適應(yīng)度函數(shù)給每個個體一個數(shù)值評價，淘汰低適應(yīng)度的個體，選擇高適應(yīng)度的個體參加遺傳操作，經(jīng)過遺傳操作后的個體集合形成下一代新的種群，再對這個新種群進行下一輪進化，這就是遺傳算法的基本原理。遺傳算法的主要步驟如下：隨機產(chǎn)生一個由確定長度的特征串組成的初始群體；對串群體迭代地執(zhí)行步驟(1)和(2)，直到滿足停止準則：計算群體中每個個體的適應(yīng)值。應(yīng)用復制、雜交和變異算子產(chǎn)生下一代群體。把在任一代中出現(xiàn)的最好的個體串指定為遺傳算法的執(zhí)行結(jié)果。這個結(jié)果可以表示問題的一個解(或近似解)?；具z傳算法的流程圖如圖1-1，其中g(shù)en是當前代數(shù)，m為每代種群中最大個體數(shù)。圖1-1基本遺傳算法的流程圖算法特點遺傳算法的特點如下：遺傳算法中不包含待解決問題所持有的形態(tài)。它是從改變基因的配置來實現(xiàn)問題的整體優(yōu)化的，因而屬于自下而上的優(yōu)化方法；類似于生物的進化過程，遺傳算法處理的是變量集合的編碼而非變量本身。它直接對結(jié)構(gòu)對象進行操作，不存在求導和函數(shù)連續(xù)性的限定；遺傳算法具有內(nèi)在的隱并行性和更好的全局尋優(yōu)能力；遺傳算法采用概率化的尋優(yōu)方法，能自動獲取和指導優(yōu)化的搜索空間，自適應(yīng)地調(diào)整搜索方向，不需要確定的規(guī)則。遺傳算法的這些特點已被人們廣泛地應(yīng)用于組合優(yōu)化、機器學習、信號處理、自適應(yīng)控制和人工生命等領(lǐng)域。它是現(xiàn)代有關(guān)智能計算中的關(guān)鍵技術(shù)之一。1.3基本遺傳算法的步驟1.3.1染色體編碼(chromosomecoding)與解碼(decode)基本遺傳算法使用固定長度的二進制符號串來表示群體中的個體，其等位基因由二值｛0，1｝所組成。初始群體中各個個體的基因可用均勻分布的隨機數(shù)來生成。例如：x=100111001000101101就可表示一個個體，該個體的染色體長度是n=18。編碼：變量x作為實數(shù)，可以視為遺傳算法的表現(xiàn)型形式。從表現(xiàn)型到基因型的映射稱為編碼。設(shè)某一參數(shù)的取值范圍為［ul,u2］，我們用長度為k的二進制編碼符號來表示該參數(shù)，則它總共產(chǎn)生2k種不同的編碼，可使參數(shù)編碼時的對應(yīng)關(guān)系為：000000?0000=0—u1000000?0001=1—u1+?000000?0010=2—u1+2??111111?1111=2k-1—u2u?u其中，?=2k1。 2?1解碼：假設(shè)某一個體的編碼為bkbk-1bk-2?b2b1,則對應(yīng)的解碼公式為x?u1?(?bi?2i?1)?i?1ku2?u1 ①k2?1例如：設(shè)有參數(shù)x￡［2，4］，現(xiàn)用5位二進制編碼對x進行編碼，得25=32個二進制串(染色體)：00000,00001,00010,00011,00100,00101,00110,0011101000,01001,01010,01011,01100,01101,01110,0111110000,10001,10010,10011,10100,10101,10110,1011111000,11001,11010,11011,11100,11101,11110,11111對于任一個二進制串，只要代入公式①，就可得到相應(yīng)的解碼，如x22=10101,它對應(yīng)的十進制為?bi?2i?1=1+0*2+1*22+0*23+1*24=21,則對應(yīng)參數(shù)i?15x的值為2+21*(4-2)/(25-1)=3.3548。個體適應(yīng)度的檢測評估基本遺傳算法按與個體適應(yīng)度成正比的概率來決定當前群體中各個個體遺傳到下一代群體中的機會多少。為了正確估計這個概率，要求所有個體的適應(yīng)度必須為非負數(shù)。所以，根據(jù)不同種類的問題，需要預(yù)先確定好由目標函數(shù)值到個體適應(yīng)度之間的轉(zhuǎn)換規(guī)律，特別是要預(yù)先確定好當目標函數(shù)值為負數(shù)時的處理方法。例如，可選取一個適當大的正數(shù)c使個體的適應(yīng)度為目標函數(shù)值加上正數(shù)c。遺傳算子基本遺傳算法使用下列三種遺傳算子：(1)選擇運算使用比例選擇算子。比例選擇因子是利用比例于各個個體適應(yīng)度的概率決定其子孫的遺傳可能性。若設(shè)種群數(shù)為m,個體i的適應(yīng)度為fi,則個體i被選取的概率為pi?fi/?fkk?1m當個體選擇的概率給定后，產(chǎn)生［0，1］之間的均勻隨機數(shù)來決定哪個個體參加交配。若個體的選擇概率大，則能被多次選中，它的遺傳基因就會在種群中擴大；若個體的選擇概率小，則被淘汰。我們經(jīng)常采用的是輪盤賭的原理，個體的選擇概率是基于它們的性能進行的一些計算。實值范圍——總和是所有個體期望的選擇概率的總和或當前種群中所有個