蚂蚁算法在车辆路径问题中应用研究

中南民族大学

硕士学位论文蚂蚁算法在车辆路径问

题中的研究姓名：程满中申请学位级

别：硕士专业：计算机应用技术指导

教师：王江晴

20070528

摘要

车辆路径问题（Vehicle「outing problem,简记VRP)是一个经典的组合优化

问题，是多种复杂问题的一种简化形式。VRP问题的搜索空间随着客户点和约束条件的

增加而增大，在庞大的空间中寻找最优解，需要大量的求解时间，因此研宄者希望采用一种求解时间短且能得到精度较高的近似解的算法来解决此类问题。

蚂蚁算法是受大自然中蚂蚁觅食启发而产生的一种智能仿生算法，具有简单通用、鲁棒性强、自调节能力出色、易于扩展、适合分布处理等特点，因此借助蚂蚁算法解决VRP问题具有非常现实的意义。本文采用蚂蚁算法来求解VRP问题，主要的研宄工作如下：

第1章通过对大量相关文献进行分析、总结和提炼，对VRP问题的起源和发展、研宄及应用的价值以及研宄的现状进行了综述，阐明了论文研宄的背景及意义、选题的理由及本文的主要工作。

第2章介绍了蚂蚁算法的基本原理、应用范围、研宄现状以及发展；分析了蚂蚁算法的特点和它的理论基础；讨论了基本蚂蚁算法模型、蚂蚁算法的优化方法以及算法的关键技术。

第3章描述了 VRP问题的数学模型，分析了 VRP问题所包含的各类约束条件，总结了求解VRP问题的几种方法及其特点。

第4章设计并实现了基于蚂蚁算法的优化算法以求解VRP问题，对蚂蚁算法的转移规则、信息素更新规则、终止条件以及参数的设置进行了深入分析及优化，通过研宄所做的工作，使得算法能得到比较优的解。

第5章对本文设计的算法进行了数值实验，并将实验的结果与其他文献上的实验结果进行了分析和比较，证实该算法能达到较好的效果。

第6章总结了全文的主要工作及创新点，分析了研宄中的不足，并展望了未来的研宄方向。

关键词：蚂蚁算法；VRP问题；组合优化；群集智能

Abstract

Vehicle routing problem (VRP) is a typical combinatorial optimization problem, which is a simplified form of various complex problems. Search space of VRP

increases along with the increase of customers and constraint condition. It will take a long time to search the best result from a huge space. So researchers hope to adopt a method, which can shorten the solving time and obtain an approximate result with high precision, to solve this problem.

Ant algorithm is a new type of swarm intelligent algorithm. It takes inspiration from the observations of ant colonies foraging behavior that ants can find the shortest paths between food sources and their nests. It is simple, common, robust, excellent in self-adjusting, easy to expand and suitable for parallel process, etc. Solving VRP with the help of ant algorithm is of practical importance. This paper adopts ant algorithm to solve vehicle routing problem. The main work is as follows:

In chapter 1, based on summarizing relative references, we summarize the origin, progress, research, application and practicality of vehicle routing problem; clarify the background, reason and significance of the research; point out the research field in this thesis.

In chapter 2, we introduce the basic principle, applied domain, current researches and development of ant algorithm; analyze its characteristics and theories; discuss its mathematic model, improved method and important techniques.

In chapter 3, we describe the mathematics model of VRP; analyze all constraint conditions of the problem; summarize some methods for solving vehicle routing problem and their characteristics.

In chapter 4, we design and realize an improved algorithm based on simple ant algorithm to solve vehicle routing problem; analyze and improve the transition rule, pheromone update formula, ending condition and adjusting parameter. Through the

work done in the research, better results can be obtained.

In chapter 5, we do experiments on the algorithm designed in this thesis;

analyze and compare the results of experiments with those of other papers; thereby verify its feasibility and validity.

In chapter 6, we point out main researcher work and innovation of the thesis; analyze the shortcomings of research on vehicle routing problem and look forward the research orientation in the future.

Key words: Ant algorithm; VRP; Combinatorial optimization; Swarm intelligence

中南民族大学

学位论文原创性声明

本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任何其他个人或集体己经发表或撰写的成果作品。对本文的研究做出重要贡献的个人和集体，均己在文中以明确方式标明。本人完全意识到本声明的法律后果由本人承担。

作者签名：日期：年月日

学位论文版权使用授权书

本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅。本人授权中南民族大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文。

本学位论文属于

