关键词: 约束布局问题, 定位定序, 量子进化算法, 启发式方法, 禁忌策略

Abstract: To solve the prematurity of evolutionary algorithm on the equilibrium constrained circles packing problem, the Multi-Quantum States Quantum-Inspired Evolutionary Algorithm (MQSQIEA) proposed in this paper was beneficial to keeping the population diversity, which combined the heuristics based on the order-based positioning technique. The layout sequence was optimized efficiently by MQSQIEA. The solving speed was improved by the multi-quantum states coding and the convergence criterion based on the average convergence probability. The observation method based on the taboo strategy and heuristic information was introduced to obtain the n-ary solution with different integers and ensure the priority to place circles with large mass and long radius. The dynamic quantum evolutionary strategy was applied to guide the population to evolve towards the best individual. The positioning probability function introduced to the positioning rule was employed to improve the solution quality. The numerical experimental results show that the proposed method can effectively solve the circular packing problem with equilibrium constraints.

Key words: constrained packing problem, order-based positioning, Quantum-Inspired Evolutionary Algorithm （QIEA）, heuristic method, tabu strategy