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

2016-01-04

决策与信息 2015年29期

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

陈烁1.2胡文刚2

1.中国人民解放军72465部队山东济南2500222.军械工程学院河北石家庄050003

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

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

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

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）表示。

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

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

式中，Sgn(x )为符号函数，当自变量大于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＜loopm，则k=k+1, 转到第（4）步；（7）如果不满足收敛准则，则根据温度管理函数T=T(n)更新温度，降温次数n=n+1，转到第（3）步；如果满足收敛准则，则输出当前最优解，算法结束。

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）表示。

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）所示的等比率下降方法，也即每一步温度以相同的比率下降。

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

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