金玲，劉曉麗，李鵬飛，王妍

華北理工大學(xué)冀唐學(xué)院

遺傳算法綜述

金玲，劉曉麗，李鵬飛，王妍

華北理工大學(xué)冀唐學(xué)院

本文對(duì)遺傳算法的基本概念、運(yùn)算過程和特點(diǎn)做了概述，并在此基礎(chǔ)上分析了遺傳算法的現(xiàn)狀及前景。

遺傳算法；生物進(jìn)化；最優(yōu)化

1.引言

遺傳算法仿效自然選擇下的生物進(jìn)化,是一種仿生物進(jìn)化過程的隨機(jī)化搜索方法,該算法通過有限的代價(jià)來解決搜索和優(yōu)化問題，由于其隨機(jī)性和非線性為其他科學(xué)技術(shù)無法或難以解決的問題提供了新的模型，這與傳統(tǒng)的搜索和優(yōu)化方法不同。

2.基本概念

遺傳算法是仿照自然界適者生存優(yōu)勝劣汰的進(jìn)化規(guī)律得到的一種隨機(jī)化搜索方法。對(duì)于優(yōu)化問題要求一個(gè)求函數(shù)的最大值，可以用下面的數(shù)學(xué)規(guī)劃模型來進(jìn)行描述:

其中(1)式作為目標(biāo)函數(shù)，X是決策變量，(2)式、(3)式作為約束條件，R是基本空間U的子集?？尚薪釾是指滿足約束條件的解，可行解集合R是指滿足約束條件的解所組成的集合。

3.遺傳算法定義

遺傳算法是從一個(gè)種群開始的，對(duì)于數(shù)學(xué)規(guī)劃模型就是從可行解集合開始的。染色體作為遺傳物質(zhì)的主要載體，種群中一定數(shù)目的個(gè)體都是經(jīng)過基因編碼得到的，個(gè)體的基因型決定了這個(gè)個(gè)體的表現(xiàn)型，我們需要通過編碼實(shí)現(xiàn)從表現(xiàn)型到基因型的映射，由于生物體內(nèi)基因編碼的工作是非常復(fù)雜的，所以我們要做一下必要的簡(jiǎn)化例如二進(jìn)制編碼。根據(jù)適者生存優(yōu)勝劣汰的遺傳規(guī)律，首先要確定初代種群，在每一代的種群迭代中再按照個(gè)體的適應(yīng)度函數(shù)以及進(jìn)行交叉、變異算子的運(yùn)算選出較優(yōu)的個(gè)體，進(jìn)入下一代的演化從而逐代產(chǎn)生出一個(gè)最優(yōu)的種群。在逐代演化的過程中，種群的適應(yīng)能力越來越強(qiáng)，最后通過對(duì)末代種群中最優(yōu)個(gè)體進(jìn)行解碼就可以得到數(shù)學(xué)規(guī)劃模型的近似最優(yōu)解。

4.遺傳算法的特點(diǎn)

遺傳算法可以很好的解決搜索問題，具有以下幾方面的特點(diǎn)：

(1)遺傳算法是從一個(gè)種群開始同時(shí)處理種群中的每個(gè)個(gè)體而不是單個(gè)個(gè)體，這是遺傳算法與傳統(tǒng)優(yōu)化算法的最大區(qū)別。遺傳算法是從數(shù)學(xué)規(guī)劃模型的解集開始進(jìn)行嫂索，同時(shí)評(píng)估搜索空間中的多個(gè)解而不是單個(gè)解。傳統(tǒng)優(yōu)化算法是從單個(gè)解開始迭代求最優(yōu)解常常會(huì)陷入局部最優(yōu)解，而遺傳算法不僅減少了這種風(fēng)險(xiǎn)而且易于實(shí)現(xiàn)并行化。

(2)遺傳算法對(duì)個(gè)體的評(píng)估只要借助適應(yīng)度函數(shù)就可以完成，幾乎不需要搜索空間的知識(shí)或其它輔助信息。而適應(yīng)度函數(shù)的定義域可以任意設(shè)定且不會(huì)受到連續(xù)可微的限制，那么這很大程度上擴(kuò)展了遺傳算法的應(yīng)用范圍。

(3)遺傳算法的搜索方向是由概率的變遷規(guī)則來引導(dǎo)，而不是確定性規(guī)則。

(4)遺傳算法在逐代演化的過程中通過得到的信息自行組織搜索時(shí)，硬度較大的個(gè)體相應(yīng)的生存概率也較高并且他獲得的基因結(jié)構(gòu)也更適應(yīng)環(huán)境。遺傳算法具有自適應(yīng)性、自組織性和自學(xué)習(xí)性。

