基于改進人工蜂群算法的貨車載貨平衡問題研究

付中華，馬英鈞

(1.武漢城市職業(yè)學(xué)院 初等教育學(xué)院，湖北 武漢 430000；2.華中師范大學(xué) 數(shù)統(tǒng)學(xué)院，湖北 武漢 430079)

基于改進人工蜂群算法的貨車載貨平衡問題研究

付中華1，馬英鈞2

(1.武漢城市職業(yè)學(xué)院 初等教育學(xué)院，湖北 武漢 430000；2.華中師范大學(xué) 數(shù)統(tǒng)學(xué)院，湖北 武漢 430079)

貨車載貨平衡問題是多約束的雙目標規(guī)劃問題，傳統(tǒng)的規(guī)劃算法往往具有較大的時間消耗。為此，針對ABC算法的特點，借鑒傳統(tǒng)遺傳算法求解組合優(yōu)化問題上的優(yōu)勢、粒子群算法的歷史極值與全局極值搜索機制及模擬退火的全局搜索策略，提出了一種求解該問題的新方法。在此基礎(chǔ)上通過數(shù)值實驗求解車廂個數(shù)為10、箱子個數(shù)為50的較復(fù)雜貨車載貨問題，并與傳統(tǒng)的遺傳算法進行對比，最終的結(jié)果表明改進算法對于貨車載貨平衡問題具有較高的求解效率。

改進ABC算法;貨車載貨平衡;遺傳算法;全局搜索機制;模擬退火策略

人們在通過工業(yè)化提高自己生活水平的同時也付出了較大的環(huán)境代價，在1970年之前的200年內(nèi)，人均耗能增加了9倍，在之后的40年內(nèi)，人均耗能又增長了25%，因此，節(jié)能減排勢在必行，是我國實現(xiàn)可持續(xù)發(fā)展的重要戰(zhàn)略舉措[1]。加強物流管理、完善物流流程、降低物流費用等增強企業(yè)競爭力的舉措越來越得到經(jīng)營者和管理者的認可,同時這也是節(jié)能減排、實現(xiàn)可持續(xù)發(fā)展的一個重要體現(xiàn)[2]。

貨車載貨問題屬于在m臺相同的機器上調(diào)度n個非搶先的任務(wù)問題，也成為m處理機調(diào)度問題，最小化貨車的最大載荷即對應(yīng)于最小化調(diào)度方案的總時間消耗。其是一種較復(fù)雜的NP-hard問題，若將該問題表示為線性問題，則很難解決處理機數(shù)超過3個、任務(wù)數(shù)超過30個的問題。針對兩臺機器和100個以內(nèi)的問題，利用動態(tài)規(guī)劃方法和樹搜索算法處理，往往需要較長的優(yōu)化時間。采用LPT(最長處理時間)啟發(fā)式算法可以很快找到較好的解，該算法的基本原則是在每次迭代中將最長處理時間的任務(wù)安排在負荷最輕的機器上，但是其尋找最優(yōu)解的比率很低[3]。

人工蜂群算法(ABC算法)于2005年系統(tǒng)被提出[4]，并在2007—2009年首次被應(yīng)用于無約朿函數(shù)優(yōu)化中，通過與差分進化算法、粒子群算法進行比較，驗證了ABC算法的良好性能。近年來，很多學(xué)者針對蜂群算法進行多方面的改進，極大地提高了蜂群算法的優(yōu)化性能。魯建廈等[5]將遺傳算法的選擇、突變等操作引入ABC算法，增加了傳統(tǒng)的ABC算法求解約束優(yōu)化問題的能力。筆者借鑒遺傳算法求解組合優(yōu)化問題時的交叉變異操作，改進傳統(tǒng)ABC算法中的鄰域搜索機制，加入粒子群算法的全局極值和歷史極值搜索，同時將模擬退火策略引入蜂群的選擇機制，并通過實驗仿真進一步驗證改進的ABC算法的求解效率。

