遺傳算法的發展現狀與應用執行個體

.

1  引言

近年來 ,遺傳算法 (GA)的卓越性能引起人們的關注 .對于以往難以解決的函數優化問題 ,複雜的多目标規劃問題 ,工農業生産中的配管、配線問題 ,以及機器學習 ,圖象識别 ,人工神經網絡的權系數調整和網絡構造等問題 ,GA是最有效的方法之一 .雖然GA在許多優化問題中都有成功的應用 ,但其本身也存在一些不足 .例如局部搜尋能力差、存在未成熟收斂和随機漫遊等現象 ,進而導緻算法的收斂性能差 ,需要很長時間才能找到最優解 ,這些不足阻礙了遺傳算法的推廣應用 .如何改善遺傳算法的搜尋能力和提高算法的收斂速度 ,使其更好地應用于實際問題的解決中 ,是各國學者一直探索的一個主要課題.之後世界範圍内掀起了關于遺傳算法的研究與應用熱潮

2  遺傳算法存在的問題及相應的改進措施

自然界早已顯示出了基因的強大威力 ,通過這種機制 ,一系列的具有智能、自組織、自修整的器官産生了 .人們要在科學研究中效仿這些生物器官 ,那麼就必須了解基因、進化的概念 .GA就是這樣一種利用自然選擇和進化思想在高維空間中尋優的方法 ,它不一定能尋得最優點 ,但是它可以找到更優 點 ,這種思路與人類行為中成功的标準是很相似的 .例如不必要求一支軍隊是最優的 ,要戰勝對手隻需它比對手更強即可 .是以 GA可能會暫時停留在某些非最優點上 ,直到變異發生使它躍居到另一個更優點上 . GA尋優過程的一個重要特點是它始終保持整個種群的進化 ,這樣即使某個體在某時刻喪失了有用的特征 ,這種特征也會被其他個體所保留并延續發展下去 .由于 GA僅需知道目标函數的資訊 ,而不需要其連續可微等要求 ,因而具有廣泛的适應性 .同時它又是一種采用啟發性知識的智能搜尋算法 ,是以往往能在搜尋空間高度複雜的問題上取得比以往算法 (如梯度法 )更好的效果D. B. Fogel提出的進化即智能的概念[1 0 ],雖然還沒有被普遍接受 ,但進化在人類生存進步過程中的重要性已可見一斑 ,是以遺傳算法作為生物進化思想在工程計算中的一種展現 ,其前途是光明的 .目前 GA在工程優化、信号處理、模式識别、管理決策、智能系統設計和人工生命等領域的成功利用正說明了這一點 .

2. 1　編碼表示

　　 Holland在運用模式定理分析編碼機制時 ,建議使用二進制編碼 ,但二進制編碼不能直接反映問題的固有結構 ,精度不高 ,個體長度大 ,占用計算機記憶體多 . Gray編碼是将二進制編碼通過一個變換進行轉換得到的編碼 ,其目的就是克服 Hamming懸崖的缺點,動态編碼 (dynamic encoding)GA是當算法收斂到某局部最優時增加搜尋的精度 ,進而使得在全局最優點附近可以進行更精确的搜尋 ,增加精度的辦法是在保持串長不變的前提下減小搜尋區域 .對于問題的變量是實向量的情形 ,可以直接采用實數進行編碼 ,這樣可以直接在解的表現型上進行遺傳操作 ,進而便于引入與問題領域相關的啟發式資訊以增加算法的搜尋能力.複數編碼[5]的GA是為了描述和解決二維問題 ,基因用 x+yi 表示 ;其還可以推廣到多元問題的描述中 .多元實數編碼[6 ]GA,使無效交叉發生的可能性大大降低 ,同時其合理的編碼長度也有助于算法在短時間内獲得高精度的全局最優解 .在組合優化中 ,可以使用有序串編碼 ,例如在文獻 [7]中用自然數編碼巧妙地解決了VRP問題 .當問題的表示是樹和圖時 ,我們還可以使用結構式編碼

2. 2　适應度函數

