Abstract: To explore more efficient methods for two-dimensional irregular packing problem,an Improved Real-Coded Quantum Evolutionary Algorithm (IRCQEA) was presented.The placement strategy for finding the optimal nesting position with the lowest center of gravity based on No Fit Polygon (NFP) was proposed,and a mathematical model was established with maximum material utilization as optimization objective.The coding method and solution generation mode for real probability amplitude were designed based on packing number list and rotation angle index list.New quantum observation could directly obtain the solution in this algorithm.The quantum update was carried out by means of self-adaptive mode and the heuristic algorithm was constructed to generate initial populations of packing list,which were utilized to guarantee the feasibility of the solution in time and quality.The simulation results and the comparative experiments on classic benchmarks demonstrated the feasibility and effectiveness of the presented IRCQEA.

Key words: irregular packing problem, no fit polygon, heuristic algorithm, real-coded, quantum-inspired evolutionary algorithm

摘要： 为探索更高效的二维不规则多边形排样方法,提出一种改进的实数编码量子进化算法。设计了基于临界多边形的按照排样件最低形心位置进行布局的放置策略,并建立了以最大化材料利用率为优化目标的数学模型;设计了基于排样编号序列和旋转角索引序列的实数几率幅值编码方法及解生成方式,通过量子观测操作直接生成问题解,使其解码效率较高;算法通过自适应调节方式进行量子更新,采用启发式算法生成排样序列初始种群,以保证解在时间和质量上的可行性。通过基准算例仿真和算法对比实验,验证了所提算法的可行性和有效性。

关键词: 不规则排样问题, 临界多边形, 启发式算法, 实数编码, 量子进化算法