一种基于新的势能曲面变平的卫星舱布局问题的启发式方法

Jing-fa LIU; Juan HUANG; Gang LI; Wen-jie LIU; Ting-zhao GUAN; Liang HAO

doi:10.1631/FITEE.1500302

Your Location：

Home >

Browse articles >

一种基于新的势能曲面变平的卫星舱布局问题的启发式方法

常规文章 | Updated：2022-05-19

- 一种基于新的势能曲面变平的卫星舱布局问题的启发式方法
- A new energy landscape paving heuristic for satellite module layouts
- 信息与电子工程前沿（英文） 2016年17卷第10期页码：1031-1043
- Affiliations：
  
  1Jiangsu Engineering Center of Network Monitoring, Nanjing University of Information Science & Technology, Nanjing 210044, China
  2School of Computer & Software, Nanjing University of Information Science & Technology, Nanjing 210044, China
  3School of Mathematics and Statistics, Nanjing University of Information Science & Technology, Nanjing 210044, China
  4Office of Informationization, Construction and Management, Nanjing University of Information Science & Technology, Nanjing 210044, China
- Author bio：
  
  E-mail: huangjuan4455@163.com
- Funds：
  
  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)
- DOI：10.1631/FITEE.1500302
  中图分类号： TP391; V474
- 收稿：2015-09-17，
  
  录用：2016-2-18，
  
  纸质出版：2016-10
- Accepted：
Scan QR Code
一种基于新的势能曲面变平的卫星舱布局问题的启发式方法[J]. 信息与电子工程前沿（英文）, 2016,17(10):1031-1043.

