基于近似技術(shù)的雙層規(guī)劃進(jìn)化算法

沈瑜，李和成，陳黎娟

（青海師范大學(xué)數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，西寧 810008）

0 引言

在工程和經(jīng)濟(jì)管理領(lǐng)域，經(jīng)常出現(xiàn)具有遞階結(jié)構(gòu)的決策問題，這類問題中決策者處在不同的層次上。首先，處在上層的決策者為了優(yōu)化自己的目標(biāo)，提出一個決策方案；處在下層的決策者根據(jù)上層提供的方案，選擇一個下層問題的最優(yōu)決策方案并反饋上層；上層結(jié)合下層反饋的方案評價自己給出的方案，該過程持續(xù)進(jìn)行，直到使上層目標(biāo)達(dá)到最優(yōu)。這類具有遞階嵌套結(jié)構(gòu)的優(yōu)化問題稱為多層優(yōu)化問題［1］，其中雙層規(guī)劃問題（BiLevel Programming Problem，BLPP）最為常見，一般模型可表示如下：

式（1）和式（2）分別稱為上層問題和下層問題。其中：x=(x1，x2，…，xn) ∈Rn和y=(y1，y2，…，ym) ∈Rm分別稱為上、下層問題的決策變量；F(x，y)：Rn+m→R 是上層問題的目標(biāo)函數(shù)，f(x，y)：Rn+m→R 是下層問題的目標(biāo)函數(shù)；G(x，y)：Rn+m→Rp和g(x，y)：Rn+m→Rq分別為上層和下層問題的約束函數(shù)。式（1）的決策過程可以表述如下：首先上層決策者在上層可行區(qū)域選擇一個變量值x。將x作為一個參數(shù)，求解下層規(guī)劃問題（2），得到下層規(guī)劃問題（2）的最優(yōu)解y。如果得到的(x，y)滿足上層問題（1）的約束條件，則稱(x，y)為雙層規(guī)劃問題（1）～（2）的一個雙層可行點(diǎn)。求解式（1）～（2）的目的就是在可行解集中選擇使上層目標(biāo)F(x，y)最小的雙層可行點(diǎn)。如果對于一個給定的上層變量x，下層問題存在多個最優(yōu)解y與其對應(yīng)，這種情況涉及下層最優(yōu)解的選擇，不同的選擇模式有不同的雙層規(guī)劃模型［2］。為了使雙層規(guī)劃問題結(jié)構(gòu)簡潔，在設(shè)計(jì)算法時更多地關(guān)注問題的遞階結(jié)構(gòu)，現(xiàn)有的文獻(xiàn)通常假設(shè)下層問題的最優(yōu)解是唯一的［3］。本文的目的是提高算法處理遞階結(jié)構(gòu)的能力。因此，仍然保留下層問題最優(yōu)解唯一的假設(shè)。

雙層模型的應(yīng)用領(lǐng)域很廣泛。在農(nóng)業(yè)生產(chǎn)中，使用化肥可以提高生產(chǎn)率，但過度使用會導(dǎo)致環(huán)境污染，針對這類問題，文獻(xiàn)［4］設(shè)計(jì)了一個雙層模型研究化肥對環(huán)境的影響；文獻(xiàn)［5］討論了核武器攔截、關(guān)鍵基礎(chǔ)設(shè)施捍衛(wèi)等安全問題，建立了相應(yīng)的雙層規(guī)劃模型；文獻(xiàn)［6］開發(fā)了一種基于雙層互補(bǔ)模型的決策工具，用于確定貧乏市場中最有利的交易；文獻(xiàn)［7］針對整車物流服務(wù)供應(yīng)鏈的訂單分配問題，提出了考慮多種運(yùn)輸方式的雙層訂單分配模型。雙層優(yōu)化模型的其他應(yīng)用，參見文獻(xiàn)［8-11］。

目前求解雙層規(guī)劃問題的方法主要可分為三大類：