适應度函數是用來區分群體中個體好壞的标準 ,是自然選擇的唯一标準 ,選擇的好壞直接影響算法的優劣 .引入适應值調節和資源共享政策可以加快收斂速度和跳出局部最優點 .對适應值進行調節就是通過變換改變原适應值間的比例關系 ,常用的比例變換有線性變換、乘幂變換和指數變換等 .對于一個問題具體采用什麼變換才能達到較優的效果 ,V. Kreinovich等在文獻 [8]中做了較詳細的讨論 而在文獻 [9]中則是采用共享的技術 ,對子群的形成和穩定起了一定作用 ,文中主要用子群消失時間的近似形式估計 Sharing的界 .文獻 [1 0 ]中采用了依據搜尋進展可變的适應值函數 ,并應用于 CuttingProblem取得較好效果 .文獻 [1 1 ]中設計了自适應選取遺傳算法的适應值函數的方法 ,該方法的計算量要比排序選擇操作的計算量小的多 ,而且有效的避免了算法的非成熟收斂 .

2 . 3　選擇政策

　　優勝劣汰的選擇機制使得适應值大的個體有較大的存活機會 ,不同的選擇政策對算法性能有較大的影響 .輪盤賭法是使用最多的選擇政策 ,但這種政策可能會産生較大的抽樣誤差 ,于是對此提出了很多的改進方法 ,如繁殖池選擇[1 2 ],Boltzmann選擇[1 3 ]等等 .但是這幾種政策都是基于适應值比例的選擇 ,常常會出現早熟收斂現象和停滞現象 .為此又提出了非線性排名選擇[3 ],這種選擇不僅避免了上述問題 ,而且可以直接使用原始适應值進行排名選擇 ,而不需對适應值進行标準化 ;但這種選擇在群體規模很大時 ,其額外計算量 (如計算總體适應值和排序 )也相當可觀 ,甚至在進行并行實作時有時要帶來一些同步限制 .基于局部競争機制的選擇如 (λ+μ)選擇[1 4],它使雙親和後代有同樣的生存競争機會在一定程度上避免了這些問題 .在 [1 5]中作者采用

了類似梯度的方式來選擇 ,不僅使較差的染色體比較好的染色體得到更大的改進 ,而且還不斷産生新的個體 ,進而不斷拓展了新的搜尋空間 . [1 6 ]中作者

引入了 Harvesting Strategies來分析遺傳算法的性能 ,Harvesting Strategies是指在每一代交叉和突變後進行兩次乃至多次篩選作為下面的群體 .采用了 Disruptive Selection,它吸收了優等和劣等個體 ,實驗結果表明了兩極分化有可能更容易找到最優解 .為了提高種群的多樣性 ,提出一種基于免疫多樣性的選擇算子[1 8],該選擇算子依賴于串的稠密度和适應值 ,串的稠密度越大 ,其保留下來的可能性越小 ,具體事例證明改進算法是有效的 .

2 . 4　控制參數

　　控制參數一般有群體大小 ,交換機率 ,變異機率等 ,這些參數對遺傳算法性能影響較大 .在标準的遺傳算法中采用經驗進行估計 ,這将帶來很大的盲目性 ,而影響算法的全局最優性和收斂性 .目前許多學者意識到這些參數應該随着遺傳進化而自适應變化 ,Davis提出自适應算子機率方法 [1 9],即用自适應

機制把算子機率與算子産生的個體适應性結合 ,高适應性值被配置設定高算子機率 . Whitley提出一種自适應突變政策與一對父串間的 Hamming距離成反比 [2 0 ],結果顯示能有效地保持基因的多樣性 .張良傑等通過引入 i位改進子空間概念 ,采用模糊推理技術來确定選取突變機率的一般性原則 [2 1 ].在文獻[2 2 ]中設計了一種群體規模可變的遺傳算法 ,它提出每個個體應當有年齡及生命期的概念并淘汰年齡大于生命期的個體進而使遺傳算法動态的控制了群體數目 ,這種方法可以找出一個接近最小代價的遺傳算法 ,同時盡量将群體規模保持在現有水準 ,防止群體規模的指數級增長 ,以降低計算的開銷 .丁承明等提出利用正交試驗法去優化選取 GA控制參數 [2 3 ],這種方法利用正交試驗的均衡分散性使得通過較少的試驗次數就可搜尋絕大部分參數組合空間 ,而且還可以确定哪個參數對 GA結果影響最顯著 ,然後有針對性地進行精确搜尋 ,進而使得 GA參數問題得到圓滿解決 .為保證種群的有用多樣性 ,提出動态群法[2 4],即當疊代到一定代數 ,若目标函數的值相同 ,則現存種群中的較差的 N個染色體被随機産生的 N個染色體代替 ,使進化過程中不斷有新個體引入 . [2 5]中用模糊規則對選擇機率和變異機率進行控制 ,線上改變其值 ,相應的算例表明 ,有較好的性能

