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

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

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

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

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

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

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

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

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