第1章
緒論

1.1 進化計算簡介

生命自從在地球上誕生以來，就開始了漫長的演化歷程，逐步從低級、簡單的生物發(fā)展為高級、復雜的生物。生物進化的原因有著各種不同的解釋，其中，達爾文（C. R. Darwin）的自然選擇學說被廣泛認同。依據達爾文的進化論，各種生物要生存下來，都要經歷“自然選擇，適者生存”的過程；每個物種在不斷的發(fā)展過程中都越來越適應環(huán)境；物種的每個個體的基本特征被后代所繼承，但后代又不完全與自己的父代相同；在個體的生存與發(fā)展中，那些更能適應環(huán)境的個體特征能被保留下來，體現(xiàn)了適者生存的原理。根據孟德爾（G. J. Mendel）和摩根（T. H. Morgan）的遺傳學，遺傳物質作為一種指令遺傳碼封裝在每個細胞中，并以基因的形式包含在染色體中；每個基因有特殊的位置并控制生物某個特殊的性質；不同的基因組合產生的個體對環(huán)境的適應性不同，通過基因雜交和基因突變可能產生對環(huán)境適應性強的后代；經過優(yōu)勝劣汰的自然選擇，適應值高的基因結構得以保存下來。在一定的環(huán)境影響下，生物物種通過自然選擇、基因交換和變異等過程進行繁殖生長，形成了生物的整個進化過程。

生物進化需要4個基本條件：

（1）存在由多個生物個體組成的種群。

（2）群體具有多樣性，即生物個體之間存在差異。

（3）種群能夠繁衍。

（4）不同個體具有不同的環(huán)境生存能力，具有優(yōu)良基因結構的個體繁殖能力強，反之則弱。

生物群體的進化機制有以下3種基本形式。

1. 自然選擇

控制生物個體群體行為的發(fā)展方向，能夠適應環(huán)境變化的生物個體具有更高的生存能力，使得它們在種群中的數量不斷增加，同時該生物個體所具有的染色體性狀特征在自然選擇過程中得以保留。

2. 雜交

通過雜交隨機組合來自父代染色體上的遺傳物質，產生不同于它們父代的染色體。生物進化過程不需要記憶，能很好地適應自然環(huán)境的信息都包含在當前生物體所攜帶的染色體的基因庫中，并由子代個體繼承下來。

3. 突變

隨機改變父代個體的染色體上的基因結構，產生具有新染色體的子代個體。變異是一種不可逆過程，具有突發(fā)性、間斷性和不可預測性，對于保證群體的多樣性具有不可替代的作用。

此外，生物進化是一個開放的過程，自然界對進化中的生物群體提供及時的反饋信息，或稱外界對生物的評價。評價反映了生物的生存價值和機會。在基于相同環(huán)境的生存競爭中，生存價值低的個體被淘汰，具有較高生存價值的個體則能生存下來，這反映了生物進化的外部動力機制。

進化計算（Evolutionary Computation，EC）的基本思想來源于達爾文的進化論，以及孟德爾和摩根的遺傳學說。進化算法通過程序迭代模擬這一過程，即把要解決的問題看作環(huán)境，一些隨機生成的解當作初始種群，效仿生物的遺傳方式，主要采用復制、交換和突變這三種遺傳操作，衍生出下一代的個體；再根據適應度的大小進行個體的優(yōu)勝劣汰，提高新一代群體的質量，經過多次迭代，逐步尋求最優(yōu)解。與傳統(tǒng)的基于微積分的方法和窮舉法等優(yōu)化算法相比，進化計算是一種成熟的具有高穩(wěn)健性和廣泛適用性的全局優(yōu)化方法，具有自組織、自適應、自學習的特性，能夠不受問題性質的限制，有效地處理傳統(tǒng)優(yōu)化算法難以解決的復雜問題。

進化算法是一種全局性隨機搜索算法，不是盲目搜索，也不是窮舉搜索，而是以目標函數為指導（既不需要計算目標函數的導數和梯度，也不要求目標函數具有連續(xù)性）進行搜索。進化算法具有內在的隱含并行性和全局尋優(yōu)能力，不斷借助交叉和變異產生新個體，擴大搜索范圍，因此它不容易陷入局部最優(yōu)解，并能以較大的概率找到全局最優(yōu)解。

進化計算包括遺傳算法（Genetic Algorithm，GA），進化策略（Evolutionary Strategies，ES），進化規(guī)劃（Evolutionary Programming，EP），遺傳編程（Genetic Programming，GP），差分進化算法（Differential Evolution Algorithm，DEA）等[1-25]。