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

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

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

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

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

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

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