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

ID:9767206

大小:54.50 KB

页数:4页

时间:2018-05-08

模拟退火算法在动态设施布置中的应用研究的论文_第1页
模拟退火算法在动态设施布置中的应用研究的论文_第2页
模拟退火算法在动态设施布置中的应用研究的论文_第3页
模拟退火算法在动态设施布置中的应用研究的论文_第4页
资源描述:

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

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

2、sflp就成了动态。这就是由rosenblatt首次提出的著名的动态设施布置问题(dynamicfacilitylayoutproblem,dflp)。  启发式算法成功发展之前,曾经用禁忌搜索技术、遗传算法等工具来求解大型组合优化问题。换言之,就是利用最速下降成对交换启发式(steepest-descentpairinistic),设施的面积和位置的大小一致,布置类型为已知的(即如附图为2×3的布置);部门之间的距离确定为一个单位。  关于dflp问题的求解,本文在urban提出的最速下降成对交换启发式解法之上,提出用一种通用的模拟退火算

3、法和最速下降成对交换相结合的启发式算法来求解dflp的最优化问题。2模拟退火算法  模拟退火(simulatedannealing,sa)算法的思想最早是由n.metropolis等人在1953年借鉴统计力学中物质退火方法而提出的。其思想观念来自固体的退火过程,加热固体至最高温使之溶化,冷却时,液体中原子的热运动渐渐减弱,随着温度的徐徐降低,原子运动渐趋有序,达到固体的最低能量状态或者基态。根据metropolis准则,粒子在温度t时趋于平衡的概率为e■,其中e为温度t时的内能,δe为其改变量,k为boltzmann常数。  1982年,k

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

5、)-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中的模拟退火启发式解法3.1参数设置  (1)接受新布置的概率确定。用模拟退火算法来解决dflp的最优化问题,首先要确定的是接受新布置的概率。接受概率如下:p(△tc)=exp(-△tc/

6、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启发式需要设置参数,用来降低当前温度以进行寻优。在程序执行的初期,接受邻域解的概率较高,这是初始温度的高低造成的。初始温度选得太高,则算法的计算量增加许多;反之,初始温度选得太低,则一旦算法落入局部最优解的陷阱中就无法再跳出来,从而无法求得全局近似最优

7、解。本文采用如下公式确定初始温度:t0=-△tc/1n(p(△tc))=-0.01f(y0)/1n(0.25)  其中:t0表示初始温度,f(y0)表示初始解的成本。3.2dflp中的算法描述  模拟退火算法是一种随机算法,在降温的过程中,须执行一系列的成对交换,确保系统处于稳定状态。把sa启发式算法直接应用于dflp的思想,叫做sai,其步骤如下:步骤0:把每阶段的流量矩阵、长度矩阵和再布置成本作为输入数据,确定sa参数:设t0为初始温度,α为降温率,a为每次温度变化时产生的变化数量,tmin为最低温度。步骤1:假定存在温度变化产生器r,

8、置r=1。步骤2:①产生初始解y0,并将其赋予当前解(即置y=y0);②产生当前解的成本f(y);③设置下列参数:best__sol=y;best__cost=f(y)。步骤3:

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
正文描述:

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

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

2、sflp就成了动态。这就是由rosenblatt首次提出的著名的动态设施布置问题(dynamicfacilitylayoutproblem,dflp)。  启发式算法成功发展之前,曾经用禁忌搜索技术、遗传算法等工具来求解大型组合优化问题。换言之,就是利用最速下降成对交换启发式(steepest-descentpairinistic),设施的面积和位置的大小一致,布置类型为已知的(即如附图为2×3的布置);部门之间的距离确定为一个单位。  关于dflp问题的求解,本文在urban提出的最速下降成对交换启发式解法之上,提出用一种通用的模拟退火算

3、法和最速下降成对交换相结合的启发式算法来求解dflp的最优化问题。2模拟退火算法  模拟退火(simulatedannealing,sa)算法的思想最早是由n.metropolis等人在1953年借鉴统计力学中物质退火方法而提出的。其思想观念来自固体的退火过程,加热固体至最高温使之溶化,冷却时,液体中原子的热运动渐渐减弱,随着温度的徐徐降低,原子运动渐趋有序,达到固体的最低能量状态或者基态。根据metropolis准则,粒子在温度t时趋于平衡的概率为e■,其中e为温度t时的内能,δe为其改变量,k为boltzmann常数。  1982年,k

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

5、)-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中的模拟退火启发式解法3.1参数设置  (1)接受新布置的概率确定。用模拟退火算法来解决dflp的最优化问题,首先要确定的是接受新布置的概率。接受概率如下:p(△tc)=exp(-△tc/

6、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启发式需要设置参数,用来降低当前温度以进行寻优。在程序执行的初期,接受邻域解的概率较高,这是初始温度的高低造成的。初始温度选得太高,则算法的计算量增加许多;反之,初始温度选得太低,则一旦算法落入局部最优解的陷阱中就无法再跳出来,从而无法求得全局近似最优

7、解。本文采用如下公式确定初始温度:t0=-△tc/1n(p(△tc))=-0.01f(y0)/1n(0.25)  其中:t0表示初始温度,f(y0)表示初始解的成本。3.2dflp中的算法描述  模拟退火算法是一种随机算法,在降温的过程中,须执行一系列的成对交换,确保系统处于稳定状态。把sa启发式算法直接应用于dflp的思想,叫做sai,其步骤如下:步骤0:把每阶段的流量矩阵、长度矩阵和再布置成本作为输入数据,确定sa参数:设t0为初始温度,α为降温率,a为每次温度变化时产生的变化数量,tmin为最低温度。步骤1:假定存在温度变化产生器r,

8、置r=1。步骤2:①产生初始解y0,并将其赋予当前解(即置y=y0);②产生当前解的成本f(y);③设置下列参数:best__sol=y;best__cost=f(y)。步骤3:

显示全部收起
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。
关闭