基于模拟退火算法的设备配备优化

陈烁 胡文刚

[摘要]抽象提出了设备配备优化数学模型和模型的约束条件，研究采用模拟退火算法寻求全局最优解，并给出了算法步骤、程序模块结构和模拟退火部分程序。针对设备配备的复杂性，提出构建设备与岗位的适应度矩阵。为解决多目标组合优化问题，采用线性加权方法科学构建了评价函数。

[关键词]设备配备；编配优化；模拟退火

1、设备配备问题描述及数学模型

1.1配备问题描述

设备配备通常按照人员岗位编配，考虑引入适应度矩阵。适应度矩阵中的元素表示某一型号设备对某一岗位的适应程度。适应度矩阵由具有丰富经验的专家进行评估得来，是一组主观数值。适应度矩阵以表格形式表示见表1。

设备配备通常还受岗位重要性、经济性和保障性等因素制约。其中岗位重要性是指设备配备的岗位的相对重要性。经济性是指配备的总成本，即配备设备的总价格。保障性是指配备的设备型号数量，总数量越少则保障越容易，保障性越高。

1.2定义数学模型

假设需要配备设备的岗位有n类，待分配的设备有m种，则定义分配矩阵X=[xij]mn。xij表示第i种设备配到第j类岗位的数量，其值为自然数。定义适应度矩阵S=[sij]mn。sij表示第i种设备对第j类岗位的适应程度，当完全适应时其值取1，当不能适应时取0。适应度值根据设备新旧、替换使用性和需求匹配度等因素由专家经验确定。

设行n维向量K为岗位的效能权重向量，kj为第j类岗位的权重因子。则设备配备综合效能目标函数可由式（1）表示。

（1）

考虑配备的经济性，要求总体价格成本要尽量低。设m维向量C为设备的成本向量，ci为第i种设备的采购价格。则成本目标函数可由式（2）表示[3]。

（2）

考虑设备的保障性，要求各岗位配备设备的型号数要尽量的少。为便于统计型号数量，需要对分配矩阵X进行适当变换。

设m维向量U，令，则配备设备型号总数目标函数可由式（3）表示。

（3）

式中，为符号函数，当自变量大于0时函数值为1，等于0时函数值为0。此处用来消除同一种设备配备到多种岗位时产生的累加效果。

1.3约束条件

（1）各崗位仅分配一件或者不分配设备，即xij=1或0。（2）各岗位权重因子之和为1，即。

2、设备配备优化算法设计

通过以上模型可以看出，设备配备优化实际上是处理有限资源的多目标优化问题，要在一定约束条件下寻找全局最优解。模拟退火算法最早是由MetroPolis N等人借鉴统计热力学中物质退火方法而提出的，它在每一次修改模型的过程中，随机产生一个新的状态模型，然后以一定的概率选择邻域中能量值大的状态。以概率接受新状态的方式使模拟退火算法成为一种全局最优算法，并得到理论证明和实际应用的验证[1]。

2.1模拟退火配备优化算法

在模拟退火算法中，从一个随机解X0开始探测整个解空间，采取一定方式扰动此解产生一个新解Xn，按照 Metropolis准则判断是否接受新解，并相应的下降控制温度。算法主要步骤描述如下：（1）初始化参数。设定初始温度T=T0，温度衰减因子为d；（2）随机产生一个分配矩阵Xn，计算评价函数F（X0）；（3）设置循环计数器初值k=1，最大循环步数loopm；（4）对X0作一个随机扰动，产生新的分配矩阵Xn，计算新分配矩阵的评价函数F（Xn），并计算评价函数增量△F=F（Xn）-F（X0）；（5）如果△Fy≤0，接受Xn为新的最优解。如果，计算exp（-△F/T）；如果exp（-△F/T），则同样接受Xn为新的最优解。否则，X0不作改变；（6）循环计数，如果K

2.2配备优化评价函数

