基于和聲搜索算法求解組合優(yōu)化問題

《基于和聲搜索算法求解組合優(yōu)化問題》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。

1、基于和聲搜索算法求解組合優(yōu)化問題　　0引言　　　　　　當(dāng)前，演化計算領(lǐng)域新算法不斷涌現(xiàn)，繼遺傳算法(GeneticAlgorithm,GA)［1］、蟻群優(yōu)化(AntColonyOptimization,ACO)［2］、粒子群優(yōu)化(ParticleSwarmOptimization,PSO)［3］和差分演化(DifferentialEvolution,DE)［4］之后，又先后出現(xiàn)了混合蛙跳算法(ShuffledAlgorithm,SFLA)［5,6］、螢火蟲算法(FireflyAlgorit

2、hm,FA)［7］與和聲搜索算法(HarmonySearchAlgorithm,HSA)［8］等多種新型進(jìn)化算法。其中，HSA是由Geem等［8］于2001年提出的一種新型進(jìn)化算法，已被應(yīng)用于求解數(shù)值優(yōu)化問題、流水線調(diào)度問題和結(jié)構(gòu)工程優(yōu)化問題［8-13］。為了能夠應(yīng)用HSA求解具有二進(jìn)制編碼的組合最優(yōu)化問題，本文提出了一種二進(jìn)制和聲搜索算法(BinaryHarmonySearchAlgorithm,BHSA)，并利用BHSA分別求解著名的k.可滿足性問題(k.SATisfiabilit

3、y,k.SAT)和背包問題()，通過對大規(guī)模k.SAT實(shí)例和實(shí)例的計算對比表明：BHSA是一種比二進(jìn)制粒子群優(yōu)化(BinaryBPSO,基于和聲搜索算法求解組合優(yōu)化問題　　0引言　　　　　　當(dāng)前，演化計算領(lǐng)域新算法不斷涌現(xiàn)，繼遺傳算法(GeneticAlgorithm,GA)［1］、蟻群優(yōu)化(AntColonyOptimization,ACO)［2］、粒子群優(yōu)化(ParticleSwarmOptimization,PSO)［3］和差分演化(DifferentialEvolution,D

4、E)［4］之后，又先后出現(xiàn)了混合蛙跳算法(ShuffledAlgorithm,SFLA)［5,6］、螢火蟲算法(FireflyAlgorithm,FA)［7］與和聲搜索算法(HarmonySearchAlgorithm,HSA)［8］等多種新型進(jìn)化算法。其中，HSA是由Geem等［8］于2001年提出的一種新型進(jìn)化算法，已被應(yīng)用于求解數(shù)值優(yōu)化問題、流水線調(diào)度問題和結(jié)構(gòu)工程優(yōu)化問題［8-13］。為了能夠應(yīng)用HSA求解具有二進(jìn)制編碼的組合最優(yōu)化問題，本文提出了一種二進(jìn)制和聲搜索算法(Binar

5、yHarmonySearchAlgorithm,BHSA)，并利用BHSA分別求解著名的k.可滿足性問題(k.SATisfiability,k.SAT)和背包問題()，通過對大規(guī)模k.SAT實(shí)例和實(shí)例的計算對比表明：BHSA是一種比二進(jìn)制粒子群優(yōu)化(BinaryBPSO,BPSO)和GA更適宜用來求解具有二進(jìn)制編碼組合最優(yōu)化問題的新算法。　　1二進(jìn)制和聲搜索算法　　和聲搜索算法(HSA)［8］是借鑒樂師們憑借記憶通過反復(fù)調(diào)整各樂器的音調(diào)而最終達(dá)到一個美妙的和聲狀態(tài)的思想實(shí)現(xiàn)進(jìn)化的

6、。在HSA中，各樂器的和聲對應(yīng)于解向量Xi=(xi1,xi2,…,xin)，評價結(jié)果對應(yīng)于目標(biāo)函數(shù)f(Xi)，和聲記憶庫(HarmonyMemory,HM)對應(yīng)于種群Pop={X1,X2,…,Xm}，而樂曲的創(chuàng)作過程即為種群的進(jìn)化過程。在基本HSA中，算法首先隨機(jī)產(chǎn)生HM，然后通過對HM的記憶思考、對音調(diào)的定調(diào)修正以及隨機(jī)選擇音調(diào)三種操作來產(chǎn)生候選解，并將候選解與HM中的最差解比較，淘汰其中的差者以更新HM；反復(fù)以上過程，達(dá)到和聲的最優(yōu)狀態(tài)為止。　　為了將和聲搜索算法用于求解

7、組合優(yōu)化問題，下面基于對HSA的記憶思考、定調(diào)修正和隨機(jī)選取三種進(jìn)化操作的離散化處理，提出一種二進(jìn)制編碼和聲搜索算法(BHSA)。　　　　　　設(shè)maxf(X)為最大組合優(yōu)化問題，其中X=(x1,x2,…,xn)∈{0,1}n為問題的解向量，對應(yīng)于各樂器的和聲的高與低，即xi=1時表示樂器i的和聲應(yīng)該為高音，否則為低音。相應(yīng)地，目標(biāo)函數(shù)f(X)對應(yīng)于和聲狀態(tài)的評價。此外，HMCR∈(0,1)稱為和聲庫的思考概率(HarmonyMemoryConsideringRate,HMCR)，

8、PAR∈(0,1)稱為定調(diào)微調(diào)概率(PitchAdjustingRate,PAR)，本文中HMCR的取值為,PAR的取值為。又設(shè)W=(w1,w2,…,wn)，B=(b1,b2,…,bn)∈{0,1}n分別表示當(dāng)前最差個體和最好個體，MaxT為迭代次數(shù)，則BHSA算法偽代碼描述如下：　　　　基于BHSA求解組合優(yōu)化問題　　2．1基于BHSA求解SAT問題可滿足性問題(SatisfiabilityProblem,SAT)是計算科學(xué)中