论文摘要
需求工程——对复杂系统的软件工程的基础研究是科技部于2007年批准的国家重点基础研究项目(即973项目)。该项目选取城市交通领域的问题作为问题研究的载体,而城市交通选路问题又是其中一个重要研究内容。应用蚁群算法解决该问题是本文研究的主要内容。蚁群算法是一种新生算法,从产生伊始就用于解决旅行商(TSP)问题。该算法具有结构简单、易于实现、正反馈性和本质的并行性等优点。本文将基本蚁群算法加以改进,有效发挥了蚁群算法的特性,为交通选路问题的解决提供了一种方案。本文首先介绍了课题的研究背景和意义,阐述了城市交通选路问题的研究现状,详细介绍了基本蚁群算法,并在此基础上提出了一种改进算法:基于中心定位的蚁群算法,并在相同的实验环境下分别用两种算法进行仿真实验,结果验证了改进算法寻找最优解的速度明显比原基本算法快,且更接近于理论上的最优值,最后将基于中心定位的蚁群算法应用于交通选路问题中。具体内容如下:(1)介绍了基本蚁群算法的基本原理,以旅行商问题为背景建立数学模型,总结了算法的具体步骤,从时间复杂度和空间复杂度两方面分析了算法的复杂度,论证了算法的收敛性。(2)在基本蚁群算法的基础上对其进行改进,提出基于中心定位的蚁群算法,以旅行商问题为背景建立了新的数学模型,同样总结了改进算法的具体实现步骤,分析了改进算法的复杂度,并论证了其收敛性。(3)利用TSPLIB网站上公布的TSP数据,对基本蚁群算法和基于中心定位的蚁群算法在相同的实验条件下进行仿真实验,并对实验结果做了对比分析,验证了基于中心定位的蚁群算法的优越性。(4)以交通选路问题为例建立数学模型,设计了解决交通选路问题的实现步骤,将基于中心定位的蚁群算法应用在交通选路问题中。(5)基于真实交通数据,建立初步的交通选路系统,基本满足了交通选路问题的需求。本文的最后从四个方面对全文进行了总结,并对今后的工作进行了展望。