一類雙層規劃問題的遺傳算法求解

于建平，杜綱

(天津大學管理與經濟學部，天津 300072)

一類雙層規劃問題的遺傳算法求解

于建平，杜綱

(天津大學管理與經濟學部，天津 300072)

研究了一類值型雙層規劃問題，即下層規劃將其目標函數最優值返回給上層規劃。在雙層規劃的解的基本概念的基礎上，給出了一種雙層的遺傳算法求解方法。該方法是在上層問題的遺傳算法中嵌套一個求解下層問題的遺傳算法。用實際的算例來驗證算法設計的可行性，同時通過與傳統算法結果的對比來表明該算法的計算效果。最后，指出了該算法的一些不足。

雙層規劃;解型;值型;遺傳算法;可行性

隨著工程設計的發展，很多重要的設計呈現出復雜的主從結構，難以用單層優化模型來描述，因而雙層規劃顯得不可替代。近年來，已有一些研究探討了雙層規劃在工程設計中的應用，如Shabde和Hoo［1］基于雙層規劃的框架建立了化工產品設計與過程控制協同優化的模型。作為雙層規劃中的一種重要情形，主從對策方法也得到了一些應用，如Hernandez等［2］在一個設計與維護的關聯優化問題上應用了主從對策方法。

雙層規劃(bilevel programming)也稱雙層優化，是指模型的約束中包含子優化問題的數學規劃，最早由Bracken和McGill［3］提出，由于它抽象了包括主從對策在內的一類重要的遞階決策問題而具有廣泛的實際背景。雙層規劃理論取得了較快的發展并成為數學規劃領域中的重要分支。雙層規劃雖然可以作為數學規劃的一種推廣形式，但它與普通數學規劃有著很大的不同。由于模型的上層中含有下層的最優解或最優值函數，使得模型易成為非光滑的優化問題，即使是線性的雙層規劃也是NP－難的［4］，并且當上層的約束中含有下層的最優解時，其可行域可能是不連通的。目前，雙層規劃的求解方法主要有針對特殊線性情形的K次最好法［5］，可采用K－T條件代替下層問題而轉化為單層規劃的方法［6］，利用對偶間隙構造罰函數而轉化為單層問題的方法［7］以及智能算法［8］等。由于一般雙層規劃求解的復雜性，Lai［9］等提出的滿意解法受到關注，該方法最初主要針對線性問題，后來被推廣到非線性的情形［10］。

雖然對于雙層規劃求解的研究很多，但常規的數學求解還僅限于一些特殊的問題。因本文提出的模型較復雜，故擬采用遺傳算法進行求解。遺傳算法是模擬生物進化中的選擇、交叉、變異過程來求解復雜優化問題的一種有效的方法，具有全局收斂性、魯棒性，且簡單通用［11］，但是針對不同的問題往往需要自身設定相應的遺傳算子。遺傳算法求解雙層規劃分為2方面:一是若模型屬于線性或非線性凸等特殊的雙層規劃，可根據情況采用K次最好法或由K－T條件轉化為單層規劃求解［12－14］;二是直接求解。這其中包括只用遺傳算法求解［15］和混合遺傳算法求解［16］。盡管國內外已有很多關于用遺傳算法求解雙層規劃的文獻，但其研究結果并不具有普適性。正如Coello［17］在其文章中所提到的:對于任何有約束的優化問題，沒有任何一個約束控制的方法可以使遺傳算法應用一切問題，每一個約束控制方法都有一定的適用范圍。

因此，本文只針對一類雙層規劃問題設計了相應的遺傳算法。寫作結構如下:第2部分是對問題背景的描述;第3部分提出了基于遺傳算法的求解方法;第4部分進行算例驗證，并與之前的研究做了效果比較;第5部分對文章進行簡要總結，闡述了結論和未來研究的方向。

1 問題描述

1.1 雙層規劃的一般模型和基本概念

王廣民等［18］根據國內外有關雙層規劃的文獻，給出了其數學模型和基本概念。雙層規劃的一般模型如下:

其中:x∈Rn，y∈Rm分別為上層和下層規劃問題的決策變量;F，f:Rn×Rm→R分別為上層和下層規劃問題的目標函數;g( h):Rn×Rm→Rp(Rq)分別為上層和下層規劃問題的約束條件。