1、保密口，在___________ 年解密后适用本授权书。

2、不保密0。

(请在以上相应方框内打“V”）

作者签名：日期：年月日导师签名：日期：年月日

第1章绪论

1.1论文选题背景与意义

人类在征服自然、改造自然的进程中，一直伴随着各式各样的物流活动。可以这么说，人类的文明史就是一部物流发展和变革的历史，经济的发展和科学技术的进步促进了物流活动的广度和深度，而物流活动的扩大和深化又进一步推动了经济和社会的发展。尽管物流活动自古有之，但是直到1915年才第一次在书本上出现了“物流”这个名词。经过近百年的理论研宄和实际运作，人们认识到合理、高效的物流能够从以下几方面创造社会财富：

(1)促进国民经济合理布局，有利于社会资源的优化配置；

(2)有效地使用流通设施和设备，节约社会资源；

(3)减少流通环节，缩短生产周期，加速资金周转；

(4)简化信息流通渠道，增强社会物质财富的可调节性；

(5)促进社会分工，加速生产的集中化、规模化。

在现今社会中，物流已经成为企业最重要的竞争领域之一，政府、企业和研宄机构纷纷将注意力转向以系统化、信息化、敏捷化和顾客导向为特征的物流管理现代化。物流领域涉及很多方面，因此，对物流的研宄也逐渐成为研宄的热点。

1.1.1VRP问题起源与发展

车辆路径问题（Vehicle routing problem,简记VRP)[1]是物流配送供应领域

中一个常见问题,首先由线性规划大师Dantzig和Ramse「在1959年提出的，他们把需求的对象称为顾客（custome「或consumer)，把顾客的所在位置称为需求结点 (node),把满足顾客的需求称为服务（service),把提供服务所使用的工具或人称为服务车辆（vehicle),把车辆的出发地称为中心（depot)。

从而VRP问题可描述如下：已知有一批客户，各客户点的位置坐标（或相互间的距离）和货物需求量已知，供应商具有若干个可供派送的车辆，运载能力给定，每辆车都从配货中心出发，完成若干客户点的运送任务后再回到配货中心。现要求以最少的车辆

数，最小的车辆总行程来完成货物的派送任务。

VRP问题提出以后，关于其的研宄已经经历了三个阶段。第一个阶段为古典的 VRP 问题研宄阶段。这一阶段主要研宄一些具体的问题，并提出了一些著名的算法。但是这时的算法多注重具体问题的派车方案，不太注意路径长度或费用的节省，而且只能处理顾客较少的问题，可移植性较差。第二阶段为基于数学规划或网络分析的VRP问题的研宄阶段。这一阶段因为数学规划和网络分析有了一定的发展。人们开始用数学规划和网络的最大和最小流来研宄VRP问题，可以说这个阶段的算法是十分精确的。但是因为VRP 问题是离散的，所建立的数学规划或者网络模型是整数规划或复杂的网络。它们的求解很困难，甚至不能求解，即使能求解，也只能处理小规模的问题。第三阶段为基于人工智能算法的VRP问题的研宄阶段。人们利用模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法和蚂蚁算法等来研宄VRP问题。它们能处理较大规模的VRP问题，可移植性强，能在合理的时间内给出问题的接近最优解或者近似最优解，是值得推广的算法。

1.1.2VRP问题的研究与应用价值

VRP问题是一个典型的组合优化问题。在许多物流配送系统中，管理者们需要采取有效的配送策略以提高服务水平、降低货运成本。VRP问题就是此类问题的集中概括和简化形式，它在可计算理论上具有重要的理论意义，同时也具有重要的实际应用价值。该问题在很多领域中有广泛的应用，如货物运输、加工调度、港口货物调配等，经过简化处理后都可建模为VRP问题。因此，能够快速有效的解决VRP问题有着极高的实际应用价值。

VRP问题是运筹学中的一个重要分支，与日常生活联系很紧密，有广泛的应用，下面就是几个典型的应用例子。

1、物流业的配货问题

在物流业，特别是针对大型连锁超市，往往需要从仓库给各个超市运送货物，各个超市有不同的货物需求，则运输部门要根据不同的需求订单、送达地点、货种、数量以及自己的运力情况，安排一个最合适的运输方式，在满足各个超市需

_____________________ 中南民族大学硕士学位论文_____________________

要的前提下使得运输的路线最短或者说运输成本最低。

2、学校班车路径和计划问题

