遺傳算法基礎(chǔ)遺傳算法定義：自適應(yīng)全局優(yōu)化概率搜索算法1.2.遺傳操作：選擇：根據(jù)各個體的適應(yīng)度，按照一定的規(guī)則或方法，從第t代群體P(t)中選擇一些優(yōu)良的個體遺傳到下一代群體P(t+1)中。交叉：將群體P(t)內(nèi)的各個個體隨機搭配成對，對每一個個體，以某個概率(交叉概率)，交互互相之間的部分染色體。變異：對群體P(t)中的每一個個體，以某個概率(變異概率)，改變某一個或某一些基因座上的基因值為其他的等位基因。1.3.遺傳算法主要運算過程：步驟一：初始化。設(shè)置進化代數(shù)計數(shù)器t=0；設(shè)置最大進化代數(shù)T；隨機生成M個個體作為初始群體P(0)。步驟二：個體評價。計算群體P(t)中各個個體的適應(yīng)度。步驟三：選擇運算。將選擇算子作用于群體。步驟四：交叉運算。將交叉算子作用于群體。步驟五：變異運算。將變異算子作用于群體。得到下一代群體P(t+1)。步驟六：終止條件判斷。若t<=T則」：t=t+1,轉(zhuǎn)到步驟二；若t>T，則以進化過程中所得到的具有最大適應(yīng)度的個體作為最優(yōu)解輸出，終止計算。

1.4.特點：遺傳算法以決策變量的編碼作為運算對象。直接以目標函數(shù)值作為搜索信息。同時使用多個搜索點的搜索信息。概率搜索技術(shù)?；具z傳算法基本遺傳算法simplegeneticalgorithms：只使用選擇算子，交叉算子，變異算子基本遺傳算法構(gòu)成要素：染色體編碼方法：固定長度二進制符號串表示個體個體適應(yīng)度評價：按照與個體適應(yīng)度成正比的概率決定當前群體中每個個體遺傳到下一代群體中的機會，適應(yīng)度為正數(shù)或0。預(yù)先設(shè)好目標函數(shù)到適應(yīng)度的轉(zhuǎn)換規(guī)則。遺傳算子：選擇使用比例選擇算子；交叉使用單點交叉算子；變異使用基本位變異算子或均勻變異算子。運行參數(shù)：M-群體大小，一般20?100；T-終止進化代數(shù)，一般100?500；Pc-交叉概率，一般0.4?0.99；Pm-變異概率，一般0.0001?0.1基本遺傳算法描述形式化定義：8元組心“匚厲，皿°匚*「 Q1)個體編碼方法；個體適應(yīng)度評價函數(shù)；初始群體；群體大??；選擇算子；交叉算子；變異算子；遺傳運算終止條件procedureSGAinitP(0);t=0;while(t<=T){計算出個體適應(yīng)度for(inti=0;i<M;i++){evaluatefitnessofP(t);計算出個體適應(yīng)度}for(inti=0;i<M;i++){selectoperationofP(t);}for(inti=0;i<M/2;i++){crossoveroperationofP(t);}for(inti=0;i<M;i++){mutationoperationofP(t);}for(inti=0;i<M;i++){P(t+1)=P(t);}t++;}基本遺傳算法的實現(xiàn)個體適應(yīng)度評價：越大，遺傳到下一代概率也越大；越小，遺傳到下一代概率也越?。徽龜?shù)或0；目標函數(shù)f(X)變換為個體適應(yīng)度F(X)兩種方法:對于求目標函數(shù)最大值的優(yōu)化問題卩(X)+CU,iff(X)+C罰〉0F*-(°, Hf(X)+CmiXOCmin為一個適當小的數(shù)：預(yù)先制定；進化到當前為止的最小目標函數(shù)值；當前代或最近幾代的最小目標函數(shù)值。對于求目標函數(shù)最小值的優(yōu)化問題Cmax為一個適當?shù)叵鄬Ρ容^大的數(shù)：預(yù)先制定；進化到當前為止的最大目標函數(shù)值；當前代或最近幾代的最大目標函數(shù)值。比例選擇算子：(有退還隨機選擇，賭盤選擇)個體被選中遺傳到下一代的概率與該個體適應(yīng)度大小成正比；執(zhí)行過程：計算出所有個體適應(yīng)度總和；計算出每一個體相對適應(yīng)度大小，即各個體被遺傳到下一代群體中的概率0到1隨機數(shù)，確定各個體被選定的次數(shù)；單點交換算子：執(zhí)行過程：群體中的個體兩兩配對，共有I 紗對個體組；對每一對配對個體，隨機設(shè)置某一基因座之后的位置為交叉點。染色體長度為n,共有n-1個可能的交叉點位置。對每一對配對個體，依交叉概率Pc在交叉點相互交換兩個個體的部分染色體，產(chǎn)生新的個體。A：10110111[o0單點交叉A'11O11O111U1B：O0011100H1 ；O0011100=00交叉占基本位變異算子：執(zhí)行過程：對個體的每一個基因座，依變異概率Pm指定變異點；對每一個指定變異點，對其基因位反運算或用其他基因位代替，產(chǎn)生新個體?！?基本位變異A：101oiii01010 :——》A“：1010ioi01010變異點遺傳算法的應(yīng)用步驟第一步：確定決策變量及其約束條件，即確定出個體的表現(xiàn)型X和問題解空間。第二步：建立優(yōu)化模型，即確定出目標函數(shù)的類型(最大？最??？)及其數(shù)學描述形式和量化方法。第三步：確定表示可行解的染色體編碼方法，也即確定出個體的基因型X及遺傳算法的搜索空間。第四步：確定解碼方法，即確定基因型X到個體表現(xiàn)型X的對應(yīng)關(guān)系或轉(zhuǎn)化方法。第五步：確定個體適應(yīng)度的量化評價方法，即確定出由目標函數(shù)f(X)到個體適應(yīng)度F(X)的轉(zhuǎn)換規(guī)則。第六步：設(shè)計遺傳算子，即確定出選擇算子，變異算子，交叉算子的具體操作步驟。第七步：確定遺傳算法的有關(guān)運行參數(shù)，M，T，Pc，Pm?！纠縍osenbrock函數(shù)的全局最大值計算。maxf(xi?孔)=100(工：—工2尸十(1~X\)2舉例： '遺傳算法構(gòu)造過程：第一步：確定決策變量及其約束條件，即確定出個體的表現(xiàn)型X和問題解空間。—2.048W^W2.048 1,2) (2-7)第二步：建立優(yōu)化模型，即確定出目標函數(shù)的類型(最大？最??？)及其數(shù)學描述形式和量化方法。

