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

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

1、基于和聲搜索算法求解組合優(yōu)化問題　　0引言　　　　　　當前，演化計算領域新算法不斷涌現(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］等多種新型進化算法。其中，HSA是由Geem等［8］于2001年提出的一種新型進化算法，已被應用于求解數(shù)值優(yōu)化問題、流水線調度問題和結構工程優(yōu)化問題［8-13］。為了能夠應用HSA求解具有二進制編碼的組合最優(yōu)化問題，本文提出了一種二進制和聲搜索算法(BinaryHarmonySearchAlgorithm,BHSA)，并利用BHSA分別求解著名的k.可滿足性問題(k.SATisfiabilit

3、y,k.SAT)和背包問題()，通過對大規(guī)模k.SAT實例和實例的計算對比表明：BHSA是一種比二進制粒子群優(yōu)化(BinaryBPSO,基于和聲搜索算法求解組合優(yōu)化問題　　0引言　　　　　　當前，演化計算領域新算法不斷涌現(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］等多種新型進化算法。其中，HSA是由Geem等［8］于2001年提出的一種新型進化算法，已被應用于求解數(shù)值優(yōu)化問題、流水線調度問題和結構工程優(yōu)化問題［8-13］。為了能夠應用HSA求解具有二進制編碼的組合最優(yōu)化問題，本文提出了一種二進制和聲搜索算法(Binar

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

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

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

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