1）基于梯度的經(jīng)典優(yōu)化方法。文獻(xiàn)［12-13］利用K-K-T（Karush-Kuhn-Tucker）條件將雙層規(guī)劃轉(zhuǎn)化為單層規(guī)劃問題，但轉(zhuǎn)化后的模型具有復(fù)雜的約束域；針對整數(shù)線性雙層規(guī)劃，文獻(xiàn)［14］提出了一個分支定界法；文獻(xiàn)［15］利用K-K-T 條件和最優(yōu)值條件將雙層模型轉(zhuǎn)化為單層優(yōu)化模型，通過求解單層問題獲得原問題的最優(yōu)解；對于弱線性雙層規(guī)劃問題，文獻(xiàn)［16］給出了一個罰函數(shù)法；文獻(xiàn)［17］利用罰函數(shù)法和K-K-T 條件設(shè)計(jì)了求解非線性雙層規(guī)劃問題的算法。這些經(jīng)典的優(yōu)化方法在求解速度上相對較快，但大部分算法要求函數(shù)具有凸可微或線性等性質(zhì)，普適性不高。另外，分支定界方法在問題規(guī)模較大時，計(jì)算量增長很快，很難推廣到大規(guī)模問題。

2）進(jìn)化方法。文獻(xiàn)［18］針對分類特征選擇的雙層規(guī)劃設(shè)計(jì)了一種新的遺傳算法；文獻(xiàn)［19］針對下層為線性分式的非線性雙層規(guī)劃問題提出了一種基于二進(jìn)制編碼的遺傳算法；文獻(xiàn)［20］研究了一類區(qū)間雙層規(guī)劃問題，提出了一種基于線性分式最優(yōu)性條件的進(jìn)化算法；針對一般的非線性雙層規(guī)劃問題，文獻(xiàn)［21］提出了一種協(xié)同進(jìn)化算法；文獻(xiàn)［22］基于新的選擇方式和混沌搜索方法，設(shè)計(jì)了一種改進(jìn)的遺傳算法；為了求解隨機(jī)雙層規(guī)劃問題，文獻(xiàn)［23］提出了一種基于空間系統(tǒng)采樣技術(shù)的元啟發(fā)式算法。單一的進(jìn)化算法雖然不需要函數(shù)凸可微，具有較好的普適性，但是往往會涉及過多的適應(yīng)度函數(shù)評估，產(chǎn)生較大的計(jì)算量。

3）混合方法。文獻(xiàn)［24］提出了一種基于模擬退火Metropolis 準(zhǔn)則的改進(jìn)粒子群優(yōu)化算法，該算法設(shè)計(jì)的目的是解決粒子群優(yōu)化算法求解雙層規(guī)劃問題時易陷入局部最優(yōu)解的問題；文獻(xiàn)［25］提出了一種混合啟發(fā)式方法求解p中值雙層問題；對于單目標(biāo)雙層規(guī)劃問題，文獻(xiàn)［26］提出了一種將全局搜索和局部搜索結(jié)合的模因算法；文獻(xiàn)［27］提出了基于多種群的多正弦余弦算法；文獻(xiàn)［28］提出了采用靈敏度分析技術(shù)的粒子群分布估計(jì)算法?；旌戏椒ńY(jié)合多種算法的優(yōu)勢處理雙層問題，整體搜索效果好。然而，由于算法的復(fù)合結(jié)構(gòu)，嵌入算法的節(jié)點(diǎn)、參數(shù)的調(diào)試是個比較復(fù)雜的問題，直接影響算法的求解效率。

眾所周知，導(dǎo)致雙層規(guī)劃問題計(jì)算量大的原因是頻繁計(jì)算下層問題。因此，要想顯著降低雙層規(guī)劃的計(jì)算量，必須減少下層問題的求解次數(shù)。Sinha 等［29］利用多值映射的方式近似下層解函數(shù)，Liu 等［30］利用插值函數(shù)近似下層問題的最優(yōu)解，這些近似技術(shù)極大地提高了算法的計(jì)算效率，但不足的是需要構(gòu)造插值函數(shù)或映射，且更新過程的計(jì)算量隨問題規(guī)模的增加快速增長，本身也會產(chǎn)生較大的計(jì)算量。

