|
|
论文:2014,Vol:32,Issue(2):240-245 |
|
|
引用本文： |
|
|
王鹏, 黄帅, 朱舟全. 求解带平衡约束圆形packing问题的改进人工蜂群算法[J]. 西北工业大学 |
|
|
Wang Peng, Huang Shuai, Zhu Zhouquan. Exploring Improved Artificial Bee Colony Algorithm for Solving Circle Packing Problem with Equilibrium Constraints[J]. Northwestern polytechnical university |
|
|
|
|
|
|
|
| 求解带平衡约束圆形packing问题的改进人工蜂群算法 |
|
| 王鹏, 黄帅, 朱舟全 |
|
| 西北工业大学 航海学院, 陕西 西安 710072 |
| 摘要: |
| 圆形packing问题是一个著名的NP难题,求解该问题具有很高的理论与实用价值。首先将趋势外推原理和微调算子引入人工蜂群算法,对其搜索的随机性进行有效的引导优化,然后将改进后的人工蜂群算法应用于带平衡约束的圆形布局的参数优化,并在文后采用3个典型实例进行了数值实验。结果表明新算法解决带平衡约束的圆形packing问题具有较强的寻优能力和较高的寻优效率,是一种实用的方法。 |
| 关键词:
约束圆形布局问题
人工蜂群算法
布局优化
启发式算法
|
|
| Exploring Improved Artificial Bee Colony Algorithm for Solving Circle Packing Problem with Equilibrium Constraints |
|
| Wang Peng, Huang Shuai, Zhu Zhouquan |
|
| College of Marine Engineering, Northwestern Polytechnical University, Xi'an 710072, China |
| Abstract: |
| As is well-known, it is difficult to solve a circle packing problem with equilibrium constraints. Therefore we aim to find a new algorithm that can further enhance search capability, efficiency and success rate. To solve the circle packing problem, we propose an improved artificial bee colony (IABC) algorithm by introducing the trend extrapolation and a fine-tuning operator into the artificial bee colony so as to reduce its randomness in the search process and improve its search efficiency. The IABC algorithm uses different adaptability degrees of food sources at different places to produce the direction of trend extrapolation and direct the search, thus reducing its randomness. To verify the effectiveness of the IABC algorithm, we apply it to solving the circle packing problem with equilibrium constraints and simulate it with the MATLAB software. The simulation results, given in Figs. 4, 5 and 6 and Tables 3 and 4, and their analysis show preliminarily that our IABC algorithm has better search capability and efficiency than both the genetic algorithm and the particle swarm optimization (PSO) algorithm. The IABC algorithm can find optimal solutions quickly without taking much computing time, indicating its efficiency in solving a circle packing problem with equilibrium constraints. |
| Key words:
algorithms
constrained optimization
efficiency
heuristic algorithms
MATLAB
particle swarm optimization (PSO)
circle packing problem with equilibrium constraints
improved artificial bee colony (IABC) algorithm
|
|
| 收稿日期: 2013-04-11
修回日期:
|
| DOI: |
| 基金项目: 国家自然科学基金(51375389)资助 |
| 通讯作者:
Email： |
| 作者简介: 王鹏(1978-),西北工业大学副教授,主要从事水下航行器总体设计及多学科优化设计研究。
|
|
| 相关功能 |
|
|
|
|
| 作者相关文章 |
|
| 王鹏 在本刊中的所有文章 |
| 黄帅 在本刊中的所有文章 |
| 朱舟全 在本刊中的所有文章 |
|
|
|
|
|
|
|
|
参考文献: |
|
|
[1] Dowaland K A, Dowaland W B. Packing Problems[J]. European Journal of Operational Research, 1992, 56(01): 2-14
[2] Andrea Lodi, Silvano Martello. Two-Dimensional Packing Problems: A Survey[J].European Journal of Operational Research,2002, 141(2): 241-252
[3] M hand Hifi, Rym M Hallah. A Literature Review on Circle and Sphere P acking P roblems: Models and Methodologies[J]. Advances in Operations Research, 2009(1): 1-22
[4] Blum C, Roli A. Meta-Heuristics in Combinatorial Optimization: Overview and Conceptual Comparison. ACM Computing Survey, 2003, 35(3): 268-308
[5] 唐飞, 滕弘飞. 一种改进的遗传算法及其在布局优化中的应用[J]. 软件学报, 1999, 10(10): 1096-1102 Tang Fei, Teng Hongfei. A Modified Genetic Algorithm and Its Application to Layout Optimization[J]. Journal of Software,1999, 10(10): 1096-1102 (in Chinese)
[6] Ignacio Castillo, Frank J Kampas. Solving Circle Packing Problems by Global Optimization: Numerical Results and Industrial Applications [J]. European Journal of Operational Research, 2008, 191, 786-802
[7] 钱志勤, 滕弘飞, 孙治国. 人机交互的遗传算法及其在约束布局优化中的应用[J]. 计算机学报, 2001, 24(5): 553-559 Qian Zhiqin, Teng Hongfei, Sun Zhiguo. Human-Computer Interactive Genetic Algorithm and Its Application to Constrained Layout Optimization [J]. Chinese Journal of Computers, 2001, 24(5): 553-559 (in Chinese)
[8] Teng H F, Sun S L, Ge W H, et al. Layout Optimization for Dishes Installed on a Rotating Circular Table —The Packing Problem with Equilibrium Behavioral Constraints [J]. Science in China (Series A), 1994, 37(12): 1272-1280 |
|
|
|
|
|
|
|
