基于gpu加速的细粒度并行模拟退火算法

《基于gpu加速的细粒度并行模拟退火算法》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、基于GPL_加速的细粒度井行模拟退火算法题。一般TsP问题可以描述为带权完全图G=(Ⅳ，R)，Ⅳ为城市节点集，月为边集。事实上非完全图也可以描述为完全图，只需要令那些不存在的边的权值足够大。每条边(j，，)∈R赋予权值，城市f与』之间的距离d。f，，∈Ⅳ，我们的目标就是找到该图的哈密尔顿回路．即其长度虽短，并且访问每个节点一次且仅有一次。所以TsP问题的最优解应该是所有城市节点号{1，2，，”}的一个置换口，并且，忙)虽小，如公式(11)所示。盟，(石)=∑d，(。)。(件1)+d，n"(1)(1．1

2、)#112模拟退火算法的起源sA算法的思想最早是由NMe昀polis等人提出的。在1983年由s．1(i蛳“ck等人和vc廿ny分别提出把它用于组合优化领域，目前已在各个领域中得到了广泛的实际应用口m”。sA算法用于解决组合优化问题的想法，足基于物理中固体物质的退火过程与一般组合优化问题间的相似性，图ll描述了组合优化与固体降温的相似性。固体降温离散函数求最小值幽l'1组台优化与州体降温的相似性Hg11ThesimilanHof＆⋯11“gandopnmizallon在对固体物质进行退火处理时，通常先

3、把固体加热至足够高的温度，同体中的粒子运动加剧而使固体的总内能变大。然后随着温度的逐渐下降，粒子也逐渐减慢运动而渐趋有序状态。若温度下降的速度足够慢，则固体物质的总内能一定能够达到最小。在加热过程中，固体物质的粒子随着温度变大而逐渐由有序状态变为尤序状状态，并且固体物质的总内能也逐渐增大。在降温过程中，只要温度下降地足够慢，固体粒子会慢慢变大连理工大学硕士学位论文得有序，并且在每个温度下都能够达到平衡态，最后在常温时达到基态，此时固体物质的总内能减为最小。在固体加热过程中，固体中粒子的运动逐渐加快，固

4、体的总内能也随着增大，从而粒子更加剧烈的运动使其离开原来位置，随温度的升高粒子由原来的有序状态变为无序状状态，如图1．2所示。AffrNucleus图1．2粒子运动规律Fig．1．27nledisciplinadanofparticlemotion在等温过程中，与周围环境交换热量不变，固体内能本能地由高内能向低内能的方向进行，当固体内能达到最小时，系统达到平衡状态，即固体粒子变成有序状态。在降温过程中，粒子热运动减弱，粒子逐渐趋于有序，最后在常温下达到基态，同时内能也减为最小。表1．1物理退火与组合优

5、化的相似性Tab．1．1Tllesimilari够ofannealingandoptimization物理退火组合优化粒子状态能量最低态冷却过程等温过程解最优解控制参数的下降Metmpolis抽样过稃一5一基于GPU加速的细粒度并行模拟退火算法物理固体退火与组合优化的相似性归纳如表1．1所示，用固体退火模拟组合优化问题，将内能E模拟为目标函数值厂，温度丁演化成控制参数f，即得到解组合优化问题的SA算法：由初始解f和控制参数初值f开始，从初始解的领域中随机产生一个新解，接受准则允许目标函数在一定范围内接

6、受使目标函数恶化的解，算法持续进行“产生新解一计算目标函数差一判断是否接受新解一接受或舍弃”的迭代过程，固体在某一恒定温度下趋于热平衡的过程，经过大量的解变化后，可以求出给定控制参数丁值的时候优化问题的相对最优解，然后逐步衰减f值，重复执行上述迭代过程。当算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由一组称作冷却进度表(CoolingscheduIe)的参数控制，包括控制参数的初始值丁以及衰减因子口、每个f值时的迭代次数(称为一个Markov链的长

7、度)￡和终止条件go1．3模拟退火算法的流程SA算法从高温开始，采用Me仃opolis接受准则在解空间进行随机搜索，随着温度的逐渐下降重复抽样过程，每温度下的抽样都达到稳定，当算法结束时所求得的最优解就作为全局近似最优解。其中，所求问题的一个解s；与固体物质的一个微观状态f以及其目标函数厂(s，)与固体物质的能量E相对应。假设随着算法逐渐减少的控制参数r与固体退火过程中的温度变化相对应，从而在每个丁取值下，算法采用Metropolis接受准则，连续执行“产生新解一判断是否接受一接受或舍弃”的迭代过程，

8、直到达到该温度下的稳定状态。算法实现步骤如下：(1)参数初始化：给定控制参数r的初始值瓦及随机产生初始解状态s。以及厂(s。)，在同一温度下采用相同的迭代次数厶=∥木咒2(七=1，2，⋯)其中∥≥1为一整数，如∥=100，刀为城市数，温度衰减系数口，令当前温度r=瓦，终止条件g。令s，=％，并计算目标函数值厂(J；)。(2)参数丁=r(后)时，按照下面过程进行厶次试探查询：①根据当前解足领域产生一个随机向量z。(对于连续变量)或随机偏移量，，l(对于离散