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

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