一類雙層規(guī)劃問題的遺傳算法求解

于建平，杜綱

(天津大學(xué)管理與經(jīng)濟(jì)學(xué)部，天津 300072)

一類雙層規(guī)劃問題的遺傳算法求解

于建平，杜綱

(天津大學(xué)管理與經(jīng)濟(jì)學(xué)部，天津 300072)

研究了一類值型雙層規(guī)劃問題，即下層規(guī)劃將其目標(biāo)函數(shù)最優(yōu)值返回給上層規(guī)劃。在雙層規(guī)劃的解的基本概念的基礎(chǔ)上，給出了一種雙層的遺傳算法求解方法。該方法是在上層問題的遺傳算法中嵌套一個求解下層問題的遺傳算法。用實(shí)際的算例來驗(yàn)證算法設(shè)計的可行性，同時通過與傳統(tǒng)算法結(jié)果的對比來表明該算法的計算效果。最后，指出了該算法的一些不足。

雙層規(guī)劃;解型;值型;遺傳算法;可行性

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

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

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

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

1 問題描述

1.1 雙層規(guī)劃的一般模型和基本概念

王廣民等［18］根據(jù)國內(nèi)外有關(guān)雙層規(guī)劃的文獻(xiàn)，給出了其數(shù)學(xué)模型和基本概念。雙層規(guī)劃的一般模型如下:

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

上述的數(shù)學(xué)模型是解型雙層規(guī)劃的一般形式，即上層規(guī)劃問題的目標(biāo)函數(shù)和約束條件不僅與上層規(guī)劃的決策變量有關(guān)，還依賴于下層規(guī)劃問題的最優(yōu)解，而下層規(guī)劃的最優(yōu)解又受上層決策變量的影響。

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

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

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

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

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

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

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

1.2 問題的提出

本文根據(jù)處理工程設(shè)計問題中的實(shí)際需求，提出了一種值型雙層規(guī)劃問題，即上層規(guī)劃問題做出決策并反應(yīng)給下層，下層規(guī)劃問題根據(jù)上層規(guī)劃的決策得出自身目標(biāo)函數(shù)的最優(yōu)值，然后將最優(yōu)值反應(yīng)給上層規(guī)劃。它的一般形式如下:

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

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

2 算法設(shè)計

遺傳算法是求解復(fù)雜優(yōu)化問題的一種新型有效的方法。已有學(xué)者將其應(yīng)用到求解雙層規(guī)劃的問題上。本文依據(jù)雙層規(guī)劃的解的概念和遺傳算法的一般流程設(shè)計了一種求解1.2中問題的方法。

2.1 遺傳算法設(shè)計流程

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

圖1 遺傳算法求解流程

2.2 遺傳算法的具體步驟

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

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

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

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

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

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

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

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

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

測試問題2:

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

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

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

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

測試問題3:

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

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

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

由兩種結(jié)果可以看出:最優(yōu)值的差距不足0.01。這也進(jìn)一步說明了本文遺傳算法的有效性，它不僅可以求解連續(xù)型的雙層規(guī)劃問題，也能求解混合型的雙層規(guī)劃問題。

4 結(jié)束語

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

［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］.控制理論與應(yīng)用，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］常永明，王宇平.求解一類特殊的雙層規(guī)劃問題的遺傳算法［J］.計算機(jī)工程與應(yīng)用，2009，45(3):45－47.

［14］王越，許全文，黃麗豐.基于改進(jìn)遺傳算法的連續(xù)函數(shù)優(yōu)化［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，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］李和成，王宇平.幾類非線性雙層規(guī)劃問題的混合遺傳算法［J］.系統(tǒng)工程與電子技術(shù)，2008，30(6):1168－1172.

［17］Coello.Theoretical and numerical constraint－h(huán)andling 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］王廣民，萬仲平，王先甲.二(雙)層規(guī)劃綜述［J］.數(shù)學(xué)進(jìn)展，2007，36(5):513－529.

［19］Kramer O.A review of constraint－h(huán)andling 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］宿潔，馬建華.兩類線性雙層規(guī)劃的算法［J］.經(jīng)濟(jì)數(shù)學(xué)，2002，19(1):68－76.

(責(zé)任編輯 劉舸)

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

國家自然科學(xué)基金資助項(xiàng)目(71071104)

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

于建平，杜綱.一類雙層規(guī)劃問題的遺傳算法求解［J］.重慶理工大學(xué)學(xué)報:自然科學(xué)版，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.