很多学校的班车经常要面对一个问题，比如在一个区域里面住了学校的很多老师，单位的班车要在每天的固定时刻到这个区域的各个站点接等车的老师去学校，要求在给定的时间区域和空间区域中能够满足所有老师的乘车需求并且要满足使用最少的汽车数和最短的路径长度来节约运输开支。

3、运输行业的电话预约问题

运输行业有种电话预约服务，一些顾客打入电话，请求服务，每个顾客都有自己的上车和下车地点，一个特定的上车和下车时间区间。问题是如何安排行车路线和派车计划，使得顾客最大限度的满意并且使行业利润保持最高。

4、飞行计划问题

80年代以来，航空领域内的飞机及其机组计划问题日益受到重视。由于飞机的一次运行固定费用几倍于机组人员的费用，所以运行的计划比运行时间更重要， VRP问题模型在该领域得到了广泛的应用。

1.1.3VRP问题的研究现状

VRP问题的求解，一直以来倍受人们的关注。对于这样一个典型的、易于描述却难以处理的NP难题，有效地解决它在可计算理论上有着重要的理论价值。并且VRP问题在诸多领域内，特别是在物流、仓储等方面，有着极高的实际应用价值，因此更具有重要的现实意义。也就吸引了众多领域的学者对它进行研宄。尽管VRP 问题仍未找到一种最好的方法来得到最优解，但是求解它的算法在逐渐改进。

对求解VRP问题，国内外目前基本都在人工智能领域进行探讨研宄，在多种智能算法理论研宄方面有了一定的进展。对于某些特定的问题，采用智能算法在求解时间和得到解的质量上都获得了较满意的结果。但是这类算法也有很多的局限，比如有些算法缺乏坚实的数学理论基础，有些尚停留在对仿真实验的数据分析基础上，算法的理论方面还有许多需要解决的问题，对算法本身的优化改进还有许多工作可以去做。

目前，在VRP问题设计上，基本上还是处在没有或者只存在单一不确定性因素（主要是需求)，未综合考虑其他的不确定性因素（如车辆、顾客、路况等）的

影响。而在求解VRP问题的过程中，问题的决策，会涉及到人的因素，人对事物认识的模糊性也影响到问题的求解，关于这方面的研宄，也基本处于空白状态。在对算法性能

评估上，也缺乏统一的测试集，因此建立统一的算法评测体系也是十分必要的。而且，在目前的VRP问题研宄中，主要集中于单一目标问题，对多目标的研宄尚显不足。同时，库存、客户点与配货中心选址等多方面的研宄也应当综合到VRP问题中来全局考虑，在这点上，研宄的工作还是有所欠缺的。因此，目前的研宄与实际应用尚有很大的距离，仍有相当长的一段路要走。

1.2立论依据

作为组合优化问题中的一个经典问题，VRP问题吸引了广大学者对它进行研宄。VRP 问题涉及到求多变量的最小值问题，而且约束条件较多。虽然它陈述起来很简单，但实际求解却很困难，它一直被视为运筹学中最富挑战性的问题之一，并且已经被证明是NP 难题。相对于相同城市数的旅行商问题(Traveling salesman problem,简称TSP)，由于条件的约束，它的求解更加复杂。在理论上，枚举法可以解决这一问题，但是当城市数较大时，解题的时间消耗会使枚举法显得没有任何实际价值。寻求一种求解时间短，能满足实际问题精度要求的解，成为解决该问题的主要途径，因此基于人工智能的群集智能（swarm intelligence) 算法来对VRP问题求解逐渐成为了一个研宄热点。

研宄群居性昆虫行为特征的科学家发现，昆虫在群落一级上的合作基本上是自组织的，在许多场合中尽管这些合作可能很简单，但是它们却可以解决复杂的问题。这种由群居性生物产生出来的一种集体行为，即产生的群集智能引起了包括计算机科学家在内的众多研宄人员的兴趣。群集智能指的是一种由众多无智能的简单个体组成的群体，通过相互之间的简单合作所表现出来的智能行为。对群集智能的研宄使我们对于有着复杂结构问题的推测有了科学的依据。群集智能以一个简单的视角来研宄适应性的行为，分析并解决问题，它强调世界的社会性以及工程科学的严格性。

由Dorigo等提出的蚂蚁算法（Ant algorithms)是一种源于大自然生物界的新型仿生类算法，是利用群集智能解决优化组合问题的典型例子。它是受昆虫