2. 5　遺傳算子

　　基本遺傳算法中采用單點交叉算子和簡單的變異算子 .它們操作比較簡單 ,計算量小 ,但是在使用過程中有很大的局限性 ,例如 :由于單點交叉破壞模式的機率較小 ,至使搜尋到的模式數也較少 ,使算法具有較低的搜尋能力 . Feng etal.對多元連續空間的GA的雜交多樣性進行了分析 ,通過建立相應的數學模型 ,Feng解釋了在多元連續空間和大規模群體中使用均勻雜交算子[2 6 ]是如何探索新的解空間區域 .為了使得變異能夠根據解的品質自适應的調整搜尋區域 ,進而能較明顯地提高搜尋能力 ,提出自适應變異算子[2 7].為了保護适應值較高的模式 ,提出自适應交叉和變異 [2 8],如果遇到适應值較高的模式 ,則通過随機引入模式外的位而進行保護 .為了克服早熟 ,引入多種群 GA[2 9],不同種群賦以不同的控制參數 ,實作不同的搜尋目的 ,通過移民算子聯系各種群 ,通過人工選擇算子儲存各種群每個進化代中的最優個體 .為了防止近親繁殖 ,擴大種群的多樣性 ,抑制超長個體的快速繁殖 ,引進近親繁殖算子 ,兩個個體是否為近親可用基因片段的 Hamming距離來判斷 ,距離越大 ,則為近親的可能越小 ;為加強局部搜尋能力 ,增加漂移算子 ,将染色體各基因片段的後二分之一的基因分别按一定的機率做 1的随機漂移 ,排位越後的基因漂移的機率越大 ,由此産生一定數量的新個體 ,用基因預選機制的小生境技術控制漂移方向 [3 0 ].因為格點法産生的點集能均勻地分布于搜尋空間 ,并且佳點又是最好的格點 ,是以可以用數論中的佳點集理論設計交叉算子[3 1 ],結果表明它的搜尋效果要比純随機法好 ,而且有效的避免早熟現象 .基于生物免疫性提出的免疫算子 [3 2 ],能夠明顯抑制進化過程中的退化現象 ,減輕 GA後期的波動 ,進而提高了搜尋效率和收斂速度 . [3 3 ]中提出的 SRM(self-reproduction)算子增強了種群的多樣性 ,CM(crossove and mutation)算子促進了有利變異的增加 ,進而使算法大大節省了存貯空間和運作時間 .采用“尺度收縮”政策的混沌變異算子 [3 4]能明顯的改善群體平均适應值 ,提高算法的性能 ,是解決優化問題的有效方法 .

2 . 6　綜合方面

文獻 [3 5]中提出了可分解 /可拼接 GA編碼 ,并基于此編碼分别在種群層次和基因層次發展了動态變異和動态選擇操作 ,這種方法很大程度上避免了早熟問題 .增強型 GA[3 6 ]中 ,引入了幾個新算子和新的種群遷移政策 ,并用其對模糊邏輯控制器進行設計 ,得到了便于了解的模糊集和模糊規則 .用小波分析中的多尺度分析對 GA中的染色體進行多尺度分解 ,這樣分解後的染色體的長度變短 ,基因交換、變異等遺傳操作更為徹底 ,有效的克服了基因丢失引起的早熟問題 [3 7].小生境技術不僅能夠保證群體中解的多樣性 ,而且具有很強的引導進化能力 ,是以小生境技術的引入 ,提高了 GA處理多峰函數優化問題的能力[3 8].将模拟退火過程引入遺傳算法[3 9],在優選交叉和變異個體的過程中加入一定的“擾動”,以達到保持種群内位串的多樣性和位串之間的競争機制 ,克服了算法易陷于極小點的問題 ,使得搜尋沿着全局最優方向進行 .廣義遺傳算法[40 ],它以多點突變操作為主 ,以基因交叉操作為輔 ,實作了從一個局部最優狀态到另一個局部最優狀态的轉移 ,使算法獲得全局最優 .為了使 GA用于限制優化 ,提出一種非穩态罰函數 GA[41 ],非穩态罰函數是遺傳代數的函數 ,當代數增加時 ,罰函數也随着增大 ,同時給GA帶來更多的選擇壓力 ,促使 GA找到可行解 .綜合遺傳算法的全局性和神經網絡的并行快速性等特點 ,提出的遺傳神經網絡算法[42 ],可克服遺傳算法最終進化至最優解較慢和神經網絡易陷入局部解的缺陷 ,具有較好的全局性和收斂速度 .采用面向對象技術設計了面向對象遺傳算法[43 ],這種方法改變了在傳統的 GA中各個函數之間隻有參數的傳遞 ,而沒有代碼的繼承性的狀況從概念上提高了軟體的可重用性 ,使用者可以更友善的設計和實作自己的編碼方案和遺傳算子 .變異基遺傳算法[44],采用變異算子進行局部優化搜尋 ,并利用随機初始化技術使算法在局部搜尋能力提高的同時仍有可能尋找到全局最優解 .貪婪遺傳算法[45]用在二次配置設定問題中取得了較好的效果 ,在該算法中引入了新的交叉算子和移民算子 ,保證了種群的多樣性 ;并且通過比賽競争使得各種群得到進化 ,很好的解決了種群多樣性及對個别好個體偏愛之間的沖突 .

