沈瑜，李和成，陳黎娟

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

0 引言

在工程和經(jīng)濟管理領域，經(jīng)常出現(xiàn)具有遞階結構的決策問題，這類問題中決策者處在不同的層次上。首先，處在上層的決策者為了優(yōu)化自己的目標，提出一個決策方案；處在下層的決策者根據(jù)上層提供的方案，選擇一個下層問題的最優(yōu)決策方案并反饋上層；上層結合下層反饋的方案評價自己給出的方案，該過程持續(xù)進行，直到使上層目標達到最優(yō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 是上層問題的目標函數(shù)，f(x，y)：Rn+m→R 是下層問題的目標函數(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）的一個雙層可行點。求解式（1）～（2）的目的就是在可行解集中選擇使上層目標F(x，y)最小的雙層可行點。如果對于一個給定的上層變量x，下層問題存在多個最優(yōu)解y與其對應，這種情況涉及下層最優(yōu)解的選擇，不同的選擇模式有不同的雙層規(guī)劃模型［2］。為了使雙層規(guī)劃問題結構簡潔，在設計算法時更多地關注問題的遞階結構，現(xiàn)有的文獻通常假設下層問題的最優(yōu)解是唯一的［3］。本文的目的是提高算法處理遞階結構的能力。因此，仍然保留下層問題最優(yōu)解唯一的假設。

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

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

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

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

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

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

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

1 基本概念

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

2 本文算法

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

步驟1 種群初始化。

首先在上層可行區(qū)域內均勻產(chǎn)生K個點xck(k=1，2，…，K)，即K個上層變量值；然后，在以這K個點為中心的鄰域內均勻產(chǎn)生-1 個點。共得到M個點，不妨設這M個點均在上層決策空間的投影區(qū)域內，如若不然，重新產(chǎ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 個體評估。

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

步驟3 交叉操作。

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

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

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

步驟4 變異操作。

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

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

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

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

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

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

步驟5 后代個體預評估。

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

步驟6 驗證后代種群的擬合程度。

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

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

步驟7 選擇操作。

步驟8 算法停止。

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

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

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

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

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

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

對于?x∈[0，5]，式（10）的誘導區(qū)域為：

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

圖3 式（10）的誘導域Fig.3 Inducible region of Equation（10）

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

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

圖4 下層解的散點圖Fig.4 Scatter diagram of follower solutions

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

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

3 數(shù)值實驗

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

算例1［31］：

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

為了說明本文算法在求解實際應用問題方面的有效性，考慮實踐常見的資費設置問題，該問題的模型如下：

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

該模型對應的網(wǎng)絡拓撲結構見圖6，其中：

圖6 道路網(wǎng)絡拓撲Fig.6 Road network topology

為了簡潔，記該應用算例為算例11［33］。

3.2 實驗參數(shù)設置

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

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

3.3 實驗結果與分析

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

從表4 可看出：

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

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

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

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

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

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

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

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

4 結語

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

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