朱志同 趙 陽 李 煒, 郭 星,

1(安徽大學(xué)計(jì)算智能與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室 安徽 合肥 230039)2(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)

基于改進(jìn)果蠅算法求解混合整數(shù)非線性規(guī)劃問題

朱志同1趙 陽2李 煒1,2郭 星1,2

1(安徽大學(xué)計(jì)算智能與信號(hào)處理重點(diǎn)實(shí)驗(yàn)室 安徽 合肥 230039)2(安徽大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 安徽 合肥 230601)

在科學(xué)及工程系統(tǒng)設(shè)計(jì)中存在許多混合整數(shù)非線性規(guī)劃MINLP(Mixed-Integer NonLinear Programming)問題，該類問題變量類型豐富且約束條件較多，難以求解，為此提出一種改進(jìn)果蠅算法。該算法對(duì)不同類型變量的更新采取不同的策略，并采用周期性的步長函數(shù)指導(dǎo)果蠅的尋優(yōu)，使其避免陷入局部最優(yōu)。并通過與另外兩種常用的算法在穩(wěn)定性、收斂速度等方面進(jìn)行了比較，實(shí)驗(yàn)結(jié)果表明該改進(jìn)的果蠅算法效果較優(yōu)，能有效地解決MINLP問題。

混合整數(shù)非線性規(guī)劃 智能計(jì)算 果蠅算法

0 引 言

在科學(xué)及工程系統(tǒng)設(shè)計(jì)中存在許多問題都是非線性規(guī)劃問題，其中混合整數(shù)非線性規(guī)劃MINLP又是非線性規(guī)劃的一個(gè)重要分支[1]?；旌险麛?shù)非線性規(guī)劃是同時(shí)包含離散性變量和連續(xù)性變量的優(yōu)化問題，許多組合優(yōu)化問題如：TSP問題、0-1背包問題等都可視為MNLP問題。對(duì)于MNLP問題，其目標(biāo)函數(shù)和約束條件的非線性，使得結(jié)果往往存在局部最優(yōu)解[2]。

解決MINLP主要有確定性方法和隨機(jī)性方法[3]。確定性方法如分枝定界法(B&B)、外逼近法(OA)、廣義Bender分解法(CBD)，但這些方法局限性很大：一是計(jì)算量太大；二是不利于編程求解。如分枝定界法取消或放寬原問題的約束，并將改變后的問題分解成多個(gè)子問題進(jìn)行求解，以此確定原問題的最優(yōu)解或其最優(yōu)解所在的區(qū)間，由此可以看出該方法不適宜用編程的方法去求解。近年來，越來越多的隨機(jī)性方法應(yīng)用于MINLP，如遺傳算法(GA)、差分進(jìn)化算法(DE)、粒子群算法(PSO)等[4-5]。但這些方法也各有缺點(diǎn)，例如：遺傳算法易于早熟且計(jì)算量大；差分進(jìn)化算法過于復(fù)雜且計(jì)算耗時(shí)多；粒子群算法容易陷入局部最優(yōu)[6]。

潘文超[7]于2011年提出了果蠅優(yōu)化算法FOA (Fruit Fly Optimization Algorithm)。該算法也屬于群智能算法的一種，作為新型的進(jìn)化算法，與其他算法相比，F(xiàn)OA在先天上就有很多優(yōu)勢(shì)，易于理解且實(shí)現(xiàn)簡單，全局尋優(yōu)能力強(qiáng)且收斂速度快，但缺點(diǎn)在于穩(wěn)定性不足，易于陷入局部最優(yōu)[8]。隨著研究的深入，很多學(xué)者對(duì)果蠅算法進(jìn)行了改進(jìn)，在保持其優(yōu)勢(shì)的情況下，盡量提高其穩(wěn)定性及跳出局部最優(yōu)的能力。目前已有研究，大多是求解連續(xù)性問題，沒有應(yīng)用于解決具有離散變量的實(shí)際問題[9]。本文通過改進(jìn)果蠅算法，使之能有效地解決混合整數(shù)非線性規(guī)劃這一實(shí)際問題[10-11]。

1 果蠅算法

1.1 基本果蠅算法

果蠅算法是基于動(dòng)物群體覓食行為演化出的一種全局尋優(yōu)新方法。果蠅在視覺和嗅覺上優(yōu)于其他物種，其發(fā)現(xiàn)食物行為的特點(diǎn)包括：① 果蠅個(gè)體使用嗅覺器官分辨食物的氣味來源并朝這個(gè)方向飛行；② 果蠅在飛行過程中使用視覺去尋找食物[12]。

