【正文】 生物遺傳和 進化過程中的這種變異現(xiàn)象 ， 在遺傳算法中引入了變異算子來產(chǎn)生新的個體 。 在遺傳運算過程中 ， 當交叉操作產(chǎn)生的后代適應(yīng)度值不再進化且沒有達到最優(yōu)時 ，意味著算法陷入了早熟 。 早熟的根源在于有效基因的缺損 ， 變異算子在一定程度上克服了這種情況 ， 它可以改善遺傳算法的局部搜索能力 ， 增加種群的多樣性 。 基本遺傳算法運行參數(shù) 遺傳算法中有下面幾個參數(shù)對遺傳算法 的運行有很大影響 ， 需認真選取 ， 它們是：個體編碼串長度 l、群體大小 M、 復(fù)制概率 Pr、 交叉概率 Pc、 變異概率 Pm、終止代數(shù) T。 (1) 編碼串長度 l 使用二進制編碼表示個體時 ， 編碼串長度 l 的選取與問題所要求的求解精度有關(guān) ；使用浮點數(shù)編碼來表示個體時 ， 編碼串長度 l 與決策變量的個數(shù) n 相等 ； 另外 ， 也可使用變長度的編碼來表示個體 。 (2) 群體大小 M 當 M 取值較小時 ， 可提高遺傳算法的運算速度 ， 但卻降低了群體的多樣性 ， 有可能會引起遺傳算法的早熟現(xiàn)象 ； 而當 M 取值較大時 ， 又會使得遺傳算法的運行效率降低 。一般建議的取值范圍是 20～ 100。 (3) 復(fù)制概率 Pr 復(fù)制操作建立在對個體的適應(yīng)度進行評價的基礎(chǔ)之上 ， 適應(yīng)度較高的個體被遺傳到下一代群體中的概率較大 ； 適應(yīng)度較低的個體被遺傳到下一代群體中的概率較小 ， 復(fù)制概率不可取的太大 ， 也不可以取的太小 。 (4) 交叉概率 Pc 交叉概率一般取值較大 。 但如果太大 ， 它會破壞群體中的優(yōu)良模式 ， 對進化運算不利 。 一般建議的取值范圍是 ～ 。 另外 ， 也可使用自適應(yīng)的思想來確定交叉概率Pc。 (5) 變異概率 Pm 如果變異概率 Pm 取值太大 ， 則容易破壞群體中的優(yōu)良模式 ， 使得遺傳算法的搜索趨于隨機性 ； 如果取值過小 ， 則它產(chǎn)生新個體和抑制早熟的能力會較差 。 一般建議的取值范圍是 ～ 。 另外也可使用自適應(yīng)的思想來確定變異概率 ， 如取 Pm 與其上一代群體間的海明距離成反比 ， 其結(jié)果會有效地維持群體的多樣性 。 (6) 終止代數(shù) T 終止代數(shù) T 是表示遺傳算法運行結(jié)束條件的一個參數(shù) ， 一般建議的取值范圍是 100～500。 至于遺傳算法的終止條件 ， 還可以利用別的判定準則 。 遺傳算法的特點 遺傳算法利用了生物進化和遺傳的基本思想 ， 所以它與許多傳統(tǒng)優(yōu)化算法的特點不同 ， 可以充分的縮短搜索時間 。 傳統(tǒng)的優(yōu)化方法主要有三 種 :枚舉法、啟發(fā)式算法和搜索算法 。 (1) 枚舉法 枚舉法是指枚舉出可行解集合內(nèi)的所有可行解 ， 以求得精確的最優(yōu)解 。 對于連續(xù)的函數(shù) ， 該方法要求先對其進行離散化處理 ， 這樣就有可能產(chǎn)生離散誤差而永遠達不到最優(yōu)解 。 但是當枚舉空間比較大時 ， 該方法的求解效率比較低 ， 有時甚至在目前最先進的計算工具上都無法求解 。 (2) 啟發(fā)式算法 啟發(fā)式算法是指尋求一種能產(chǎn)生可行解的啟發(fā)式規(guī)則 ， 以找到一個最優(yōu)解或近似最優(yōu)解 。 該方法的求解效率雖然比較高 ， 但是對于每一個需要求解的問題都必須找出其特有的啟發(fā)式規(guī)則 ， 這個啟發(fā)式規(guī)則沒有通用性 ， 不 適合于所有的問題 。 (3) 搜索算法 搜索算法是指尋求一種算法 ， 能在可行解集合的一個子集內(nèi)進行搜索操作 ， 以找到問題的最優(yōu)解或者近似最優(yōu)解 。 該方法雖然保證不了一定能夠得到問題的最優(yōu)解 ， 但是如果適當?shù)睦靡恍﹩l(fā)知識 ， 就可在近似解的質(zhì)量和求解效率上達到一種較好的平衡 。 而遺傳算法既是一種自然進化系統(tǒng)的計算模型 ， 也是一種通用的求解優(yōu)化問題的適應(yīng)性搜索方法 。 隨著問題種類的不同以及問題規(guī)模的擴大 ， 要尋求一種能以有限的代價來解決搜索和優(yōu)化的通用方法 ， 遺傳算法正是提供了一種有效的途徑 ， 它不同于傳統(tǒng)的優(yōu)化方法 ， 它具備的特點 主要有以下幾個方面 : (1) 遺傳算法采用群體搜索尋找最優(yōu)解 ， 而不是從單個個體搜索尋找最優(yōu)解 。 搜索軌道有多條 ， 而非單條 ， 覆蓋面大 ， 利于全局擇優(yōu) 。 這是遺傳算法與傳統(tǒng)優(yōu)化算法的最大區(qū)別 ， 傳統(tǒng)優(yōu)化算法是從單個個體搜索尋找最優(yōu)解 ， 效率比較低 。 (2) 遺傳算法求解時利用適應(yīng)度函數(shù)值信息 ， 并不需要問題導(dǎo)數(shù)等與問題直接相關(guān)的信息 。 所以說在所定義的函數(shù)不連續(xù)、多峰或不可微的情況下 ， 也能以很大的概率收斂到全局最優(yōu)解 。 (3) 遺傳算法是以決策變量的編碼作為運算對象 。 在優(yōu)化過程中借鑒生物學(xué)中染色體和基因等概念 ， 模擬自然界中生 物的遺傳和進化等機理 ， 應(yīng)用遺傳操作 ， 可方便求解無數(shù)值概念或很難有數(shù)值概念的優(yōu)化問題 ， 這樣的話 ， 遺傳算法就克服了非數(shù)值變量的操作 。 (4) 遺傳算法有極強的容錯能力 。 遺傳算法的初始解集本身就帶有大量與最優(yōu)解相差甚遠的信息 ， 通過選擇、交叉、變異操作能迅速排除與最優(yōu)解相差極大的解 ， 這是一個強烈的濾波過程 。 并且是一個并行濾波機制 。 因此 ， 遺傳算法有很高的容錯能力 ， 因為它就相當預(yù)先就進行了運算 ， 或則說在內(nèi)部就進行了運算 ， 大大增加了運算的效率 。 (5) 遺傳算法使用概率搜索技術(shù) 。 它屬于一種自適應(yīng)概率搜索技術(shù) ， 其選擇、交叉 、變異等運算都是以一定的概率進行的 ， 增加了其搜索過程的靈活性 。 實踐和理論證明了在一定條件下遺傳算法總是以概率 1 收斂于問題的最優(yōu)解 。 (6) 遺傳算法具有隱含的并行性 。 并行性是指兩個或多個事件在同一時刻發(fā)生 ， 這樣就大大增加了運算的速度 。 遺傳算法的基本模型 (1) 將問題的解表示為編碼串（生物學(xué)術(shù)語稱為染色體） ， 每一碼串代表問題的一個可行解 。 (2) 隨機產(chǎn)生一組串長為 m 的初始群體 ， 該群體就是問題的一個可行解的集合 。 (3) 分別將編碼串譯碼成尋優(yōu)參數(shù) ， 計算對應(yīng)的目標函數(shù)并變換為適應(yīng)值 。 (4) 根據(jù) 碼串個體適應(yīng)值的高低 ， 執(zhí)行應(yīng)用復(fù)制、交換和變異算子產(chǎn)生下一代群體 。 (5) 返回步驟 3， 直到滿足停止準則為止 。 這樣 ， 反復(fù)執(zhí)行步驟 3 到步驟 5， 使碼串群體一代代不斷進化 ， 最后搜索到最適應(yīng)問題的個體 ， 求得問題的最優(yōu)解 ， 其流程圖如圖 1 所示 。 開 始結(jié) 束產(chǎn) 生 初 始 群 體計 算 個 體 適 應(yīng) 度適 應(yīng) 值 高 的 個 體執(zhí) 行 復(fù) 制選 擇 、 交 叉 、 變 異輸 出 結(jié) 果是 否 滿 足 停 止 準 則是否 圖 1 遺傳算法流程圖 遺傳算法的應(yīng)用 遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架 ， 它不依賴于問題的具體領(lǐng)域、對問題的種類有很強的魯棒性 ， 所以廣泛應(yīng)用于很多學(xué)科 。 下面是遺傳算法的一些主要應(yīng)用領(lǐng)域： 1 函數(shù)優(yōu)化 函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域 ， 也是對遺傳算法進行性能評價的常用算例 。很多人構(gòu)造出了各種各樣的復(fù)雜形式的測試函數(shù) ， 有連續(xù)函數(shù)也有離散函數(shù) ， 有凸函數(shù)也有凹函數(shù) ， 有低維函數(shù)也有高維函數(shù) ， 有確定函數(shù)也有隨機函數(shù) ， 有單峰值函數(shù)也有多峰值函數(shù)等 ， 用這些幾何特性各具特色的函數(shù)來評價遺傳算法的性能 ， 更能反映算法的本質(zhì)效果 。 而對于一些非線性、多模型、多目標的函數(shù)優(yōu)化問題 ， 用其他優(yōu)化方法較難求解 ， 而遺傳算法卻可以方便地得到較好的結(jié)果 。 2 組合優(yōu)化 隨著問題規(guī)模的增大 ， 組合優(yōu)化問題的搜索空間也急劇擴大 ， 有時 在目前的計算機上用枚舉法很難或甚至不可能求出其精確最優(yōu)解 。 對這類復(fù)雜問題 ， 人們已意識到應(yīng)把主要精力放在尋求其滿意解上 ， 而遺傳算法是尋求這種滿意解的最佳工具之一 。 實踐證明 ， 遺傳算法已經(jīng)在求解旅行商問題、背包問題、裝箱問題、布局優(yōu)化、圖形劃分問題等各種具有 NP 難度的問題得到成功的應(yīng)用 。 3 生產(chǎn)調(diào)度問題 生產(chǎn)調(diào)度問題在很多情況下建立起來的數(shù)學(xué)模型難以精確求解 ， 即使經(jīng)過一些簡化之后可以進行求解 ， 也會因簡化得太多而使得求解結(jié)果與實際相差甚遠 。 目前在現(xiàn)實生產(chǎn)中主要是靠一些經(jīng)驗來進行調(diào)度 。 現(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度 問題的有效工具 ，在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用 。 4 自動控制 在自動控制領(lǐng)域中有很多與優(yōu)化相關(guān)的問題需要求解 ， 遺傳算法已在其中得到了初步的應(yīng)用 ， 并顯示出良好的效果 。 例如用遺傳算法進行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學(xué)習(xí)等 ， 都顯示出了遺傳算法在這些領(lǐng)域中應(yīng)用的可能性 。 5 機器人學(xué) 機器人是 一類復(fù)雜的難以精確建模的人工系統(tǒng) ， 而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究 ， 所以 ， 機器人學(xué)理所當然地成為遺傳算法的一個重要應(yīng)用領(lǐng)域 。 例如 ，遺傳算法已經(jīng)在移動機器人路徑規(guī)劃、關(guān)節(jié)機器人運動軌跡規(guī)劃、機器人逆運動學(xué)求解、細胞機器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方面得到研究和應(yīng)用 。 6 圖像處理 圖像處理是計算機視覺中的一個重要研究領(lǐng)域 。 在圖像處理過程中 ， 如掃描、特征提取、圖像分割等不可避免地會存在一些誤差 ， 從而影響圖像的效果 。 如何使這些誤差最小是使計算機視覺達到實用化的重要要求 。 遺傳算法在這些圖像處理中的優(yōu)化計算方面找到了用武之地 ， 目前已在模式識別 (包括漢字識別 )、圖像恢復(fù)、圖像邊緣特征提取等方面得到了應(yīng)用 。 7 人工生命 人工生命是用計算機、機械等人工媒體模擬或構(gòu)造出的具 有自然生物系統(tǒng)特有行為 的人造系統(tǒng) 。 自組織能力和自學(xué)習(xí)能力是人工生命的兩大主要特征 。 人工生命與遺傳算法有著密切的關(guān)系 。 基于遺傳算法的進化模型是研究人工生命現(xiàn)象的重要基礎(chǔ)理論 ， 雖然人工生命的研究尚處于啟蒙階段 ， 但遺傳算法已在其進化模型、學(xué)習(xí)模型、行為模型、自組織模型等方面顯示出了初步的應(yīng)用能力 ， 并且必將得到更為深入的應(yīng)用和發(fā)展 。 人工生命與遺傳算法相輔相 成 ， 遺傳算法為人工生命的研究提供一個有效的工具 ， 人工生命的研究也必將促進遺傳算法的進一步發(fā)展 。 8 遺傳編程 1989 年 ， 美國 Standford 大學(xué)的 Koza 教授發(fā)展了遺傳編程的概念 ， 其基本思想是 :采用樹型結(jié)構(gòu)表示計算機程序 ， 運用遺傳算法的思想 ， 通過自動生成計算機程序來解決問題 。 雖然遺傳編程的理論尚未成熟 ， 應(yīng)用也有一些限制 ， 但它已成功地應(yīng)用于人工智能、機器學(xué)習(xí)等領(lǐng)域 ， 目前公開的遺傳編程實驗系統(tǒng)有十多個 。 9 機器學(xué)習(xí) 學(xué)習(xí)能力是高級自適應(yīng)系統(tǒng)所具備的能力之一 ， 基于遺傳算法的機器學(xué)習(xí) ， 特別是分類器系統(tǒng) ， 在很 多領(lǐng)域中都得到了應(yīng)用 。 例如 ， 遺傳算法被用于學(xué)習(xí)模糊控制規(guī)則 ，利用遺傳算法來學(xué)習(xí)隸屬度函數(shù) ， 從而更好地改進了模糊系統(tǒng)的性能 ； 基于遺傳算法的機器學(xué)習(xí)可用來調(diào)整人工神經(jīng)網(wǎng)絡(luò)的連接權(quán) ， 也可用于人工神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)優(yōu)化設(shè)計 ； 分類器系統(tǒng)也在學(xué)習(xí)式多機器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用 。 10 數(shù)據(jù)挖掘 數(shù)據(jù)挖掘是近幾年出現(xiàn)的數(shù)據(jù)庫技術(shù) ， 它能夠從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應(yīng)用價值的知識和規(guī)則 。 許多數(shù)據(jù)挖掘問題可看成是搜索問題 ， 數(shù)據(jù)庫看作是搜索空間 ， 挖掘算法看作是搜索策略 。 因此 ， 應(yīng)用遺傳算法在數(shù)據(jù)庫中進行搜索 ，對隨機產(chǎn)生的一組規(guī)則進行進化 ， 直到數(shù)據(jù)庫能被該組規(guī)則覆蓋 ， 從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則 。 Sunil 已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘工具 ， 利用該工具對兩個飛機失事的真實數(shù)據(jù)庫進行了數(shù)據(jù)挖掘?qū)嶒?， 結(jié)果表明遺傳算法是進行數(shù)據(jù)挖掘的有效方法之一 。 遺傳算法 今 后 的研究方向 遺傳算法是多學(xué)科結(jié)合與滲透的產(chǎn)物 ， 已經(jīng)發(fā)展成一種自組織、自適應(yīng)的綜合技術(shù) ，廣泛應(yīng)用在計算機科學(xué)、工程技術(shù)和社會科學(xué)等領(lǐng)域 。 其研究工作主要集中在以下幾個方面： 1 基礎(chǔ)理論 它包括進一步發(fā)展遺傳算法的數(shù)學(xué)基礎(chǔ) ， 從理論和試驗研究它們的 計算復(fù)雜性 。 在遺傳算法中 ， 群體規(guī)模和遺傳算子的控制參數(shù)的選取非常困難 ， 但它們又是必不可少的試驗參數(shù) 。 在這方面 ， 已有一些具有指導(dǎo)性的試驗結(jié)果 。 遺傳算法還有一個過早收斂的問題 ， 怎樣阻止過早收斂也是人們正在研究的問題之一 。 2 分布并行遺傳算法 遺傳算法在操作上具有高度的并行性 ， 許多研究人員都在探索在并行機和分布式系統(tǒng)上高效執(zhí)行遺傳算法的策略 。 對分布并行遺傳算法的研究表明 ， 只要通過保持多個群體和恰當控制群體間的相互作用來模擬并行執(zhí)行過程 ， 即使不使用并行計算機 ， 也能提高算法的執(zhí)行效率 。 3 分類系統(tǒng) 分類系統(tǒng)屬于基 于遺傳算法的機器學(xué)習(xí)中的一類 ， 包括一個簡單的基于串規(guī)則的并行生成子系統(tǒng)、規(guī)則評價子系統(tǒng)和遺傳算法子系統(tǒng) 。 分類系統(tǒng)被人們越來越多地應(yīng)用在科學(xué)、工程和經(jīng)濟領(lǐng)域中 ， 是目前遺傳算法研究中一個十分活躍的領(lǐng)域 。 4 遺傳神經(jīng)網(wǎng)絡(luò) 它包括連接權(quán)、網(wǎng)絡(luò)結(jié)構(gòu)和學(xué)習(xí)規(guī)則的進化 。 遺傳算法與神經(jīng)網(wǎng)絡(luò)相結(jié)合 ， 正成功地用于從時間序列分析來進行財政預(yù)算 。 在這些系統(tǒng)中 ， 訓(xùn)練信