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

《模拟退火算法在动态设施布置中的应用研究 》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、模拟退火算法在动态设施布置中的应用研究摘要制造业必须以运营效率和快速的反应适应产品的复杂化和需求。探讨了对生产部门间制造设施的布置和重组，以使物料搬运和重组成本最小化，进而提出动态设施布置问题及资源的有效组合和配置，确保设施间的物流通畅和提高企业生产效率。　　关键词模拟退火启发式动态设施布置　　静态设施布置问题（staticfacilitylayoutproblem，SFLP）被认为是解决设施布置的有效方法。资源（如机器、部门或者劳动力）的有效组合和配置，可以确保设施间的物流通畅和提高企业生产效率。当设施

2、间的物流量在布置范围内变化时，SFLP就成了动态。这就是由Rosenblatt首次提出的著名的动态设施布置问题（dynamicfacilitylayoutproblem，DFLP）。　　启发式算法成功发展之前，曾经用禁忌搜索技术、遗传算法等工具来求解大型组合优化问题。换言之，就是利用最速下降成对交换启发式（steepest-descentpairinistic），设施的面积和位置的大小一致，布置类型为已知的（即如附图为2×3的布置）；部门之间的距离确定为一个单位。　　关于DFLP问题的求解，本文在Urba

3、n提出的最速下降成对交换启发式解法之上，提出用一种通用的模拟退火算法和最速下降成对交换相结合的启发式算法来求解DFLP的最优化问题。2模拟退火算法　　模拟退火（SimulatedAnnealing，SA）算法的思想最早是由N.Metropolis等人在1953年借鉴统计力学中物质退火方法而提出的。其思想观念来自固体的退火过程，加热固体至最高温使之溶化，冷却时，液体中原子的热运动渐渐减弱，随着温度的徐徐降低，原子运动渐趋有序，达到固体的最低能量状态或者基态。根据Metropolis准则，粒子在温度T时趋于平

4、衡的概率为e■，其中E为温度T时的内能，ΔE为其改变量，k为Boltzmann常数。　　1982年，Kinkpatrick等人首次用模拟退火算法解决组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法。由初始解i和控制参数初值t开始，对当前解重复“产生新解-计算目标函数差-判断是否接受-接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解。　　下面给出模拟退火算法的基本步骤：　　（1）给定模型每一个参数变化范围，在这个范围内随机选择一个初

5、始模型m0，并计算相应的目标函数值E(m0)。　　（2）对当前模型进行扰动产生一个新模型m，计算相应的目标函数值E(m)，得到△E=E（m）-E（m0）。　　（3）若ΔE<0，则新模型m被接受；若ΔE>0，则新模型按概率P=exp（-△E/T）进行接受，T为温度。当模型被接受时，置m0=m，E（m0）=E（m）。　　（4）在温度T下，重复一定次数的扰动和接受过程，即重复步骤（2）、（3）。　　（5）缓慢降低温度T。　　（6）重复步骤（2）、（5），直至收敛条件满足为止。3DFLP中的模拟退火启

6、发式解法3.1参数设置　　（1）接受新布置的概率确定。用模拟退火算法来解决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之间的随机数，且xf（y），thenbest__cost=f（y）andbestsol=y

7、。步骤6：ifi=A，thenupdater=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）是矢量，代表部

8、门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