1 貨車載貨平衡問題

1.1 問題描述

貨車載貨平衡問題可以描述為：有n節(jié)貨車車廂，其最大允許載重均為cap，使用者用n節(jié)車廂運輸m個箱子，這些箱子的重量分別為wi(i=1,2,…，m)，需要解決的問題是如何分配才能使得每節(jié)車廂的實際載重均不超過最大允許載重，且使裝載量最大的車廂的裝載量最小,同時保證車廂能夠裝載盡可能多的箱子。

1.2 模型建立

(1)定義裝載方案變量loadi(i=1,2,…，m)表示第i個箱子裝載到第loadi個貨車車廂上，根據(jù)實際條件，這些變量取整數(shù)，且應(yīng)滿足貨車車廂總個數(shù)的約束。因此可定義約束條件(1)和約束條件(2)。

0≤landi≤n

(1)

landi∈Z

(2)

特別地，當(dāng)landi=0，表示箱子i不裝入任何一個車廂。

(2)每節(jié)車廂的實際載重不能超過最大允許載重cap，因此，可定義約束條件(3)。

(3)

(3)為了保證車廂間的裝載量更為均衡，令f1表示當(dāng)前裝載量最大的車廂，只需要求f1盡可能地小就可達到，因此可表示為式(4)的形式。

(4)

(4)保證盡可能多的箱子裝入車廂，即使得剩余的重量盡可能小，可定義目標函數(shù)f2：

(5)

綜上，優(yōu)化的最終目標是在保證約束(1)～約束(3)成立的條件下，使得目標函數(shù)f1和f2盡可能地小。

2 人工蜂群算法簡介及改進

2.1 人工蜂群算法簡介

ABC算法包括初始化階段、采蜜蜂階段、觀察蜂階段、偵察蜂階段[6]，具體過程如下：

(1)算法的初始狀態(tài)由偵查蜂生成一組隨機的蜜源位置Xi=(xi1,xi2,…,xiD)其中，i=1,2，…,NS,NS表示蜜源的個數(shù)，D表示問題解的維數(shù)。

(2)算法的循環(huán)迭代過程主要包括采蜜蜂的鄰域搜索、觀察蜂的選擇和搜索、偵查蜂的決策和選擇3個階段。采蜜蜂根據(jù)偵查蜂反饋的蜜源信息，按照式(6)對蜜源的鄰域進行搜索，并利用貪婪準則進行更新；對于采蜜蜂反饋的蜜源信息，觀察蜂利用輪盤賭的方式進行選擇，并根據(jù)式(6)對選擇的蜜源進行鄰域搜索；在算法進行過程中，偵查蜂根據(jù)蜜源的開采次數(shù)Bas和控制參數(shù)Limit的關(guān)系，判斷是否舍棄該蜜源，并利用式(7)進行更新。

(6)

(7)

式中：j為隨機選擇的維度；Xi為原始蜜源；Xk為選擇的蜜源；new_Xji鄰域搜索后產(chǎn)生的新蜜源；xjmax,xjmin分別為第j個分量的取值上界和下界。

(3)根據(jù)循環(huán)數(shù)和預(yù)設(shè)定的最大循環(huán)代數(shù)來判定是否跳出迭代。

2.2 算法改進

針對貨車載貨平衡問題多約束雙目標規(guī)劃的特點，借鑒遺傳算法求解組合優(yōu)化問題時交叉、變異算子、粒子群算法的全局搜索及模擬退火算法特點，將式(6)中的鄰域搜索操作替換為隨機基因位交叉和全局交叉相結(jié)合；貪婪選擇機制改為模擬退火選擇策略；將雙目標規(guī)劃通過加權(quán)轉(zhuǎn)化為單目標優(yōu)化問題。

2.2.1 生成初始可行蜜源

