李俊青 王 永 桑紅燕 高開周 韓玉艷 孟 濤

(1.聊城大學(xué) 計算機(jī)學(xué)院，山東 聊城 252059；2.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟(jì)南 250014)

人工蜂群優(yōu)化及其在資源管理中的應(yīng)用①

李俊青1,2王 永1桑紅燕1高開周1韓玉艷1孟 濤1

(1.聊城大學(xué) 計算機(jī)學(xué)院，山東 聊城 252059；2.山東師范大學(xué) 信息科學(xué)與工程學(xué)院，山東 濟(jì)南 250014)

近年來，各種智能優(yōu)化算法得到了廣泛推廣和應(yīng)用，人工蜂群優(yōu)化作為其中的一種典型算法被成功應(yīng)用到工業(yè)界和制造業(yè)，譬如求解鋼鐵生產(chǎn)調(diào)度問題、供應(yīng)鏈優(yōu)化過程、交通問題等.本文首先對人工蜂群優(yōu)化算法進(jìn)行描述，并分析了該算法的收斂性.其次，對人工蜂群優(yōu)化算法在各個領(lǐng)域的應(yīng)用進(jìn)行歸類總結(jié).最后，分析了討論了人工蜂群優(yōu)化如何應(yīng)用于教學(xué)設(shè)計，以推動人工智能在教學(xué)改革中的應(yīng)用.

人工蜂群優(yōu)化，智能優(yōu)化算法，收斂性，教學(xué)設(shè)計

0 引言

人工蜂群算法是由Karaboga等[1]于2005年提出的一種新的群體智能優(yōu)化算法，是模擬蜜蜂尋找食物的過程而演化的仿生過程.自2005以來，ABC算法已被應(yīng)用于求解許多優(yōu)化問題[1-4].在基本ABC中，食物源(food source)和人工蜜蜂(artificial bees)是基本構(gòu)成要素.人工蜜蜂又被分為三種[1-4]，即雇傭蜂(Employed bees)、跟隨蜂(Onlooker bees)和偵察蜂(Scout bees).雇傭蜂的任務(wù)是在隨機(jī)食物源周圍進(jìn)一步挖掘，以便找到更好的食物源；在雇傭蜂把挖掘后的信息帶回后，守在蜂巢中的跟隨蜂按照一定概率選擇較好的食物，進(jìn)一步搜索挖掘；當(dāng)某些食物在經(jīng)過一定周期后，未曾發(fā)生改變，則派出偵察蜂隨機(jī)搜索新的食物源.

在2015世界機(jī)器人大會開幕時，習(xí)近平總書記明確指出，要將機(jī)器人和智能制造納入優(yōu)先重點(diǎn)領(lǐng)域，加強(qiáng)同各國科技界、產(chǎn)業(yè)界的合作，推動機(jī)器人科技研發(fā)和產(chǎn)業(yè)化進(jìn)程，使機(jī)器人科技及其產(chǎn)品更好為推動發(fā)展、造福人民服務(wù)[5].人工蜂群優(yōu)化算法作為人工智能領(lǐng)域中的典型算法已經(jīng)越來越得到關(guān)注和推廣.本文首先對人工蜂群優(yōu)化算法進(jìn)行描述，并分析了該算法的收斂性.其次，對人工蜂群優(yōu)化算法在各個領(lǐng)域的應(yīng)用進(jìn)行歸類總結(jié).最后，分析了討論了人工蜂群優(yōu)化如何應(yīng)用于教學(xué)設(shè)計，以推動人工智能在教學(xué)改革中的應(yīng)用.

1 基本人工蜂群算法

1.1 ABC控制參數(shù)

ABC算法中基本控制參數(shù)包括：解集大小SN，解無更新而被丟棄的周期大小Ls，雇傭蜂數(shù)目Es，跟隨蜂數(shù)目Os，偵察蜂數(shù)目Ss和終止條件[1-4].

1.2 初始解集

(1)

1.3 局部搜索策略

