A Quasi-physical And Quasi-human Algorithm For Solving The Circle Packing With Equilibrium Constraints Problem

The circles packing problem (CPP) is a typical NP-hard problem with largecomputational complexity, which has broad applications such wireless communication,aerospace, transportation, etc. Due to the objective difficulty of the problem, the exactalgorithms with long computation time are not appropriate for the practical application.Thus, the researches usually use heuristic methods for solving this problem. Thequasi-physical method looks for physical phenomena equivalent to the original problem inthe natural world, and then gets inspiration and designs efficient algorithms. The circlepacking with equilibrium constraints problem (CPECP) is an important extension of theCPP by introducing the static equilibrium. It is a global optimization problem with thebackground of satellite module layout design.After a thorough analysis of the problem, two quasi-physical models are introducedbase on the quasi-physical method. By combining these two models, the three constraints ofthe problem are converted into a single-objective optimization function. In the local searchprocess, some new strategies of quasi-physical descent are proposed as the integration ofthe quasi-physical and quasi-human method, which effectively improves the global searchability and local search speed of the algorithm. The concept of ‘action space’ in solving therectangular packing problem is used when the calculation falls into a local minimum trap.By squaring the circle, a new basin hopping method based on action space is proposed tolead the calculation jump out of current basin and move to promising areas. The taboostrategy is adopted to avoid repeating search for the same areas. A quasi-physical algorithmbased on action space (QPAS) is finally introduced by combining the improvedquasi-physical method and basin hopping strategy.Experiments based on two sets of11representative test instances. The computationalresults show that QPAS has a good performance in radius of container, accuracy andcomputation time. In addition, two sets of CPP instances are reformed into34CPECPinstances to further test QPAS.