貨車載貨的車廂裝載方案必須滿足整數(shù)條件，因此采用整數(shù)編碼的方式產(chǎn)生初始蜜源。對于任一蜜源X=(x1,x2,…，xm)，其中xi為第i個貨箱的實際裝載方案，xi∈{0,1,2,…，n}，因此隨機生成[0,n]間的m維整數(shù)作為初始蜜源。例如,對于車廂的個數(shù)n=3,箱子的個數(shù)m=5，蜜源X=(1,3,1,3,2)表示第1,2,3,4,5個箱子分別裝載在第1,3,1,3,2節(jié)車廂。

2.2.2 改進鄰域搜索策略

傳統(tǒng)的ABC算法中，采蜜蜂和觀察蜂利用式(6)進行鄰域搜索，這比較適合實數(shù)編碼的蜜源搜索，但對于筆者研究的問題會產(chǎn)生許多非整數(shù)蜜源維度。為了減少計算的復(fù)雜度，提升蜂群鄰域搜索的效率，筆者借鑒遺傳算法的交叉算子和粒子群算法的全局極值更新算子對蜂群的鄰域搜索操作進行改進，改進公式的簡單形式如式(8)所示：

(8)

式中：F表示new_Xji與Xji,Xjk,XjP,XjG間存在著一定的關(guān)系；Xjk為隨機選取的鄰域蜜源；XjP為該蜜源的歷史最優(yōu)蜜源；XjG為全局最優(yōu)蜜源。

鄰域搜索的具體操作步驟為：①生成[1,m]間的隨機整數(shù)j，表示鄰域搜索的維度。②按照式(9)和式(10)分別計算進化因子μ和判別概率P，其中cycle為當(dāng)前的代數(shù)，maxcycle為總迭代代數(shù)。③根據(jù)判別概率，確定蜜源進行局部極值更新和全局極值更新，即當(dāng)P<0.5時，new_Xji=XjP；否則new_Xji=XjG。

(9)

(10)

由式(9)可以看出，迭代初期進化因子μ較小，對應(yīng)的判別概率P也較小，此時進行歷史極值更新，使粒子能夠較自由地發(fā)散到搜索空間中,較少受到“社會意識部分”的影響,以增加群內(nèi)粒子的多樣性[7]；隨著迭代次數(shù)cycle的增加,判別概率P逐漸變大，此時較大的概率進行全局極值更新,進而加強了粒子向全局最優(yōu)點的收斂能力。

2.2.3 模擬退火的選擇策略

傳統(tǒng)的ABC算法，當(dāng)采蜜蜂和觀察蜂進行鄰域搜索后，利用貪婪策略進行蜜源選擇，盡管可以較快地找到局部最優(yōu)的蜜源，但是同樣會丟失暫時適應(yīng)度不高、但更接近全局最優(yōu)的蜜源。借鑒模擬退火策略的概率全局優(yōu)化性能[8]，筆者利用模擬退火策略代替貪婪選擇，具體的算法步驟為：①在算法起始設(shè)定初始溫度T和退火參數(shù)k。②比較原始蜜源的適應(yīng)度f(X)和鄰域搜索后蜜源的適應(yīng)度f(X′)，若f(X′)≤f(X)，則接受新解X′；若f(X′)>f(X)，則以概率P接受新解，其中P=e-[f(X′)-f(X)]/kT。③按照一定的方式對當(dāng)前溫度T進行降溫。

在為期4天的游學(xué)之旅中，游學(xué)隊伍先后轉(zhuǎn)輾河南省上蔡金豐公社、邵店分社、韓寨分社、小岳寺分社，河南省驛城金豐公社、和崗分社、程樓分社，河北省行唐金豐公社、伏流分社、上碑分社，3個金豐公社10個觀摩點，輾轉(zhuǎn)1000多公里，進行現(xiàn)場觀摩學(xué)習(xí)，各分社社長現(xiàn)場講解如何建組織配機械、如何發(fā)動農(nóng)戶、如何實現(xiàn)服務(wù)本村農(nóng)戶的過程和關(guān)鍵環(huán)節(jié)，各事業(yè)合伙人現(xiàn)場提問，邊聽邊記，學(xué)之所長。