______________________ 中南民族大学硕士学位论文 _____________________ 王国中蚂蚁的行为特性的启发,依照蚂蚁觅食原理即蚂蚁寻找从蚁巢到食物的最短路径时的搜索机制设计而成的一种智能算法，也是一种启发式随机型搜索算法。蚂蚁算法以其简单通用、自调节能力强、鲁棒性强、适于并行处理以及应用范围广、易于扩展等特

性，非常适合于求解VRP问题。当今许多研宄者对蚂蚁算法的改进使算法更加有效。Do 「igo等人提出了 Ant-Q算法N，充分利用学习机制，强化最优信息的反馈，降低了当蚁群规模较大时的搜索时间，同时防止了信息素的无穷积累，提高了系统搜索更好的可行解的能力。Dorigo和Gambardel la还提出了 ACS算法' 其无论在搜索时间和解的质量上都取得了很好的效果。Thomas等研宄者提出了最大-最小蚂蚁系统（Max-Min Ant System, MMAS)算法m，该算法有效解决了由于某条路径信息素浓度过大，而导致全部蚂蚁都集中到此条路径上，使蚂蚁放弃了对新的可行解的搜索而过早地收敛于非全局最优解的问题。这些方法对加快算法的搜索速度，降低搜索时间，提高解的质量都有积极的意义，但是还不能完全解决当群体规模较大时搜索解的时间太长以及不一定能收敛于全局最优解的问题。

蚂蚁算法提出至今也就十多年时间，在国内的研宄应用更落后于国外，国内应用蚂蚁算法解决各类问题的资料文献也不是很多，著作就更加少。这在一方面也增加了研宄者运用蚂蚁算法去解决实际问题的难度。查阅中国期刊全文数据库，94年至今关于蚂蚁算法的文章大致有400来篇，其中大多数都是关于算法的函数优化或者蚂蚁算法在TSP 问题上的研宄应用。而关于VRP问题用蚂蚁算法来求解的资料更是少之又少，检索数据库只有不到20篇文章，在这其中绝大多数论文都是近两三年发表的。可以看出采用蚂蚁算法研宄VRP问题，在国内属于刚刚起步的阶段。因此，采用蚂蚁算法的思想来求解VRP问题，在国内是一个比较前沿的研宄领域，也富有挑战性。

1.3本文所做工作

本文分析了蚂蚁算法的基本原理，介绍了它的应用领域，同时对VRP问题的应用价值及其研宄现状作了分析，根据蚂蚁算法及VRP问题的特点，在前人研宄成果的基础上，对传统方法进行了改进，设计出一个比较好的改进算法来提高蚂

蚁算法求解VRP问题的速度和解的质量，并通过仿真实验验证算法的可行性及有效性。本文共分六章，具体安排如下：

第1章绪论。介绍了论文研宄的背景及意义，对VRP问题的起源、发展、研宄工作、应用价值以及研宄现状进行了综述，阐明了选题的理由及本文的主要工作。

第2章蚂蚁算法。介绍了蚂蚁算法的基本原理、应用范围、研宄现状以及发展；分析了蚂蚁算法的特点和它的理论基础；讨论了基本蚂蚁算法、蚂蚁算法的优化方法以及

关键技术。

第3章车辆路径问题。描述了 VRP问题的数学模型，分析了 VRP问题所包含的各类约束条件，总结了求解VRP问题的几种方法及特点。

第4章基于蚂蚁算法的VRP问题求解。分析了运用蚂蚁算法求解VRP问题的实现方法，设计并实现了基于蚂蚁算法的优化算法，并对算法中参数的设置进行了较深入的研宄。

第5章数值实验及结果分析。设计了相关的实验，通过实验的结果与其他文献上的实验结果进行分析比较，证实该算法能达到较好的效果。

第6章结论与展望。总结了全文的主要工作，讨论了下一步研宄的有关内容。

第2章蚂蚁算法

蚂蚁算法是一种源于大自然生物界的新型仿生类算法，它于20世纪90年代初由意大利学者Dorigo、Maniezzo首先提出。作为通用型随机优化算法，它吸收了昆虫王国中蚂蚁的行为特征，通过其内在的搜索机制，已在一系列的优化组合问题求解中取得了成效[8]。自从蚂蚁算法在著名的旅行商问题上取得了成效以来，已陆续渗透到其他问题的求解上蚂蚁算法的正反馈性和协同性使其可以用于分布式系统，隐含的并行性更使之具有极强的发展潜力本章首先对蚂蚁算法的原理、主要特点以及发展和应用作简要的概述，并由此引入蚂蚁算法的相关理论基础，然后介绍蚂蚁算法的基本数学模型，最后讨论蚂蚁算法的关键技术。

