解非線性雙層規(guī)劃的算法研究.pdf

1、經(jīng)濟、管理、政策制定和工程設(shè)計等人類生活的各個領(lǐng)域中都存在優(yōu)化問題,其中決策優(yōu)化問題是人們研究的焦點問題。雙層規(guī)劃是一類重要的優(yōu)化問題,具有很重要的應(yīng)用價值和現(xiàn)實意義。然而雙層規(guī)劃是非凸不可微的問題,所以求解它非常困難,線性雙層規(guī)劃作為最簡單的一類雙層規(guī)劃問題已經(jīng)被證明是 NP-難問題。應(yīng)用傳統(tǒng)算法求解有很多的局限性,而對于一些復(fù)雜高維的問題,傳統(tǒng)算法更是難以計算,由于啟發(fā)式算法不需要目標函數(shù)的梯度等信息,所以求解這類復(fù)雜問題更為方便。

2、生物地理學(xué)算法(BBO)是一種基于生物地理棲息地的平衡理論的啟發(fā)式算法,這種算法不受目標函數(shù)的凸性以及搜索空間的連續(xù)性等條件的限制,已經(jīng)廣泛用于求解單層優(yōu)化問題。至今為止,BBO算法很少用于求解雙層規(guī)劃。
　　本文研究兩類特殊的非線性雙層規(guī)劃問題,基于BBO算法分別結(jié)合復(fù)合形法和坐標輪換法,設(shè)計求解這兩類雙層規(guī)劃的混合BBO算法。
　　本文的主要工作如下:
　　第一,對下層規(guī)劃是關(guān)于下層變量的線性規(guī)劃、上層目標函數(shù)是非

3、凸不可微的雙層規(guī)劃問題,首先,基于下層線性規(guī)劃最優(yōu)解滿足的條件,將問題轉(zhuǎn)化為單層規(guī)劃問題;其次,結(jié)合復(fù)合形法及四種不同的遷移率模型,設(shè)計了一種混合BBO算法。克服了原BBO算法局部收斂性較弱的缺點,增強了BBO算法的局部搜索能力,有效提高了解的精度,加快了算法收斂速度。進一步,證明了混合BBO算法以概率一收斂于全局最優(yōu)解;最后,實驗結(jié)果表明本文算法是有效的、穩(wěn)定的,且結(jié)果優(yōu)于比較的算法所得結(jié)果。
　　第二,對下層規(guī)劃關(guān)于下層變量是

4、可微的凸規(guī)劃、上層規(guī)劃的目標函數(shù)和約束函數(shù)均是非凸不可微的雙層規(guī)劃問題,首先,利用下層凸規(guī)劃的最優(yōu)性條件(KKT條件),將下層規(guī)劃用KKT條件代替,而將原問題轉(zhuǎn)化為一個單層規(guī)劃問題;然后,利用均勻設(shè)計產(chǎn)生初始種群,引入交叉算子和選擇算子,結(jié)合坐標輪換法,運用隨機遷移率模型等,提出了一種改進的BBO算法;進一步,證明了算法以概率一收斂于全局最優(yōu)解;最后,大量實驗結(jié)果表明該算法對求解這類雙層規(guī)劃問題是有效的,并且具有較高的穩(wěn)定性,且優(yōu)于比較