【正文】 模式定理 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 100 基本遺傳算法 ? 模式 定理（ schema theorem） 在給定時(shí)間步 t ,一個(gè)特定模式 H 有 m 個(gè)代表串包含在種群 A(t) 中，記為 m=m(H,t)，在再生階段，每個(gè)串根據(jù)它的適應(yīng)值進(jìn)行復(fù)制，一個(gè)串 Ai 的再生概率為 模式定理 ??? njjiiffp1智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 101 基本遺傳算法 ? 模式 定理（ schema theorem） 當(dāng)采用非重疊的 n 個(gè)串的種群替代種群 A(t)，可以得到： 其中 f(H) 是在時(shí)間 t ，模式 H 的串的平均適應(yīng)度； 而整個(gè)種群的平均適應(yīng)度為 模式定理 ?????? njjfHfntHmtHm1)(),()1,(fHftHmtHm )(),()1,( ??nffnjj??? 1 ??? njjiiffp1智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 102 基本遺傳算法 模式定理 )0,()1(),()1()(),()1,( HmctHmcf fcftHmtHm t ?????????? 模式 定理（ schema theorem） 假設(shè)從 t=0 開始，某一特定模式適應(yīng)度值保持在種群平均適應(yīng)度以上一個(gè) cf （ c 為一常數(shù)），則模式的選擇生長方程為 在種群平均值以上（以下）的模式將按指數(shù)增長（衰減）的方式復(fù)制。 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 103 基本遺傳算法 ? 模式 定理（ schema theorem） 考慮交叉操作，模式 H 被破壞的概率為 δ(H)/(l1)，模式 H 生存概率為 1 δ(H)/(l1) ，若交叉操作發(fā)生的概率為 pc，因此對于模式 H 的生存概率計(jì)算為： 同時(shí)考慮選擇、交叉操作對模式的影響，可得： 模式定理 1)(1??? lHppcs??????? ????? 1)(1)(),()1,(lHpfHftHmtHmc?H1= * 1 * * * * 0 H2= * * * 1 0 * 0 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 104 基本遺傳算法 ? 模式 定理（ schema theorem） 考慮變異操作，單個(gè)等位基因存活的概率為 1 pm ，當(dāng)模式 H 中 O(H) 個(gè)確定位都存活時(shí)，模式 H 才被保留，存活概率為： 同時(shí)考慮選擇、交叉和變異操作對模式的影響，可得： 模式定理 )1( )(1)1( )( ?????? mmHOm ppHOp?????? ?????? mc pHOlHpfHftHmtHm )(1)(1)(),()1,( ?H1= * 1 * * * * 0 H2= * * * 1 0 * 0 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 105 基本遺傳算法 ? 模式 定理（ schema theorem） 模式定理 ：在遺傳算子選擇、交叉、變異的作用下，具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式在子代中呈指數(shù)增長。 具有低階、短定義距以及平均適應(yīng)度高于種群平均適應(yīng)度的模式被定義為 積木塊 。 模式定理 ?????? ?????? mc pHOlHpfHftHmtHm )(1)(1)(),()1,( ?智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 106 基本遺傳算法 ? 積木塊假設(shè) （ building block hypothesis） 遺傳算法通過短定義距、低階以及高平均適應(yīng)度的模式（積木塊），在遺傳操作作用下相互結(jié)合，最終接近全局最優(yōu)解。 模式定理 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 107 遺傳算法的改進(jìn) CHC算法 自適應(yīng)遺傳算法 基于小生境技術(shù)的遺傳算法 遺傳算法的應(yīng)用 解決帶約束的函數(shù)優(yōu)化問題 解決多目標(biāo)優(yōu)化問題 解決組合優(yōu)化問題 遺傳算法在過程建模中的應(yīng)用 遺傳算法在模式識別中的應(yīng)用 ? 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 108 遺傳算法的改進(jìn) ? 改進(jìn)的途徑 ? 改變遺傳算法的組成成分； ? 采用混合遺傳算法； ? 采用動(dòng)態(tài)自適應(yīng)技術(shù)； ? 采用非標(biāo)準(zhǔn)的遺傳操作算子； ? 采用并行遺傳算法等。 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 109 遺傳算法的改進(jìn) ? 改進(jìn)思路 ? 1991年 Eshelman提出的一種改進(jìn)遺傳算法； ? C：跨世代精英選擇（ Cross generational elitist selection）策略； ? H：異物種重組（ Heterogeneous rebination）； ? C：大變異（ Cataclysmic mutation）。 CHC算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 110 遺傳算法的改進(jìn) ? 選擇（ C：跨世代精英選擇 ） ? 上一代種群與通過新的交叉方法產(chǎn)生的個(gè)體群混合起來，從中按一定概率選擇較優(yōu)的個(gè)體； ? 即使當(dāng)交叉操作產(chǎn)生較劣個(gè)體偏多時(shí)，由于原種群大多數(shù)個(gè)體殘留，不會引起個(gè)體的評價(jià)值降低； ? 可以更好地保持遺傳多樣性； ? 排序方法，克服比例適應(yīng)度計(jì)算的尺度問題。 CHC算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 111 遺傳算法的改進(jìn) ? 交叉（ H：異物種重組 ） ? 均勻交叉的改進(jìn)：當(dāng)兩個(gè)父個(gè)體位值相異的位數(shù)為m時(shí)，從中隨機(jī)選取 m/2個(gè)位置，實(shí)行父個(gè)體位值的交換； ? 確定一閾值，當(dāng)個(gè)體間距離低于該閾值時(shí)，不進(jìn)行交叉操作。進(jìn)化收斂的同時(shí)，逐漸地減小該閾值。 CHC算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 112 遺傳算法的改進(jìn) ? 變異（ C：大變異 ） ? 在進(jìn)化前期不采取變異操作，當(dāng)種群進(jìn)化到一定收斂時(shí)期，從最優(yōu)個(gè)體中選擇一部分個(gè)體進(jìn)行初始化； ? 初始化：選擇一定比例（擴(kuò)散率，一般 ）的基因座，隨機(jī)地決定它們的位值。 CHC算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 113 遺傳算法的改進(jìn) ? 參數(shù)分析 ? 交叉概率 Pc和變異概率 Pm的選擇是影響遺傳算法行為和性能的關(guān)鍵，直接影響算法的收斂性； ? Pc越大，新個(gè)體產(chǎn)生的速度就越快，但過大會使優(yōu)秀個(gè)體的結(jié)構(gòu)很快被破壞； Pc過小，搜索過程緩慢，以至停止不前； ? Pm過小，不易產(chǎn)生新個(gè)體結(jié)構(gòu)， Pm過大，變成純粹的隨機(jī)搜索； 自適應(yīng)遺傳算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 114 遺傳算法的改進(jìn) ? 自適應(yīng)策略 使 Pc和 Pm能夠隨適應(yīng)度自動(dòng)改變： ? 當(dāng)種群各個(gè)體適應(yīng)度趨于一致或趨于局部最優(yōu)時(shí)，使 Pc和 Pm增加；而當(dāng)群體適應(yīng)度比較分散時(shí)，使 Pc和 Pm減少； ? 對于適應(yīng)度較高的個(gè)體，對應(yīng)于較低的 Pc和 Pm ；而較低適應(yīng)度的個(gè)體，對應(yīng)于較高的 Pc和 Pm 。 在保持群體多樣性的同時(shí)，保證遺傳算法收斂性。 自適應(yīng)遺傳算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 115 遺傳算法的改進(jìn) ? 自適應(yīng)方法 fmax——群體中最大的適應(yīng)度值； favg——每代群體的平均適應(yīng)度值； f’——要交叉的兩個(gè)個(gè)體中較大的適應(yīng)度值； f——要交叉或變異的個(gè)體適應(yīng)度值； 自適應(yīng)遺傳算法 ????????????????????a v ga v ga v gma v ga v ga v gcffkffffffkPffkffffffkP ,)( ,)39。(4m a xm a x32m a xm a x1k k k k4 取 (0,1)的值 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 116 遺傳算法的改進(jìn) ? 自適應(yīng)方法進(jìn)一步改進(jìn) ? 適用于進(jìn)化后期，不適于進(jìn)化前期，因?yàn)榍捌诘膬?yōu)秀個(gè)體有可能是局部最優(yōu)點(diǎn)； ? 使最大適應(yīng)度個(gè)體的交叉概率和變異概率由 0提高到 Pc2和 Pm2 ； ? 采用精英選擇策略，將優(yōu)良個(gè)體直接復(fù)制到下一代。 自適應(yīng)遺傳算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 117 遺傳算法的改進(jìn) ? 自適應(yīng)方法進(jìn)一步改進(jìn) 自適應(yīng)遺傳算法 0 0 , , , , ,))((39。 ,39。,)39。)((21211m a x2111m a x211????????????????????????????mmcca v gma v ga v ga v gmmmma v gca v ga v ga v gccccPPPPffPffffffPPPPffPffffffPPPP智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 118 遺傳算法的改進(jìn) ? 小生境概念 ? 小生境（ niche）：生物學(xué)中，特定環(huán)境中的一種組織功能； ? 在 SGA中，容易“近親繁殖”； ? NGA（ Niche Generic Algorithm），將每一代個(gè)體劃分為若干類，每類選出優(yōu)秀個(gè)體組成一個(gè)種群； ? 優(yōu)勢：保持解的多樣性，提高全局搜索能力，適合復(fù)雜多峰函數(shù)的優(yōu)化。 基于小生境技術(shù)的遺傳算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 119 遺傳算法的改進(jìn) ? 選擇策略 ? 預(yù)選擇機(jī)制、排擠機(jī)制、分享機(jī)制； ? 預(yù)選擇（ preselection,1970）機(jī)制 ? 當(dāng)子個(gè)體的適應(yīng)度超過其父個(gè)體適應(yīng)度時(shí)，子個(gè)體才可以替代父個(gè)體，否則父個(gè)體仍保留； ? 有效維持種群多樣性，造就小生境進(jìn)化環(huán)境。 基于小生境技術(shù)的遺傳算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 120 遺傳算法的改進(jìn) ? 排擠（ crowding,1975）機(jī)制 ? 設(shè)置排擠因子 CF（ CF=2或 3），隨機(jī)選取 1/CF個(gè)個(gè)體組成排擠成員，排擠與其相似（用距離來度量）的個(gè)體； ? 個(gè)體之間的相似性可用個(gè)體編碼串之間的海明距離來度量。 基于小生境技術(shù)的遺傳算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 121 遺傳算法的改進(jìn) ? 共享（ sharing,1987）機(jī)制 ? 通過個(gè)體之間的相似性程度的共享函數(shù)來調(diào)整各個(gè)體的適應(yīng)度； ? 共享函數(shù)的目的：將搜索空間的多個(gè)峰值在地理上區(qū)分開來，每一個(gè)峰值處接受一定比例數(shù)目的個(gè)體，比例數(shù)目與峰值高度有關(guān)； 基于小生境技術(shù)的遺傳算法 智能優(yōu)化計(jì)算 華東理工大學(xué)自動(dòng)化系 2022年 122 遺傳算法的改進(jìn) ? 共享（ sharing,1987）機(jī)制 ? 共享函數(shù)的值越大，表明個(gè)體之間越相似，記為S(dij)， dij為兩個(gè)個(gè)體 i和 j之間的距離； σsha