2.1蚂蚁算法概述

2.1.1蚂蚁算法产生

一群蚂蚁往某处觅食，虽然它们个体向随机的方向运动，所选择的路径也不一定相同，但是作为一个整体它们仍然是朝一个目的地运动的。它们之间通过相互协调、分工、合作来完成觅食。蚂蚁算法是一种源于大自然生物世界的新型仿生类算法。当人们观察蚂蚁觅食或者搬家的时候，会发现基本上蚂蚁都是沿着一条路线一个挨一个的运动，而这条路线往往又是起点与终点之间最理想的路线。受昆虫王国中蚂蚁的行为特征的启发，依照蚂蚁觅食原理，即蚂蚁寻找从蚁巢到食物的最短路径时的搜索机制，意大利科学家Do「igo、Maniezzo等人在20世纪 90年代初设计并提出了这种仿生类智能算法——蚂蚁算法。

2.1.2蚂蚁算法原理

通过研宄蚂蚁的运动，研宄者发现蚂蚁会在所经过的路径上留下一种挥发性分泌物(phe「omone ,以下称为信息素），信息素随着时间的推移会逐渐挥发消失。蚂蚁在运动过程中能够感知这种物质的存在及其强度，并以此来指导自己的运动

图2.1蚂蚁系统路径寻优过程

在“蚂蚁觅食”的过程中，每只蚂蚁的行动是随机、并行进行的。开始的时

方向，其倾向于朝着这种物质强度高的方向移动，即选择该路径的概率与当时这条 路径上该物质的强度成正比。信息素强度越高的路径,选择它的蚂蚁就越多，则在 该路径上留下的信息素的强度就更大,而强度大的信息素又吸引更多的蚂蚁,从而 形成一种正反馈。通过这种正反馈,蚂蚁最终可以发现最佳路径，最终大部分的蚂 蚁都会走此路径。这就是蚂蚁算法的原理。

下面以图为例来说明蚂蚁系统的工作原理。设A 是巢穴，E 是食物源(反 之亦然）,从A 到E 的往返路径上都存在着觅食的蚂蚁，如图2.1(a)所示。然而, 从某一时刻开始路径AE 上出现了一障碍物HC ,使得单一的AE 路径分解成两条长 短不等的路径ACE 和AHE ,如图2.1(b)中所示。此时,处在B 点和D 点的蚂蚁必须 对前进的方向进行选择,而影响蚂蚁选择的因素则为路径上的信息素浓度,信息素 浓度越高的路径,蚂蚁选择它的概率就越大。在初始时刻，由于路径BHD 和BCD 上 均无信息存在,位于B 和D 的蚂蚁可以随机选择路径。从统计的角度可以认为它们 以相同的概率选择BHD 和BCD 。由于路径BCD 比BHD 短,选择BCD 的蚂蚁将比选择 BHD 的蚂蚁更早到达D 点,此时路径BCD 上的信息素浓度要大于BHD,这将影响由D 到B 以及返回的蚂蚁的选择,它们会以较大的概率选择BCD 。这样随着时间的推移, 蚂蚁将会以越来越大的概率选择路径BCD,以至于最终完全选择路径BCD 。从而找 到由蚁巢到食物源的最短路径,如图2.1(c)所示。

_____________________ 中南民族大学硕士学位论文_____________________ 候，各个蚂蚁的搬运是无序的，但经过一段时间以后，由于各个个体之间的通讯，便逐渐形成了有序的搬运、堆放这样一种群体活动。路径的选择是由信息素的浓度决定的，并倾向于朝信息素浓度高的方向移动，而信息素的浓度关键在于单位时间通过的蚂蚁数量。假设A、B之间有两条路径a、b，路径a的距离比b短，蚁群由B至A再返回B。在通常情况下，经过一段时间后，会有较多的蚂蚁选择a。但是假如b比a的“路况”要好，一段时间后，选择b比选择a来回的时间要短（比如a 路径发生了堵塞），这样蚂蚁留下的信息素会随着时间的流逝而“挥发”，b的信息素浓度反而比a大，一段时间后，选择b路径的蚂蚁反而会比a路径多。

2.1.3蚂蚁算法策略及特点

通过对蚂蚁算法的研宄，可以发现蚂蚁算法中存在着几个重要的策略[12]:

①选择策略：信息素浓度与路径被选择的概率成正比，蚂蚁倾向选择向信息素浓度

高的路径转移。

②更新策略：路径上的信息素浓度与蚂蚁的经过量成正比,与经过的时间成反比。

每条路径上的信息素浓度都是动态变化的。

③协同策略：蚂蚁之间的互相通讯、协同工作实际上是由信息素的浓度来决定。个

体的信息素都会对路径上的整体信息素变化起到作用，而路径整体的信息素变

化又影响个体蚂蚁的路径选择。

正是以上三种策略，使得蚂蚁算法在初始解的基础上经过一段时间后能够发现其中的最优解。同时，使得蚂蚁算法具有以下几个方面的特点：

①简单性：系统中单个个体的能力比较简单，每个个体的执行时间比较短，实现起

来比较方便。

②自调节性：单个个体具有改变环境的能力，能对系统进行调节。

③鲁棒性：无中心控制或数据源，不会由于某一个或者某几个个体的故障而影响整

个问题的求解。

④分布性：群体中相互合作的个体是独立的、并行的、分布的。

⑤可扩展性：各个个体通过对环境的感知进行合作，个体的增加或减少对系统通信

的影响非常小，具有更好的可扩展性。

2.1.4蚂蚁算法的发展及应用

蚂蚁算法诞生于1991年，是一类新颖而前沿的问题求解算法，是利用群集智能解决组合优化问题的典型例子[13]。最初由Do「igo等人提出蚂蚁系统（Ant system，简称AS)的概念，这就是蚂蚁算法模型的雏形。之后，在算法理论问题、数学模型改进与算法应用研宄领域，这类算法很快就得到了国内外学者们的关注。在国外，学者们提出了不同版本的蚂蚁算法，进一步地提高了算法的性能。

当蚂蚁群体规模较大时,要找出一条较好的路径需较长的搜索时间，Dorigo等人在基本的蚂蚁算法的基础上提出了称之为Ant-Q的蚂蚁算法，是结合蚂蚁系统 (Ant System，简称AS )和Q学习机制的耦合算法[14]。每次让信息量最大的路径以较大的概率被选中，以充分利用学习机制,强化最优信息的反馈。Ant-Q算法采用行为选择机制,用来指引蚂

蚁的初始寻优。

蚁群算法（Ant Colony System，简称ACS)是由Dorigo和Gambardel la等人基于Ant-Q算法的基础上提出的一种改进的蚁群算法?，它继承了Ant-Q算法优点并对基本AS模型做出了几点重要改进。它要求蚂蚁在寻优过程中只能采用局部信息对信息素浓度进行调整；在所有的寻优结束后，信息素浓度再一次进行调整，而这次采用全局信息，只对过程中发现的最佳路径上的信息素浓度进行加强它主要在下面三点作了改进：一是状态转移规则为更好更合理地利用新路径和利用关于问题的先验知识提供了方法；二是全局更新规则只应用于最优的蚂蚁路径上；三是在建立问题解决方案的过程中，采用局部信息素更新规则。

