旅行商问题求解算法综述

旅行商问题作为NP难题的典型代表,从诞生以来一直都是计算机算法理论研究的热点话题,各种针对该问题的算法层出不穷。对相关的代表性算法进行了介绍与总结,在分析各种算法的特点之后,提出了各类算法的改进方向,对旅行商问题的研究进行了展望。     

旅行商问题的综述教学研究

旅行商问题是数学上的组合优化问题,是一个经典的NP完全问题。该问题在工程上有很强的实用背景;对该问题的研究一直受到众多学者的重视,对其的求解亦提出了各种不同算法;同时就该问题还提出了各种推广形式,但就该问题的教学研究却很少有人涉及。针对这些情况,本文就该问题的综述与教学做几方面的研究,以提高对该问题的教学质量、增强学生的学习积极性。     

扩展旅行商问题模型研究

旅行商问题是一个经典的组合优化NP问题.对于现实问题由于限制条件的增加,TSP衍生出许多相关问题,在许多领域内具有实际的应用价值.针对TSP问题,由一般的TSP模型入手,根据实际问题不断把模型进行推广,进而建立了相应的优化模型.     

基于模拟退火技术的旅行商问题求解算法

旅行商问题是一个经典的图论问题,也被证明是一个NP-完全问题,在问题规模较小时,可通过枚举来得到问题的最优解,但仍然无法找到多项式时间复杂度的算法。在TSP问题中引入模拟退火的思想,通过求解一系列随温度变化的物理系统的自由能函数的局部极小来求得问题的最优解,并给出了求解的启发式算法。     

浅谈旅行商问题与蚁群算法

蚁群算法是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等启发式搜索算法之后的又一种应用于组合优化问题的算法。根据蚁群算法的特性,求解旅行商问题,利用仿真实验程序对蚁群求解旅行商问题进行模拟。     

基于自适应蚁群算法的旅行商问题的求解

提出一种解决旅行商问题的改进自适应蚁群算法.在传统蚁群算法的基础上,引入自适应算法进行种群初始化;从对选择策略的改进、蚁群信息量的全局修正和引入变异三个方面实现遗传参数自适应调节,在加快寻优速度的同时防止寻优陷入局部最优;采用基于贪婪方法的启发式交叉算子优化交叉结果;对交叉前后的种群分别实施精英个体保留策略,保证最优基因结构得以延续.实验结果分析表明,改进的遗传算法可以在种群规模较小的情况下具有更可靠的寻优能力.     

混合蛙跳算法改进及其对旅行商问题的求解

针对混合蛙跳算法在进化过程中容易陷入局部最优的问题,使用群体适应度值判断算法在进化过程中是否陷入局部最优,如果陷入局部最优,则对整个种群的当前最优解Gb进行贪婪倒位变异,如果变异后的Gb(新)要优于Gb(旧),则使用Gb (新);否则,使用模拟退火算法判断是否接受Gb (旧)。通过实验,将改进前后的混合蛙跳算法用于对旅行商问题的求解,并通过对比,验证了改进后的算法较未改进的算法更有效。     

车辆路径安排问题算法研究综述

车辆路径安排是决定物流配送费用的主要因素。车辆路径安排问题(Vehicle Routing Problem,VRP)是近年来应用数学、计算机科学和物流科学研究的一个热点问题,产生了众多的研究成果。本文首先讨论了VRP的分类,然后基于VRP算法构造方法的分类,概要介绍了近五年来VRP算法研究的主要成果,并对研究方法进行了分析,最后对全文进行了总结,并探讨了该问题未来的研究方法。     

基于遗传算法的旅行商问题的研究

巡回旅行商问题(TSP)是一个组合优化方面的问题,已经成为测试组合优化新算法的标准问题。应用遗传算法解决TSP问题,首先对访问城市序列进行排列组合的方法编码,这保证了每个城市经过且只经过一次。接着生成初始种群,并计算适应度函数,即计算遍历所有城市的距离。然后用最优保存法确定选择算子,以保证优秀个体直接复制到下一代。采用有序交叉和倒置变异法确定交叉算子和变异算子。最后用MATLAB来实现算法,仿真后,观察路径,得出最终结果。     

遗传算法求解旅行商问题的一个新方法

提出了利用遗传算法求解TSP问题的一个新方法,该方法采用二进制编码,并巧妙地设计了一种解码算法,不仅可以使得种群进化,而且扩大了搜索的空间。实验表明,比起传统的遗传算法,新方法的性能有显著改善。     

解决TSP问题的一种改进遗传算法