為了解決上述問題，本文針對具有上下層約束的一般雙層規(guī)劃，基于參數(shù)規(guī)劃的最優(yōu)解理論，提出了一種基于下層解近似技術(shù)的進(jìn)化算法。與現(xiàn)有的近似技術(shù)相比，本文算法不需要設(shè)計(jì)近似函數(shù)，在獲得下層最優(yōu)解方面能真正減少計(jì)算量。

1 基本概念

本文討論的雙層規(guī)劃問題中，上下層函數(shù)沒有特殊限制，這一點(diǎn)與線性、二次等特殊模型不同，更有一般性。為了敘述方便，引進(jìn)一些符號和概念［3］。

2 本文算法

本文算法采取了多種群協(xié)同進(jìn)化的模式。協(xié)同進(jìn)化不僅考慮了局部個體信息的充分交換，而且為下層解的近似估計(jì)提供了便利。下面分別給出算法的各個關(guān)鍵環(huán)節(jié)。

步驟1 種群初始化。

首先在上層可行區(qū)域內(nèi)均勻產(chǎn)生K個點(diǎn)xck(k=1，2，…，K)，即K個上層變量值；然后，在以這K個點(diǎn)為中心的鄰域內(nèi)均勻產(chǎn)生-1 個點(diǎn)。共得到M個點(diǎn)，不妨設(shè)這M個點(diǎn)均在上層決策空間的投影區(qū)域內(nèi)，如若不然，重新產(chǎn)生即可。這些點(diǎn)組成規(guī)模為M的初始種群，個體記為xi(i=1，2，…，M)。同時，這些個體根據(jù)與K個中心個體xck的距離聚類為K組，即，初始種群P(0)由K個子種群P1、P2、…、PK組成，每個小種群包含個個體。將xi(i=1，2，…，M)代入下層問題中解出下層問題的最優(yōu)解yi(i=1，2，…，M)。令代數(shù)t=0。

步驟2 個體評估。

以上層目標(biāo)函數(shù)F(x，y)為適應(yīng)度函數(shù)。根據(jù)評估結(jié)果，選出種群中最好的個體，并存儲在最優(yōu)解集合A中。

步驟3 交叉操作。

由于參數(shù)優(yōu)化理論，最優(yōu)解對參數(shù)具有一定的依賴性，因此，本文算法中交叉后代盡可能在距離較近的個體之間產(chǎn)生。在子種群Pk(k=1，2，…，K)中，以交叉概率Pc隨機(jī)選擇兩個距離較近的個體xi和xj進(jìn)行交叉操作，產(chǎn)生的后代個體為：

其中：λ∈(0，1)。根據(jù)產(chǎn)生的xc，對應(yīng)的下層最優(yōu)解通過如下方式近似：

交叉過程如圖1（a）所示。交叉父代個體處于上層決策空間中，實(shí)心圓點(diǎn)和空心圓點(diǎn)表示隨機(jī)選擇的父代個體，小三角表示交叉后代。下層決策空間中，實(shí)心圓點(diǎn)和空心圓點(diǎn)表示父代個體對應(yīng)的下層最優(yōu)解，小三角表示交叉后代的下層近似解。子種群的設(shè)計(jì)限定了交叉父代個體之間的距離，在一定程度上保證了近似解的準(zhǔn)確性。

步驟4 變異操作。

在種群P(t)中，以變異概率Pm隨機(jī)選擇個體xi進(jìn)行高斯變異操作，其后代個體為：

并給出其對應(yīng)的近似下層最優(yōu)解：

其中：β～N(0，1)。

計(jì)算后代個體xm與K個中心個體(k=1，2，…，K)的距離，并將變異后代放入距離近的子種群。

