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

发布时间：2019-05-14 17:03

【摘要】：旅行商问题是一个经典的NP(non-deterministic polynomial)困难问题,在日常生活中比较常见,例如物流、旅游、抄表等等。由于旅行商问题的时间复杂度增长很快,精确算法很难在可接受的时间内找到最优答案。因此解决旅行商问题通常使用启发式算法,遗传算法就是其中之一。遗传算法是一种仿生算法。遗传算法将所需解决的问题抽象为种群,对种群的个体进行适应度评估,按照人工方向进行定向选择,淘汰适应度低个体,保留适应度高的个体进行基因重组和变异,经过多次迭代,得到问题的一个近似最优解。遗传算法自诞生以来得到了广泛的应用。但是,遗传算法存在对初始种群依赖性强、易早熟、收敛速度难以控制等方面的缺陷,需要对遗传算法进行改进。为了克服遗传算法的缺陷,提出遗传蚁群算法。遗传蚁群算法结合使用遗传算法和蚁群算法,将蚁群算法中的信息素引入遗传算法中。初始化过程中,遗传蚁群算法对初始种群进行基因比对,淘汰重复率过高的个体。这样可以保证初始群体均匀分布。遗传蚁群算法分为两个阶段:全局搜索阶段和快速收敛阶段。不同阶段中蚂蚁种群对信息素的反应是不同的。在全局搜索阶段,遗传蚁群算法需要充分搜索全局空间,此时蚂蚁种群对信息素是抗拒的,蚂蚁将会有更高的概率选择未被访问的路径。在快速收敛阶段,蚂蚁种群对信息素是喜好的,蚂蚁种群将会快速聚集到信息素高的路径上。以供水收费系统为应用场景,通过实际应用论证遗传蚁群算法的性能。在供水收费系统中存在抄表员抄表路径优化的问题,问题实质为求解旅行商问题。抄表员每月都会对自己负责抄表的区域进行抄表工作。通过使用遗传蚁群算法优化抄表路径,并对比、分析遗传蚁群算法的性能,证明使用该算法能够提高抄表工作的效率,节省抄表所需的时间,从而可以调整抄表工作的抄表员数量,节省人力财力。
[Abstract]:......
【学位授予单位】：山东科技大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：TP18

【参考文献】

相关期刊论文 前10条

1 陈顺立;;农业机器人路径优化及轨迹跟踪研究—基于遗传算法[J];农机化研究;2017年08期

2 李纯思;衣淑娟;;水稻浸种催芽箱温度传感器优化配置——基于遗传算法[J];农机化研究;2017年06期

3 曹思聪;夏辉;孙可;;基于蚁群算法的TSP问题分析[J];鞍山师范学院学报;2017年02期

4 金保华;岳艳;周兵;;基于改进遗传算法的otsu图像分割算法[J];湖北民族学院学报(自然科学版);2017年01期

5 伍建伟;刘夫云;李峤;;MATLAB遗传算法函数ga优化实例[J];机械工程与自动化;2017年02期

6 黄轶文;张梅;;基于蚁群算法的六自由度采摘机器人轨迹规划研究[J];农机化研究;2017年03期

7 孙文兵;;遗传算法降维优化的BP模型及葡萄酒质量预测[J];邵阳学院学报(自然科学版);2017年01期

8 王春华;邱立鹏;潘德文;;改进蚁群算法的机器人焊接路径规划[J];传感器与微系统;2017年02期

9 王云松;孙佳林;龚跃;;基于蚁群算法的云任务调度研究[J];长春理工大学学报(自然科学版);2017年01期

10 李雅琼;;基于粒子群算法的遗传算法优化研究[J];兰州文理学院学报(自然科学版);2017年01期

相关硕士学位论文 前9条

1 张鹏程;基于改进遗传算法的冷链物流路径优化研究[D];安徽理工大学;2016年

2 叶晶晶;蛙跳算法的改进及在车辆路径问题中的研究[D];广东工业大学;2016年

3 马振;改进蚁群算法及其在TSP中的应用研究[D];青岛理工大学;2016年

4 赵李明;基于遗传算法和BP神经网络的广州市空气质量预测与时空分布研究[D];江西理工大学;2016年

5 王丹;基于改进遗传算法的物流配送车辆路径问题研究[D];长春工业大学;2016年

6 潘挺雷;基于改进蚁群算法的区域车辆配送路径优化方法研究[D];浙江理工大学;2016年

7 解英全;基于遗传蚁群混合算法的机场停机位分配研究[D];西安工业大学;2015年

8 邵娜娜;蚁群算法求解最大团问题研究与应用[D];河北工业大学;2015年

9 王霜;大型TSP问题的蚁群优化规则研究[D];吉林大学;2012年

，

本文编号：2476889