The Quasi-physical Optimization Approach Research Using Wang-Landau Sampling For Weighted Circles Packing Problem

Weighted layout problem is a complex multi-objective layout problem which takes VLSI layout design as research background.The layout problem of cylinders and cuboids with performance constraints is a complex multi-objective problem,which takes the layout design of spacecraft cabin as research background.Due to a high-dimensional real solution space and two conflicted objectives,it is very difficult to solve.For the packing schemes of above problems,it is not only required that there is not overlap area between any two objects and its space utilization is as high as possible,but also is required satisfying the given performance constraints.In this paper,the problem of weighted circles layout is studied by support of the National Science Foundation(Project: Research on Theory and Approach of Divide-conquer and Stepwise Optimization for Two Types of Layout Problems with Performance constraints,No: 61272294).So far,the domestic and foreign experts put forward many effective algorithms,such as heuristic algorithms,evolutionary algorithms,interactive algorithms and their variations so on,but it is still needs to further improve the solution accuracy.Based on the elastic potential energy in physics,this paper proposes an optimization mechanism and approach of two-stage solution by combining the adaptive gradient method with Wang_Landau sampling mechanism and the construction of non-isomorphic layout pattern,whose main innovations are as follows:1.For weighted circles layout problem of the rectangular container,the elastic potential energy function of the system is constructed.After the size of a rectangular container is estimated,embedding degrees between circles and between the rectangular container and circle are defined.Then based on two embedding degree definitions,the elastic potential energy function of the system is constructed.2.For weighted circles layout problem of rectangular container,this paper proposes a two-stage adaptive quasi-physical gradient optimization method.In the first stage,the energy function is a linear function of the elastic potential energy and the weight distance,and the adaptive step is used.SO,the convergence speed of the proposed approach by improved.The idea is that the sum of weight distances is a part of the elastic potential energy,the every circle is considered as a "magnetic" ball,the gravitation between two balls is determined by a given weight matrix.So,through the gradient iteration,the system is optimized toward the desired goal.In the second stage,the quasi-feasible solution is adjusted into a feasible solution without any overlap area.The Experiment results show that the proposed algorithm has related less the sum of weighted distances and more compact packing scheme.3.For weighted circles layout problem of rectangular container,a two-stage global optimization algorithm based on Wang_Landau sampling is proposed.By constructing non isomorphic layout pattern and WL sampling the global search ability and stability of the proposed algorithm is improved.Numerical experiments show the feasibility,effectiveness and stability of the proposed algorithm.Taking VLSI layout design as the research background,a two-stage optimization algorithm is proposed based on the known information of the given mathematical model.And through the WL sampling,the global sampling ability is improved so that both the sum of the weighted distance and the envelope area are optimized.The results show that both the accuracies of the sum of the weighted distance and the envelope area are better than that of the existing algorithms,respectively.It is hoped that the proposed algorithm can provide reference for designers.