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

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