Fuzzy Artificial Bees Colony Algorithm for Solving Multi-choice Multidimensional Knapsack Problem

Operations Research and Management Science ›› 2013, Vol. 22 ›› Issue (5): 98-103.

• Theory Analysis and Methodology Study • Previous Articles Next Articles

Fuzzy Artificial Bees Colony Algorithm for Solving Multi-choice Multidimensional Knapsack Problem

LIU Yin¹, MA Liang¹, HUANG Yu²

1. Business School, University of Shanghai for Science and Technology, Shanghai 200093, China;
2. School of Communication and Art Design, University of Shanghai for Science and Technology, Shanghai 200093, China

Received:2012-10-23 Online:2013-10-25

模糊人工蜂群算法的多选择多维背包问题求解

柳寅¹, 马良¹, 黄钰²

1.上海理工大学管理学院,上海 200093;
2.上海理工大学出版印刷与艺术设计学院,上海 200093

作者简介:柳寅(1986-),男,博士研究生,研究方向:智能优化;马良(1964-),男,教授,研究方向:智能优化;黄钰(1988-),女,硕士,研究方向:教育经济。
基金资助:
国家自然科学基金资助项目(70871081);上海市重点学科建设资助项目 (S30504);上海市研究生创新基金资助项目 (JWCXSL1201 )

Abstract

Abstract: Aiming at the premature convergence problem in traditional artificial bees colony algorithm, fuzzy artificial bees colony algorithm is proposed, which is based on the principles of fuzzy processing and bees colony behavior. Fuzzy inputs and fuzzy outputs are introduced into the algorithm to maintain dynamic updates of the nectar access probability. According to effective adjustment on nectar access probability during the different stages of algorithm calculation, the algorithm avoids local optima. Simulated tests of multi-choice multidimensional knapsack problem and comparisons with other algorithms show the algorithm is feasible and effective and the algorithm has strong global optimization ability.

Key words: intelligent optimization algorithm, fuzzy rules, fuzzy artificial bees colony algorithm, multi-choice multidimensional knapsack problem

摘要： 针对传统人工蜂群算法早熟收敛问题,基于模糊化处理和蜂群寻优的特点,提出一种模糊人工蜂群算法。将模糊输入输出机制引入到算法中来保持蜜源访问概率的动态更新。根据算法计算过程中的不同阶段对蜜源访问概率有效调整,避免算法陷入局部极值。通过对多选择多维背包问题的仿真实验和与其他算法的比较,表明本算法可行有效,有良好的鲁棒性。

关键词: 智能优化算法, 模糊规则, 模糊人工蜂群算法, 多选择多维背包问题

CLC Number:

211.1

LIU Yin, MA Liang, HUANG Yu. Fuzzy Artificial Bees Colony Algorithm for Solving Multi-choice Multidimensional Knapsack Problem[J]. Operations Research and Management Science, 2013, 22(5): 98-103.

柳寅, 马良, 黄钰. 模糊人工蜂群算法的多选择多维背包问题求解[J]. 运筹与管理, 2013, 22(5): 98-103.

References

[1] Freville A. The multidimensional 0-1 knapsack problem: an overview[J]. European J of Operational Research, 2004, 155(9): 1-21.
[2] Karaboga D. An idea based on honey Bee swarm for numerical optimization[R]. Technical Report-TR06, Erciyes University, 2005.
[3] Bonabeau E, Dorigo M, Theraulaz G. Swarm intelligence: fromnatural to artificial systems[M]. New York: Oxford University Press, 1999.
[4] Bitam S, Batouche M, Talbi E. A survey on bee colony algorithms[C]. 2011 IEEE International Symposium on Parallel & Distributed Processing, Workshops and PhdForum, 2010: 1-8.
[5] 刘勇,马良.函数优化的蜂群算法[J].控制与决策,2012,27(6):886-890.
[6] 杨进,马良.蜂群优化算法在带软时间窗的车辆路径问题中的应用[J].预测,2010,29(6):67-69.
[7] 肖永豪,余卫宇.基于蜂群算法的图像边缘检测[J].计算机应用研究,2010, 27(7):2748-2750.
[8] 罗彬,邵培基等.基于粗糙集理论-神经网络-蜂群算法集成的客户流失研究[J].管理学报,2011,8(2):265-271.
[9] Kovacic Z, Bogdan S. Fuzzy controller design: theory and applications[M]. Boca Raton: CRC Press Inc, 2006.
[10] 胡珂,李迅波等.改进的人工蜂群算法性能[J].计算机应用,2011,31(4):1107-1110.
[11] 王湘中,喻寿益等.一种强引导型遗传算法[J].控制与决策,2004,19(7):705 -798.
[12] Moser M, Jokanovic D P, Shiratori N. An algorithmfor the multidimesional multiple-choice knapsack problem[J]. IEICE Trans on Fundamentals Electron, 1997, 80(3): 582-589.
[13] Khan S, Li K F, Manning E G. Solving the knapsack problem for adaptive multimedia systems[J]. Stud Inform, 2002, 2(1): 154-174.
[14] 马良,朱刚,宁爱兵.蚂蚁优化算法[M].北京:科学出版社,2008.
[15] 张晓霞,唐立新.一种新的求解MMKP问题的ACO&PR算法[J].控制与决策,2009,24(5):729-733.
[16] 韩燕燕,马良等.多选择背包问题的人工蜂群算法[J].计算机应用研究,2012,29(3):862-864.

Fuzzy Artificial Bees Colony Algorithm for Solving Multi-choice Multidimensional Knapsack Problem

模糊人工蜂群算法的多选择多维背包问题求解

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 3

Recommended Articles

Metrics

[1]	DU Jian, ZHAO Xu, WANG Jun, ZHAO Yuan. Feeder Liner Network Design Model Considering Schedule Reliability [J]. Operations Research and Management Science, 2018, 27(7): 122-132.
[2]	QIN Lu, LIU Hong-chao, SUN Zhi-yuan. Optimization Method of Passenger Vehicle Transportation Network Based on Orthogonal Experimental [J]. Operations Research and Management Science, 2018, 27(12): 38-46.
[3]	YANG Hong-mei. The Application of Set Pair Analysis in Fuzzy Rule Extraction of Domestic Economy Growth [J]. Operations Research and Management Science, 2013, 22(3): 194-200.