上述的數學模型是解型雙層規劃的一般形式，即上層規劃問題的目標函數和約束條件不僅與上層規劃的決策變量有關，還依賴于下層規劃問題的最優解，而下層規劃的最優解又受上層決策變量的影響。

一些基本概念的定義如下:

1)雙層規劃問題的約束域:Ω={(x，y)| ( x，y)≤0，h( x，y)≤0}。

2)對于任意給定的x，下層規劃問題的可行域:Ω(x)={y|h( x，y)≤0}。

3)對于任意給定的x，下層規劃問題的合理反應集即下層問題的最優解集:M(x)={y|y∈rg min{ f( x，y)}，y∈Ω(x)}。

4)雙層規劃的誘導域即上層規劃的可行域: R={(x，y)|(x，y)∈Ω，y∈M(x)}。

5)雙層規劃問題的最優解(x*，y*)滿足?(x，y)∈IR有F( x*，y*)≤F( x，y)。

整個雙層規劃問題的復雜性取決于上下層規劃的特性，線性雙層規劃問題(即上下層規劃問題的目標函數和約束條件都是線性的)最為簡單，且易求解;相反，非線性雙層規劃不易求解，而且目標函數往往不可微、不連續、多峰，誘導域非凸、不連通，合理反應集M(x)為非單點集，這些都進一步增加了求解的難度。

1.2 問題的提出

本文根據處理工程設計問題中的實際需求，提出了一種值型雙層規劃問題，即上層規劃問題做出決策并反應給下層，下層規劃問題根據上層規劃的決策得出自身目標函數的最優值，然后將最優值反應給上層規劃。它的一般形式如下:

其中:lbx∈Rn(lby∈Rm)和ubx∈Rn(uby∈Rm)分別為決策變量x(y)的下界和上界;v(x):Rn×Rm→R為上層規劃問題的決策x固定時下層規劃問題的目標函數最優值。

上述雙層規劃的上層規劃問題的目標函數不僅與上層規劃的決策變量有關，而且依賴于下層規劃問題的目標函數的最優值，而下層規劃的最優值又受上層決策變量的影響;上層問題的約束條件不含有下層問題的決策變量;x和y都有上下界約束;x和y既可以是連續變量，也可以是離散變量。此類問題的基本概念與1.1節中雙層規劃的基本概念是一致的，但它可避免當下層規劃為多峰問題時無法找到雙層規劃問題的全局最優解的情況。

2 算法設計

遺傳算法是求解復雜優化問題的一種新型有效的方法。已有學者將其應用到求解雙層規劃的問題上。本文依據雙層規劃的解的概念和遺傳算法的一般流程設計了一種求解1.2中問題的方法。

2.1 遺傳算法設計流程

為了有效地求解模型(2)，本文設計了一個嵌套的遺傳算法。該方法先產生上層規劃的初始種群，驗證其可行性，然后將每一個可行的上層決策x代入下層規劃，下層規劃利用遺傳算法求解出最優決策y*(x)和最優值v(x)，同時下層把最優值v(x)返回給上層來求解上層決策的適應度值，隨后將上層決策種群進行選擇、交叉、變異，按照此步驟循環一定的次數后，得到上層規劃的最優解x*和相應的下層問題的最優解()。上述方法的流程如圖1所示。

圖1 遺傳算法求解流程

2.2 遺傳算法的具體步驟

步驟1(初始化和編碼)在上層規劃的界約束上隨機生成Nl個初始解。對于連續型變量，本文采用二進制編碼，每個變量的編碼長度根據求解精度和其上下界來確定;對于離散型的變量，本文采用有序數組的標記方法，即實數編碼。例如，如果變量x1為一離散變量，其取值為數列{x11，x12，…，x1n1}中的數，n1為數列中的元素個數，具體編碼策略如圖2所示。

圖2 離散型變量的編碼策略

步驟2(嵌套遺傳算法)針對上層規劃種群的每個可行個體x，利用遺傳算法求解下層規劃問題:首先設定遺傳代數為當前外層循環次數，同時設定下層遺傳算法的個體數量Nf;然后對下層規劃進行初始化(編碼方式同步驟1)，基于下層優化目標函數進行個體評價(評價采用動態罰函數方法［19］)，再進行選擇操作、交叉操作以及變異操作;最后求得上層種群可行個體所對應的下層規劃的最優解y*(x)和最優值v(x)，記錄最優解并將最優值返回上層。

