求解約束優(yōu)化問題的螢火蟲算法及其工程應(yīng)用

龍文，蔡紹洪，焦建軍，陳義雄，黃亞飛

?

求解約束優(yōu)化問題的螢火蟲算法及其工程應(yīng)用

龍文1，蔡紹洪1，焦建軍1，陳義雄2，黃亞飛2

(1. 貴州財(cái)經(jīng)大學(xué)貴州省經(jīng)濟(jì)系統(tǒng)仿真重點(diǎn)實(shí)驗(yàn)室，貴州貴陽，550004；2. 中南大學(xué)信息科學(xué)與工程學(xué)院，湖南長沙，410083)

針對基本螢火蟲算法存在收斂速度慢、易陷入局部最優(yōu)等缺點(diǎn)，提出一種改進(jìn)的螢火蟲算法用于求解約束優(yōu)化問題。該算法首先利用混沌序列初始化螢火蟲的位置，引入動態(tài)隨機(jī)局部搜索以加快算法的收斂速度；為了避免算法陷入局部最優(yōu)，對當(dāng)前全局最優(yōu)解進(jìn)行多樣性變異操作。對幾個數(shù)值優(yōu)化和工程優(yōu)化問題進(jìn)行實(shí)驗(yàn)。研究結(jié)果表明：與其他啟發(fā)計(jì)算法相比，該算法具有較強(qiáng)的尋優(yōu)性能。

螢火蟲算法；約束優(yōu)化問題；動態(tài)隨機(jī)局部搜索；工程優(yōu)化

在工程實(shí)際應(yīng)用中，許多問題可轉(zhuǎn)化為求解含有約束條件的函數(shù)優(yōu)化問題。不失一般性，1個含有不等式約束、等式約束和變量界約束的約束優(yōu)化問題(最小化)可描述為

1 基本螢火蟲算法

FA是模擬自然界中螢火蟲的發(fā)光行為而衍生出的啟發(fā)式全局優(yōu)化方法，它利用螢火蟲發(fā)光特性在搜索空間中尋找伙伴，并向位置較優(yōu)的螢火蟲移動，從而達(dá)到了進(jìn)化的目的。

在描述具體的FA之前，需進(jìn)行如下假設(shè)。

1) 螢火蟲不分雌雄，發(fā)光較強(qiáng)的螢火蟲可以吸引其他發(fā)光較弱的螢火蟲。

2) 每個螢火蟲的吸引度與其發(fā)光強(qiáng)度成正比。對于任意2只螢火蟲，發(fā)光較弱的螢火蟲會朝發(fā)光較強(qiáng)的螢火蟲移動，且與隨著2只螢火蟲之間的距離的變大而變小。最亮的螢火蟲(即最大的螢火蟲)是隨機(jī)飛行的。

3) 螢火蟲的與目標(biāo)函數(shù)值有關(guān)。

在滿足上述3個假設(shè)的情況下，基本螢火蟲算法的步驟如下。

Step 1 設(shè)置算法參數(shù)：種群規(guī)模，最大吸引度0，吸收系數(shù)，隨機(jī)步長，最大迭代次數(shù)。在解空間中隨機(jī)初始化螢火蟲的位置，令=1。

Step 2 平均每只螢火蟲的發(fā)光強(qiáng)度I(=1，2，…，)，將發(fā)光強(qiáng)度I作為適應(yīng)度(x)(x表示問題的1個解)，即I=(x)，1≤≤。

其中：為決策變量的維數(shù)。

螢火蟲的吸引度為

Step 4 移動更新螢火蟲的位置。螢火蟲被發(fā)光強(qiáng)度更亮的螢火蟲吸引而發(fā)生位置移動。

Step 5 發(fā)光強(qiáng)度最亮的螢火蟲隨機(jī)飛行：

Step 6 判斷算法是否滿足終止條件，若滿足，則算法結(jié)束，輸出最優(yōu)解；否則，令=+1，返回 Step 2。

2 改進(jìn)螢火蟲算法

2.1 種群初始化

目前，F(xiàn)A幾乎全部采用隨機(jī)方式對螢火蟲的位置進(jìn)行初始化，這有可能導(dǎo)致螢火蟲分布位置的不均勻。另外，在求解優(yōu)化問題前，由于對全局最優(yōu)解沒有任何先驗(yàn)知識，若隨機(jī)初始化種群個體，則不利于搜索到全局最優(yōu)解，可能導(dǎo)致增加迭代次數(shù)或種群規(guī)模，這勢必會增加算法的計(jì)算量。因此，初始種群的優(yōu)劣對FA的收斂性及搜索效率會產(chǎn)生較大的影響。