雇傭蜂和跟隨蜂采用局部搜索進(jìn)行食物源的搜索挖掘，基本ABC中局部搜索策略為：隨機(jī)找到兩個食物源i和k，計算兩個食物源在第j維度的差值作為更新的部分，其具體計算公式

(2)

其中k∈{1,2,…,SN}∧i≠k.

1.4 全局搜索策略

守候在蜂巢中的跟隨蜂通過輪盤賭注方法，選擇較好的搜索空間繼續(xù)進(jìn)行食物源搜索，其計算公式如

(3)

其中fi表示第i個食物源目標(biāo)值的大小.

2 基本ABC算法收斂性分析

2.1 算法的收斂準(zhǔn)則

以下給出算法的收斂準(zhǔn)則[6,7].

定義1 給定一個目標(biāo)函數(shù)f，其解空間是從Rn到R，S是Rn的一個子集.在S中 某個點(diǎn)z，使得f的值最小化或者至少能夠產(chǎn)生函數(shù)f的一個可接受的近似最優(yōu)解.

假設(shè)1f(H(z,ξ))≤f(z),如果ζ∈S，則f(H(z,ξ))≤f(ξ).其中H是產(chǎn)生一個鄰域解的函數(shù).上述假設(shè)保證采用H函數(shù)產(chǎn)生的新的個體優(yōu)于當(dāng)前個體.

2.2 基本人工蜂群算法的收斂性分析

文獻(xiàn)[6]證明了在基本人工蜂群算法中，存在以下定理：

定理2 蜂群狀態(tài)序列{H(t);t≥0}是有限齊次Markov鏈.

3 人工蜂群算法研究進(jìn)展

3.1 針對連續(xù)優(yōu)化問題求解

Karaboga和Basturk[1]針對多維數(shù)值優(yōu)化問題，對比了ABC、DE、PSO和EA等多種算法，驗(yàn)證了ABC方法的有效性.Kang等[8]融合標(biāo)準(zhǔn)單純形算法和ABC算法，用于求解反演分析問題(inverse analysis problem).Alatas[9]針對全局?jǐn)?shù)值優(yōu)化問題，給出了混沌ABC算法求解.Omkar等[10]給出了一種多目標(biāo)ABC優(yōu)化算法，用于求解組合結(jié)構(gòu)的設(shè)計問題.Karaboga和Akay[11]針對約束優(yōu)化問題，給出了改進(jìn)的ABC算法.Akay和Karaboga[12]設(shè)計了一種改進(jìn)的ABC算法，用于求解實(shí)參優(yōu)化問題.研究表明，基本ABC算法主要應(yīng)用于求解連續(xù)優(yōu)化問題，如何采用ABC算法解決離散優(yōu)化問題是一個研究熱點(diǎn).

3.2 針對算法改進(jìn)

Banharnsakun等[13]改進(jìn)了基本ABC算法中的跟隨蜂策略，全局最好解用于在全體解中共享，以提高算法收斂能力.同時，每次迭代過程中，調(diào)整蜜蜂的搜索范圍半徑，提高了算法全局搜索的能力.Karaboga和Ozturk[14]針對ABC算法進(jìn)行聚類分析，驗(yàn)證了算法的收斂能力.Ozturk等[30]結(jié)合遺傳算子，改進(jìn)了ABC算法的收斂能力和搜索性能.

3.3 針對優(yōu)化調(diào)度問題求解

近年來，ABC算法被廣泛用于求解各種優(yōu)化調(diào)度問題，典型的應(yīng)用包括資源有限的項(xiàng)目調(diào)度問題[15]、帶有時間窗的旅行商問題[16]、低空航空器目標(biāo)識別問題[17]、無人作戰(zhàn)飛行器路徑規(guī)劃問題[18]、可靠性冗余分配問題[19]、設(shè)計和制造中的魯棒優(yōu)化問題[20]等.

