求解幾類(lèi)復(fù)雜優(yōu)化問(wèn)題的進(jìn)化算法及其應(yīng)用.pdf

1、在工程設(shè)計(jì)、科學(xué)計(jì)算、經(jīng)濟(jì)領(lǐng)域中存在著各種類(lèi)型的復(fù)雜優(yōu)化問(wèn)題，通常需要求解它們的全局最優(yōu)解而不是局部最優(yōu)解。進(jìn)化算法是一類(lèi)魯棒性強(qiáng)的全局搜索算法，對(duì)基于梯度的傳統(tǒng)優(yōu)化方法無(wú)法或難以處理的高度非線性、不可微、多峰、多變量問(wèn)題，尤其是目標(biāo)函數(shù)的導(dǎo)數(shù)無(wú)法求出，受噪聲影響或沒(méi)有明確的數(shù)學(xué)形式這樣的問(wèn)題，進(jìn)化算法具有很大的優(yōu)勢(shì)。本文對(duì)幾類(lèi)復(fù)雜優(yōu)化問(wèn)題，包括無(wú)約束全局優(yōu)化、約束優(yōu)化、整數(shù)規(guī)劃和混合整數(shù)規(guī)劃、線性?xún)蓪右?guī)劃、凸二次兩層規(guī)劃、一般的非線性

2、兩層規(guī)劃以及離散兩層規(guī)劃進(jìn)行了系統(tǒng)深入的研究，根據(jù)不同類(lèi)型的問(wèn)題，設(shè)計(jì)和開(kāi)發(fā)了不同的進(jìn)化算法，并將所設(shè)計(jì)的部分算法應(yīng)用到實(shí)際問(wèn)題中，以驗(yàn)證算法的有效性和實(shí)用性。論文的主要研究成果可概括為以下幾個(gè)方面： 1．在設(shè)計(jì)新變異算子的基礎(chǔ)上提出了一種實(shí)數(shù)編碼遺傳算法，結(jié)合一種局部搜索算子——簡(jiǎn)化的二次插值法，提出了求解無(wú)約束全局優(yōu)化問(wèn)題的混合遺傳算法。還分析了該算法的收斂性，對(duì)23個(gè)標(biāo)準(zhǔn)測(cè)試函數(shù)作了數(shù)值實(shí)驗(yàn)。與文獻(xiàn)中其它進(jìn)化算法的比較結(jié)果

3、表明了算法的有效性。最后，將該算法應(yīng)用于圓柱共形天線陣方向圖優(yōu)化綜合，獲得了良好的效果。 2．采用精確罰函數(shù)法，把約束優(yōu)化問(wèn)題轉(zhuǎn)化為無(wú)約束優(yōu)化問(wèn)題，將簡(jiǎn)化的二次插值法作為局部搜索算子，合并到差分進(jìn)化算法中，提出了一種求解約束優(yōu)化問(wèn)題的混合差分進(jìn)化算法。采用該算法求解了13個(gè)標(biāo)準(zhǔn)測(cè)試問(wèn)題，并與文獻(xiàn)中已有的進(jìn)化算法作了比較，結(jié)果表明混合差分進(jìn)化算法性能優(yōu)良。最后，采用該算法優(yōu)化設(shè)計(jì)了4個(gè)著名的工程問(wèn)題，所得結(jié)果表明了算法的有效性和實(shí)

4、用性。 3．對(duì)不同類(lèi)型的離散優(yōu)化問(wèn)題提出了不同的進(jìn)化算法。首先，對(duì)一類(lèi)0-1整數(shù)規(guī)劃——多維背包問(wèn)題，將正交試驗(yàn)設(shè)計(jì)應(yīng)用到雜交算子中，結(jié)合一種基于貪婪思想的約束處理，提出了一種0-1編碼的正交遺傳算法。其次，對(duì)一般的整數(shù)規(guī)劃問(wèn)題，設(shè)計(jì)了一種整數(shù)編碼的混合進(jìn)化算法。該算法中采用帶有隨機(jī)參數(shù)的差分變異算子；將正交表和因素分析引入雜交過(guò)程，設(shè)計(jì)了雜交算子；設(shè)計(jì)了一種遷移算子來(lái)增加種群的多樣性；把簡(jiǎn)化的二次插值法用作局部搜索算子；通過(guò)對(duì)

5、每一代中最好染色體的基因進(jìn)行微調(diào)，來(lái)跳出局部最優(yōu)解。對(duì)所有算子產(chǎn)生的染色體均使用了一種取整和截?cái)嗖僮鬟^(guò)程，以保證所求問(wèn)題的變量滿(mǎn)足整數(shù)要求和邊界約束條件。最后，對(duì)混合整數(shù)規(guī)劃，設(shè)計(jì)了一種整數(shù)和實(shí)數(shù)混合編碼的混合進(jìn)化算法。對(duì)所提出的三個(gè)進(jìn)化算法作了大量的數(shù)值實(shí)驗(yàn)，并與文獻(xiàn)中的其它進(jìn)化算法作了比較，結(jié)果表明了三個(gè)算法的有效性。采用正交遺傳算法求解了投資決策和成本預(yù)算問(wèn)題，進(jìn)一步說(shuō)明了算法的有效性和實(shí)用性。 4．對(duì)線性?xún)蓪右?guī)劃和凸二次

6、兩層規(guī)劃問(wèn)題分別提出了一種正交遺傳算法。采用KKT最優(yōu)性條件將這兩類(lèi)兩層問(wèn)題分別轉(zhuǎn)化為單層互補(bǔ)松弛問(wèn)題，并對(duì)KKT乘子進(jìn)行0-1二進(jìn)制編碼，將互補(bǔ)松弛問(wèn)題分別轉(zhuǎn)化為一系列線性規(guī)劃或凸二次規(guī)劃，其最優(yōu)解就對(duì)應(yīng)原兩層規(guī)劃的一個(gè)可行解。在此基礎(chǔ)上，分別設(shè)計(jì)了求解兩類(lèi)單層互補(bǔ)松弛問(wèn)題的正交遺傳算法。理論分析和數(shù)值實(shí)驗(yàn)結(jié)果表明，求解這兩類(lèi)兩層問(wèn)題的正交遺傳算法是有效的，能以較少的計(jì)算代價(jià)求出問(wèn)題的全局最優(yōu)解。最后，采用線性?xún)蓪右?guī)劃的正交遺傳算法求

7、解了價(jià)格控制問(wèn)題。 5．對(duì)上層規(guī)劃是非凸、不可微的非線性?xún)蓪右?guī)劃問(wèn)題，采用均勻設(shè)計(jì)法產(chǎn)生初始種群，結(jié)合局部搜索算子——簡(jiǎn)化的二次插值法，提出了一種混合遺傳算法。分析了算法的收斂性，大量的數(shù)值實(shí)驗(yàn)結(jié)果驗(yàn)證了算法的有效性，也表明了算法能找到高質(zhì)量的最優(yōu)解。最后，采用該算法求解了交通網(wǎng)絡(luò)設(shè)計(jì)和公路通行費(fèi)設(shè)置問(wèn)題，進(jìn)一步驗(yàn)證了算法的有效性和實(shí)用性。 6．對(duì)離散兩層規(guī)劃問(wèn)題提出了兩種進(jìn)化算法。對(duì)整數(shù)線性?xún)蓪右?guī)劃問(wèn)題，首先將其轉(zhuǎn)化為