求解約束優(yōu)化新的引力搜索算法

吳施豫+錢偉懿

摘要： 針對約束優(yōu)化問題，提出了一種新的引力搜索算法。在該算法中，對每一個粒子定義兩個質(zhì)量，一是“可行質(zhì)量”另一個是“不可行質(zhì)量”。若對可行粒子更新，則采用可行質(zhì)量；否則采用不可行質(zhì)量。其目的使可行粒子向目標(biāo)函數(shù)值好的方向發(fā)展，使不可行粒子向可行域方向發(fā)展。最后對5個測試函數(shù)進行數(shù)值實驗，數(shù)值結(jié)果表明提出的算法是可行的、有效的。

Abstract： A new gravitational search algorithm is proposed for constrained optimization problem. In this algorithm， two mass are defined for each particle， "feasible mass" and "infeasible mass". If feasible particles are updated， feasible mass is used； otherwise， infeasible mass is used. Its purpose is to make feasible particles develop to the direction of good objective function value， and the infeasible particles develop to the direction of feasible domain. Finally， the numerical experiments of five test functions are carried out. The numerical results show that the proposed algorithm is feasible and effective.

關(guān)鍵詞： 引力搜索算法；約束優(yōu)化；違反約束度；全局優(yōu)化

Key words： gravitational search algorithm；constraint optimization；violation of constraint；global optimization

中圖分類號：TP301.6 文獻標(biāo)識碼：A 文章編號：1006-4311（2017）12-0205-02

1 概述

本文考慮如下約束優(yōu)化問題：

min f（x）

s.t. gi（x）？燮0，i=1，2，3…q

hj（x）=0，j=q+1，q+2，…m（1）

lk？燮xk？燮uk，k=1，2，…，n

其中x=（x1，x2，…xn）∈Rn為決策向量，整體搜索空間 ？贅={x∈Rn|lk？燮xk？燮uk，k=1，2，…，n}，可行域為S={x∈？贅|gi（x）？燮0，hj（x）=0，i=1，2，…q，j=q+1，…，m}，f（x）：S？奐Rn→R是一實值目標(biāo)函數(shù)。問題（1）經(jīng)常出現(xiàn)在科學(xué)和工程等領(lǐng)域，因此它在優(yōu)化問題中起到重要作用。 解決約束優(yōu)化問題的常用有確定性和隨機性兩種方法。 由于一些問題中存在目標(biāo)函數(shù)或約束函數(shù)不可微等問題，從而導(dǎo)致確定性方法具有一定局限性，因此，近年來一些隨機性優(yōu)化方法被廣泛應(yīng)用到求解約束優(yōu)化問題。最近，Rashedi 等人提出一種新的啟發(fā)式優(yōu)化算法，稱為引力搜索算法[1]（Gravitational Search Algorithm，簡稱GSA），自從GSA被提出后，一些學(xué)者利用GSA來求解約束優(yōu)化問題。Pal 等人利用GSA算法使用修復(fù)方法解決約束優(yōu)化問題[2]。 Mondal等人使用GSA通過重新初始化不可行的粒子來解決約束優(yōu)化問題[3]。Yadav 和Deep給出求解約束優(yōu)化問題的引力搜索算法[4]。劉勇和馬良對灰色非線性約束優(yōu)化問題給出了GSA方法[5]。 Poole等人[6]提出了一種有效的約束處理方法，通過可行群和不可行群分別優(yōu)化目標(biāo)函數(shù)和約束違反程度，但是該方法當(dāng)不可行的粒子更新時，可行解的目標(biāo)函數(shù)的信息尚未被充分考慮?；谀繕?biāo)函數(shù)和約束違反度，本文對每個粒子定義兩個質(zhì)量，一個是“可行質(zhì)量”，另一個是“不可行質(zhì)量”。當(dāng)可行粒子更新時，在GSA中使用“可行質(zhì)量”，當(dāng)不可行粒子更新時使用“不可行質(zhì)量”。其目的當(dāng)粒子可行時使其向好的適應(yīng)值方向進化，當(dāng)粒子不可行時向可行域方向進化。數(shù)值結(jié)果表明所提出的算法是有效的。

