Abstract: Rectangular packing problem is a typical NP-Hard problem,the solution time will increase exponentially with increasing of parts' number.To reduce the computing time of similar tasks and improve the optimization performance and material utilization,combined with the lowest skyline search algorithm based on fitness evaluation factor,a novel ants reinforcement learning algorithm based on knowledge transfer was proposed for rectangular packing problem.Aiming at the high-dimensional knowledge space,this algorithm constructed a high-dimensional space combination matrix based on knowledge extension.With the help of “trial-and-error” learning mode of reinforcement learning,the algorithm acquired and updated knowledge in the knowledge matrix by using ant colony with self-learning ability.The knowledge acquired by pre-learning was transferred to the target task by linear transfer strategy,which helped the new task make decisions quickly online.Simulation result showed that the proposed algorithm could obtain a higher quality solution at the speed of 2-6 times faster than other intelligent algorithm,which was very suitable in solving large and medium-scale rectangular packing problem.

Key words: rectangular packing problem, ant colony algorithm, reinforcement learning, knowledge transfer

摘要： 矩形排样是典型的NP-Hard问题,当零件数量增加时,求解时间便会呈指数倍急剧增长。为缩减相似排样任务的计算时间,提高寻优性能与材料利用率,结合基于匹配度评价的最低水平线算法,提出基于知识迁移的蚁群强化学习算法,以解决矩形排样问题。该算法针对高维知识空间,构建基于知识延伸的高维空间合并矩阵,并借助强化学习“试错”学习模式,在知识矩阵中利用有自学习能力的蚁群完成知识的获取与更新。而后将“预学习”获得的知识利用线性迁移策略迁移给目标任务,指导其在线快速做出决策。通过算例仿真表明：该算法能获得较高质量的解,同时寻优速度达到其他智能算法的2~6倍,在求解大中规模矩形排样问题上具有较好的实用性。

关键词: 矩形排样, 蚁群算法, 强化学习, 知识迁移