用改进的散射搜索法求解带平衡约束的圆形packing问题

《用改进的散射搜索法求解带平衡约束的圆形packing问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《计算机学报》2009年6期用改进的散射搜索法求解带平衡约束的圆形Packing问题王奕首1),2)史彦军1)滕弘飞1),3)1)(大连理工大学机械工程学院，大连，116024)2)(大连理工大学航空航天学院，大连，116024)3)(大连理工大学计算机科学与工程系，大连，116024)摘要：以卫星布局为背景的带平衡约束的圆形packing问题属NP难问题。本文用给出的改进的散射搜索方法求解。一是给出基于极坐标变换的散射搜索多样性生成策略，二是采取基于极角和极径差异度的参考集更新策略，三是用梯度下降法和

2、Nelder-Mead直接搜索法分别作为散射搜索法中不同阶段所产生新解的改进方法，从而构成改进的散射搜索法，提高了散射搜索法的探索和搜索能力。数值实验结果表明了该改进散射搜索法的可行性和有效性。关键词：带平衡约束Pakcing问题，散射搜索，局部搜索，启发式方法中图分类号：TP391AnimprovedscattersearchforcirclespackingproblemwiththeequilibriumconstraintWANGYi-Shou1),2)SHIYan-Jun1)TENGHong-

3、Fei1),3)1)(SchoolofMechanicalEngineering,DalianUniversityofTechnology,Dalian116024)2)(SchoolofAeronauticsandAstronautics,DalianUniversityofTechnology,Dalian116024)3)(DepartmentofComputerScienceandEngineering,DalianUniversityofTechnology,Dalian116024)Abst

4、ract:Theequilibrium-constrainedcirclespackingproblemwiththebackgroundofsatellitemodulelayoutdesignbelongstoNP-hardproblem.Weextendscattersearch(SS)todealwiththisproblem,andproposetheimprovedscattersearch.Weempiricallystudythecoordinatetransformation-base

5、ddiversificationmethodandthereferencesetupdatemethodonthebasisoftwodissimilarities.ThenweadaptthegradientdescentalgorithmandNelder–MeadsimplexalgorithmtoimprovethetrialsolutiongeneratedattwodifferentstagesinSS,respectively.Theimprovedscattersearchcanmake

6、atradeoffbetweenexplorationandexploitation.Experimentresultsshowthefeasibilityandeffectivenessoftheimprovedscattersearch.Keywords:Equilibriumconstrainedpackingproblem;Scattersearch;Localsearch,Heuristicmethod9《计算机学报》2009年6期1引言收稿日期：2007-1-27.修改稿收到日期：2008-

7、11-18.本课题得到国家自然科学基金项目(No.50275019,No.50575031,No.60674078)和国家高技术研究发展计划项目(No.2006AA04Z109)资助.王奕首，男，1978年生，博士研究生，主要研究方向为航天器布局，演化计算和知识融合.E-mail：yishouwang@gmail.com.史彦军，男，1973年生，博士，讲师，主要研究方向为布局设计，演化计算.滕弘飞，男，1936年生，教授，博士生导师，主要研究方向为CAD及优化，布局设计，计算智能和知识融合.E-mai

8、l：tenghf@dlut.edu.cn.Packing问题是经典的组合优化问题，属于NP-Hard问题，在制造、物流、网络通信、航天(如卫星舱布局)等领域有广泛应用[1-3]。本文主要研究带平衡约束的圆形Packing问题，属约束布局优化问题，其应用背景是在一个带自旋的返回式卫星舱内，布置仪器、设备等有效载荷(简称为待布物)，使得待布物互相不干涉，空间利用率高，且系统质心要尽量靠近卫星舱的中心轴线，使得卫星舱的静不平衡量尽可能小[3]。1