基于tbb的并行模拟退火算法.pdf

中国科技论文在线http://www.paper.edu.cn

基于TBB的并行模拟退火算法#
董丽丽，李妮，龚光红*
（北京航空航天大学自动化科学与电气工程学院，北京100191）
摘要：模拟退火算洱是乜种通疄盠随机搜索算洱，扬功地解决了大规模盠组合优化和NP复
杂悃问题。但是随着问题规模增大和对解得质量觝求盠提高，所需时间也随之增大。本旣
提剖了引入多种群群体优化机制柠造并行算洱，并利疄TBB技术实琌了模拟退火算洱盠并
行，减少了运行时间，并且解盠质量有所提高。
关键词：人工智腙；模拟退火；并行；TBB
中图分类号：TP18

ParallelsimulatedannealingalgorithmbasedonTBB
DONGLili,LiNi,GongGuanghong
(AutomationScienceandElectricalEngineeringSchool,BeiHangUniversity,BeiJing100191)
Abstract:Simulatedannealingalgorithmisageneralrandomsearchalgorithm,andsuccessfully
resolvealarge-scalecombinatorialoptimizationproblemsandNPproblems.However,withthe
increaseofthemagnitudeoftheproblemsandqualityrequirements,thetimerequiredalsoincreases.
Inthispaper,withtheintroductionofmulti-colonyaoptimizemechanismtoformparallel
algorithm,TBBtechnologyisappliedtoachieveaparallelsimulatedannealing
algorithm.Consequently,therunningtimeisreducedandthequalityofsolutionisalso
improved.
Keywords:artificialintelligence;simulatedannealing;parallel;TBB

0引言
模拟退火算法是从某一较高初温开始，采用具有概率突跳特性的Metropolis接受准则在
解空间中进行随机搜索。随着温度的下降，重复抽样，直到整个过程各温度下的抽样稳定，
最终得到问题的全局最优解。其实质结构分为内外两层循环。内部的循环则在当前温度下重
复抽样，直到抽样稳定。为了保证能够达到平衡状态，内循环次数要足够大才行。最常见的
办法就是将内循环次数设为较大常数[1]，这就是系统最耗时的地方。标准的模拟退火算法仅
对一个解进行串行优化，其效率很难提高。因此，考虑引入多种群群体优化机制，构造多个
初始解并行求解模拟退火算法PSA[2](parallelsimulatedannealing)，以提高算法的效率。
1模拟退火算法
模拟退火算法源于对固体退火过程的模拟，采用Metropolois接受准则，并用一组称为
冷却进度表[3]的参数控制算法过程，使算法给处一个近似最优解。Metropolis接受准则使算

法跳离局部最优的陷阱。根据Metropolis准则，粒子在温度Tk时趋于平衡几率为

exp(−+ET/k)，其中E为温度Tk时的内能，+E为其改变量，k为Boltzmann常数。将内
能E模拟为目标函数值f,温度T演化成控制参数t。由初始解i和控制参数初值t开始,对
当前解重复“产生新解→计算目标函数差→判断是否接受→接受或舍弃”的迭代,并逐步衰

基金项目：教育部博士点基金项目（20091102120013）
作者简介：董丽丽（1986-），女，硕士生，计算机仿真.E-mail:[e-mail]

-1-
中国科技论文在线http://www.paper.edu.cn

减t值,算法终止时的当前解即为所得近似最优解。
模拟退火算法的计算步骤如下描述[4]：

第1步：初始化，任选初始状态i，给定初始温度T0和终止温度Tf，令k=0,Tk=T0；
第2步：随机产生一个领域解j，计算目标值增量+ffjfi=()−()；

第3步：若+f<0,令ij=转第4步；否则产生α=U(0,1)，若exp(−>+fT/k)α，
则令ij=；
第4步：若达到热平衡（内循环次数到达L）转到第5步；否则转到第2步；

第5步：降低Tk，kk=+1，若Tk<Tf,则算法停止，否则转到第2步。
由上面的步骤可知，模拟退火算法具有内在的串行性。每一步循环中，状态改变都是在
前一步