運(yùn)用改進(jìn)直方圖模型的分布估計(jì)算法求解連續(xù)空間優(yōu)化問(wèn)題.pdf

1、近些年來(lái)，越來(lái)越多的學(xué)者和研究人員關(guān)注智能優(yōu)化領(lǐng)域，智能優(yōu)化算法因而得到廣泛地研究，并且應(yīng)用到多個(gè)領(lǐng)域，例如生物信息學(xué)、數(shù)據(jù)挖掘、模式識(shí)別、城市規(guī)劃和軟件工程管理優(yōu)化，等等。在智能優(yōu)化算法中，很多算法都是大家熟悉或者有所聽聞的，其中包括遺傳算法(Genetic Algorithm，GA)、粒子群算法(Particle Swarm Optimization，PSO)、蟻群算法(Ant ColonyOptimization，ACO)、量子演

2、化算法(Quantum Evolutionary Algorithm，QEA)，盡管這些算法在解決傳統(tǒng)的離散問(wèn)題或者傳統(tǒng)的連續(xù)問(wèn)題都有較好的效果，但是對(duì)于一些更復(fù)雜的問(wèn)題，這些算法很難使用傳統(tǒng)方式進(jìn)行解決?，F(xiàn)實(shí)生活中的很多問(wèn)題都可以抽象為連續(xù)優(yōu)化問(wèn)題，如果算法能夠很好的解決這些連續(xù)優(yōu)化問(wèn)題，那么現(xiàn)實(shí)生活中的很多問(wèn)題就游刃而解了。
　　 分布估計(jì)算法是智能優(yōu)化領(lǐng)域的一個(gè)新興的隨機(jī)優(yōu)化算法，也是當(dāng)前智能優(yōu)化領(lǐng)域的研究熱點(diǎn)。分布估計(jì)算

3、法是將概率統(tǒng)計(jì)理論和遺傳算法思路相結(jié)合，形成的一種全新的智能進(jìn)化模式。分布估計(jì)算法通過(guò)概率統(tǒng)計(jì)的手段建立解空間內(nèi)種群個(gè)體分布的概率模型，然后對(duì)概率模型隨機(jī)采樣產(chǎn)生新的群體，接著更新概率模型，如此反復(fù)進(jìn)行。分布估計(jì)算法摒棄了傳統(tǒng)遺傳算法的交叉操作(Crossover Operation)和變異操作(Mutation Operation)，是一種全新的先進(jìn)的進(jìn)化模式，它通過(guò)概率圖模型對(duì)變量之間的關(guān)系進(jìn)行建模，從而能夠解決多變量相關(guān)的優(yōu)化問(wèn)題

4、。
　　 然而，傳統(tǒng)的分布估計(jì)算法用于解決離散問(wèn)題(例如背包問(wèn)題、最大團(tuán)問(wèn)題)。實(shí)際上，現(xiàn)實(shí)生活中很多領(lǐng)域都屬于連續(xù)問(wèn)題，因此將分布估計(jì)算法應(yīng)用到連續(xù)問(wèn)題是一個(gè)很有用的研究。實(shí)際上，已經(jīng)有一些學(xué)者和研究人員嘗試將分布估計(jì)算法改進(jìn)為能夠解決連續(xù)問(wèn)題的算法，但是效果都不是很好，因此分布估計(jì)算法也不能應(yīng)用到實(shí)際的連續(xù)問(wèn)題中(例如求解基于TOY模型的蛋白質(zhì)折疊結(jié)構(gòu)預(yù)測(cè)問(wèn)題)。這篇文章則提出了一種新穎的方式改進(jìn)傳統(tǒng)分布估計(jì)算法使其能夠很好

5、地解決連續(xù)問(wèn)題，在這篇文章里，我們稱其為基于直方圖的分布估計(jì)算法(Population Based Incremental Learning algori thm using Hi stogramprobabilistic model for Continuous optimization，HPBILc)。我們使用了直方圖概率模型(Histogram Model)作為變量的概率分布，通過(guò)使用基于群體的累計(jì)增量技術(shù)(Population

6、Based Accumulation Strategy)和區(qū)域細(xì)分技術(shù)(Sub-dividing Strategy)來(lái)更新直方圖模型，使用均勻分布法(UniformDistribution Strategy)進(jìn)行個(gè)體采樣。其中，直方圖概率模型可以理解為將待解決問(wèn)題的某一變量的連續(xù)空間細(xì)分為多個(gè)小區(qū)間，每個(gè)小區(qū)間擁有一個(gè)取值概率，取值概率的大小就是該空間的柱狀高度?；谌后w的累計(jì)增量技術(shù)主要是能夠根據(jù)算法抽取出來(lái)的優(yōu)秀候選解的雙向反饋信息

7、更新柱狀的高度，使得較有可能獲取更優(yōu)解的小區(qū)間的柱狀高度更高，較少可能獲取更優(yōu)解的小區(qū)間的柱狀高度更低。區(qū)域細(xì)分技術(shù)則是針對(duì)某一特定小區(qū)間的柱狀高度高于某一臨界值，則對(duì)該小區(qū)間細(xì)分為更小的小區(qū)間，使得區(qū)間不斷細(xì)化，在不斷細(xì)化過(guò)程中，算法可以得到更為精確的解。在實(shí)驗(yàn)部分，我們使用了經(jīng)典的23個(gè)連續(xù)函數(shù)問(wèn)題進(jìn)行測(cè)試，并將測(cè)試結(jié)果和經(jīng)典的FEP，最近幾年文獻(xiàn)中的分布估計(jì)算法進(jìn)行了比較，并且用圖示分析HPBILc的收斂性。我們也將HPBILc應(yīng)