步驟3(上層規劃的適應度值)對于上層規劃的可行個體x，通過嵌套的遺傳算法得到對應的下層問題的最優值v(x);然后代入上層問題的目標函數F( x，v(x ));最后比較所有可行個體對應的目標函數值，得出最大的一個，并記為Fmax，用當前代的Fmax與上一代的Fmax做比較。如果當前代的Fmax大，就保留;如果上一代的Fmax大，就用其替代。利用式子Fmax－F( x，v(x ))計算每一個可行個體的適應度值，對于不可行個體，則設其適應度值為零。

步驟4(終止條件)如果當前代達到最大迭代次數，則停止，并將當前的最優個體和其對應的下層問題的最優解作為雙層規劃的最優解記錄下來;如果未達到最大迭代次數，則繼續步驟5。

步驟5(選擇、交叉、變異)設定交叉概率和變異概率，針對上層問題的種群分別采用輪盤賭方法、均勻交叉、均勻變異的方法進行選擇、交叉、變異，記錄變異后的種群為新一代的種群，然后重復步驟2。

3 數值實驗

為了驗證嵌套遺傳算法的計算性能以及魯棒性，本文將其與傳統的雙層規劃求解方法進行比較。為了更好地顯示算法的可行性和效果，本文選取了3種不同的算例進行測試。第1個為線性雙層規劃問題(上下層規劃都為線性規劃);第2個是下層為非線性雙層規劃問題;第3個為混合型的雙層規劃問題。上下層遺傳算法的參數設置如下:種群規模為50，迭代次數為200，二進制編碼的精度為0.01，交叉概率為0.8，變異概率為0.01。

圖3 測試問題1的遺傳算法迭代圖像

測試問題2:

測試問題2是一個非線性雙層規劃問題，已有方法求解的最優值和最優解為［21］:

本文最優計算結果為(遺傳算法迭代圖像如圖4所示):

從兩種結果來看:最優解的差別比較大，而最優值的差距仍然在0.01左右。這一方面說明了此問題有可能是一個多峰問題，另一方面也說明了本文算法的可行性和有效性。

圖4 測試問題2的遺傳算法迭代圖像

測試問題3:

測試問題3是一個混合型雙層規劃問題，已有方法求解的最優值和最優解為［22］:

本文最優計算結果為(遺傳算法迭代圖像如圖5所示):

圖5 測試問題3的遺傳算法迭代圖像

由兩種結果可以看出:最優值的差距不足0.01。這也進一步說明了本文遺傳算法的有效性，它不僅可以求解連續型的雙層規劃問題，也能求解混合型的雙層規劃問題。

4 結束語

本文根據值型雙層規劃的特點——可以避免下層規劃為多峰問題時雙層規劃無解的情況，提出了一種嵌套的遺傳算法，并通過算例驗證了算法的效果及其可行性，給解決實際問題提供了一個有效的計算方法。雖然本文的算法在求解值型雙層規劃時具有一定的適用性，但是當上下層規劃問題非常復雜、可行域比較小，而搜索范圍過大時，往往不易找到可行解。這也是本文沒有在模型(2)中加入等式約束的原因。在今后的研究中可嘗試加入一種使初始化種群在可行域中產生的方法［20］，即確定可行域的方法，使交叉、變異算子都為可行算子［21］，即交叉、變異后的個體都為可行個體，或是采用某種修復策略將不可行的個體變為可行個體。

［1］Vikram，Shabde，Hoo.Optimum controller design for a spray drying process［J］.Control Engineering Practice，2008，16(5):541－552.

［2］Hernandez，Seepersad，Mistree.Designing for maintenance:a game theoretic approach［J］.Eng.Opt.，2002，34 (6):561－577.

［3］Bracken J，JTMcGill.Mathematical programs with optimization problems in the constraints［J］.Operations Research，1973，21(1):37－44.

［4］Jeroslow R G.The polynomial hierarchy and a simple model for competitive analysis［J］.Mathematical programming，1985，32(2):146－164.

［5］Bialas W F，Karwan M H.Two－level Linear Programming［J］.Management Science，1984，30(8):1004－1021.

