一种求解Packing问题概率控制搜索行为的启发式算法  

A heuristic algorithm for packing problems:searching behaviors controlled by probability

作　　者：胡清华[1] 孙治国[1] 邓四二[1,2] 滕弘飞[1] 

机构地区：[1]大连理工大学机械工程学院,辽宁大连116024 [2]河南科技大学机电工程学院,河南洛阳471003

出　　处：《大连理工大学学报》2009年第1期71-76,共6页Journal of Dalian University of Technology

基　　金：国家自然科学基金资助项目(50575031);国家“十一五”科技攻关资助项目(JPPT-115-189)

摘　　要：研究一种求解圆形和圆形与矩形混合Packing问题的启发式算法.借鉴Agent概念,赋予待布物具有跳跃、交换、旋转、移动和容器缩放等5种搜索行为,在寻优过程中以概率机制控制上述各搜索行为,并给出寻优过程中启用该搜索行为的时机及其操作顺序,该概率控制机制的适应性控制参数由待布物之间干涉信息决定.该法纯用上述搜索行为寻优,不辅以其他优化方法.该Packing问题数值实验结果表明,算法是可行和有效的.A heuristic algorithm is developed for circle packing problem or circle rectangular mixed packing problem. Using the concept of Agent for reference, the objects （circles and rectangles） are endowed with the searching behaviors to jump, swap, rotate and move within layout space. A probability-based mechanism is introduced for controlling these different behaviors. Application time and order of these behaviors are presented. The probability parameters are determined by overlapping area among objects. This algorithm only uses these behaviors without other optimization algorithms. The numerical experiments on the test problems have proved that the algorithm is feasible and effective.

关 键 词：圆形与矩形Packing问题 启发式算法 搜索行为 概率控制机制 

分 类 号：TP391.72[自动化与计算机技术—计算机应用技术]