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

蚁群算法在车辆路径优化中的应用 毕 业 设 计(论 文)题目:蚁群算法在车辆路径优化中的应用 姓 名夏彬彬 学 号 0910312134 所在学院 湖北工业大学 专业班级 09计职1班 指导教师 宗欣露 日 期 2013 年 5 月 8 日 摘 要 许多实际工程问题可以抽象为相应的组合优化问题,TSP问题是作为所有组合优化问题的范例而存在的,它已成为并将继续成为测试组合优化新算法的标准问题。从理论上讲,使用穷举法可以求解出TSP问题的最优解;但是对现有的计算机来说,让它在如此庞大的搜索空间中寻求最优解,几乎是不可能的。所以,各种求TSP问题近似解的算法应运而生了,本文所描述的蚁群算法(AC)也在其中。 目前已出现了很多的启发式算法,而蚁群算法作为一种新型的启发式算法,已成功地应用于求解TSP问题。蚂蚁通过分泌信息素来加强较好路径上信息素的浓度,同时按照路径上的信息素浓度来选择下一步的路径:好的路径将会被越来越多的蚂蚁选择,因此更多的信息素将会覆盖较好的路径;最终所有的蚂蚁都集中到了好的路径上。蚂蚁的这种基于信息素的正反馈原理正是整个算法的关键所在。 本文介绍了基本蚁群算法概念、原理及蚁群算法的特点,再根据蚁群算法的缺点做出了优化。采用轮盘赌选择代替了基本框架中通过启发式函数和信息素选择路径,改进蚁群算法的信息素传递参数,让整个算法更快速的找到最优解。其次,采用最大最小优化系统限制最大值和最小值,让整个系统更快收敛,得到最优解。 关键字:蚁群算法,TSP问题,启发式函数,轮盘算法,最大最小优化 ABSTRACT Many practical engineering problems can be abstracted as corresponding combinatorial optimization problem, TSP problem is an example of all as a combinatorial optimization problem, it has become and will continue to be a new combinatorial optimization algorithm of standard test problems. In theory, using the exhaustion method can solve the TSP problem optimal solution; But for the existing computer, let it in such a large search space to seek the optimal solution, it is almost impossible. So, all kinds of algorithm arises at the historic moment, the approximate solution of the TSP problem described in this paper, ant colony algorithm AC is among them Has appeared a lot of heuristic algorithm and ant colony algorithm as a kind of new heuristic algorithm, has been successfully used in solving TSP problems. Ant secretion by pheromones to strengthen the good path pheromone concentration, at the same time according to the path to choose the next path pheromone concentration: good paths will be more and more ants to choose, so that more information will cover good path; Eventually all the ants on a good path. This positive feedback based on the pheromone of ant principle is the key to the whole algorithm This paper introduces the basic concept of ant colony algorithm, principle and characteristics of ant colony algorithm, according to the disadvantages of ant colony algorithm optimization. Adopting roulette selection instead of the basic framework by heuristic function and choose path pheromone, pheromone passing parameters of improved ant colony algorithm, make the whole algorithm find the optimal solution more quickly. Second, limiting the imum and the minimum imum minimum optimization system, make the whole system faster convergence and the optimal solution is obtained Keywords: ant colony algorithm, the TSP problem, a heuristic function, roulette algorithm, imum_minimum optimization 目录摘 要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_MIN ACO243.2.1 _MIN算法的框架结构243.2.2 _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 _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年的计策上下降2?3个百分点。 合理使用优化运输路线,降低企业物流成本,是物流管理的很重要内容。针对物流管理中对运输车辆路径优化调配的要求,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度中心树松弛。后来,/.he对这种方法做了进一步改进,可求解有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) 蚁群算法的优化 根据蚁群算法的基本原理做出优化,避免蚁群算法的缺点,在迭代次数尽量少,迭代结果尽量趋近最优解的情况下做出优化。本文主要讲解轮盘算法和_min算法在蚁群算法中的优化。(3) 蚁群算法在TSP问题中的应用 利用蚁群算法的特点以及蚁群算法的优化应用到TSP问题中。1.4 开发环境与工具 计算机:HP ProBook 4416S 系统:Microft Windows XP Professinal 版本2002 Service Pack3 内存:2G 开发语言:C+ 运行环境:Microsoft Visual C+ 6.01.5 论文的组织结构 第一章 绪论 主要是讲解本课题研究内容、目的和意义,国内外对蚁群算法的研究现状以及本系统开发环境的介绍; 第二章 蚁群算法 主要是介绍什么是蚁群算法,蚁群算法的原理和思想以及蚁群算法的优缺点; 第三章 改进的蚁群算法 主要是讲解在基本蚁群算法的基础上对蚁群算法做出优化(本文采用了轮盘选择和-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 i0;iN_CITY_COUNT;i+ m_nAllowedCityi1; /设置全部城市为没有去过 m_nPathi0; /蚂蚁走的路径全部设置为0 /蚂蚁走过的路径长度设置为0 m_dbPathLength0.0; /随机选择一个出发城市 m_nCurCityNornd0,N_CITY_COUNT; /设置出发城市 m_nPath0m_nCurCityNo; /标识出发城市为已经去过了 m_nAllowedCitym_nCurCityNo0; /已经去过的城市数量设置为1 m_nMovedCityCount1; (2)选择下一个城市,返回城市编号 int CAnt:ChooseNextCity int nSelectedCity-1; /返回结果,先暂时把其设置为-1 /计算当前城市和没去过的城市之间的信息素总和 double dbTotal0.0; double probN_CITY_COUNT; / 保存城市被选中的概率 for int i0;iN_CITY_COUNT;i+ if m_nAllowedCityi 1 /城市没去过 probipowg_Trialm_nCurCityNoi,ALPHA*pow1.0/g_Distancem_nCurCityNoi,BETA; /该城市和当前城市间的信息素 dbTotaldbTotal+probi; /累加信息素,得到总和 else probi0.0; /直接选择概率最大的点 double temp_-1; forint ii0;iiN_CITY_COUNT;ii+ iftemp_probii temp_probii; nSelectedCityii; if nSelectedCity -1 for int i0;iN_CITY_COUNT;i+ if m_nAllowedCityi 1 /城市没去过 nSelectedCityi; break; /返回结果 return nSelectedCity; (3)更新环境信息素 /更新环境信息素,基本算法 /* void CTsp:UpdateTrial /临时保存信息素 double dbTempAryN_CITY_COUNTN_CITY_COUNT; memsetdbTempAry,0,sizeofdbTempAry; /先全部设置为0 /计算新增加的信息素,保存到临时数组里 int m0; int n0; for int i0;iN_ANT_COUNT;i+ /计算每只蚂蚁留下的信息素 for int j1;jN_CITY_COUNT;j+ mm_cAntAryi.m_nPathj; nm_cAntAryi.m_nPathj-1; dbTempArynmdbTempArynm+DBQ/m_cAntAryi.m_dbPathLength; dbTempArymndbTempArynm; /最后城市和开始城市之间的信息素 nm_cAntAryi.m_nPath0; dbTempArynmdbTempArynm+DBQ/m_cAntAryi.m_dbPathLength; dbTempArymndbTempArynm; /更新环境信息素 for i0;iN_CITY_COUNT;i+ for int j0;jN_CITY_COUNT;j+ g_Trialijg_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问题中,DBQ100是大多数研究学者认为所公认的较好值。 第3章改进的蚁群算法 (1)采用轮盘赌选择代替了基本框架中通过启发式函数和信息素选择路径,改进蚁群算法的信息素传递参数,让整个算法更快速的找到最优解。 (2)最大最小优化主要作了如下改进: A:每次迭代结束后,只有最优解所属路径上的信息被更新,从而更好地利用了历史信息; B:为了避免算法过早收敛于并非全局最优的解,将各条路径可能的外激素浓度限制于【T_min,T_】,超出这个范围的值被强制设为T_min或者是T_,可以有效的避免某条路径上的信息量远大于其余路径,使得所有蚂蚁都集中到同一条路径上,从而使算法不再扩散; C:初始时刻,各条路径上外激素的其实浓度设为T_,在算法的初始时刻,P(0p1,信息素政法系数)取较小值时,算法有更好的发现较好解的能力。所有蚂蚁完成一次迭代后,按下式对路径上的信息作全局更新:t+11-t+t, 0,1 允许更新的路径可以全局最优解,或本次迭代的最优解。实践证明,逐渐增加全局最优解的使用频率,会使该算法获得较好的性能。3.1 轮盘赌选择3.1.1 轮盘赌选择基本思想 个体被选中的概率与其适应度函数值成正比。设群体大小为n,个体i的适应度为Fi,则个体i被选中遗传到下一代群体的概率为:/3.1.2 轮盘赌选择工作过程 设想群体全部个体的适当性分数由一张饼图来代表 见图。 群体中每一染色体指定饼图中一个小块。块的大小与染色体的适应性分数成比例,适应性分数愈高,它在饼图中对应的小块所占面积也愈大。为了选取一个染色体,要做的就是旋转这个轮子,直到轮盘停止时,看指针停止在哪一块上,就选中与它对应的那个染色体。举例: 轮盘赌选择法的选择概率计算表个体1234567891011适应度2.01.81.61.41.21.00.80.60.40.20.1选择概率0.180.160.150.130.110.090.070.060.030.020.0累计概率0.180.340.340.490.620.730.890.950.981.001.00若产生随机数为0.81,则6号个体被选中。实现代码: /*/轮盘选择,选择第一个大于随机数的点 double dbTemp0.0; if dbTotal 0.0 /总的信息素值大于0 dbTemprnd0.0,dbTotal; /取一个随机数 for int i0;iN_CITY_COUNT;i+ if m_nAllowedCityi 1 /城市没去过 dbTempdbTemp-probi; /这个操作相当于转动轮盘 if dbTemp 0.0 /轮盘停止转动,记下城市编号,直接跳出循环 nSelectedCityi; break; 3.2_MIN ACO3.2.1 _MIN算法的框架结构 -Min算法非常类似于Min-Min算法。同样要计算每一任务在任一可用机器上的最早完成时间,不同的是-Min算法改进了信息素更新策略,增加了限制条件: (1)信息素更新 在蚁群算法中,对所有蚂蚁走过的路径都进行信息素更新;而在_MIN蚂蚁算法中,只对在当前循环中找到最优解或是自实验以来找到的最优解的蚂蚁进行信息素更新,更新公式为:(a)b在公式ab中, 表示迭代最优解或全局最优解。在本文的所讲解的内容,所采用的是每次迭代的全局最优解。 (2)信息素大小的限制 在每个解元素上的信息被限定在一个区间(,)内,在更新信息素的时候,信息素的量如果超过了这个范围,就要做相应的限制: 如果 ,则设置 ; 如果 ,则设置; 和的值可以分别由以下公式得到:其中:是得到的最优解路径长度。 蚂蚁完成一次搜索,即为一次迭代。设迭代次数为n2时,取=/20;当迭代次数n2时,则由以下公式来计算: 式中 n/2,0.5 (3)信息素初始值设为 3.2.2 _MIN 算法流程图 _MIN改进算法与基本的蚁群算法的其他地方一致,仅仅是更新信息素的策略不同,以下是_MIN更新信息素的函数流程图: 是 否 是 否第4章蚁群算法在车辆路径问题中的应用4.1 车辆路径问题简介4.1.1 车辆路径问题定义 车辆路径问题(VRP)是Dantzig和Ramser于1959年提出的,它是指一定数量的客户,各自有不同数量的货物需求,配送中心向客户提供货物,由一个车队负责分送货物,组织适当的行车路线,目标是使得客户的需求得到满足,并能在一定的约束下,达到诸如路程最短、成本最小、耗费时间最少等目的。 车辆路线问题自1959年提出以来,一直是网络优化问题中最基本的问题之一,由于其应用的广泛性和经济上的重大价值,一直受到国内外学者的广泛关注。车辆路线问题可以描述如下(如图): VRP示意图 设有一场站(depot),共有M 辆货车,车辆容量为Q,有N位顾客(customer),每位顾客有其需求量D。车辆从场站出发对客户进行配送服务最后返回场站,要求所有顾客都被配送,每位顾客一次配送完成,且不能违反车辆容量的限制,目的是所有车辆路线的总距离最小。车辆路线的实际问题包