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

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

2、高企业生产效率。 当设施间的物流量在布置范围内变化时，SFLP就成了动态。这就是由Rosenblatt首次提出的著名的动态设施布置问题（dynamicfacilitylayoutproblem，DFLP）。 启发式算法成功发展之前，曾经用禁忌搜索技术、遗传算法等工具来求解大型组合优化问题。换言之，就是利用最速下降成对交换启发式（steepest-descentpairwiseexchangeheuristic）从初始解开始产生邻域解。通常这类启发式的时间效率不高，并且只收敛于局部最优。为了克服这些缺陷，本文提出用模拟退火启发式解决DFLP最优问题，用固体退火的思想来接受邻域解，以免陷入局部最优

3、。 1DFLP的基本思想 企业随着市场的变化而调整其设施布置，本文称其为柔性布置。DFLP就是以将来的可预测变化为基础的。预期的未来可以划分为很多区段，这些区段可以定义为周、月甚至是年。研究动态设施布置问题时，设每1区段的流量数据是可预测和连续的，则设施布置问题中的每个区段，可以用SFLP（QAP）进行解决。 DFLP的布置规划是以可预测未来为基础的1系列布置，每个布置规划跟每个区段有关。在布置过程中，在原有基础上对设施的移动而产生的成本称为再布置成本，设施的再布置可能导致产品的损失，还可能需要专业人员和专门的设备。因此，再布置成本由劳动力成本、设备成本和产品损耗成本组成；另外，对制造设施来说

4、，在设施间还要对物料进行搬运以满足设施加工的需要，搬运物料所投入的成本，称为物料搬运成本。成本的大小由设施间物料的流量以及设施间的距离决定，它是决定布置是否合理的最重要的衡量标准，1般占总运作成本的20%50%，占产品制造成本的15%70%，这成为设施布置中需要考虑的重要指标。因此，布置规划的总成本由所有区段的物料搬运成本和与再布置成本之和组成。 布置规划的目的是使搬运成本与再布置成本之和达到最小。在这过程中，须重复交换部门间的位置以满足上述要求，当物料搬运成本大于再布置成本时，可以把DFLP看作1系列的SFLPs（QAPs）来求解。 附图所示是具有6个设施在3个区段的DFLP事例。在第1区段

5、，设施1、2、3、4、5和6分别被安置在位置3、4、1、5、2和6，由于设施3和5在第2区段被分配到不同的位置（即分别在位置2和1），则其再布置成本就是把设施3移动到位置2所产生的成本与把设施5移动到位置1所产生的成本之和。另外，在布置中，由于在阶段2和在阶段3的布置是1样的，故在阶段3中没有再布置成本。 为了操作方便，可以对DFLP进行如下的假设：设施间的流量是动态而确定的（deterministic），设施的面积和位置的大小1致，布置类型为已知的（即如附图为2×3的布置）；部门之间的距离确定为1个单位。 关于DFLP问题的求解，本文在Urban提出的最速下降成对交换启发式解法之上

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

7、1982年，Kinkpatrick等人首次用模拟退火算法解决组合优化问题，将内能E模拟为目标函数值f，温度T演化成控制参数t，即得到解组合优化问题的模拟退火算法。由初始解i和控制参数初值t开始，对当前解重复“产生新解-计算目标函数差-判断是否接受-接受或舍弃”的迭代，并逐步衰减t值，算法终止时的当前解即为所得近似最优解。 下面给出模拟退火算法的基本步骤： （1）给定模型每1个参数变化范围，在这个范围内随机选择1个初始模型m0，并计算相应的目标函数值E(m0)。 （2）对当前模型进行扰动产生1个新模型m，计算相应的目标函数值E(m)，得到E=E（m）-E（m0）。 （3）若E<0，则新模型

8、m被接受；若E>0，则新模型按概率P=exp（-E/T）进行接受，T为温度。当模型被接受时，置m0=m，E（m0）=E（m）。 （4）在温度T下，重复1定次数的扰动和接受过程，即重复步骤（2）、（3）。 （5）缓慢降低温度T。 （6）重复步骤（2）、（5），直至收敛条件满足为止。 3DFLP中的模拟退火启发式解法 3.1参数设置 （1）接受新布置的概率确定。用模拟退火算法来解决DFLP的最优化问题，首先要确定的是接受新布置的概率。接受概率如下： P（Tc）=exp（Tc/Tc） Tc=T0r-1r=1，2，R 其中：Tc表示当前温度，Tc表示总成本的改变量(如果邻域解的成本比当前解的成本

9、低，则Tc=f（y）-f（y）)，T0是初始温度，为降温率，通常为0.9，r-1为温度降低的数量。设x是01之间的随机数，且x（2）初始温度的确定。SA启发式需要设置参数，用来降低当前温度以进行寻优。在程序执行的初期，接受邻域解的概率较高，这是初始温度的高低造成的。初始温度选得太高，则算法的计算量增加许多；反之，初始温度选得太低，则1旦算法落入局部最优解的陷阱中就无法再跳出来，从而无法求得全局近似最优解。本文采用如下公式确定初始温度： T0=-Tc/1n（p（Tc）=-0.01f（y0）/1n（0.25） 其中：T0表示初始温度，f(y0)表示初始解的成本。 3.2DFLP中的算法描述 模拟退

10、火算法是1种随机算法，在降温的过程中，须执行1系列的成对交换，确保系统处于稳定状态。把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=T0r-1，如

11、果Tc步骤4：随机选取区段t，然后随机选取其中的两个设施u和v，相互交换其位置，得到的解设为y，置i=i+1；计算总成本的改变量：Tc=f（y）-f（y）。 步骤5：if（Tc<0）or（Tc>0andx=random（0，1）f（y），thenbest_cost=f（y）andbestsol=y。 步骤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）是矢量，代表部门i的位置，i=1，2，N。例如，有6个部门的初始布置中，第1阶段