混沌是一種非線性現(xiàn)象，具有隨機(jī)性、遍歷性、有界性和規(guī)律性等特點(diǎn)，對初始值是極度敏感的，可在一定范圍內(nèi)按自身規(guī)律不重復(fù)地遍歷所有狀態(tài)，可將其應(yīng)用到優(yōu)化算法中來提高其全局搜索能力。因此，本文采用混沌序列初始化螢火蟲的位置，以維持種群的多樣性，為進(jìn)一步有效地進(jìn)行全局搜索建立基礎(chǔ)。本文引入常用的Logistic映射[8]進(jìn)行種群初始化，即

其中：為控制參數(shù)；x為變量；為迭代次數(shù)。當(dāng)=4時，式(6)完全處于混沌狀態(tài)，的取值不同，混沌序列的搜索范圍也不同。

2.2 動態(tài)隨機(jī)局部搜索

為了增強(qiáng)FA的局部搜索能力和加快其收斂速度，本文引入一種具有很強(qiáng)局部搜索能力的動態(tài)隨機(jī)局部搜索技術(shù)[9]，其具體步驟如下。

Step 1 設(shè)定局部搜索代數(shù)，搜索步長上限0，對于每一個搜索步長的最大迭代次數(shù)為，，epoch= 0，=0。

Step 2 重置迭代計(jì)數(shù)器，=0。

Step 4 更新epoch，即epoch=epoch+1。

Step 7 若＜，則轉(zhuǎn)Step 3；否則轉(zhuǎn)Step 8。

Step 8=+1。

Step 10 若epoch=，則算法結(jié)束；否則返回 Step 2。

其中：epoch為局部搜索迭代計(jì)數(shù)器；best為當(dāng)前最優(yōu)解；(?)為計(jì)算適應(yīng)值的函數(shù)。

2.3 多樣性變異策略

變異算子可避免算法陷入局部最優(yōu)，同時也可保持種群的多樣性。本文對當(dāng)前全局最優(yōu)解進(jìn)行多樣性變異操作，其具體實(shí)現(xiàn)如下[10]：

2.4 約束處理技術(shù)

FA是一種基于無約束的全局優(yōu)化方法，因此利用它求解約束優(yōu)化問題時一定要結(jié)合一種合適的約束處理技術(shù)。Deb[11]提出了一種不需要任何參數(shù)的聯(lián)賽選擇算子，比較和選擇個體時采用如下3個比較準(zhǔn)則：

1) 若選擇進(jìn)行比較的2個個體均為可行個體，則目標(biāo)函數(shù)值小的個體要優(yōu)。

2) 若選擇進(jìn)行比較的2個個體中，一個為可行個體，另一個為不可行個體，則可行個體要優(yōu)。

3) 若選擇進(jìn)行比較的2個個體均為不可行個體，則約束違反度小的個體要優(yōu)。約束違反度計(jì)算公式為

由于這種約束處理技術(shù)原理簡單、參數(shù)設(shè)置少，容易實(shí)現(xiàn)。因此，本文采用基于可行性規(guī)則的聯(lián)賽選擇算子來處理約束條件。

2.5 算法步驟

綜上所述，本文提出的改進(jìn)FA算法步驟如下。

Step 1 設(shè)置算法參數(shù)：種群規(guī)模，最大吸引度0，吸收系數(shù)，隨機(jī)步長，動態(tài)隨機(jī)局部搜索代數(shù)，對于每一個搜索步長的最大迭代次數(shù)，變異概率p，最大迭代次數(shù)。

Step 2 在解空間中利用混沌序列初始化螢火蟲的位置，令=1。

Step 3 計(jì)算每只螢火蟲的發(fā)光強(qiáng)度I(=1，2，…，)，將發(fā)光強(qiáng)度I作為適應(yīng)度值(x)(x表示問題的一個解)，即，找出當(dāng)前最優(yōu)位置及其對應(yīng)的最優(yōu)適應(yīng)度。

Step 4 根據(jù)2.4節(jié)中的方法比較和選擇螢火蟲進(jìn)入下一代群體。

Step 5 判斷算法是否滿足結(jié)束條件，若滿足，則算法結(jié)束，輸出全局最優(yōu)解；否則，轉(zhuǎn)Step 6。

Step 6 計(jì)算各螢火蟲的吸引度。先按式(2)確定2只螢火蟲之間的距離r，然后根據(jù)式(3)計(jì)算螢火蟲的吸引度。

Step 7 移動更新螢火蟲的位置。根據(jù)式(4)更新螢火蟲的位置。

