A heuristic quasi-physical algorithm with coarse and fine adjustment for multi-objective weighted circles packing problem

作者：Liu, Jingfa; Zhang, Kewang^*; Yao, Yonglei; Xue, Yu; Guan, Tinzhao

来源：Computers & Industrial Engineering, 2016, 101: 416-426.

DOI：10.1016/j.cie.2016.09.029

• Weighted circles packing problem
• Coarse and fine adjustment
• Heuristic
• Quasi-physical algorithm
• Multi-objective optimization
• Non-dominated sorting

The weighted circles packing problem is a kind of multi-objective optimization problem with constraints and NP-hard problem in math. Based on quasi-physical strategy and the penalty function method, we convert the problem into an unconstrained optimization problem, and propose a heuristic quasi physical algorithm with coarse and fine adjustment based on dichotomy method (HQPA-CFDM) to solve it: Starting from any initial configuration, we use dichotomy method to form an envelope container, and employ the quasi-physical algorithm to optimize total potential energy of the current configuration. To find a feasible solution quickly, inspired by the coarse-to-fine control strategy in the manufacture industry, we divide the process of quasi-physical algorithm into two phases: coarse adjustment and fine adjustment. In addition, an alterable strategy of elastic coefficient and an off-trap strategy for jump out of local minima are put forward. Three typical examples in the literature are employed for verifying the proposed algorithm, and the numerical experiments show that HQPA-CFDM has refreshed the current best results of all typical examples. According to statistics and analysis of experimental results, the proposed algorithm has a stable performance.

• 出版日期2016-11
• 单位南京信息工程大学