模擬退火策略在一定程度上保留了貪婪策略的擇優(yōu)選擇思想，同時也以一定的概率接受新的次優(yōu)解，在一定程度上增強傳統(tǒng)ABC算法跳出局部最優(yōu)的能力[9]。

2.2.4 約束條件和多目標處理

智能算法本質(zhì)上是基于區(qū)間約束優(yōu)化問題提出的，由式(3)容易看出，筆者所研究問題中的約束條件較多，為了消除不同約束條件間的量級差異，筆者在對約束條件進行歸一化處理的基礎(chǔ)上，針對約束條件式(3)和目標函數(shù)式(4)、式(5)，建立蜜源的總罰值函數(shù)和適應(yīng)度函數(shù)，具體過程如下：①計算蜜源關(guān)于約束條件式(3)的罰函數(shù)值qj(X)，如式(10)所示。②將約束函數(shù)和目標函數(shù)進行綜合處理，根據(jù)重要性設(shè)置權(quán)重，計算總目標函數(shù)值F(X)，具體計算公式如式(11)所示。

(10)

(11)

對于該問題，首先必須滿足約束條件是最為重要的，其次要求車廂里面能裝載盡可能多的箱子，最后才是車廂間的平衡，權(quán)重的設(shè)置通過單位歸一化和數(shù)量級的差別表示其重要性的區(qū)別。綜上，得到改進的人工蜂群算法流程圖,如圖1所示。

圖1 改進的人工蜂群算法流程圖

3 仿真模擬及結(jié)果分析

設(shè)定車廂的個數(shù)n=10，箱子的個數(shù)m=50，車廂的最大容量cap=100，箱子的重量wi如表1所示，箱子的總重量為908，平均每個車廂分配的最大箱子重量的下界為90.8。

表1 箱子重量

采用Matlab 12a進行編程，分別利用筆者提出的改進人工蜂群算法和遺傳算法進行求解。人工蜂群算法的參數(shù)設(shè)置為：蜜源規(guī)模NS=200,控制參數(shù)Limit=20，最大循環(huán)代數(shù)maxcycle=500；遺傳算法的參數(shù)設(shè)置為：種群規(guī)模popsize=200，最大遺傳代數(shù)maxgen=500，交叉概率Pc=0.8，變異概率Pm=0.2，代溝GGAP=0.9。得到的最優(yōu)裝載方案如表2所示。

表2 兩種算法的最優(yōu)裝載方案結(jié)果對比

由表2可以看出，無論人工蜂群算法還是遺傳算法，得到的結(jié)果都能保證滿足約束條件，并且使得目標函數(shù)f1達到最小,剩余物品重量為0。但是對于目標函數(shù)f2,改進蜂群算法求得的最小值為92,遺傳算法求得的最小值為99。

圖2 兩種算法的優(yōu)化過程對比

兩種算法的優(yōu)化過程對比如圖2所示，可以看出改進的人工蜂群算法經(jīng)過500次左右的迭代已經(jīng)可以找到全局最優(yōu)解，而傳統(tǒng)的遺傳算法只能得到局部最優(yōu)解，初步說明了改進人工蜂群算法對于貨車載貨平衡問題有較高的求解效率。同時，在迭代初期遺傳算法和改進人工蜂群的迭代效率較為接近，但是在100代左右遺傳算法基本上陷入停滯狀態(tài)；而改進人工蜂群算法卻能跳出局部最優(yōu)解，最終達到全局最優(yōu)解，進一步說明改進人工蜂群算法在求解貨車載貨平衡問題時的高效性。

4 結(jié)論

