Full Text:   <687>

Summary:  <356>

CLC number: TP391; V474

On-line Access: 2016-06-06

Received: 2015-09-06

Revision Accepted: 2016-02-28

Crosschecked: 2016-05-10

Cited: 4

Clicked: 1740

Citations:  Bibtex RefMan EndNote GB/T7714


Liang Hao


-   Go to

Article info.
Open peer comments

Frontiers of Information Technology & Electronic Engineering  2016 Vol.17 No.6 P.527-542


Multi-objective layout optimization of a satellite module using the Wang-Landau sampling method with local search

Author(s):  Jing-fa Liu, Liang Hao, Gang Li, Yu Xue, Zhao-xia Liu, Juan Huang

Affiliation(s):  Jiangsu Engineering Center of Network Monitoring, Nanjing University of Information Science & Technology, Nanjing 210044, China; more

Corresponding email(s):   haoliang90518@163.com

Key Words:  Packing, Layout design, Satellite module, Wang-Landau algorithm

Jing-fa Liu, Liang Hao, Gang Li, Yu Xue, Zhao-xia Liu, Juan Huang. 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.

@article{title="Multi-objective layout optimization of a satellite module using the Wang-Landau sampling method with local search",
author="Jing-fa Liu, Liang Hao, Gang Li, Yu Xue, Zhao-xia Liu, Juan Huang",
journal="Frontiers of Information Technology & Electronic Engineering",
publisher="Zhejiang University Press & Springer",

%0 Journal Article
%T Multi-objective layout optimization of a satellite module using the Wang-Landau sampling method with local search
%A Jing-fa Liu
%A Liang Hao
%A Gang Li
%A Yu Xue
%A Zhao-xia Liu
%A Juan Huang
%J Frontiers of Information Technology & Electronic Engineering
%V 17
%N 6
%P 527-542
%@ 2095-9184
%D 2016
%I Zhejiang University Press & Springer
%DOI 10.1631/FITEE.1500292

T1 - Multi-objective layout optimization of a satellite module using the Wang-Landau sampling method with local search
A1 - Jing-fa Liu
A1 - Liang Hao
A1 - Gang Li
A1 - Yu Xue
A1 - Zhao-xia Liu
A1 - Juan Huang
J0 - Frontiers of Information Technology & Electronic Engineering
VL - 17
IS - 6
SP - 527
EP - 542
%@ 2095-9184
Y1 - 2016
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/FITEE.1500292

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.

This paper’s main contributions are introducing the Wang-Landau method (W-L) for solving the layout optimization of a satellite module problem and connecting the W-L with L-S to form the proposed method. This is new and useful to solve the layout optimization of a satellite module problem.




Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[1]Allen, S.D., Burke, E.K., Kendall, G., 2011. A hybrid placement strategy for the three-dimensional strip packing problem. Eur. J. Oper. Res., 209(3):219-227.

[2]Bennell, J.A., Dowsland, K.A., Dowsland, W.B., 2001. The irregular cutting-stock problem—a new procedure for deriving the no-fit polygon. Comput. Oper. Res., 28(3):271-287.

[3]Chen, W., Shi, Y.J., Teng, H.F., 2008. An improved differential evolution with local search for constrained layout optimization of satellite module. LNCS, 5227:742-749.

[4]Crainic, T.G., Perboli, G., Rei, W., et al., 2011. Efficient lower bounds and heuristics for the variable cost and size bin packing problem. Comput. Oper. Res., 38(11):1474-1482.

[5]Gonçalves, J.F., Resende, M.G., 2011. A parallel multi-population genetic algorithm for a constrained two-dimensional orthogonal packing problem. J. Comb. Optim., 22(2):180-201.

[6]He, K., Mo, D.Z., Xu, R.C., et al., 2013. A quasi-physical algorithm based on coarse and fine adjustment for solving circles packing problem with constraints of equilibrium. Chin. J. Comput., 36(6):1224-1234 (in Chinese).

[7]Huang, W.Q., Kang, Y., 2004. A short note on a simple search heuristic for the diskspacking problem. Ann. Oper. Res., 131(1-4):101-108.

[8]Huo, J.Z., Teng, H.F., 2009. Optimal layout design of a satellite module using a coevolutionary method with heuristic rules. J. Aerosp. Eng., 22(2):101-111.

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

[10]Khanafer, A., Clautiaux, F., Talbi, E.G., 2012. Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts. Comput. Oper. Res., 39(1):54-63.

[11]Landau, D.P., Tsai, S.H., Exler, M., 2004. A new approach to Monte Carlo simulations in statistical physics: Wang-Landau sampling. Am. J. Phys., 72(10):1294-1302.

[12]Lei, K.Y., Qiu, Y.H., 2006. A study of constrained layout optimization using adaptive particle swarm optimizer. J. Comput. Res. Dev., 43:1724-1731 (in Chinese).

[13]Li, Z.Q., 2010. A fast projection-separation approach for collision detection between polytopes. J. Comput. Aid. Des. Comput. Graph., 22(4):639-646 (in Chinese).

[14]Li, Z.Q., Xie, Y.F., Tian, Z.J., et al., 2012. A heuristic particle swarm optimization with quasi-human strategy for weighted circles packing problem. 8th Int. Conf. on Natural Computation, p.723-727.

[15]Liu, J.F., Li, G., 2010. Basin filling algorithm for the circular packing problem with equilibrium behavioral constraints. Sci. Chin. Inf. Sci., 53(5):885-895 (in Chinese).

[16]Liu, J.F., Xue, S.J., Liu, Z.X., et al., 2009. An improved energy landscape paving algorithm for the problem of packing circles into a larger containing circle. Comput. Ind. Eng., 57(3):1144-1149.

[17]Liu, J.F., Li, G., Chen, D.B., et al., 2010. Two-dimensional equilibrium constraint layout using simulated annealing. Comput. Ind. Eng., 59(4):530-536.

[18]Liu, J.F., Li, G., Geng, H.T., 2011. A new heuristic algorithm for the circular packing problem with equilibrium constraints. Sci. Chin. Inf. Sci., 54(8):1572-1584.

[19]Liu, Z.W., Teng, H.F., 2008. Human–computer cooperative layout design method and its application. Comput. Ind. Eng., 55(4):735-757.

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

[21]Moon, I., Nguyen, T.V.L., 2014. Container packing problem with balance constraints. OR Spectr., 36(4):837-878.

[22]Schulz, B.J., Binder, K., Müller, M., et al., 2003. Avoiding boundary effects in Wang-Landau sampling. Phys. Rev. E, 67(6):067102.

[23]Seaton, D.T., Wüst, T., Landau, D.P., 2010. Collapse transitions in a flexible homopolymer chain: application of the Wang-Landau algorithm. Phys. Rev. E, 81(1):011802.

[24]Sun, Z.G., Teng, H.F., 2003. Optimal layout design of a satellite module. Eng. Optim., 35(5):513-529.

[25]Tang, F., Teng, H.F., 1999. A modified genetic algorithm and its application to layout optimization. J. Softw., 10(10): 1096-1102 (in Chinese).

[26]Teng, H.F., Chen, Y., Zeng, W., et al., 2010. A dual-system variable-grain cooperative coevolutionary algorithm: satellite-module layout design. IEEE Trans. Evol. Comput., 14(3):438-455.

[27]Wang, F., Landau, D.P., 2001. Efficient, multiple-range random walk algorithm to calculate the density of states. Phys. Rev. Lett., 86(10):2050.

[28]Wang, Y.S., Teng, H.F., 2009. Knowledge fusion design method: satellite module layout. Chin. J. Aeronaut., 22(1): 32-42.

[29]Wu, M.H., Yu, Y.X., Zhou, J., 1997. An octree algorithm for collision detection using space partition. Chin. J. Comput., 20(9):849-854 (in Chinese).

[30]Xu, Y.C., Xiao, R.B., 2008. Ant colony algorithm for layout optimization with equilibrium constraints. Contr. Dec., 23(1):25-29 (in Chinese).

[31]Zhang, B., Teng, H.F., Shi, Y.J., 2008. Layout optimization of satellite module using soft computing techniques. Appl. Soft Comput., 8(1):507-521.

[32]Zhang, D.F., Deng, A.S., Kang, Y., 2005. A hybrid heuristic algorithm for the rectangular packing problem. Int. Conf. on Computational Science, p.783-791.

[33]Zhang, Z.H., Wang, Y.S., Teng, H.F., et al., 2013. Parallel dual-system cooperative co-evolutionary differential evolution algorithm with human-computer cooperation for multi-cabin satellite layout optimization. J. Converg. Inform. Technol., 8(4):711-720.

[34]Zhou, C., Bhatt, R.N., 2005. Understanding and improving the Wang-Landau algorithm. Phys. Rev. E, 72(2):025701.

[35]Zhou, C., Gao, L., Gao, H.B., 2005. Particle swarm optimization based algorithm for constrained layout optimization. Contr. Dec., 20(1):36-40 (in Chinese).

Open peer comments: Debate/Discuss/Question/Opinion


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - Journal of Zhejiang University-SCIENCE