【摘 要】
：
旅行商问题（Travelling salesman problem,TSP）是一种NP问题,在物流路线规划等领域有着广泛的应用。目前,研究人员提出了不同的算法来解决TSP,主要分为精确算法和启发式算法。由于精确算法设计复杂和求解时间长,启发式算法受到了广泛关注。在启发式算法中,蚁群算法是一种经典且有效的启发式算法,然而由于蚁群算法的参数不能灵活设置和局部启发信息不足等原因,算法容易陷入局部最优,因
论文部分内容阅读
旅行商问题（Travelling salesman problem,TSP）是一种NP问题,在物流路线规划等领域有着广泛的应用。目前,研究人员提出了不同的算法来解决TSP,主要分为精确算法和启发式算法。由于精确算法设计复杂和求解时间长,启发式算法受到了广泛关注。在启发式算法中,蚁群算法是一种经典且有效的启发式算法,然而由于蚁群算法的参数不能灵活设置和局部启发信息不足等原因,算法容易陷入局部最优,因此如何使用不同策略避免蚁群算法陷入局部最优是目前研究的热点。膜计算是一种并行计算模型,该模型由几种类似细胞的膜组成,膜计算与传统的计算模型相比,具备极大的并行性。膜进化算法（Membrane evolutionary algorithm,MEA）是受膜计算启发的一种算法框架,有分裂、融合等算子,在许多NP问题中,MEA都表现了出优秀的性能。本文研究了求解TSP的启发式算法,在蚁群算法的基础上,从初始化策略和局部搜索策略出发,提出了动态自适应蚁群优化算法（Dynamic adaptive ant colony optimization algorithm,DAACO）,该算法能够有效提升求解TSP的性能和效率。此外,针对DAACO算法在大规模实例中的不足,结合膜进化算法框架,提出了求解TSP的动态自适应膜进化算法（Dynamic adaptive membrane evolutionary algorithm for solving travelling salesman problem,DAMEATSP）,该算法能够有效提升大规模实例中解的质量。本文主要工作内容及成果如下:（1）在蚁群算法的基础上,提出了两种改进策略,形成了DAACO算法,包括:基于凸包和聚类的初始化策略,该初始化策略使蚂蚁的数量能够自适应不同规模的实例,增加了初始解的多样性;基于“邻居对”的局部搜索策略,该策略优化了蚂蚁的寻优方式,增加了蚂蚁局部寻优的启发式信息,能够有效地避免算法的搜索过程陷入局部最优。DAACO算法在TSPLIB数据集中进行了测试,与近几年的启发式算法相比,DAACO在求解性能和求解效率都表现出了不俗的效果。（2）针对DAACO算法在大规模实例中的不足,在DAACO的基础上,结合膜进化算法框架,提出了DAMEATSP算法。在DAMEATSP中,本文设计了不同求解算子,同时引入局部匹配机制,提升了算法在求解大规模实例中的求解性能。本研究获得了解决TSP的新算法,提高了启发式算法求解TSP的性能,验证了膜进化算法解决NP问题的高效性,为求解TSP的启发式算法提供了新的思路。
其他文献
最大团问题（Maximum Clique Problem,简称MCP）是一类NP难问题,有效求解它的精确算法大多数是基于分支定界（Branch-and-Bound,简称B＆B）框架的,其中的上界策略对缩小解空间、提高算法效率起着重要作用。目前应用最广泛的是基于图着色的上界,但该上界与最优解之间常常存在一定的差距而导致解空间过大。此外它的时间复杂度总是大于O（n2）,当图规模较大时它可能对算法效率产
最近数十年,信息技术尤其是互联网领域相关技术的高速发展,催生出的数据在样本数量与维度上日益庞大。在高维数据中,样本数通常难以均匀覆盖高维空间,这将导致维度灾难,严重损害机器学习算法的性能。特征选择通过从原始特征中挑选部分特征,精简使用特征的数目,避免了样本数与维度严重不相称的情况,已成为数据挖掘领域中常用的预处理技术。近年来,基于进化计算技术的特征选择算法备受关注,这得益于它们优秀的全局搜索能力。
传统的中小学地理教学经常使用地球仪作为辅助教学工具,虽然地球仪能直观的展示相关地理区域,但是由于地球仪本身的限制而无法承载过多的信息,而增强现实（Augmented Reality,AR）技术能够将虚拟信息叠加到现实场景上进行实时交互,将AR技术与地理教学相结合可以使教学内容更加丰富、生动、有趣,能够激发学生的学习兴趣。目标检测算法具有较强的识别物体的能力,将目标检测算法与AR技术相结合,可以提高
随着互联网行业的发展,深度学习技术在各个研究领域得到了广泛的运用,特别是在计算机视觉相关领域。人脸表情识别属于学科交叉的领域范畴,它的研究可以让机器学习人类的情感,有助于提高人机交互的效率,这一技术可以推广到医疗、交通、教育等不同的日常情景。但表情识别的准确率容易受表情图像中光线、角度、细节等因素影响。因此,为进一步提升表情识别网络模型的性能,本文共分三个方面对表情识别深度网络进行改进,主要工作包
人脸表情识别作为情感计算重要的组成部分,在公共安全、智慧交通和医疗康复等领域有着巨大的应用前景。在过去的几年里,数据驱动的深度神经网络虽然将人脸表情识别准确率提高到了新层次,但是仍面临以下两个关键性难点:（1）头部的偏转造成了面部遮挡和配准误差,导致识别准确率再向上提升变得异常困难,并且难以运用到实际场景中;（2）现有数据集中存在一些不确定性表情样本,这些样本造成提取出的特征有害。为了解决以上问题
近年来,基于相空间重构（Phase-Space Reconstruction,PSR）的时间序列图像化方法因能描述时间序列的非线性信息等优点,已被用于提升时间序列分类（Time Series Classification,TSC）的性能。然而,这类方法因需要将高维相空间中的轨迹投影到二维平面,往往会导致信息丢失或造成虚假的信息,从而导致分类准确率的下降。本论文的研究目的便是分别在单变量时间序列（U
近年来,随着社会信息化程度越来越高,互联网改变了人们的生活,成为了人们生产生活中不可缺少的一部分。但是,随着网络安全问题日益凸显,人们的隐私和数据安全不断受到威胁。数字身份作为互联网的基础设施,是网络安全中的重要一环。而传统的身份管理方式下存在用户隐私泄露、身份管理效率低、数据共享困难等问题。为了改进数字身份管理方式,保障网络数据安全和用户隐私安全,本文进行了以下研究:1)为了解决集中式数字身份管
目标跟踪是计算机视觉领域一项基础性挑战任务,具有重要的学术价值与实用意义。在给定初始帧标注信息后,其任务不仅要在后续帧中对目标中心进行粗略定位,还需要进行精确的目标状态估计。近来,基于孪生架构的方法因其能在保持良好速度的同时取得较显著的性能,引起了目标跟踪领域的广泛关注。然而,孪生网络分支通常是独立的,缺乏信息交互,这限制了模型性能的进一步提升。为了增强孪生网络分支的协作能力,本文提出基于孪生架构
安防监控系统不仅能给居民提供安全保障,而且也常用于协助案件侦破。行人重识别（Person Re-identification,Re ID）技术作为计算机视觉领域的热门研究方向,旨在实现跨摄像头下快速自动地行人身份识别及检索,可以显著提高警务人员对监控数据的利用效率。然而监控视频中存在背景干扰强、行人姿态差异大等问题,夜间环境下还会进行红外模式成像,这些因素都给行人重识别带来了挑战。目前,在单模态场
随着互联网和智能终端的普及,网络文本信息量增长迅速。传统的文档级、句子级情感分析已经无法满足当前文本研究对细粒度情感倾向的需求。方面级情感分析可以对实体进行多方面、全方位的情感描述,但由于文本语言环境的复杂性,现有方法在泛化等性能上仍然存在不足,本文从方面目标情感分析和方面类别情感分析子任务入手,以深度学习为基础展开研究,主要工作和贡献如下:（1）针对于现有方面目标情感分析模型存在的参数量过大、局