将多目标优化问题转化为单目标优化问题的方法很多，本文采取线性加权和法。配备优化模型中有配备综合效能P、配备总体成本C和配备型号总数量Y三个目标函数，其中配备总体成本C和配备型号总数量Y具有不同量纲，且函数值在量级上有较大差异，需要先转化为无量纲且等量级的目标函数。设Cnax为编配最大成本，N为设备型号总数量，令Cz=1-C/Cnax，Yz=1-Y/N。式中Cz为经济性指标，Yz为保障性指标。可以看出，Cz、Yz均无量纲且值在[0，1]之间。成本C越低，则经济性指标越高；配备总型号数量Yz越少，则保障性指标Yz越高。设α、ΒΓ分为配备综合效能、经济性和保障性指标的加权因子，则评价函数F（X）可由式（6）表示。

F（X）=α·P+β·Cz+γ·Yz （6）

2.3降温管理和收敛准则

（1）降温管理。在产生新解的过程中，当解的质量变差的概率呈Boltzmann分布时，S.Geman和D.Geman从理论上证明了采用t（k）=K/log（1+k）对数降温方式可使模拟退火算法收敛于全局最优解；当解的质量变差的概率呈Cahchy分布时，H.Szu和R.Hartley从理论上证明按t（k）=K（1+k）降温方式可使模拟退火算法收敛于全局最优解[2]。实际应用中为了简化计算，常采用一些简单直观的温度下降方法。本文采用式（7）所示的等比率下降方法，也即每一步温度以相同的比率下降。

Tk+1=d·Tk （7）

式中k≥O，为温度下降次数；0

（2）收敛准则。算法的收斂准则设为多次迭代都没有新解产生或者控制参数小到一定程度，即经过loopm次循环，按照Metropolis准则判断，均不接受新解，或者温度下降到终止温度Tend。

3、程序实现

3.1程序模块结构

根据夜视装备编配优化模拟退火算法，可设计程序模块结构如图1所示。

（1）主程序模块。该模块通过调用初始数据录入模块、产生初始解模块、模拟退火处理模块、评价函数计算模块和运算结果输出模块，实现全部算法功能。

（2）初始数据录入模块。该模块用于输入问题的已知条件和算法运行参数，问题的已知条件包括设备总数、岗位总数及权重、各型号设备价格、设备对岗位的适应度矩阵、评价函数中的各分函数加权因子等；算法的运行参数包括初始温度、终止温度、温度衰减系数、循环次数等。

（3）产生初始解模块。用于按照矩阵排列的解的表示方法，随机产生1个元素值均为0或1的m×n矩阵，该排列即为一个初始解，将该初始解作为当前解。

（4）模拟退火处理模块。该模块用于在同一温度下不断执行扰动操作，并按模拟退火算法的接受概率决定是否以扰动产生的新解代替当前解。

（5）评价函数计算模块。该模块的作用是根据问题的已知条件，计算各目标函数值，并利用公式（6）计算出该解的评价值。

（6）运算结果输出模块。该模块用于输出程序的运算结果，即算法求得的最终解所对应的分配矩阵和目标函数值。

3.2模拟退火部分程序

本文程序用C语言实现，下面给出模拟退火部分程序片段。

while（T>T_end）

{ dF=J（F（i+1））-J（F（i））；

if（dF>=0） //表达扰动后得到更优解，则总是接受扰动

F（i+1）=F（i）； //接受从F（i）到F（i+1）的扰动

else

{ if（exp（dF/T）>random（0，1））

F（i+1）=F（i）； //接受从F（i）到F（i+1）的扰动

}

T*=d； //降温退火 ，0

i++；}

4、结束语

设备配备优化是一个多目标组合优化问题，本文研究采用模拟退火算法寻找全局最优解，给出了具体算法步骤和程序实现方案。将智能算法应用于解决设备配备优化的问题，具有实践指导意义。

参考文献

[1]林令娟.模拟退火微粒群混合算法的研究[D].济南：山东师范大学，2010.

[2]刘晓莹.基于改进模拟退火算法的给水管网改扩建优化规划[D].合肥：合肥工业大学，2009.