模拟退火算法在动态设施布置中的应用研究

接受新布置的概率确定。用模拟退火算法来解决DFLP的最优化问题，首先要确定的是接受新布置的概率。接受概率如下：
P（△Tc）=exp（－△Tc/Tc）
Tc=T0αr-1　　 r=1，2，…，R
　　其中：Tc表示当前温度，△Tc表示总成本的改变量(如果邻域解的成本比当前解的成本低，则△Tc=f（y′）-f（y）)，T0是初始温度，α为降温率，通常为0.9，r-1为温度降低的数量。设x是0～1之间的随机数，且x 　　（2）初始温度的确定。SA启发式需要设置参数，用来降低当前温度以进行寻优。在程序执行的初期，接受邻域解的概率较高，这是初始温度的高低造成的。初始温度选得太高，则算法的计算量增加许多；反之，初始温度选得太低，则一旦算法落入局部最优解的陷阱中就无法再跳出来，从而无法求得全局近似最优解。本文采用如下公式确定初始温度：
T0=-△Tc/1n（p（△Tc））=-0.01f（y0）/1n（0.25）
　　其中：T0表示初始温度，f(y0)表示初始解的成本。
3.2 DFLP中的算法描述
　　模拟退火算法是一种随机算法，在降温的过程中，须执行一系列的成对交换，确保系统处于稳定状态。把SA启发式算法直接应用于DFLP的思想，叫做SAI，其步骤如下：
步骤0：把每阶段的流量矩阵、长度矩阵和再布置成本作为输入数据，确定SA参数：设T0为初始温度，α为降温率，A为每次温度变化时产生的变化数量，Tmin为最低温度。
步骤1：假定存在温度变化产生器r，置r=1。
步骤2：①产生初始解y0，并将其赋予当前解（即置y=y0）；②产生当前解的成本f（y）；③设置下列参数：best__sol=y；best__cost=f（y）。
步骤3：给每个温度改变次数赋予初值：i=0，根据退火调度设置当前温度，Tc=T0αr-1，如果Tc 步骤4：①随机选取区段t，然后随机选取其中的两个设施u和v，相互交换其位置，得到的解设为y′，置i=i+1；②计算总成本的改变量：△Tc=f（y）-f（y）。
步骤5：if（ΔTc<0）or（ΔTc>0 and x=random（0，1）f（y），then best__cost=f（y）and best sol=y。
步骤6：if i=A，then update r=r+1返回步骤3，否则返回步骤4。
以上的启发式参数最初的α、A和Tmin由试验得出，Tmin的值取0.01（Tmin=0.01）。由于p（ΔTc）=exp（-VTc/Tc）以及Tc=T0，r=1。
在步骤2中，初始解或布置规划y的值y0=[αx0（1），αx0（2），…，αx0（f）]，初始解中的n元矢量αx0（f）代表了t阶段的初始布置规划，其中t=1，2，…，T。另外αx0（f）=[x0（1），x0（2），…，x0（N）]，其中的元素x0（i）是矢量，代表部门i的位置，i=1，2，…，N。例如，有6个部门的初始布置中，第一阶段：αx0（1）=[1，2，3，4，5，6]，如果这个任务还用于阶段2和阶段3，αx0（1）=αx0（2）=αx0（3），则没有再布置成本。简言之，在阶段1、2、3，设施1、2、3、4、5和6被布置在1、2、3、4、5、和6几个位置。步骤2和3中，启发式参数和数值被初始化，如果达到终止条件（即Tc0（即f（y′）>f(y))且x 3.3 改进的模拟退火算法在DFLP中的应用
　　从上面的步骤中得知，把模拟退火的思想直接应用于DFLP中求最优解的方法，比较复杂，计算机执行的效率也比较低，本文把这种思想称为SAⅠ。针对SAⅠ复杂和执行效率的缺点，在SAⅠ基础上添加了正反馈技术的算法用于求解DFLP最优化问题，把这种思想称为SAⅡ。
　　SAⅡ执行SAⅠ的1-6步骤，区别是在步骤5包含了正反馈技术，在步骤4重复执行完随机成对交换（随机选择阶段t和其中的两个部门u和v进行交换）以后，获取邻域解y′。同时，获取总成本改变量ΔTc。
由于SAⅡ和SAⅠ的唯一不同点在于步骤5，虽然SAⅡ启发式执行更多的步骤，但SAⅡ因需要较少的重复次数获取高质量的解，从而在计算上更有效率。
4 结语
　　模拟退火算法作为一种有效的全局优化算法，正以其思路清晰、原理简单、使用灵活得到广泛应用。随着全局优化技术不断发展，新的优化机制、技术和方法不断涌现，作为基础算法的模拟退火算法亦可充分发挥其串行优势，自身不断改进的同时不断与新的优秀算法结合,得出更合理、有效的混合优化算法。由于在中文文献中，暂时很少有人用模拟退火算法解决DFLP问题，本文提出用模拟退火算法求解DFLP最优解的思想，以供参考。
参考文献
1 Alan R，McKendall Jr etc.Simulated annealing heuristics for the dynamic facility layout problem[J]. Computers & Operations Research,2005（6） 来源：778论文在线  www.qiqi8.cn
2 吴斐,侯云章.基于启发式结果的模拟退火算法在布局问题中的应用[J].物流技术，2005（6）
3 王金敏．布局问题的模拟退火算法[J].计算机辅助设计与图形学学报,1998(3)
4 谢云.模拟退火算法综述[J].微计算机信息,1998(4)

    

上一页  [1] [2]