Study On Quasi-physical And Quasi-human Algorithm For Circle And Rectangle Orthogonal Packing Problem With Equilibrium Constraints

To solve the layout design problem of satellite module (SMLD) which belongs to3Dcombinatorial optimization problem with performance constraints, it is necessary tosimplify all components into some cylinders and cuboids. If each of the components of thesatellite module is vertically placed on the corresponding bearing plate, this problem will beconverted into the2D circle and rectangle packing problem with performance constraints.For the circular container with fixed volume, the aim of SMLD is to minimize the radius ofthe outside envelope circle of layout system as small as possible and satisfy the geometricconstraints and equilibrium constraints of the layout system. By so far, many scholars athome or abroad have proposed many effective algorithms including heuristic algorithms(e.g. quasi-physical and quasi-human algorithm), evolutionary algorithms (e.g. geneticalgorithm, particle swarm optimization and ant colony algorithm), cooperation algorithmsand human-machine interactive algorithms. However, it still needs to be further studied thepower approach owing to some deficiencies for them. Quasi-physical and Quasi-humanalgorithm is a kind of known algorithm for circle layout problem. But it is difficult to solvethe rectangle layout problem with performance constraints and the circle and rectanglelayout problem with performance constraints. In addition, the performance of evolutionalgorithms still need to further improved.In order to break through the bottleneck of SMLD (interference quantity calculationproblem), our research group devotes ourselves to explore more effective the mechanismand methods to solve the rectangle layout problem with equilibrium constraints, supportedby a grant from the National Natural Science Foundation (61272294), Natural ScienceFoundation of Hunan Province (11JJ6050) and Research Foundation of Education Bureauof Hunan Province (11A120). This paper puts forward a kind of the quasi-physical andquasi-human algorithm for the rectangle orthogonal packing problem with equilibriumconstraints through further studying SMLD. In addition, applying quasi-physical andquasi-human algorithm into the circle and rectangle layout problem, we present a kind ofdivide-conquer quasi-physical quasi-human algorithm for circle and rectangle orthogonalpacking problem with the equilibrium constraints. The main innovations of this paper are asfollows:For orthogonal rectangle packing problem with equilibrium constraints, aquasi-physical quasi-human algorithm is proposed. Two consecutive and monotonedecreasing embedding degree function between the two orthogonal rectangular and betweenorthogonal rectangular and the container, are defined and testified. Then the algorithm is applied to evaluate operation. The numerical experiments results show that the performanceof the algorithm is better than that of the existing algorithm.For circle and rectangle orthogonal packing problems with equilibrium constraint, thispaper puts forward a divide-conquer quasi-physical quasi-human algorithm for the circleand rectangle orthogonal packing problem with the equilibrium constraints. After randomlygenerating a layout solution for a circle container with the given radius, then a feasiblesolution is searched through quasi-physical quasi-human algorithm and its mass center andthe outer envelope radius are calculated. If the outer envelope radius is less than thethreshold, then the satisfactory layout solution will take as the solution of the problem inthis paper, otherwise renew given radius to solve the problem. The numerical experimentsresults show that the computational precision of quasi-physical quasi-human algorithm isbetter.For the orthogonal rectangular packing problem with equilibrium constraints and thecircle and rectangle orthogonal packing problem with equilibrium constraints, this paperpresents the quasi-physical quasi-human algorithm, and its performance is better than thatof existing other algorithms. Authors hope that the approaches of in the paper will behelpful for the solving other similar layout problems.