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

论文摘要

遗传算法（Genetic Algorithm,简称GA）是一种通过模拟自然进化过程来搜索最优解的启发式搜索算法。由于该算法具有内在的隐并行性、良好的全局寻优能力和较强的鲁棒性,所以被广泛用于求解复杂的组合优化问题,比如旅行商问题（Traveling salesman problem,TSP）和多旅行商问题（Multiple Traveling Salesman Problem,MTSP）。TSP是经典的NP-hard组合优化问题,而MTSP是TSP的一种推广,相比TSP,MTSP具有更多的实际应用,但是研究成果却相对较少。因此本文对求解MTSP的遗传算法和MTSP的不同模型进行研究,主要研究工作如下:（1）首先针对研究较多的单起点闭回路多旅行商问题,提出了一种融合杂草算法繁殖机制和局部优化变异算子的改进遗传算法（RLGA）。该算法利用入侵杂草优化算法中以适应度为基准的繁殖机制来产生种群并进行遗传操作,以此来提高算法的搜索效率;同时提出一种混合局部优化算子作为变异算子来提高算法的局部搜索能力,从而提高收敛精度。实验结果表明,RLGA在求解工作量平衡的多旅行商问题时可以快速收敛到较优解,并且求解精度得到了很大的提高。（2）为克服固定起点闭回路多旅行商问题不能对最佳配送中心进行寻优的缺陷,提出了一种起点可寻优的多旅行商问题模型,该模型中起点未预先指定,而是允许在求解过程中进行优化。更进一步,针对这种新模型,提出了一种融合杂草算法繁殖机制的可寻址改进单亲遗传算法（RAIPGA）,并设计出了一种新的编码方式,可在种群初始化时产生含有随机配送中心的个体,以使得在算法过程中对配送中心位置进行寻优。在RAIPGA中,所采用的杂草算法繁殖机制可以产生与父代起点一致的子代,从而加快收敛速度;其改进的单亲遗传操作可同时对配送中心和路径进行寻优;混合选择算子对群体进行选择,并可避免算法陷入早熟收敛。仿真实验表明RAIPGA在寻找最佳配送中心和最短路径方面具有良好的性能,且能在旅游路径规划问题上得到很好的应用。（3）针对多起点闭回路多旅行商问题,提出了一种模糊C均值聚类单亲遗传算法（FCMPGA）。该算法首先按照欧氏距离和城市隶属度将城市分成若干类,之后将每个类作为一个TSP并通过改进的单亲遗传算法进行求解,这不仅可极大缩减算法的搜索空间,使种群在缩减后的搜索空间进行更充分的探索,且能更快地得到问题的最优解。实验结果表明,该算法在不同规模问题上均具有良好的求解性能,尤其在大规模问题上算法性能表现更优,且收敛速度更快。

论文目录

文章来源

类型: 硕士论文

作者: 胡士娟

导师: 鲁海燕

关键词: 遗传算法,多旅行商问题,繁殖机制,模糊均值聚类,变异算子

来源: 江南大学

年度: 2019

分类: 基础科学,信息科技

专业: 数学,自动化技术

单位: 江南大学

分类号: TP18;O224

总页数: 52

文件大小: 3874K

下载量: 977

相关论文文献

• [1].针对旅行商问题的改进循环交叉算子遗传算法[J]. 现代计算机 2020(16)
• [2].对称型旅行商问题在工程运输中的应用[J]. 四川建材 2020(07)
• [3].基于多旅行商问题的应急设施服务区划分模型[J]. 交通运输系统工程与信息 2020(05)
• [4].使用动态规划解决旅行商问题[J]. 科技与企业 2016(03)
• [5].带油耗的单商品取送货旅行商问题研究[J]. 物流科技 2016(04)
• [6].求解复杂旅行商问题的混合粒子群算法[J]. 轻工机械 2015(03)
• [7].多旅行商问题研究综述[J]. 价值工程 2012(02)
• [8].基于并行遗传算法多旅行商问题的求解[J]. 微型电脑应用 2011(07)
• [9].子旅行商问题及其蚁群求解算法[J]. 计算机应用与软件 2011(11)
• [10].基于自组织优化算法的一类多旅行商问题[J]. 计算机应用 2010(02)
• [11].多源点的旅行商问题的一种求解方法[J]. 科协论坛(下半月) 2010(09)
• [12].基于遗传算法的一类多旅行商问题研究[J]. 计算机应用 2009(01)
• [13].基于仿真的遗传算法求解动态旅行商问题[J]. 系统管理学报 2009(05)
• [14].改进蜂群算法求解大规模着色瓶颈旅行商问题[J]. 通信学报 2018(12)
• [15].基于离散粒子群优化算法的含权旅行商问题新解法[J]. 计算机应用与软件 2019(01)
• [16].关于旅行商问题的数学模型[J]. 科学技术创新 2019(17)
• [17].遗传算法在旅行商问题的研究与应用[J]. 工业控制计算机 2013(11)
• [18].不确定旅行商问题的鲁棒模型与算法[J]. 计算机应用 2014(07)
• [19].基于遗传算法的旅行商问题的研究[J]. 安阳师范学院学报 2012(02)
• [20].一类多出发点多旅行商问题规划算法[J]. 山东理工大学学报(自然科学版) 2011(02)
• [21].浅谈旅行商问题与蚁群算法[J]. 黄冈职业技术学院学报 2010(06)
• [22].基于遗传算法的多旅行商问题研究[J]. 计算机应用研究 2009(05)
• [23].动态旅行商问题的研究[J]. 计算机工程 2008(10)
• [24].基于猴群算法求解旅行商问题[J]. 计算机工程与应用 2018(02)
• [25].浅谈旅行商问题与粒子群优化算法[J]. 电子制作 2015(09)
• [26].求解多旅行商问题的新混合遗传算法:以应急物资配送为例[J]. 系统管理学报 2014(02)
• [27].旅行商问题分支限界法的一个注解[J]. 洛阳师范学院学报 2011(08)
• [28].旅行商问题模型应用——巡检线路选择[J]. 花炮科技与市场 2019(01)
• [29].面向多旅行商问题的多目标模拟退火算法研究[J]. 南京师大学报(自然科学版) 2017(03)
• [30].求解最小比率旅行商问题的混合行为蚁群算法[J]. 合肥工业大学学报(自然科学版) 2016(01)

标签：遗传算法论文;  多旅行商问题论文;  繁殖机制论文;  模糊均值聚类论文;  变异算子论文;