其具體過程如下：

① 初始化參數(shù)，果蠅種群數(shù)量(mSize)，迭代次數(shù)(pSize)，飛行范圍也即自變量的定義域(dom)。

② 隨機(jī)初始化果蠅群位置(xis,yis):

xis=rand(dom)

(1)

yis=rand(dom)

(2)

③ 果蠅個(gè)體先使用嗅覺分別食物氣味的方向并立即飛向該方向，再使用視覺發(fā)現(xiàn)該食物，RandomValue為[-1,1]上的隨機(jī)值，其值的正負(fù)表示果蠅飛行的方向，大小表示果蠅飛行的距離:

xi=xis+RandomValue

(3)

yi=yis+RandomValue

(4)

④ 計(jì)算每只果蠅當(dāng)前位置與原點(diǎn)的距離(disti)及食物的氣味濃度值(si):

(5)

(6)

⑤ 將si代入到目標(biāo)函數(shù)中，求出該位置上食物的氣味濃度值(smelli):

smelli=function(si)

(7)

⑥ 在果蠅群中找出氣味濃度值最大的果蠅個(gè)體:

[bestsmell bestindex]=max(smelli)

(8)

⑦ 保留最大氣味濃度值，所有果蠅向該位置聚集，并將該位置更新為果蠅群的新位置:

Bestsmell=bestsmell

(9)

xis=x[bestindex]

(10)

yis=y[bestindex]

(11)

⑧ 判斷算法是否達(dá)到結(jié)束標(biāo)志，若是則結(jié)束，否則重復(fù)執(zhí)行步驟③-步驟⑥，判斷當(dāng)前果蠅群中最優(yōu)的氣味濃度值是否優(yōu)于歷史最優(yōu)氣味濃度值，若是則執(zhí)行步驟⑦。

1.2 改進(jìn)的果蠅算法

由1.1節(jié)基本果蠅算法的流程可以看出，該算法在果蠅個(gè)體的更新方式及計(jì)算上存在不足，具體如下：

1) 式(3)、式(4)在連續(xù)域上采用隨機(jī)數(shù)方式更新果蠅個(gè)體位置，使得果蠅尋優(yōu)的效率較為低下；

2) 在連續(xù)域上取值不能適用于離散域，適用范圍較窄；

3) 式(5)、式(6)是計(jì)算當(dāng)前位置與原點(diǎn)間的距離，不能適用于最優(yōu)點(diǎn)不是原點(diǎn)的情況。

為此，我們要用其解決混合整數(shù)非線性規(guī)劃問題，必須對(duì)其進(jìn)行改造。針對(duì)基本果蠅算法的不足，改進(jìn)主要有以下三個(gè)方面：

1) 對(duì)不同類型變量采取不同的更新方式，如式(14)、式(15)，解決了變量類型與更新方式不匹配的問題。

2) 采取步長函數(shù)指導(dǎo)果蠅位置的更新，如式(16)、式(17) ，使果蠅在尋找最優(yōu)解的過程不再具有隨機(jī)性，可以加快收斂，參數(shù)α為連續(xù)型變量的指導(dǎo)參數(shù)，取值范圍為0.5～0.95，β為離散型變量的參數(shù)，取值范圍為0.2～0.5。并且該函數(shù)具有周期性，可以提高果蠅跳出局部最優(yōu)解的能力，更好地找出全局最優(yōu)解，參數(shù)T為其周期，取值范圍為20～40，T值越小，函數(shù)震蕩越強(qiáng)，T值越大，函數(shù)精度越高。p為當(dāng)前的迭代次數(shù)。

3) 去除式(5)和式(6)，將變量直接帶入所求函數(shù)中，如式(18)，簡化了計(jì)算。

下面是改進(jìn)的果蠅算法的詳細(xì)步驟：

① 初始化參數(shù)，果蠅種群數(shù)量(mSize)，迭代次數(shù)(pSize)，步長函數(shù)的參數(shù)α、β、p、T，果蠅在變量j的飛行范圍(domj∈[domL,j,domu,j])。

② 隨機(jī)生成果蠅群的初始位置，其中，xaxi,j為連續(xù)型變量，yaxi,j為離散型變量:

xaxi,j=rand(domj)

(12)

yaxi,j=?rand(domj)」

(13)

③ 果蠅個(gè)體中各種變量的更新規(guī)則，即其使用嗅覺及視覺發(fā)現(xiàn)食物，如xi,j代表第i只果蠅中的第j個(gè)變量,randomvalue∈[-1,1]:

