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