遺傳算法研究綜述

摘 要：通過介紹遺傳算法的基本概念和基本原理，說明了遺傳算法應用領域，指出了遺傳算法在應用中的幾個關鍵問題，并介紹了遺傳算法研究新動向及存在的問題。

關鍵詞：遺傳算法；編碼機制；遺傳算子；適應度函數

1 遺傳算法的基本原理

遺傳算法類似于自然進化，通過作用于染色體上基因尋找最好的染色體來求解問題。與自然界相似，遺傳算法對求解問題的本身一無所知，它所需要的僅是對遺傳算法所產生的染色體有更多的繁殖機會。在遺傳算法中，通過隨機方式產生若干個所求解問題的數字編碼，即染色體，形成初始種群；通過適應度函數給每個個體一個數值評價，淘汰低適應度的個體，選擇高適應度的個體參加遺傳操作，經過遺傳操作后的個體集合成下一代新的種群，對這個新種群進行下一輪進化。

2 遺傳算法的應用

遺傳算法在應用中最關鍵的問題有如下3 個。

（1）串的編碼方式。本質是問題編碼。一般把問題的各種參數用二進制編碼，構成子串；然后把子串拼接構成“染色體”串。串長度及編碼形式對算法收斂影響極大。

（2）適應函數的確定。適應函數（fitness function）也稱對象函數（object function），這是問題求解品質的測量函數；往往也稱為問題的“環境”。一般可以把問題的模型函數作為對象函數；但有時需要另行構造。

（3）遺傳算法自身參數設定。遺傳算法自身參數有3 個，即群體大小n、交叉概率Pc 和變異概率Pm。群體大小n 太小時難以求出最優解， 太大則增長收斂時間。一般n=30-160。交叉概率Pc 太小時難以向前搜索，太大則容易破壞高適應值的結構。一般取Pc=0.25-0.75。變異概率Pm太小時難以產生新的基因結構，太大使遺傳算法成了單純的隨機搜索。一般取Pm=0.01-0.2。

遺傳算法的主要應用領域在于函數優化（非線性、多模型、多目標等），機器人學（移動機器人路徑規劃、關節機器人運動軌跡規劃、細胞機器人的結構優化等），控制（瓦斯管道控制、防避導彈控制、機器人控制等），規劃（生產規劃、并行機任務分配等），設計（VLSI 布局、通信網絡設計、噴氣發動機設計等），組合優化（TSP 問題、背包問題、圖分劃問題等），圖像處理（模式識別、特征提取、圖像恢復等），信號處理（濾波器設計等），人工生命（生命的遺傳進化等）。

3 遺傳算法的研究新動向

3.1 基于遺傳算法的機器學習

這一新的研究方向把遺傳算法從歷史離散的搜索空間的優化搜索算法擴展到具有獨特的規則生成功能嶄新的機器學習算法。這一新的學習機制對于解決人工智能中知識獲取和知識優化精煉的瓶頸難題帶來了希望。遺傳算法作為一種搜索算法從一開始就與機器學習有著密切聯系。分類器系統CS-1 是GA 的創立Holland 教授等實現的第一個基于遺傳算法的機器學習系統。分類器系統在很多領域都得到了應用。例如，分類器系統在學習式多機器人路徑規劃系統中得到了成功應用；Goldberg 研究了用分類器系統來學習控制一個煤氣管道仿真系統；Wilson 研究了一種用于協調可移動式視頻攝像機的感知運動的分類器系統等。

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

遺傳算法正日益和神經網絡、模糊推理以及混沌理論等其它智能計算方法相互滲透和結合，以達到取長補短的作用。近年來在這方面已經取得了不少研究成果，并形成了“計算智能”的研究領域， 這對開拓21 世紀中新的智能計算技術具有重要意義。GA 的出現使神經網絡的訓練（包括連接權系數的優化、網絡空間結構的優化和網絡的學習規劃優化）有了一個嶄新的面貌，目標函數既不要求連續，也不要求可微，僅要求該問題可計算，而且搜索始終遍及整個解空間，因此容易得到全局最優解。

3.3 并行處理的遺傳算法

并行處理的遺傳算法的研究不僅是遺傳算法本身的發展，而且對于新一代智能計算機體系結構的研究都是十分重要的。GA 在操作上具有高度的并行性，許多研究人員都在探索在并行機上高效執行GA 的策略。研究表明，只要通過保持多個群體和恰當地控制群體間的相互作用來模擬并執行過程，即使不使用并行計算機，我們也能提高算法的執行效率。在并GA 的研究方面，一些并GA 模型已經被人們在具體的并行機上執行了；并行GA 可分為兩類：一類是粗粒度并行GA，主要開發群體間的并行性；另一類是細粒GA，主要開發一個群體中的并行性。

3.4 遺傳算法與人工生命的滲透

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

3.5 遺傳算法與進化規則及進化策略的結合

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

參考文獻

[1]張文修，梁怡.遺傳算法的教學基礎[M].西安：西安交通大學出版社，2000.

[2]余建坤，張文彬，陸玉昌.遺傳算法及其應用[J].云南民族學院學報，2002（4）.

[3]蔡自興，徐光.人工智能及應用[M].北京：清華大學出版社，2003.

[4]蔣騰旭.智能優化算法概述[J].電腦知識與技術，2007（8）.

[5]任慶生，葉中行.遺傳算法中常用算子的分析[J].電子學報，2005（5）.

作者簡介

溫歡（1985-），江西南昌人，江西科技學院商學院教務處，本科，研究方向：應用數學