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

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

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

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

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