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

徐文鋒

遺傳算法起源于上個世紀(jì)60年代，是一類模擬生物進(jìn)化的智能優(yōu)化算法，遺傳算法是通過對一組編碼表示進(jìn)行簡單的遺傳操作和優(yōu)勝劣汰的自然選擇來指導(dǎo)學(xué)習(xí)和確定搜索的方向。算法從一組隨機(jī)產(chǎn)生的初始群體開始搜索過程，以適應(yīng)度函數(shù)為依據(jù)，采用基于適應(yīng)值比例的選擇策略在當(dāng)前種群中選擇個體，通過雜交和變異來產(chǎn)生下一代種群。如此模仿生命的進(jìn)化一代代演化下去，直到滿足期望的終止條件為止。目前，遺傳算法已成為進(jìn)化計算研究的一個重要分支。

一、遺傳算法的原理

遺傳算法是模擬達(dá)爾文的生物自然選擇學(xué)說和自然界的生物進(jìn)化過程的一種自適應(yīng)全局概率搜索算法。在解決具體問題時先大致確定問題的潛在解的一個集合，這個集合就是算法的初始種群。種群由計算機(jī)生成（一般是隨機(jī)生成）的一定數(shù)目的個體組成，個體就是潛在解的計算機(jī)編碼，那么我們最后要求的解就由這些初始生成的個體進(jìn)化而來。每個個體具有其自的特征（攜帶不同基因），我們根據(jù)這些個體的不同的特征來確定其存活到下一代的可能性高低，按照優(yōu)勝劣汰的法則，我們由父代來產(chǎn)生子代，如此來繁衍。

當(dāng)然在具體的進(jìn)化過程中為了保持種群多樣性防止過早收斂，還要在其中使個體以一定小概率發(fā)生變異。這樣在最后滿足收斂條件后的種群最優(yōu)個體就是問題的近似最優(yōu)解。遺傳算法的實現(xiàn)過程主要包括編碼、產(chǎn)生群體、計算適應(yīng)度、復(fù)制、交換、變異等操作。

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

遺傳算法提供了一種求解復(fù)雜系統(tǒng)優(yōu)化問題的通用框架，它不依賴于問題的具體領(lǐng)域，對問題的種類有很強(qiáng)的魯棒性。所以，廣泛應(yīng)用于很多學(xué)科。下面是目前遺傳算法的主要應(yīng)用領(lǐng)域：

1、函數(shù)優(yōu)化

工程上經(jīng)常會遇到在多準(zhǔn)則或多設(shè)計目標(biāo)下設(shè)計和決策的問題，如果這些目標(biāo)是相背的，需要找到滿足這些目標(biāo)的最佳設(shè)計方案。通常的做法是根據(jù)某有效函數(shù)將多目標(biāo)合成單一目標(biāo)來進(jìn)行優(yōu)化。

函數(shù)優(yōu)化是遺傳算法的經(jīng)典應(yīng)用領(lǐng)域，也是對遺傳算法進(jìn)行性能評價的常用算例。很多人構(gòu)造出了各種各樣的復(fù)雜形式的測試函數(shù)。有連續(xù)函數(shù)也有離散函數(shù)，有凸函數(shù)也有凹函數(shù)，有低維函數(shù)也有高維函數(shù)，有確定函數(shù)也有隨機(jī)函數(shù)，有單峰值函數(shù)也有多峰值函數(shù)等。用這些幾何特性各具特色的函數(shù)來評價遺傳算法的性能，更能反映算法的本質(zhì)效果而對于一些非線性、多模型、多目標(biāo)的函數(shù)優(yōu)化問題，用其他優(yōu)化方法較難求解。而遺傳算法卻可以方便地得到較好的結(jié)果。

2、組合優(yōu)化

組合優(yōu)化是指在給定約束條件下，求解目標(biāo)函數(shù)的最優(yōu)值。隨著問題規(guī)模的增大，組合優(yōu)化問題的搜索空間也急劇擴(kuò)大。有時在目前的計算機(jī)上用枚舉法很難或甚至不可能求出其精確最優(yōu)解。對這類復(fù)雜問題，人們已意識到應(yīng)把主要精力放在尋求其最佳求解上，而遺傳算法是尋求這種解的最佳工具之一。現(xiàn)如今，遺傳算法已經(jīng)在旅行商問題、背包問題、裝箱問題、布局優(yōu)化、圖形劃分問題等各種具問題中得到成功的應(yīng)用。

3、生產(chǎn)調(diào)度問題

生產(chǎn)調(diào)度問題在很多情況下建立起來的數(shù)學(xué)模難以精確求解，即使經(jīng)過一些簡化之后可以進(jìn)行求解.也會因簡化得太多而使得求解結(jié)果與實際相差甚遠(yuǎn)。目前在現(xiàn)實生產(chǎn)中主要是靠一些經(jīng)驗來進(jìn)行調(diào)度?，F(xiàn)在遺傳算法已成為解決復(fù)雜調(diào)度問題的有效下具。在單件生產(chǎn)車間調(diào)度、流水線生產(chǎn)間調(diào)度、生產(chǎn)規(guī)劃、任務(wù)分配等方面遺傳算法都得到了有效的應(yīng)用。

4、自動控制

