摘 要：分布估計算法是遺傳算法和統(tǒng)計學(xué)習(xí)的結(jié)合，通過統(tǒng)計學(xué)習(xí)的手段建立解空間內(nèi)個體分布的概率模型，對概率模型隨機(jī)采樣產(chǎn)生新的群體，如此反復(fù)進(jìn)行，實(shí)現(xiàn)群體的進(jìn)化。將分布估計算法推廣應(yīng)用到整數(shù)規(guī)劃的解空間中，提出一種求解整數(shù)規(guī)劃的新算法，經(jīng)數(shù)值實(shí)驗(yàn)表明該算法有效。

關(guān)鍵詞：分布估計算法；非線性整數(shù)規(guī)劃；概率模型；解空間

中圖分類號：O224；TP183 文獻(xiàn)標(biāo)識碼：B 文章編號：1004-373X(2008)10-129-03

Method of Estimation Distribution Algorithm for Solving Nonlinear Integer Programming

XIONG Shengwu1，LIU Mingfang1，LIU Xinliang2

(1.School of Computer Science and Technology，Wuhan University of Technology，Wuhan，430070，China;

2.Information System and Management College，National University of Defense Technology，Changsha，410073，China)

Abstract：Estimation of Distribution Algorithms (EDAs) acquire solutions by statistically learning and sampling the probability distribution of the best individuals of the population at each iteration of the algorithm.An estimation distribution algorithm is developed for nonlinear integer programming in this paper.It is shown that the method is efficient by the numerical experiment.

Keywords：estimation of distribution algorithms;nonlinear integer programming;probability model;solution space

1 引 言

整數(shù)規(guī)劃是數(shù)學(xué)規(guī)劃中較復(fù)雜的一大類問題。Murty^[1]證明了非線性規(guī)劃問題為NP-hard問題，作為其子集的非線性整數(shù)規(guī)劃也必為NP-hard問題，求解該問題精確解的算法具有指數(shù)復(fù)雜度。整數(shù)規(guī)劃廣泛應(yīng)用于許多工程領(lǐng)域，如資源管理、生產(chǎn)調(diào)度、可靠性優(yōu)化、目標(biāo)分配、超大規(guī)模集成電路設(shè)計等。對于變量規(guī)模較小的整數(shù)規(guī)劃，傳統(tǒng)的求解方法有分支定界法、割平面法和隱枚舉法等。但對于較大規(guī)模的問題，傳統(tǒng)的方法比較耗時，近年來隨著進(jìn)化計算的發(fā)展，許多學(xué)者運(yùn)用遺傳算法(GA)、模擬退火算法(SA)、微粒群算法(PSO)、蟻群算法(AA)等方法來求解整數(shù)規(guī)劃問題^[2-6]。遺傳算法吸取了生物進(jìn)化和遺傳變異論的研究成果，是一種群體性全局尋優(yōu)方法，但算法執(zhí)行到一定階段后向最優(yōu)解收斂速度緩慢，且遺傳算法的性能依賴于遺傳因子（選擇概率、交叉概率、變異概率、種群規(guī)模、染色體長度等）的取值，并且會出現(xiàn)早熟收斂情況。模擬退火算法模擬物質(zhì)材料的冷卻與結(jié)晶過程，通過退火溫度控制搜索過程，但當(dāng)問題規(guī)模較大時，系統(tǒng)進(jìn)入熱平衡狀態(tài)(對應(yīng)于最優(yōu)解)的時間較長。粒子群算法和蟻群算法性能也依賴于設(shè)定參數(shù)（如強(qiáng)度的衰減系數(shù)等），參數(shù)設(shè)定的優(yōu)劣直接影響算法的運(yùn)算效果。分布估計算法提出一種全新的進(jìn)化模式，通過統(tǒng)計學(xué)習(xí)的手段建立解空間內(nèi)個體分布的概率模型，然后對概率模型隨機(jī)采樣產(chǎn)生新的群體，如此反復(fù)進(jìn)行，實(shí)現(xiàn)群體的進(jìn)化。本文將分布估計算法推廣應(yīng)用到整數(shù)規(guī)劃的解空間中，提出一種求解整數(shù)規(guī)劃的新算法。

2 分布估計算法

分布估計算法（Estimation of Distribution Algorithms，EDAs）^[7-9]是在進(jìn)化計算領(lǐng)域興起了一類新型的優(yōu)化算法，是一種全新的進(jìn)化模式。EDAs是在1996年由M[AKu¨]hlenbein 和Paaβ提出的一種廣義型求解法。相對于傳統(tǒng)的GA，在EDAs生成后代種群的過程中不需要交叉、變異操作，取而代之的是從一個概率分布中采樣新的個體生成新的種群，而此概率模型是根據(jù)包含有從前代種群中挑選出來的個體的數(shù)據(jù)集估計而來。分布估計算法通過一個概率模型描述候選解在空間的分布，采用統(tǒng)計學(xué)習(xí)手段從群體宏觀的角度建立一個描述解分布的概率模型，然后對概率模型隨機(jī)采樣產(chǎn)生新的種群，如此反復(fù)進(jìn)行，實(shí)現(xiàn)種群的進(jìn)化，直到滿足停止準(zhǔn)則。

