基于群體協(xié)作與周期震蕩衰減策略的果蠅優(yōu)化算法的研究.pdf

1、群智能算法作為一種啟發(fā)式隨機(jī)算法，一直以來備受研究者的青睞。該類算法適用范圍較廣，它不要求目標(biāo)對象具有特殊的結(jié)構(gòu)，只需提供少量的信息就可以對目標(biāo)對象進(jìn)行求解，并且這類算法實現(xiàn)過程也比較簡單。本文研究的果蠅優(yōu)化算法(FOA)也屬于群智能算法中的一種，它是基于對果蠅覓食行為的模擬而總結(jié)出的一種仿生類群智能算法。目前，雖然FOA算法的研究與應(yīng)用還處于起步階段，其理論研究的深度與應(yīng)用領(lǐng)域的廣度都不及其他群智能算法。盡管如此，F(xiàn)OA也依然取得了一

2、些不錯的成果，例如，在經(jīng)濟(jì)領(lǐng)域內(nèi)的企業(yè)績效評估、交通領(lǐng)域內(nèi)的道路規(guī)劃及科學(xué)理論的研究等。果蠅優(yōu)化算法的優(yōu)點較為突出，它結(jié)構(gòu)簡單、易于理解及編程實現(xiàn)，并且全局尋優(yōu)能力強(qiáng)、收斂速度快，但是，F(xiàn)OA算法的局限性也同樣明顯。首先，果蠅算法在迭代過程中，果蠅在可行域內(nèi)的移動距離與方向都是隨機(jī)的，造成算法的穩(wěn)定性較差、尋優(yōu)精度不高;其次，算法沒有很好的利用果蠅群的歷史信息，導(dǎo)致算法的效率較為低下，有較大的概率陷入局部極值點。本文的一個重要研究內(nèi)容就

3、是針對FOA算法的局限性，設(shè)計出一種性能更加優(yōu)越的果蠅優(yōu)化算法，并將這種改進(jìn)的果蠅優(yōu)化算法在云工作流任務(wù)調(diào)度中進(jìn)行了初步的應(yīng)用研究。隨著云計算產(chǎn)業(yè)的興起與蓬勃發(fā)展，作為云計算的核心----云工作流任務(wù)調(diào)度算法的研究也越來越重要。任務(wù)調(diào)度問題是一個經(jīng)典的NP-完全問題，智能算法一直是該研究領(lǐng)域的首選方案。其中，研究最多的智能算法為蟻群算法與粒子群算法，經(jīng)過多年的研究蟻群算法或者粒子群算法在理論方面趨于完善，其在性能方面提升的空間越來越小。

4、因而，急需在調(diào)度算法方面進(jìn)行理論突破，或?qū)で笠环N新的算法來給調(diào)度策略提供其他的改進(jìn)思路。
　　本研究主要內(nèi)容包括：⑴針對果蠅算法的穩(wěn)定性、尋優(yōu)精度及效率等問題，提出了基于群體協(xié)作與周期震蕩衰減策略的果蠅優(yōu)化算法。該改進(jìn)算法從三個方面對原果蠅算法進(jìn)行了理論上的改進(jìn)：采用群體協(xié)作方式，根據(jù)果蠅飛行能力的不同，將果蠅進(jìn)行分群，提高了種群的多樣性及算法的穩(wěn)定性；)改進(jìn)果蠅信息的更新策略，由最優(yōu)個體決定子代果蠅的搜索域，轉(zhuǎn)變?yōu)橛梢活愖顑?yōu)果蠅

5、群決定子代的搜索域，這種方式提高了果蠅群的利用率；采用具有周期震蕩遞減性質(zhì)的步長函數(shù)指導(dǎo)果蠅群的飛行，該函數(shù)使得果蠅既可以在全局域的搜索范圍更廣，又可以在局部域的搜索更加細(xì)化，提高了尋優(yōu)的精度。⑵為了驗證改進(jìn)果蠅算法的性能，選取具有代表性的BenchMark函數(shù)作為測試用例，并將本文算法同其他群智能算法進(jìn)行性能比較，綜合地評價改進(jìn)算法的性能。⑶將提出的改進(jìn)算法應(yīng)用到云工作流任務(wù)調(diào)度領(lǐng)域中，采用亞馬遜EC2計價模型，并將QoS約束中的成本