之后Thomas等研宄者提出了最大-最小蚂蚁系统（Max-Min Ant System，MMAS) 算法，该系统模型保证只有产生最好结果的路径上才允许信息素得到更新。同时，对每条路径上的信息素浓度加以限制,设置最大、最小信息素浓度值以有效的避免在搜索中算法过早的收敛于局部最优的解，也避免了某条路径上的信息素浓度过分的大于其他路径以至于所有蚂蚁全部集中到这条路径上来，而放弃了对新的可行解的搜索。同时,在循环开始时通过根据需要来设置初始信息素浓度，使蚂蚁更高效地探索更多的可行解。MAX-MIN蚁群系统是一个易于扩展的模型,可以添加局部优化算法来提高蚁群系统的精度并加快收敛的速度。

______________________ 中南民族大学硕士学位论文 _____________________ 在此之后又有许多研宄者根据蚂蚁算法的思想，针对现时算法模型在面对具体问题的局限性，提出了很多改进的算法模型，来优化算法能力和提高算法的效率。同时，他们也把蚂蚁算法应用到众多复杂的经典理论问题中。最先，Dorigo 将蚁群算法应用在TSP 问题求解中，之后又应用该算法求解了分配问题，车间调度问题（Job-Shop problem,简称JSP)，均取得了较好的效果。受其影响蚂蚁算法逐渐引起了其他研宄者的注意，将蚂蚁算法的思想应用到各自研宄领域以及其他组合优化问题（比如车辆路径规划、二次指派、工序调度、背包问题、群组规划等等)，取得了大量的研宄成果。在某些具体问题中，蚂蚁算法的性能更是达到乃至超越了用于该问题的其它经典的求解算法。

