唐伟[1]2008年在《基于改进遗传算法的TSP问题求解研究》文中研究表明旅行商问题(Traveling Salesman Problem,TSP)就是要决定一条经过图中所有顶点当且仅当一次且距离最短的回路,即距离最短的Hamilton回路。TSP问题是一个具有广泛的应用背景和重要理论价值的组合优化问题,属于典型的NP问题。因此,对TSP问题有效求解算法的研究具有十分重要的意义。本文通过对遗传算法和TSP问题求解的相关方法的分析与研究,提出了一种求解TSP问题的改进遗传算法,并通过具体实例验证了改进算法的有效性。首先,问题的规模对于TSP问题的求解来说是一个很重要的因素,其时间复杂度将随着问题规模呈指数形式增长。因此,分块求解方法是求解TSP问题的一种可行的方法。本文提出了一种基于最小生成树的TSP问题分块求解算法,以此达到降低问题的规模、缩短算法运行时间的目的。其次,交叉算子是遗传算法的核心算子,是遗传进化的动力。本文在研究EAX交叉算法的基础上,通过对比分析,指出多个子环路合并为一个环路的算法是EAX算法的一个瓶颈。为此,本文提出了多阶段环路合并算法解决该问题。同时,改进EAX算法中的e-set选择策略,并对EAX算法的解采用混合的局部搜索算法来加以修正。最后,针对所提出的改进算法,本文选择TSPLIB中典型的TSP问题实例,进行实际验证。实验结果表明,本文所提出的改进算法能够有效地求解TSP问题,使求解效率得到了一定的提高。
杨鸣[2]2008年在《动态多目标TSP演化算法研究》文中研究说明在科学管理与经济决策的许多应用领域中,现实世界存在着大量的动态多目标优化问题。对于旅行商问题(Traveling Salesman Problem,TSP),实际中经常要同时考虑多个目标,如路程最短、时间最短、费用最省、风险最小等多方面的因素。目标之间往往存在冲突性。如何在多个目标中寻找一个公平、合理的解是比较复杂的问题。此外在实际生活中,大量的多目标优化问题具有实时性,问题的状态随着时间变化。这些优化问题除了具有多个目标的性质外,同时还具有动态性。动态多目标TSP是从移动计算、移动通信等应用领域中提出的一类新的Np-难的数学理论模型,它属于演化计算的一个最新的研究领域。动态多目标TSP是动态TSP和多目标TSP的结合,是作为航天通信(地基、空基与天基相互之间进行通信)的数学理论模型于2004年首次提出来的。与经典的TSP、静态多目标TSP、动态单目标TSP相比,动态多目标TSP更复杂,具有更大的挑战性。它要求实时跟踪动态变化的最优Pareto前沿。动态多目标TSP的研究将推动一些实际问题,如:移动计算、移动通讯、航天通信等网络拓扑设计与路由算法的研究和发展。所以研究动态多目标TSP具有重大的理论意义和应用价值。本文前两章介绍了TSP的基本知识、研究现状和遗传算法的基础理论知识。第叁章到第五章,介绍了作者对动态多目标TSP取得的研究成果。动态多目标TSP中有一些重大理论问题没有解决,例如:动态程度的度量问题,目标之间的冲突程度的度量问题,动态多目标优化算法的性能的评估问题以及Pareto最优解的数目与目标冲突程度的关系问题等。在第叁章中,对动态多目标TSP的动态程度和目标冲突程度的度量问题进行了研究。首次提出了动态程度和目标冲突程度的概念。问题的动态变化是通过代价矩阵的变化体现的,度量动态变化程度就是比较代价矩阵发生了多大的变化;而度量目标冲突程度则是比较各个目标的代价矩阵之间的冲突程度有多大。所以,度量问题的动态程度和目标之间的冲突程度就是度量某些代价矩阵的相异程度。根据上述思路,首次给出了问题的动态程度和目标冲突程度的度量方法。根据这些方法,可计算出动态多目标TSP问题的状态发生了多大的变化和目标之间的冲突程度。它们对动态多目标TSP的算法设计具有重要的指导意义。并且提出了动态多目标TSP优化算法的评估准则Paretos-Similarity。它可以从Pareto解集中解的数目、Pareto解集中每一个目标的最佳逼近度、Pareto解集的平均逼近度、Pareto解集分布的均匀性与多样性四个因素综合地评估某一Pareto解集与最优Pareto解集的逼近程度。根据Paretos-Similarity可对算法得出的解的质量和算法的性能进行有效地评价。在第四章中,提出了DMOInver-Over算法求解动态多目标TSP,它是Inver-Over的动态多目标版本,其通过Inver-Over算子和动态弹性松弛算子相结合来求解动态多目标TSP。实验中以两个目标的叁维标准测试问题CHNl44+5为例,对本文提出的DMOInver-Over的有效性进行了验证。从实验中可以看出,DMOInver-Over通过Inver-Over算子和动态弹性松弛算子相结合,配合下一代种群的生成规则生成新种群,可以在比较短的时间内得到一个近似最优Pareto解集。对于动态多目标TSP,问题的状态和特征是随着时间变化的。根据优化问题的定理NFLTs,采用单个算法设计的方法已经不能有效地求解这类极其复杂、多变的优化问题。在第五章中,提出了一种新的求解动态多目标TSP的算法设计方法:多算法的协同演化策略(multi-algorithm coevolution strategy,MACS)。MACS采用在一次迭代过程中,运行多个算法生成新种群,通过多算法协同演化,可以充分发挥全局优化算法和局部优化算法的性能,达到多个算法的优势互补,避免单一算法的局限性;可以在加快算法收敛速度的同时,保持Pareto解集的多样性,保证Pareto前沿的均匀分布。实验中以两个目标的叁维标准测试问题CHN144+5为例,对本文提出的MACS的有效性进行了验证。实验结果表明,MACS比单个算法的优化方法收敛速度更快,求得的Pareto解集的多样性更好,解的分布更加均匀,可以有效地求解动态多目标TSP。
黄美玲[3]2007年在《蚁群优化算法的研究及其应用》文中认为蚁群算法是一种最新发展的模拟昆虫王国中蚂蚁群体觅食行为的仿生优化算法。在解决许多复杂的组合优化问题方面，展现了优异的性能，但在解决实际问题中仍然不够成熟，还有很大的发展空间。本文针对目前蚁群算法在解决实际组合优化问题时存在的一些缺陷，在大量阅读相关文献的基础上提出了几个可能性方面的改进方法及改进策略。本文主要工作是在蚁群算法实验性分析的基础上对算法模型进行改进，具体体现在通过对蚁群算法的一系列实验性分析，找到较为合理的参数组合范围和组合原则；信息素更新机制方面，首次引入了“先验因子”的概念，在信息素更新的时候更好地考虑先前的“经验”，以便尽力避免不必要的无用搜索；以及采用融合Hopfield神经网络的策略解决TSP问题。在解决实际TSP时，首先对所有城市所组成的无向图进行预处理，去掉其中的交叉路径；然后采取蚁群算法和人工神经网络中的Hopfield神经网络模型相融合的策略，利用改进后的蚁群算法来求解神经网络中的所有参数的较优组合，再用蚁群算法训练后Hopfield神经网络对TSP进行求解。最后，通过基准问题库中的Ei151TSP和Att48TSP的求解，验证了改进后的蚁群算法的可行性以及改进后的蚁群神经网络应用于求解TSP的高效性。
武交峰[4]2007年在《应用遗传算法提高蚁群算法性能的研究》文中研究表明蚁群算法(ant colony algorithm简称ACA)是最近几年才提出来的一种新型的模拟进化算法，它来源于对真实蚂蚁群体寻找从巢穴到食物源最短路径方法的模拟，体现了真实蚁群的协作过程。算法由若干个蚂蚁共同构造解路径，通过在解路径上释放信息素，借助选择策略、信息素更新等操作来提高解的质量，进而达到优化的目的。可见，它是一种随机搜索算法。蚁群算法不仅能够智能搜索、全局优化，而且具有高度的本质并行性、正反馈性、鲁棒性及协同性等优点，在解决复杂优化问题上显示出了良好的适应性，具有许多优良品质和实际应用价值，是一种很有前景的方法。因此，蚁群算法的研究无论从理论上还是实用上都具有较高的价值。作为一种近年提出的新算法，蚁群算法还没有像遗传算法、模拟退火算法等那样形成系统的分析方法和坚实的数学基础，算法中各个参数的选择也没有理论上的指导；算法初期信息素匮乏，导致搜索时间较长；算法运行过程中容易出现收敛过早或停滞现象；不能扩大解的搜索范围；不能很好的利用当前解所带的信息等。本文以基本蚁群算法的性能分析为背景，通过实验分析了基本蚁群算法中五个参数：启发因子α，期望因子β，信息素挥发度ρ，蚂蚁数量m以及总信息量Q各自对算法性能的影响。实验结果表明α，β，ρ这叁个参数对算法的影响较大，并且他们的作用是紧密耦合的。目前对于这些参数的选择大多以经验或试验来确定，造成试验工作量大且难以得到最佳的参数配合，影响了算法的使用。本文利用遗传算法来优化这叁个参数，并将其应用在TSP问题的仿真实验中。实验表明，该方法能够快速的找到一组较优解，可使蚁群算法获得较优的运行性能，说明了该方法的可行性和有效性。本文在查阅大量国内外参考文献的基础上，针对前面基本蚁群算法初始信息素匮乏的缺陷，给出一个可行的解决方案：将蚁群算法与遗传算法相结合形成混合算法(GA-ACA)。其基本思路是：算法一开始充分利用遗传算法快速性、随机性、全局收敛性的特点，搜索出待求解问题的初始信息素分布；然后在此初始信息素分布的情况下，充分利用蚁群算法并行性、正反馈性、求精解效率高等特点来求解。此外，GA-ACA混合算法相对于基本蚁群算法在以下几个方面进行了改进：①引入确定性与随机性相结合的选择策略，减少算法陷入局部解的概率；②对局部信息素与全局信息素采用自适应的信息素更新策略动态调整，更好的利用当前解；③引入2-opt局部搜索算法来扩大解的搜索空间。将混合算法在经典的组合优化问题旅行商问题(TSP)和二次指派问题(QAP)上进行了仿真验证。实验结果表明，该混合算法不但加速了蚁群算法的收敛速度，而且提高了所得优化解的质量。
朱林杰[5]2007年在《基于TSP的遗传算法优化研究》文中认为在人工智能领域中，研究在搜索过程中自动获取和积累有关搜索空间的知识并自适应地控制搜索过程从而得到最优解的通用搜索一直是令人瞩目的课题。旅行商(TSP)问题是组合优化领域中的一个典型问题，虽然它陈述起来很简单，但求解却很困难，并且已经被证明是NP完全问题。遗传算法是借鉴生物界自然选择和进化机制发展起来的全局的概率搜索算法。在众多解决TSP问题的方法中，遗传算法有着其他方法不具备的很多优点，对于中小规模TSP问题，遗传算法可以得到最优解，对于大规模TSP问题，可以得到近似最优解。本文通过对遗传算法常见的各选择算子，交叉算子，变异算子进行比较，确定了以效果较好的锦标赛精英选择、部分映射交叉，移位变异和插入变异为基础的算子进行优化。针对锦标赛精英选择过于集中在少数优良个体的现象，提出了一种新的选择方法：差异双亲锦标赛精英选择法。针对于倒置变异和插入变异各自的优缺点，提出了一种新的变异方法：倒置-插入混合变异法。对已有的算法和改进的算法进行了比较，采用随机生成位置的城市，比较固定代数后算法解的好坏。实践证明，改进后的算法能够产生更好的解。此外，还得到另一个结论：相同城市数目的TSP问题，用同样的方法如果采用环型排列的城市能得到最优解，用随机排列的城市未必能得到最优解，所以环型城市TSP测试不具有通用性。本文测试工具为FLASH，全部代码由Action Script2.0语言编写。
汪采萍[6]2007年在《蚁群算法的应用研究》文中研究说明蚁群算法是一种新型仿生类优化算法，是继模拟退火、遗传算法、禁忌搜索等之后的又一启发式智能优化算法。蚁群算法由意大利学者M. Dorigo等人首先提出，并成功地应用于求解一系列NP完全的组合优化问题，如：旅行商问题、二次分配问题、车辆寻路问题和图着色问题等等。蚁群算法从提出到现在，短短十余年的时间，以其在离散型组合优化问题中的突出表现，吸引了人们的极大关注。论文针对基本蚁群算法收敛速度较慢和算法容易出现停滞现象的缺点，对蚁群算法进行研究，提出了两种改进的蚁群优化算法，并分别应用于TSP问题和多维0-1背包问题。论文的研究工作主要包括以下两个方面：1．改进的蚁群算法应用于TSP问题的研究。提出一种求解TSP问题的具有分段和变异特性的蚁群算法SMAS。该算法融合了分段的分而治之思想和遗传算法中的变异，有利于保持群体多样性的特性，是在采用轮盘赌方式的最大最小蚁群算法陷入局部最优解的情况下，引入随机分段和遗传算法的变异操作来优化当前最优解，改善解的质量，有效地改善了蚁群算法易于过早地收敛于非最优解的缺陷。2．改进的蚁群算法应用于多维0-1背包问题的研究(MKPACA)。0-1背包问题是典型的NP完全问题，且蚁群算法已成功地解决了许多组合优化的难题。因此，论文提出一种求解多维0-1背包问题的蚁群算法——MKPACA，当物品数较大时，也取得了较好的求解质量。在MKPACA中，引入受益量密度的概念，改变概率计算的时机，并采用“轮盘赌”方式根据概率p_j选择下一个物资，这样既兼顾了概率大小，又增加了搜索的随机性，兼顾解空间的多种情况，有效改善了蚁群算法搜索速度慢且易于过早地收敛于非最优解的缺陷。
吴兴健[7]2011年在《基于改进的遗传蚁群混合算法的TSP问题求解研究》文中研究说明TSP问题是一个典型的组合优化问题,也是一个易于描述却难以处理的NP难题。针对TSP问题的研究,长期以来,人们一直在寻求一种高效、快速的近似算法,以便在合理的计算时间范围内准确地求解一个规模较大问题,其中,典型的智能优化算法有蚁群算法和遗传算法以及两者的混合算法等。本文主要研究一个改进的遗传蚁群混合算法并用于求解TSP问题,其主要研究工作如下：(1)结合TSP问题的特点,在求解初期,应用Delaunay叁角剖分的候选集策略来减少求解问题的搜索空间,以加快搜索速度,并以此作为运用改进算法求解TSP问题的基础。(2)重点分析了蚁群、遗传及其传统的混合算法的不足,针对这些缺陷提出了一些改进：1)引入动态融合的策略以确保两种算法的最佳融合时机；2)引入灰预测模型对最大最小蚁群算法信息素限界进行估计；3)引入云关联规则,实现混合算法的参数自适应调节。经过这些改进,使得遗传算法与蚁群算法更好地的动态融合在一起,充分发挥各自优势,更高效地用于求解TSP问题。为了验证改进算法的性能,本文利用TSPLIB提供的实验数据,对比分析了本文所提出的改进算法与最大最小蚁群算法、改进前的遗传蚁群混合算法的运行结果。结果表明,本文所提出的改进算法的性能相对较优。
杜宗宗[8]2009年在《基于遗传算法的移动机器人路径规划研究》文中指出移动机器人是机器人领域的一个重要发展方向,而路径规划是移动机器人系统中的一个重要内容,因为它的好坏直接影响到机器人所完成任务的质量,所以路径规划成为移动机器人领域的一个研究热点。本文中的移动机器人路径规划包含两方面的内容:避障路径规划和TSP路径规划问题。避障路径规划是指依据某个或某些优化准则,在其工作空间中找到一条从起始点到目标点能避开所有障碍物的一条最优路径。TSP路径规划问题是指已知几个城市之间的相互距离,现有一个推销员必须遍访这几个城市,并且每个城市只能访问一次,最后又必须返回出发城市,如何安排他对这些城市的访问次序,使其旅行路线总长度最短。本文首先讨论了路径规划技术的发展现状以及应用方法,也指出了本课题的研究意义和主要研究的内容。其次通过对遗传算法和模拟退火算法的研究,分析了各自的优缺点。并把这两个算法结合构成了遗传模拟退火算法,它兼备了很强的全局和局部搜索能力,在变量数目较大时尤其突出。把遗传模拟退火算法运用到避障路径规划当中,并采用新型的初始种群生成算法,仿真结果表明这种算法使移动机器人避障路径规划提高了收敛速度,达到了较好的规划效果。最后研究了运用遗传算法求解TSP路径规划问题,对基本遗传算法的求解TSP路径规划问题进行了改进。为了解决群体的多样性和收敛速度的矛盾,本文采用了依概率近邻法来生成初始种群,这种初始种群生成方法较近邻算法略差,但个体多样性水平优于近邻算法。为了在遗传算法的整体运行过程中保持种群多样性、提高收敛速度,本文将相似性、群体分级等概念引入到遗传算法中,将等级较高的个体采用启发交叉算法进行交叉,并采取杰出者记录与“父子混合”选择策略来保证算法的全局收敛性,仿真结果证明了改进算法的有效性。
孙海雷[9]2007年在《改进的遗传算法求解TSP问题》文中提出遗传算法是一种模拟自然界生物进化的搜索算法,由于它简单易行、鲁棒性强,尤其是不需要专门的领域知识而仅用适应度函数作评价来指导搜索过程,从而使它的应用范围极为广泛,并且已在众多领域得到了实际应用,取得了令人瞩目的成果,引起了广大学者和工程人员的关注。TSP问题是一个典型NP难题,具有广泛的应用,多年来一直是学者们研究的热点。由于大多数学者认为NP问题不存在多项式时间内的完全算法,因此设计TSP问题的近似算法具有非常重要的意义。TSP问题还成为了衡量近似算法效率的主要标准。本文对遗传算法的理论与应用进行了一些研讨。首先介绍了遗传算法的基本原理及其应用,其次分析了TSP问题的研究现状、数学模型、求解方法等,最后在标准遗传算法的基础上提出了改进的遗传算法。针对TSP问题的特点,在遗传算法的交叉过程中对边的邻接状况采用了新的评价标准,结合顺序交叉算子和贪婪策略,本文设计提出了两种新的交叉算子:顺序插入交叉算子与动态顺序插入交叉算子,它们有效地利用了局部信息,并且能很好地继承父代的优秀基因段,实例仿真表明了该算法的可行性和有效性。
姜昌华[10]2007年在《遗传算法在物流系统优化中的应用研究》文中研究指明物流已被认为是继降低原材料消耗和提高劳动生产率之后的“第叁利润源”。通过优化物流系统,可以降低物流成本,从而增强企业的市场竞争能力。因此,研究物流系统中的优化问题,具有十分重要的意义,是国内外研究的一个热点。库存成本与配送成本是物流系统的核心成本,在物流总成本中占据了很大的比例。如果能降低库存成本与配送成本,就能有效地降低物流成本。遗传算法是一种应用很广泛的智能优化算法,本文对遗传算法进行了分析研究,针对遗传算法的一些缺陷提出了相应的改进方法。在上述研究基础上,本文基于遗传算法,研究了物流系统中的库存优化问题及车辆路径问题。本文将库存仿真优化问题与车辆路径问题都看作是组合优化问题,并应用遗传算法进行求解。本文的主要研究工作及贡献可归纳如下:(1)对随机库存系统建立了基于离散事件系统的计算机仿真模型。用系统仿真方法求解最优库存策略时,其难点之一在于仿真的优化。为此,本文将计算机仿真技术和遗传算法相结合,应用遗传算法来优化模型的控制参数,即获得最优的库存控制策略。针对随机系统的特点,设计了候选解收集器,它能够收集在仿真优化过程中产生的Pareto解;提出了M精英选择算子,用于保护潜在的最优个体,使它们在交叉、变异算子中不被破坏。针对两种常用的库存控制策略进行了仿真优化的实验,结果表明本文提出的仿真优化方法是有效的。(2)旅行商问题(TSP)是车辆路径问题的子问题。为了求解TSP问题,研究了常用于TSP问题的叁种交叉算子的优化效果,提出了一种求解TSP问题的高效混合遗传算法HGA-TSP。在该算法中以变形的OX算子作为交叉算子,以2-opt算法作为遗传算法的变异算子;提出了K近邻点集的概念以缩减搜索空间并提高算法的时间效率。(3)将单配送中心,多辆运输车且无约束的车辆路径问题建模成具有总路径长度最短、子路径长度均衡性好这两个目标的双目标多旅行商问题(MTSP),并基于HGA-TSP算法,研究了叁种求解上述问题的解决方案。(4)对于带能力约束的车辆路径问题(CVRP),提出了一种新的双层染色体编码方案和一种子路径交换算法。双层染色体编码方案不需要预先知道最优解所需要的车辆数,并能确保染色体不违反能力约束,这更适合求解实际物流配送系统中的车辆路径问题。此外,相对于常用的单层染色体编码方案,该编码方案还能降低搜索空间的大小,从而提高搜索效率并降低计算时间。子路径交换算法可以有效提高遗传算法的求解精度。基于上述双层染色体编码方案和子路径交换算法,设计了两种求解CVRP问题的混合遗传算法,分别是HGA-CVRP算法和HGA-SE-CVRP算法。(5)对于带时间窗约束的车辆路径问题(VRPTW,首先改进了双层染色体编码方案,以便在编程实现时更方便地进行子路径的处理。然后研究了遗传算法与邻域搜索算法的结合方式,在遗传算法中引入了带克隆操作的邻域搜索算子。最后提出了一种求解VRPTW问题的新型混合遗传算法HGA-VRPTW。(6)综合应用了面向对象分析与设计、多线程、UML等先进的软件开发方法与技术,设计并开发了VRP仿真实验室,这是一个用于研究车辆路径问题的软件包,具有使用简便、界面美观的特点。VRP仿真实验室在本文的研究中发挥了重要的作用,是研究车辆路径问题的有力工具。本文对大量的基准测试实例(Benchmark)进行了仿真计算,计算结果表明,本文所提出的一系列算法能有效求解物流系统中的库存优化问题与车辆路径问题。
参考文献：
[1]. 基于改进遗传算法的TSP问题求解研究[D]. 唐伟. 大连海事大学. 2008
[2]. 动态多目标TSP演化算法研究[D]. 杨鸣. 中国地质大学. 2008
[3]. 蚁群优化算法的研究及其应用[D]. 黄美玲. 南昌大学. 2007
[4]. 应用遗传算法提高蚁群算法性能的研究[D]. 武交峰. 太原理工大学. 2007
[5]. 基于TSP的遗传算法优化研究[D]. 朱林杰. 大连理工大学. 2007
[6]. 蚁群算法的应用研究[D]. 汪采萍. 合肥工业大学. 2007
[7]. 基于改进的遗传蚁群混合算法的TSP问题求解研究[D]. 吴兴健. 大连海事大学. 2011
[8]. 基于遗传算法的移动机器人路径规划研究[D]. 杜宗宗. 江南大学. 2009
[9]. 改进的遗传算法求解TSP问题[D]. 孙海雷. 重庆大学. 2007
[10]. 遗传算法在物流系统优化中的应用研究[D]. 姜昌华. 华东师范大学. 2007
标签：数学论文; 遗传算法论文; 蚁群算法论文; 路径规划论文; tsp论文; 信息素论文; 系统仿真论文; 混合策略论文; 多目标优化论文; 优化策略论文; 算法论文; tsp问题数学模型论文;