遺傳算法學(xué)習(xí)筆記

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

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

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

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

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

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

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