Research On Evolutionary Algorithm With Heuristic Strategy For Weighted Circles Layout Problem

Layout problem with performance constraints (PCLP problem) has widespread application background, for example, cutting plates of iron and steel plate enterprise (the maximum product rate constraint), the layout design of printed circuit board (PCB)(the minimal the sum of weighted distance product constraint), the layout scheme design of spacecraft cabin (the minimal unbalance constraint) and machine equipment layout in factory (minimum freight cost constraint) etc..2-dimensional PCLP problems discussed currently include the weighted layout problem and layout problem with equilibrium constraints and so on. This paper studies the former. Because weighted layout problem is a NP-hard combinatorial optimization problem, it is very difficult to be solved in polynomial time. Thus scholars have been studying it deeply, and proposed many effective algorithms such as heuristic and evolutionary algorithm etc. But both the solving accuracy and computational efficiency for the layout problem are expected to be improved, especially for large scale layout problem. Therefore, weighted circle layout problem is studied in this paper and some effective mechanisms and algorithms are proposed. The main work is as follows:1. For weighted circles layout problem, a heuristic mechanism and algorithm is proposed in this paper. According to the known information of the problem itself, the layout knowledge is got, and heuristic ordering and locating rules are established based on the knowledge. The roulette selection of the ordering rule is to take the circles radius and the row vector norm of the weight matrix as the probability factor and calculate the placed order of the circle objects; use external counter-clockwise location rule to locate the circles. This heuristic algorithm is able to construct layout scheme which outside enveloping rectangle area is smaller quickly, and it has low computational complexity.2. For weighted circles layout problem, an ant colony layout optimization mechanism and algorithm is proposed by combing the proposed heuristic strategy with ant colony algorithm. The experimental results show that the calculation accuracy of the proposed algorithm is higher than the existing algorithms.3. For weighted circles layout problem, a particle swarm optimization algorithm with quasi-human strategy is put forward. The mechanism is that the better solution constructed by heuristic algorithm is further optimized through particle swarm local optimization algorithm to attain the optimal solution. The numerical experimental results show that both the computational efficiency and the solving accuracy of the proposed algorithm are significantly improved compared to the existing algorithms. This paper discusses the weighted circles layout problem taking printed circuit board layout and place machines of workshop as study background. The information of the layout problem itself is used in the proposed optimize algorithm for solving the layout problem. A heuristic algorithm is proposed at first, then heuristic ant algorithm and quasi-human particle swarm optimization algorithm is explored. They are able to solve two-dimensional weighted circles layout problem effectively. Finally, author hope the proposed approach will be spread and applied to other similar layout problems.