變異過程如圖1（b）所示：上層決策空間中，實(shí)心圓點(diǎn)表示父代個體空心圓點(diǎn)通過高斯變異產(chǎn)生的后代個體；下層決策空間中，空心圓點(diǎn)表示父代個體對應(yīng)的下層最優(yōu)解，該點(diǎn)進(jìn)行同樣的變異操作產(chǎn)生的后代個體是對應(yīng)的下層近似最優(yōu)解（實(shí)心圓點(diǎn)）。在種群中進(jìn)行的變異會在這個約束域內(nèi)產(chǎn)生點(diǎn)，具備全局搜索的功能，有助于保持算法的開采能力。

圖1 交叉操作和變異操作示意圖Fig.1 Schematic diagrams ofcrossover operation and mutation operation

步驟5 后代個體預(yù)評估。

對于產(chǎn)生的后代個體，包括交叉?zhèn)€體和變異個體，計(jì)算下層近似最優(yōu)解yi，然后將(xi，yi)代入上層目標(biāo)函數(shù)和約束函數(shù)。若(xi，yi)不滿足約束，則賦予較大的目標(biāo)函數(shù)值；否則，以上層目標(biāo)函數(shù)值為該個體的預(yù)評估值，之所以稱之為預(yù)評估值，是因?yàn)橄聦硬]有獲得精確的最優(yōu)解。

步驟6 驗(yàn)證后代種群的擬合程度。

在子種群Pk(k=1，2，…，K)中，隨機(jī)選擇M3K個較好個體進(jìn)行驗(yàn)證。驗(yàn)證過程如下：將經(jīng)過交叉或變異操作后的個體xi代入下層問題中，得到其精確最優(yōu)解，則對應(yīng)的精確可行解為(xi，)。比較F(xi，yi)與F(xi，)的大小關(guān)系。若式（8）成立，則認(rèn)為擬合程度好；反之，則認(rèn)為擬合程度不好。

γ為充分小的正數(shù)；α為擬合系數(shù)，α值越小說明擬合程度越好，反之亦然。根據(jù)擬合程度檢驗(yàn)，通過設(shè)定閾值，可得到擬合程度較好的子種群和擬合程度較差的子種群。

步驟7 選擇操作。

步驟8 算法停止。

如果滿足停止標(biāo)準(zhǔn)，則輸出集合A中的解；反之，令t=t+1，執(zhí)行步驟3。

本文算法流程如圖2 所示。

圖2 本文算法的流程Fig.2 Flowchart of the proposed algorithm

本文算法的主要目的是減少下層問題的計(jì)算頻次，最終達(dá)到提高計(jì)算效率的目的。首先根據(jù)歐氏距離對種群個體進(jìn)行聚類形成子種群，其次交叉在子種群內(nèi)部進(jìn)行。由于個體間的距離較近，因此，兩個父代個體交叉產(chǎn)生的后代在父代個體附近?？紤]到上層變量的不同只導(dǎo)致下層問題參數(shù)的不同，基于靈敏度分析理論，最后采用比例近似技術(shù)估計(jì)后代個體對應(yīng)的下層最優(yōu)解。這個技術(shù)有效避免了對下層問題的頻繁求解，減少了計(jì)算量，這是與現(xiàn)有算法的本質(zhì)不同。

本文算法對問題涉及的函數(shù)、變量等無特殊要求，具有較好的普適性，因此，可用于處理線路優(yōu)化、軟件設(shè)計(jì)、資費(fèi)設(shè)置等領(lǐng)域內(nèi)的雙層規(guī)劃模型。

在雙層規(guī)劃常見的算例中任選一個，具體如下：

對于?x∈[0，5]，式（10）的誘導(dǎo)區(qū)域?yàn)椋?/p>

在圖3 中，實(shí)線部分為式（10）的誘導(dǎo)區(qū)域。在種群進(jìn)化過程中，抽取了10 對父代個體，給出了對應(yīng)后代及近似下層解，并對每個后代計(jì)算了精確的下層最優(yōu)解。所有數(shù)據(jù)見表1。

圖3 式（10）的誘導(dǎo)域Fig.3 Inducible region of Equation（10）

