求解幾類復雜優(yōu)化問題的進化算法及其應(yīng)用.pdf

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

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

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

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

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

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

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