基于线程构造模块的多核并行模拟退火方法

摘要

本发明公开了一种基于线程构造模块的多核并行模拟退火方法，主要解决模拟退火算法在大规模工程应用中的运行效率问题和对计算机多核资源的利用问题。利用线程构造模块支持多核处理器并行计算和支持扩展的线程嵌套并行的优点，并在原有的串行模拟退火算法基础上引入多种群群体优化机制构造并行算法。首先设置环境变量，然后构造并行模块，接着设定初始参数，再进行各个初始状态独立寻优，然后获取当前最优状态和最优结果，接着执行降温过程，最后获得最优状态和最优结果。本发明设计过程简单灵活，易于扩展，符合计算机朝着多处理器及多核架构的发展趋势，是一种方便快速、实用性强的并行模拟退火设计方法。

主权项

1、一种基于线程构造模块的多核并行模拟退火方法，其特征在于，该方法包括如下步骤：步骤一：设置环境变量；线程构造模块TBB并行数据处理平台的安装与环境设置，在计算机里置入线程构造模块TBB的文件包，并在Visual C++即VC目录中添加线程构造模块TBB的包含文件.include、库文件.lib及可执行文件.bin；步骤二：构造并行模块；首先，确定并行处理模块，改进的模拟退火中初始温度的确定、各个初始状态寻优和更新最优结果的过程都是并行处理的，再结合实际问题，找到实际问题中能够并行处理的部分；然后，根据线程构造模块TBB并行模板规范类构造并行模块；步骤三：设定初始参数；设置问题规模，即初始状态个数、内循环长度、温度收敛系数、目标函数；调用计算初始温度的parallel_for并行模块，并设置初始状态及对应的目标函数值，从初始状态对应的目标函数值中选出最小值作为最优结果，并得到对应的最优状态；步骤四：各个初始状态独立寻优；调用parallel_for设计的各个初始状态搜寻路径模块，该模块能够实现各个初始状态在一次内循环中的并行寻优；具体寻优过程是：每个初始状态随机生成候选状态，根据Metropolis接受准则，判断是否接受候选状态，接受则作为下次循环的初始状态，并得到初始目标函数值；否则初始状态不变；其中Metropolis接受准则是指随机生成一个位于0到1之间的随机数ε∈(0，1)，若exp(-Δf/T)＜ε，则接受候选状态，否则不接受，Δf表示候选状态的目标值与初始状态的目标值的差值，T表示当前温度，ε是一个位于0到1之间的随机数；步骤五：获取当前最优状态和最优结果；调用parallel_reduce并行模块，将最优结果和各个初始状态对应的目标函数值比较，如果目标函数值中的最小值小于最优结果，则将该最小值及对应的状态赋给最优结果和最优状态，否则最优结果和最优状态不变；步骤六：执行降温过程；降低温度，判断温度是否到达最低温度，若温度已到达最低温度，则执行步骤七，否则执行步骤四；步骤七：获得最优状态和最优结果；结束，最终寻到实际问题中的最优状态及最优结果。