遺傳算法的設(shè)計與實現(xiàn) PPT課件

1 遺傳算法的設(shè)計與實現(xiàn) 湖南大學(xué)軟件學(xué)院歐陽柳波 2 0引言 通過理論分析 我們對遺傳算法有更深入的認識 為解決實際問題提供了很好的指導(dǎo) 但通常情況下 由于實際問題不能滿足理論分析所要求的前提條件 一些理論結(jié)果往往不能直接應(yīng)用于實際問題中 我們需要根據(jù)待解決的問題設(shè)計不同的遺傳算子 選取不同的參數(shù) 從而使算法更有效 在遺傳算法實現(xiàn)上 編碼方法 遺傳算子的選擇 控制參數(shù)的選取等都是十分關(guān)鍵的問題 3 1編碼原則與方法 把優(yōu)化問題的解的參數(shù)形式轉(zhuǎn)換成基因鏈碼的表示形式 這一轉(zhuǎn)換操作就叫做編碼 也可以稱作是問題的表示 representation 一般來講 由于遺傳算法的魯棒性 其對編碼要求并不苛刻 大多數(shù)問題可以采用基于 0 1 符號集的二值編碼形式 編碼的策略或方法對于遺傳操作 尤其是對交叉操作的功能影響很大 因而編碼問題常被稱為編碼 交叉問題 4 1 1編碼原則 1 通過編碼后 問題的解由某種基因鏈碼形式表示 我們稱該基因鏈碼的所有個體構(gòu)成了表達空間 因此編碼問題實際是從問題空間到表達空間的映射問題 個體因一次變異所能遷移到的局部空間叫做變異近鄰 mutationneighborhood 由兩個體進行一次交叉所能遷移到的局部空間叫交叉近鄰 crossoverneighborhood 在GA空間中 由于交叉近鄰是由兩個個體所決定的 所以它比變異近鄰遷移要大些 如果編碼方法和交叉處理不當(dāng) 在遺傳算法中因交叉產(chǎn)生的個體有可能成為無用解或無效解 編碼策略與交叉策略互為依存 恰當(dāng)?shù)卦O(shè)計編碼和交叉策略或方法 對于發(fā)揮遺傳算法的功能十分重要 5 1 1編碼原則 2 設(shè)計編碼策略時 ?？紤]以下3個問題 1 完備性 completeness 對于問題空間中的任一點都有表達空間的一個點與之對應(yīng) 即問題空間的所有可能解都能表示為所設(shè)計的基因鏈碼形式 2 健全性 soundness 對于表達空間中的任一點都有問題空間中的一個點與之對應(yīng) 即任何一個基因鏈碼都對應(yīng)一個可能解 3 非冗余性 non redundancy 問題空間和表達空間一一對應(yīng) 對于一些問題 很難設(shè)計出同時滿足上述3個性質(zhì)的編碼方案 但完備性是必須滿足的一個性質(zhì) 在有些情況下 允許生成無用解 也允許不滿足非冗余性 6 1 1編碼原則 3 為使編碼設(shè)計能有效地提高算法的搜索效率 DeJong提出更為客觀明確的編碼評估準(zhǔn)則 稱之為編碼原理或編碼規(guī)則 1 有意義基因塊編碼規(guī)則 所設(shè)計的編碼方案應(yīng)當(dāng)易于生成與所求問題相關(guān)的短定義距和低階的基因塊 2 最小字符集編碼規(guī)則 所設(shè)計的編碼方案應(yīng)采用最小字符集以使問題得到自然的表示或描述 7 1 1編碼原則 4 前章中求f x x2 x 0 31 函數(shù)極值的例子 其采用的是二進制5位編碼方法 我們也可給出另一種非二值編碼 該編碼建立在32個字符組成的字符集基礎(chǔ)上 其中包括 A Z 共26個字符和 1 6 中的6個數(shù)字 這兩種編碼的部分對應(yīng)關(guān)系如下表1 表1二值編碼和非二值編碼表示的比較 8 1 1編碼原則 5 為什么通常情況下要采用二值編碼方案 1 顯然 在二值編碼情況下 群體碼串的相似性很容易找到 在非二值編碼情況下 碼串的相似性很難觀察到 2 實際上 如果不限制基因鏈碼的長度 可以證明 使用二進制能表達的模式數(shù)最多 根據(jù)模式理論 一個編碼方案應(yīng)該能提供最多的模式 3 二進制編碼方案符合最小字符集的編碼規(guī)則 9 1 1編碼原則 6 旅行商問題 一個有窮的 城市 集合C C1 C2 Cm 對于任意一對城市Ci Cj C 有 距離 d Ci Cj R 要求從某個城市出發(fā)經(jīng)過每個城市一次 且只經(jīng)過一次 找出距離之和最小的路徑 考慮5個城市的旅行商問題 如下圖 給問題的一個可行解 給了出如下兩種編碼表示方法 1 ABCDE 2 PABPACPADPAEPBCPBDPBEPCDPCEPDE 1000100101 編碼 1 只要考慮每個城市僅在基因鏈碼中出現(xiàn)一次即可避免生成無意義的個體 即滿足編碼規(guī)則 1 但不滿足規(guī)則 2 編碼 2 不易滿足規(guī)則 1 而更易滿足規(guī)則 2 顯然這兩個編碼在具體應(yīng)用中具有矛盾性 真正有效的編碼設(shè)計應(yīng)在評估規(guī)范和準(zhǔn)則的基礎(chǔ)上 充分考慮編碼與問題約束條件的關(guān)系 編碼與遺傳操作尤其是交叉操作間的關(guān)系 10 1 2編碼方法 1 一維編碼是指搜索空間的參數(shù)轉(zhuǎn)換到遺傳空間后 其相應(yīng)的基因呈一維排列構(gòu)成基因鏈碼 即表示個體的字符集中的要素構(gòu)成了字符串 1 2 1二進制編碼即將原問題的解映射成為0 1組成的位串 然后在串空間上進行遺傳操作 結(jié)果再通過解碼過程還原其解空間的解 然后再進行適應(yīng)度值的計算 1 二進制編碼的優(yōu)點 能表達的模式數(shù)最多 簡單易行 符合最小字符集編碼原則 便于用模式定理進行分析 11 1 2編碼方法 2 2 二進制編碼的缺點 尤其在求解連續(xù)優(yōu)化問題時 相鄰整數(shù)的二進制編碼具有較大的Hamming距離 如15和16的二進制表示為01111和10000 算法要從15改進到16則必須改變所有的位 這種缺陷降低遺傳算子的效率 這一缺陷有時被稱為Hamming懸崖 HammingCliffs 二進制編碼時 一般要先給出求解的精度 以確定串長 而精度一旦確定后 就很難在算法中進行調(diào)整 從而使算法失去微調(diào)功能 若一開始就選取較高的精度 則位串就很長 這樣會降低算法的較率 求解高維優(yōu)化問題時 二進制編碼位串將非常長 從而使得算法的搜索效率很低 12 1 2編碼方法 3 1 2 2Gray編碼Gray編碼是將二進制編碼通過一個變換而得到的編碼 其目的是克服二進制編碼中的Hamming懸崖的缺點 設(shè)有二進制串b1b2 bn 對應(yīng)的Gray串為a1a2 an 則從二進制編碼到Gray編碼的變換為 其中 表示模2加法 而從一個Gray串到二進制串的變換為 如果i 1如果i 1 如 二進制串1101011對應(yīng)的Gray串為1011110 13 1 2編碼方法 4 1 2 3動態(tài)編碼動態(tài)編碼是當(dāng)算法收斂到某局部極值時增加搜索的精度 增加精度的辦法是在保持串長不變的前提下減少搜索區(qū)域 1 2 4實數(shù)編碼對問題的變量是實向量的情形 可以直接采用十進制進行編碼 這樣便可直接對解進行遺傳操作 從而便于引入與問題領(lǐng)域相關(guān)的啟發(fā)式信息以增加遺傳算法的搜索能力 對于大部分數(shù)值優(yōu)化問題 通常需要針對十進制編碼的特性 引入其他一些專門設(shè)計的遺傳算子 試驗證明 采用實數(shù)編碼比采用二進制編碼的算法平均效率要高 14 1 2編碼方法 5 1 2 5有序串編碼若目標(biāo)函數(shù)的值只與表示解的字符串中各字符的位置有關(guān)而與其具體值無關(guān) 則稱為純排序問題 如前述的5個城市的旅行商問題的第一種編碼方式 一般在組合優(yōu)化問題中使用較多 1 2 6多參數(shù)映射編碼在優(yōu)化問題求解中常會碰到多參數(shù)優(yōu)化問題 如 函數(shù)f x y x2y2 x 0 63 y 0 63 的優(yōu)化中 可如下編碼 x用8位的0 1串表示 y也用8位的0 1串表示 將這兩個串按x在前 y在后的順序連接起來 構(gòu)成16位的0 1串作為基因鏈碼表示 一般來講 多參數(shù)映射編碼中的每一個子串對應(yīng)各自串的編碼參數(shù) 所以可用不同長度的基因鏈碼表示各自的參數(shù) 15 1 2編碼方法 6 1 2 7可變長編碼 1 自然界生物進化過程中 越是高等生物其染色體越長 即染色體的長度不是固定不變的 Goldberg于1991年提出的MessyGA mGA 就融入了這種機制 mGA不同于標(biāo)準(zhǔn)的遺傳算法 它可以較好地克服標(biāo)準(zhǔn)遺傳算法對非線性問題處理的弱點 具有以下特點 染色體長度可變 允許過剩指定和缺省指定 基于切斷和拼接操作的交叉處理 分為二階段處理 即原始階段和并立階段或?qū)与A段 16 1 2編碼方法 7 1 2 7可變長編碼 2 在mGA中 基因的意義和基因位置無關(guān) 而是由成對的符號所決定 如下表中的 a1 b4 c3 可看作是三位長的串 解釋為a的值為1 b的值為4 c的值為3 17 1 2編碼方法 8 1 2 7可變長編碼 3 mGA在做適應(yīng)度計算時需要把以表形式表示的個體轉(zhuǎn)換成規(guī)定長度的字符串形式 要除去多余指定或補足缺省指定 因此在mGA中經(jīng)適應(yīng)度計算后 群體中染色體長度是相等的 但經(jīng)過其特有的交叉操作后 新群體中的染色體長度又可能不相等了 如 父輩1 111 111111 后代1 111 000父輩2 000000 000 后代2 000000 111111 mGA的可變長染色體編碼尤其在求解非線性問題時表現(xiàn)出很好的效果 但是前述的模式定理已不適用于mGA 為此需要再做分析和研究 18 1 2編碼方法 9 1 2 8二維染色體編碼在許多應(yīng)用中 問題的解呈二維或多維表示 此時采用一維編碼很不方便 交叉操作也很不直觀 因而可采用多維編碼 例如圖像恢復(fù)處理 圖像恢復(fù)是指把一個被干擾的圖像恢復(fù)到它的原始面目 顯然圖像恢復(fù)處理所求的解是一個圖像 一個染色體就代表一個圖像 可表示為一個二維的二值數(shù)組 如下圖給出一個8 8的二值圖像編碼 19 1 2編碼方法 10 1 2 8二維染色體編碼二維染色體編碼的交叉操作 父代 子代 模式定理仍然適用 由于圖像的數(shù)據(jù)量很大 用遺傳算法進行圖像恢復(fù)時計算量很大 以32 32的二值圖像為例 此問題相當(dāng)于在32 32 1024維空間中尋優(yōu) 20 2 適應(yīng)度函數(shù) 遺傳算法在優(yōu)化搜索中基本上不用外部信息 僅用適應(yīng)度函數(shù)為尋優(yōu)依據(jù) 遺傳算法對適應(yīng)度函數(shù)的唯一要求是 該函數(shù)不能為負 這使GA應(yīng)用范圍很廣 適應(yīng)度函數(shù)的設(shè)計要根據(jù)待求解問題而定 適應(yīng)度函數(shù)的設(shè)計直接影響GA的性能 在許多問題求解中 其目標(biāo)是求函數(shù)g x 的最小值 而不是最大值 即使某個問題可自然地表示為求最大值形式 但也不能保證對于所有的x g x 都取非負值 由于GA中要對個體的適應(yīng)度進行比較排序并在此基礎(chǔ)上確定選擇概率 所以適應(yīng)度值要取正值 因此將目標(biāo)函數(shù)映射成求最大值形式且函數(shù)值非負的適應(yīng)函數(shù)是必要的 21 2 1目標(biāo)函數(shù)映射成適應(yīng)度函數(shù) GA中 把最小化問題轉(zhuǎn)化為最大化問題 可采用以下方法進行轉(zhuǎn)換 Cmax可以是一個合適的輸入值 也可采用迄今為止進化中g(shù) x 的最大值 或g x 的最大值 如果g x 非負 也可采用f x 1 g x 當(dāng)問題是求g x 的最大值時 適應(yīng)度函數(shù)的非負性可用如下變換得到保證 式中系統(tǒng)Cmin可以是合適的輸入值 或是當(dāng)前一代或前k代中g(shù) x 的最小值 或g x 的最小值 22 2 2適應(yīng)度函數(shù)調(diào)整 在進化初期 群體中會出現(xiàn)異常個體 并占據(jù)很大的比例 若按照輪盤賭策略 這些異常個體競爭力太突出 會控制選擇過程 導(dǎo)致未成熟收斂現(xiàn)象 從而影響算法的全局優(yōu)化性能 對于未成熟收斂現(xiàn)象 應(yīng)設(shè)法降低某些異常個體的競爭力 可以通過縮小相應(yīng)的適應(yīng)度函數(shù)值來實現(xiàn) 有時也需要擴大相應(yīng)的適應(yīng)度函數(shù)值 這種縮放稱作適應(yīng)度調(diào)整 scaling 適應(yīng)度調(diào)整已成為保持進化過程中競爭水平的重要技術(shù)之一 23 2 2適應(yīng)度函數(shù)調(diào)整 2 2 1線性調(diào)整 1 設(shè)原適應(yīng)度函數(shù)為f x 調(diào)整后的適應(yīng)度函數(shù)為f x 則線性調(diào)整可采用下式表示f x af x b式中系統(tǒng)a和b的選擇要滿足兩個條件 原適應(yīng)度平均值要等于調(diào)整后的適應(yīng)度平均值 調(diào)整后適應(yīng)度函數(shù)的最大值f max x 要等于原適應(yīng)度函數(shù)平均值的所指定的倍數(shù) 即f max x Cfavg x 其中C為得到所期待的最優(yōu)個體的復(fù)制數(shù) 實驗表明 對一個不太大的群體而言 C可以在1 2 2 0之間取值 條件 是為了保證每個群體可以產(chǎn)生一個期待的后代 條件 是為了控制原適應(yīng)度最大的個體產(chǎn)生后代的數(shù)目 24 2 2適應(yīng)度函數(shù)調(diào)整 2 2 1線性調(diào)整 2 圖1是正常調(diào)整結(jié)果 其中少數(shù)異常個體的適應(yīng)度被縮小 同時數(shù)量不多的個體適應(yīng)度被擴大 圖2中壞個體的適應(yīng)度值遠小于平均適應(yīng)度值和最大適應(yīng)度值 且favg x 和fmax x 又比較接近 當(dāng)采用線性調(diào)整欲把favg x 和fmax x 拉開時 原來低適應(yīng)度值經(jīng)調(diào)整后變成了負值 可通過把fmin x 映射到調(diào)整后的適應(yīng)度最小值f min x 且使f min x 0來解決 圖1正常調(diào)整的結(jié)果 圖2不合理的調(diào)整 25 2 2適應(yīng)度函數(shù)調(diào)整 2 2 2冪調(diào)整該調(diào)整方法可定義為 f x fk x 式中指數(shù)k與待求解問題有關(guān) 而且在算法過程中可按需要做修正 該調(diào)整方法由Gillies提出 他曾在機器視覺實驗中采用了該方法 當(dāng)時 他取k 1 005 26 2 3適應(yīng)度函數(shù)設(shè)計對GA的影響 適應(yīng)度函數(shù)的設(shè)計與GA中的選擇操作直接相關(guān) 同時也在其他方面有影響 1 適應(yīng)度函數(shù)影響遺傳算法的迭代停止條件嚴格地說 遺傳算法的迭代停止條件尚無定論 但一般以發(fā)現(xiàn)滿足最大值或次優(yōu)解作為GA迭代停止條件 但一般適應(yīng)度最大值或次優(yōu)解適應(yīng)度下限也很難確定 所以在許多應(yīng)用中 若發(fā)現(xiàn)群體個體進化已趨于穩(wěn)定狀態(tài) 即 當(dāng)發(fā)現(xiàn)群體一定比例的個體已完全是同一個體 則終止算法迭代 27 2 3適應(yīng)度函數(shù)設(shè)計對GA的影響 2 適應(yīng)度函數(shù)與問題約束條件遺傳算法由于僅靠適應(yīng)度來評估和引導(dǎo)搜索 所以求解問題所固有的約束條件不能明確表示出來 我們可以考慮在進化過程中 每迭代一次就設(shè)法檢測新個體是否違背了約束條件 若不滿足 則刪除 但并方法效率不高 而且有時尋找一個有效個體的難度不亞于尋找最優(yōu)個體 可采取一種懲罰方法 并將此懲罰體現(xiàn)在適應(yīng)度函數(shù)中 這樣一個帶約束的優(yōu)化問題就轉(zhuǎn)換為一個附帶考慮代價或懲罰的非約束優(yōu)化問題 28 2 3適應(yīng)度函數(shù)設(shè)計對GA的影響 例如 一個帶約束最小化問題可描述如下 ming x 約束條件 bi x 0 i 1 n上述問題可這樣轉(zhuǎn)化為非約束問題 其中 x 為懲罰函數(shù) r為懲罰系數(shù) 29 3 遺傳算子 選擇算子交叉算子變異算子 30 3 1選擇算子 1 3 1 1適應(yīng)度比例方法這是目前最基礎(chǔ)也是最常用的選擇方法 它也叫輪盤賭選擇方法 即每個個體的選擇概率和其適應(yīng)度值成比例 設(shè)群體大小為n 其中個體的適應(yīng)度值為f 則被選擇的概率Psi為 個體的適應(yīng)度值越大 它選擇的機會就越多 31 3 1選擇算子 2 下表給出了采用適應(yīng)度比例方法的適應(yīng)度值與選擇概率的例子 這里適應(yīng)度函數(shù)采用冪調(diào)整方法 k 2 當(dāng)個體被選中后 可隨機地組成配對 供后面的交叉操作使用 32 3 1選擇算子 3 3 1 2最佳個體保存方法該方法的思想是把群體中適應(yīng)度值最高的個體不進行配對交叉而直接復(fù)制到下一代中 該方法的優(yōu)點是 進化過程中某一代的最優(yōu)解可不被交叉或變異操作破壞 但也隱含危機 即局部最優(yōu)個體的遺傳基因會急速增加而造成進化陷于局部解 也就是說 該方法的全局搜索能力差 它適合于單峰性質(zhì)的優(yōu)化問題的空間搜索 而不適于多峰性質(zhì)的空間搜索 該方法一般與其他方法結(jié)合使用 33 3 1選擇算子 4 3 1 3期望值方法在輪盤賭選擇方法中 當(dāng)個體數(shù)不太多時 依據(jù)產(chǎn)生的隨機數(shù)有可能出現(xiàn)較大的選擇誤差 也就是說 適應(yīng)度高的個體有可能被淘汰 適應(yīng)度低的個體也有可能被選擇 采用期望值方法可解決這個問題 期望值方法思想如下 計算群體中每個個體在下一代生存的期望數(shù)目 若某個個體被選中并要參與配對和交叉 則下一代中的生存的期望數(shù)目減去0 5 若不參與配對和交叉 則該個體的期望數(shù)目減1 在 的兩種情況中 若一個個體的期望值小于1 則該個體不參與選擇 DeJong曾對比了上述三種方法 實驗表明 采用期望值方法的性能優(yōu)于其他兩種方法 34 3 1選擇算子 5 3 1 4排序選擇方法是指根據(jù)適應(yīng)度值大小在群體中對個體排序 然后把事先設(shè)定好的概率表按順序分配給個體 作為各自的選擇概率 選擇概率僅與序號有關(guān)與適應(yīng)度值無直接關(guān)系 選擇概率和序號的關(guān)系需事先確定 基于概率的選擇 仍存在統(tǒng)計誤差 右表給出了一個例子 35 3 1選擇算子 6 3 1 5聯(lián)賽選擇方法類似體育中的比賽制度 其思想是 從群體中任意選擇一定數(shù)目的個體 稱為聯(lián)賽規(guī)模 其中適應(yīng)度最高的個體保存到下一代 這一過程反復(fù)執(zhí)行 直到保存到下一代的個體數(shù)達到預(yù)先設(shè)定的數(shù)目為止 聯(lián)賽規(guī)模一般取2 以上幾種選擇方法 對于遺傳算法的性能的影響各不相同 在具體使用這些方法時 應(yīng)根據(jù)問題求解的特點選擇一種方法 或者是把它們結(jié)合使用 當(dāng)然在有些情況下 需要尋找新的方法 36 3 2交叉算子 1 3 2 1單點交叉又叫簡單交叉 具體操作是 在個體基因串中隨機設(shè)定一個交叉點 交叉操作時 該點前或后的兩個個體的部分結(jié)構(gòu)進行互換 并生成兩個新個體 如前例中函數(shù)f x x2優(yōu)化中的交叉方法就是單點交叉 當(dāng)基因鏈碼的長度為n時 可能有n 1個交叉點位置 3 2 2兩點交叉與單點交叉類似 只是隨機設(shè)置2個交叉點 父輩兩個個體在兩個交叉點之間的基因鏈碼相互交換 生成新個體 如下例 父輩個體1 aaa aaa aaa aaa bbb aaa父輩個體2 bbb bbb bbb bbb aaa bbb對于兩點交叉而言 若染色體長度為n 則可能有 n 1 n 2 2種交叉點的位置 37 3 2交叉算子 2 3 2 3多點交叉又稱為廣義交叉 若用參數(shù)c表示交叉數(shù) 則當(dāng)c 1時 廣義交叉就是單點交叉 c 2時 廣義交叉就是兩點交叉 多點交叉不常被采用 因為當(dāng)基因鏈碼的長度n較小 或交叉點數(shù)c較大時 即使模式的階和定義矩較小 具有優(yōu)良特性的模式也很容易被破壞 另外出于計算速度的考慮 基因鏈碼的長度n不會很長 38 3 2交叉算子 3 3 2 3均勻交叉均勻交叉是依概率交換兩個父輩個體基因串中的每一位 其過程是 先隨機地產(chǎn)生一個與父輩個體基因串具有相同長度的二進制串 其中0表示不交換 1表示交換 這個二進制串稱為交叉模板 然后根據(jù)該模板對兩個父輩基因串進行交叉 得到的兩個新基因串即為后代新個體 例如 父輩個體1 110010111000父輩個體2 101011101011交叉模板 001101011100后代個體1 111011101000后代個體2 100010111011由于均勻交叉在交換位時不考慮其所在位置 破壞模式的概率較大 但另一方面 它能搜索到一些前面基于點的交叉方法無法搜索到的模式 39 3 2交叉算子 4 在很多應(yīng)用中 交叉算子是以一定概率實現(xiàn)的 這一概率稱為交叉概率 前幾種交叉方法 只是最基本的方法 解決實際問題時 由于問題的特殊性和編碼方式不同 交叉算子也會有不同 交叉算子未提供算法向最優(yōu)解收斂的保證 模式定理只是考慮到選擇算子可以維持模式 而交叉算子和變異算子會破壞模式 但這并不影響遺傳算法的實用性 許多具有向最優(yōu)解收斂的算法卻犧牲了它們的全局性和靈活性 因此不少很難求解的優(yōu)化問題 對于基于交叉的遺傳算法而言卻是簡單可解的 交叉算子對遺傳算法收斂性的影響是遺傳算法研究中的重要課題之一 40 3 3變異算子 1 變異操作就是把某些基因位置上的基因值取反 即1 0 或0 1 一般來說 變異操作的基本步驟如下 在群體中所有個體的碼串范圍內(nèi)隨機地確定基因位置 以事先設(shè)定的變異概率Pm來對這些基因位置的基因值進行變異 GA中 交叉算子以其全局搜索能力而作為主要算子 變異算子因局部搜索能力而作為輔助算子 它們相互配合又相互競爭的操作 使GA具備兼顧全局和局部的均衡搜索能力 所謂相互配合 是指當(dāng)群體在進化中陷于搜索空間中某個超平面而僅靠交叉不能擺脫時 通過變異操作可有助于這種擺脫 所謂相互競爭 是指當(dāng)通過交叉已形成所期望的基因塊時 變異操作可能破壞這些基因塊 如何有效地配合使用交叉和變異操作 是目前GA的一個重要研究內(nèi)容 41 3 3變異算子 2 3 3 1基本變異算子針對二值基因鏈碼而言 對群體中基因鏈碼隨機挑選c個基因位置 對這些基因位置的基因值以概率Pm取反 即1 0 或0 1 當(dāng)c 1時 就如前例中函數(shù)f x x2的最優(yōu)求解中的變異方法 3 3 2均勻變異該變異方法針對實數(shù)編碼方式 設(shè)V v1 v2 vm 是群體的一個個體 Z z1 z2 zm 是變異產(chǎn)生的后代 在個體V中隨機地選擇一個分量vk 然后在一個定義的區(qū)間 ak bk 中均勻隨機地取一個數(shù)vk 代替vk 得到Z 即Z v1 vk vm 42 3 3變異算子 3 3 3 3正態(tài)變異與均勻變異略有不同 首先在個體V中隨機地選擇一個分量vk 然后不是在一個定義的區(qū)間 ak bk 中均勻隨機地取一個數(shù)vk 代替vk 而是選擇的vk 是服從N vk 2 正態(tài)分布的 3 3 4非一致變異將變異算子與進化代數(shù)聯(lián)系起來 使得在進化的初期 變異的范圍相對較大 隨著進化的推進 變異的范圍越來越小 此時 變異算子起著進化微調(diào)的作用 如 在個體V中隨機地選擇一個分量vk 對vk變異后的結(jié)果vk 服從N vk 2 t 正態(tài)分布 這里t是進化的代數(shù) 2 t 隨著t的增大而趨于0 當(dāng)然 2 t 的不同會導(dǎo)致略微不同的算法 43 3 3變異算子 4 3 3 5自適應(yīng)性變異非一致性變異加強了算法的局部搜索 但其變異范圍只與進化代數(shù)有關(guān) 而與個體性能無關(guān) 即無論解的質(zhì)量好壞 其變異的范圍都是相同的 我們可采用一種方法使適應(yīng)度大的個體在較小的范圍內(nèi)變異 而適應(yīng)度小的個體在較大的范圍內(nèi)變異 因而引入變異溫度的概念 類似于模擬退火中溫度的概念 解的變異溫度定義為 T 1 f s fmax 其中f s 表示個體s的適應(yīng)度 fmax是待求解問題的最大適應(yīng)度值 對于很多問題 fmax很難確定 只要給出一個粗略的上限即可 也可以使用當(dāng)前群體中的最大適應(yīng)度值作為fmax 在個體V中隨機地選擇一個分量vk 對vk變異后的結(jié)果vk 服從N vk 2 T 正態(tài)分布 這里T是變異溫度 2 T 應(yīng)該隨著