论文编号:YYSX246论文字数:15543
基于蚁群算法求解公交线路最短路径问题点击下载
摘 要
蚁群算法(Ant Colony Algorithm，ACA)是一种用来在图中寻找优化路径的机率型算法。它由意大利学者Dorigo、Maniezzo于20世纪90年代初首先提出，其灵感来源于蚂蚁在寻找食物过程中能从窝巢至食物源找到最短路径的行为。作为通用型随机优化算法，它吸收了昆虫王国中蚂蚁的行为特征， 具有并行性、正反馈性、健壮性等特点，通过其内在的搜索机制，已在一系列的组合优化问题的求解中取得了成效。
公交线路最短路径问题是一个要求寻找从指定起点出发务必经过各指定站点且只能经过一次最终到达指定终点的最短路径问题，是一类典型的NP完全问题，属于组合优化问题。
本文利用蚁群算法来求解公交线路最短路径问题。通过蚂蚁选择某条路径即给该路径赋一定的信息素（蚂蚁的分泌物），使得一定范围内的其它蚂蚁能够察觉到并对它们以后的行为产生影响，促使蚂蚁在某些路径上的数量越来越多。积累信息素越多的路径，成为越短路径的可能性就越大。通过实验表明，蚁群算法能有效地解决公交线路最短路径问题。
【关键词】蚁群算法，信息素，最短路径，公交线路，组合优化
Based on Ant Colony Algorithm for the Shortest Path Problem of Bus Lines
Abstract
....
【Keywords】ant colony algorithm, pheromone, shortest path, bus lines, combinatorial optimization
目录
摘 要I
ABSTRACTII
1 概述1
1.1选题背景1
1.2研究现状1
1.3课题意义2
1.4问题描述2
2 蚁群算法介绍及总体设计3
2.1蚁群算法思想起源3
2.2蚁群算法研究现状3
2.3蚁群算法的特点4
2.4蚁群算法的应用5
2.5蚁群算法原理介绍6
2.6基于蚁群算法的数学模型7
2.7基于蚁群算法的总体设计8
2.7.1实现步骤8
2.7.2程序结构流程图9
3 蚁群算法求解公交线路最短路径问题的具体实现10
3.1设定站点10
3.2初始化参数10
3.3设置起点11
3.4转移选择11
3.5信息素更新13
3.6重置到起点14
3.7输出结果14
4 数据分析15
4.1 NcMax值分析15
4.2 M值分析16
4.3 alfa值分析16
4.4 beta值分析17
4.5 rou值分析18
4.6 Q值分析19
5 总结与展望20
参考文献21
基于蚁群算法求解公交线路最短路径问题......