首页
学习
活动
专区
工具
TVP
发布
精选内容/技术社群/优惠产品,尽在小程序
立即前往

干货 | 用模拟退火(SA, Simulated Annealing)算法解决旅行商问题

前 排 最近这个春节又快到了,虽然说什么有钱没钱回家过年。但也有部分小伙伴早已经备好了盘缠和干粮,准备在这个难得的假期来一场说走就走的旅行了。毕竟世界这么大我想去看看呵……等等,醒醒吧各位 但是,作为21世纪的新一代青年,即使咱穷,梦想还是要有的,对吧。那么,问题来了,如何用最少的钱,环绕中国各大城市走一波?咳咳,今天小编就是为解决此问题而来的。顺带提一波,最近天冷了。小编在这里给大家送上最真切的关心…… * 内容提要: *旅行商问题介绍 *模拟退火算法 *旅行商问题的解决 我想用最少的钱环游中国一圈 01

08
  • 您找到你想要的搜索结果了吗?
    是的
    没有找到

    Boltzmann机详解

    我们知道,Hopfield神经网络拥有联想记忆的能力,这也是对生物神经网络的一种模拟。但是,Hopfield神经网络也和BP神经网络一样,有一个致命的缺陷:只能找到局部最优解,而无法沿着梯度上升的方向在全局的角度寻求全局最优解。 为了解决这个问题,1983年,Kirkpatrick等提出了模拟退火算法(SA)能有效的解决局部最优解问题。‘退火’是物理学术语,指对物体加温在冷却的过程。模拟退火算法来源于晶体冷却的过程,如果固体不处于最低能量状态,给固体加热再冷却,随着温度缓慢下降,固体中的原子按照一定形状排列,形成高密度、低能量的有规则晶体,对应于算法中的全局最优解。模拟退火算法包含两个部分即Metropolis算法和退火过程。Metropolis算法就是如何在局部最优解的情况下让其跳出来,是退火的基础。1953年Metropolis提出重要性采样方法,即以概率来接受新状态,而不是使用完全确定的规则,称为Metropolis准则,计算量较低。

    02

    模拟退火算法优化指派问题

    之前二狗已经分别介绍过了,如何用模拟退火算法和遗传算法,进行背包问题的求解。其实背包问题是可以看成是一个可以看成是一个比较特殊的,有线性约束的,0-1规划问题。在数学中还有很多其他特殊的问题,比如指派问题。指派问题可以看成是更特殊的多个背包问题(很多个背包求优,每个背包只能装一样物品)。基本指派问题一般可以描述为有n个任务n个人。要求为n个任务分配给指定的人来完成。并且在这种基本情况下,人和任务需要是一一对应的关系。不能有重复,不能出现两个人做同一个任务,或者一个人同时做两个任务的情况。(这些情况也属于指派问题的范畴,但属于更加复杂的情况,今天就不做讲解)。指派问题已经有了明确可解的算法,也就是我们大家都知道的匈牙利算法。同样的,这个问题也可以使用模拟退火来解决。今天我们就使用模拟退火算法来为大家演示,如何在指派问题进行优化?

    04

    人工智能:智能优化算法

    优化问题是指在满足一定条件下,在众多方案或参数值中寻找最优方案或参数值,以使得某个或多个功能指标达到最优,或使系统的某些性能指标达到最大值或最小值。优化问题广泛地存在于信号处理、图像处理、生产调度、任务分配、模式识别、自动控制和机械设计等众多领域。优化方法是一种以数学为基础,用于求解各种优化问题的应用技术。各种优化方法在上述领域得到了广泛应用,并且已经产生了巨大的经济效益和社会效益。实践证明,通过优化方法,能够提高系统效率,降低能耗,合理地利用资源,并且随着处理对象规模的增加,这种效果也会更加明显。 在电子、通信、计算机、自动化、机器人、经济学和管理学等众多学科中,不断地出现了许多复杂的组合优化问题。面对这些大型的优化问题,传统的优化方法(如牛顿法、单纯形法等)需要遍历整个搜索空间,无法在短时间内完成搜索,且容易产生搜索的“组合爆炸”。例如,许多工程优化问题,往往需要在复杂而庞大的搜索空间中寻找最优解或者准最优解。鉴于实际工程问题的复杂性、非线性、约束性以及建模困难等诸多特点,寻求高效的优化算法已成为相关学科的主要研究内容之一。 受到人类智能、生物群体社会性或自然现象规律的启发,人们发明了很多智能优化算法来解决上述复杂优化问题,主要包括:模仿自然界生物进化机制的遗传算法;通过群体内个体间的合作与竞争来优化搜索的差分进化算法;模拟生物免疫系统学习和认知功能的免疫算法;模拟蚂蚁集体寻径行为的蚁群算法;模拟鸟群和鱼群群体行为的粒子群算法;源于固体物质退火过程的模拟退火算法;模拟人类智力记忆过程的禁忌搜索算法;模拟动物神经网络行为特征的神经网络算法;等等。这些算法有个共同点,即都是通过模拟或揭示某些自然界的现象和过程或生物群体的智能行为而得到发展;在优化领域称它们为智能优化算法,它们具有简单、通用、便于并行处理等特点。 **

    01
    领券