模拟退火算法综述(3)

综合性介绍模拟退火算法

　　　　　　　　　　　　　　　　　《微计算机信息》1998年第14卷第5期

lem)、独立集问题(IndependentSetProblem)、图着

成试验的处理机直接对公共存贮区的当前解进行下一轮试验,此时其它处理机可能会修改当前解,各处理机的结果可能发生混乱,但随着控制参数t值的减小,接受概率越来越小,解也渐趋有序直至最终排除混乱。如图2所示,其中每条线段表示一个试验,在线段错开处可能发生混乱。

对上述并行策略,操作并行中可并行的步骤数受具体问题的限制,整个算法只能同步并行,但不同步骤可分别并行。独立试验并行实际上相当于P台单机分别串行,最后从P个结果中选出最优者所以并不能。(,5(,可望得到较好的解或较高,虽然该方法仍是同步并行的,但可较好的发挥并行计算的优越性,是一种很好的并行方法。区域分裂是完全异步并行的,加速和效率都很高,是一种较好的并行方法,但要求定义空间允许分裂,同时分裂方法还要能反映整体优化要求(如TSP就要求分裂的各个区间必须相变),此外,区域分裂法也包含有混乱松驰的思想。混乱松驰法采用“不怕出错”的思想,是一种高效的异步并行算法,但其渐近收敛性尚待进一步研究,此外,此方法在实际应用时需作适当调整,避免进程中的混乱影响最终结果。　　

色问题(GraphColouringProblem)、调度问题

(SchedulingProble)、划分问题(PartitionProblem)以及布局问题(PlacementProblem),均以较高的效率得到了较好的结果。　　

六并行策略

模拟退火算法是一种随机近似算法,所求解的质

量有赖于大量的试验。随着问题规模的增大和对解的质量要求的提高,所需时间也随之增长,而冷却进度表并不能从根本上提高算法的效率,解决的办法是将算法并行实现以提高其性能。

算法中每轮试验的后三个步骤均依赖于前一步聚的结果,故四个步骤只能串行执行,组合优化问题的特点,。

(1):P,1所示,其

。

图1操作并行示意图

(2)试验并行:由多个处理机同时并行试验,根据

对各处理机的中间结果是否综合取舍,又分为两种形式。

独立试验并行,由P台处理机各自独立地试验并完成整个算法,最后比较所得的P个结果并从中选出最优者。

协同试验并行:P台处理机同时开始试验,分别产生P个新解并作出判断,对所有满足接受准则者按某个法则5选择一个接受,其余的全部舍弃,再在此基

础上进行下一轮试验。

七结论

综上所述,模拟退火算法是一种通用、高效、健壮、

可行的拟物型随机近似算法,并且可以较容易地并行实现以进一步提高运行效率,适合求解大规模组合组合优化问题特别是NP完全问题,因此具有很大的实用价值。同时由于其讨论涉及随机分析、Mapkob理论、渐近收敛性、统计分析方法和并行算法等学科,所以其研究还具有重要的理论意义,此外,对模拟退火算法作一些局部或策略上的修改,还可得到一些推广或变异形式,此外不再赘述。

作者简介谢云,荆州师范高等专科学校计算机系主任、副教授,武汉大学计算机软件工程国家重点实验室客座研究员,湖北省有突出贡献的中青年专家。主要从事计算机软件和并行算法研究。参加了八六三项目“非数值计算的并行算法”并负责模拟退火算法的研究。

(收稿日期:98,6,10)

图2混乱松驰并行示意图

(3)区域分裂并行:将定义空间分裂成P个子空

间,由P台处理机分别在这些子空间上试验。

(4)混乱松驰并行:各处理机同时开始试验,先完

—68—