学年论文范本

1、学 年 论 文论文题目蚁群算法关于物流配送简单应用学生姓名周映婷学号 091614408专业班级金融信息与计算科学指导教师姚慧玲职称 2012年8月24日摘要本文建立了带约束条件的物流配送问题的数学模型，运用蚁群算法解决物流配送路径优化问题，并将遗传算法的复制、交叉、变异等遗传算子引入蚁群算法，同时改进信息素的更新方式、客户点选择策略，以提高算法的收敛速度和全局搜索能力。经过多次实验和计算，证明了用改进的蚁群算法优化物流配送线路，可以有效而快速地求得问题的最优解或近似最优解。关键字：蚁群算法、物流配送、优化目 录 一、引言1二、蚁群算法背景及国内外研究现状 1三、蚁群算法的理论初探 7（一）蚁

2、群算法的基本原理5（二）蚁群算法的基本算法 6 四、蚁群算法的算法1参考文献一、 引言 如今随着市场经济的繁荣，物流配送业迅猛发展，越来越多的企业看到了物流配送在企业生产销售流程中的重要作用。随着企业规模的逐渐壮大，业务规模也不断扩大，配送网点的数量也逐渐增多，安排配送路线的复杂度越来越高，手工安排配送线路已经很难满足企业的业务需求，采用计算机进行路线安排势在必行。而物流配送路径优化问题正好是典型的组合优化问题，属于一类NP完全难问题，具有很高的计算复杂性。蚁群算法是一种最新发展的模拟昆虫王国中蚂蚁群体觅食行为的仿生优化算法，它能够将问题求解的快速性、全局优化特性和有限时间内答案的合理性结合起

3、来, 因此对于能够直接转化为路径优化问题的组合类寻优问题, 能取得比较理想的效果。2、 蚁群算法的背景及国内外研究现状蚁群算法是由意大利学者DorigoM于1991年提出的，其实际上是一个复杂的智能系统，它有很强的鲁棒性，优良的分布式计算机制和易于与其他方法结合等优点。蚁群算法是一种最新发展的模拟昆虫王国中蚂蚁群体觅食行为的仿生优化算法，该算法采用了正反馈并自动催化机制，在解决许多复杂优化问题上已经展现出一优异的性能和巨大的发展潜力，近几年吸引了国内外许多学者对其进行了多方面的研究工作。国际著名的顶级学术刊物Nature曾多次对蚁群算法的研究成果进行报道，Future Generation C

4、omputer Systems和IEEE Transations on Evolutionary Computation分别于2000年和2002年了蚁群算法特刊，在布鲁塞尔每两年召开一次的蚁群算法国际研讨会会进一步促进了这一智能计算领域的学术交流，从而使这种新兴的仿生优化算法展现出勃勃生机，其应用范围完全可以和遗传算法相媲美。它现在已成为国际智能计算领域中备受关注的研究热点和前沿性课题。蚁群优化算法最初用于解决TSP问题，经过多年的发展，已经陆续渗透到其他领域中，如，图着色问题、大规模集成电路设计、通讯网络中的路由问题以及负载平衡问题、车辆调度问题等。蚁群算法在若干领域己获得成功的应用，其中

5、最成功的是在组合优化问题中的应用。近年来遗传算法、禁忌搜索算等都在此问题上进行了运用，并取得了成。但也存在各自的问题，如遗传算法局部搜索能力不强，总体上可行解的质量不是很，禁忌搜索算法对于初始解具有较强的依赖等等。目前研究的热点是混合算，通过混合在一定程度上弥补算法的缺陷。3、 蚁群算法的理论初探 3.1蚁群算法的基本原理 根据仿生学家的研究发现：蚂蚁虽然没有视觉，但它们会分泌一种叫信息素的分泌物标记它们碰过的路。在未知的路口，它们随机地挑选一条路径前行，同时释放信息素，它们走过的路越长，则释放的信息量越少。当它们再次经过该路口时，则选择信息素较浓的路径概率比较大，从而形成了一个正反馈机制。

6、对上面的蚁群总结规范描述如下：1、范围：蚂蚁观察到的范围是一个方格世界，蚂蚁有一个参数为速度半径（一般是3），那么它能观察到的范围就是3*3个方格世界，并且能移动的距离也在这个范围之内。 2、环境：蚂蚁所在的环境是一个虚拟的世界，其中有障碍物，有别的蚂蚁，还有信息素，信息素有两种，一种是找到食物的蚂蚁洒下的食物信息素，一种是找到窝的蚂蚁洒下的窝的信息素。每个蚂蚁都仅仅能感知它范围内的环境信息。环境以一定的速率让信息素消失。 3、觅食规则：在每只蚂蚁能感知的范围内寻找是否有食物，如果有就直接过去。否则看是否有信息素，并且比较在能感知的范围内哪一点的信息素最多，这样，它就朝信息素多的地方走，并且每

