资源描述：
《布局问题的模拟退火算法 - 副本.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、第10卷 第3期计算机辅助设计与图形学学报Vol.10,No.31998年5月J.CAD&CGMay,1998布局问题的模拟退火算法①①①②王金敏 陈东祥 马丰宁 查建中(①天津大学机械系 天津 300072)(②北方交通大学机械系 北京 100044)摘要 布局问题属于NP2完全问题已被研究多年.模拟退火法是一种新的通用启发式优化算法,现已广泛用于解决大规模集成电路逻辑布线设计、图象处理等组合优化问题.本文通过对布局问题及模拟退火算法的分析,将它们综合起来构成了求解布局问题的模拟退火算法.计算结果表明,本文算法得到的解优于传统优化方法所得到的解
2、;文章还通过实验对算法中各参数所起作用进行了论述.关键词 布局问题,模拟退火算法,爬山法,全局优化,NP2完全问题中图分类号 TH11ASIMULATEDANNEALINGPACKINGALGORITHM①①①②WANGJin2MinCHENDong2XiangMAFeng2NingCHAJian2Zhong(①DepartmentofMechanicalEngineering,TianjinUniversity,Tianjin300072)(②DepartmentofMechanicalEngineering,NorthernJiaotongU
3、niversity,Beijing100044)AbstractPackingproblemswhichbelongtoNP2completeproblemshavebeenstud2iedformanyyears.Asakindofnewheuristicoptimizationmethod,simulatedannealingalgorithmhasbeenappliedtosomecombintorialoptimizationproblemssuchasVLSIde2signandimageprocessing.Accordingtoth
4、eanalysisonpackingproblemsandsimulatedannealingalgorithm,thispaperpresentsasimulatedannealingpackingalgorithmwhichcanbeusedtosolvepackingproblems.Thecalculatingresultsshowthealgorithmcanobtainabettersolutionwhichcann′tbegottenbytraditionaloptimizatoinalgorithm.Thepaperalsodis
5、cussessomeparameter′srolesinthealgorithmbyseveralexamples.Keywordspackingproblems,simulatedannealingalgorithm,hillclimbing,globalop2timum,NP2completeproblems1996206221收稿,1997209216收到修改稿.本文得到国家自然科学基金资助(编号59475045).王金敏,1963年11月出生,博士,副教授,主要研究方向为智能布局、计算机辅助设计.陈东祥,硕士,副教授,主要研究方向为计算机
6、辅助设计及图形学.马丰宁,博士,副教授,主要研究方向为计算机辅助设计及系统工程.查建中,博士,教授,博士生导师,主要研究方向为计算机辅助设计、智能工程.©1995-2006TsinghuaTongfangOpticalDiscCo.,Ltd.Allrightsreserved.254计算机辅助设计与图形学学报1998年1 概 述自1831年高斯(Gauss)研究布局问题开始,虽然经过几代人的努力,但迄今尚无成熟的理论和有效的数值计算方法.所谓布局问题就是将一些物体按一定要求合理地放置在一个空间内,且使所占空间尽量地小.其中物体称为布局物件,空间称
7、为布局容器.布局问题广泛存在于航空航天工业、造船业、纺织业、玻璃加工业及交通运输等工业领域.由于布局问题属于NP2完全问题,因而吸引了大量研究人员对其进行深入的研究.[1]Udy利用序列二次规划和广义简约梯度法来解小型三维布局问题,但其解的质量过分[2]依赖于初始位置的选择.Kim和Gossard通过惩罚因子将布局约束转化为目标函数惩罚项,然后用无约束优化方法来求解.由于优化算法本身只能找到局部最优解,因而对于规模大或物体形状复杂的布局问题,局部最优的数目将急剧增加且其质量将急剧下降,即与全局最优解的差别越来越大.此外,布局问题中导数的求解也十分
8、困难.针对上述情况,本文利用一种新的通用启发式优化算法——模拟退火法来求解布局问题.通过对布局问题及模拟退火算法的分析,将它们结合起来构