根據(jù)概率模型的復(fù)雜程度以及不同的采樣方法，分布估計算法發(fā)展很多不同的具體實(shí)現(xiàn)方法，但是都可以歸納為下面的基本步驟：首先隨機(jī)生成M個個體，并有這些個體決定初始群體D0，并且對所有的個體進(jìn)行評估。然后執(zhí)行第一步，挑選N（N≤M）個個體（通稱他們都擁有最好的目標(biāo)函數(shù)值）。然后生成一個能最好的反映出n個變量相互依賴關(guān)系的n維概率模型。在根據(jù)上一步所得的概率分布獲得M個新的個體組成新的種群。然后循環(huán)這3步，直到滿足停止準(zhǔn)則。

其偽代碼形式如下：



Pseudo-code of EDAs：

D0←：Generate M individuals (the initial population) at random

Repeat for t=1，2，… until the stopping criterion is met

Dst－1←：SelectN≤Mindividuals from Dt－1according to the selection method

Pt(x)=P(xDst－1)←：Estimate the probability distribution of an individual being among the selected individuals

Dt←：Sample M individuals (the new population) from Pt(x)

3 非線性整數(shù)規(guī)劃問題

有約束的整數(shù)規(guī)劃模數(shù)學(xué)模型為：

[WB]Minimizef(X)=f(x1，x2，…，xn)

Subjecttoli≤xi≤ui i=1，2，…，n

xi∈Z i=1，2，…，n

上式中：[WTHZ]Z為整數(shù)空間；變量xi的下、上限li，ui為整數(shù)，w=ui－li+1為xi的可能取的個數(shù)。對很多類實(shí)際應(yīng)用組合優(yōu)化問題，xi的可行域可以枚舉。

可行解空間如圖1所示，xi有ai個節(jié)點(diǎn)，每個變量取一個值就構(gòu)成空間一個解。如xi取第mi個節(jié)點(diǎn)，則對應(yīng)的解為(x1，x2，…，xn)=(l1+m1－1，l2+m2－1，…，ln+mn－1)。

圖1 可行解空間

對于有約束的整數(shù)規(guī)劃可以把原約束方程作為罰函數(shù)項加入到原目標(biāo)中，變成無約束的優(yōu)化問題?；诖?，本文主要研究無約束整數(shù)規(guī)劃問題的求解方法。

4 整數(shù)規(guī)劃的分布估計算法

4.1 解空間的概率模型

在討論的非線性整數(shù)規(guī)劃問題中，描述解空間的概率模型用簡單的概率向量p=(p1，p2，…，pn)表示，p表示群體的概率分布。

4.2 初始化群體

初始群體D0在解空間按照均勻分布隨機(jī)抽樣產(chǎn)生。即概率向量p0(x)=p0(x1，x2，…，xn)=∏ni=1p0(xi)，其中p0(xi=li+mj－1)=1w，i=1，2，…，n；j=1，2，…，ui-li+1。群體規(guī)模為2s，通過適應(yīng)值函數(shù)f(x)計算各個個體的適應(yīng)值。

4.3 新解產(chǎn)生

在此選擇截斷方法作為選擇策略，選擇種群的一半，即選擇適應(yīng)值較高的s個個體，Dsl。因此Dsl表示第l代選擇后的優(yōu)勢群體。概率向量p通過表達(dá)式p1(x)=p1(x1，x2，…，xn)=∏ni=1p(xi|Dsl-1)更新。根據(jù)這個概率向量p通過隨機(jī)采樣的方法產(chǎn)生新一代群體，至此分布估計算法完成了一個周期?？梢娫诓粩嘀貜?fù)產(chǎn)生新解的過程中，適應(yīng)值高的個體的出現(xiàn)概率越來越大。按照這個步驟改變個體在解空間的概率分布，使適應(yīng)值高的個體分布概率變大，適應(yīng)值低的個體分布概率變小，如此反復(fù)進(jìn)化，最終將產(chǎn)生問題的最優(yōu)解。

4.4 停止準(zhǔn)則

由于概率向量p的作用，當(dāng)?shù)螖?shù)足夠多時，概率向量p會逐漸增大到1，這時產(chǎn)生問題的最優(yōu)解。即停止準(zhǔn)則為p=1。

4.5 算法步驟

算法步驟為：

（1） 隨機(jī)產(chǎn)生2s個個體（即初始群體）D0；

（2） 通過適應(yīng)值函數(shù)f(x)計算各個個體的適應(yīng)值；

（3） 以截斷方法作為選擇策略，選擇種群的一半，即選擇適應(yīng)值較高的s個個體，Dsl-1；

