基于蚁群算法求解公交线路最短路径问题

摘  要

蚁群算法(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

ABSTRACT II

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