xi,j=xaxi,j+αj×randomvalue

(14)

yi,j=?yaxi,j+βj×randomvalue」

(15)

αj=|domU,j-domL,j|×αp%T

(16)

βj=|domU,j-domL,j|×βp%T

(17)

④ 將xi,j、yi,j代入目標(biāo)函數(shù)中，求出該果蠅此時(shí)位置上的氣味濃度(smelli):

smelli=Function(xi,j,yi,j)

(18)

⑤ 找出果蠅群中氣味濃度最優(yōu)的果蠅個(gè)體:

[bestsmell bestindex]=max(smelli)

(19)

⑥ 保留最優(yōu)氣味濃度值及該果蠅的位置，所有果蠅都飛向該位置:

bestSmell=bsetsmell

(20)

xaxi,j=x[bestindex]

(21)

yaxi,j=y[bestindex]

(22)

⑦ 判斷算法是否到達(dá)結(jié)束標(biāo)志，若是則結(jié)束算法，否則重復(fù)步驟③-步驟⑤，并判斷當(dāng)前果蠅群中最優(yōu)氣味濃度是否優(yōu)于歷史值，若是則還回步驟⑥。

對(duì)比基本算法與改進(jìn)的算法可知，本文從基本算法的不足與所研究問題的特點(diǎn)出發(fā)，有針對(duì)性地提出了周期性震蕩函數(shù)指導(dǎo)果蠅飛行，以及分離不同類型變量的更新方式，從而能有效地解決所研究的問題。

2 數(shù)值實(shí)驗(yàn)與分析

本文選取四個(gè)混合整數(shù)非線性規(guī)劃問題進(jìn)行仿真[13-14]，該類函數(shù)是由實(shí)際的工程問題抽象而成。并且選取的函數(shù)具有很強(qiáng)的檢驗(yàn)性，第一個(gè)測(cè)試用例連續(xù)性的變量多于離散性的變量，而第二個(gè)測(cè)試用例則相反，這樣可以綜合的檢驗(yàn)出改進(jìn)算法的性能。并將改進(jìn)算法與粒子群算法[15](PSO)及差分進(jìn)化算法[16](DE)進(jìn)行了比較。PSO算法中慣性約束系數(shù)W=0.5，加速系數(shù)c1=2、c2=2；DE算法中變異算子F=0.5，交叉算子CR=0.15。PSO及DE的種群數(shù)與迭代數(shù)均和果蠅算法一致。果蠅群數(shù)量mSize=100，迭代次數(shù)pSize=1 000，步長參數(shù)α=0.65、β=0.35、T=20，p為當(dāng)前的迭代次數(shù)。該實(shí)驗(yàn)的計(jì)算機(jī)配置與環(huán)境為：英特爾CPU、3.5GHz，8GB內(nèi)存，Win7 64位操作系統(tǒng)。本文主要從算法的穩(wěn)定性、收斂速度及最優(yōu)解的精度等方面與粒子群算法(PSO)及差分進(jìn)化算法(DE)進(jìn)行了綜合的比較。本文算法在下文圖中用OURS表示。

2.1 混合整數(shù)非線性規(guī)劃問題

混合整數(shù)非線性規(guī)劃其一般形式為：

minf(x,y)

(23)

其中，m、n分別表示不等式約束或等式約束的個(gè)數(shù)，x表示ne維連續(xù)變量，y表示nc維整數(shù)或離散變量。

(1) 測(cè)試用例1：

minf1(x,y)=-y+2x-In(x/2)

(24)

最優(yōu)解為(x.y)=(1.375,1)，最優(yōu)值為2.214。

(2) 測(cè)試用例2：

min f2(x,y)=-0.7y+5(x1-0.5)2+0.8

(25)

最優(yōu)解為(x1,x2,y)=(0.941 94,-2,1)，最優(yōu)值為1.076 54。

(3) 測(cè)試用例3：

minf4(x,y)= 0.622 4(0.062 5y1)x1x2+

3.166 1(0.062 5y1)2x2+

19.84(0.062 5y1)2x1

(26)

已知最優(yōu)解為(x1,x2,y1,y2)=(38.860 1,221.365,12,6)，最優(yōu)值為5 850.38。

(4) 測(cè)試用例4：

minf3(x,y)= (y1-1)2+(y2-1)2+

(y3-1)2-In(1+y4)+

(x1-1)2+(x2-2)2+(x3-3)2