在求解車間調(diào)度問題中，ABC算法也得到了一定應(yīng)用.Huang和Lin[21]針對開放車間調(diào)度問題，給出了基于空閑時間過濾機(jī)制的ABC算法.Pan等[22]給出了自適應(yīng)鄰域結(jié)構(gòu)的ABC算法框架；Sang等[23]研究了最小化總流經(jīng)時間的批量流水線調(diào)度問題；Al-Salamah[24]則針對不同批次大小的單機(jī)批量調(diào)度問題，給出了基于約束二進(jìn)制的ABC算法.針對柔性作業(yè)車間調(diào)度問題：文[25]設(shè)計了一種多目標(biāo)ABC優(yōu)化算法；進(jìn)一步，Li等[26]給出了基于Pareto文檔集的多目標(biāo)ABC算法，用于求解帶設(shè)備維修約束的FJSP問題；Gao等[27]則研究了帶有訂單插入的FJSP問題.晏曉輝等[28]則針對銅板帶熔鑄作業(yè)調(diào)度問題，給出了一種多目標(biāo)ABC算法.Sundar等[39]針對無等待作業(yè)車間調(diào)度問題，給出了多種鄰域結(jié)構(gòu)的ABC算法.

4 人工蜂群優(yōu)化在資源管理中的應(yīng)用

4.1 人工蜂群優(yōu)化在排課設(shè)計中的應(yīng)用

排課是教學(xué)中的一項(xiàng)非常重要的工作，涉及學(xué)生、教室、教師等多種因素，包含諸多約束條件和目標(biāo)，因而復(fù)雜的排課任務(wù)可以認(rèn)為是一種NP難問題[30].解決此類問題的有效方法包括確定性算法，譬如分支定界方法、迭代搜索算法等.隨著智能優(yōu)化算法的推廣和應(yīng)用[30,31]，元啟發(fā)式方法在排課系統(tǒng)中得到了越來越多的應(yīng)用和推廣，如粒子群優(yōu)化算法[31]、離散型熒火蟲算法[32]等.

通常，排課系統(tǒng)的主要約束包括：一位教師同一基本教學(xué)時間段只能在一個班級上課；一個班級在同一基本教學(xué)時間段只能上一位教師的課；一個教室在同一基本教學(xué)時間段只能有一個教師上課.另外，由于個別教師的特殊要求，還需要加入一些軟約束條件，譬如，重要的專業(yè)課程最好安排在黃金時間段，教師不要連續(xù)長時間教授課程等.優(yōu)化的目標(biāo)是教師的滿意度、學(xué)生的滿意度達(dá)到最大化，同時滿足各項(xiàng)約束條件.

采用人工蜂群優(yōu)化算法設(shè)計排課系統(tǒng)，核心工作如下：(1) 編碼問題.本文給出的方法是，建立兩個向量，即課程向量和教師向量.課程向量以課程代號為編碼基本元素，課程代號的有序排列作為排課系統(tǒng)的一個既定方案，如{C1,C2,C3,…,Cm}代表m門課的一個排列次序，即一個課程向量.教師向量以教師編號為編碼基本元素，如{T1,T2,T3,…,Tn}，代表n位教師的一個排列次序，即一個教師向量.(2) 解碼方案.解碼的基本過程是，從課程向量中提取一門課，對應(yīng)位置選擇一位教師，從空閑教室中選擇一個教室.但上述解碼過程中，有可能存在非法編碼問題，如對應(yīng)的教師無法勝任所選的課程.此時，應(yīng)該融合修復(fù)方案，即選擇另外一個教師選擇這門課程.(3) 進(jìn)化策略.人工蜂群優(yōu)化的關(guān)鍵進(jìn)化過程主要取決于其局部搜索的過程，因而設(shè)計局部搜索策略對算法優(yōu)化的過程影響較大.針對上述兩向量編碼方式，主要考慮采用三種局部搜索算子，即交換(swap)、插入(insert)、逆轉(zhuǎn)(reverse).其中swap算子用于交換向量中任意選擇的兩個元素，insert用于把向量中任選的元素插入到不同的位置，reverse算子用于把向量中任選的兩個不同位置的全部元素逆序排列.通過上述操作算子，蜂群中的一個解變成另一個解，進(jìn)而更新并進(jìn)化尋優(yōu).(4) 精英保留策略.通過進(jìn)化，保留蜂群中最優(yōu)的個體，使得系統(tǒng)進(jìn)化朝理想的求解區(qū)域.(5) 跳出局部最優(yōu)能力.由于優(yōu)化算法的固有特性，往往無法跳出局部最優(yōu)，即算法搜索到一定階段后，易出現(xiàn)“早熟”的現(xiàn)象.針對這類問題，可以設(shè)計與禁忌搜索算法、模擬退火算法相結(jié)合的策略，進(jìn)而提高算法全局搜索的能力.

