new energy landscape paving heuristic for satellite module layouts

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

Three-dimensional packing / Energy landscape paving / Layout optimization / Performance constraints

References

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

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

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

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

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

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

[7] Glover, F., 1990a. Tabu search—part I.Informs J. Comput., 1(1): 89–98.

[8] Glover, F., 1990b. Tabu search—part II.Orsa J. Comput., 2(1): 4–32.

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

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

[11] He, K., Zeng, M.D., Xu, R.C., , 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. http://dx.doi.org/10.3724/SP.J.1013.2013.01224

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

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

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

[15] Liu, J.F., Xue, S.J., Liu, Z.X., , 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. http://dx.doi.org/10.1016/j.cie.2009.05.010

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

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

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

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

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

[21] Rakshit, A., Bandyopadhyay, P., 2013. 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., 1021:206–214. http://dx.doi.org/10.1016/j.comptc.2013.07.023

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

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

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

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

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

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

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

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

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

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

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

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

[34] 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. http://dx.doi.org/10.1016/j.asoc.2007.03.004

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

RIGHTS & PERMISSIONS

2016 Zhejiang University and Springer-Verlag Berlin Heidelberg