模拟退火算法在TSP问题中的优化研究+源码(3)
时间:2017-04-24 22:29 来源:毕业论文 作者:毕业论文 点击:次
(5)返回List，结束。 f(x→y)表示状态x到状态y；当目标函数f()从x状态变到y状态时减少那么概率为1，若从x状态变到y状态时目标函数增加那么接受概率为 。 2.2 模拟退火算法求解分析 2.2.1 循环分析 一个内循环和一个外循环在模拟退火算法中是比较常见的循环设置，内循环表示的是在一个特定温度T下，在邻近解空间进行随机搜索。外循环表示温度下降变化，迭代步数的增加和控制停止条件。内、外循环步骤数的设置很重要，如果内循环设置的比较小，则不能对相应邻域所有的解实现等概率搜索，从而使最终结果不是最优。外循环设置过大则会出现最优解重复次数的增加，优化速率会很差。在每一个T温度时，必须迭代相同的步数，否则可能会得不到最优解或者每次解的结果差别很大。问题大小决定了内循环次数，最常用的方法是与邻域空间大小相近的次数，在TSP问题中的解空间的大小为n ,n为城市数。那么可取n, ,(k=3,4,5,6……)。 初始温度的设置是模拟退火算法中很重要的环节，如果初始温度设置过高，那么将使计算时间增加，循环步骤徒增或者是过早的陷入稳定，使计算效率降低。如果温度设置过低，那么在冷却过程的次数就会减少，使算法不能够找到该状态下的最优解。同时温度的设置会影响到Metropolis算法对恶化解概率。 2.2.2模拟退火算法漏斗原理 漏斗原理表示的是在能量降低的过程中会出现一些假最低点或者成为局部最优点。这些局部最优点会影响算法的求解结果。如果算法在修改参数数据后求解的结果与上次实验求解的结果相差较大，那么上次求解的结果很可能陷入的局部最优解里面。模拟退火算法是迭代启发式自适应概率搜索算法，而在搜索过程中的目标函数值得变化类似于物理过程中的能量变化，会呈现出典型的漏斗形状，其表现为在大量的局部最小点中搜索全局最优解会使系统陷入歧途的陷阱，最终的结果将得不到全局最优解。而统计学的一个基本模型认为一个物理系统所处的能量为E的状态的概率与Gibbs-Boltzmann函数 ，T为系统温度，k为一个常数。如图1所示。 (责任编辑：qin) |