一种基于蜜蜂进化选择算子的布局遗传算法  

A Genetic Algorithm for Packing Problems Based on Bee Evolutionary Selection Operator

作　　者：王金敏[1,2] 朱丽苹[2] 甄士刚 

机构地区：[1]天津市高速切削与精密加工重点实验室,天津300222 [2]天津职业技术师范大学机械工程学院,天津300222

出　　处：《图学学报》2014年第5期690-696,共7页Journal of Graphics

基　　金：国家自然科学基金资助项目(60975046)

摘　　要：三维矩形布局问题属于NP难问题,对于三维矩形布局问题的求解大多依赖于各种启发式算法。该文以布局物体体积递减为定序规则,结合布局物体在布局空间中的几何可行域,以吸引子法为定位规则,利用蜜蜂进化型遗传算法优化吸引子函数中的参数来求解三维矩形布局问题(BEGA),得到新型布局遗传算法。最后对不同的算例进行了计算,并与以标准比例选择作为选择算子的传统布局遗传算法(SPGA)等对比证明了该算法的有效性。Three dimensional rectangular packing is a NP-hard problem,which is often solved by heuristic algorithms.In this paper the sequencing rules is determined by the volume of packing items,the positioning rules are determined by attractor function with the geometry feasible region of packing items in packing space.Then the parameters in the attractor function are optimized by bee evolution genetic algorithm （BEGA）,the new packing genetic algorithm is formed.Finally,different benchmarks are carried out,and the paper proves the validity of the algorithm by comparing with the traditional packing genetic algorithm （SPGA） which chooses the standard proportional selection as its operator,etc.

关 键 词：布局问题 启发式算法 吸引子 蜜蜂进化 

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