当前位置: 美高梅棋牌 > 智能家电 > 正文

爬山算法与模拟退火算法的分析与实现

时间:2019-10-03 06:34来源:智能家电
爬山算法是一种局部择优的方法,是一种局部贪心的最优算法。采用启发式方法,是对深度优先搜索的一种改进,它利用反馈信息帮助生成解的决策。该算法每次从当前解的临近解空间

爬山算法是一种局部择优的方法,是一种局部贪心的最优算法。采用启发式方法,是对深度优先搜索的一种改进,它利用反馈信息帮助生成解的决策。 该算法每次从当前解的临近解空间中选择一个最优解作为当前解,直到达到一个局部最优解,属于人工智能算法的一种。

旅行商问题(TSP)介绍

旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。
从图论的角度来看,该问题实质是在一个带权完全无向图中,找一个权值最小的Hamilton回路。由于该问题的可行解是所有顶点的全排列,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用,国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题,常用的方法包括:分枝定界法、线性规划法、动态规划法等。但是,随着问题规模的增大,精确算法将变得无能为力,因此,在后来的研究中,国内外学者重点使用近似算法或启发式算法,主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。

  • 对称TSP:城市A到城市B的距离 等于 城市B到城市A的距离
  • 非对称TSP:城市A到城市B的距离 不等于 城市B到城市A的距离
  1. 随机选择一个登山的起点;
  2. 每次拿相邻点与当前点进行比对,取两者中较优者,作为爬坡的下一步;
  3. 重复第2步,直至该点的邻近点中不再有比其大的点;
  4. 选择该点作为本次爬山的顶点,即为该算法获得的最优解。

实现简单,其主要缺点是会陷入局部最优解,不一定能搜索到全局最优解。如下图所示:假设C点为当前解,爬山算法搜索到A点这个局部最优解就会停止搜索,因为在A点无论向那个方向小幅度移动都不能得到更优的解。

编辑:智能家电 本文来源:爬山算法与模拟退火算法的分析与实现

关键词: