演化算法的計算復雜性研究.pdf

1、演化算法是受進化論啟發(fā)而提出的一大類隨機優(yōu)化算法。該類算法將進化論“物競天擇，適者生存”的思想用于求解優(yōu)化問題，在計算機科學界得到了廣泛而持久的關注。它興起于上世紀六十年代，蓬勃發(fā)展于八十年代和九十年代，最終形成人工智能領域的一個分支—演化計算。總體來說，演化計算是一門實驗科學，它的絕大部分工作都立足于模擬實驗和實際應用。究其原因，這類算法復雜的隨機行為使得嚴密的理論研究(尤其是計算復雜性研究)難以開展。為了更好地理解演化算法復雜的隨機

2、行為從而設計出更高效的演化算法，本文從多個方面開展演化算法的計算復雜性研究，以期增強演化計算領域的理論基礎：我們不僅關注更貼近實際的經典演化算法(遺傳算法)，也關注學術界流行的新型演化算法；我們不僅關注求解傳統(tǒng)靜態(tài)優(yōu)化問題的演化算法，也關注求解動態(tài)優(yōu)化問題的演化算法；我們不僅關注算法的理論研究，也關注理論結果的實際意義。本文的主要貢獻包括：
　　 (1)研究了種群經典演化算法的計算復雜性。早期的理論研究常常關注簡單但脫離實際的算

3、法模型，這些簡化的算法模型距離實際應用中的經典演化算法還有相當大的差距。而本文考慮在算法形式以及運行機制上更貼近實際的種群經典演化算法，為該類算法的時間復雜度分析提出了一種新穎的、系統(tǒng)的方法，并將此方法應用于分析種群規(guī)模不同的經典演化算法在若干單峰和多峰優(yōu)化問題上的時間復雜度。在演化計算領域，上述工作第一次給出了(N+N)經典演化算法(算法的父代種群和子代種群規(guī)模相等)時間復雜度的專用分析方法，從而從理論上分析了不同的種群規(guī)模對種群演化

4、算法性能的影響。
　　 (2)研究了一類新型演化算法(分布評估算法)的計算復雜性。與直接進化種群的經典演化算法不同，這類算法通過在線調整概率模型來間接地進化種群。在分布評估算法興起和發(fā)展的近二十年來，絕大部分研究都局限于實驗觀察。雖然有少量研究者關注種群分布評估算法的收斂性，但還沒有研究者成功地對這類算法的時間復雜度進行過嚴密的理論研究。本文為分布評估算法的時間復雜度分析提出一種一般性的研究思路?；谠撍悸罚疚姆治隽霜毩⑦吘壏?/p>

5、布算法(分布評估算法的一種實例)的時間復雜度，并從理論上驗證了對算法的概率模型進行“松弛”的必要性和有效性。在演化計算領域，這項工作第一次為分布評估算法的計算復雜性分析提出了一般性的研究思路，并從理論上嚴密地分析了種群分布評估算法的時間復雜度，為分布評估算法的計算復雜性研究作出了突破性的貢獻。
　　 (3)研究了在動態(tài)優(yōu)化問題背景下隨時間可變的變異率策略(隨著算法的運行，變異率參數(shù)可發(fā)生變化)對經典演化算法性能的影響。在演化計算

6、領域，許多研究者對引入適應性變異率策略、自適應變異率策略來提升算法性能抱有較大期望。而本文通過計算復雜性研究發(fā)現(xiàn)，在某些動態(tài)優(yōu)化問題上，任意隨時間可變的變異率策略都不比固定變異率策略具本質上的優(yōu)勢?；谶@個結果，本文建議在求解動態(tài)優(yōu)化問題時，如果缺乏先驗知識，演化算法最好不要使用自適應變異率等可變變異率策略，而是按照奧坎姆剃刀原則使用簡單的固定變異率策略。在演化計算領域，這項工作第一次系統(tǒng)地分析了任意隨時間可變的(如自適應)變異率對算法