【正文】 率 Pm， Pm通常較小，約為 ～ 。也就是說， 1000個字符中有 1～ 10個發(fā)生突變。然后，針對每個字符在 [ 0， 1 ]之間產(chǎn)生三位有效數(shù)的均勻分布隨機數(shù)。若 Pm = ，凡是隨機數(shù)小于 ，將實現(xiàn)突變。示例如下： （ 5） 突變 55 表中有三個字符長度為 4的舊個體。對應(yīng)每個字符，依次產(chǎn)生 [ 0， 1 ]區(qū)間均勻分布的隨機數(shù) 12個。表中只有 2號個體的第 3個字符以及 3號個體的第 4個字符需要發(fā)生突變，因為它們對應(yīng)的隨機數(shù)小于 。 序號 舊個體 隨機數(shù) 新字符 新個體 1 2 3 1010 1100 0010 1 1 1010 1110 0011 （ 5） 突變 56 隨機確定突變的位置后，執(zhí)行突變的方法有兩種。一種是直接產(chǎn)生突變，將表中的 2號和 3號舊個體分別改寫作 1110及 0011。 另一種方法，按 50%的概率隨機產(chǎn)生新字符 0或 1。表中 2號個體產(chǎn)生的新字符為 0，與需要突變的第三行字符恰好一樣，因此新個體等同于舊個體。表中 3號個體產(chǎn)生的新字符（ 1）不同于待突變的原來字符（ 0），因此新個體不同于舊個體。很明顯，后一種突變方法的突變概率僅為前一種方法的 50%。通常建議采用后一種方法，增加突變的隨機性。 序號 舊個體 隨機數(shù) 新字符 新個體 1 2 3 1010 1100 0010 0 1 1010 1100 0011 （ 5） 突變 57 還有一種執(zhí)行突變的方法，是根據(jù)給定的概率 Pm1。隨機選擇突變的個體。當(dāng)被突變的個體選中后，在字長范圍內(nèi)用均勻分布的隨機數(shù)選擇突變的字符，使該個體發(fā)生突變。然而，這時的概率 Pm1 ，不同于突變概率 Pm，后者是針對字符而言，前者是針對個體。遺傳算法中討論的正是字符的突變概率 Pm，兩者間的關(guān)系與字長 L有關(guān)。 盡管突變和交換都能產(chǎn)生新個體，但是在遺傳算法中，交換的作用遠(yuǎn)比突變重要。 （ 5） 突變 58 遺傳算法是一種反復(fù)迭代的搜索方法，它通過多次進(jìn)化逐漸逼近最優(yōu)解而不是恰好等于最優(yōu)解，因此需要確定終止條件。 其一 , 最常用的終止方法是規(guī)定遺傳（迭代）的代次。剛開始時，迭代次數(shù)小一些，如規(guī)定 100次。然后視情況逐漸增加次數(shù)，可達(dá)到上千次。 （ 6） 終止條件 59 當(dāng)目標(biāo)函數(shù)是方差這一類有最優(yōu)目標(biāo)值的問題時，可采用控制偏差的方法實現(xiàn)終止。一旦遺傳算法得出的目標(biāo)函數(shù)值（適應(yīng)度）與實際目標(biāo)值之差小于允許值后，算法終止，即： f(x) ： 遺傳算法得出的目標(biāo)函數(shù)值。 f * ：實際目標(biāo)值。 △ ：足夠小的數(shù)。 | f(x) – f * | ≤△ （ 6） 終止條件 60 第三種終止方法是檢查適應(yīng)度的變化。在遺傳算法后期，一旦最優(yōu)個體的適應(yīng)度沒有變化或變化很小時，即令計算終止。 遺傳算法的另一個重要參數(shù)是每代群體中的個體數(shù)。很明顯，個體數(shù)目越多，搜索范圍越廣，容易獲取全局最優(yōu)解。然而個體數(shù)目太多，每次迭代時間也長。通常，個體數(shù)目可取 1001000之間。 （ 6） 終止條件 7 遺傳算法的應(yīng)用領(lǐng)域 （ 1） 函數(shù)優(yōu)化 。 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域 ， 也是遺傳算法進(jìn)行性能評價的常用算例 。 尤其是對非線性 、多模型 、 多目標(biāo)的函數(shù)優(yōu)化問題 ，采用其他優(yōu)化方法較難求解 ， 而遺傳算法卻可以得到較好的結(jié)果 。 （ 2） 組合優(yōu)化 。 隨著問題的增大 ， 組合優(yōu)化問題的搜索空間也急劇擴大 ， 采用傳統(tǒng)的優(yōu)化方法很難得到最優(yōu)解 。 遺傳算法是尋求這種滿意解的最佳工具 。例如 ， 遺傳算法已經(jīng)在求解旅行商問題 、 背包問題 、 裝箱問題 、 圖形劃分問題等方面得到成功的應(yīng)用 。 （ 3） 生產(chǎn)調(diào)度問題 在很多情況下 ， 采用建立數(shù)學(xué)模型的方法難以對生產(chǎn)調(diào)度問題進(jìn)行精確求解 。 在現(xiàn)實生產(chǎn)中多采用一些經(jīng)驗進(jìn)行調(diào)度 。 遺傳算法是解決復(fù)雜調(diào)度問題的有效工具 ，在單件生產(chǎn)車間調(diào)度 、 流水線生產(chǎn)車間調(diào)度 、 生產(chǎn)規(guī)劃 、 任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用 。 （ 4） 自動控制 。 在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解 ， 遺傳算法已經(jīng)在其中得到了初步的應(yīng)用 。 例如 ， 利用遺傳算法進(jìn)行控制器參數(shù)的優(yōu)化 、 基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí) 、 基于遺傳算法的參數(shù)辨識 、 基于遺傳算法的神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的優(yōu)化和權(quán)值學(xué)習(xí)等 。 （ 5）機器人 例如，遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用。 （ 6） 圖像處理 遺傳算法可用于圖像處理過程中的掃描 、 特征提取 、 圖像分割等的優(yōu)化計算 。 目前遺傳算法已經(jīng)在模式識別 、 圖像恢復(fù) 、 圖像邊緣特征提取等方面得到了應(yīng)用 。 利用遺傳算法求 Rosenbrock函數(shù)的極大值 8 遺傳算法應(yīng)用 求函數(shù)極值 ???????????)2,1()1()(100),( 21222121ixxxxxxfi 用長度為 10位的二進(jìn)制編碼串來分別表示兩個變量x1,x2。 10位二進(jìn)制編碼串可以表示從 0到 1023之間的 1024個不同的數(shù) ， 故將 x1,x2的定義域離散化為 1023個均等的區(qū)域 ， 包括兩個端點在內(nèi)共有 1024個不同的離散點 。 從離散點 到離散點 ， 分別對應(yīng)于從0000000000(0)到 1111111111(1023)之間的二進(jìn)制編碼 。 編碼 將 x1,x2分別表示的兩個 10位長的二進(jìn)制編碼串連接在一起，組成一個 20位長的二進(jìn)制編碼串，它就構(gòu)成了這個函數(shù)優(yōu)化問題的染色體編碼方法。使用這種編碼方法，解空間和遺傳算法的搜索空間就具有一一對應(yīng)的關(guān)系。 例如： 表示一個個體的基因型，其中前 10位表示 x1，后 10位表示 x2。 110 11100 01 000 01101 11:x確定解碼方法：解碼時需要將 20位長的二進(jìn)制編碼串切斷為兩個 10位長的二進(jìn)制編碼串 ， 然后分別將它們轉(zhuǎn)換為對應(yīng)的十進(jìn)制整數(shù)代碼 ， 分別記為 y1和 y2。 依據(jù)個體編碼方法和對定義域的離散化方法可知 ， 將代碼 y轉(zhuǎn)換為變量 x的解碼公式為 例如 ， 對個體 )2,1( ???? iyx ii110 11100 01 000 01101 11:x 它由兩個代碼所組成 上述兩個代碼經(jīng)過解碼后，可得到兩個實際的值 確定個體評價方法：由于 Rosenbrock函數(shù)的值域總是非負(fù)的，并且優(yōu)化目標(biāo)是求函數(shù)的最大值，故可將個體的適應(yīng)度直接取為對應(yīng)的目標(biāo)函數(shù)值，即 , 21 ??? xx 881,55 21 ?? yy ),()(21 xxfxF ?(88 1)1101 1100 01(55 ) 0000 1101 11選個體適應(yīng)度的倒數(shù)作為目標(biāo)函數(shù) 設(shè)計遺傳算子：選擇運算使用比例選擇算子 ， 交叉運算使用單點交叉算子 ， 變異運算使用基本位變異算子 。 確定遺傳算法的運行參數(shù)：群體大小 M=80， 終止進(jìn)化代數(shù)G=100， 交叉概率 Pc=， 變異概率 Pm=。 )(1)(xFxJ ? 采用上述方法進(jìn)行仿真 ， 經(jīng)過 200步迭代 ， 當(dāng) 時 ， Rosenbrock函數(shù)具有極大值 ， 極大值為 。 438 440 21 ???? ,xx演講完畢，謝謝觀看！