A heuristic quasi-physical algorithm with coarse and fine adjustment for multi-objective weighted circles packing problem. (November 2016)

• Record Type: Journal Article
• Authors: Liu, Jingfa; Zhang, Kewang; Yao, Yonglei; Xue, Yu; Guan, Tinzhao
• Is Part Of: Computers & industrial engineering. Volume 101(2016)
• Page Start: 416
• Page End: 426
• Publication Date: 2016-11
• Subjects: Weighted circles packing problem -- Coarse and fine adjustment -- Heuristic -- Quasi-physical algorithm -- Multi-objective optimization -- Non-dominated sorting; Engineering -- Data processing -- Periodicals; Industrial engineering -- Periodicals; 620.00285
• DOI: 10.1016/j.cie.2016.09.029
• Languages: English
• ISSNs: 0360-8352

Abstract

Highlights: The problem is converted into an unconstrained optimization problem by the quasi-physical strategy. A feasible solution of the problem is obtained by heuristic quasi-physical algorithm with coarse and fine adjustment. In the coarse adjustment we put forward an alterable elastic coefficient. The fast non-dominated sorting approach is used to determine the Pareto optimal solutions of the problem. Abstract: 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.