Jing-fa LIU, Juan HUANG, Gang LI, et al. A new energy landscape paving heuristic for satellite module layouts[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(10): 1031-1043.
一种基于新的势能曲面变平的卫星舱布局问题的启发式方法[J]. 信息与电子工程前沿（英文）, 2016,17(10):1031-1043. DOI： 10.1631/FITEE.1500302.

Jing-fa LIU, Juan HUANG, Gang LI, et al. A new energy landscape paving heuristic for satellite module layouts[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(10): 1031-1043. DOI： 10.1631/FITEE.1500302.

摘要

卫星舱布局问题是一种带性能约束的三维布局优化问题，已经被证明具有NP难度。通过采用拟物策略和罚函数方法，我们将该问题转化为一个不带约束的优化问题。势能曲面变平法（energy landscape paving

ELP）是一个经典的基于蒙特卡洛的全局优化算法，已被成功应用于许多优化问题。ELP能够通过在复杂的势能曲面随机行走来搜索低能构形。然而，当ELP陷入又窄又深的势能曲面山谷时，它很难逃离。通过提出ELP方法中直方图函数的一种新的更新机制，我们获得了一种改进的势能曲面变平法。通过将带局部搜索的梯度法融入改进的ELP方法，为卫星舱布局问题提出了一种新的全局搜索方法nELP。本文测试了来自文献的两个有代表性的算例。计算结果显示，nELP是求解带性能约束的卫星舱布局问题的有效算法。

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.

关键词

Keywords

references

N Bansal , , , X Han , , , K Iwama , , , 等 . . A harmonic algorithm for the 3D strip packing problem . . SIAM J. Comput. , , 2013 . . 42 ( ( 2 ): ): 579 - - 592 . . DOI: 10.1137/070691607 http://doi.org/10.1137/070691607 . .

J Cagan , , , K Shimada , , , S Yin . . A survey of computational approaches to three-dimensional layout problems . . Comput. Aided Des. , , 2002 . . 34 ( ( 8 ): ): 597 - - 611 . . DOI: 10.1016/S0010-4485(01)00109-9 http://doi.org/10.1016/S0010-4485(01)00109-9 . .

Y Chen , , , H.F Teng . . Coevolutionary algorithm with coarse-to-fine grain strategy and its application to layout design of satellite module . . J. Dalian Univ. Tech. , , 2010 . . 50 ( ( 6 ): ): 931 - - 936 . . . .

A.P.C. Cuco , , , F.L de Sousa , , , A.J.S Neto . . A multi- objective methodology for spacecraft equipment layouts . . Optim. Eng. , , 2014 . . 16 ( ( 1 ): ): 165 - - 181 . . DOI: 10.1007/s11081-014-9252-z http://doi.org/10.1007/s11081-014-9252-z . .

A.M Valle , , , T.A de Queiroz , , , F.K Miyazawa , , , 等 . . Heuristics for two-dimensional knapsack and cutting stock problems with items of irregular shape . . Expert Syst. Appl. , , 2012 . . 39 ( ( 16 ): ): 12589 - - 12598 . . DOI: 10.1016/j.eswa.2012.05.025 http://doi.org/10.1016/j.eswa.2012.05.025 . .

S.I Galiev , , , M.S Lisafina . . Linear models for the approximate solution of the problem of packing equal circles into a given domain . . Eur. J. Oper. Res. , , 2013 . . 230 ( ( 3 ): ): 505 - - 514 . . DOI: 10.1016/j.ejor.2013.04.050 http://doi.org/10.1016/j.ejor.2013.04.050 . .

F Glover . . Tabu search—part Ⅰ . . Informs J. Comput. , , 1990a . . 1 ( ( 1 ): ): 89 - - 98 . . . .

F Glover . . Tabu search—part Ⅱ . . Orsa J. Comput. , , 1990b . . 2 ( ( 1 ): ): 4 - - 32 . . . .

K Hamacher . . Energy landscape paving as a perfect optimization approach under detrended fluctuation analysis . . Phys. A , , 2007 . . 378 ( ( 2 ): ): 307 - - 314 . . DOI: 10.1016/j.physa.2006.11.071 http://doi.org/10.1016/j.physa.2006.11.071 . .

U.H.E Hansmann , , , L.T Wille . . Global optimization by energy landscape paving . . Phys. Rev. Lett. , , 2002 . . 88 ( ( 6 ): ): 068105 . .

K He , , , M.D Zeng , , , R.C Xu , , , 等 . . A quasi-physical algorithm based on coarse and fine adjustment for solving circles packing problem with constraints of equilibrium . . Chin. J. Comput. , , 2013 . . 36 ( ( 6 ): ): 1224 - - 1234 . . DOI: 10.3724/SP.J.1013.2013.01224 http://doi.org/10.3724/SP.J.1013.2013.01224 . .

J.Z Huo , , , Y.J Shi , , , H.F Teng . . Layout design of a satellite module using a human-guided genetic algorithm . . IEEE Int. Conf. on Computational Intelligence and Security , , 2006 . . 230 - - 235 . . . .

K Jansen , , , L Prädel . . A new asymptotic approximation algorithm for 3-dimensional strip packing . . LNCS , , 2014 . . 8327 327 - - 338 . . DOI: 10.1007/978-3-319-04298-5_29 http://doi.org/10.1007/978-3-319-04298-5_29 . .

Z.Q Li , , , H.L Zhang , , , J.H Zheng , , , 等 . . Heuristic evolutionary approach for weighted circles layout . . Commun. Comput. Inform. Sci. , , 2011 . . 86 324 - - 331 . . DOI: 10.1007/978-3-642-19853-3_47 http://doi.org/10.1007/978-3-642-19853-3_47 . .

J.F Liu , , , S.J Xue , , , Z.X Liu , , , 等 . . An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle . . Comput. Ind. Eng. , , 2009 . . 57 ( ( 3 ): ): 1144 - - 1149 . . DOI: 10.1016/j.cie.2009.05.010 http://doi.org/10.1016/j.cie.2009.05.010 . .

J.F Liu , , , G Li , , , H.T Geng . . A new heuristic algorithm for the circular packing problem with equilibrium constraints . . Sci. China Inform. Sci. , , 2011 . . 54 ( ( 8 ): ): 1572 - - 1584 . . DOI: 10.1007/s11432-4351-3 http://doi.org/10.1007/s11432-4351-3 . .

J.F Liu , , , L Hao , , , G Li , , , 等 . . Muti-objective layout optimization of a satellite module using the Wang-Landau sampling method with local search . . Front. Inform. Technol. Electron. Eng. , , 2016 . . 17 ( ( 6 ): ): 527 - - 542 . . DOI: 10.1631/FITEE.1500292 http://doi.org/10.1631/FITEE.1500292 . .

Z.W Liu , , , H.F Teng . . Human-computer cooperative layout design method and its application . . Comput. Ind. Eng. , , 2008 . . 55 ( ( 4 ): ): 735 - - 757 . . DOI: 10.1016/j.cie.2006.11.007 http://doi.org/10.1016/j.cie.2006.11.007 . .

A Lodi , , , S Martello , , , M Monaci . . Two-dimensional packing problems: a survey . . Eur. J. Oper. Res. , , 2002 . . 141 ( ( 2 ): ): 241 - - 252 . . DOI: 10.1016/S0377-2217(02)00123-6 http://doi.org/10.1016/S0377-2217(02)00123-6 . .

S Martello , , , D Vigo . . The three-dimensional bin packing problem . . Oper. Res. , , 2000 . . 48 ( ( 2 ): ): 256 - - 267 . . . .

A Rakshit , , , P Bandyopadhyay . . Finding low energy minima of (H2O)25 and (H2O)30 with temperature basin paving Monte Carlo method with effective fragment potential: new ‘global minimum’ and graph theoretical characterization of low energy structures . . Comput. Theor. Chem. , , 2013 . . 1021 206 - - 214 . . DOI: 10.1016/j.comptc.2013.07.023 http://doi.org/10.1016/j.comptc.2013.07.023 . .

A Schug , , , W Wenzel , , , U.H.E Hansmann . . Energy landscape paving simulations of the trp-cage protein . . J. Chem. Phys. , , 2005 . . 122 ( ( 19 ): ): 194711 . .

S Shanker , , , P Bandyopadhyay . . Monte Carlo temperature basin paving with effective fragment potential: an efficient and fast method for finding low-energy structures of water clusters (H 2 O) 20 and (H 2 O) 25 . . Phys. Chem. A. , , 2011 . . 115 ( ( 42 ): ): 11866 - - 11875 . . DOI: 10.1021/jp2073864 http://doi.org/10.1021/jp2073864 . .

M.E Silveira , , , S.M Vieira , , , J.M.D.C Sousa . . An ACO algorithm for the 3D bin packing problem in the steel industry . . LNCS , , 2013 . . 7906 535 - - 544 . . DOI: 10.1007/978-3-642-38577-3_55 http://doi.org/10.1007/978-3-642-38577-3_55 . .

Z.G Sun , , , H.F Teng . . Optimal layout design of a satellite module . . Eng. Optim. , , 2003 . . 35 ( ( 5 ): ): 513 - - 529 . . DOI: 10.1080/03052150310001602335 http://doi.org/10.1080/03052150310001602335 . .

Z.G Sun , , , H.F Teng , , , Z Liu . . Several key problems in automatic layout design of spacecraft modules . . Prog. Nat. Sci. , , 2003 . . 13 ( ( 11 ): ): 801 - - 808 . . . .

H.F Teng , , , Y Chen , , , W Zeng , , , 等 . . A dual-system variable-grain cooperative coevolutionary algorithm: satellite-module layout design . . IEEE Trans. Evol. Comput. , , 2010 . . 14 ( ( 3 ): ): 438 - - 455 . . DOI: 10.1109/TEVC.2009.2033585 http://doi.org/10.1109/TEVC.2009.2033585 . .

J Thomas , , , N.S Chaudhari . . Design of efficient packing system using genetic algorithm based on hyper heuristic approach . . Adv. Eng. Softw. , , 2014 . . 73 ( ( 5 ): ): 45 - - 52 . . DOI: 10.1016/j.advengsoft.2014.03.003 http://doi.org/10.1016/j.advengsoft.2014.03.003 . .

J.F Tsai , , , P.C Wang , , , M.H Lin . . A global optimization approach for solving three-dimensional open dimension rectangular packing problems . . Optimization , , 2014 . . 64 ( ( 12 ): ): 1 - - 18 . . DOI: 10.1080/02331934.2013.877906 http://doi.org/10.1080/02331934.2013.877906 . .

Y.S Wang , , , H.F Teng . . Knowledge fusion design method: satellite module layout . . Chin. J. Aeronaut. , , 2009 . . 22 ( ( 1 ): ): 32 - - 42 . . DOI: 10.1016/S1000-9361(08)60066-7 http://doi.org/10.1016/S1000-9361(08)60066-7 . .

Y.S Wang , , , B.X Yue , , , H.F Teng , , , 等 . . Satellite payloads configuration design using multi-agent system based on ant colony optimization . . IEEE Int. Conf. on soft Computing and Pattern Recognition , , 2011 . . 336 - - 341 . . . .

L.X Zhan , , , Z Jeff , , , Y Chen , , , 等 . . Monte Carlo basin paving: an improved global optimization method . . Phys. Rev. E. , , 2006 . . 73 ( ( 1pt2 ): ): 015701 . .

B Zhang , , , H.F Teng . . Particle swarm optimization based on pyramid model for satellite module layout . . Chin. J. Mech. Eng. , , 2005 . . 18 ( ( 4 ): ): 530 - - 536 . . . .

B Zhang , , , H.F Teng , , , Y.J Shi . . Layout optimization of satellite module using soft computing techniques . . Appl. Soft Comput. , , 2008 . . 8 ( ( 1 ): ): 507 - - 521 . . DOI: 10.1016/j.asoc.2007.03.004 http://doi.org/10.1016/j.asoc.2007.03.004 . .

D.F Zhang , , , A.S Deng . . An effective hybrid algorithm for the problem of packing circles into a larger containing circle . . Comput. Oper. Res. , , 2005 . . 32 ( ( 8 ): ): 1941 - - 1951 . . DOI: 10.1016/j.cor.2003.12.006 http://doi.org/10.1016/j.cor.2003.12.006 . .

浏览量

Downloads

CSCD

文章被引用时，请邮件提醒。

Submit

工具集

关联资源

暂无数据