(27)

已知最優(yōu)解為：(x1,x2,x3,y1,y2,y3,y4)=(0.2,1.280 624,1.954 483,1,0,0,1)，最優(yōu)值為3.557 463。

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

本文從以下幾個(gè)方面來對(duì)比各種算法在解決上述兩個(gè)測(cè)試用例時(shí)的性能。圖1-圖4表示三種算法在迭代次數(shù)為1 000時(shí)算法的尋優(yōu)情況。其橫坐標(biāo)表示為1 000次迭代數(shù)據(jù)每20次取樣所形成的50個(gè)樣本數(shù)，縱坐標(biāo)為每個(gè)取樣樣本上的函數(shù)最優(yōu)值。

圖1 三種算法解決測(cè)試用例1的性能對(duì)比圖

圖2 三種算法解決測(cè)試用例2的性能對(duì)比圖

圖3 三種算法解決測(cè)試用例3的性能對(duì)比圖

圖4 三種算法解決測(cè)試用例4的性能對(duì)比圖

從圖1和圖2中可以看出，由于函數(shù)f1及函數(shù)f2的變量較少，離散性變量不多于連續(xù)性變量，并且變量的域間較小，所以從圖1和圖2上可以看出三種算法在對(duì)此類型的問題求解的效率較高、效果也較好。但是，本文算法(圖中的OURS)從收斂速度來看，性能明顯比其他兩種要好。其原因一是函數(shù)的特點(diǎn)造成的，二是改進(jìn)的果蠅算法中加入了步長函數(shù)可以指導(dǎo)果蠅的飛行，加快果蠅尋找到最優(yōu)值。圖3中函數(shù)f3的變量類型的個(gè)數(shù)相同，但是，變量的域間距較大。從圖3中可以看出本文算法優(yōu)于DE及PSO算法。圖4中函數(shù)f4的離散性變量多于連續(xù)性變量，從圖中可以看出三種算法都在某一段時(shí)間內(nèi)陷入了局部最優(yōu)，但改進(jìn)的果蠅算法最后能找到最優(yōu)值，而其他算法在面對(duì)多離散性變量問題時(shí)效果就不是那么好了。

圖5-圖8表示了三種算法迭代次數(shù)分別為100、500和1 000次，獨(dú)立運(yùn)行50次時(shí)，得到的50個(gè)最優(yōu)值中達(dá)到所規(guī)定的誤差精度的成功次數(shù)占總次數(shù)的比例。其中達(dá)到函數(shù)f1、f2的規(guī)定最優(yōu)值的誤差精度為1%，而函數(shù)f2、f4的誤差精度為5%。

圖5 三種算法解決測(cè)試用例1的性能對(duì)比圖

圖6 三種算法解決測(cè)試用例2的性能對(duì)比圖

圖7 三種算法解決測(cè)試用例3的性能對(duì)比圖

圖8 三種算法解決測(cè)試用例4的性能對(duì)比圖

從圖5-圖8的直方圖可以得出這三種算法在解決不同復(fù)雜度的函數(shù)時(shí)，它們的效率及成功率也不相同，對(duì)于較復(fù)雜的離散變量，改進(jìn)的果蠅算法有較高的成功率，表明算法的穩(wěn)定性較強(qiáng)。

表1表示了該三種算法它們獨(dú)自運(yùn)行50次，每次迭代1 000次時(shí)的實(shí)驗(yàn)結(jié)果，從表中可以看出，本算法比其他兩種算法穩(wěn)定性較好，且精度要高。

表1 三種算法最優(yōu)值與最差值對(duì)比表

3 結(jié) 語

本文提出了一種求解混合整數(shù)非線性規(guī)劃問題的改進(jìn)果蠅算法，該算法通過分離不同類型的變量，且對(duì)變量的更新方式設(shè)置不同的步長約束函數(shù)，使得該改進(jìn)的算法能有效地提高穩(wěn)定性、避免陷入局部最優(yōu)。實(shí)驗(yàn)結(jié)果表明，改進(jìn)的果蠅算法比其他算法在求解此類非線性規(guī)劃問題上的收斂速度快、精度高。然而，該改進(jìn)的果蠅算法的適應(yīng)性較低，雖對(duì)所求解問題的效果較好，但對(duì)其他規(guī)劃問題的求解還有待深入的研究。

[1]ZhangXS.Introductiontomathematicalprogramming[J].Introductiontomathematicalprogramming,2000,46(4071):273-298.

