1.1.1 遺傳算法

1962年，美國密歇根大學(xué)J. H. Holland等人[7,8]借鑒了達(dá)爾文的生物進(jìn)化論和孟德爾的遺傳定律的基本思想，通過提取、簡化與抽象提出了遺傳算法（GA）。GA是從一個經(jīng)過基因（Gene）編碼的一定數(shù)目的個體（Individual）組成的種群（Population）開始的，代表了問題可行解集。每個個體實際上是染色體（Chromosome）帶有特征的實體。染色體作為遺傳物質(zhì)的主要載體，其內(nèi)部表現(xiàn)（基因型）是某種基因組合，它決定了個體的外部表現(xiàn)。例如，膚色是由染色體中控制這一特征的某種基因組合決定的。因此，在一開始需要實現(xiàn)從表現(xiàn)型到基因型的映射，即編碼工作。由于仿照基因編碼的工作很復(fù)雜，往往需要進(jìn)行簡化，如二進(jìn)制編碼。初始種群產(chǎn)生之后，按照適者生存和優(yōu)勝劣汰的原理，逐代（Generation）演化產(chǎn)生出越來越好的近似解，在每一代，根據(jù)問題域中個體的適應(yīng)度（Fitness）大小選擇（Selection）個體，并借助于自然遺傳學(xué)的遺傳算子（Genetic Operators）進(jìn)行組合交叉（Crossover）和變異（Mutation），產(chǎn)生出代表新的解集的種群。這個過程將導(dǎo)致種群像自然進(jìn)化一樣，后代種群比前代更加適應(yīng)環(huán)境，末代種群中的最優(yōu)個體經(jīng)過解碼（Decoding），可以作為問題近似最優(yōu)解。

編碼機(jī)制直接制約著GA的性能。二進(jìn)制編碼被廣泛應(yīng)用于各種GA中，但這種編碼方法在連續(xù)函數(shù)離散化時存在映射誤差，因而又提出了很多非二進(jìn)制編碼方法：格雷碼、樹型編碼、量子比特編碼等。

適應(yīng)度函數(shù)將目標(biāo)函數(shù)值轉(zhuǎn)換成適應(yīng)值，用來評價個體的優(yōu)劣，并作為遺傳操作的依據(jù)。適應(yīng)度是指種群中各個個體對環(huán)境的適應(yīng)程度，根據(jù)適應(yīng)度的大小，決定某個個體是繁殖還是死亡，因此適應(yīng)度是進(jìn)化的驅(qū)動力。從生物學(xué)角度看，適應(yīng)度相當(dāng)于“適者生存，生存競爭”的生物生存能力，在進(jìn)化過程中有重要意義。適應(yīng)度通常是費用、盈利、方差等目標(biāo)的表達(dá)式。適應(yīng)度函數(shù)通常根據(jù)目標(biāo)函數(shù)和約束條件來設(shè)計，要確保目標(biāo)函數(shù)變化方向與適應(yīng)度函數(shù)變化方向一致，這是GA的重要搜索依據(jù)。適應(yīng)度函數(shù)的優(yōu)劣決定著算法的收斂性能，以及算法能否跳出局部最優(yōu)解，各種變換尺度策略（如線性尺度變換、指數(shù)尺度變換等）被用來調(diào)節(jié)原適應(yīng)值之間的比例。

遺傳算子主要通過選擇、交叉和變異3種操作來實現(xiàn)搜索。國內(nèi)外很多研究對遺傳算子進(jìn)行改進(jìn)以提高算法性能，S. A. Jafari等人[9]設(shè)計了一種模糊準(zhǔn)則和性別選擇方法，張鈸等人[10]用佳點集方法改進(jìn)了交叉操作，孟偉等人[11]基于蜜蜂進(jìn)化模型將最優(yōu)個體與其余個體分別交叉，楊啟文等人[12]借鑒數(shù)字技術(shù)中的二元邏輯設(shè)計了一種二元變異算子，這些改進(jìn)都能不同程度地提高種群多樣性和進(jìn)化速度，克服早熟收斂。吳少巖等人[13]研究交配算子與其探索子空間的關(guān)系，提出了設(shè)計良好算子的指導(dǎo)性原則，并構(gòu)造出了一種啟發(fā)式交配算子。

