Intelligent Optimization Algorithms For Solving The Weighted Circles Packing Problem

With the engineering background of the very large scale integrated (VLSI)circuit layout design and the placement of factory machinery and equipment, this article studies the weighted circles packing (WCP) problem. WCP problem is a kind of NP-hard problem. The aim of the WCP problem is to find a feasible layout, which should satisfy the following requirements: 1) the sum of weighed distances of n circular objects as small as possible; 2) the area of envelope container of n circular objects as small as possible; 3) without any overlapping area among circular objects and between each of the circular objects and the envelope container. This article use linear weighting method and multi-objective method to solve the WCP problem,respectively. Detailed description and the research results of this article are as follows:(1) Study a new single-objective algorithm for WCP problem. In this article, we put forward a heuristic quasi-physical algorithm with coarse and fine adjustment based on dichotomy method (HQPA-CFDM) to solve it. Based on linear weighting method, we convert the problem into an unconstrained optimization problem, and build a relevant mathematical model of 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, the process of quasi-physical algorithm is divided into two phases: coarse adjustment and fine adjustment. In the quasi-physical algorithm, an alterable strategy of elastic coefficient is proposed. In addition, an off-trap strategy for jump out of local minima is 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.(2) Study a new multi-objective algorithm for WCP problem. In this article, we propose a multi-objective configuration space evolutionary algorithm (MOCSEA) to solve it. Based on quasi-physical strategy and the penalty function method, we convert the problem into an unconstrained multi-objective optimization problem, and build a corresponding mathematical model of it. Starting from an initial configuration bank (i.e., population), we adopt an adaptive step length gradient method with early termination strategy (GD) to legitimate the configuration (i.e.,individual) of the initial configuration bank. Afterwards, we use some evolutionary operations to form an evolutionary configuration bank, including select operation,crossover operation and mutate operation. In the period of evolution, the select operation uses elitist strategy, the crossover operation adopt single-point crossover and multi-point crossover,and the mutate operation employs heuristic mutation strategy. At this time, we adopt GD to legitimate the evolutionary configuration bank.In addition, an optimal individual selection method for selecting some excellent individuals from evolutionary configuration bank and an updating mechanism of configuration for updating the initial configuration bank are put forward. By using fast non-dominated sorting method, a set of Pareto optimal solutions are obtained after updating the initial configuration bank in many times. By computing three typical examples in the literature, the numerical experiments show that MOCSEA has a better performance.