Computer Science ›› 2016, Vol. 43 ›› Issue (12): 287-292.doi: 10.11896/j.issn.1002-137X.2016.12.053

Previous Articles     Next Articles

Packing Method Based on Wang-Landau Sampling for Simplified Satellite Module with Static Non-equilibrium Constraints

LIU Jing-fa, HUANG Juan, JIANG Yu-cong, LIU Wen-jie and HAO Liang   

  • Online:2018-12-01 Published:2018-12-01

Abstract: With the background of the three-dimensional layout optimization problem on the bearing plate of the simplified satellite module,we studied the cylinder and cuboid mixed layout problem with static non-equilibrium constraints.To address this problem,the Wang-Landau sampling algorithm,which has been successful applied to statistic physics and the protein structure prediction problem,is introduced to solve the packing problem of satellite module at the first time.The Wang-Landau sampling algorithm can produce a flat histogram of energy by sampling the energies of the whole energy space effectively,so as to estimate the density of states of all possible energiesin the range accurately.By incorporating the steepest descent method with an accelerating strategy and the translation of the center of mass into the Wang-Landau sampling algorithm,an improved Wang-Landau sampling algorithm was proposed.The computational results of two classic instances from the literature show that the convergence rate and the quality of solution of the improved Wang-Landau sampling algorithm outperform other algorithms in literature.

Key words: Static non-equilibrium constraint,Wang-Landau sampling algorithm,Packing of satellite module,Steepest descent method

[1] Huang Wen-qi,Xu Ru-chu.Introduction to the modern theory of computation-background,foreground and solving method for the NP-hard problem[M].Beijing:Science Press,2004:47-70(in Chinese) 黄文奇,许如初.近世计算理论导引——NP难度问题的背景、前景及其求解算法研究[M].北京:科学出版社,2004:47-70
[2] Zhang De-fu,Han Shui-hua,Ye Wei-guo.A bricklaying heuristic algorithm for the orthogonal rectangular packing problem[J].Chinese Journal of Computers,2008,31(3):510-514(in Chinese) 张德富,韩水华,叶卫国.求解矩形Packing问题的砌墙式启发式算法[J].计算机学报,2008,1(3):510-514
[3] Ge Hong-wei,Liu Lin-ju.Rectangle-packing problem based on mo-dified particle swarm optimization algorithm[J].Computer Engineering,2009,35(7):186-188(in Chinese) 葛洪伟,刘林炬.基于改进粒子群优化算法的矩形Packing问题[J].计算机工程,2009,35(7):186-188
[4] Wei Li-jun,Zhang De-fu,Chen Qing-shan.A least wasted first heuristic algorithm for the rectangular packing problem[J].Computers and Operations Research,2009,36(5):1608-1614
[5] Liu Jing-fa,Li Gang.Basin filling algorithm for the circle pac-king problem with the static equilibrium constraints[J].Science China:Information Science,2010, 40(3):423-432(in Chinese) 刘景发,李刚.求解带平衡性能约束的圆形装填问题的吸引盘填充算法[J].中国科学:信息科学,2010,40(3):423-432
[6] Leung S C H,Zhang D F,Zhou C L,et al.A hybrid simulated annealing metaheuristic algorithm for the two-dimensional knapsack packing problem[J].Computers and Operations Research,2012,39(1):64-73
[7] Huang Wen-qi,Chen Mao.Note on:An improved algorithm for the packing of unequal circles within a larger containing circle[J].Computers and Industrial Engineering,2006,50(3):338-344
[8] Wang Yi-shou,Shi Yan-jun,Teng Hong- fei.An improved scatter search for circles packing problem with the equilibrium constraint[J].Chinese Journal of Computers,2009,2(6):1215-1219(in Chinese) 王奕首,史彦军,滕弘飞.用改进的散射搜索法求解带平衡约束的圆形Packing问题[J].计算机学报,2009,2(6):1215-1219
[9] Liu Jing-fa,Xue Sheng-jun,Liu Zhao-xia,et al.An improved ener-gy landscape paving algorithm for the problem of packing circles into a larger containing circle[J].Computers and Industrial Engineering,2009,57(3):1144-1149
[10] Li Zi-qiang,Tian Zhuo-jun,Wang Yi-shou,et al.A fast heuristic parallel ant colony algorithm for circles packing problem with the equilibrium constraints[J].Journal of Computer Research and Development,2013,49(9):1899-1909(in Chinese) 黎自强,田茁君,王奕首,等.求解平衡约束圆形Packing问题的快速启发式并行蚁群算法[J].计算机研究与发展,2013,49(9):1899-1909
[11] He Kun,Mo Dan-zeng,Xu Ru-chu,et al.A quasi-physical algorithm based on coarse and fine adjustment for solving circles packing problem with constraints of equilibrium[J].Chinese Journal of Computers,2013,36(6):1224-1234(in Chinese) 何琨,莫旦增,许如初,等.基于粗精调技术的求解带平衡约束圆形Packing问题的拟物算法[J].计算机学报,2013,36(6):1224-1234
[12] He Kun,Mo Dan-zeng,Ye Tao,et al.A coarse-to-fine quasi-physical optimization method for solving the circle packing problem with equilibrium constraints[J].Computers & Industrial Engineering,2013,66(4):1049-1060
[13] Xiao Ren-bin,Xu Yi-chun,Amos M.Two hybrid compactionalgorithms for the layout optimization problem[J].Biosystems,2007,90(2):560-567
[14] Liu Jing-fa,Li Gang,Geng Huan-tong.A new heuristic algo-rithm for the circular packing problem with equilibrium constraints[J].Science China:Information Science,2011,54(8):1572-1584
[15] Wang F,Landau D P.Efficient,multiple-range random walk algorithm to calculate the density of states[J].Physical Review Letters,2001,86(10):2050-2053
[16] Teng Hong-fei,Sun Shou-lin,Liu De-quan,et al.Layout optimization for the objects located within a rotating vessel-a three-dimensional packing problem with behavioral constraints[J].Computers and Operations Research,2001,28(6):521-535
[17] Liu Jing-fa,Gao Ze-xu,Long Yu-zheng,et al.Heuristic algo-rithm for the packing problem of satellite module with dynamic unbalance constraints[J].Journal of Computer-Aided Design & Computer Graphics,2014,26(8):1232-1239(in Chinese) 刘景发,高泽旭,龙羽正,等.求解带动不平衡约束的卫星舱布局问题的启发式算法[J].计算机辅助设计与图形学学报,2014,26(8):1232-1239
[18] Huo Jun-zhou,Li Guang-qiang,Teng Hong-fei,et al.Human-computer cooperative ant colony/genetic algorithm for satellite module layout design[J].Chinese Journal of Mechanical Engineering,2005,41(3):112-116(in Chinese) 霍军周,李广强,滕弘飞,等.人机结合蚁群/遗传算法及其在卫星舱布局设计中的应用[J].机械工程学报,2005,41(3):112-116
[19] Zhou Zi-ling.Heuristic layout algorithm foe meteorological satellite module with static non-equilibrium constraints[D].Nanjing:Nanjing University of Information Science & Technology,2013(in Chinese) 周子铃.带静不平衡约束的气象卫星舱的启发式布局算法[D].南京:南京信息工程大学,2013

