多阶段协同求解卫星舱耦合布局优化问题的双邻域人工蜂群算法
|
摘要
针对三维卫星舱布局优化问题(three-dimensional satellite module layout optimization problem,3DSMLOP),本文提出了一种具有双邻域的改进人工蜂群算法,并将其与多阶段求解策略结合,形成多阶段双邻域人工蜂群算法(multi-stage dual neighborhood artificial bee colony algorithm,MS-DABC).3DSMLOP是一个复杂的多约束耦合问题,其解空间是非连续、非线性、多模态的.MS-DABC将3DSMLOP分解为多个子系统,并根据优化目标在各个子系统之间的耦合关系,将优化过程分为两个阶段.第一阶段,针对无耦合的优化目标,各个子系统利用具有双邻域结构的改进人工蜂群算法独立进行优化.在第一阶段求得的最优解的基础上,第二阶段采用一般人工蜂群算法来优化子系统的旋转角度,利用各个子系统之间的协同旋转来解决耦合的优化目标.仿真实验结果表明,该算法求解复杂的卫星舱布局问题非常有效,在3DSMLOP算例求解上性能突出.
This paper presents an improved artificial bee colony algorithm with dual neighborhood, and combines it with a multi-stage solving strategy to form a multi-stage dual neighborhood artificial bee colony algorithm(MS-DABC) for the three-dimensional satellite module layout optimization problem(3DSMLOP). 3DSMLOP is a complex multi-constrained coupling problem whose solution space is non-continuous, non-linear, multi-modal.MS-DABC decomposes 3DSMLOP into several subsystems, and divides the optimization process into two stages according to the coupling relationship on optimization goals between subsystems. In the first stage, each subsystem uses the dual neighborhood artificial bee colony algorithm(DABC) to optimize no-coupling optimization goals independently. Based on the optimal solution obtained in the first stage, the coupling optimization goals are solved by the collaborative rotation between the subsystems in the second stage. The rotation angles are optimized by the artificial bee colony algorithm. Numerical experiment results show that MS-DABC is very effective and has outstanding performance for solving the 3DSMLOP example.
This paper presents an improved artificial bee colony algorithm with dual neighborhood, and combines it with a multi-stage solving strategy to form a multi-stage dual neighborhood artificial bee colony algorithm(MS-DABC) for the three-dimensional satellite module layout optimization problem(3DSMLOP). 3DSMLOP is a complex multi-constrained coupling problem whose solution space is non-continuous, non-linear, multi-modal.MS-DABC decomposes 3DSMLOP into several subsystems, and divides the optimization process into two stages according to the coupling relationship on optimization goals between subsystems. In the first stage, each subsystem uses the dual neighborhood artificial bee colony algorithm(DABC) to optimize no-coupling optimization goals independently. Based on the optimal solution obtained in the first stage, the coupling optimization goals are solved by the collaborative rotation between the subsystems in the second stage. The rotation angles are optimized by the artificial bee colony algorithm. Numerical experiment results show that MS-DABC is very effective and has outstanding performance for solving the 3DSMLOP example.
引文
1 Teng H F,Sun S L,Ge W H,et al.Layout optimization for dishes installed on a rotating circular table–the packing problem with equilibrium behavioral constraints.Sci Sin Math,1994,24:754–760[滕弘飞,孙守林,葛文海,等.转动圆桌平衡摆盘——带平衡性能约束的Packing问题.中国科学:数学,1994,24:754–760]
2 Xiao R B,Xu Y C,Amos M.Two hybrid compaction algorithms for the layout optimization problem.Bio Systems,2007,90:560–567
3 Wang Y S,Shi Y J,Teng H F.An improved scatter search for circles packing problem with the equilibrium constraint.Chin J Comput,2009,32:1214–1221[王奕首,史彦军,滕弘飞.用改进的散射搜索法求解带平衡约束的圆形Packing问题.计算机学报,2009,32:1214–1221]
4 Liu J F,Li G.Basin filling algorithm for the circular packing problem with equilibrium behavioral constraints.Sci Sin Inform,2010,53:885–895[刘景发,李刚.求解带平衡性能约束的圆形装填问题的吸引盘填充算法.中国科学:信息科学,2010,40:423–432]
5 Li G,Liu J F.Heuristic algorithm based on tabu search for the circular packing problem with equilibrium constraints.Sci Sin Inform,2011,41:1076–1088[李刚,刘景发.基于禁忌搜索的启发式算法求解带平衡约束的圆形装填问题.中国科学:信息科学,2011,41:1076–1088]
6 Li Z Q,Tian Z J,Wang Y S,et al.A fast heuristic parallel ant colony algorithm for circles packing problem with the equilibrium constraints.J Comput Res Dev,2012,49:1899–1909[黎自强,田茁君,王奕首,等.求解平衡约束圆形packing问题的快速启发式并行蚁群算法.计算机研究与发展,2012,49:1899–1909]
7 Huang Z D,Xiao R B.An emergent computation approach to the problem of polygon layout with performance constraints.Phys A,2013,392:5074–5088
8 He K,Mo D Z,Xu R C,et al.A quasi-physical algorithm based on coarse and fine adjustment for solving circles packing problem with constraints of equilibrium.Chin J Comput,2013,36:1224–1234[何琨,莫旦增,许如初,等.基于粗精调技术的求解带平衡约束圆形packing问题的拟物算法.计算机学报,2013,36:1224–1234]
9 Huang W Q,He K.Apure quasi-human algorithm for solving cuboid packing problem.Sci China Ser F-Inf Sci,2009,39 :617–622[黄文奇,何琨.求解长方体packing问题的纯粹拟人算法.中国科学F辑:信息科学,2009,39:617–622]
10 Zhang D F,Peng Y,Zhu W X,et al.A hybrid simulated annealing algorithm for the three-dimensional packing problem.Chin J Comput,2009,32:2147–2156[张德富,彭煜,朱文兴,等.求解三维装箱问题的混合模拟退火算法.计算机学报,2009,32:2147–2156]
11 Li W,Huang W Q,Jiang D C,et al.A heuristic algorithm for cube packing with time schedule.Sci Sin Inform,2010,53 :18–29[李未,黄文奇,蒋东辰,等.一种求解带有时间调度的四维长方体装填问题的启发式算法.中国科学:信息科学,2010,40:1–12]
12 Szykman S,Cagan J.Constrained three–dimensional component layout using simulated annealing.J Mech Design,1997,119:28–35
13 Braun R D,Moore A A,Kroo I M.Collaborative approach to launch vehicle design.J Spacecraft Rockets,1997,34:478 –486
14 Grignon P M,Fadel G M.A GA based configuration design optimization method.J Mech Design,2004,126:6–14
15 de Sousa F L,Muraoka I,Galski R L.On the optimal positioning of electronic equipment in space platforms.In:Proceedings of the 19th International Congress of Mechanical Engineering,Brasilia,2007.5–9
16 Sun Z G,Teng H F.Optimal layout design of a satellite module.Eng Optimiz,2003,35:513–529
17 Zhang B,Teng H F,Shi Y J.Layout optimization of satellite module using soft computing techniques.Appl Soft Comput,2008,8:507–521
18 Wang Y S,Teng H F,Shi Y J.Cooperative coevolutionary scatter search for satellite module layout design.Eng Computations,2009,26:761–785
19 Teng H,Chen Y,Zeng W,et al.A dual-system variable-grain cooperative coevolutionary algorithm:satellite-module layout design.IEEE T Evolut Comput,2010,14:438–455
20 Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Optimization.Kayseri:Erciyes University.Technical Report TR06.2005
21 Karaboga D,Basturk B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm.J Global optim,2007,39:459–471
22 Li J Q,Pan Q K,Gao K Z.Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems.Int J Adv Manuf Tech,2011,55:1159–1169
23 Karaboga D,Akay B.A comparative study of artificial bee colony algorithm.Appl Math Comput,2009,214:108–132
2 Xiao R B,Xu Y C,Amos M.Two hybrid compaction algorithms for the layout optimization problem.Bio Systems,2007,90:560–567
3 Wang Y S,Shi Y J,Teng H F.An improved scatter search for circles packing problem with the equilibrium constraint.Chin J Comput,2009,32:1214–1221[王奕首,史彦军,滕弘飞.用改进的散射搜索法求解带平衡约束的圆形Packing问题.计算机学报,2009,32:1214–1221]
4 Liu J F,Li G.Basin filling algorithm for the circular packing problem with equilibrium behavioral constraints.Sci Sin Inform,2010,53:885–895[刘景发,李刚.求解带平衡性能约束的圆形装填问题的吸引盘填充算法.中国科学:信息科学,2010,40:423–432]
5 Li G,Liu J F.Heuristic algorithm based on tabu search for the circular packing problem with equilibrium constraints.Sci Sin Inform,2011,41:1076–1088[李刚,刘景发.基于禁忌搜索的启发式算法求解带平衡约束的圆形装填问题.中国科学:信息科学,2011,41:1076–1088]
6 Li Z Q,Tian Z J,Wang Y S,et al.A fast heuristic parallel ant colony algorithm for circles packing problem with the equilibrium constraints.J Comput Res Dev,2012,49:1899–1909[黎自强,田茁君,王奕首,等.求解平衡约束圆形packing问题的快速启发式并行蚁群算法.计算机研究与发展,2012,49:1899–1909]
7 Huang Z D,Xiao R B.An emergent computation approach to the problem of polygon layout with performance constraints.Phys A,2013,392:5074–5088
8 He K,Mo D Z,Xu R C,et al.A quasi-physical algorithm based on coarse and fine adjustment for solving circles packing problem with constraints of equilibrium.Chin J Comput,2013,36:1224–1234[何琨,莫旦增,许如初,等.基于粗精调技术的求解带平衡约束圆形packing问题的拟物算法.计算机学报,2013,36:1224–1234]
9 Huang W Q,He K.Apure quasi-human algorithm for solving cuboid packing problem.Sci China Ser F-Inf Sci,2009,39 :617–622[黄文奇,何琨.求解长方体packing问题的纯粹拟人算法.中国科学F辑:信息科学,2009,39:617–622]
10 Zhang D F,Peng Y,Zhu W X,et al.A hybrid simulated annealing algorithm for the three-dimensional packing problem.Chin J Comput,2009,32:2147–2156[张德富,彭煜,朱文兴,等.求解三维装箱问题的混合模拟退火算法.计算机学报,2009,32:2147–2156]
11 Li W,Huang W Q,Jiang D C,et al.A heuristic algorithm for cube packing with time schedule.Sci Sin Inform,2010,53 :18–29[李未,黄文奇,蒋东辰,等.一种求解带有时间调度的四维长方体装填问题的启发式算法.中国科学:信息科学,2010,40:1–12]
12 Szykman S,Cagan J.Constrained three–dimensional component layout using simulated annealing.J Mech Design,1997,119:28–35
13 Braun R D,Moore A A,Kroo I M.Collaborative approach to launch vehicle design.J Spacecraft Rockets,1997,34:478 –486
14 Grignon P M,Fadel G M.A GA based configuration design optimization method.J Mech Design,2004,126:6–14
15 de Sousa F L,Muraoka I,Galski R L.On the optimal positioning of electronic equipment in space platforms.In:Proceedings of the 19th International Congress of Mechanical Engineering,Brasilia,2007.5–9
16 Sun Z G,Teng H F.Optimal layout design of a satellite module.Eng Optimiz,2003,35:513–529
17 Zhang B,Teng H F,Shi Y J.Layout optimization of satellite module using soft computing techniques.Appl Soft Comput,2008,8:507–521
18 Wang Y S,Teng H F,Shi Y J.Cooperative coevolutionary scatter search for satellite module layout design.Eng Computations,2009,26:761–785
19 Teng H,Chen Y,Zeng W,et al.A dual-system variable-grain cooperative coevolutionary algorithm:satellite-module layout design.IEEE T Evolut Comput,2010,14:438–455
20 Karaboga D.An Idea Based on Honey Bee Swarm for Numerical Optimization.Kayseri:Erciyes University.Technical Report TR06.2005
21 Karaboga D,Basturk B.A powerful and efficient algorithm for numerical function optimization:artificial bee colony(ABC)algorithm.J Global optim,2007,39:459–471
22 Li J Q,Pan Q K,Gao K Z.Pareto-based discrete artificial bee colony algorithm for multi-objective flexible job shop scheduling problems.Int J Adv Manuf Tech,2011,55:1159–1169
23 Karaboga D,Akay B.A comparative study of artificial bee colony algorithm.Appl Math Comput,2009,214:108–132