模拟退火算法及其改进算法

《模拟退火算法及其改进算法》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、1.模拟退火算法起源1.1模拟退火算法起源于物理退火1.1.1物理退火过程：a.加温过程b.保温过程c.冷却过程T0降温温度升高原子动能增加跳离原来位置的概率增加原子动能减小跳离原来位置的概率减小继续降温原子位置排列将趋于能量低的状态最后稳定根据这一物理过程，1953年Metropolis提出重要性采样法，即以概率接受新状态。称为Metropolis准则。该准则指出： 固体在恒定温度下达到热平衡的过程可以用MorteCarol算法方法加以模拟，虽然该方法简单，但必须大量采样才能得到比较精确的结果，因而计算

2、量很大。鉴于物理系统倾向于能量较低的状态，而热运动又妨碍它准确落到最低态。采样时着重选取那些有重要贡献的状态则可较快达到较好的结果。1.2随机神经网络BP神经网络和反馈神经网络都是使能量函数按梯度单调下降，如图常常导致网络落入局部最小点而达不到全局最小点，这就意味着训练不收敛。而随机网络即能赋予网络下山的能力，也能赋予网络上山的能力，特点如下：（1）在学习阶段，随机网络不像其它网络那样基于某种确定性算法（2）在运行阶段，随机网络不是按某种确定性的网络方程进行状态演变，神经元的净输入不能决定其状态是1还是0

3、.2.3模拟退火算法的特点2.3.1模拟退火算法的优点计算过程简单，通用，鲁棒性强，适用于并行处理，可用于求解复杂的非线性优化问题2.3.2模拟退火算法的缺点降温过程与解的质量的矛盾2.4模拟退火算法的改进（1）设计合适的状态产生函数，使其根据搜索进程的需要表现出状态的全空间分散性或局部区域性。（2）设计高效的退火策略。(3)避免状态的迂回搜索。(4)采用并行搜索结构。(5)为避免陷入局部极小，改进对温度的控制方式(6)选择合适的初始状态。(7)设计合适的算法终止准则。还可以通过以下方式进行改进(1)增加

4、升温或重升温过程。在算法进程的适当时机，将温度适当提高，从而可激活各状态的接受概率，以调整搜索进程中的当前状态，避免算法在局部极小解处停滞不前。(2)增加记忆功能。为避免搜索过程中由于执行率接受环节而遗失当前遇到的最优解，可通过增加存储环节，将一些在这之前好的态记忆下来。(3)增加补充搜索过程。即在退火过程结束后，以搜索到的最优解为初始状态，再次执行模拟退火过程或局部性搜索。(4)对每一当前状态，采用多次搜索策略，以概率接受区域内的最优状态，而非标准SA的单次比较方式。(5)结合其他搜索机制的算法，如遗传

5、算法、混沌搜索等。3模拟退火算法的应用3.1改进模拟退火算法导弹研制投资决策研究中的应用3.1.1情况概述导弹研制投资决策是在综合考虑投资效果和风险的前提下从众多的投资对象中选择一组合适的投资对象的过程。投资总风险定义为：投资组合的总效益为：：为第i个项目的总净现值为0表示第i个项目未被选中，为1表示被选中根据上述原则，决策目标函数为资金约束为：其中：为投资额下限，为投资额上限。可得到投资风险组合优化决策模型如下：3.1.2模型建立本模型的建立基于以下三个原则：（1）单位风险收益最大原则通过计算组合投资的

6、平均收益与组合风险比来判断组合方案的优劣比值大的组合方案表其单位风险所获得的收益也大（2）投资剩余资源最少原则如果仅依据单位风险收益最大原则来决策就可能出现只有很少几个项目被选中的情况这样会造成分配后的剩余资金过多因此在投资组合优化决策中应在每笔单项投资可行的基础上增加一个最低投资额度的约束条件以使剩余资金处于可以接受的水平3.1.3根据模拟退火算法的思想设计适合该模型的算法步骤1产生初始解其中，为可能解集合，代表第个单位是否获得投资的状态给出控制参数初值Mapkob链长度N以及停止参数K和步骤2判断初始

7、解的可行性，若不可行，则进行快速调整，否则转步骤3.步骤3产生新解并计算新解与当前解的目标函数值之差然后由接受准则计算取上服从均匀分布的随机数若接受新解，否则放弃新解。步骤4累计重排次数n，若转步骤3，否则转步骤5步骤5判断停止准则是否满足，若不满足,则令转步骤3,否则停止算法输出当前解。由于模拟退火算法的随机性，终止解可能不是整个过程所遇到的解中最优的，即使是最优的，虽然可证明算法对整体最优解的渐进收敛性，但终止解的可接受性也不能不遭到怀疑，另外，当终止解在最优解的附近时，算法本身不能迅速逼近或达到它。

8、3.1.4实例分析某型导弹改进项目的投资为300万元，为270万元。现有10个研制单位申请投资，有关信息如表1表2所示。现在要求确定军方的投资组合决策，以决定对哪些单位投资。在计算机上运行后得到最优解运用Matlab软件，可以根据上述算法编制相应程对该问题进行求解，其中相关参数的设置为