No related articles found!
Full text



[1] LEI Li-hui and WANG Jing. Parallelization of LTL Model Checking Based on Possibility Measure[J]. Computer Science, 2018, 45(4): 71 -75, 88 .
[2] XIA Qing-xun and ZHUANG Yi. Remote Attestation Mechanism Based on Locality Principle[J]. Computer Science, 2018, 45(4): 148 -151, 162 .
[3] LI Bai-shen, LI Ling-zhi, SUN Yong and ZHU Yan-qin. Intranet Defense Algorithm Based on Pseudo Boosting Decision Tree[J]. Computer Science, 2018, 45(4): 157 -162 .
[4] WANG Huan, ZHANG Yun-feng and ZHANG Yan. Rapid Decision Method for Repairing Sequence Based on CFDs[J]. Computer Science, 2018, 45(3): 311 -316 .
[5] SUN Qi, JIN Yan, HE Kun and XU Ling-xuan. Hybrid Evolutionary Algorithm for Solving Mixed Capacitated General Routing Problem[J]. Computer Science, 2018, 45(4): 76 -82 .
[6] ZHANG Jia-nan and XIAO Ming-yu. Approximation Algorithm for Weighted Mixed Domination Problem[J]. Computer Science, 2018, 45(4): 83 -88 .
[7] WU Jian-hui, HUANG Zhong-xiang, LI Wu, WU Jian-hui, PENG Xin and ZHANG Sheng. Robustness Optimization of Sequence Decision in Urban Road Construction[J]. Computer Science, 2018, 45(4): 89 -93 .
[8] LIU Qin. Study on Data Quality Based on Constraint in Computer Forensics[J]. Computer Science, 2018, 45(4): 169 -172 .
[9] ZHONG Fei and YANG Bin. License Plate Detection Based on Principal Component Analysis Network[J]. Computer Science, 2018, 45(3): 268 -273 .
[10] SHI Wen-jun, WU Ji-gang and LUO Yu-chun. Fast and Efficient Scheduling Algorithms for Mobile Cloud Offloading[J]. Computer Science, 2018, 45(4): 94 -99, 116 .