This article describes a study of the satellite module layout problem （SMLP）, which is a three-dimensional （3D） layout optimization problem with performance constraints that has proved to be non-deterministic poly...This article describes a study of the satellite module layout problem （SMLP）, which is a three-dimensional （3D） layout optimization problem with performance constraints that has proved to be non-deterministic polynomial-time hard （NP-hard）. To deal with this problem, we convert it into an unconstrained optimization problem using a quasi-physical strategy and the penalty function method. The energy landscape paving （ELP） method is a class of Monte-Carlo-based global optimization algorithm that has been successfully applied to solve many optimization problems. ELP can search for low-energy layouts via a random walk in complex energy landscapes. However, when ELP falls into the narrow and deep valleys of an energy landscape, it is difficult to escape. By putting forward a new update mechanism of the histogram function in ELP, we obtain an improved ELP method which can overcome this drawback. By incorporating the gradient method with local search into the improved ELP method, a new global search optimization method, hELP, is proposed for SMLP. Two representative instances from the literature are tested. Computational results show that the proposed hELP algorithm is an effective method for solving SMLP with performance constraints.展开更多
基金Project supported by the National Natural Science Foundation of China （No. 61373016）, the Six Talent Peaks Project of Jiangsu Province, China （No. DZXX-041）, the Project Funded by the Priority Academic Program Development of Jiangsu Higher Education Institutions, and the Natural Science Foundation of Jiangsu Province, China （No. BK20141005）
文摘This article describes a study of the satellite module layout problem （SMLP）, which is a three-dimensional （3D） layout optimization problem with performance constraints that has proved to be non-deterministic polynomial-time hard （NP-hard）. To deal with this problem, we convert it into an unconstrained optimization problem using a quasi-physical strategy and the penalty function method. The energy landscape paving （ELP） method is a class of Monte-Carlo-based global optimization algorithm that has been successfully applied to solve many optimization problems. ELP can search for low-energy layouts via a random walk in complex energy landscapes. However, when ELP falls into the narrow and deep valleys of an energy landscape, it is difficult to escape. By putting forward a new update mechanism of the histogram function in ELP, we obtain an improved ELP method which can overcome this drawback. By incorporating the gradient method with local search into the improved ELP method, a new global search optimization method, hELP, is proposed for SMLP. Two representative instances from the literature are tested. Computational results show that the proposed hELP algorithm is an effective method for solving SMLP with performance constraints.
