求解多目标卫星舱布局优化问题的带局部搜索的Wang-Landau抽样算法

Jing-fa LIU; Liang HAO; Gang LI; Yu XUE; Zhao-xia LIU; Juan HUANG

doi:10.1631/FITEE.1500292

Your Location：

Home >

Browse articles >

求解多目标卫星舱布局优化问题的带局部搜索的Wang-Landau抽样算法

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

- 求解多目标卫星舱布局优化问题的带局部搜索的Wang-Landau抽样算法
- Multi-objective layout optimization of a satellite module using the Wang-Landau sampling method with local search
- 信息与电子工程前沿（英文） 2016年17卷第6期页码：527-542
- 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:haoliang90518@163.com
- Funds：
  
  Project supported by the National Natural Science Foundation of China (Nos. 61373016 and 61403206), 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.1500292
  中图分类号： TP391; V474
- 收稿：2015-09-06，
  
  录用：2016-2-28，
  
  纸质出版：2016-06
- Accepted：
Scan QR Code
求解多目标卫星舱布局优化问题的带局部搜索的Wang-Landau抽样算法[J]. 信息与电子工程前沿（英文）, 2016,17(6):527-542.

Jing-fa LIU, Liang HAO, Gang LI, et al. Multi-objective layout optimization of a satellite module using the Wang-Landau sampling method with local search[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(6): 527-542.
求解多目标卫星舱布局优化问题的带局部搜索的Wang-Landau抽样算法[J]. 信息与电子工程前沿（英文）, 2016,17(6):527-542. DOI： 10.1631/FITEE.1500292.

Jing-fa LIU, Liang HAO, Gang LI, et al. Multi-objective layout optimization of a satellite module using the Wang-Landau sampling method with local search[J]. Frontiers of Information Technology & Electronic Engineering, 2016, 17(6): 527-542. DOI： 10.1631/FITEE.1500292.

摘要

目的

成功的卫星舱布局设计不仅可以有效降低卫星舱的发射成本与建造成本，而且可以提高其承载能力、使用寿命及稳定性。本文研究成果理论上可望推广应用于具有不同布局空间和考虑其他设计目标、约束条件的布局设计问题，有助于推进航天器布局设计理论的研究。在算法实践上期望有助于人造卫星仪器舱布局设计问题实用化方法与技术的研究和应用，并可望推广应用于其它复杂航天器布局设计领域。

创新点

将Wang-Landau随机抽样算法和基于梯度法的局部搜索算法相结合，并引入一些启发式布局更新策略，提出了一种新的混合算法。实验结果表明该算法可以有效解决多目标卫星舱组件布局优化问题。

方法

借鉴罚函数思想把带约束的优化问题转化为不带约束的优化问题；采用二分法找到卫星舱的最小半径；提出快速干涉量计算方法；通过结合Wang-Landau抽样算法，基于梯度法的局部搜索算法和启发式布局更新策略构建了一种混合算法（WL-LS）。

结论

通过结合Wang-Landau抽样算法、局部搜索算法和启发式布局更新策略，所提出的混合算法在实验结果上优于现有的最好算法，是一种求解多目标卫星舱布局优化问题的有效算法。

Abstract

The layout design of satellite modules is considered to be NP-hard. It is not only a complex coupled system design problem but also a special multi-objective optimization problem. The greatest challenge in solving this problem is that the function to be optimized is characterized by a multitude of local minima separated by high-energy barriers. The Wang-Landau (WL) sampling method

which is an improved Monte Carlo method

has been successfully applied to solve many optimization problems. In this paper we use the WL sampling method to optimize the layout of a satellite module. To accelerate the search for a global optimal layout

local search (LS) based on the gradient method is executed once the Monte-Carlo sweep produces a new layout. By combining the WL sampling algorithm

the LS method

and heuristic layout update strategies

a hybrid method called WL-LS is proposed to obtain a final layout scheme. Furthermore

to improve significantly the efficiency of the algorithm

we propose an accurate and fast computational method for the overlapping depth between two objects (such as two rectangular objects

two circular objects

or a rectangular object and a circular object) embedding each other. The rectangular objects are placed orthogonally. We test two instances using first 51 and then 53 objects. For both instances

the proposed WL-LS algorithm outperforms methods in the literature. Numerical results show that the WL-LS algorithm is an effective method for layout optimization of satellite modules.

关键词

Keywords

references

SD Allen , , , EK Burke , , , G Kendall . . A hybrid placement strategy for the three-dimensional strip packing problem . . Eur. J. Oper. Res. , , 2011 . . 209 ( ( 3 ): ): 219 - - 227 . . DOI: 10.1016/j.ejor.2010.09.023 http://doi.org/10.1016/j.ejor.2010.09.023 . .

JA Bennell , , , KA Dowsland , , , WB Dowsland . . The irregular cutting-stock problem—a new procedure for deriving the no-fit polygon . . Comput.Oper. Res. , , 2001 . . 28 ( ( 3 ): ): 271 - - 287 . . DOI: 10.1016/S0305-0548(00)00021-6 http://doi.org/10.1016/S0305-0548(00)00021-6 . .

W Chen , , , YJ Shi , , , HF Teng . . An improved differential evolution with local search for constrained layout optimization of satellite module . . LNCS , , 2008 . . 5227 742 - - 749 . . DOI: 10.1007/978-3-540-85984-0_89 http://doi.org/10.1007/978-3-540-85984-0_89 . .

TG Crainic , , , G Perboli , , , W Rei , , , 等 . . Efficient lower bounds and heuristics for the variable cost and size bin packing problem . . Comput. Oper. Res. , , 2011 . . 38 ( ( 11 ): ): 1474 - - 1482 . . DOI: 10.1016/j.cor.2011.01.001 http://doi.org/10.1016/j.cor.2011.01.001 . .

JF Gonalves , , , MG Resende . . A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem . . J. Comb. Optim. , , 2011 . . 22 ( ( 2 ): ): 180 - - 201 . . DOI: 10.1007/s10878-009-9282-1 http://doi.org/10.1007/s10878-009-9282-1 . .

K He , , , DZ Mo , , , RC 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.1016.2013.01224 http://doi.org/10.3724/SP.J.1016.2013.01224 . .

WQ Huang , , , Y Kang . . A short note on a simple search heuristic for the diskspacking problem . . Ann.Oper.Res. , , 2004 . . 131 ( ( 1-4 ): ): 101 - - 108 . . DOI: 10.1023/B:ANOR.0000039514.14699.03 http://doi.org/10.1023/B:ANOR.0000039514.14699.03 . .

JZ Huo , , , HF Teng . . Optimal layout design of a satellite module using a coevolutionary method with heuristic rules . . J. Aerosp. Eng. , , 2009 . . 22 ( ( 2 ): ): 101 - - 111 . . DOI: 10.1061/(ASCE)0893-1321(2009)22:2(101) http://doi.org/10.1061/(ASCE)0893-1321(2009)22:2(101) . .

B Jin , , , HF Teng . . Case-based evolutionary design approach for satellite module layout . . J. Sci. Ind. Res. , , 2007 . . 66 ( ( 12 ): ): 989 - - 994 . . . .

A Khanafer , , , F Clautiaux , , , EG Talbi . . Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts . . Comput. Oper. Res. , , 2012 . . 39 ( ( 1 ): ): 54 - - 63 . . DOI: 10.1016/j.cor.2010.07.009 http://doi.org/10.1016/j.cor.2010.07.009 . .

DP Landau , , , SH Tsai , , , M Exler . . A new approach to Monte Carlo simulations in statistical physics: Wang-Landau sampling . . Am. J. Phys. , , 2004 . . 72 ( ( 10 ): ): 1294 - - 1302 . . DOI: 10.1119/1.1707017 http://doi.org/10.1119/1.1707017 . .

KY Lei , , , YH Qiu . . A study of constrained layout optimization using adaptive particle swarm optimizer . . J. Comput. Res. Dev. , , 2006 . . 43 1724 - - 1731 . . . .

ZQ Li . . A fast projection-separation approach for collision detection between polytopes . . J.Comput.Aid. Des.Comput.Graph. , , 2010 . . 22 ( ( 4 ): ): 639 - - 646 . . . .

ZQ Li , , , YF Xie , , , ZJ Tian , , , 等 . . A heuristic particle swarm optimization with quasi-human strategy for weighted circles packing problem . . 8th Int. Conf. on Natural Computation , , 2012 . . 723 - - 727 . . DOI: 10.1109/ICNC.2012.6234660 http://doi.org/10.1109/ICNC.2012.6234660 . .

JF Liu , , , G Li . . Basin filling algorithm for the circular packing problem with equilibrium behavioral constraints . . Sci. Chin. Inf. Sci. , , 2010 . . 53 ( ( 5 ): ): 885 - - 895 . . DOI: 10.1007/s11432-010-0080-2 http://doi.org/10.1007/s11432-010-0080-2 . .

JF Liu , , , SJ Xue , , , ZX 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 . .

JF Liu , , , G Li , , , DB Chen , , , 等 . . Two-dimensional equilibrium constraint layout using simulated annealing . . Comput. Ind. Eng. , , 2010 . . 59 ( ( 4 ): ): 530 - - 536 . . DOI: 10.1016/j.cie.2010.06.009 http://doi.org/10.1016/j.cie.2010.06.009 . .

JF Liu , , , G Li , , , HT Geng . . A new heuristic algorithm for the circular packing problem with equilibrium constraints . . Sci. Chin. Inf. Sci. , , 2011 . . 54 ( ( 8 ): ): 1572 - - 1584 . . DOI: 10.1007/s11432-011-4351-3 http://doi.org/10.1007/s11432-011-4351-3 . .

ZW Liu , , , HF 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 . .

S Martello , , , D Pisinger , , , D Vigo . . The three-dimensional bin packing problem . . Oper. Res. , , 2000 . . 48 ( ( 2 ): ): 256 - - 267 . . DOI: 10.1287/opre.48.2.256.12386 http://doi.org/10.1287/opre.48.2.256.12386 . .

I Moon , , , T.V.L. Nguyen . . Container packing problem with balance constraints . . OR Spectr. , , 2014 . . 36 ( ( 4 ): ): 837 - - 878 . . DOI: 10.1007/s00291-013-0356-1 http://doi.org/10.1007/s00291-013-0356-1 . .

BJ Schulz , , , K Binder , , , M Müller , , , 等 . . Avoiding boundary effects in Wang-Landau sampling . . Phys. Rev.E , , 2003 . . 67 ( ( 6 ): ): 067102 DOI: 10.1103/PhysRevE.67.067102 http://doi.org/10.1103/PhysRevE.67.067102 . .

DT Seaton , , , T Wüst , , , DP Landau . . Collapse transitions in a flexible homopolymer chain: application of the Wang-Landau algorithm . . Phys. Rev.E , , 2010 . . 81 ( ( 1 ): ): 011802 DOI: 10.1103/PhysRevE.81.011802 http://doi.org/10.1103/PhysRevE.81.011802 . .

ZG Sun , , , HF 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 . .

F Tang , , , HF Teng . . A modified genetic algorithm and its application to layout optimization . . J. Softw. , , 1999 . . 10 ( ( 10 ): ): 1096 - - 1102 . . . .

HF 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 . .

F Wang , , , DP Landau . . Efficient, multiple-range random walk algorithm to calculate the density of states . . Phys. Rev. Lett. , , 2001 . . 86 ( ( 10 ): ): 2050 DOI: 10.1103/PhysRevLett.86.2050 http://doi.org/10.1103/PhysRevLett.86.2050 . .

YS Wang , , , HF 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 . .

MH Wu , , , YX Yu , , , J Zhou . . An octree algorithm for collision detection using space partition . . Chin. J. Comput. , , 1997 . . 20 ( ( 9 ): ): 849 - - 854 . . . .

YC Xu , , , RB Xiao . . Ant colony algorithm for layout optimization with equilibrium constraints . . Contr. Dec. , , 2008 . . 23 ( ( 1 ): ): 25 - - 29 . . . .

B Zhang , , , HF Teng , , , YJ 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 . .

DF Zhang , , , AS Deng , , , Y Kang . . A hybrid heuristic algorithm for the rectangular packing problem . . Int. Conf. on Computational Science , , 2005 . . 783 - - 791 . . DOI: 10.1007/11428831_97 http://doi.org/10.1007/11428831_97 . .

ZH Zhang , , , YS Wang , , , HF Teng , , , 等 . . Parallel dual-system cooperative co-evolutionary differential evolution algorithm with human-computer cooperation for multi-cabin satellite layout optimization . . J. Converg. Inform. Technol. , , 2013 . . 8 ( ( 4 ): ): 711 - - 720 . . DOI: 10.4156/jcit.vol8.issue4.82 http://doi.org/10.4156/jcit.vol8.issue4.82 . .

C Zhou , , , RN Bhatt . . Understanding and improving the Wang-Landau algorithm . . Phys. Rev. E , , 2005 . . 72 ( ( 2 ): ): 025701 DOI: 10.1103/PhysRevE.72.025701 http://doi.org/10.1103/PhysRevE.72.025701 . .

C Zhou , , , L Gao , , , HB Gao . . Particle swarm optimization based algorithm for constrained layout optimization . . Contr. Dec. , , 2005 . . 20 ( ( 1 ): ): 36 - - 40 . . . .

浏览量

Downloads

CSCD

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

Submit

工具集

关联资源

暂无数据