在工业社会的实际应用领域，蚂蚁算法的成功正引起了国际上众多企业的关注。Eu 「o Bios公司首先把蚂蚁算法应用于求解现实世界中不同类型的调度问题。同时，Ant Optima公司以蚂蚁算法为工具，成功地开发出多种工业优化的软件工具，例如DYVOIL 产品成功地解决了瑞士某企业的车辆燃油分配管理问题;ANTR0UTE 产品则解决了一些大型连锁超市集团企业的运输车辆调度与路由问题。此外，国外的企业还把蚂蚁算法应用于大型制造商生产线的设计、网络路由与负载平衡的规划、水利设施的建设、数据挖掘、金融现金流的分析与预测等广泛的实际应用领域。

国内在最近几年也掀起了一股研宄蚂蚁算法的热潮，与蚂蚁算法相关的学术著作也相继推出，算法的应用领域得到了不断的拓广，算法的性能也得到了不断的提高。然而总体上来讲，蚂蚁算法在国内的研宄尚刚刚起步，在工业企业中的应用尚未成熟，大量的理论研宄与实际应用工作还处于摸索与探讨阶段。

2.2蚂蚁算法理论基础

蚂蚁算法作为优化的方法之一，属于人工群集智能领域。人工群集智能，大都受自然群集智能如昆虫群和动物群等的启发而来。除了具有独特的强有力的合作搜索能力外，还可以利用一系列的计算代理对问题进行分布式处理，从而大大提高搜索效率。

在蚂蚁算法中，提出了人工蚂蚁（Artificial Ants)的概念，它的设计原理

和动物世界的蚂蚁是一种模仿的关系。人工蚂蚁绝大部分的行为特征都源于真实蚂蚁，它们具有的共同特征主要表现如下[17]:

1.个体的合作性

人工蚂蚁和真实蚂蚁一样，是一群相互合作的个体。这些个体可以通过相互的协作

在全局范围内找出问题较优的解决方案。每只人工蚂蚁都能够建立一个解决方案，但高质量的解决方案是整个蚁群合作的结果。

2.任务的共同性

人工蚂蚁和真实蚂蚁有着共同的任务，那就是寻找连接起点（蚁穴）和终点 (食物源）的最短路径（最小代价）。真实蚂蚁不能跳跃，它们只能沿着相邻区域的状态行进，人工蚂蚁也一样，只能一步一步地沿着问题的邻近状态移动。

3.通过使用信息素进行间接通讯

人工蚂蚁能够在全局范围释放信息素，这些信息素被局部地存于它们所经过的问题状态中。与真实蚂蚁的间接通讯相似，人工蚂蚁之间的通讯也有两个主要特征：

(1)模仿真实蚂蚁信息素的释放。通过给问题状态分配合适的状态变量来模仿真实蚂蚁信息素的释放。

(2)状态变量只能被人工蚂蚁局部到达。在人工蚂蚁群中，人工信息素轨迹是一种分布式的数值信息。只有经过信息素轨迹的人工蚂蚁使用相应的状态变量来表明它感受到了信息素，相反，没有经过该轨迹就不能够感受到相应的信息素。蚂蚁通过修改这些信息来反映它们在解决一个具体问题时所积累的经验。在蚂蚁算法中，局部的人工信息素轨迹是人工蚂蚁进行通讯的唯一渠道。

4.自催化机制——正反馈

当一些路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，使得信息素强度增大。根据蚂蚁倾向于选择信息素强度大的路径的特点，后来的蚂蚁选择该路径的概率也越高，从而增加了该路径的信息素强度，这种选择过程是一种正反馈机制。这种正反馈机制利用信息素浓度作为反馈，通过对系统演化过程中较优解的自增强作用，使得问题的解向着全局最优的方向不断进化，最终能够有效地获得相对较优的解。正反馈在基于群体的优化算法中是一个强有力的机制。但在使用正反馈时，要注意避免早熟收敛（premature convergence).

5.信息素的挥发机制

在蚂蚁算法中存在着一种挥发机制，类似与真实信息素的挥发。这种机制可以使蚂蚁逐渐忘记过去，不受过去经验的过分约束，这有利于指引蚂蚁向着新的方向进行搜索，避免早熟收敛。

6.不预测未来状态概率的状态转移策略