TSP是一个典型的组合优化问题,也是一个NP难题,其可能的路径总数是随着城市数目n的增长而成几何型增长的,所以一般很难准确地求出其最优解,因而寻找出有效的近似求解算法就成了解决此问题的最佳方法。文章首先介绍了在初始化阶段经行改进的遗传方法。通过把改进方法同标准的遗传算法相比较,得出改进遗传算法在性能上有改进。最后,我们还分析了实验结果并提出了评价初始解优劣的一个指标函数——局部相似度函数,并给出了函数的具体表达式。     

求解TSP问题的几种算法比较

旅行售货商问题(简称TSP)是离散优化的一个经典的重要问题,对求解算法的研究非常重要。在介绍求解TSP问题的贪婪算法、禁忌搜索算法、模拟退火算法、遗传算法的基本思想之后,提出了相应的算法。针对测试库的四个典型算例,用程序实现这些算法,对这些算法的运行时间和结果进行比较研究。结果表明贪婪算法短时间就可以得出解,禁忌搜索算法与遗传算法的效果相当,模拟退火算法比遗传算法的结果好。     

局部社区发现算法研究综述

社区发现能帮助人们了解社交网络的结构特性及隐藏信息。局部社区发现算法不需要网络的整体信息,以局部结构信息为基础,可以快速找到目标节点所在的局部社区,提高了效率,因而受到学者们的青睐。按算法基本思想,现有局部社区发现算法可分为标签传播类算法、局部扩张算法等。对部分局部社区发现领域的研究成果进行总结,分析它们的优缺点,并提出未来局部社区发现算法研究方向。     

单目视觉惯性的同时定位与地图构建综述

在机器人领域,同时定位与地图构建（SLAM）是导航定位的关键技术。单目视觉传感器由于结构简单、成本低且能获取丰富的视觉信息,被广泛应用于 SLAM。随着无人机、AR 设备以及自动驾驶汽车技术的快速发展,视觉惯性 SLAM（VI-SLAM）技术得到了越来越多人的关注。针对 VI-SLAM,从滤波与非线性优化的角度出发,首先介绍相关算法理论框架,然后分析几种具有代表性的单目 VI-SLAM 算法创新点及实现方案,并通过 EuRoC MAV 数据集评估各算法优劣,最后结合深度学习与语义 SLAM,对 SLAM 未来发展趋势进行探讨。     

数字水印算法分析综述

本文主要针对近年来数字水印算法在空域方法和频域方法上的发展,演变过程及其间的一些典型算法进行综述,并分析了这些主要算法的优缺点。其中大部分算法针对的源数据是图像,但其中的很多技术对于音频及视频等其他形式的多媒体数据也同样适用。     

本地差分隐私频率估计研究综述

本地差分隐私(LDP)频率估计是数据挖掘领域的一个重要组成部分,目的是在满足LDP的前提下计算特定数据项出现的频率.在基于云服务的应用中,LDP频率估计实现了数据采集过程与数据分析过程的隐私保护,可应用于频繁模式挖掘、恶意攻击检测等.但是LDP频率估计存在随机化噪声较多、依赖数据量较大、高维数据分析准确性较低等缺点.介...     

基于语义的搜索算法研究

基于XML得出改进的语义表示法,能解决当前常用网络搜索引擎缺乏理解用户想法而导致查询结果不满意的问题。文档解析算法、模式匹配算法、生成XMLSE文档算法等几个基于语义搜索的核心算法,辅以人工标注和建立规则库,构成一个语义网络,能达到精确的搜索,提高搜索效率。     

有保证调度算法的研究

有保证的调度对硬实时系统是必须的 ,这是因为系统中每个进程必须满足它们的截止时间 ,否则后果不堪设想 .本文讨论了两种有保证的调度算法 ,它们是分支限界法和回溯法 ,给出了用这两种算法寻找最优解的过程 ,提出逻辑结点和物理结点的概念 .通过对多个进程集合寻找最优解的实验 ,对两种算法在产生的结点个数、比较次数、搜索树的拓扑结构及占用的内存空间等方面进行了比较     

机器学习的五大类别及其主要算法综述

机器学习作为一门源于人工智能和统计学的学科,是当前数据分析领域重点研究方向之一。首先通过追溯机器学习起源和介绍不同算法在求解策略上的启发性思路,讨论五类机器学习的发展及其主要算法在评价方法和优化方式上的实现,进一步总结归纳各算法适用领域和算法优劣,最后指出各算法克服自身缺陷的最新进展和未来实现多算法融合的研究方向。