王金敏， 朱丽苹， 甄士刚

(1. 天津市高速切削与精密加工重点实验室，天津 300222；2. 天津职业技术师范大学机械工程学院，天津 300222)

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

王金敏1,2， 朱丽苹2， 甄士刚2

(1. 天津市高速切削与精密加工重点实验室，天津 300222；2. 天津职业技术师范大学机械工程学院，天津 300222)

三维矩形布局问题属于NP难问题，对于三维矩形布局问题的求解大多依赖于各种启发式算法。该文以布局物体体积递减为定序规则，结合布局物体在布局空间中的几何可行域，以吸引子法为定位规则，利用蜜蜂进化型遗传算法优化吸引子函数中的参数来求解三维矩形布局问题(BEGA)，得到新型布局遗传算法。最后对不同的算例进行了计算，并与以标准比例选择作为选择算子的传统布局遗传算法(SPGA)等对比证明了该算法的有效性。

布局问题；启发式算法；吸引子；蜜蜂进化

布局问题[1-2]广泛存在于生产生活实际中，如运输、下料、剪裁、排版等。解决好布局问题无疑具有巨大的现实意义。布局问题可以定义为给定布局空间和若干布局物体，将布局物体合理地布置到布局空间中并满足某种最优指标。这些指标通常是使布局空间利用率最大、布局成本最小等。学术界已经证明布局问题属于非确定多项式(non-deterministic polynomial，NP)难问题。对于NP难问题，普通的精确性求解算法难以建立合适的数学模型及找到问题的全局最优解，因此长期以来大多布局问题的求解依赖于各种启发式算法。……