4.2 人工蜂群優(yōu)化在教學(xué)資源管理中的應(yīng)用

目前，各類教學(xué)資源呈爆炸式增長，如何在大數(shù)據(jù)時代搜索合適的教學(xué)資源，進(jìn)而更有利于教學(xué)開展，已經(jīng)成為當(dāng)前研究的熱點(diǎn).在大數(shù)據(jù)背景下，教學(xué)資源往往分布在各個節(jié)點(diǎn)，資源的分布性決定了資源共享需要考慮節(jié)點(diǎn)的分布性、資源的實(shí)時更新性、資源的有效性、資源的可用性，同時應(yīng)滿足用戶需求最大化、經(jīng)濟(jì)指標(biāo)最小化等目標(biāo)，是一個多約束、多目標(biāo)、動態(tài)的優(yōu)化過程.基于此，人工蜂群優(yōu)化適合于在教學(xué)資源共享、教學(xué)資源推薦等教學(xué)設(shè)計中應(yīng)用和推廣，搭建一種基于人工智能優(yōu)化算法的教學(xué)資源共享、推薦平臺，使得教學(xué)資源的使用、推薦過程實(shí)現(xiàn)自動化、智能化.

4.3 人工蜂群優(yōu)化在新工科建設(shè)中的應(yīng)用

新工科建設(shè)是工科類院校發(fā)展的方向，新工科建設(shè)特別強(qiáng)調(diào)學(xué)生的數(shù)據(jù)跟蹤，譬如，大學(xué)生在大學(xué)階段的課程成績跟蹤、畢業(yè)就業(yè)跟蹤等.設(shè)計一種自動跟蹤和優(yōu)化平臺，必定有力促進(jìn)新工科建設(shè).在云計算平臺下，采用Hadoop、Map/Reduce管理和存儲大數(shù)據(jù)，采用數(shù)據(jù)挖掘算法開展數(shù)據(jù)清洗、知識抽取及數(shù)據(jù)聚類，采用人工蜂群優(yōu)化算法進(jìn)行數(shù)據(jù)分析和優(yōu)化，采用可視化技術(shù)進(jìn)行數(shù)據(jù)展示，進(jìn)而實(shí)現(xiàn)一種大學(xué)生學(xué)業(yè)、畢業(yè)、就業(yè)等大數(shù)據(jù)自動化跟蹤平臺.

5 結(jié)束語

人工蜂群算法近年來得到了廣泛關(guān)注，在各個應(yīng)用領(lǐng)域證明了該算法的有效性.在今后的推廣和應(yīng)用中，應(yīng)注重以下幾個方面的研究：(1) 目前對人工蜂群算法的改進(jìn)，僅局限于針對連續(xù)優(yōu)化問題的改進(jìn).如何改進(jìn)ABC算法，使之更好地優(yōu)化離散問題，亟待有效解決；(2) 應(yīng)用ABC算法求解調(diào)度問題方面，如何結(jié)合問題特征，分析問題先驗(yàn)知識，設(shè)計自適應(yīng)的算法框架，尚待進(jìn)一步研究；(3) 針對離散優(yōu)化調(diào)度問題，如何結(jié)合實(shí)際生產(chǎn)約束尚缺乏綜合考慮，因而無法直接應(yīng)用于求解現(xiàn)實(shí)調(diào)度問題.結(jié)合實(shí)際生產(chǎn)約束，挖掘問題特征、約束條件、目標(biāo)特點(diǎn)，進(jìn)而設(shè)計適合問題的優(yōu)化算法框架，是進(jìn)一步研究的熱點(diǎn)；(4) 如何應(yīng)用人工蜂群算法，提高教學(xué)改革的效果是進(jìn)一步研究的熱點(diǎn).譬如，采用人工蜂群算法用于教學(xué)中的大數(shù)據(jù)分析、資源共享等.