3　遺傳算法的發展動向 (GA' s developmen-tal trends)

GA在應用方面的豐碩成果 ,使人們對它的發展前景充滿信心 .其主要應用領域在于函數優化 (非線性 ,多模型 ,多目标等 ),機器人學 (移動機器人路徑規劃 ,關節機器人運動軌迹規劃 ,細胞機器人的結構優化等 ),控制 (瓦斯管道控制 ,防避飛彈控制 ,機器人控制等 ),規劃 (生産規劃 ,并行機任務配置設定等 ),設計 (VLSI布局 ,通信網絡設計 ,噴氣發動機設計等 ),組合優化 (TSP問題 ,背包問題 ,圖分劃問題等 ),圖象處理 (模式識别 ,特征提取 ,圖象恢複等 ),信号處理 (濾波器設計等 ),人工生命 (生命的遺傳進化等 ).此外遺傳算法的研究出現了幾個引人注目的新動向 :

3 . 1　基于遺傳算法的機器學習

這一新的研究方向把遺傳算法從曆史離散的搜

索空間的優化搜尋算法擴充到具有獨特的規則生成功能的嶄新的機器學習算法 .這一新的學習機制對于解決人工智能中知識擷取和知識優化精煉的瓶頸難題帶來了希望 .遺傳算法作為一種搜尋算法從一開始就與機器學習有着密切聯系 .分類器系統 CS-1是 GA的創立者 Holland教授等實作的第一個基于遺傳算法的機器學習系統 .分類器系統在很多領域都得到了應用 .例如 ,分類器系統在學習式多機器人路徑規劃系統中得到的成功應用 ; Goldberg研究了用分類器系統來學習控制一個瓦斯管道仿真系統 ;Wilson研究了一種用于協調可移動式視訊錄影機的感覺—運動的分類器系統等 .分類器系統在基于遺傳算法的機器學習研究中影響很大 ,但具體實作方法和要解決的具體問題有關 .基于遺傳算法的概念學習是近幾年來機器學習領域的一個較為引人注目的研究方向 ,由于概念學習隐含的搜尋機制 ,使得遺傳算法在概念學習中有用武之地 .目前也有一些嵌入領域知識的基于遺傳算法的機器學習的研究 ,如将概念學習中特有的操作遺傳操作化 ,并顯示出一定的優點 .此外 ,學習分類系統的并行實作在基于遺傳算法的機器學習研究中也占有相當的分量 .

3 . 2　遺傳算法與其他計算智能方法的互相滲透和結合

遺傳算法正日益和神經網絡、模糊推理以及混沌理論等其他智能計算方法互相滲透和結合 ,必能達到取長補短的作用 .近年來在這方面已經取得不少研究成果 ,并形成了“計算智能”的研究領域 ,這對開拓 2 1世紀中新的智能計算技術将具有重要的意義 . GA的出現使神經網絡的訓練 (包括連接配接權系數的優化、網絡空間結構的優化和網絡的學習規則優化 )有了一個嶄新的面貌 ,目标函數既不要求連續 ,也不要求可微 ,僅要求該問題可計算 ,而且它的搜尋始終遍及整個解空間 ,是以容易得到全局最優解 .GA與神經網絡的結合正成功的被用于從時間序列的分析來進行财政預算 ,在這些系統中 ,訓練信号是模糊的 ,資料是有噪聲的 ,一般很難正确的給出每個執行的定量評價 ,如采用 GA來學習 ,就能克服這個困難 ,顯著提高了系統的性能 . Muhlenbein分析了多層感覺機網絡的局限性 ,并猜想下一代神經網絡将會是遺傳神經網絡 .遺傳算法還可以用于學習模糊控制規則和隸屬度函數 ,進而更好地改善模糊系統的性能 .文獻 [46 ]中将模糊邏輯、神經網絡和遺傳算法三者有機的結合起來應用于溫室夏季溫濕度控制中 ,實驗結果表明得到了良好的控制效果 .混沌表現出的随機性是系統内在的随機性 ,被稱為僞随機性 ,它在生物進化中起着重要的作用 ,是系統進化與資訊之源 .混沌與遺傳算法的結合已有人進行過嘗試 ,如吳新餘等[47]采用多種混沌模型構造随機開關 ,以此控制交叉操作以改進 GA的性能 .文獻 [3 4]中更加直接 ,采用混沌序列構造變異算子 ,為遺傳算法的實作開辟了新的途徑 .

3 . 3　并行處理的遺傳算法

并行處理的遺傳算法的研究不僅是遺傳算法本身的發展 ,而且對于新一代智能計算機體系結構的研究都是十分重要的 . GA在操作上具有高度的并行性 ,許多研究人員都正在探索在并行機上高效執行 GA的政策 .近幾年也發表了不少這方面的論文 ,研究表明 ,隻要通過保持多個群體和恰當地控制群體間的互相作用來模拟并執行過程 ,即使不使用并行計算機 ,我們也能提高算法的執行效率 .在并行GA的研究方面 ,一些并行 GA模型已經被人們在具體的并行機上執行了 ;并行 GA可分為兩類 :一類是粗粒度并行 GA,它主要開發群體間的并行性 ,如Cohoon分析了在并行計算機上解圖劃分問題的多群體 GA的性能 ;另一類是細粒度 GA,它主要開發一個群體中的并行性 ,如 Kosak将群體中的每個個體映射到一個連接配接機的處理單元上 ,并指出了這種方法對網絡圖設計問題的有效性 .

3 . 4　遺傳算法與人工生命的滲透

人工生命是用計算機、機械等人工媒體模拟或構造出的具有自然生物系統特有行為的人造系統 ,人工生命與遺傳算法有着密切的關系 ,基于遺傳算法的進化模型是研究人工生命現象的重要理論基礎 .雖然人工生命的研究尚處于啟蒙階段 ,但遺傳算法已在其進化模型、學習模型、行為模型、自組織模型等方面顯示出了初步的應用能力 ,并且必将得到更為深入的應用和發展 .人工生命與遺傳算法相輔相成 ,遺傳算法為人工生命的研究提供了一個有效的工具 ,人工生命的研究也必将促進遺傳算法的進一步發展 .

3 . 5　遺傳算法與進化規則及進化政策的結合

遺傳算法、進化規則及進化政策是演化計算的三個主要分支 ,這三種典型的進化算法都以自然界中生物的進化過程為自适應全局優化搜尋過程的借鑒對象 ,是以三者之間有較大的相似性 ;另一方面 ,這三種算法又是從不完全相同的角度出發來模拟生物的進化過程 ,分别是依據不同的生物進化背景、不同的生物進化機制而開發出來的 ,是以三者之間也有一些差異 .随着各種進化計算方法之間互相交流深入 ,以及對各種進化算法機理研究的進展 ,要嚴格地區分它們既不可能 ,也沒有必要 .在進化計算領域内更重要的工作是生物進化機制 ,構造性能更加優良、适應面更加廣泛的進化算法 .

4　結論

遺傳算法作為一種非确定性的拟自然算法 ,為複雜系統的優化提供了一種新的方法 ,并且經過實踐證明效果顯著 .盡管遺傳算法在很多領域具有廣泛的應用價值 ,但它仍存在一些問題 ,各國學者一直在探索着對遺傳算法的改進 ,以使遺傳算法有更廣泛的應用領域 .

總之,遺傳算法的未來是非常的美好的,隻要我們對它們進行細緻的分析,對它的缺點加以改造,優點進行繼承,把它應用到我們的生産當中去,這樣在生産當中還可以對它的缺點進行完善.