表1 近似下層解和精確下層解Tab.1 Approximate and precise follower solutions

表1 數(shù)據(jù)顯示，大部分下層最優(yōu)解小數(shù)點(diǎn)后兩位是一致的，僅僅最后一個個體出現(xiàn)了大于10-2的誤差，說明由近似技術(shù)得到的后代個體準(zhǔn)確性較高。表2 給出了近似解的目標(biāo)函數(shù)值和精確解的目標(biāo)函數(shù)值，它們的絕對誤差均小于給定的閾值（最后一列，取γ=0.01）。根據(jù)表1～2 中的數(shù)據(jù)分別繪制擬合曲線，見圖4～5。從圖4～5 的曲線和點(diǎn)的擬合程度可知，由近似技術(shù)得到的近似后代個體與精確后代個體的位置大部分是重合的，意味著本文提出的近似技術(shù)是可行有效的。

圖4 下層解的散點(diǎn)圖Fig.4 Scatter diagram of follower solutions

表2 目標(biāo)函數(shù)值的誤差Tab.2 Errors of objective function values

圖5 目標(biāo)函數(shù)曲線圖Fig.5 Curves of objective functions

3 數(shù)值實(shí)驗(yàn)

3.1 測試函數(shù)與應(yīng)用算例

算例1［31］：

本文選取了10 個算例作為測試函數(shù)，其中，算例1～2 是整數(shù)線性雙層規(guī)劃，選自文獻(xiàn)［31］；算例3～5 是混合整數(shù)雙層規(guī)劃，選自文獻(xiàn)［32］；算例6～10 是一般類型的雙層規(guī)劃，選自文獻(xiàn)［29］。算例1 的上層決策變量的維數(shù)是4，下層決策變量的維數(shù)是2；算例2 的上層決策變量的維數(shù)是4，下層決策變量的維數(shù)是3，并且上層規(guī)劃問題是一個0-1 規(guī)劃問題。算例6～8 的上層或下層目標(biāo)函數(shù)是二次函數(shù)。算例10的上層目標(biāo)函數(shù)是不可微的，下層目標(biāo)函數(shù)是二次函數(shù)。這些算例是雙層規(guī)劃算法常見的測試函數(shù)。本文算法在這10個算例上分別進(jìn)行了仿真測試。

為了說明本文算法在求解實(shí)際應(yīng)用問題方面的有效性，考慮實(shí)踐常見的資費(fèi)設(shè)置問題，該問題的模型如下：

其中：集合G表示起點(diǎn)-終點(diǎn)的組合；集合D表示網(wǎng)絡(luò)圖中點(diǎn)的集合；集合B表示的是網(wǎng)絡(luò)圖中弧（路）的集合。B1表示收取通行費(fèi)的弧（路）的集合，B2表示不收取通行費(fèi)的?。罚┑募?。在雙層規(guī)劃模型中，上層決策變量xa表示道路a∈B1的通行費(fèi)用，由上層決策者直接控制；下層決策變量表示起點(diǎn)到終點(diǎn)的車流量。i+(i-)表示以i作為起點(diǎn)（終點(diǎn)）的路的集合。每一條路a∈B都提供了駕駛這條路的行駛成本ca，該成本不包括通行費(fèi)用。對于每一組g∈G，從起點(diǎn)o(g)到終點(diǎn)d(g)的需求車輛數(shù)為ng。上層目標(biāo)函數(shù)（12）需要使收費(fèi)站的收益最大化，下層目標(biāo)函數(shù)（13）傾向于使用戶的支出最小化。

該模型對應(yīng)的網(wǎng)絡(luò)拓?fù)浣Y(jié)構(gòu)見圖6，其中：

圖6 道路網(wǎng)絡(luò)拓?fù)銯ig.6 Road network topology

為了簡潔，記該應(yīng)用算例為算例11［33］。

3.2 實(shí)驗(yàn)參數(shù)設(shè)置