第三步：確定表示可行解的染色體編碼方法，也即確定出個體的基因型X及遺傳算法的搜索空間。用長度10位的二進制編碼串表示xl,x2,1024個數(shù)表示-2.048到2.048共4096個離散點。例如：基因型X：00001101111101110001第四步：確定解碼方法，即確定基因型X到個體表現(xiàn)型X的對應(yīng)關(guān)系或轉(zhuǎn)化方法。將代碼yi轉(zhuǎn)換為xi的解碼公式:將代碼yi轉(zhuǎn)換為xi的解碼公式:=4.096x1023-2.048（；=1,2）x1=4.096*55/1023-2.048=-1.818;x2=4.096*881/1023-2.048=1.476個體表現(xiàn)型X{-1.818,1.476}第五步：確定個體適應(yīng)度的量化評價方法，即確定出由目標函數(shù)f(X)到個體適應(yīng)度F(X)的轉(zhuǎn)換規(guī)則。max fJ1，乂2)=100—帀)？十(1—列)2目標函數(shù)不為負，F(xiàn)(X)=f(x1,x2)第六步：設(shè)計遺傳算子，即確定出選擇算子，變異算子，交叉算子的具體操作步驟。比例選擇算子，單點交叉算子，基本位變異算子第七步：確定遺傳算法的有關(guān)運行參數(shù)，M，T，Pc，Pm。M=80；T=200；Pc=0.6；Pm=0.001遺傳算法的基本實現(xiàn)技術(shù)3.1.編碼方法遺傳算法對個體編碼實施選擇，交叉，變異，不斷搜索出適應(yīng)度較高的個體，并在群體中增加其數(shù)量，最終尋求近似最優(yōu)解。把一個問題可行解從其解空間轉(zhuǎn)換到遺傳算法所能處理的搜索空間的轉(zhuǎn)換方法就叫編碼。首要問題，關(guān)鍵步驟編碼方法很大程度上決定如何進行群體的遺傳進化運算以及遺傳進化運算的效率。好的編碼方法，使得交叉，變異運算簡單的實現(xiàn)和執(zhí)行。差的編碼方法，使得交叉，變異運算難以實現(xiàn)，產(chǎn)生無效解。影響效率。編碼原則一：有意義積木塊編碼原則；應(yīng)使用能易于產(chǎn)生與所求問題相關(guān)的且具有低階短定義長度模式的編碼方案。模式；指具有某些基因相似性的個體的集合。使用易于生成適應(yīng)度較高的個體的編碼方案。編碼原則二：最小字符集編碼原則：應(yīng)使用能使問題得到自然表示或描述的具有最小編