（4） 估計選擇的s個個體中每個個體的概率分布pl(x)=p(x|Dsl－1)，并通過這個表達(dá)式更新概率向量p；

（5） 根據(jù)概率向量p通過隨機(jī)采樣的方法產(chǎn)生新一代群體Dsl；

（6） 如果沒有滿足停止準(zhǔn)則，返回第（2）步。

5 算 例

為了驗(yàn)證上述分布估計算法求解非線性整數(shù)規(guī)劃的有效性，用EDAs解下列算例^[10]：

算例F1： min F1=|x1|+|x2|+…+|x10|

St.－10≤xi≤10，xi∈Z(i=1，2，…，10)

算例F2： min F2=x21+x22+…+x210

St.－10≤xi≤10，xi∈Z(i=1，2，…，10)

算例F3： min F3=(x1－10x2)2+5(x3－x4)2+(x2－2x3)4+10(x1－10x4)4

St.－10≤xi≤10，xi∈Z(i=1，2，…，4)

采用本文所提出的算法，利用Java語言編程求解算例。隨機(jī)產(chǎn)生100個個體組成初始種群D0（s=50），計算適應(yīng)值之后以截斷方法作為選擇策略，選取適應(yīng)值較高的50個個體，估計這50個個體的概率分布更新向量p，在根據(jù)p[WTBZ]通過隨機(jī)采樣的方法產(chǎn)生100個個體的新一代群體。反復(fù)執(zhí)行直到滿足停止準(zhǔn)則，求得全局最優(yōu)解，最優(yōu)解取值如表1所示。

圖2 采用EDA算法的算例計算結(jié)果圖

6 結(jié) 語

分布估計算法是進(jìn)化計算領(lǐng)域內(nèi)一個嶄新的分支，他通過對整個群體建立數(shù)學(xué)模型，直接描述整個群體的進(jìn)化趨勢，是對生物進(jìn)化“宏觀”層面上的數(shù)學(xué)建模。分布估計算法通過概率模型可以描述變量之間的相互關(guān)系，對于解決非線性整數(shù)問題更加有效。通過算例，說明本文給出的算法有效。

參 考 文 獻(xiàn)

［1］Katta G Murty.Some NP-complete Problem in Quadratic and Nonlinear Programming［J］.Mathematical Programming.1987(39):117-129.

［2］Rudolph G．An Evolutionary Algorithm for Integer Programming．Parallel Problem Solving from Natures—PPSN Ⅲ［M］.Lecture Notes in Computer Science，Springer，Berlin.1994．

［3］豐建榮，劉志河，劉正和.混合整數(shù)規(guī)劃問題遺傳算法的研究及仿真實(shí)現(xiàn)［J］.系統(tǒng)仿真學(xué)報，2004，16(4):845-848．

［4］謝云．用模擬退火算法并行求解整數(shù)規(guī)劃問題［J］．高技術(shù)通訊，1991，1(10):21-26.

［5］譚瑛，高慧敏，曾建潮.求解整數(shù)規(guī)劃問題的微粒群算法［J］.系統(tǒng)工程理論與實(shí)踐，2004，24(5):126-129.

［6］黃樟燦，吳方才，胡曉林.基于信息素的整數(shù)規(guī)劃的演化求解［J］.計算機(jī)應(yīng)用研究，2001，18(7):27-29.

［7］Bengoetxea E，Larra[AKnˇ]aga P，Bloch I，et al.Solving graph Matching with EDAs Using a Permutation-based Representation.Estimation of Distribution Algorithms.A New Tool for Evolutionary Computation.Kluwer Academic Publishers，2002.

［8］Zhang Qingfu，Sun Jianyong，Edward Tsang，et al.Estimation of Distribution Algorithm with′2-opt Local Search for the Quadratic Assignment Problem.StudFuzz，2006:281-292.

［9］Jiri Oceanasek.Entropy-based Convergence Measurement in Discrete Estimation of Distribution Algorithms.StudFuzz，2006:39-50.

［10］Pearl J.Probabilistic Reasoning in Intelligent System[M].Morgan Kaufmann Publishers，1988.

作者簡介 熊盛武 男，1967年出生，湖北武漢人，博士，教授，武漢理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院。主要研究方向?yàn)橹悄苡嬎恪C(jī)器學(xué)習(xí)。

劉明芳 女，1980年出生，山東濱州人，碩士研究生，武漢理工大學(xué)計算機(jī)科學(xué)與技術(shù)學(xué)院。主要研究方向?yàn)橹悄苡嬎?、計算機(jī)軟件理論及可靠性分析。

劉新亮 男，1982年出生，山東濱州人，博士研究生，國防科技大學(xué)信息系統(tǒng)與管理學(xué)院。主要研究方向?yàn)橄到y(tǒng)工程、系統(tǒng)優(yōu)化分析。

注：本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。