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

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

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

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

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

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

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

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

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