花粉授粉機制在改進粒子群算法研究

曲鵬舉,何 雪

(貴州理工學院工程訓練中心,貴州 貴陽 550025)

0 引言

隨著“中國制造2025”概念的提出,柔性化制造對我國創新發展新技術起到了一定的促進作用,而柔性作業中的多目標優化問題也成為研究重點。

很多學者在柔性作業加工多目標優化方面進行了研究。朱光宇等[1]針對緊前工序對機床主件制造車間生產調度的影響,構建考慮運輸時間的緊前約束下的四目標柔性作業車間調度模型,設計基于勾股模糊前景值最優覓食算法求解該調度模型;Agel等[2]為解決柔性作業調度問題,提出相較于其他算法更為簡單高效的后啟發式迭代貪婪算法;唐紅濤等[3]針對加工時間不確定的模糊分布式柔性作業車間調度問題,在引入三角模糊數的基礎上,提出了一種改進的灰狼優化算法以最小化最大模糊完工時間;李瑞等[4]針對同時考慮最大模糊完工時間和總模糊機器負載的雙目標模糊柔性作業車間調度問題,提出了一種改進的基于分解的多目標進化算法;孟磊磊等[5]針對分布式柔性作業車間最小化最大完工時間問題,提出一種混合蛙跳算法;Meng等[6]針對柔性作業調度加工問題提出了一種基于區間決策變量和域濾波算法的高效約束規劃(CP)模型。上述文獻已經利用改進蟻群算法、貪婪算法、遺傳算法等進行了研究,但是還沒有粒子群算法結合Logistic與花朵授粉算法對柔性作業多目標優化問題的研究。

針對柔性作業中多目標優化問題,首先構建多目標任務滿意度數學模型,該模型以最小加工時間、最低制造成本、最短運輸時間為目標,去量綱操作后利用幾何平均法求解綜合滿意度評價值;其次為了解決標準粒子群算法求解過程中收斂性緩慢、穩定性低、易陷入局部最優等缺點,提出一種改進的粒子群算法(Logistic chaotic map and flower pollination mechanism employed in particle swarm optimization,LFPSO),該算法通過改良粒子群算法的慣性權重平衡全局和局部搜索能力;同時,為增加粒子群前期的搜索性能,在慣性權重中加入了Logistic混沌映射豐富粒子多樣性;再次,為平衡全局搜索能力與局部搜索能力,引入花粉授粉機制作為全局搜索閾值控制粒子群算法全局搜索和局部搜索的啟動時間,最后通過仿真驗證了算法的適用性。

1 數學模型構架

1.1 模型描述

柔性作業多目標優化問題定義:已知有n個待加工工件,在m臺可用機器設備上進行加工,每個工件有m道工序需要加工,每個工件的加工工序以及加工耗時已知[7],在約束條件下,使加工時間、加工成本、儲存成本最低。

表1 柔性作業多目標優化參數及評價指標

加工時間目標函數為

minFmax=min{maxTk}

(1)

式中:maxTk為第k號機器實際運行時間的最大值; minFmax為加工時間目標函數,表示所有設備最小完成時間。

制造成本的目標函數為

(2)

式中: minCT為所有加工工件的全部成本的最小值。

儲存成本目標函數為

(3)

式中:minS為工件儲存成本最小值。

1.2 滿意度評價值構造

為綜合考慮多目標加工問題加工滿意度,將加工時間、制造成本和儲存成本去量綱化操作,消除量綱不同對滿意度評價值的影響,從而得到相應的去量綱化比值,計算過程如下:

(4)

(5)

(6)

式中:F0、C0、S0分別為目標函數加工時間、制造成本、儲存成本去量綱化后的比值。

利用何平均法求解綜合滿意度評價值,即

(7)

式中:χ為綜合滿意度評價值,其大小直接反映了加工時間、制造成本、儲存成本情況。

1.3 柔性作業多目標優化問題約束條件

加工約束條件為:

maxχ

(8)

minFmax

(9)

(10)

minCT

(11)

(12)

minS

(13)

S′≥S

(14)

Fijk-Fi(j-1)k≥Cijk

(15)

Cijk>0

(16)

Fabk-Fijm≥Cabk

(17)

Fijm≥Cijk

(18)

