演化算法的計算復(fù)雜性研究.pdf

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

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

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

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

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

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