[計算機]ch9現代數據挖掘技術--遺傳算法(編輯修改稿)
2024-11-15 03:41 本頁面
【文章內容簡介】 叉算子 又稱重組、配對算子。交叉分兩步，首先按照一定的方法，隨機地從交配池中取出要交配的一對染色體，然后進行交叉，產生一對新的位串。交叉的方法是，先根據位串長度 L，隨機產生一個交叉位置，即 [1， L1]上的一個整數，然后進行交叉。 例如： A1=1100|10， A2=1010|01， “ |”表示交叉位置，則交叉后得： ? 遺傳算法是有效性主要來自選擇和交叉操作，尤其是交叉，在遺傳算法中起著核心作用。 1 1 0 0 0 11 ??A 1 0 1 0 1 02 ??A? 選擇和交叉算子基本上完成了遺傳算法的大部分搜索功能，而 變異 則增加了遺傳算法找到接近最優(yōu)解的能力。變異就是以很小的概率，隨機改變字符串某個位置上的值。在二進制編碼中，就是將 0變成 1，將 1變成 0。變異與選擇、交叉算子結合在一起，就能避免由選擇和交叉算子引起的某些信息的永久性丟失，從而保證了遺傳算法的有效性。變異發(fā)生的概率極低，一般取值在 ～ 。 ? 在變異操作中，變異率 Pm對遺傳算法的性能有較大的影響，為了提高遺傳算法的性能，在算法是運行過程中，動態(tài)改變變異率 Pm，即根據個體的適應值決定個體的變異率 Pm。對于適應值高的個體，取較小的變異率；而對于適應值低的個體，取較大的變異率。 ? 遺傳算法是一種反復迭代的搜索算法，它通過多次進化逐漸逼近最優(yōu)解，因此需要確定停機條件。 ? 最常用的停機條件是規(guī)定遺傳的代數，即迭代次數。 ? 當遺傳算法是用來產生新的規(guī)則時，停機條件不能簡單地用遺傳代數確定。一次學習過程的結束是當目前工作規(guī)則已收斂，停機條件應該定義為：子代種群的規(guī)則與其父代完全相同，并且各規(guī)則的適應值已連續(xù) M次保持不變。也就是說，當前工作種群已不再進化了。其中，M是根據不同的應用情況事先設置的一個參數。 ? 停機條件 ： ?代數計數器初始化： t← 0； ?產生初始種群； ?評價群體 P(t)的適應值； ?根據當前群體的每個個體的適應值進行選擇生成中間群體 P1(t)； ?個體交叉 (重組 )操作： P2(t) ←crossover[ P1(t)] ； ?個體變異操作： P3(t) ←mutation[ P2(t)] ； ?評價群體 P3(t)的適應值； ?終止條件判斷，若不滿足終止條件，則： t← t+1， 轉向第 3步，繼續(xù)進行遺傳操作過程； 若滿足終止條件，則：輸出當前最優(yōu)個體，算法結束。 問題：求解 在 [0， 31] 上的最大值。 1）編碼：用 5位二進制表示 x，有 x=0 即 00000 x=31 即 11111
教學課件相關推薦
鄂ICP備17016276號-1