式(8)表示求解最大綜合滿意度評價值;式(9)、式(10)表示所有工件實際完成的時間必須在可接受最大加工時間之內;式(11) 、式(12)表示所有工件實際加工成本必須在可接受最大加工成本之內;式(13) 、式(14)表示實際儲存成本必須在可接受最大儲存成本之內;式(15)表示任意工序必須在其緊前工序完成之后進行;式(16)表示任意工序持續時間都不為0;式(17)表示任意工序的持續時間不能大于最后一道工序時長;式(18)表示任意工序加工時間都不少于預設定加工時長。

2 改進粒子群算法

2.1 標準粒子群算法

標準粒子群優化算法(particle swarm optimization,PSO)因其實現過程簡單、設定參數少等特點在眾多領域獲得應用。標準的粒子群優化算法位置和速度狀態屬性為:

(19)

(20)

2.2 Logistic混沌映射改進

Logistic混沌映射具有普遍性和隨機性的特點[8],為了增加粒子群算法粒子多樣性,在粒子群算法中加入Logistic混沌映射可以豐富粒子種群數量。Logistic混沌映射公式為

αt+1=αt×σ(1-αt)

(21)

式中:αt為Logistic映射函數第t次迭代的值;σ為Logistic映射函數參數,σ∈(0,4)。

σ越小,αt隨機性越差,隨著迭代次數的增多,αt會逐漸趨于定值;σ越大,αt隨機性越強,因此為了保證Logistic映射的隨機性和多樣性,在取值范圍內,σ值越大越好,因此取σ=3.998,α0=1。

2.3 粒子群算法慣性權重冪函數改進

慣性權重ω是粒子群算法的重要參數,直接影響算法的收斂速度,改進慣性權重對算法有重要影響。為改進標準粒子群算法缺陷,提出慣性權重冪函數自適應調節方法,即

(22)

式中:ωmax為慣性權重最大值;ωmin為慣性權重最小值。

當ωmax=0.9,ωmin=0.4時,算法有較好的搜索性能。慣性權重冪函數自適應調節,在粒子群算法運行初期,可以擴大粒子搜索范圍,加大粒子發散性;在算法后期慣性權重呈冪函數遞減狀態,能夠快速局部尋優,提升算法效率。

2.4 花朵授粉機制的引進

花朵授粉算法(flower pollination algorithm,FPA)是一種啟發式算法,具有全局授粉規則、局部授粉規則2種機制。全局授粉規則和局部授粉規則之間的轉換通過FPA算法轉換概率規則進行選擇。如果轉換概率p取值過大,算法長期處于全局搜索階段,收斂速度過慢[9];如果轉換概率p過小,算法過早陷入局部搜索,容易陷入局部最優,影響算法尋優能力[10]。

因此,在粒子群算法中引入花朵授粉算法進行粒子位置更新,同時引入概率轉換規則控制粒子群算法的全局搜索和局部搜索之間轉換閾值p,全局搜索規則為

(23)

萊維飛行公式為

(24)

轉換閾值p為

(25)

式中: rand∈(0,1)為隨機數;pmax為最大轉換概率,pmin為最小轉換概率,pmax=0.8,pmin=0.2;t為當前迭代次數;tmax為最大迭代次數,若rand≤p,則按照式(20)更新粒子位置,若rand>p,則按照式(23)更新粒子位置,通過轉換閾值p實現了全局搜索和局部搜索的轉換。

LFPSO算法流程如下:

a.通過式(1)～式(18)建立柔性作業多目標綜合滿意度評價模型。根據約束條件式(8)～式(18),并通過式(1)～式(3)建立目標函數加工時間minFmax、制造成本minCT和儲存成本minS,根據式(4)和式(6)對3個目標函數去量綱化操作,在算法進化過程中不斷記錄3個目標函數及去量綱化比值,建立柔性作業多目標綜合滿意度評價模型。

b.設定改進粒子群算法參數,包括粒子數N、最大迭代次數tmax等。

c.根據式(21)在粒子群算法前期引入Logistic混沌映射。

d.根據式(22)改進粒子群算法慣性權重。

e.根據式(25),計算轉換閾值p,并與rand進行比較,若rand>p,則粒子群算法按照式(23)進行全局搜索,若rand≤p,則按照式(20)進行局部搜索。

f.計算新解的適應度,并與當前解進行比較。

g.判定是否達到最大迭代次數,若t=tmax,輸出當前最優解,并作為全局最優解;若t

LFPSO算法流程如圖1所示。

圖1 LFPSO算法流程

3 仿真驗證