[2] 張莉,馮大政,李宏.求解整數(shù)非線性規(guī)劃結(jié)合正交雜交的離散PSO算法[J].控制與決策,2012,27(9):1387-1387.

[3] 劉明明,崔春風(fēng),童小嬌,等.混合整數(shù)非線性規(guī)劃的算法軟件及最新進(jìn)展[J].中國科學(xué):數(shù)學(xué),2016(1):001.

[4] 劉振澤,許洋,王峰明.改進(jìn)差分進(jìn)化算法在非線性模型預(yù)測(cè)控制中的應(yīng)用[J].北京工業(yè)大學(xué)學(xué)報(bào),2015,41(5):680-685.

[5]GuoX,LiX.AGeneticAlgorithmforaClassofFractionalBilevelProgrammingProblemswithIntervalCoefficients[J].AdvancesinAppliedMathematics,2015,4(1):63-69.

[6] 吳小文,李擎.果蠅算法和5種群智能算法的尋優(yōu)性能研究[J].火力與指揮控制,2013,38(4):17-20.

[7] 潘文超.應(yīng)用果蠅優(yōu)化算法優(yōu)化廣義回歸神經(jīng)網(wǎng)絡(luò)進(jìn)行企業(yè)經(jīng)營績效評(píng)估[J].太原理工大學(xué)學(xué)報(bào)(社會(huì)科學(xué)版),2011,29(4):1-5.

[8]YuanX,DaiX,ZhaoJ,etal.Onanovelmulti-swarmfruitflyoptimizationalgorithmanditsapplication[J].AppliedMathematics&Computation,2014,233(3):260-271.

[9]PanWT.AnewFruitFlyOptimizationAlgorithm:Takingthefinancialdistressmodelasanexample[J].Knowledge-BasedSystems,2012,26(2):69-74.

[10] 鄭曉龍,王凌,王圣堯.求解置換流水線調(diào)度問題的混合離散果蠅算法[J].控制理論與應(yīng)用,2014,31(2):159-164.

[11] 楊書,舒勤,何川.改進(jìn)的果蠅算法及其在PPI網(wǎng)絡(luò)中的應(yīng)用[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(12):291-294.

[12]ShanD,CaoGH,DongHJ.LGMS-FOA:AnImprovedFruitFlyOptimizationAlgorithmforSolvingOptimizationProblems[J].MathematicalProblemsinEngineering,2013,2013(7):1256-1271.

[13]LinYC,HwangKS,WangFS.Amixed-codingschemeofevolutionaryalgorithmstosolvemixed-integernonlinearprogrammingproblems[J].Computers&MathematicswithApplications,2004,47(8-9):1295-1307.

[14]DeepK,SinghKP,KansalML,etal.Arealcodedgeneticalgorithmforsolvingintegerandmixedintegeroptimizationproblems[J].AppliedMathematics&Computation,2009,212(2):505-518.

[15] 唐俊.PSO算法原理及應(yīng)用[J].計(jì)算機(jī)技術(shù)與發(fā)展,2010,20(2):213-216.

[16] 梅覓,薛惠鋒,谷雨.旅行商問題的改進(jìn)差分進(jìn)化方法[J].信息技術(shù),2011(2):20-23.

SOLVING MIXED INTEGER NONLINEAR PROGRAMMING BASED ON THE IMPROVED FRUIT FLIES ALGORITHM

Zhu Zhitong1Zhao Yang2Li Wei1,2Guo Xing1,2

1(KeyLaboratoryofICSP,MinistryofEducation,AnhuiUniversity,Hefei230039,Anhui,China)2(SchoolofComputerScienceandTechnology,AnhuiUniversity,Hefei230601,Anhui,China)

There are many MINLP problems in the design of science and engineering systems, which are rich in variables and have many constraints and are difficult to solve. Therefore, this paper proposes an improved fruit flies algorithm. The algorithm uses different strategies to update different types of variables, and uses the periodic step function to guide the optimization of FOA so as to avoid falling into local optimization. Compared with the other two commonly used algorithms in terms of stability, convergence speed and so on, experimental results show that the improved fruit flies algorithm can effectively solve the MINLP problems.

Mixed integer nonlinear programming Smart computing Fruit flies algorithm

2016-06-24。國家科技支撐計(jì)劃項(xiàng)目(2015BAK24B00)。朱志同，碩士生，主研領(lǐng)域：智能計(jì)算，信號(hào)處理。趙陽，本科生。李煒，教授。郭星，博士。

TP301.6

A

10.3969/j.issn.1000-386x.2017.06.047