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

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

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

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

4、子群的多樣性，用接種疫苗算子來(lái)加強(qiáng)算法的求精能力。通過(guò)典型旅行商問(wèn)題和任務(wù)分配與調(diào)度問(wèn)題，對(duì)算法進(jìn)行了仿真比較，結(jié)果表明離散粒子群優(yōu)化算法能夠很好地應(yīng)用到組合優(yōu)化問(wèn)題中。 針對(duì)異構(gòu)環(huán)境下獨(dú)立任務(wù)分配問(wèn)題，基于遺傳算法、蟻群優(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è)分配方案。這些算法采用了免疫原理來(lái)提高算法的空間探索能力和局部求精能力；仿真結(jié)果表明，智能優(yōu)化算法能夠很好地應(yīng)用于求解任務(wù)分配問(wèn)題，基于免疫原理的優(yōu)化算子能夠有效地提高算法的搜

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