[1] Karaboga D. An idea based on honey bee swarm for numerical optimization[R]. Technical Report TR06, Erciyes University, Engineering Faculty, Computer Engineering Department, 2005.

[2] Karaboga D, Basturk B. On the performance of artificial bee colony (ABC) algorithm[J]. Applied Soft Computing, 2008, 8(1): 687-697.

[3] Karaboga D, Akay B. A comparative study of artificial bee colony algorithm[J]. Applied Mathematics and Computation, 2009, 214(1): 108-132.

[4] Karaboga N. A new design method based on artificial bee colony algorithm for digital IIR filters[J]. Journal of the Franklin Institute, 2009, 346(4): 328-348.

[5] 習(xí)近平.將機(jī)器人和智能制造納入優(yōu)先重點(diǎn)領(lǐng)域[EB/OL]. http://news.sohu.com/20151124/n427789699.shtml.

[6] Rudolph G. Convergence analysis of canonical genetic algorithms[J]. IEEE Transactions on Neural Networks, 1994, 5(1): 96-101.

[7] 徐宗本. 計算智能中的仿生學(xué)理論與算法[M]. 北京: 科學(xué)出版社, 2003.

[8] Kang F, Li J, Xu Q. Structural inverse analysis by hybrid simplex artificial bee colony algorithms[J]. Computers & Structures, 2009, 87(13): 861-870.

[9] Alatas B. Chaotic bee colony algorithms for global numerical optimization[J]. Expert Systems with Applications, 2010, 37(8): 5 682-5 687.

[10] Omkar S N, Senthilnath J, Khandelwal R, et al. Artificial Bee Colony (ABC) for multi-objective design optimization of composite structures[J]. Applied Soft Computing, 2011, 11(1): 489-499.

[11] Karaboga D, Akay B. A modified artificial bee colony (ABC) algorithm for constrained optimization problems[J]. Applied Soft Computing, 2011, 11(3): 3 021-3 031.

[12] Akay B, Karaboga D. A modified artificial bee colony algorithm for real-parameter optimization[J]. Information Sciences, 2012, 192: 120-142.

[13] Banharnsakun A, Achalakul T, Sirinaovakul B. The best-so-far selection in artificial bee colony algorithm[J]. Applied Soft Computing, 2011, 11(2): 2 888-2 901.

[14] Karaboga D, Ozturk C. A novel clustering approach: Artificial Bee Colony (ABC) algorithm[J]. Applied Soft Computing, 2011, 11(1): 652-657.

[15] Shi Y J, Qu F Z, Chen W, et al. An artificial bee colony with random key for resource-constrained project scheduling[C].//Life System Modeling and Intelligent Computing. Springer Berlin Heidelberg, 2010: 148-157.

[17] Xu C, Duan H. Artificial bee colony (ABC) optimized edge potential function (EPF) approach to target recognition for low-altitude aircraft[J]. Pattern Recognition Letters, 2010, 31(13): 1 759-1 772.

[18] Xu C, Duan H, Liu F. Chaotic artificial bee colony approach to Uninhabited Combat Air Vehicle (UCAV) path planning[J]. Aerospace Science and Technology, 2010, 14(8): 535-541.

[19] Yeh W C, Hsieh T J. Solving reliability redundancy allocation problems using an artificial bee colony algorithm[J]. Computers & Operations Research, 2011, 38(11): 1 465-1 473.

[20] Cui Z, Gu X. An improved discrete artificial bee colony algorithm to minimize the makespan on hybrid flow shop problems[J]. Neurocomputing, 2015, 148: 248-259.