Step 8 發(fā)光強(qiáng)度最亮的螢火蟲按式(5)進(jìn)行隨機(jī)飛行。

Step 9 對當(dāng)前最優(yōu)螢火蟲的位置(當(dāng)前全局最優(yōu)解)進(jìn)行動態(tài)隨機(jī)局部搜索。

Step 10 以一定的概率p對每一代全局最優(yōu)解進(jìn)行多樣性變異操作，令=+1，返回Step 3。

3 數(shù)值實(shí)驗(yàn)與比較分析

為了驗(yàn)證所提出的改進(jìn)螢火蟲算法(記為IFA)的有效性，本文首先從文獻(xiàn)[12]選取4個標(biāo)準(zhǔn)約束優(yōu)化問題進(jìn)行測試實(shí)驗(yàn)，然后將IFA應(yīng)用到2個工程優(yōu)化應(yīng)用問題中。

4個約束優(yōu)化測試問題的具體表達(dá)式為：

；

G2:

G4:

在4個約束優(yōu)化函數(shù)中，G1，G3和G4是最小值問題，G2是最大值問題，在一般情況下，通過將最大值問題轉(zhuǎn)化為最小值問題。

利用IFA求解上述4個約束優(yōu)化問題，其參數(shù)設(shè)置如下：種群規(guī)模=50，最大吸引度0=0.20，吸收系數(shù)=1，隨機(jī)步長=0.25，動態(tài)隨機(jī)局部搜索迭代次數(shù)=100，對于每一個搜索步長α的最大迭代次數(shù)=10，變異概率p=0.1，最大迭代次數(shù)為3 000。每個測試函數(shù)在上述參數(shù)設(shè)置下獨(dú)立運(yùn)行30次，記錄其最好結(jié)果、平均結(jié)果、最差結(jié)果和標(biāo)準(zhǔn)差，并與文獻(xiàn)[13]中的genetic algorithm (GA)，evolution strategy (ES)，particle swarm optimization (PSO)，simulating annealing (SA)，bat algorithm (BA)和firefly algorithm (FA)[14]得到的結(jié)果進(jìn)行比較，結(jié)果如表1所示。

表1 IFA和其他6種算法對4個約束優(yōu)化問題的尋優(yōu)結(jié)果比較

從表1可知：對于4個標(biāo)準(zhǔn)約束優(yōu)化測試問題，IFA求得的解精度高、且30次實(shí)驗(yàn)的標(biāo)準(zhǔn)差較小，從而說明IFA具有較強(qiáng)的全局尋優(yōu)能力和穩(wěn)定性。與GA相比，IFA對4個函數(shù)均得到了較好的結(jié)果。與ES相比，對于函數(shù)G1和G2，IFA獲得了相似的最優(yōu)結(jié)果和較好的平均結(jié)果、最差結(jié)果和標(biāo)準(zhǔn)差；對于函數(shù)G3和G4，IFA得到的結(jié)果比ES要優(yōu)。與PSO算法相比，對于函數(shù)G2，IFA獲得了相似的結(jié)果；對于函數(shù)G1，G3和G4，IFA得到了較好的結(jié)果。與SA相比，對于函數(shù)G1和G2，IFA獲得了相似的結(jié)果；對于函數(shù)G3和G4，IFA則得到了較好的結(jié)果。與BA相比，對于函數(shù)G1，G2和G4，IFA獲得了相似的結(jié)果；而對于函數(shù)G3，IFA求得的結(jié)果要優(yōu)。與FA相比，對于函數(shù)G1和G4，IFA得到的結(jié)果要優(yōu)。對于函數(shù)G2和G3，IFA得到了相似的最優(yōu)結(jié)果和較好的平均結(jié)果、最差結(jié)果和標(biāo)準(zhǔn)差。圖1~4所示為IFA對4個函數(shù)的尋優(yōu)收斂曲線。

從圖1~4可以清晰地看出：對于4個測試函數(shù)，IFA迭代較少次數(shù)時就達(dá)到全局最優(yōu)解或近似最 優(yōu)解。

圖1 IFA對函數(shù)G1的尋優(yōu)收斂曲線

圖2 IFA對函數(shù)G2的尋優(yōu)收斂曲線

圖3 IFA對函數(shù)G3的尋優(yōu)收斂曲線

圖4 IFA對函數(shù)G4的尋優(yōu)收斂曲線

4 IFA在工程優(yōu)化中的應(yīng)用

為了進(jìn)一步驗(yàn)證IFA的有效性，本文將其求解2個工程優(yōu)化問題，即焊接梁結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題和拉力/壓力彈簧結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題。

4.1 焊接梁結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題