5.運(yùn)算過程

為實(shí)現(xiàn)優(yōu)勝劣汰的進(jìn)化過程就需要根據(jù)環(huán)境適應(yīng)度對(duì)群體中的個(gè)體施加一定的操作，使模型的解在優(yōu)化搜索的角度逐代優(yōu)化并逼近最優(yōu)解，這就是模擬生物基因遺傳的遺傳操作，包括選擇、交叉、變異三個(gè)基本遺傳算子，具有如下特點(diǎn):

(1)選擇算子。選擇是在個(gè)體適應(yīng)度評(píng)估的基礎(chǔ)上從群體中選擇優(yōu)勝淘汰劣質(zhì)個(gè)體的操作，其目的是將較優(yōu)的個(gè)體遺傳到下一代，較優(yōu)的個(gè)體可能是直接遺傳到下一代的也可能是通過配對(duì)交叉產(chǎn)生新個(gè)體再遺傳到下一代的。目前常用的選擇算子有隨機(jī)遍歷抽樣法、適應(yīng)度比例方法、局部選擇法等。

(2)交叉算子。交叉是指把兩個(gè)父代個(gè)體的部分結(jié)構(gòu)加以替換重組而生成新個(gè)體的操作，交叉算子期望將有益基因組合在一起，對(duì)種群中的兩個(gè)個(gè)體根據(jù)交叉率隨機(jī)交換某些基因產(chǎn)生新的基因組合。生物進(jìn)化過程中遺傳基因重組發(fā)揮了主要作用，交叉算子在遺傳算法中的地位就等同于基因重組，交叉算子很大程度上提高了遺傳算法的搜索能力。

(3)變異算子。變異算子是指改變?nèi)后w中個(gè)體串的某些基因座上的基因值。變異算子使遺傳算法具有局部的隨機(jī)搜索能力，這種局部隨機(jī)搜索能力在遺傳算法通過交叉算子已接近最優(yōu)解鄰域時(shí)可以加速向最優(yōu)解收斂。另外，變異算子還能防止遺傳算法出現(xiàn)未成熟收斂現(xiàn)象從而維持群體多樣性。

交叉算子可以提高遺傳算法的全局搜索能力，而變異算子對(duì)提高遺傳算法的局部搜索能力有幫助，交叉算子和變異算子之間既相互配合又相互競(jìng)爭(zhēng)，也正因?yàn)槿绱诉z傳算法具有均衡的搜索能力。那么，交叉算子和變異算子如何有效地配合使用就成為目前遺傳算法的一個(gè)重要研究?jī)?nèi)容。

(4)終止條件。當(dāng)出現(xiàn)以下情況時(shí)算法終止：最優(yōu)群體和個(gè)體的適應(yīng)度不再上升；最優(yōu)個(gè)體的適應(yīng)度達(dá)到給定的閥值；迭代次數(shù)達(dá)到預(yù)設(shè)的代數(shù)，預(yù)設(shè)的代數(shù)一般為100-500代。

6.遺傳算法的現(xiàn)狀

進(jìn)入90年代遺傳算法在理論研究和應(yīng)用研究方面都取得了很大的進(jìn)展。遺傳算法不但應(yīng)用研究的領(lǐng)域擴(kuò)大而且利用遺傳算法解決優(yōu)化和規(guī)則問題的能力也顯著提高，同時(shí)對(duì)于產(chǎn)業(yè)應(yīng)用方面的研究也在摸索之中。

由于遺傳算法思想簡(jiǎn)單、易于實(shí)現(xiàn)在許多應(yīng)用領(lǐng)域例取得了豐碩的成果與進(jìn)展，例如如函數(shù)優(yōu)化、組合優(yōu)化、圖像處理和模式識(shí)別、人工生命、生產(chǎn)調(diào)度問題、機(jī)器學(xué)習(xí)和自動(dòng)控制等領(lǐng)域。對(duì)于遺傳算法，我們應(yīng)該從收斂性，編碼方法，增強(qiáng)算子適應(yīng)性，適應(yīng)度函數(shù)進(jìn)行更為深入的研究。

[1]遺傳算法理論及應(yīng)用.周明，孫樹棟編著.國防工業(yè)出版社1999

[2]遺傳算法：理論、應(yīng)用與軟件實(shí)現(xiàn).王小平、曹立明著.西安交通大學(xué)出版社2002

[3]遺傳算法的基本理論與應(yīng)用.李敏強(qiáng)等著.科學(xué)出版社2002