總的來說，GA具有較好的全局搜索能力，算法的迭代基于概率機(jī)制以滿足隨機(jī)性特點，容易擴(kuò)展并與其他算法融合。然而，GA不能有效利用反饋信息，往往會造成迭代的冗余，使得算法效率較低，容易進(jìn)入早熟收斂，局部尋優(yōu)能力需要不斷改進(jìn)提高。

GA是一個迭代計算過程，其實施的主要步驟包括編碼、群體初始化、選擇、遺傳操作、評價和終止判定6步，GA流程圖如圖1-1所示。

1. 編碼

編碼的主要任務(wù)是建立解空間與染色體空間中點的一一對應(yīng)關(guān)系。GA通常在染色體空間中進(jìn)行操作。在多數(shù)情況下，不同的編碼方式?jīng)Q定了不同的遺傳操作方式。對編碼的一般原則性要求主要有完備性、健全性和非冗余性。完備性是指解空間中的所有點都能表示為染色體空間中的點，健全性是指染色體空間中的所有點都能表示為解空間中的點，非冗余性是指解空間和染色體空間中的點一一對應(yīng)。

2. 群體初始化

與傳統(tǒng)優(yōu)化方法相比，GA的一個顯著的特點是對群體進(jìn)行操作，所以在進(jìn)化開始時必須進(jìn)行群體初始化，產(chǎn)生進(jìn)化的起點群體。通常隨機(jī)構(gòu)造初始群體，當(dāng)然也可以在初始群體中植入一些具有特殊“性狀”的個體，以加速算法向全局最優(yōu)解收斂。

3. 選擇

GA的選擇操作與生物的自然選擇機(jī)制相類似，它體現(xiàn)了“適者生存，不適者被淘汰”的生物進(jìn)化機(jī)理。實現(xiàn)原則為“性狀”優(yōu)良的個體具有較多的機(jī)會被選進(jìn)交配池產(chǎn)生后代，而“性狀”低劣的個體則具有較少的機(jī)會被選擇。這里的“性狀”通過評價操作進(jìn)行量化。最常用的選擇方式是賭輪選擇、聯(lián)賽選擇和排序選擇。

4. 遺傳操作

遺傳操作被視為GA的核心。它直接影響和決定了GA的優(yōu)化能力，是生物進(jìn)化機(jī)理在GA中最主要的體現(xiàn)。目前，已有適用于各種不同類型問題的多種遺傳操作算子。其中，雜交與變異是最常用的遺傳操作，雜交體現(xiàn)了同一群體中不同個體之間的信息交換，而變異則能維系群體中信息的多樣性。這些遺傳操作在優(yōu)化中的主要作用是以不同的方式不斷產(chǎn)生新的個體。

5. 評價

評價是GA的驅(qū)動力，是GA體現(xiàn)有向搜索、區(qū)別于隨機(jī)搜索的標(biāo)志。它將同一群體中不同個體的優(yōu)劣進(jìn)行數(shù)值標(biāo)量化，為選擇操作提供客觀依據(jù)。確定GA評價準(zhǔn)則主要依賴于要求解的問題。

6. 終止判定

通常依靠經(jīng)驗和運(yùn)行結(jié)果給定的進(jìn)化最大代數(shù)作為終止判據(jù)。

GA的早熟問題（Premature Convergence）是指進(jìn)化過程收斂于非期望的局部極值或群體的最佳個體進(jìn)化到問題的非最優(yōu)解，進(jìn)化過程就停滯不前的現(xiàn)象。早熟問題嚴(yán)重影響了GA的應(yīng)用，目前，還沒有一種通用的解決方法。用GA求解一個復(fù)雜的實際優(yōu)化問題，無法定量、準(zhǔn)確地判斷在優(yōu)化過程中何時出現(xiàn)早熟，因而，控制或消除早熟問題就比較困難。