碼字符集的編碼方案。進制編碼方法某一參數(shù)的取值范圍［Umin,Umax］,用長度1的二進制編碼符號串表示該參數(shù)，產(chǎn)生21不同編碼。編碼精度：―-1解碼公式：工=解碼公式：工=Umin+（若婦2一）?％；：丁罰優(yōu)點：編解碼簡單易行；交叉變異等遺傳操作便于實現(xiàn)；符合最小字符集編碼規(guī)則；便于利用模式定理對算法進行理論分析格雷碼編碼方法二進制編碼為：BKsi…廠山格雷編碼為："只品松i…HSm— *二進制碼到格雷碼轉(zhuǎn)換公式：gi= 十b譏I=m1,m-2,…，1二進制碼到格雷碼轉(zhuǎn)換公式：格雷碼到二進制碼轉(zhuǎn)換公式：a—br+“「—中I，小二…、］遺傳算法中使用格雷碼進行個體編碼的主要原因：任意兩個整數(shù)的差，是對應(yīng)格雷碼的海明距離。遺傳算法局部搜索能力不強，因為：新一代群體的產(chǎn)生主要是依靠上一代群體之間的隨機交叉重組來完成。對于變異操作，個體基因型X的微小差異，產(chǎn)生個體表現(xiàn)型X的相差較大。格雷碼不會。優(yōu)點：提高遺傳算法的局部搜索能力；交叉變異等遺傳操作便于實現(xiàn)；符合最小字符集編碼原則；便于利用模式定理對算法進行理論分析。浮點數(shù)編碼方法二進制編碼存在連續(xù)函數(shù)離散化時的映射誤差；不便于反應(yīng)所求問題的特定知識。每個基因值用某一范圍內(nèi)的一個浮點數(shù)來表示，個體的編碼長度等于其決策變量的個數(shù)。優(yōu)點：表示范圍較大的數(shù)；適合精度較高的遺傳算法；便于較大空間的遺傳搜索；改善

