差分進化算法在組合優(yōu)化問題中的應用研究.pdf

1、在工程實踐和科學研究中存在著大量的組合優(yōu)化問題,且大多帶有約束條件,采用傳統(tǒng)的數(shù)學優(yōu)化方法將很難求解。差分進化算法是近年提出的一種新的自然計算方法,也是基于種群迭代的群智能優(yōu)化方法,雖在求解帶約束的組合優(yōu)化問題中得到較好應用,但在算法的精度和求解效率上仍存在著瓶頸。因此針對具體優(yōu)化問題,研究并設計高效的差分進化算法正受到國內(nèi)外研究者的普遍關注,也正逐步成為進化計算領域的研究熱點。
　　 本研究緊緊圍繞經(jīng)典的背包問題和等圓Pack

2、ing問題,它們是兩類具有代表性的組合優(yōu)化問題,進行較深入的探索研究,并取得相應的研究成果:
　　 (1)針對離散空間的組合優(yōu)化問題,提出了一種基于置換策略的離散差分進化算法。主要的工作有:一是將置換策略和差分進化算法相結合,提出一種基于置換策略的單目標差分進化算法,并將該算法應用于求解單目標背包問題；二是結合NSGA-Ⅱ的精英保留機制,在差分進化算法的基礎上,給出多目標差分進化算法；三是給出基于置換策略的多目標差分進化算法,應

3、用該算法求解多目標背包問題。實驗結果和分析表明,該算法能夠有效地解決背包問題,特別是在大規(guī)模問題的求解上,算法優(yōu)化性能明顯優(yōu)于NSGA-Ⅱ。
　　 (2)針對連續(xù)空間的大規(guī)模約束的組合優(yōu)化問題,設計出求解問題的差分進化算法,并驗證算法的可行性。本文選取其中的等圓Packing問題進行研究,將等圓Packing問題轉換成多目標問題,設計出適合求解等圓Packing問題的差分進化算法,并通過大量實驗,驗證文中所設計算法的可行性。