蚁群算法在车辆路径优化中的应用毕业论文.doc

本科毕业生设计（论文）蚁群算法在车辆路径优化中的应用毕业论文目录摘 要2ABSTRACT3第1章 绪论61.1 研究目的和意义61.2 国内外研究现状71.2.1 国外研究现状71.2.2 国内研究现状81.3 本文研究内容9（1） 基本蚁群算法9（2） 蚁群算法的优化9（3） 蚁群算法在TSP问题中的应用91.4 开发环境与工具91.5 论文的组织结构10第2章蚁群算法102.1 蚁群算法简介102.2 蚁群算法的原理112.2.1 蚂蚁觅食规则122.2.2 蚂蚁移动规则122.2.3 蚂蚁避障规则122.2.4 蚂蚁撒信息素规则122.3 蚁群算法的特点及优缺点132.3.1 蚁群算法的特点132.3.2 蚁群算法的优点142.3.3 蚁群算法的缺点142.5 蚁群算法的核心函数15（1）初始化15（2）选择下一个城市，返回城市编号15（3）更新环境信息素17（4）检查终止条件18（5）输出最优值182.6 蚁群算法的参数分析192.6.1 蚂蚁数量N_ANT_COUNT192.6.2 启发因子192.6.3 期望启发因子202.6.4 信息素挥发度202.6.5 总信息量（DBQ）21第3章改进的蚁群算法213.1 轮盘赌选择223.1.1 轮盘赌选择基本思想223.1.2 轮盘赌选择工作过程223.2 MAX_MIN ACO243.2.1 MAX_MIN算法的框架结构243.2.2 MAX_MIN 算法流程图26第4章蚁群算法在车辆路径问题中的应用284.1 车辆路径问题简介284.1.1 车辆路径问题定义284.1.2 车辆路径问题分类294.2 车辆路径问题的求解算法294.2.1 精确算法294.2.2 启发式算法304.3 蚁群算法解决车辆路径问题314.4 数值实验结果及分析334.4.1 轮盘赌选择优化前后数据对比334.4.2 MAX_MIN算法改进前后数据对比34第5章总结与展望36参考文献36第1章 绪论 TSP问题是一种特殊的车辆路径问题，是作为所有组合优化问题的范例而存在的，它已成为并将继续成为测试组合优化新算法的标准问题。传统解法对小搜索空间的TSP问题适用，而且有的算法获得精确解的性质也正是人们所期望的。于是，许多求TSP问题近似解的新算法应运而生，启发式算法便是其中之一。而蚁群算法（AC）是由意大利学者Macro Dorigo等人在20世纪90年代提出来的1，它是继模拟退火算法、遗传算法、禁忌搜索算法、人工神经网络算法等之后的一种新型的启发式算法，已成功地应用于求解TSP问题。蚁群算法在解决TSP问题时具有许多优良性质，但也存在着两个主要的缺陷：收敛速度较慢，并且容易出现停滞。为此，不少研究者提出了一些优化策略及改进，如：蚁群系统算法ACS（也称蚁群优化算法ACO）、最大最小蚁群系统算法MMAS等；这些改进在一定程度上提高了算法的有效性，但效果并不明显。如何进一步地对算法进行优化，即优化策略的研究，也正是当前蚁群算法研究的最大的热点。另外，人们也注意到：改进后的蚁群算法在解决大型的TSP问题时，关键参数的设置和信息素的更新将花费很长的时间。而由于蚁群算法中蚂蚁的个体行为具有内在的并行性，因此可以考虑将算法进行分布式并行处理来缩短算法的运行时间。如何进行并行处理，亦即并行策略的研究，是目前蚁群算法研究的又一个热点。1.1 研究目的和意义物流是供应链中最重要的组成部分，是商品从生产者经过各流通环节最终到达消费者手中的过程。物流业这是专门从事物流活动的行业，从企业销售成本和商品价格组成角度考察，物流业蕴藏着巨大的商机。物流业被誉为经济发展动脉的“加速器”和商业结果演变的“润滑剂”，现代企业的“第三利润源泉”。通过提高物流管理水平和效率，降低物流成本，可以为企业及社会带来可观的经济效益，改善国民经济运行效率，提高国际竞争力。因此，国家和各地政府纷纷定制了各种有利于物流发展的政策和计划。在国家“十一五规划”中讲“大力发展现代物流”作为今后重点发展的领域，明确提出“十一五”结束即2010年，全社会物流成本要比2004年的计策上下降23个百分点。合理使用优化运输路线，降低企业物流成本，是物流管理的很重要内容。针对物流管理中对运输车辆路径优化调配的要求，1959年由Dantzig和Ramser首先提出了车辆路径问题的数学模型。车辆路径问题已经是近几十年来运筹学、应用数学、网络分析、计算机应用及交通运输等学科研究一个热点问题，并且在通讯、身长、国防、生物计算机应用等领域得到了广泛的应用。1.2 国内外研究现状车辆路径问题的研究有着现实的经济意义和学术意义。自从VRP被Dantzig和Ramser于1959年提出之后，很快就引起了运筹学、应用数学、物流科学、计算机科学等各个学科专家学者与运输计划制定者和管理者的极大重视，成为运筹学与组合优化领域的前沿问题和研究热点。许多学者对该问题进行了大量的理论研究及实验分析，目前己经产生出多种成熟的算法，取得了令人瞩目的成果，为后人的继续研究提供了极高的参考价值。1.2.1 国外研究现状1962年，Balinski等人首先提出VRP的集分割，直接考虑可行解集合，在此基础上进行优化，建立了最简单的VRP模型。1971年，Eilon提出将动态规划法用于固定车辆数的VRP，通过递归方法求解。1974年，Wren Gillett等人提出扫描算法，将该算法应用于车辆调度问题，并和当时其它算法进行了比较，证明该算法所求得的解较优于其它方法。1981年，Christofides等人提出了k度中心树和相关算法，对固定车辆数m的m-TSP进行了进行k度中心树松弛。后来，M.L.Fishe对这种方法做了进一步改进，可求解有134个客户的VRP。1991年，Gendreau等人将禁忌搜索方法应用于VRP，它是比较好的启发式算法，可以成功地应用于许多经典的VRP。1996年，J.Lawrence将遗传算法用于VRP的研究，有效的求解出带时间窗限制的VRP。1.2.2 国内研究现状在我国，有关车辆路径问题的研究是在20世纪90年代以后才逐渐兴起的，比国外相对落后。随着顾客需求的变化，运输车辆的调度显得日益重要。近年来，我国理论界逐渐开始关注车辆路径问题的研究，并已取得初步成果。蚁群算法、启发式算法以及一些混合算法被学者们广泛的利用，代表了较近的研究思想。启发式算法作为一种逐次逼近的算法，虽然不一定得到最优解，但是可以高效率地得到具有较高精度的解，而且也易于考虑各种实际问题，因此，现已成为解决VRP问题的重要方法。与传统的启发式算法相比，近年来所采用的一些新的启发式算法，通过对启发式规则和搜索方式的改进，在求解多节点、多约束的VRP问题上可以获得较快的收敛速度和较高质量的全局解。浙江大学蔡延光等人运用模拟退火算法和遗传算法求解多重车辆调度问题，并将其集成为智能算法库，作为设计智能运输调度系统的依据。鞍山钢铁学院李大卫和东北大学姜大力等分别针对有时间窗和无时间窗约束下的车辆路径问题用基因编码遗传算法求解，结果在较快速度下得到了近优解。崔雪丽、马良和范炳全等人基于近年来出现的新型智能优化思想：人工蚂蚁系统给出了一种可快速求解VRP的蚂蚁搜索算法。通过定义基本的人工蚂蚁状态转移概，并结合局部搜索策略，用迭代次数控制算法的运行时间，从而使该方法具有使用意义和可操作性。经一系列数据测试和验证，与若干已有的经典算法相比较，获得了较好的结果。杨善林人等提出一种基于蚁群优化的混合算法来解决VRP。首先提出一种ACO 算子，然后加入局部搜索机制并使用基于问题的特定启发信息节约量来改进算法。尹小峰等针对了蚁群算法存在的过早收敛问题引入节省量以及车辆载重利用率两种启发式信息对蚁群算法加以改进，并加入2.opt方法对问题求解进行局部优化，计算机仿真结果表明，这种混合蚁群算法对求解车辆路径问题有较好的改进效果。1.3 本文研究内容本文的研究内容可以概括为三部分：蚁群算法的基础性理论、蚁群算法的优化以及蚁群算法在TSP问题中的应用：（1） 基本蚁群算法了解基本蚁群算法的概念、原理以及代码如何实现。（2） 蚁群算法的优化根据蚁群算法的基本原理做出优化，避免蚁群算法的缺点，在迭代次数尽量少，迭代结果尽量趋近最优解的情况下做出优化。本文主要讲解轮盘算法和max_min算法在蚁群算法中的优化。（3） 蚁群算法在TSP问题中的应用利用蚁群算法的特点以及蚁群算法的优化应用到TSP问题中。1.4 开发环境与工具计算机：HP ProBook 4416S系统：Microft Windows XP Professinal 版本2002 Service Pack3内存：2G开发语言：C+运行环境：Microsoft Visual C+ 6.01.5 论文的组织结构第一章 绪论 主要是讲解本课题研究内容、目的和意义，国内外对蚁群算法的研究现状以及本系统开发环境的介绍；第二章 蚁群算法 主要是介绍什么是蚁群算法，蚁群算法的原理和思想以及蚁群算法的优缺点；第三章 改进的蚁群算法 主要是讲解在基本蚁群算法的基础上对蚁群算法做出优化（本文采用了轮盘选择和MAX-MIN两种优化方式）第四章 蚁群算法在车辆路径问题中的应用第五章 总结与展望第2章蚁群算法2.1 蚁群算法简介蚁群算法(ant colony optimization, ACO)，又称蚂蚁算法，是一种用来在图中寻找优化路径的机率型算法。它由Marco Dorigo于1992年在他的博士论文中提出，其灵感来源于蚂蚁在寻找食物过程中发现路径的行为。蚁群算法是一种模拟进化算法，初步的研究表明该算法具有许多优良的性质。针对PID控制器参数优化设计问题，将蚁群算法设计的结果与遗传算法设计的结果进行了比较，数值仿真结果表明，蚁群算法具有一种新的模拟进化优化方法的有效性和应用价值。蚁群算法（Ant Clony Optimization， ACO）是一种群智能算法，它是由一群无智能或有轻微智能的个体（Agent）通过相互协作而表现出智能行为，从而为求解复杂问题提供了一个新的可能性。蚁群算法是一种仿生学算法，是由自然界中蚂蚁觅食的行为而启发的。在自然界中，蚂蚁觅食过程中，蚁群总能够按照寻找到一条从蚁巢和食物源的最优路径。图（1）显示了这样一个觅食的过程。图（1）蚂蚁觅食在图1（a）中，有一群蚂蚁，假如A是蚁巢，E是食物源（反之亦然）。这群蚂蚁将沿着蚁巢和食物源之间的直线路径行驶。假如在A和E之间突然出现了一个障 碍物（图1（b），那么，在B点（或D点）的蚂蚁将要做出决策，到底是向左行驶还是向右行驶？由于一开始路上没有前面蚂蚁留下的信息素 （pheromone），蚂蚁朝着两个方向行进的概率是相等的。但是当有蚂蚁走过时，它将会在它行进的路上释放出信息素，并且这种信息素会议一定的速率散 发掉。信息素是蚂蚁之间交流的工具之一。它后面的蚂蚁通过路上信息素的浓度，做出决策，往左还是往右。很明显，沿着短边的的路径上信息素将会越来越浓（图 1（c），从而吸引了越来越多的蚂蚁沿着这条路径行驶。2.2 蚁群算法的原理设想，如果我们要为蚂蚁设计一个人工智能的程序，那么这个程序要多么复杂呢？首先，你要让蚂蚁能够避开障碍物，就必 须根据适当的地形给它编进指令让他们能够巧妙的避开障碍物，其次，要让蚂蚁找到食物，就需要让他们遍历空间上的所有点；再次，如果要让蚂蚁找到最短的路 径，那么需要计算所有可能的路径并且比较它们的大小，而且更重要的是，你要小心翼翼的编程，因为程序的错误也许会让你前功尽弃。这是多么不可思议的程序！ 太复杂了，恐怕没人能够完成这样繁琐冗余的程序。然而，事实并没有你想得那么复杂，上面这个程序每个蚂蚁的核心程序编码不过100多行！为什么这么简单的程序会让蚂 蚁干这样复杂的事情？答案是：简单规则的涌现。事实上，每只蚂蚁并不是像我们想象的需要知道整个世界的信息，他们其实只关心很小范围内的眼前信息，而且根 据这些局部信息利用几条简单的规则进行决策，这样，在蚁群这个集体里，复杂性的行为就会凸现出来。这就是人工生命、复杂性科学解释的规律！那么，这些简单规则是什么呢？2.2.1 蚂蚁觅食规则在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地 方走，并且每只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。2.2.2 蚂蚁移动规则每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住刚才走过了哪些点，如果发现要走的下一点已经在之前走过了，它就会尽量避开。2.2.3 蚂蚁避障规则如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。2.2.4 蚂蚁撒信息素规则每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。2.3 蚁群算法的特点及优缺点2.3.1 蚁群算法的特点（1）蚁群算法是一种自组织的算法在系统论中，自组织和它组织是组织的两个基本分类，其区别在于组织力或组织指令是来自于系统的内部还是来自于系统的外部，来自于系统内部的是自组织，来自于系统外部的是他组织。如果系统在获得空间的、时间的或者功能结构的过程中，没有外界的特定干预，我们便说系统是自组织的。在抽象意义上讲，自组织就是在没有外界作用下使得系统熵增加的过程(即是系统从无序到有序的变化过程)。蚁群算法充分体现了这个过程，以蚂蚁群体优化为例子说明。当算法开始的初期，单个的人工蚂蚁无序的寻找解，算法经过一段时间的演化，人工蚂蚁间通过信息激素的作 用，自发的越来越趋向于寻找到接近最优解的一些解，这就是一个无序到有序的过程。（2）蚁群算法是一种本质上并行的算法每只蚂蚁搜索的过程彼此独立，仅通过信息激素进行通信。所以蚁群算法则可以看作是一个分布式的多agent系统，它在问题空间的多点同时开始进行独立的解搜索，不仅增加了算法的可靠性，也使得算法具有较强的全局搜索能力。（3）蚁群算法是一种正反馈的算法从真实蚂蚁的觅食过程中我们不难看出，蚂蚁能够最终找到最短路径，直接依赖于最短 路径上信息激素的堆积，而信息激素的堆积却是一个正反馈的过程。对蚁群算法来说，初始时刻在环境中存在完全相同的信息激素，给予系统一个微小扰动，使得各 个边上的轨迹浓度不相同，蚂蚁构造的解就存在了优劣，算法采用的反馈方式是在较优的解经过的路径留下更多的信息激素，而更多的信息激素又吸引了更多的蚂 蚁，这个正反馈的过程使得初始的不同得到不断的扩大，同时又引导整个系统向最优解的方向进化。因此，正反馈是蚂蚁算法的重要特征，它使得算法演化过程得以进行。（4）蚁群算法具有较强的鲁棒性相对于其它算法，蚁群算法对初始路线要求不高，即蚁群算法的求解结果不依赖子初始路线的选择，而且在搜索过程中不需要进行人工的调整。其次，蚁群算法的参数数目少，设置简单，易于蚁群算法应用到其它组合优化问题的求解。2.3.2 蚁群算法的优点蚁群算法的成果运用激起了人们的极大兴趣，并吸引了一批研究人员从事蚁群算法的研究。研究表明，蚁群算法是一种有效的随机搜素算法，具有如下优点：（1）较强的鲁棒性：无中心控制，不会由于某一个或者某几个个体的故障而影响整个问题的求解；（2）本质并行性：蚁群在问题空间的多点不同时开始进行独立的解搜素，增强了算法的全局搜素能力；（3）正反馈性：蚁群算法能够最终找到最短路径，直接依赖于最短路径上的信息素的堆积，而信息素的堆积就是一个正反馈的过程；（4）易于与其他方法结合：蚁群算法很容易与多种启发式算法结合，以改善算法的性能。（5）自组织性：算法初期，单个的人工蚂蚁无序地寻找解，经过一段时间的烟花，蚂蚁间通过信息素的作用，自发地越来越趋向于寻找到接近最优解的一些解，是个从无序到有序的过程；2.3.3 蚁群算法的缺点虽然蚁群算法有许多优点，但同时也存在一些缺陷，如：（1）与其他方法相比，该算法一般需要较长的搜索时间，计算量较大，蚁群算法的复杂度可以反映这一点；（2）该方法容易出现停滞现象（stagnation behaviour），即搜索进行到一定程度后，所有个体所发现的解完全一致，不能对解空间进一步进行搜索，不利于发现更好的解。2.5 蚁群算法的核心函数（1）初始化将所有城市设置为没有去过，清空蚂蚁走过的路径编号（置0），蚂蚁走过长度设置0，并随机选取一个出发点，以及标识改点走过。void CAnt:Init()for (int i=0;iN_CITY_COUNT;i+)m_nAllowedCityi=1; /设置全部城市为没有去过m_nPathi=0; /蚂蚁走的路径全部设置为0/蚂蚁走过的路径长度设置为0m_dbPathLength=0.0; /随机选择一个出发城市m_nCurCityNo=rnd(0,N_CITY_COUNT);/设置出发城市m_nPath0=m_nCurCityNo;/标识出发城市为已经去过了m_nAllowedCitym_nCurCityNo=0; /已经去过的城市数量设置为1m_nMovedCityCount=1; （2）选择下一个城市，返回城市编号int CAnt:ChooseNextCity()int nSelectedCity=-1; /返回结果，先暂时把其设置为-1/计算当前城市和没去过的城市之间的信息素总和double dbTotal=0.0;double probN_CITY_COUNT; / 保存城市被选中的概率for (int i=0;iN_CITY_COUNT;i+)if (m_nAllowedCityi = 1) /城市没去过probi=pow(g_Trialm_nCurCityNoi,ALPHA)*pow(1.0/g_Distancem_nCurCityNoi,BETA); /该城市和当前城市间的信息素dbTotal=dbTotal+probi; /累加信息素，得到总和elseprobi=0.0;/直接选择概率最大的点double temp_max=-1;for(int ii=0;iiN_CITY_COUNT;ii+)if(temp_maxprobii)temp_max=probii;nSelectedCity=ii;if (nSelectedCity = -1)for (int i=0;iN_CITY_COUNT;i+)if (m_nAllowedCityi = 1) /城市没去过nSelectedCity=i;break;/返回结果return nSelectedCity;（3）更新环境信息素/更新环境信息素,基本算法/*void CTsp:UpdateTrial()/临时保存信息素double dbTempAryN_CITY_COUNTN_CITY_COUNT;memset(dbTempAry,0,sizeof(dbTempAry); /先全部设置为0/计算新增加的信息素,保存到临时数组里int m=0;int n=0;for (int i=0;iN_ANT_COUNT;i+) /计算每只蚂蚁留下的信息素for (int j=1;jN_CITY_COUNT;j+)m=m_cAntAryi.m_nPathj;n=m_cAntAryi.m_nPathj-1;dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength;dbTempArymn=dbTempArynm;/最后城市和开始城市之间的信息素n=m_cAntAryi.m_nPath0;dbTempArynm=dbTempArynm+DBQ/m_cAntAryi.m_dbPathLength;dbTempArymn=dbTempArynm;/更新环境信息素for (i=0;iN_CITY_COUNT;i+)for (int j=0;jN_CITY_COUNT;j+)g_Trialij=g_Trialij*ROU+dbTempAryij; /最新的环境信息素 = 留存的信息素 + 新留下的信息素（4）检查终止条件如果达到最大迭代次数，算法终止，输出最终最优解；否则，执行（5），输出当前迭代最优解，重新初始化所有的蚂蚁的路径矩阵所有元素初始化为0，禁忌表表清空，允许表表中加入所有的城市节点。随机选择它们的起始位置（也可以人工指定）。在路径矩阵中加入起始节点，允许表中去掉该起始节点，重复执行（2），（3）,(4)步。（5）输出最优值每次迭代结束，输出当前迭代编号以及本次迭代中最优解蚂蚁的路径长度。2.6 蚁群算法的参数分析 从蚁群算法的模型中可以看出，蚁群算法的参数空间庞大，合适的参数组合能够过有全局收哟能力和较快的瘦脸术的，不合适的参数组合则会使得算法收敛较慢或者达到局部最优解。然而，目前对各参数该如何选择也没有严格的理论依据，只是根据经验和实验来选取合适的参数值。基于此，国内外许多研究人员在蚁群算法的参数分析和优化组合方面做了大量的工作。对、N_ANT_COUNT（N_ANT_COUNT，蚂蚁数量）等参数的选择进行了初步研究；2.6.1 蚂蚁数量N_ANT_COUNT蚂蚁算法是通过多个候选解组成的群体进化过程来搜索最优解，所以蚂蚁的数目N_ANT_COUNT对一群算法有一定的影响。N_ANT_COUNT大，会提高蚁群算法的全局搜索能力和稳定性，但数量过大会导致大量曾被搜索过的路径上的信息素变化趋于平均，信息正反馈作用减弱，随机性增强，收敛速度减慢。反之，N_ANT_COUNT小，会使从来未被搜索到的解上的信息素减小到接近于0，全局搜索的随机性减弱，虽然收敛速度加快，但是会使算法的全局性能降低，稳定性变差，出现过早停滞现象。经大量的仿真试验获得：当N_ANT_COUNT属于【0.6*N_CITY_COUNT,09*N_CITY_COUNT】时（N_CITY_COUNT为城市数量），蚁群算法的全局收敛性和收敛速度都比较好。 2.6.2 启发因子启发银子是表示蚂蚁在运动过程中所积累的信息素在知道蚁群搜索中的相对重要程度，其大小反映了蚂蚁在路径搜索中随机因素作用强弱。越大，蚂蚁选择以前走过的路径可能性就越大，实现自催化过程，但搜索的随机性减弱；越小，易使蚁群算法过早陷入局部最优。而已有研究证明：对于小规模的TSP问题，在蚁群算法的三种模型中=1时，解的质量和稳定性都是最好的。2.6.3 期望启发因子期望启发因子是表示能见度相对重要程度的参数。的大小反映了蚂蚁在路径搜索过程中确定性因素作用的强弱。而已有研究表明：过小，讲导致蚂蚁群体陷入纯粹的随机搜索，在此情况下很难找到最优解；过大，蚂蚁在局部点上选择局部最短路径的可能性越大，虽然加快了收敛速度，但减弱了随机性，易陷入局部最优。对于TSP问题，不同城市规模，的具体取值各有不同。一般【2,5,8】时，算法的综合性比较好。2.6.4 信息素挥发度在蚁群算法中，人工蚂蚁是具有人类记忆功能的，随着时间的推移，以前留下的信息将要逐渐消失。如前所述，在算法模型中，参数表示信息素挥发度，其大小直接关系到蚁群算法的全局搜索能力及其收敛速度；1-信息素残留印子，反映了蚂蚁个体之间相互影响的强弱。研究表明：在其它参数相同的情况下，信息素挥发度的大小对一群算法的收敛性影响非常大，与循环次数近似成反比关系。当极小时，路径上残留信息占主导地位，信息正反馈作用相对较弱，手术的随机性增强，因而蚁群算法的收敛速度很慢。若较大时，正反馈作用占主导地位，搜素的随机性减弱，导致收敛速度快，但易陷入局部最优状态。对于TSP问题，不同的问题规模，的曲子也不尽相同。一般来说，【0.1,0.5】时，性能的算法较好。2.6.5 总信息量（DBQ）总信息量DBQ为蚂蚁循环一周时释放在所经路径上的信息素总量，在基本一群算法中他是一个产量。一般的理解是：总信息量DBQ越大，则在蚂蚁已经走过的路径上信息素的累积越快，可以加强蚁群搜素时的正反馈性能，有助于算法的快速收敛。DBQ过小，则信息素浓度增长太慢，正反馈信息太少，使算法难以收敛。研究表明：在蚁周模型中，由于TSP的规模不同，路径长度各不相同，如果读不通的TSP使用相同的DBQ值，则信息素总量更新尺度是不同的，最终修改信息素的程度存在很大不稳定性。DBQ的取值应与说处理的TSP的规模相对应，确保信息素总量更新在可控制范围内。在小规模TSP问题中，DBQ=100是大多数研究学者认为所公认的较好值。第3章改进的蚁群算法（1）采用轮盘赌选择代替了基本框架中通过启发式函数和信息素选择路径，改进蚁群算法的信息素传递参数，让整个算法更快速的找到最优解。（2）最大最小优化主要作了如下改进： A：每次迭代结束后，只有最优解所属路径上的信息被更新，从而更好地利用了历史信息； B：为了避免算法过早收敛于并非全局最优的解，将各条路径可能的外激素浓度限制于【T_min,T_max】,超出这个范围的值被强制设为T_min或者是T_max，可以有效的避免某条路径上的信息量远大于其余路径，使得所有蚂蚁都集中到同一条路径上，从而使算法不再扩散； C：初始时刻，各条路径上外激素的其实浓度设为T_max，在算法的初始时刻，P（0p 0.0) /总的信息素值大于0dbTemp=rnd(0.0,dbTotal); /取一个随机数for (int i=0;iN_CITY_COUNT;i+)if (m_nAllowedCityi = 1) /城市没去过dbTemp=dbTemp-probi; /这个操作相当于转动轮盘if (dbTemp = max,，则设置ij= max；如果ij= min，则设置ij=min；max和min的值可以分别由以下公式得到：max=11-1LSbest其中：LSbest是得到的最优解路径长度。 蚂蚁完成一次搜索，即为一次迭代。设迭代次数为n2时，则由以下公式来计算： min=max1-nPbestavg-1nPbest式中avg =n/2，Pbest=0.5（3）信息素初始值设为max3.2.2 MAX_MIN 算法流程图 MAX_MIN改进算法与基本的蚁群算法的其他地方一致，仅仅是更新信息素的策略不同，以下是MAX_MIN更新信息素的函数流程图：开始寻找当前迭代路径最短的蚂蚁根据公式计算公式，计算MAX值和MIN的值根据公式计算相邻两城市的路径信息素是否超过MAX将信息素上限设为MAX 是 否信息素是否小于MIN将信息素下线设为MIN 是 否依次将任意两城市的信息素加上本次新增的信息素结束第4章蚁群算法在车辆路径问题中的应用4.1 车辆路径问题简介4.1.1 车辆路径问题定义车辆路径问题（VRP）是Dantzig和Ramser于1959年提出的，它是指一定数量的客户，各自有不同数量的货物需求，配送中心向客户提供货物，由一个车队负责分送货物，组织适当的行车路线，目标是使得客户的需求得到满足，并能在一定的约束下，达到诸如路程最短、成本最小、耗费时间最少等目的。 车辆路线问题自1959年提出以来，一直是网络优化问题中最基本的问题之一，由于其应用的广泛性和经济上的重大价值，一直受到国内外学者的广泛关注。车辆路线问题可以描述如下（如图）： 场站VRP示意图设有一场站（depot），共有M 辆货车，车辆容量为Q，有N位顾客（customer），每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站，要求所有顾客都被配送，每位顾客一次配送完成，且不能违反车辆容量的限制，目的是所有车辆路线的总距离最小。车辆路线的实际问题包括配送中心配送、公共汽车路线制定、信件和报纸投递、航空和铁路时间表安排、工业废品收集等。4.1.2 车辆路径问题分类根据研究的重点不同，VRP存在多种分类方式：（a）按一直信息的特征，可分为确定性VRP和不确定性VRP，其中不确定性VRP可进一步分为随机车辆路径问题（SVRP）和模糊车辆路径（PVRP）； （b）按约束条件，可以分为带有容量限制的车辆路径问题（CVRP），带有时间距离约束的车辆路径问题（DVRP）以及带有时间窗的车辆路径问题（VRPTW）；（c）按需求是否可以分割，可以分为可分割的车辆路径问题和不可分割的车辆路径问题；（d）按每个顾客需求量是否超过车的容量来分，可以分为满载车辆路径和非满载车辆路径问题；（e）按配送中心的多少来分可以分为但车场车辆路径问题（SVRP）。即一般车辆路径问题（VRP），以及多车场车辆路径问题（MVRP），其中MVRP又可以根据是否每辆车都有固定的重点车场分为重点车场固定的车辆路径问题和重点车场不固定的开放式车辆路径问题（OVRP）；按优化目标分，又可以分为单目标问题和多目标问题；按路由过程中相关信息是否改变，又可以分为动态VRP和静态VRP。4.2 车辆路径问题的求解算法 由于情况不同，VRP数学模型够早及求解算法也有较大的差别。目前有关VRP模型的研究已经取得了较大的成果。综合过去的相关研究，VRP模型基本可以分为图模型、数学模型和仿真模型。VRP的求解算法非常丰富，基本可以分为紧缺算法和iq法师算法两大类。求解VRP的启发式算法有不同的分类方法。4.2.1 精确算法精确算法指可求出最优解的算法。到目前为止，已提出的精确算法种类较多，有分支定界法、割平面法、整数规划算法和动态规划算法等。另外，还有的认为精确算法指股东认购配股，可认购数量不足1股的部分按照精确算法原则处理。即先按照配售比例和每个账户股数计算出可认购数量 的整数部分；对于计算出不足1股的部分（尾数保留三位小数），将所有账户按照尾数从大到小的顺序进位（尾数相同则随机排序），直至每个账户获得的可配股数 量加总与可配售总量一致。另外关于精确算法原则取整，其实举个例子就明白了： 假设有共有100手债券发行，四个人认购 ：第1人认购25.8手，第2人认购25.6手，第3人认购25.4手，第4人认购25.2手 ，结果是每人25手。 再假设有共有101手债券发行，四个人认购 ：第1人认购25.8手，第2人认购25.6手，第3人认购25.4手，第4人认购25.2手，结果是第1人26手，其他人25手。 再假设有共有103手债券发行，四个人认购 ：第1人认购25.8手，第2人认购25.6手，第3人，认购25.4手 第4人认购25.2手 ，结果是第13人26手，第4人25手。 从这里可以看出，分配原则是先分配整数，如果有剩余按零头的大小分配。实际情况大于0.5手可能能分配到1手，但也可能分不到。4.2.2 启发式算法由于VRP是NP-hard问题，难以用精确算发求解，启发式算法是求解车辆运输问题的主要方法，多年来许多学者对车辆运输问题进行了研究，提出了各种各样的启发式方法。车辆运输问题的启发式方法可以分为简单启发式算法、两阶段启发式算法、人工智能方法建立的启发式方法。 简单启发式方法包括节省法或插入法、 路线内间节点交换法、贪婪法和局部搜索法等方法。节省法或插入法（savings or insertion）是在求解过程中使用节省成本最大的可行方式构造路线，直到无法节省为止。交换法则是依赖其他方法产生一个起始路线，然后以迭代的方式 利用交换改善法减少路线距离，直到不能改善为止。1960年，Clarke和Wright6首先提出一种启发式节省法（savings methods）来建立车队配送路线。简单启发式方法简单易懂、求解速度快，但只适合求解小型、简单的VRP问题。 两阶段方法包括先分组后定路线（clusterfirst-route second）和先定路线后分组（routefirst-cluster second）两种启发式策略。前者是先将所有需求点大略分为几个组，然后再对各个组分别进行路线排序；后者则是先将所有的需求点建构成一条路线，再根据 车辆的容量将这一路线分割成许多适合的单独路线。 1990年以来，人工智能方法在解决组合优化问题上显示出强大功能，在各个领域得到充分应用，很多学者也将人工智能引入车辆路线问题的求解中，并构造了大量的基于人工智能的启发式算法。禁忌搜索法（TS）基本上是属于一种人工智能型（AI）的局部搜寻方法，Willard首先将此算法用来求解VRP ，随后亦有许多位学者也发表了求解VRP的TS 算法。西南交通大学的袁庆达7等设计了考虑时间窗口和不同车辆类型的禁忌算法，这种算法主要采用GENIUS方法产生初始解，然后禁忌算法对初始解优化。模拟退火方法具有收敛速度快，全局搜索的特点，Osman8对VRP的模拟退火算法进行了研究，他提出的模拟退火方法主要适合于解决路线分组。遗传算法具有求解组合优化问题的良好特性，Holland首先采用遗传算法（GA）编码解决VRPTW 问题。现在多数学者采用混合策略，分别采用两种人工智能方法进行路线分组和路线优化。Ombuki9提出了用遗传算法进行路线分组，然后用禁忌搜索方法进行路线优化的混合算法。Bent和Van Hentenryck10则首先用模拟退火算法将车辆路线的数量最小化，然后用大邻域搜索法（largneighborhood search）将运输费用降到最低。 总结几种人工智能方法可以看出，TS算法所得到的解最接近最优解，但其运算时间也最长，是GA算法的23倍，SA算法的近20倍；由 于GA算法也能较好的逼近最优解，同时使运算时间大大缩短，所以GA算法能兼顾运算时间和效率两方面，是具有较好的发展前途的方法；SA算法求解速度非常 快，也能提供一定程度上的优化方案在求解较小规模问题上具有较好效果。4.3 蚁群算法解决车辆路径问题 给定一个有n个城市的TSP问题，人蚂蚁的数量m，每个人工蚂蚁的行为符合下列规律：（1）根据路径上的信息素浓度，以相应的概率来选取下一步路径；（2）不再选取自己本次循环已经走过的路径为下一步路径；（3）当完成了一次循环后，根据整个路径长度来释放相应浓度的信息素，并更新走过的路径上的信息素浓度。实现步骤如下：开始参数初始化对每只蚂蚁按概率移植下一城市，完成一次循环计算各蚂蚁的路径长度，记录当前最优解修改信息素是否迭代结束 否 是输出最优解结束步骤1：初始化相关参数，如蚂蚁的数目，城市的数量，迭代次数，总的信息素等；步骤2：对每只蚂蚁按概率移至下一城市节点，完成第一次循环