遺傳算法研究綜述

摘 要：通過介紹遺傳算法的基本概念和基本原理，說明了遺傳算法應(yīng)用領(lǐng)域，指出了遺傳算法在應(yīng)用中的幾個(gè)關(guān)鍵問題，并介紹了遺傳算法研究新動(dòng)向及存在的問題。

關(guān)鍵詞：遺傳算法；編碼機(jī)制；遺傳算子；適應(yīng)度函數(shù)

1 遺傳算法的基本原理

遺傳算法類似于自然進(jìn)化，通過作用于染色體上基因?qū)ふ易詈玫娜旧w來求解問題。與自然界相似，遺傳算法對(duì)求解問題的本身一無所知，它所需要的僅是對(duì)遺傳算法所產(chǎn)生的染色體有更多的繁殖機(jī)會(huì)。在遺傳算法中，通過隨機(jī)方式產(chǎn)生若干個(gè)所求解問題的數(shù)字編碼，即染色體，形成初始種群；通過適應(yīng)度函數(shù)給每個(gè)個(gè)體一個(gè)數(shù)值評(píng)價(jià)，淘汰低適應(yīng)度的個(gè)體，選擇高適應(yīng)度的個(gè)體參加遺傳操作，經(jīng)過遺傳操作后的個(gè)體集合成下一代新的種群，對(duì)這個(gè)新種群進(jìn)行下一輪進(jìn)化。

2 遺傳算法的應(yīng)用

遺傳算法在應(yīng)用中最關(guān)鍵的問題有如下3 個(gè)。

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

（2）適應(yīng)函數(shù)的確定。適應(yīng)函數(shù)（fitness function）也稱對(duì)象函數(shù)（object function），這是問題求解品質(zhì)的測(cè)量函數(shù)；往往也稱為問題的“環(huán)境”。一般可以把問題的模型函數(shù)作為對(duì)象函數(shù)；但有時(shí)需要另行構(gòu)造。

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

遺傳算法的主要應(yīng)用領(lǐng)域在于函數(shù)優(yōu)化（非線性、多模型、多目標(biāo)等），機(jī)器人學(xué)（移動(dòng)機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化等），控制（瓦斯管道控制、防避導(dǎo)彈控制、機(jī)器人控制等），規(guī)劃（生產(chǎn)規(guī)劃、并行機(jī)任務(wù)分配等），設(shè)計(jì)（VLSI 布局、通信網(wǎng)絡(luò)設(shè)計(jì)、噴氣發(fā)動(dòng)機(jī)設(shè)計(jì)等），組合優(yōu)化（TSP 問題、背包問題、圖分劃問題等），圖像處理（模式識(shí)別、特征提取、圖像恢復(fù)等），信號(hào)處理（濾波器設(shè)計(jì)等），人工生命（生命的遺傳進(jìn)化等）。

3 遺傳算法的研究新動(dòng)向

3.1 基于遺傳算法的機(jī)器學(xué)習(xí)

這一新的研究方向把遺傳算法從歷史離散的搜索空間的優(yōu)化搜索算法擴(kuò)展到具有獨(dú)特的規(guī)則生成功能嶄新的機(jī)器學(xué)習(xí)算法。這一新的學(xué)習(xí)機(jī)制對(duì)于解決人工智能中知識(shí)獲取和知識(shí)優(yōu)化精煉的瓶頸難題帶來了希望。遺傳算法作為一種搜索算法從一開始就與機(jī)器學(xué)習(xí)有著密切聯(lián)系。分類器系統(tǒng)CS-1 是GA 的創(chuàng)立Holland 教授等實(shí)現(xiàn)的第一個(gè)基于遺傳算法的機(jī)器學(xué)習(xí)系統(tǒng)。分類器系統(tǒng)在很多領(lǐng)域都得到了應(yīng)用。例如，分類器系統(tǒng)在學(xué)習(xí)式多機(jī)器人路徑規(guī)劃系統(tǒng)中得到了成功應(yīng)用；Goldberg 研究了用分類器系統(tǒng)來學(xué)習(xí)控制一個(gè)煤氣管道仿真系統(tǒng)；Wilson 研究了一種用于協(xié)調(diào)可移動(dòng)式視頻攝像機(jī)的感知運(yùn)動(dòng)的分類器系統(tǒng)等。

3.2 遺傳算法與其他計(jì)算智能方法的相互滲透和結(jié)合

遺傳算法正日益和神經(jīng)網(wǎng)絡(luò)、模糊推理以及混沌理論等其它智能計(jì)算方法相互滲透和結(jié)合，以達(dá)到取長補(bǔ)短的作用。近年來在這方面已經(jīng)取得了不少研究成果，并形成了“計(jì)算智能”的研究領(lǐng)域， 這對(duì)開拓21 世紀(jì)中新的智能計(jì)算技術(shù)具有重要意義。GA 的出現(xiàn)使神經(jīng)網(wǎng)絡(luò)的訓(xùn)練（包括連接權(quán)系數(shù)的優(yōu)化、網(wǎng)絡(luò)空間結(jié)構(gòu)的優(yōu)化和網(wǎng)絡(luò)的學(xué)習(xí)規(guī)劃優(yōu)化）有了一個(gè)嶄新的面貌，目標(biāo)函數(shù)既不要求連續(xù)，也不要求可微，僅要求該問題可計(jì)算，而且搜索始終遍及整個(gè)解空間，因此容易得到全局最優(yōu)解。

3.3 并行處理的遺傳算法

并行處理的遺傳算法的研究不僅是遺傳算法本身的發(fā)展，而且對(duì)于新一代智能計(jì)算機(jī)體系結(jié)構(gòu)的研究都是十分重要的。GA 在操作上具有高度的并行性，許多研究人員都在探索在并行機(jī)上高效執(zhí)行GA 的策略。研究表明，只要通過保持多個(gè)群體和恰當(dāng)?shù)乜刂迫后w間的相互作用來模擬并執(zhí)行過程，即使不使用并行計(jì)算機(jī)，我們也能提高算法的執(zhí)行效率。在并GA 的研究方面，一些并GA 模型已經(jīng)被人們?cè)诰唧w的并行機(jī)上執(zhí)行了；并行GA 可分為兩類：一類是粗粒度并行GA，主要開發(fā)群體間的并行性；另一類是細(xì)粒GA，主要開發(fā)一個(gè)群體中的并行性。

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

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

3.5 遺傳算法與進(jìn)化規(guī)則及進(jìn)化策略的結(jié)合

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

參考文獻(xiàn)

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

[2]余建坤，張文彬，陸玉昌.遺傳算法及其應(yīng)用[J].云南民族學(xué)院學(xué)報(bào)，2002（4）.

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

[4]蔣騰旭.智能優(yōu)化算法概述[J].電腦知識(shí)與技術(shù)，2007（8）.

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

作者簡介

溫歡（1985-），江西南昌人，江西科技學(xué)院商學(xué)院教務(wù)處，本科，研究方向：應(yīng)用數(shù)學(xué)