7、只蚂蚁都会以小概率犯错误，从而并不是往信息素最多的点移动。蚂蚁找窝的规则和上面一样，只不过它对窝的信息素做出反应，而对食物信息素没反应。4、移动规则：每只蚂蚁都朝向信息素最多的方向移，并且，当周围没有信息素指引的时候，蚂蚁会按照自己原来运动的方向惯性的运动下去，并且，在运动的方向有一个随机的小的扰动。为了防止蚂蚁原地转圈，它会记住最近刚走过了哪些点，如果发现要走的下一点已经在最近走过了，它就会尽量避开。 5、避障规则：如果蚂蚁要移动的方向有障碍物挡住，它会随机的选择另一个方向，并且有信息素指引的话，它会按照觅食的规则行为。 6、播撒信息素规则：每只蚂蚁在刚找到食物或者窝的时候撒发的信息素最多，

8、并随着它走远的距离，播撒的信息素越来越少。根据这几条规则，蚂蚁之间并没有直接的关系，但是每只蚂蚁都和环境发生交互，而通过信息素这个纽带，实际上把各个蚂蚁之间关联起来了。比如，当一只蚂蚁找到了食物，它并没有直接告诉其它蚂蚁这儿有食物，而是向环境播撒信息素，当其它的蚂蚁经过它附近的时候，就会感觉到信息素的存在，进而根据信息素的指引找到了食物。3.2 蚁群算法的基本算法蚁群算法是一种由于受自然界生物的行为启发而产生的“自然”算法。它是从对蚁群行为的研究中产生的。蚁群中的蚂蚁以“信息素”（pheromone为媒介的间接的异步的联系方式是蚁群算法的最大的特点。蚂蚁在行动（寻找食物或者寻找回巢的路径）中，

9、会在它们经过的地方留下一些化学物质（我们称之为“信息”）。这些物质能被同一蚁群中后来的蚂蚁感受到，并作为一种信号影响后到者的行动（具体表现在后到的蚂蚁选择有这些物质的路径的可能性，比选择没有这些物质的路径的可能性大得多），而后到者留下的信息会对原的信息素进行加强，并且如此循环下去。这样，被越多蚂蚁择的路径，在后到蚂蚁的择中被中的可能性就越大（因为残留的信息浓度较大的缘故。由于在一定的时间内，越短的路径会被越多的蚂蚁访问，因而积累的信息量也就越多，在下一个时间内被其他的蚂蚁选中的可能性也就越大。这个过程会一直持续到所有的蚂蚁都走最短的那一条路径为止。我们用人工蚂蚁代替车辆对客户点进行配送，蚂蚁在

10、i 客户点择服务的下一个客户点j 时，主要考虑两个因素，一是i，j两顾客点之间的关系的亲密程度，称为可见度，记为；另外考虑的是由迄今完成的循环所得路径方案体现出来的由i 到j 的可行性，即信息素浓度。在t 时刻蚂蚁k 由客户点i 转移到客户点j 的概率：（t）=，j 1.4其中，allowedk=0,1,n-1-tabuk 表示蚂蚁k 尚未服务的客户点。可见度 ：当下一个要服务的客户点会使运载总量超出汽车载重量，或者使运距超过一次最大行驶距离时，就返回到配送中心，人工蚂蚁代表下一辆车出发，继续配送。当一次循环结束后，蚂蚁遍历了所有客户点，完成一次配送。当所有蚂蚁完成一次循环后，根据各蚂蚁遍历的

11、好坏（目标函数值），计算信息素增量，更新相关路径上的信息素，更新规则：4、 蚁群算法的算法4.1遗传算法对蚁群算法的改进遗传算法的操作算子是遗传算法的核心内容，我们将复制、交叉、变异这些遗传算子引入蚁群算法中，以提高算法的收敛速度和全局搜索能力。复制遗传算法中，复制的主要思想是认为父代中的优质个体可能更接近全局最优解，应该在子代中继承并继续进化。复制操作使得父代中优质的个体能够在子代中得以保存，避免交叉变异等操作导致优质个体在种群中丢失。蚁群算法中，在每一代搜索完成后，我们将当前父代中最优的解复制到子代中，使得最优的个体能在子代中继续积累信息素，这样能加快算法的收敛速度。编码遗传算法中的交叉和

12、变异操作是建立在基因编码上的，因此在引入交叉和变异操作之前，我们首先对物流配送模型进行编码。假设L 个客户点，K 辆配送车辆，本文采用的编码方式是将这L 个客户点分别用1 到L 这L 个自然数标识；第一辆车从配送中心出发时用0 标识，其他车辆则分别用L+1，L+2，L+K -1 表示。由于同一辆车可以多次配送，所以，2 次以上配送的车辆出发时，依次用L+K，L+K+1，表示。新的一辆车从配送点出发，或者编码结束，就表示前一辆的路线结束，返回配送中心。这样就将一次配送表示为一组由0 和自然数组成的编码。例如，6 个客户点，我们分别用1 至6 表示，3 辆车进行配送。那么编码：0，1，2，3，7，

