基于極值動力學的優(yōu)化方法及其應用研究.pdf

1、近年來，對NP難的組合優(yōu)化問題尋求高效的解決方法已成為優(yōu)化領域的一個極具挑戰(zhàn)性的研究課題。除了傳統(tǒng)的運籌學方法，現(xiàn)代啟發(fā)式方法正在得到越來越多的研究人員的關注和重視，已經(jīng)廣泛地應用于基礎研究和實際工程領域。現(xiàn)有的大多數(shù)啟發(fā)式方法，如進化算法、人工生命、模擬退火算法和禁忌算法等，都是從生物進化、統(tǒng)計物理和人工智能等領域發(fā)展而來。極值動力學優(yōu)化算法(EO)是近年來出現(xiàn)的一種新穎的、通用的、基于局部搜索的啟發(fā)式方法，該方法是從統(tǒng)計物理學發(fā)展而

2、來。眾所周知，模擬退火算法(SA)是模擬系統(tǒng)處于平衡態(tài)的一種優(yōu)化方法，與SA不同的是，EO算法的理論基礎建筑在Bak-Sneppen生物進化模型之上，該模型模擬處于遠離平衡態(tài)的系統(tǒng)，具備自組織臨界性(SOC)。SOC是指不管系統(tǒng)處于何種初始狀態(tài)，不需要調整任何參數(shù)，整個系統(tǒng)就可以演化到一個自組織臨界狀態(tài)，在該狀態(tài)下，系統(tǒng)呈現(xiàn)出冪律分布(Power-law)。遺傳算法通過對交配池中的所有可能解實施選擇、雜交和變異等遺傳操作來達到尋優(yōu)的目的

3、，而EO算法總是不斷地變異近似解的最差組成部分(即所謂的極值動力學機制)來達到尋優(yōu)的目的。正是這種內在的極值動力學機制，使得EO具備很強的爬山能力，尤其在求解帶有相變點的組合優(yōu)化問題時EO更是展現(xiàn)出強大的優(yōu)勢。EO算法的特點是收斂速度快，局部搜索能力強，只有變異算子，無可調參數(shù)(對于基本EO算法)或只有一個可調參數(shù)丁(對于т-EO算法)。目前EO算法已經(jīng)被成功地應用于求解一些NP難的組合優(yōu)化問題，如二分圖，旅行商問題，圖著色，旋轉玻璃和

4、動態(tài)組合優(yōu)化問題。但是，國外對于EO算法在數(shù)值優(yōu)化和多目標優(yōu)化問題方面的研究并不多，國內學者對EO算法的研究更少之甚少。本文主要研究求解無約束或帶約束數(shù)值優(yōu)化問題的EO算法，并將求解單目標優(yōu)化問題的EO算法擴展到多目標優(yōu)化領域。本文的主要工作包括： (1)本文從分析EO算法的機理入手，提出了一種求解約束連續(xù)優(yōu)化問題的新算法-帶自適應Lévy變異的基于種群的EO算法(PEO)，通過求解6個經(jīng)典的約束連續(xù)優(yōu)化問題，實驗結果證實了PE

5、O能與3種流行的優(yōu)化算法相匹敵，不失為一種求解數(shù)值約束優(yōu)化問題的有效方法。 (2)為了彌補標準粒子群算法容易陷入局部極值點的不足，本文提出了一種新穎的混合粒子群-極值動力學優(yōu)化算法(PSO-EO)，該算法有效地結合了PSO的全局搜索能力和EO的局部搜索能力，使得標準PSO算法可以跳出局部極值點，從而彌補了標準PSO算法的不足。迄今為止，還沒有文獻提出將EO和PSO結合起來的優(yōu)化算法。通過求解6個經(jīng)典的復雜單峰/多峰函數(shù)，PSO-

6、EO算法被證實了具有避免早熟收斂的特點，是一種求解復雜數(shù)值優(yōu)化問題的有效算法。 (3)由于EO算法只有變異操作，因此，變異算子對EO算法的性能好壞起到了重要作用。本文將高斯變異和柯西變異有效地結合起來，提出了一種新穎的適合于求解數(shù)值優(yōu)化問題的變異算子-混合高斯-柯西變異，該算子將“粗調”和“微調”很好地結合起來，并且省去了決定何時在不同變異之間進行切換的麻煩。 (4)本文將基于Pareto支配概念的適應度評價方法引入到E

7、O，提出了一種新穎的多目標極值動力學優(yōu)化方法(MultiobljectiveExtremalOp-timization，MOEO)，使EO算法成功地擴展到多目標優(yōu)化領域。接著，用MOEO算法解決了多目標連續(xù)優(yōu)化問題(包括無約束問題和帶約束問題)，實驗結果表明MOEO非常適合于求解多目標連續(xù)優(yōu)化問題，能夠與3種經(jīng)典的多目標進化算法(即NSGA-Ⅱ，SPEA2和PAES)相匹敵。最后，提出了一種適合于求解多目標0/1背包問題的MOEO算法。

8、實驗結果表明MOEO算法具有快速的收斂能力和良好的多樣化性能，具有與3種經(jīng)典的多目標進化算法(即NSGA，SPEA和NPGA)相競爭的優(yōu)勢。 (5)本文利甩MOEO算法解決了4個經(jīng)典的機械組件設計問題。實驗結果表明：MOEO算法找到的非劣解集在收斂性和多樣性方面有著良好的性能，能夠與3種經(jīng)典的多目標進化算法(NSGA-Ⅱ，SPEA2和PAES)相匹敵。因此，MOEO算法是一個能解決實際工程優(yōu)化問題的行之有效的方法。 (6