2 改進的引力搜索算法

GSA是一個用于求解全局優(yōu)化問題的群體啟發(fā)式方法。在GSA中，搜索區(qū)域中的每個解被視為具有一定質(zhì)量的粒子。根據(jù)目標(biāo)函數(shù)值定義其質(zhì)量，基于牛頓引力定律定義粒子間的引力，在引力作用下，粒子在搜索空間內(nèi)向質(zhì)量大的粒子移動，即向具有較好目標(biāo)函數(shù)值的粒子移動。由于GSA最初用于解決盒子約束優(yōu)化問題，所以定義的質(zhì)量只與目標(biāo)函數(shù)有關(guān)，對于解決一般約束優(yōu)化問題，對質(zhì)量定義必須進行新的研究。因此本文對每個粒子定義兩個質(zhì)量，從而提出新的引力搜索算法。

假設(shè)粒子群體由N個粒子組成，第i（i=1，2，…，N）個粒子在t時刻的位置和速度分別為x■■=（x■■，x■■，…x■■）和v■■=（v■■，v■■，…v■■）其中x■■和v■■分別表示第i個粒子在第d維空間上的位置和速度。

設(shè)粒子x違反第j個約束的程度為

Hj（x）=max{gj（x），0}， j=1，2，…，qmax{hj（x）-■，0} j=q+1，…，m（2）

其中？著 >0為等式約束允許的估值，則粒子x違反約束程度定義如下：H（x）=■Hj（x）（3）

假設(shè)粒子i在t時刻是“可行”，即x■■∈S，則定義他的可行質(zhì)量為mi（t）=■（4）

FMi（t）=■（5）

不可行質(zhì)量為■■（t）=1+■（6）

IMi（t）=■（7）

其中fitnessbest（t）表示在t時刻粒子在S中最好的適應(yīng)值；fitnessworst（t）表示t時刻粒子粒子在中S最差的適應(yīng)值。

假設(shè)粒子i在t時刻是“不可行”，即x■■？埸S，則定義他的可行質(zhì)量為FMi（t）=0（8）

不可行質(zhì)量為■■（t）=■（9）

IMi（t）=■（10）

其中，Hbest（t）=■{H（x■■）}，Hworst（t）=■{H

（x■■）}。

粒子i對粒子j的引力定義如下：

F■■（t）=G（t）■（x■■-x■■）（11）

其中d=1，2，…n，G（t）=G0e■，G0表示萬有引力的初始值，？琢為常數(shù)，Mi（t）表示粒子i的質(zhì)量，T表示最大迭代次數(shù)，t表示當(dāng)前迭代次數(shù)，？著是一個很小的常量，Rij=■ Xi，Xj ■ 表示第i個粒子和第j個粒子之間的歐氏距離。

作用在粒子粒子i上的引力為

F■■（t）=■randj×F■■（t）（12）

其中Kbest按較好適應(yīng)值從N線性遞減到1，rand是[0，1]之間的隨機數(shù)。

根據(jù)運動法則，粒子i在第d維空間上的加速度為

a■■=■（13）

粒子i的速度和位置更新公式如下：

v■■=randi×v■■+a■■（14）

x■■=x■■+v■■（15）

由（5）、（8）和（11）式可以看出，對“可行”粒子操作時，“不可行”粒子對其沒有影響，而質(zhì)量越大的可行粒子對其影響越大，從而使其向適應(yīng)值較好方向進化.由（7），（10），和（11）式可以看出，對“不可行”粒子操作時，“可行”粒子對其影響最大，而違反約束程度越小的不可行粒子對其影響也大，從而使其向可行域方向進化。改進GSA步驟如下：