焊接梁結(jié)構(gòu)設(shè)計(jì)優(yōu)化的目標(biāo)是在一定約束條件下使其總成本最小。焊接梁的結(jié)構(gòu)如圖5所示，它有4個設(shè)計(jì)變量，分別為(1)，(2)，(3)和(4)，約束變量為梁上的彎曲應(yīng)力、剪應(yīng)力、壓曲臨界載荷P和梁的尾端誤差。

圖5 焊接梁結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題

焊接梁結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題的目標(biāo)函數(shù)和約束條件如下。

其中：

；；；

；；；；

4個變量的取值范圍為0.1≤1≤2.0，0.1≤4≤2.0，0.1≤2≤10.0，0.1≤3≤10.0。

利用IFA對焊接梁結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題進(jìn)行求解，并與co-evolutionary differential evolution (CDE)[15]，co-evolutionary particle swarm optimi- zation (CPSO)[16]和mine blast algorithm (MBA)[17]進(jìn)行比較，結(jié)果如表2和表3所示。

表2 4種算法對焊接梁設(shè)計(jì)問題的最優(yōu)結(jié)果比較

表3 不同算法對焊接梁設(shè)計(jì)問題的尋優(yōu)統(tǒng)計(jì)結(jié)果比較

從表2和表3可知：對于焊接梁結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題，IFA求得的最優(yōu)解為1.724 894，僅略差于MBA的最優(yōu)解。與CDE算法和CPSO算法相比，IFA獲得了較好的最優(yōu)結(jié)果、平均結(jié)果、最差結(jié)果和標(biāo)準(zhǔn)差。

4.2 拉力/壓力彈簧結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題

拉力/壓力彈簧結(jié)果設(shè)計(jì)優(yōu)化問題如圖6所示，其設(shè)計(jì)目標(biāo)是在滿足最小撓度、剪應(yīng)力和振動頻率等約束條件下最小化其質(zhì)量，它有3個設(shè)計(jì)變量，分別是彈簧線圈直徑(1)、彈簧圈平均直徑(2)和有效繞圈數(shù)(3)。

圖6 拉力/壓力彈簧結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題

拉力/壓力彈簧結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題的目標(biāo)函數(shù)和約束條件如下：

利用IFA對拉力/壓力彈簧結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題進(jìn)行求解，并與CDE、CPSO和accelerating adaptive trade-off model (AATM)[18]進(jìn)行比較，結(jié)果如表4和表5所示。

表4 4種算法對拉壓彈簧設(shè)計(jì)問題的最優(yōu)結(jié)果比較

表5 不同算法對拉壓彈簧設(shè)計(jì)問題的尋優(yōu)統(tǒng)計(jì)結(jié)果比較

從表4和表5可以看出：對于拉力/壓力彈簧結(jié)構(gòu)設(shè)計(jì)優(yōu)化問題，與其他3種算法相比，IFA求得了最優(yōu)的結(jié)果。與CDE算法相比，IFA獲得了較好的最優(yōu)結(jié)果，而CDE算法則得到了較好的平均結(jié)果、最差結(jié)果和相似的標(biāo)準(zhǔn)差。與CPSO算法和AATM算法相比，IFA獲得了較好的最優(yōu)結(jié)果、平均結(jié)果、最差結(jié)果和標(biāo)準(zhǔn)差。

5 結(jié)論

1) 提出一種基于動態(tài)隨機(jī)局部搜索和多樣性變異的改進(jìn)螢火蟲算法。該算法利用動態(tài)隨機(jī)局部搜索以加快算法的收斂速度，引入多樣性變異操作以避免算法陷入局部最優(yōu)。

2) 該算法比同類算法在搜索能力和搜索效率兩方面均有較大的提高。最后將該算法應(yīng)用于求解2個實(shí)際工程設(shè)計(jì)優(yōu)化問題，獲得了較滿意的結(jié)果。

[1] Pan Q, Suganthan P, Wang L, et al. A differential evolution algorithm with self-adapting strategy and control parameters[J]. Computers & Operations Research, 2011, 38(1): 394?408.

[2] Long W, Liang X, Huang Y, et al. A hybrid differential evolution augmented Lagrangian method for constrained numerical and engineering optimization[J]. Computer-Aided Design, 2013, 45(12): 1562?1574.

[3] Yang X. Firefly algorithms for multimodal optimization[C]// Proceedings of the International Conference on Stochastic Algorithms: Foundations and Applications. Beilin: Springer-Verlag, 2009: 169?178.

[4] Pal S, Rai C, Singh A. Comparative study of firefly algorithm and particle swarm optimization for noisy non-linear optimization problems[J]. International Journal of Intelligent Systems and Applications, 2012, 4(10): 50?57.