[21] Huang Y M, Lin J C. A new bee colony optimization algorithm with idle-time-based filtering scheme for open shop-scheduling problems[J]. Expert Systems with Applications, 2011, 38(5): 5 438-5 447.

[22] Pan Q K, Tasgetiren M F, Suganthan P N, et al. A discrete artificial bee colony algorithm for the lot-streaming flow shop scheduling problem[J]. Information Sciences, 2011, 181(12): 2 455-2 468.

[23] Sang H, Gao L, Pan Q. Discrete artificial bee colony algorithm for lot-streaming flowshop with total flowtime minimization[J]. Chinese Journal of Mechanical Engineering, 2012, 25(5): 990-1 000.

[24] Al-Salamah M. Constrained binary artificial bee colony to minimize the makespan for single machine batch processing with non-identical job sizes[J]. Applied Soft Computing, 2015, 29: 379-385.

[25] Li J Q, Pan Q K, Tasgetiren M F. A discrete artificial bee colony algorithm for the multi-objective flexible job-shop scheduling problem with maintenance activities[J]. Applied Mathematical Modelling, 2014, 38(3): 1 111-1 132.

[26] Li J Q, Pan Q K, Gao K Z. Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems[J]. The International Journal of Advanced Manufacturing Technology, 2011, 55(9-12): 1 159-1 169.

[27] Gao K Z, Suganthan P N, Chua T J, et al. A two-stage artificial bee colony algorithm scheduling flexible job-shop scheduling problem with new job insertion[J]. Expert Systems with Applications, 2015, 42(21): 7 652-7 663.

[28] 晏曉輝, 朱云龍, 張浩. 基于 MOABC/D 的銅板帶熔鑄作業(yè)調(diào)度優(yōu)化[J]. 計算機(jī)集成制造系統(tǒng), 2013, 19(10): 2 528-2 535.

[29] Sundar S, Suganthan P N, Jin C T, et al. A hybrid artificial bee colony algorithm for the job-shop scheduling problem with no-wait constraint[J]. Soft Computing, 2017, 21(5): 1 193-1 202.

[30] 江浩, 江兵. 基于改進(jìn)粒子群優(yōu)化算法的貝葉斯網(wǎng)絡(luò)結(jié)構(gòu)學(xué)習(xí)[J]. 聊城大學(xué)學(xué)報:自然科學(xué)版, 2015(1):83-87.

[31] 鄭亞強(qiáng). 基于布谷鳥搜索算法優(yōu)化的正交小波多模盲均衡算法[J]. 聊城大學(xué)學(xué)報:自然科學(xué)版, 2014, 27(1):102-106.

ResearchonArtificialBeeColonyAlgorithmandItsApplicationsinResourceManagement

LI Jun-qing1,2WANG Yong1SANG Hong-yan1GAO Kai-zhou1HAN Yu-yan1MENG Tao1

(1.School of Computer Science, Liaocheng University, Liaocheng 252059, China； 2.School of Information Science and Engineering, Shandong Normal University, Jinan 250014,China)

During recent years, varieties of intelligent optimization algorithms have been developed and applied in many types of areas. As one of the modern intelligent optimization algorithm, the canonical artificial bee colony has also been proposed and applied in many industrial and manufactural fields, such as the iron-steel production scheduling problem, the supply chain optimization problem, and the traffic problems. In this study, firstly, the canonical artificial bee colony algorithm was described, and then the convergence ability was analyzed. Lastly, the applications of the artificial bee colony algorithm were classified and summarized. Lastly, the application of artificial bee colony algorithm in the instructional design is discussed, and which will propose the development of the artificial intelligence in the education reformation.

artificial bee colony algorithm,intelligent optimization algorithm,convergence ability,instructional design.

2017-05-20

國家自然科學(xué)基金項(xiàng)目(61773192)資助

李俊青,E-mail:1141231492@qq.com.

TP 391.4

A

1672-6634(2017)03-0083-05