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

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