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

陈烁1.2 胡文刚2

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

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

[教育期刊网 http://www.jyqkw.com
关键词 ]设备配备；编配优化；模拟退火

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

1.1配备问题描述

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

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

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

3、程序实现

3.1程序模块结构

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

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

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

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

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

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

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

3.2模拟退火部分程序

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

4、结束语

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

教育期刊网 http://www.jyqkw.com
参考文献

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

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