优化算法-模拟退火法计算.doc

优化算法-模拟退火法计算[作者:佚名 | 来源:本站原创 | 阅读:737 | 更新:2006-1-5 | 编辑:澜雨]模拟退火法计算  MCM 85B题、CMCM 98B题、 CMCM 97A题的C程序(注:这些程序参考了“C语言数值算法程序大全”)  1、MCM 85B题是一个STEINER生成树问题,经过简化,问题可以通过穷举法计算得到,但如果不作简化,则所有可能虚设点的位置有927个,这里用穷举法就行不通了,我们使用模拟退火法计算,算法如下:步1:给定初始温度T, :步3 --8循环K次步3:步 4--7循环M次步4:随机确定一个数N(1~7)步5:随机确定进行下列两种调整中的一种:规则1:在原有的状态上增加一些虚设点或减少一些虚设点,增加或减少的点数以及位置是随机的规则2:在原有虚设点选取一些点进行随机移动,选取的点数在1,4 之间,随机确定,考虑各点在上下左右各方向移动组合,选取最优的作为候选者,移动的距离是随机的,且随着温度的下降而减少步6:计算由步5选择的N个点和原始点组成完全图的最小生成树的权W*,W*-W->D步7:按照如下规则确定是否接受新的生成树:如果D<0,则接受,W*->W如果D>0,则按照EXP(-D/T)的概率接受,W*->W步8:T*-->T,降温点击这里下载程序 点击浏览该文件 MCM85B2、CMCM 97A题,97年全国大学生数模竞赛A题“零件的参数设计”,可以归结为非线性规划模型,由于目标函数很复杂,且又是一个多维函数,因此求解比较困难,为应用模拟退火法进行求解,将7个自变量的取值范围进行离散化,,这样,所有7个变量取值就组成了一个极为庞大的离散空间, 而这个问题变成组合优化模型。这个问题算法基本上同上题,状态调整规则是:每次从7个自变量中随机选取1-4个,让选取的自变量随机移动,考虑选取的自变量在两个方向移动组合,从中选取最佳的作为候选者,自变量移动的距离随着温度的降低而减少,为避免陷入局部极小,可以从多个随机选取的初始值开始计算,算法的其余部分和上述算法一样。点击这里下载程序点击浏览该文件