2遺傳算法(3).ppt

河北大學(xué) 吳彬 wubinbb 1 2遺傳算法 3 遺傳算法技術(shù)介紹 河北大學(xué) 2 吳彬 wubinbb 2 5連續(xù)性遺傳算法 實(shí)數(shù)編碼 河北大學(xué) 3 吳彬 wubinbb 二進(jìn)制數(shù)編碼的不足 100個(gè)變量 250 250 精度0 00001100 26 2600長(zhǎng)的二進(jìn)制串表示染色體 此時(shí)的遺傳算法的搜索空間大約為22600 河北大學(xué) 4 吳彬 wubinbb 實(shí)數(shù)編碼的優(yōu)越性 適合于在遺傳算法中表示范圍較大的數(shù) 適合于精度要求較高的問(wèn)題 便于與經(jīng)典優(yōu)化方法混合使用 便于處理含約束條件的問(wèn)題 河北大學(xué) 5 吳彬 wubinbb 設(shè)計(jì)遺傳算法須注意問(wèn)題 適應(yīng)度 復(fù)制 不依賴于問(wèn)題的編碼方法 選擇 變異 運(yùn)行后要保證個(gè)體在約束范圍內(nèi) 一些參數(shù) 本質(zhì)上都可以使得它隨著遺傳代數(shù)的不同而變化 河北大學(xué) 6 吳彬 wubinbb 2 5連續(xù)性遺傳算法 適應(yīng)度線性變換Ranking適應(yīng)度分配復(fù)制比例選擇法 輪盤選擇 隨機(jī)一致選擇競(jìng)技選擇法交換線性交換中間交換啟發(fā)式交換突變均勻變異非均勻變異 河北大學(xué) 7 吳彬 wubinbb 約束條件的處理 懲罰策略 懲罰技術(shù)是遺傳算法解約束優(yōu)化問(wèn)題中最常用的技術(shù) 本質(zhì)上它是通過(guò)懲罰不可行解將約束問(wèn)題轉(zhuǎn)化為無(wú)約束問(wèn)題 河北大學(xué) 8 吳彬 wubinbb 約束條件的處理 懲罰策略 河北大學(xué) 9 吳彬 wubinbb 約束條件的處理 懲罰策略 河北大學(xué) 10 吳彬 wubinbb 約束條件的處理 懲罰策略 懲罰策略的主要問(wèn)題是如何設(shè)計(jì)一個(gè)懲罰函數(shù) 從而能有效地引導(dǎo)遺傳搜索達(dá)到解空間的最好區(qū)域 河北大學(xué) 11 吳彬 wubinbb 約束條件的處理 懲罰策略 懲罰項(xiàng)的評(píng)估函數(shù)加法形式對(duì)于極大化問(wèn)題 取 河北大學(xué) 12 吳彬 wubinbb 約束條件的處理 懲罰策略 懲罰項(xiàng)的評(píng)估函數(shù)乘法形式對(duì)于極大化問(wèn)題 取 河北大學(xué) 13 吳彬 wubinbb 約束條件的處理 懲罰策略 懲罰項(xiàng)的評(píng)估函數(shù)不帶參數(shù)的懲罰項(xiàng)帶參數(shù)的懲罰項(xiàng)帶參數(shù)的懲罰策略主要用于在遺傳算法運(yùn)行的不同階段懲罰項(xiàng)對(duì)目標(biāo)函數(shù)的懲罰的大小不同 一般來(lái)說(shuō) 希望初期懲罰小些 后期懲罰大些 河北大學(xué) 14 吳彬 wubinbb 約束條件的處理 懲罰策略 不帶參數(shù)的懲罰項(xiàng) 河北大學(xué) 15 吳彬 wubinbb 約束條件的處理 懲罰策略 帶參數(shù)的懲罰項(xiàng) 河北大學(xué) 16 吳彬 wubinbb 約束條件的處理 懲罰策略 初期懲罰小后期懲罰大 河北大學(xué) 17 吳彬 wubinbb 謝謝 參考文獻(xiàn)GEATbx Intro Algorithmen v33a 河北大學(xué) 18 吳彬 wubinbb 后面是細(xì)節(jié) 前面的ppt是后面的一個(gè)綱要后面的ppt是前面綱要的細(xì)節(jié) 河北大學(xué) 19 吳彬 wubinbb 線性交換 需要注意 防止染色體超出約束范圍 河北大學(xué) 20 吳彬 wubinbb 線性交換 河北大學(xué) 21 吳彬 wubinbb 中間交換 需要注意 防止染色體超出約束范圍 河北大學(xué) 22 吳彬 wubinbb 中間交換 河北大學(xué) 23 吳彬 wubinbb 啟發(fā)式交換 r為 0 1 間隨機(jī)數(shù)不比差 即對(duì)最大值問(wèn)題特點(diǎn)使用了目標(biāo)函數(shù)值以確定搜索方向 只生成一個(gè)后代它可能根本不產(chǎn)生解 河北大學(xué) 24 吳彬 wubinbb 啟發(fā)式交換 此算子有可能產(chǎn)生不可行解 此時(shí)產(chǎn)生另一個(gè)隨機(jī)數(shù)r以及另一個(gè)后代 如果嘗試w此后仍失敗 算子終止 河北大學(xué) 25 吳彬 wubinbb 啟發(fā)式交換 主要作用微調(diào)朝一個(gè)最有希望的方向搜索 河北大學(xué) 26 吳彬 wubinbb 均勻變異 河北大學(xué) 27 吳彬 wubinbb 均勻變異 依次指定個(gè)體編碼串中的每個(gè)基因座為變異點(diǎn) 對(duì)每一個(gè)變異點(diǎn) 以變異概率pm從對(duì)應(yīng)基因取值范圍內(nèi)取一隨機(jī)數(shù)來(lái)替代原有基因值 河北大學(xué) 28 吳彬 wubinbb 非均勻變異 河北大學(xué)