人工蚂蚁和真实蚂蚁一样，应用概率的决策机制沿着邻近状态移动，从而建立问题的解决方案。人工蚂蚁的策略只是充分利用了局部信息，而并没有利用前瞻性来预测未来的状态。因此，所应用的策略在时间和空间上是完全局部的。这个策略既是一个由问题状态所标示的信息函数，又是一个由过去的蚂蚁引起的环境局部改变的函数。

综上所述，作为分布式智能体（Distribute Agent)的人工蚂蚁的行为可以作如下描述：一群人工蚂蚁相互协作在问题的解空间中搜索好的解。这些人工蚂蚁按照人工信息素踪迹（Artificial Pheromone Trails)和基于问题的启发式信

息的指引在问题空间移动以构造问题的解。在此，相对自然界蚂蚁分泌的信息素，人工蚂蚁群设置了一种长期记忆，但这种记忆不是局部的存在于单个的人工蚂蚁，而是全局地分布在整个问题空间。当人工蚂蚁在问题空间中移动时，它们在其经过的路径上留下信息素踪迹，当然，留下信息素的多少与此次爬行（构造解的过程）所构造的解的质量密切相关。这些踪迹反映了人工蚂蚁在问题空间遍历（即构造问题的解）过程中的经历。各个搜寻问题解的人工蚂蚁恰恰是利用这些低水平的信息素的简单交流，从而一步步向问题的最优解靠拢。换句话说，信息素在蚁群的协作和通讯中起到一种间接媒介的作用，研宄社会性生物种群的学者称这种媒介为协同机制（Stigmergy)。人工蚂蚁在解空间中一步一步地移动从而构造问题的解，同时，他们根据解的质量在其路径上留下相应浓度的信息素，蚁群中的其他蚂蚁倾向于沿着信息素浓的路径前进，同样这些蚂蚁也将在这段路径上留下自己的信息素，这就形成了一种自催化强化学习机制，也就是正反馈。这种正反馈机制将指引蚁群找到高质量的问题解，在此意义上，蚂蚁算法是一种强化学习算法。

除了转移策略、更新策略和协同策略，蚂蚁算法还包括另外两个机制：信息素挥发和后台行为。路径上的信息素随着时间不断挥发将驱使人工蚂蚁探索解空间中新的领域从而避免求解过程过早地收敛于局部最优解。后台行为包括邻域（局部）搜索过程以及问题全局信息的收集。蚂蚁算法是一种基于种群的构造型自然启发式优化方法，这种构造型方法如果与改进型迭代方法相结合，例如邻域搜索，其效果会更好。此外，通过在解构造过程中动态的收集基于问题本身的这种启发式全局信息，将引导蚁群在高质量的问题空间中搜索。

但同时，人工蚂蚁又具有一些真实蚂蚁所不具备的行为特征，主要表现在以下几点?:

1.人工蚂蚁生活在离散的世界中，它们的移动实质上是由一个离散状态到另一个离散状态的跃迀。

2.人工蚂蚁拥有一个内部的状态，这个私有的状态记忆了蚂蚁过去的行为。

3.人工蚂蚁释放一定量的信息素，它是蚂蚁所建立的问题解决方案优劣程度的函数。

4.人工蚂蚁释放信息素的时间可以视情况而定，而真实蚂蚁是在移动的同时释放信息素。人工蚂蚁可以在建立了一个可行的解决方案之后再进行信息素的更新。

5.为了提高系统的总体性能，蚁群被赋予了很多其他的本领，如局部优化、原路返回等等，这些本领在真实蚂蚁中是找不到的。在许多应用中，蚂蚁算法中加入了局部更新规则。

2.3蚂蚁算法模型

自蚂蚁算法提出以来，出现了多种不同的具体搜索方法，如：AS、Ant-Q、ACS、MMAS 等等。尽管具体实现过程略有差异，但一般而言，蚂蚁算法都遵循如下的统一框架模型[19]:

procedure组合优化问题的蚂蚁算法

设置参数，初始化信息素踪迹；

whi le(不满足结束条件时)do;

_____________________ 中南民族大学硕士学位论文_____________________ for蚁群中的每个蚂蚁；

fo「每个解构造步骤，（直到构造出完整解）；

蚂蚁按信息素及启发式信息的指引构造一步问题的解；

进行信息素局部更新；（可选） end

end

以某些已获得的解为起点进行邻域（局部）搜索；（可选）

根据某些已获得的解的质量进行全局信息素更新；