智能優(yōu)化方法及其應(yīng)用研究.pdf

1、生物體和自然生態(tài)系統(tǒng)可以通過自身的演化就使許多在人類看來高度復(fù)雜的優(yōu)化問題得到滿意的解決，受此啟發(fā)，產(chǎn)生了以模仿自然與生物機(jī)理為特征的智能優(yōu)化方法，它們?yōu)橛脗鹘y(tǒng)的優(yōu)化方法難以解決的NP-困難問題提供了有效的解決途徑。任務(wù)的合理分配與調(diào)度是并行分布式系統(tǒng)獲取高性能的關(guān)鍵因素之一，它們是NP-困難的問題，基于智能優(yōu)化方法的任務(wù)分配與調(diào)度算法是解決這些問題的有效算法。本論文主要研究三種典型的智能優(yōu)化算法，遺傳算法、蟻群優(yōu)化算法和粒子群優(yōu)化算法

2、，研究如何通過免疫原理提高它們的性能，并把它們應(yīng)用于解決異構(gòu)環(huán)境下的獨(dú)立任務(wù)分配問題及同構(gòu)和異構(gòu)環(huán)境下的相關(guān)任務(wù)調(diào)度問題。 提出了具有免疫特性的蟻群優(yōu)化算法，針對蟻群優(yōu)化算法易于陷入早熟收斂和局部求精能力不足的缺點(diǎn)，從人工免疫系統(tǒng)的基本原理出發(fā)，設(shè)計(jì)了三種免疫算子：免疫抑制算子、信息素平滑算子和接種疫苗算子；使用免疫抑制算子、信息素平滑算子來保持蟻群的多樣性，使算法在迭代的后期依然保持進(jìn)化能力，使用接種疫苗算子來提高算法的局部求

3、精能力，使蟻群優(yōu)化算法在局部開采和全局探索間取得更好的平衡。通過典型旅行商問題和任務(wù)分配與調(diào)度問題，對算法進(jìn)行了仿真比較，結(jié)果表明免疫算子能有效地提高蟻群優(yōu)化算法的性能。 提出了離散粒子群優(yōu)化算法的基本設(shè)計(jì)原則，根據(jù)離散量運(yùn)算的特點(diǎn)，對粒子的位置、速度等量及其運(yùn)算規(guī)則進(jìn)行了重新定義，為抑制早熟停滯現(xiàn)象，為粒子和粒子群分別定義了個(gè)體多樣性、微觀多樣性和宏觀多樣性，從人工免疫系統(tǒng)的基本原理出發(fā)，提出用排斥算子和膨脹算子來增加或保持粒

4、子群的多樣性，用接種疫苗算子來加強(qiáng)算法的求精能力。通過典型旅行商問題和任務(wù)分配與調(diào)度問題，對算法進(jìn)行了仿真比較，結(jié)果表明離散粒子群優(yōu)化算法能夠很好地應(yīng)用到組合優(yōu)化問題中。 針對異構(gòu)環(huán)境下獨(dú)立任務(wù)分配問題，基于遺傳算法、蟻群優(yōu)化算法、離散粒子群優(yōu)化算法和免疫原理，分別就解空間的直接和間接編碼方式，提出了一些新的優(yōu)化算法。基于直接編碼方式的算法有免疫遺傳算法、免疫蟻群優(yōu)化算法和免疫離散粒子群優(yōu)化算法，它們直接以解空間為算法的搜索空間

5、；基于間接編碼方式的算法有免疫混合遺傳算法、分段免疫混合蟻群優(yōu)化算法和免疫混合離散粒子群優(yōu)化算法，它們是表啟發(fā)式分配算法和智能優(yōu)化算法的結(jié)合，以任務(wù)分配順序表為搜索空間，搜索最優(yōu)的任務(wù)分配順序，然后把搜索出的任務(wù)分配順序表用最小完成時(shí)間算法進(jìn)行解碼，得到相應(yīng)的一個(gè)分配方案。這些算法采用了免疫原理來提高算法的空間探索能力和局部求精能力；仿真結(jié)果表明，智能優(yōu)化算法能夠很好地應(yīng)用于求解任務(wù)分配問題，基于免疫原理的優(yōu)化算子能夠有效地提高算法的搜

6、索效率、優(yōu)化搜索結(jié)果。 針對并行分布式系統(tǒng)中相關(guān)任務(wù)的調(diào)度問題，基于遺傳算法、蟻群優(yōu)化算法、離散粒子群優(yōu)化算法和免疫原理，分別就解空間的直接和間接編碼方式，提出了一些新的優(yōu)化算法。直接編碼的混合遺傳算法直接用問題可行解為染色體編碼，以解空間為算法的搜索空間，根據(jù)拉馬克進(jìn)化原理，設(shè)計(jì)了單點(diǎn)自學(xué)習(xí)交叉算子來提高算法的求精能力，采用了免疫變異算子來維持種群的多樣性；基于間接編碼方式的算法有間接編碼的混合遺傳算法、蟻群優(yōu)化算法和離散粒子