［6］Fortuny－Amat J，McCarl B.A representation and economic interpretation of a two－level programming problem［J］.Journal of the Operational Research Society，1981，32 (9):783－792.

［7］Anandalingam G，White D J.A solution method for the linear static Stackelberg problem using penalty functions［J］.IEEE Transactions on Automatic Control，1990，35 (10):1170－1173.

［8］Mathieu R，Pittard L，Anandalingam G.Genetic algorithm based approach to bi－level linear programming［J］.RAIRO Rechercheoperationnelle，1994，28(1):1－21.

［9］Lai Y J.Hierarchical optimization:A satisfactory solution［J］.Fuzzy sets and systems，1996，77(3):321－335.

［10］OE Emam.A fuzzy approach for bi－level integer non－linear programming problem［J］.Applied mathematics and computation，2006，172(1):62－71.

［11］席裕庚，柴天佑.遺傳算法綜述［J］.控制理論與應用，1996(6):697－708.

［12］Hejazi S R，AMemariani G Jahanshahloo.Linear bilevel programming solution by genetic algorithm［J］.Computers＆Operations Research，2002，29(13):1913－1925.

［13］常永明，王宇平.求解一類特殊的雙層規劃問題的遺傳算法［J］.計算機工程與應用，2009，45(3):45－47.

［14］王越，許全文，黃麗豐.基于改進遺傳算法的連續函數優化［J］.重慶理工大學學報:自然科學版，2011，25 (2):62－67.

［15］Oduguwa V，Roy R.Bi－level Optimisation using Genetic Algorithm［C］//Proceedings of the 2002 IEEE International Conference on Artificial Intelligence Systems.［S.l.］:［s.n.］，2002:322－327.

［16］李和成，王宇平.幾類非線性雙層規劃問題的混合遺傳算法［J］.系統工程與電子技術，2008，30(6):1168－1172.

［17］Coello.Theoretical and numerical constraint－handling techniques used with evolutionary algorithms:a survey of the state of the art［J］.Computer methods in applied mechanics and engineering，2002，191(11):1245－1287.

［18］王廣民，萬仲平，王先甲.二(雙)層規劃綜述［J］.數學進展，2007，36(5):513－529.

［19］Kramer O.A review of constraint－handling techniques for evolution strategies［J］.Applied Computational Intelligence and Soft Computing，2010:1－11.

［20］Li X，Du G.Inequality constraint handling in genetic algorithms using a boundary simulation method［J］.Computers＆Operations Research，2012，39(3):521－540.

［21］Liu B.Stackelberg－Nash equilibrium for multilevel programming with multiple followers using genetic algorithms［J］.Computers＆Mathematics with Applications，1998，36(7):79－89.

［22］宿潔，馬建華.兩類線性雙層規劃的算法［J］.經濟數學，2002，19(1):68－76.

(責任編輯 劉舸)

Genetic Algorithm for Solving a Class of Bi-level Programming Problems

YU Jian－ping，DU Gang
(College of Management and Economics，Tianjin University，Tianjin 300072，China)

This paper studies a kind of value－type bi－level programming，namely the lower programming returns its optimal value of the objective function to upper level.Based on the basic concept of solution of the bi－level programming，we propose a method of two－level genetic algorithm.This method nests a genetic algorithm in genetic algorithm of the upper problem to solve a problem in the lower.Then，this paper uses practical examples to verify the feasibility of algorithm design，while the computation result of algorithm design is compared with the traditional algorithm to illustrate the calculating effectiveness.In the end，this paper puts forward some disadvantages of the algorithm.

bi－level programming;solution－type;value－type;genetic algorithm;feasibility

TP 18;O221

A

1674－8425(2014)04－0093－06

10.3969/j.issn.1674－8425(z).2014.04.020

2013－12－15

國家自然科學基金資助項目(71071104)

于建平(1987—)，男，碩士研究生，主要從事工業工程方面的研究。

于建平，杜綱.一類雙層規劃問題的遺傳算法求解［J］.重慶理工大學學報:自然科學版，2014(4):93－98.Citation format:YU Jian－ping，DU Gang.Genetic Algorithm for Solving a Class of Bi－level Programming Problems［J］.Journal of Chongqing University of Technology:Natural Science，2014(4):93－98.