[5] Yang X, Hosseini S, Gandomi A. Firefly algorithm for solving non-convex economic dispatch problems with value loading effect[J]. Applied Soft Computing, 2012, 12(3): 1180?1186.

[6] Gandomi A, Yang X, Alavi A. Mixed variable structural optimization using firefly algorithm[J]. Computers and Structures, 2011, 89: 2325?2336.

[7] Kumbharana S, Pandey M. Solving traveling salesman problem using firefly algorithm[J]. International Journal for Research in Science & Advanced Technologies, 2013, 2(2): 53?57.

[8] Liu B, Wang L, Jin Y, et al. Improved particle swarm optimization combined with chaos[J]. Chaos, Solis & Fractals, 2005, 25(5): 1261?1271.

[9] Hamzacebi C. Improving genetic algorithms’ performance by local search for continuous function optimization[J]. Applied Mathematics and Computation, 2008, 196(1): 309?317.

[10] Wang Y, Cai Z, Zhou Y, et al. Constrained optimization based on hybrid evolutionary algorithm and adaptive constraint?handling technique[J]. Structural Multidiscipline Optimization, 2009, 37(4): 395?413.

[11] Deb K. An efficient constraint handling method for evolutionary optimization[J]. Computers Methods in Applied Mechanics and Engineering, 2000, 186(2/3/4): 311?338.

[12] Runarsson T, Yao X. Stochastic ranking for constrained evolutionary optimization[J]. IEEE Transactions on Evolutionary Computation, 2000, 4(3): 284?294.

[13] Gandomi A, Yang X, Talatahari S, et al. Coupled eagle strategy and differential evolution for unconstrained and constrained global optimization[J]. Computers and Mathematics with Applications, 2012, 63(1): 191?200.

[14] Deshpande A, Phatnani G, Kulkarni A. Constraint handling in firefly algorithm[C]//Proceedings of IEEE International Conference on Cybernetics. Lausame, Switzerland: IEEE Press, 2013: 186?190.

[15] Huang F, Wang L, He Q. An effective co-evolutionary differential evolution for constrained optimization[J]. Applied Mathematics and Computation, 2007, 186(1): 340?356.

[16] He Q, Wang L. An effective co-evolutionary particle swarm optimization for constrained engineering design problems[J]. Engineering Applications of Artificial Intelligence, 2007, 20(1): 89?99.

[17] Sadollah A, Bahreininejad A, Eskandar H, et al. Mine blast algorithm: A new population based algorithm for solving constrained engineering optimization problems[J]. Applied Soft Computing, 2013, 13(5): 2592?2612.

[18] Wang Y, Cai Z, Zhou Y. Accelerating adaptive trade-off model using shrinking space technique for constrained evolutionary optimization[J]. International Journal for Numerical Methods in Engineering, 2009, 77(11): 1501?1534.

(編輯 楊幼平)

Firefly algorithm for solving constrained optimization problems and engineering applications

LONG Wen1, CAI Shaohong1, JIAO Jianjun1, CHEN Yixiong2, HUANG Yafei2

(1. Guizhou Key Laboratory of Economics System Simulation, Guizhou University of Finance and Economics, Guiyang 550004, China; 2. School of Information Science and Engineering, Central South University, Changsha 410083, China)

Firefly algorithm (FA) has a few disadvantages in the global searching, including slow convergence speed and high possibility of being trapped in local optimum. An improved FA was proposed to solve constrained optimization problems. Firstly, chaotic sequence was used to initiate firefly position. Secondly, dynamic random local search technique was introduced to improve speed of convergence; thirdly, a diversity mutation operator was given on the global optimum of each generation, thus the algorithm could effectively jump out of local minima. The experimental results and comparisons with other meta-heuristic methods using a set of numerical and engineering optimization problems show that the proposed algorithm is an effective method.

firefly algorithm; constrained optimization problem; dynamic random local search; engineering optimization

10.11817/j.issn.1672-7207.2015.04.013

TP273

A

1672?7207(2015)04?1260?08

2014?04?22；

2014?06?22

國家自然科學(xué)基金資助項(xiàng)目(61463009)；貴州省科學(xué)技術(shù)基金資助項(xiàng)目(黔科合J字[2013]2082號)(Project (61463009) supported by the National Natural Science Foundation of China; Project ([2013]2082) supported by the Science Technology Foundation of Guizhou Province, China)

龍文，博士，教授，從事進(jìn)化計(jì)算、系統(tǒng)建模與優(yōu)化控制研究；E-mail：lw084601012@163.com