步驟1：設(shè)置各參數(shù)，在？贅內(nèi)隨機初始化粒子的位置和速度，計算粒子的適應(yīng)值或違反約束程度，保存當(dāng)前最優(yōu)可行解Pg，若沒有可行粒子，令Pg為無窮大。令t=0；

步驟2： 判斷粒子i（i=1，2，…，N）是否在S內(nèi)，若在S內(nèi)，計算各粒子的可行質(zhì)量，用可行質(zhì)量代替粒子質(zhì)量，否則計算各粒子的不可行質(zhì)量，用不可行質(zhì)量代替粒子質(zhì)量；

步驟3：按（12）計算粒子i的引力；

步驟4：按（13）式計算計算粒子i的加速度；

步驟5：按（14）和（15）式更新粒子i的速度和位置；

步驟6：計算各粒子的適應(yīng)值和違反約束程度，更新當(dāng)前最好的可行解Pg；

步驟7： 判斷是否滿足最大迭代步，若滿足，則輸出Pg；否則令t=t+1，轉(zhuǎn)步驟2。

3 數(shù)值實驗

為了評價改進算法（簡稱，IGSA）的性能，我們選取文獻[7]中的5個測試函數(shù)進行實驗研究并與其他算法進行比較。

從表1可以看出，對于測試函數(shù)G1和G4，IGSA算法與3S-MGSA算法都能夠找到問題的最優(yōu)解，而GSA算法不能夠找到最優(yōu)解。對于測試函數(shù)G2和G3，IGSA算法優(yōu)于其他兩種算法。對于測試函數(shù)G5，IGSA算法不如3S-MGSA算法，但優(yōu)于GSA算法。總體來說，IGSA算法有較好的尋優(yōu)能力，在解決約束優(yōu)化問題方面具有更好的性能。

4 結(jié)束語

本文所提出的方法不需要使用懲罰函數(shù)，并且也不同于文獻[2]的方法。我們在GSA中定義了粒子的可行的質(zhì)量和不可行的質(zhì)量，可行的質(zhì)量可以引導(dǎo)可行粒子向全局最優(yōu)解方向搜索，不可行的質(zhì)量可以引導(dǎo)不可行粒子向可行區(qū)域方向搜索，從而提高了算法解決約束優(yōu)化問題的性能。在未來研究中，我們將研究更好處理約束的方法，并應(yīng)用到一些啟發(fā)式算法中。

參考文獻：

[1]Rashedi， E. Nezamabadi-pour， H.， Saryazdi， S. GSA： A gravitational search algorithm [J]. Information Sciences， 2009， 179（13）： 2232-2248.

[2]Pal，K. Saha，C. Das，S. et al. Dynamic constrained optimization with offspring repair based gravitation search algorithm [C]// Proc. CEC14， Cancun， Mexico： 2013： 2414-2421.

[3]Mondal S. Bhattacharya A. Halder S. Solution of cost constrained emission dispatch problems considering wind power generation using gravitational search algorithm [C]// Proc. ICAESM， Nagapattinam India： IEEE Press， 2012：169-174.

[4]Yadav A. Deep K. Constrained optimization using gravitational search algorithm [J]. National Academy Science Letters， 2013， 36（5）：527-534.

[5]劉勇，馬良.灰色非線性約束規(guī)劃的改進引力搜索算法求解[J].數(shù)學(xué)的實踐與認(rèn)識，2013，43（7）：99-103.

[6]Poole， D. J. Allen C. B. Rendall T. C. S. Analysis of constraint handling methods for the gravitational search algorithm [C]// Proc. CEC14， Beijing， China： IEEE Press， 2014： 2005-2012.

[7]Efren M. M. Coello C. A. C. A simple multimembered evolution strategy to solve constrained optimization problems [J]. IEEE Transactions on Evolutionary Computation， 2005， 9（1）： 1-17.