基于改進果蠅算法求解混合整數非線性規劃問題

朱志同 趙 陽 李 煒, 郭 星,

1(安徽大學計算智能與信號處理重點實驗室 安徽 合肥 230039)2(安徽大學計算機科學與技術學院 安徽 合肥 230601)

基于改進果蠅算法求解混合整數非線性規劃問題

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

1(安徽大學計算智能與信號處理重點實驗室 安徽 合肥 230039)2(安徽大學計算機科學與技術學院 安徽 合肥 230601)

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

混合整數非線性規劃 智能計算 果蠅算法

0 引 言

在科學及工程系統設計中存在許多問題都是非線性規劃問題，其中混合整數非線性規劃MINLP又是非線性規劃的一個重要分支[1]。混合整數非線性規劃是同時包含離散性變量和連續性變量的優化問題，許多組合優化問題如：TSP問題、0-1背包問題等都可視為MNLP問題。對于MNLP問題，其目標函數和約束條件的非線性，使得結果往往存在局部最優解[2]。

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

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

1 果蠅算法

1.1 基本果蠅算法

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

其具體過程如下：

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

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

xis=rand(dom)

(1)

yis=rand(dom)

(2)

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

xi=xis+RandomValue

(3)

yi=yis+RandomValue

(4)

④ 計算每只果蠅當前位置與原點的距離(disti)及食物的氣味濃度值(si):

(5)

(6)

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

smelli=function(si)

(7)

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

[bestsmell bestindex]=max(smelli)

(8)

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

Bestsmell=bestsmell

(9)

xis=x[bestindex]

(10)

yis=y[bestindex]

(11)

⑧ 判斷算法是否達到結束標志，若是則結束，否則重復執行步驟③-步驟⑥，判斷當前果蠅群中最優的氣味濃度值是否優于歷史最優氣味濃度值，若是則執行步驟⑦。

1.2 改進的果蠅算法

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

1) 式(3)、式(4)在連續域上采用隨機數方式更新果蠅個體位置，使得果蠅尋優的效率較為低下；

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

3) 式(5)、式(6)是計算當前位置與原點間的距離，不能適用于最優點不是原點的情況。

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

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

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

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

下面是改進的果蠅算法的詳細步驟：

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

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

xaxi,j=rand(domj)

(12)

yaxi,j=?rand(domj)」

(13)

③ 果蠅個體中各種變量的更新規則，即其使用嗅覺及視覺發現食物，如xi,j代表第i只果蠅中的第j個變量,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代入目標函數中，求出該果蠅此時位置上的氣味濃度(smelli):

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

(18)

⑤ 找出果蠅群中氣味濃度最優的果蠅個體:

[bestsmell bestindex]=max(smelli)

(19)

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

bestSmell=bsetsmell

(20)

xaxi,j=x[bestindex]

(21)

yaxi,j=y[bestindex]

(22)

⑦ 判斷算法是否到達結束標志，若是則結束算法，否則重復步驟③-步驟⑤，并判斷當前果蠅群中最優氣味濃度是否優于歷史值，若是則還回步驟⑥。

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

2 數值實驗與分析

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

2.1 混合整數非線性規劃問題

混合整數非線性規劃其一般形式為：

minf(x,y)

(23)

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

(1) 測試用例1：

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

(24)

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

(2) 測試用例2：

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

(25)

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

(3) 測試用例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)

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

(4) 測試用例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)

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

2.2 實驗結果與分析

本文從以下幾個方面來對比各種算法在解決上述兩個測試用例時的性能。圖1-圖4表示三種算法在迭代次數為1 000時算法的尋優情況。其橫坐標表示為1 000次迭代數據每20次取樣所形成的50個樣本數，縱坐標為每個取樣樣本上的函數最優值。

圖1 三種算法解決測試用例1的性能對比圖

圖2 三種算法解決測試用例2的性能對比圖

圖3 三種算法解決測試用例3的性能對比圖

圖4 三種算法解決測試用例4的性能對比圖

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

圖5-圖8表示了三種算法迭代次數分別為100、500和1 000次，獨立運行50次時，得到的50個最優值中達到所規定的誤差精度的成功次數占總次數的比例。其中達到函數f1、f2的規定最優值的誤差精度為1%，而函數f2、f4的誤差精度為5%。

圖5 三種算法解決測試用例1的性能對比圖

圖6 三種算法解決測試用例2的性能對比圖

圖7 三種算法解決測試用例3的性能對比圖

圖8 三種算法解決測試用例4的性能對比圖

從圖5-圖8的直方圖可以得出這三種算法在解決不同復雜度的函數時，它們的效率及成功率也不相同，對于較復雜的離散變量，改進的果蠅算法有較高的成功率，表明算法的穩定性較強。

表1表示了該三種算法它們獨自運行50次，每次迭代1 000次時的實驗結果，從表中可以看出，本算法比其他兩種算法穩定性較好，且精度要高。

表1 三種算法最優值與最差值對比表

3 結 語

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

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

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

[3] 劉明明,崔春風,童小嬌,等.混合整數非線性規劃的算法軟件及最新進展[J].中國科學:數學,2016(1):001.

[4] 劉振澤,許洋,王峰明.改進差分進化算法在非線性模型預測控制中的應用[J].北京工業大學學報,2015,41(5):680-685.

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

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

[7] 潘文超.應用果蠅優化算法優化廣義回歸神經網絡進行企業經營績效評估[J].太原理工大學學報(社會科學版),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] 鄭曉龍,王凌,王圣堯.求解置換流水線調度問題的混合離散果蠅算法[J].控制理論與應用,2014,31(2):159-164.

[11] 楊書,舒勤,何川.改進的果蠅算法及其在PPI網絡中的應用[J].計算機應用與軟件,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算法原理及應用[J].計算機技術與發展,2010,20(2):213-216.

[16] 梅覓,薛惠鋒,谷雨.旅行商問題的改進差分進化方法[J].信息技術,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。國家科技支撐計劃項目(2015BAK24B00)。朱志同，碩士生，主研領域：智能計算，信號處理。趙陽，本科生。李煒，教授。郭星，博士。

TP301.6

A

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