許多控制領(lǐng)域問題，當(dāng)考慮到系統(tǒng)優(yōu)化、自適應(yīng)、自組織和自學(xué)習(xí)等方面的要求時，一般存在許多常規(guī)方法難以湊效的困難。遺傳算法已在其中得到了初步的應(yīng)用，并顯示出良好的效果。例如用遺傳算法進(jìn)行航空控制系統(tǒng)的優(yōu)化、使用遺傳算法設(shè)計空間交會控制器、基于遺傳算法的模糊控制器的優(yōu)化設(shè)計、基于遺傳算法的參數(shù)辨識、基于遺傳算法的模糊控制規(guī)則的學(xué)習(xí)、利用遺傳算法進(jìn)行人工神經(jīng)網(wǎng)絡(luò)的結(jié)構(gòu)優(yōu)化設(shè)計和權(quán)值學(xué)習(xí)等。都顯出了遺傳算法在這此領(lǐng)域中應(yīng)用的可能性。

5、機(jī)器人學(xué)

機(jī)器人是一類復(fù)雜的難以精確建模的人工系統(tǒng)，而遺傳算法的起源就來自于人工自適應(yīng)系統(tǒng)的研究。所以，機(jī)器人學(xué)理所當(dāng)然地成為遺傳算法的一個重要應(yīng)用領(lǐng)域。例如，遺傳算法已經(jīng)在移動機(jī)器人路徑規(guī)劃、關(guān)節(jié)機(jī)器人運動軌跡規(guī)劃、機(jī)器人逆運動學(xué)求解、細(xì)胞機(jī)器人的結(jié)構(gòu)優(yōu)化和行為協(xié)調(diào)等方而得到研究和應(yīng)用。

6、圖像處理

圖像處理和模式識別是計算機(jī)視覺中的一個重要領(lǐng)域。在圖像處理過程中，如掃描、特征提取、圖像分割等不可避免地會存在誤差，從而影響圖像的效果。如何使這些誤差最小是使計算機(jī)視覺達(dá)到實用化的重要要求。目前遺傳算法已經(jīng)在圖像校準(zhǔn)、圖像分割、幾何形狀識別、圖像壓縮、三維重建優(yōu)化以及圖像檢索、模式識別（包括漢字識別）、圖像恢復(fù)、圖像邊緣特征提取等方而得到了很好的應(yīng)用。

7、人工生命

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

8、機(jī)器學(xué)習(xí)

學(xué)習(xí)能力是高級自適應(yīng)系統(tǒng)所具備的能力之一，基于遺傳算法的機(jī)器學(xué)習(xí)，特別是分類器系統(tǒng)，在很多領(lǐng)域中都得到了應(yīng)用。例如，遺傳算法被用于學(xué)習(xí)模糊控制規(guī)則，利用遺傳算法來學(xué)習(xí)隸屬度函數(shù)，從而更好地改進(jìn)了模糊系統(tǒng)的性能；基于遺傳算法的機(jī)器學(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í)式多機(jī)器人路徑規(guī)劃系統(tǒng)中得到了成功的應(yīng)用。

9、數(shù)據(jù)挖掘

數(shù)據(jù)挖掘是從大型數(shù)據(jù)庫中提取隱含的、先前未知的、有潛在應(yīng)用價值的知識和規(guī)則。許多數(shù)據(jù)挖掘問題可看成是搜索問題，數(shù)據(jù)庫看作是搜索空間，挖掘算法看作是搜索策略。因此，應(yīng)用遺傳算法在數(shù)據(jù)庫中進(jìn)行搜索，對隨機(jī)產(chǎn)生的一組規(guī)則進(jìn)行進(jìn)化.直到數(shù)據(jù)庫能被該組規(guī)則覆蓋，從而挖掘出隱含在數(shù)據(jù)庫中的規(guī)則。Sunil已成功地開發(fā)了一個基于遺傳算法的數(shù)據(jù)挖掘下具。利用該工具對兩個飛機(jī)失事的真實數(shù)據(jù)庫進(jìn)行了數(shù)據(jù)挖掘?qū)嶒?，結(jié)果表明遺傳算法是進(jìn)行數(shù)據(jù)挖掘的有效方法之一。

除此之外，隨著對遺傳算法的進(jìn)一步研究和發(fā)展，遺傳算法將在更多的領(lǐng)域發(fā)揮其作用?，F(xiàn)在遺傳算法還分別在經(jīng)濟(jì)學(xué)、免疫系統(tǒng)、生態(tài)學(xué)、進(jìn)化現(xiàn)象和學(xué)習(xí)現(xiàn)象、社會經(jīng)濟(jì)問題等方面都有所應(yīng)用。

參考文獻(xiàn)

1、錢志勤、騰弘飛，孫治國。人機(jī)交互的遺傳算法機(jī)器在約束布局優(yōu)化中的應(yīng)用.計算機(jī)學(xué)報，2001

2、馬玉明，賀愛玲，李愛民. 遺傳算法的理論研究綜述. 山東輕工業(yè)學(xué)院學(xué)報， 2004，18（3）：77～80

3、吉根林. 遺傳算法研究綜述. 計算機(jī)應(yīng)用與軟件， 2004，21（2）：69～73

4、馬光文，王黎.遺傳算法在水電站優(yōu)化調(diào)度中的應(yīng)用.水科學(xué)進(jìn)展，1997，8

5、姚文俊. 遺傳算法及其研究進(jìn)展. 計算機(jī)與數(shù)字工程， 2004，32（4）：41～43

6、高艷霞，劉峰，王道洪. 改進(jìn)型遺傳算法及其應(yīng)用研究. 上海大學(xué)學(xué)報， 2004（10）：249～253

7、馬立肖，王江晴. 遺傳算法在組合優(yōu)化問題中的應(yīng)用. 計算機(jī)工程與科學(xué)， 2005，27（7）：72～73、82