遺傳算法計算復(fù)雜性；符號編碼方法基因值取自一個無數(shù)值含義，而只有代碼含義的符號集。優(yōu)點：符合有意義積木塊編碼原則；便于在遺傳算法中利用所求解問題的專門知識；便于遺傳算法和相關(guān)近似算法的混合使用。多參數(shù)級聯(lián)編碼方法將各個參數(shù)分別以某種編碼方法進行編碼，按一定順序連接在一起，組成了表示全部參數(shù)的個體編碼。每個參數(shù)編碼方式可以不同，上下界可以不同，編碼長度精度可以不同。多參數(shù)交叉編碼方法將各參數(shù)中起主要作用的碼位集中在一起，不易被遺傳算子破壞掉。參數(shù)編碼:bxb"bn…bf。參數(shù)編碼:bxb"bn…bf。21幻2"23…02罰…九1以2宀3…小2^22…仏2?3&23…嘰??*:叭訪2稅…嘰協(xié)級聯(lián):適合于各參數(shù)之間的相互關(guān)系較弱，特別是某一個或少數(shù)幾個參數(shù)起主要作用時的優(yōu)化問題。交叉：適合于各參數(shù)之間的相互關(guān)系較強，各參數(shù)對最優(yōu)解的貢獻相當時的優(yōu)化問題。3.2.適應(yīng)度函數(shù)遺傳算法中，群體的進化過程就是以群體中各個個體的適應(yīng)度為依據(jù)，通過反復(fù)迭代不斷尋求出適應(yīng)度較大的個體，最終得到最優(yōu)解或次優(yōu)解。目標函數(shù)和適應(yīng)度函數(shù)(1)求最大值：(1)求最大值：(2)(2)求最小值：適應(yīng)度尺度變換：各個個體被遺傳到下一代群體中的概率由該個體的適應(yīng)度來確定。為了克服遺傳算法中出現(xiàn)早熟現(xiàn)象(早起收斂)，希望在遺傳算法運行的初期階段，對適應(yīng)度較高的個體進行控制，降低其適應(yīng)度與其他個體適應(yīng)度之間的差異程度，限制其復(fù)制數(shù)量，維護群體多樣性。為了克服算法運行后期階段因為個體平均適應(yīng)度和最佳適應(yīng)度相近而導致的競爭力不強的問題，算法對適應(yīng)度適當放大，擴大個體最佳適應(yīng)度與其他個體適應(yīng)度之間的差異程度，提高個體間的競爭性。定義：在遺傳算法運行的不同階段，對個體的適應(yīng)度進行適當?shù)臄U大或縮小，稱為適應(yīng)度尺度變換。⑴線性尺度變換:F'二材卜'+兀F-原適應(yīng)度度；F-新適應(yīng)度；a,b-系數(shù)條件一：新適應(yīng)度的平均值等于原適應(yīng)度的平均值，F(xiàn)嚀八心；保證群體中適應(yīng)度接近平均適應(yīng)度的個體有期待的數(shù)量被遺傳到下一代。條件二：新的個體最大適應(yīng)度等于原始個體最大適應(yīng)度的指定倍數(shù)FsC為最佳個體的期望復(fù)制數(shù)量，對于M=50?100,—般取C=1.2?2；保證群體中最好新適應(yīng)度新適應(yīng)度原適應(yīng)度圖3-2線性尺度變換的異常情況？乘幕尺度變換:“；k與所求解問題有關(guān)；在算法中需要不斷修正；指數(shù)尺度變換：廠二^口〔迓^)；0決定了選擇的強制性，越小，原適應(yīng)度較高的個體新適應(yīng)度與其他個體的適應(yīng)度相差越大，增加了選擇該個體的強制性。選擇算子(復(fù)制算子)適應(yīng)度較高的個體被遺傳到下一代的概率較大，適應(yīng)度較低的個體被遺傳到下一代的概率較小目的:避免基因缺失，提高全局收斂性和計算效率比例選擇回放式隨機采樣方法，各個個體被選中的概率與個體適應(yīng)度成正比；基于概率，選擇誤差較大；差較大；最優(yōu)保存策略原因:遺傳算法運行過程中，交叉、變異等遺傳操作不斷產(chǎn)生新個體，產(chǎn)生優(yōu)良個體的同時，有時這些操作的隨機性，也可能破壞掉當前群體中適應(yīng)度最好的個體。導致:降低群體的平均適應(yīng)度，算法運行效率，收斂性。使用最優(yōu)保存策略模型，當前群體中適應(yīng)度最高的個體不參與交叉，變異，用它替代掉經(jīng)過交叉變異后的最低適應(yīng)度個體。具體操作過程:找出當前群體中適應(yīng)度最高最低的個體；若當前群體中的最佳個體適應(yīng)度比迄今為止的最好個體適應(yīng)度還高，則替換之；用迄今為止的最高個體適應(yīng)度替換當前群體中的最低個體適應(yīng)度。保證迄今為止得到的最好的適應(yīng)度個體不會被運算破壞，保證收斂性的重要條件。缺點：容易使局部最優(yōu)解不被淘汰，快速擴散，使算法的全局搜索能力不強。要與其他方法配合使用。推廣：保留多個最優(yōu)個體不參加運算，直接復(fù)制 穩(wěn)態(tài)復(fù)制確定式采樣選擇按照一種確定方法采樣選擇具體操作過程：計算各個個體在下一代中的期望生存數(shù)目LN-確定各個個體在下一代群體中的生存?zhèn)€數(shù)；確定下一代總的個體數(shù)M⑶Ni小數(shù)部分降序排列，取前個，加入下一代。無回放隨機選擇(期望值選擇方法)根據(jù)每個個體在下一代中的生存期望值隨機選擇具體操作過程計算每個個體在下一代中生存期望數(shù)目：若一個個體被選中參與交叉，下一代中生存期望減0.5；未選中減1.0生存期望小于0，不在被選中降低一些選擇誤差無回放余數(shù)隨機選擇具體操作過程(1)計算每個個體在下一代中生存期望數(shù)目(2)LV-確定各個個體在下一代群體中的生存?zhèn)€數(shù)；確定下一代總的個體數(shù)

⑶以“作為各個個體新的適應(yīng)度，用比例選擇方法；隨機確定剩下⑶以“M的M丄A」個個體。確保適應(yīng)度比平均適應(yīng)度大的個體一定被復(fù)制。排序選擇原因：前面的方法要求適應(yīng)度非負，要求對負的適應(yīng)度進行處理。排序選擇著眼于個體適應(yīng)度之間的大小關(guān)系，對正負無特別要求。按適應(yīng)度大小排序，基于排序分配被選中的概率。具體操作過程：對所有個體按適應(yīng)度大小排序根據(jù)具體問題，設(shè)計概率分配表，依次分配。用比例選擇方法產(chǎn)生下一代。仍使用隨機選擇，較大選擇誤差。隨機聯(lián)賽選擇基于個體適應(yīng)度大小關(guān)系，只有個體適應(yīng)度之間的比較，無算數(shù)運算，對正負無特別要求。聯(lián)賽規(guī)模：每次進行適應(yīng)度比較的個體數(shù)目，一般N=2具體操作過程;隨機選取N個個體進行適應(yīng)度比較，將適應(yīng)度大的復(fù)制上述重復(fù)M次，得到下一代群體中M個個體3.4.交叉算子目前常用：隨機配對，將群中M個個體以隨機的方式組成LM/2」對。要求：不要太多的破壞優(yōu)良個體，有效地產(chǎn)生一些較好的新個體。單點交叉：(簡單交叉)只隨機設(shè)置一個交叉點，在該點相互交換部分染色體。特點：若鄰接基因座之間關(guān)系能提供較好的個體性狀和較高的個體適應(yīng)度的話，破壞可

