|
|
|
| A new energy landscape paving heuristic for satellite module layouts |
| Jing-fa Liu, Juan Huang, Gang Li, Wen-jie Liu, Ting-zhao Guan, Liang Hao |
| Jiangsu Engineering Center of Network Monitoring, Nanjing University of Information Science & Technology, Nanjing 210044, China; School of Computer & Software, Nanjing University of Information Science & Technology, Nanjing 210044, China; School of Mathematics and Statistics, Nanjing University of Information Science & Technology, Nanjing 210044, China; Office of Informationization, Construction and Management, Nanjing University of Information Science & Technology, Nanjing 210044, China |
|
|
|
Abstract 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, nELP, is proposed for SMLP. Two representative instances from the literature are tested. Computational results show that the proposed nELP algorithm is an effective method for solving SMLP with performance constraints.
|
|
Received: 17 September 2015
Published: 08 October 2016
|
|
|
一种基于新的势能曲面变平的卫星舱布局问题的启发式方法
\n 概要：卫星舱布局问题是一种带性能约束的三维布局优化问题，已经被证明具有NP难度。通过采用拟物策略和罚函数方法，我们将该问题转化为一个不带约束的优化问题。势能曲面变平法（energy landscape paving, ELP）是一个经典的基于蒙特卡洛的全局优化算法，已被成功应用于许多优化问题。ELP能够通过在复杂的势能曲面随机行走来搜索低能构形。然而，当ELP陷入又窄又深的势能曲面山谷时，它很难逃离。通过提出ELP方法中直方图函数的一种新的更新机制，我们获得了一种改进的势能曲面变平法。通过将带局部搜索的梯度法融入改进的ELP方法，为卫星舱布局问题提出了一种新的全局搜索方法nELP。本文测试了来自文献的两个有代表性的算例。计算结果显示，nELP是求解带性能约束的卫星舱布局问题的有效算法。
\n
关键词：
三维布局,
势能曲面变平,
布局优化,
性能约束
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