實(shí)驗(yàn)中用到的參數(shù)取值如表3 所示，對每個測試函數(shù)算法獨(dú)立運(yùn)行20 次，記錄得到的最優(yōu)解。

表3 相關(guān)參數(shù)及取值Tab.3 Related parameter and their values

3.3 實(shí)驗(yàn)結(jié)果與分析

表4 中測試算例1～10 為獨(dú)立運(yùn)行20 次后上層目標(biāo)函數(shù)的最好值、最差值和均值，對比算法為文獻(xiàn)［31-32，29］算法；算例11（應(yīng)用實(shí)例）的對比算法為文獻(xiàn)［33］算法。

從表4 可看出：

表4 上層目標(biāo)函數(shù)值的最好值、最差值和均值Tab.4 Best values，worst values and mean values of leader objective functions

1）前10 個算例中，本文算法相較于對比算法，找到的最優(yōu)解相同或更好（算例8 為更好）。本文算法找到每個算例上層目標(biāo)函數(shù)值的最好值、最差值和均值都一致，說明算法穩(wěn)定可行。在測試算例8 上，本文找到的上層目標(biāo)函數(shù)值（最好值、最差值和均值）都比相應(yīng)文獻(xiàn)中的最好值好，說明本文算法有較強(qiáng)的全局搜索能力。

2）對于算例11（應(yīng)用實(shí)例），本文算法找到了比文獻(xiàn)［33］算法更好的上層目標(biāo)函數(shù)值，并且上層目標(biāo)函數(shù)最好值、最差值和均值一致，說明用該算法求解應(yīng)用實(shí)例——資費(fèi)設(shè)置問題是可行有效的。

表5 為10 個測試算例上獲得的最優(yōu)解對比，表6 為最優(yōu)解對應(yīng)的下層目標(biāo)函數(shù)值對比。從表5～6 可看出，本文算法在算例8 中均能找到更好的最優(yōu)解。

表5 本文算法和比較算法的最優(yōu)解對比Tab.5 Best solutions comparison of the proposed algorithm and compared algorithms

表6 最優(yōu)解對應(yīng)的下層目標(biāo)函數(shù)值Tab.6 Follower objective function values corresponding to best solutions

為了檢測算法的計(jì)算時間，以算法找到最優(yōu)解為停止標(biāo)準(zhǔn)，記錄了算法找到最優(yōu)解時的平均CPU 時間（CPU）。為了顯示近似技術(shù)的有效性和比較的公平性，以本文算法為框架，對每個上層變量均求解下層問題，同樣以該算法找到最優(yōu)解為停止標(biāo)準(zhǔn)，獲得下層最優(yōu)解，記錄算法所需的CPU 時間（Update All CPU，UACPU），所有數(shù)據(jù)見表7。由表7 可知，UACPU 時間較長，CPU 時間較短，說明近似技術(shù)能有效提高找到最優(yōu)解的速度，減少運(yùn)行時間。對于求解資費(fèi)設(shè)置問題，本文算法能提高計(jì)算效率。

表7 本文算法的CPU時間和UACPU時間比較Tab.7 Comparison of CPU time and UACPU time of the proposed algorithm

4 結(jié)語

為了減少雙層規(guī)劃的計(jì)算量，本文提出了一種基于近似技術(shù)的進(jìn)化算法。本文算法通過多種群協(xié)同進(jìn)化的方式，僅僅求解部分下層問題，由近似技術(shù)得到下層問題的近似最優(yōu)解，并根據(jù)小種群的擬合程度選取下一代個體，最終獲得問題的全局最優(yōu)解。本文算法在保證計(jì)算精度的同時，節(jié)約了大量的下層計(jì)算量。本文算法未構(gòu)造插值函數(shù)和映射，在計(jì)算框架上更簡潔。

下一步，將研究算法中一些關(guān)鍵參數(shù)的取法，在自適應(yīng)分組、近似技術(shù)改進(jìn)等方面開展工作，提高算法在解決復(fù)雜優(yōu)化問題方面的效率。