13、4，5，8，6表示3 辆车的配送线路分别是：车辆10->1->2->3->0，车辆20->4->5->0，车辆30->6->0。又如编码：0，1，2，3，8，4，5，9，6表示的配送线路为：车辆10->1->2->3->0，车辆30->4->5->0，车辆1 第二次配送0->6->0。交叉交叉操作是遗传算法中增加种群多样性，防止算法早熟、停滞的操作。在蚁群算法中引入交叉操作，可以效地扩大搜索空间，避免算法陷入局部最优解。在蚁群算法每一代搜索完成之后，我们将其中的最优解和次优解进行编码交叉

14、操作，交叉规则如下：1) 假设两组编码分别是S1 和S2，首先随机生成交叉段的长度和交叉段起始位置；2) 找出S1 和S2 中的交叉段，假设S1：P1|P2|P3， S2：Q1|Q2|Q3，P2 和Q2 分别是S1 和S2 的交叉段；将Q2 插入S1 中，位于P2 前面， 这样形成新的编码S3 ：P1|Q2|P2|P3；3) 在S3 中，删除P1、P2、P3 中与Q2重复的编码。形成交叉编码S3；4) 同样的方法用在S2 上，生成新的编码S4；5) 比较S1、S2、S3、S4 的结果，出最优的两组编码并保存。变异变异操作也是增加种群多样性的一种进化手段。适度的变异，既能保持种群内个体的多样化，

15、又能提高算法的效率。在蚁群算法中，我们在完成交叉操作后，对种群中最优个体进行变异操作，操作方法为：1) 随机生成变异次数N；2) 随机生成两个不同的自然数n1，n2>1（第一位不变，保证编码以物流中心为起点）；3) 在最优个体的编码S 中，将第n1 位和第n2 位的编码对调；4) 重复2)、3)N 次，生成新的编码S；3) 比较S 和S的结果，保存较优解。（具体程序见附件）蚁群算法数据 城市的数量为50，车辆数量为1；蚂蚁数量为30（进行搜索的蚂蚁数量，一般取值为城市数量的2/3）城市的x,y坐标为：城市0（37,52）、城市1（25,80）、城市2（30,23）、城市3（70,60）、

16、城市4（92,51）、城市5（42,64）、城市6（87,45）、城市7（39,7）、城市8（28,71）、城市9（55,20）、城市10（14,56）备注：城市0为初始城市，即货车开始地点，另，以上坐标都是随机编写。下面为用经遗传算法改进后的蚁群算法运行后得出的结果：表1_1 最佳路径最短路径为： 1 10 1 8 5 3 4 6 9 7 2总最短路径长为：244.163，由第45代产生的最佳结果，变异成功3次，用时0.031秒。表1_2 进化图以上为进化图；x,y轴分别是城市坐标轴，蓝色部分的线表示平均路径长度，红色部分的线表示最短路径路径长度。参考文献：1 XU Ning, LI Chu

17、n-guang, ZHANG Jian, etal. Studies on Some ModernOptimization Algorithms. SYSTEMSENGINEERING AND ELECTRONICS. 2002Vol.24 No.12: 101-104. 徐宁，李春光，张健等. 几种现代优化算法的比较研究. 系统工程与电子技术， 2002 年，第24 卷第12 期：101-104.2 LANG Mao-xiang. Study of theoptimizing of physical distributionrouting problem based on genetical

18、gorithm J. China Journal of Highwayand Transport, 2002, 15(3): 76-79. (inChinese) 郎茂祥. 基于遗传算法的物流配送路径优化问题研究J. 中国公路学报，2002,15(3)：76-79.3 CHANG Yun-tao, PENG Guo-xiong. Urbanarterial road coordinate control based ongenetic algorithm J. Journal of Trafficand Transportation Engineering, 2003,3(2):106-112

19、. (in Chinese) 常云涛，彭国雄.基于遗传算法的城市干道协调控制J. 交通运输工程学报，2003，3(2)：106-112.4 LIN Yang, CAI Yuan-li, HUANG Yong-xuan.Dynamic origin-destination matrixestimation for freeways J. Journal ofChang'an University (Natural ScienceEdition), 2003, 23(6): 83-86. (in Chinese)林勇，蔡远利，黄永宣. 高速公路动态OD矩阵估计J. 长安大学学报(自然科学版)，2003，23(6)：83-86.5 LANG Mao-xiang, HU Si-ji. Study on theOptimization of Phys