【正文】 )(1)(xFxJ ? 采用上述方法進(jìn)行仿真 ， 經(jīng)過 200步迭代 ， 當(dāng) 時(shí) ， Rosenbrock函數(shù)具有極大值 ， 極大值為 。 例如： 表示一個(gè)個(gè)體的基因型，其中前 10位表示 x1，后 10位表示 x2。 10位二進(jìn)制編碼串可以表示從 0到 1023之間的 1024個(gè)不同的數(shù) ， 故將 x1,x2的定義域離散化為 1023個(gè)均等的區(qū)域 ， 包括兩個(gè)端點(diǎn)在內(nèi)共有 1024個(gè)不同的離散點(diǎn) 。 （ 5）機(jī)器人 例如，遺傳算法已經(jīng)在移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、機(jī)器人結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用。 遺傳算法是解決復(fù)雜調(diào)度問題的有效工具 ，在單件生產(chǎn)車間調(diào)度 、 流水線生產(chǎn)車間調(diào)度 、 生產(chǎn)規(guī)劃 、 任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用 。 遺傳算法是尋求這種滿意解的最佳工具 。 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域 ， 也是遺傳算法進(jìn)行性能評價(jià)的常用算例 。很明顯，個(gè)體數(shù)目越多，搜索范圍越廣，容易獲取全局最優(yōu)解。 △ ：足夠小的數(shù)。然后視情況逐漸增加次數(shù)，可達(dá)到上千次。 盡管突變和交換都能產(chǎn)生新個(gè)體，但是在遺傳算法中，交換的作用遠(yuǎn)比突變重要。隨機(jī)選擇突變的個(gè)體。表中 3號個(gè)體產(chǎn)生的新字符（ 1）不同于待突變的原來字符（ 0），因此新個(gè)體不同于舊個(gè)體。 序號 舊個(gè)體 隨機(jī)數(shù) 新字符 新個(gè)體 1 2 3 1010 1100 0010 1 1 1010 1110 0011 （ 5） 突變 56 隨機(jī)確定突變的位置后，執(zhí)行突變的方法有兩種。若 Pm = ，凡是隨機(jī)數(shù)小于 ，將實(shí)現(xiàn)突變。 突變個(gè)體的選擇以及突變位置的確定，都是采用隨機(jī)的方法產(chǎn)生。正是有了交換操作，群體的性態(tài)才多種多樣。有時(shí)，這種差別很明顯，如表中的第一組個(gè)體，被交換部分完全不一樣。后者選擇兩個(gè)或多個(gè)交換點(diǎn)，只有兩點(diǎn)間的字符才參加交換。假設(shè)字符串長度為 L，則在 [ 0， L ]區(qū)間內(nèi)產(chǎn)生隨機(jī)整數(shù)，該整數(shù)便是交換點(diǎn)的位置。首先，要確定交換的概率 Pc，大致為 ～ 。 （ 3） 復(fù)制 51 下表是個(gè)體兩兩交換的示例，字符串內(nèi)的下橫線代表交換點(diǎn)的位置，交換點(diǎn)及其后面的字符串兩兩互換。當(dāng)然，適應(yīng)度小的個(gè)體盡管被復(fù)制的概率小，但仍有可能被“破格”復(fù)制，這樣就增加個(gè)體的多樣性，便于執(zhí)行交換及突變。如下圖所示。依次序?qū)⒌谌械睦塾?jì)適應(yīng)度與隨機(jī)數(shù)相比較，其值大于或等于隨機(jī)數(shù)的第一個(gè)個(gè)體列為入選的復(fù)制對象。 個(gè)體是否被復(fù)制的依據(jù)是其適應(yīng)度的大小，適應(yīng)度大者被復(fù)制，小者被淘汰，使新群體中的個(gè)體總數(shù)與原來群體相同。 a、 b ：系數(shù)。這種不正常的取舍，對于個(gè)體數(shù)目不多的群體尤為嚴(yán)重，會(huì)把遺傳算法的搜索引向誤區(qū) ，過早地收斂于 局部最優(yōu)解 。 U(x)：最大值問題下的適應(yīng)度。 對于最小值問題，其適應(yīng)度按下式轉(zhuǎn)換： f (x) = Cmax g (x) 當(dāng) g(x) Cmax 0 其他情況 f(x)：轉(zhuǎn)換后的適應(yīng)度。在運(yùn)用過程中可以借鑒以下經(jīng)驗(yàn)。根據(jù)適應(yīng)度的大小，決定某些個(gè)體是繁殖或是消亡。個(gè)別研究者采用不等長的字符串，這時(shí)就需要跟蹤記錄，經(jīng)常調(diào)整操作方式，比較煩瑣。例如，對于 [ 16， 31 ]的十進(jìn)制數(shù)，我們可以用 4位二進(jìn)制 0/1字符在 [ 0000， 1111 ]范圍內(nèi)表示。例如，用 4位 0/1字符串表示 1 ～ 16。當(dāng)問題比較簡單，例如只描述高 /低、大 /小等布爾型性質(zhì)時(shí)，每一位 0/1變量就代表一個(gè)性質(zhì)。隨機(jī)地改變某一個(gè)體的某個(gè)字符后添入新群體中。 Pc Pt Pm No No Yes Gen： =0 隨機(jī)產(chǎn)生初始群體 滿足終止條件 計(jì)算群體中各個(gè)體的適應(yīng)度 i： =0 i： =M? 選擇遺傳算子及概率 根據(jù)適應(yīng)度選擇兩個(gè)個(gè)體 i： =i+1 執(zhí)行交換 將兩個(gè)交換結(jié)果添入新群體 i： =i+1 將復(fù)制結(jié)果添入新群體 執(zhí)行復(fù)制 根據(jù)適應(yīng)度選擇一個(gè)個(gè)體 將突變結(jié)果添入新群體 執(zhí)行突變 Gen： =Gen+1 輸出結(jié)果 結(jié)束 Yes 37 概括地講，遺傳算法主要執(zhí)行以下四步： （ 1） 隨機(jī)地建立由字符串組成的初始群體； （ 2） 計(jì)算各個(gè)體的適應(yīng)度； （ 3） 根據(jù)遺傳概率，利用下述操作產(chǎn)生新群體： 1） 復(fù)制 。 i：已處理個(gè)體的累計(jì)數(shù)，當(dāng) i等于 M，表明這一代的個(gè)體已全部處理完畢，需要轉(zhuǎn)入下一代群體。 遺傳算法的詳細(xì)流程如下圖?？刂齐[性性狀的基因是隱性基因 ，用小寫英文字母表示。 遺傳算法的生物學(xué)含義 33 遺傳學(xué)很注重 等位基因 ，它是反映生物某一形態(tài)所對應(yīng)的基因。 遺傳算法的基本特征 32 遺傳算法受生物進(jìn)化與遺傳的啟發(fā)，形成一種獨(dú)特的優(yōu)化方式，因此，遺傳算法的運(yùn)算原則常常與生物進(jìn)化及遺傳學(xué)說吻合，而且其術(shù)語也常常仿效生物學(xué)的術(shù)語。 （ 6）并行式算法 遺傳算法是從初始群體出發(fā)，經(jīng)過復(fù)制、交換、突變等操作，產(chǎn)生一組新的群體。因此遺傳算法從某種意義上講是一種只考慮輸入與輸出關(guān)系的黑箱問題。 遺傳算法的基本特征 30 （ 3）全局最優(yōu)解 遺傳算法由于采用交換、突變等操作，產(chǎn)生新的個(gè)體，擴(kuò)大了搜索范圍，使得搜索得到的優(yōu)化結(jié)果是全局最優(yōu)解而不是局部最優(yōu)解。 29 （ 1）智能式搜索 遺傳算法的搜索策略，既不是盲目式的 亂搜索 ，也不是窮舉式 的全面搜索，它是有指導(dǎo)的搜索。通常，突變概率很小，約為 ，本例的第一代中就沒有發(fā)生突變。例如，下式左側(cè)的個(gè)體于第 3位突變，得到新個(gè)體如右側(cè)所示。交換開始的位置稱 交換點(diǎn) 。被交換的母體都選自經(jīng)過復(fù)制產(chǎn)生的新一代個(gè)體（優(yōu)勝者）。使最小適應(yīng)度由原來的 64增加到 169。 3號個(gè)體性能最差，將它刪除，使之死亡，表中的 M表示傳遞給下一代的個(gè)體數(shù)目，其中 2號個(gè)體占 2個(gè)， 3號個(gè)體為 0， 1號、 4號個(gè)體保持為 1個(gè)。如 2號個(gè)體的 f(xi)/f 值最高（ ），為優(yōu)良個(gè)體， 3號個(gè)體最低（ ），為不良個(gè)體。 x值相應(yīng)為 13， 24， 8， 19。這種字符串相當(dāng)于遺傳學(xué)中的染色體。 若只有選擇和交叉 ， 而沒有變異 ， 則無法在初始基因組合以外的空間進(jìn)行搜索 ， 使進(jìn)化過程在早期就陷入局部解而進(jìn)入終止過程 ， 從而影響解的質(zhì)量 。交叉有單點(diǎn)交叉、兩點(diǎn)交叉、還有一致交叉、順序交叉和周期交叉。 （ 2） 交叉 （ Crossover Operator） 復(fù)制操作能從舊種群中選擇出優(yōu)秀者 ， 但不能創(chuàng)造新的染色體 。 如：愛斯基摩人 ， 非洲原始部落 遺傳算法的基本操作為： （ 1） 復(fù)制 （ Reproduction Operator） 復(fù)制是從一個(gè)舊種群中選擇生命力強(qiáng)的個(gè)體位串產(chǎn)生新種群的過程 。 （ 3） 生存斗爭和適者生存：具有適應(yīng)性變異的個(gè)體被保留下來 ，不具有適應(yīng)性變異的個(gè)體被淘汰 ， 通過一代代的生存環(huán)境的選擇作用 ， 性狀逐漸逐漸與祖先有所不同 ， 演變?yōu)樾碌奈锓N 。 自然選擇學(xué)說包括以下三個(gè)方面： 遺傳算法 （ 1） 遺傳：這是生物的普遍特征 ， 親代把生物信息交給子代 ， 子代總是和親代具有相同或相似的性狀 。 其主要特點(diǎn)是 (1)直接對結(jié)構(gòu)對象進(jìn)行操作 ， 不存在求導(dǎo)和函數(shù)連續(xù)性的限定； (2)具有內(nèi)在的隱含并行性和更好的全局尋優(yōu)能力； (3)