筆者采用改進人工蜂群算法求解貨車載貨平衡問題，借鑒遺傳算法的編碼方式和交叉變異操作、粒子群算法的全局和歷史極值更新機制及模擬退火選擇策略，在一定程度上提升了人工蜂群算法解決組合優(yōu)化問題的性能和全局搜索的能力，通過仿真實驗進一步驗證了算法的有效性。將智能算法應(yīng)用到貨車載貨方案設(shè)計中，不僅提高了車輛的運輸效率，同時增強了車輛的安全性能。降低物流的費用，提升物流運輸?shù)男?，為企業(yè)管理者的決策安排提供了科學(xué)的依據(jù)。但是筆者算法的一些操作只是針對貨車載貨平衡問題提出的，在后續(xù)的研究中尚需進一步進行推廣研究。

[1] 董奧,平星星,姜亮,等.基于能效監(jiān)測的能源管理優(yōu)化[J].節(jié)能技術(shù),2013,31(3):269-273.

[2] 李德福.中小企業(yè)物流管理優(yōu)化策略研究[J].物流科技,2010,33(2):53-55.

[3] GUERET C, PRINS C, SEVAUX M. Applications of optimization with Xpress-MP[M].Pairs: Dash Optimization Ltd，2006:171-195.

[4] 王艷嬌.人工蜂群算法的研究與應(yīng)用[D].哈爾濱：哈爾濱工程大學(xué),2013.

[5] 魯建廈,翁耀煒，李修琳，等.混合人工蜂群算法在混流裝配線排序中的應(yīng)用[J].計算機集成制造系統(tǒng)，2014,20(1):121-127.

[6] 馬英鈞.基于人工蜂群算法的約束優(yōu)化問題研究[D].武漢：華中師范大學(xué),2015.

[7] 馮翔,陳國龍,郭文忠.粒子群優(yōu)化算法中加速因子的設(shè)置與試驗分析[J].集美大學(xué)學(xué)報(自然科學(xué)版)，2006,11(6):146-151.

[8] 吳意樂,何慶.基于改進遺傳模擬退火算法的WSN路徑優(yōu)化算法[J].計算機應(yīng)用研究，2016,33(10):2959-2960.

[9] 盧宇婷,林禹攸.模擬退火算法改進綜述及參數(shù)探究[J].大學(xué)數(shù)學(xué)，2015,31(6):97-103.

[10] 王松,李紅星.基于遺傳搜索策略的人工蜂群算法[J].北京聯(lián)合大學(xué)學(xué)報，2017,31(1):87-91.

FU Zhonghua:Assoc. Prof.; Primary Education College,Wuhan City Vocational College, Wuhan 430000,China.

Research on Truck Load Balancing Problem Based on Improved Artificial Bee Colony Algorithm

FUZhonghua，MAYingjun

The problem of truck load balance is a bi-objective programming with multi-conditions. The traditional planning method spends a lot of time. A new method is given to solve this problem in this paper, it based on the traditional legend method and characteristics of ABC algorithm with the advantages of combinatorial optimization, the historical extremum of swarm optimization algorithm, global extremum searching mechanism and global search strategy on simulated annealing. Finally,it uses numerical experiments to solve truck load balance problem with 10 compartments and 50 cases. Comparing with the traditional method,the improved algorithm has a high efficiency for the truck load balance problem.

improved ABC algorithm;truck load balancing problem;genetic algorithm;global search mechanism;simulated annealing strategy

2095-3852(2017)04-0484-04

A

2017-02-26.

付中華(1965-)，女，湖北隨州人，武漢城市職業(yè)學(xué)院初等教育學(xué)院副教授,主要研究方向為數(shù)據(jù)挖掘.

馬英鈞(1987-)，男，河南南陽人，華中師范大學(xué)數(shù)統(tǒng)學(xué)院博士研究生，主要研究方向數(shù)據(jù)挖掘.

武漢市高教局教學(xué)研2014年度重點課題基金項目(2014035).

TP301.6

10.3963/j.issn.2095-3852.2017.04.021