能性最小。雙點交叉和多點交叉：設(shè)置兩個交叉點進行部分交換。具體操作過程：(1)相互配對的兩個個體中隨機設(shè)置兩個交叉點。(2)交換兩個交叉點之間的染色體。(2)交換兩個交叉點之間的染色體。工兀工雙點交叉A:J：x；yyyyyyyy B"zyy；xrrxj：x'yyy推廣：多點交叉力：JTST推廣：多點交叉力：JTST;.TJC;XXJCB：yy:yy\yyy! 三點交叉■yyyA'：J7x:yy:XIX\yyy? ; IB\yy\xJ：\yyy?xx.z多點交叉不太使用，容易破壞好的模式均勻交叉：兩個配對個體的每一個基因座以相同的交叉概率進行交換，形成新個體主要操作過程：(1)隨機產(chǎn)生一個屏蔽字y…Wi,1為個體編碼長度⑵Wi=0,A，繼承A第i個基因座的基因值，B'繼承B第i個基因座的基因值⑶Wi=1,A，繼承B第i個基因座的基因值，B'繼承A第i個基因座的基因值x 均勻交叉-Azxyxyxyx,yxy^?yyyyyyyyyyyW—0101010101Bzyxyxyjcyxyjc算術(shù)交叉兩個個體線性組合產(chǎn)生兩個新個體，操作對象一般是浮點數(shù)編碼表示的個體。(X^1=aX；+(1-a)X；例：兩個個體X；'繪，產(chǎn)生的新個體亠II“乞；a可以為常數(shù)(均勻算術(shù)交叉)；可以是變量(非均勻算術(shù)交叉)操作主要過程確定系數(shù)a；根據(jù)公式生成兩個新個體。3.5.變異算子個體染色體編碼串中某些基因座上的基因值用該基因座的其他等位基因替換，形成新個體。二進制編碼個體中，編碼字符集{0,1},變異點上基因值取反。浮點數(shù)編碼個體中，變異點處基因值取[Umin,Umax],變異操作就是隨機取數(shù)替換之。符號編碼個體中，編碼字符集{A,B,C},變異操作就是隨機取不同替換之。交叉運算是產(chǎn)生新個體的主要方法，決定了算法的全局搜索能力；變異運算是輔助方法，決定了算法的局部搜索能力；群體多樣性，防止早熟現(xiàn)象。相輔相成?；疚蛔儺愐宰儺惛怕蔖m隨機指定某一位或幾位，變異。缺點：變異發(fā)生概率較小，作用較慢，較不明顯。均勻變異具體操作過程:依次指定個體編碼中每個基因座為變異點。對每個變異點，以變異概率Pm從基因值取值范圍中取一隨機數(shù)替代之。例：個體x」八廠…4…-,xk為變異點，取值范圍「工…m,產(chǎn)生新個體X=工1…Q…工).…工/；乂；= +廠?(ULx一Sd〉；r為[0,]]符合均勻分布的隨機數(shù)。適合算法運行初期，使搜索點在整個搜索空間自由移動，增加群體多樣性。邊界變異均勻變異的變形例：個體X」d…4xk為變異點，取值范圍：工產(chǎn)生新個,J尤加訐random(0,1)=0體乂 I….廠：…「「…「： HeIt「mdO1)=1：不適合變量取值范圍寬的情況，并且無其他約束條件；適合最優(yōu)解位于或接近于可行解的邊界的問題。非均勻變異原因：均勻變異可以使個體在搜索空間內(nèi)自由移動，但不便于重點搜索。對原有基因做隨機擾動，重點搜索原個體附近的微小區(qū)域。例：個體X」d…4…-,xk為變異點，取值范圍：『2匸爲」，產(chǎn)生新個, \^k+△（￡*匚爲*-vj）,ifrandom?1）=0體X-廠I…』］…丁r■…廠『； 、4一△〔』，琪〔鳥J,ifranJoiiJO,1j-1；表示［0,y