由于LFPSO算法為隨機優化算法,為驗證LFPSO算法的性能,對比LFPSO算法與經典PSO算法[11]、花朵授粉算法(FPA)[12]、慣性權重余弦自適應調節粒子群算法(CPSO)[13]和一維編碼粒子群算法(HRPSO)[14]在求解6個測試函數與6個不同規模加工作業算例的表現。設備參數為Win10 64位Inter(R) Core (TM) i5-9400 @2.90 GHz RAM 8 GB MATLAB2014b。

3.1 求解測試函數

選取6個有代表性的測試函數,種群規模均為N=40,維度D=50,測試函數均是fmin=0時取得最優。測試函數信息如表2所示,結果如表3所示。

表2 測試函數信息表

表3 測試函數結果平均值

由表3可知,在6個測試函數的結果平均值中,LFPSO算法在4個測試函數f2、f4、f5和f6中都取得了最好的結果,HRPSO算法在f1和f4測試函數中取得了最優,CPSO算法在f3測試函數中取得了最優值,而PSO和FPA算法在6個測試函數中求得的最優值個數均為0。與其他4種算法相比,LFPSO算法在3個多峰函數中都求得最優結果,證明其在求解多峰函數問題上性能較好。

3.2 求解不同規模加工作業算例

選取6個不同規模加工作業算例,用LFPSO與其他算法求解對比,種群規模N=50,最大迭代次數tmax=500,不同規模加工信息對比結果如表4所示。

表4 不同規模加工信息對比

在6個不同規模的加工任務中,PSO算法在加工時間、制造成本、儲存成本3個優化目標中都是最多的,其次是FPA算法,LFPSO算法在加工工件數和機器數較少的任務1和任務2中并沒有體現出較大的優勢,CPSO和HRPSO算法在任務1和任務2中優勢比較明顯,綜合滿意度值比較高;隨著加工工件數和機器數的增多,在任務3～任務6中,LFPSO算法優勢體現了出來,加工時間、制造成本、儲存成本3個優化目標均為最優,綜合滿意度值也最高。

隨著工件數和機器數的增多,加工任務規模增大,各算法求解時長不斷增長,任務1中,求解時長最大的算法為PSO算法(8.6 s),最短的是HRPSO算法(8.0 s)和LFPSO算法(8.0 s),時間差率(時間差率=(最大求解時長-最小求解時長)/ 最大求解時長)為6.98%;任務2中,求解時長最長的算法為PSO算法(15.7 s),最短的是LFPSO算法(14.2 s),時間差率為9.55%;任務3中,求解時長最長的算法為PSO算法(24.3 s),最短的是LFPSO算法(19.6 s),時間差率為19.34%;任務4中,求解時長最長的算法為PSO算法(49.7 s),最短的是LFPSO算法(37.7 s),時間差率為24.14%;任務5中,求解時長最長的算法為PSO算法(77.3 s),最短的是LFPSO算法(60.9 s),時間差率為23.80%;任務6中,求解時長最長的算法為PSO算法(139.7 s),最短的是LFPSO算法(106.8 s),時間差率為23.55%。

在綜合滿意度和求解時長的分析中,任務1和任務2中LFPSO算法優勢沒有體現出來可能是因為LFPSO算法采用了Logistic混沌映射,粒子發散性多樣性比較好,在加工任務數量少的時候,啟動耗時較多,而隨著加工任務的增多,算法運行時間顯著增加,LFPSO算法在求解柔性作業多目標優化問題的優勢體現出來。綜合滿意度值和迭代次數如圖2所示。

圖2 綜合滿意度值和迭代次數

4 結束語

在柔性作業多目標加工問題研究中,提出了改進粒子群算法(LFPSO),得到了以下結論:

a.在多目標加工問題數學模型構造中,以最小加工時間、最低制造成本、最短運輸時間為目標,去量綱操作后利用幾何平均法求解綜合滿意度評價值,增加了數學模型的適用范圍。

b.粒子群算法慣性權重的改進,對全局和局部搜索能力的平衡有重要作用;為增加粒子群前期的搜索性能,在慣性權重中加入了Logistic混沌映射豐富粒子多樣性,為平衡全局搜索能力與局部搜索能力,引入花粉授粉機制作為全局搜索閾值,加強粒子群算法搜索性能。

c.LFPSO算法通過與其他4種算法測試函數和仿真實例結果對比,驗證了LFPSO算法的在求解柔性作業多目標優化問題的有效性。