2遺傳算法(3).ppt

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