课程设计（论文）基于蚁群算法的物流软件的实现

1、基于蚁群算法的物流软件的实现目 录1引言- 1 -2算法部分- 1 -21简介- 1 -22 模型- 2 -23 算法的实现设计- 3 -24 蚂蚁算法的优点与不足- 4 -241 优势- 4 -242 不足- 4 -243 改进的方法：优选各种参数- 4 -244 优选参数- 4 -3系统部分- 5 -31 软件结构：- 5 -32 软件的实现- 6 -321 工具与原理- 6 -322 特点与实现原理- 6 -3221 核心算法使用了matlab生成的动态链接库- 6 -3222 显示坐标系相对于用户透明- 8 -3223 消除闪烁- 9 -3224 自定义代价表达式- 9 -3225 可

2、设定界面和默认参数- 10 -3226 可保存地图- 10 -4小结- 10 -参考文献- 11 -附录(主要代码)- 12 -基于蚁群算法的物流软件的实现【摘 要】随着经济的发展，交流的加强，物流受到越来越多人的关注，物流技术也日新月异。如何使用一种物流技术来减小物流的代价，并且使这种技术能被大多数不熟悉计算机技术的物流工作者所使用成为人们关注的焦点。由于人们过多的关注蚁群算法的模型，基于蚁群算法的物流软件市面上见到的并不多，在实际应用中这类软件不仅要解决好利用蚁群算法计算最小代价的问题，还要解决好对于计算前后数据的可视化的处理，因为我们不能期望用户对于一大堆浮点数有什么样好的感觉。本文就从

3、算法和系统两个方面介绍了以蚁群算法为核心的物流优化软件的开发过程。在计算模型的选择上，由于物流配送最终要返回发货的城市，从而在路径上形成一个回环，故选用的是比较流行的蚁群算法解决tsp问题的模型。用户坐标系选用的是用户比较熟悉的经纬度坐标系。通过整个软件系统的运作，用户可以很容易的得到他所期望代价的最优路径而不必关心繁杂的计算过程。【关键字】蚁群算法 物流配送 最优路径 可视化数据1引言开发一套优秀的物流软件，可以加快对客户需求的响应速度, 提高服务质量, 增强客户对物流系统的满意度, 降低服务商的运营成本。近年来一些新的启发式方法在求解此类问题上可以获得较快的收敛速度和较高质量的全局解。蚁群

4、算法正是这样的一种算法，它是由意大利学者marcodorigo等提出的一种仿生寻优算法，通过信息素的积累和更新来寻求最优解。蚁群算法主要特点是: 正反馈、分布式计算、与某种启发式算法相结合。正反馈过程使得该方法能很快发现较好解； 分布式计算使得该方法易于并行实现；与启发式算法相结合, 使得该方法易于发现较好解。2算法部分21简介较为简单的主体的聚集相互作用, 必然会涌现出复杂的大尺度行为。遗传算法之父霍兰德称这种现象为突现聚集特性。生物群体的复杂适应性行为就是从组成群体的适应性个体行为中涌现出来的一种全局性质。蚂蚁是一类行为简单的昆虫, 只有十分有限的记忆能力。在个体水平上, 蚂蚁的行为带有随

5、机性。但在群体水平上, 蚁群的集体行为却高度有序。蚂蚁依靠集体的智慧, 可完成相当复杂的任务。蚂蚁的觅食行为是动物行为学家非常感兴趣的现象。蚂蚁搬运食物回巢的路上, 分泌一种化学激素, 以吸引其他蚂蚁到这条路上来。蚁群通过这种机制, 可以发现一条从蚁巢到食物源的最短路径。假设在蚁巢和食物源之间, 存在两条长度不同的路径a 和b, 其中路径a 和b 的长度不同, 且b 的长度明显地大于a的长度, 那么蚂蚁将会选择较短的路径a。一般认为, 沿路径a 找到食物, 然后又从路径a 返回的蚂蚁, 花费时间较少, 将成为第一批携带食物回到蚁巢的蚂蚁。这样, 路径a 首先被蚂蚁两次分泌的化学激素重复标记。由

6、于这时路径a 上化学激素比路径b 上的多, 所以随后出巢和返巢的蚂蚁被吸引到a上来。随着越来越多的蚂蚁选择路径a , 路径a 上化学激素的浓度也越来越大。最后, 几乎所有蚂蚁选择了路径a。这一现象首先被deneubourg所发现。蚁群算法是根据以上现象提出的, 它的基本假设是群体的突现聚集特性。22 模型对一组给定的城市坐标,按照尽量少的消耗代价的原则,求其最佳的排列问题。有一个物流公司要到送货到n城市去,每个城市必须去一次且仅能去一次,遍历所有城市之后回到出发城市,并且满足代价最小的路径。在最理想的情况下，假设有n个城市,每个城市都有到其他城市的一条加权边,而且两城市i, j间距离dij =

7、 dji ,要求出最优解,即从( n -1) ! 条路径搜索出一条,时间复杂度为o ( ( n - 1) ! ) ,当问题规模从n增加到( n + 1)时,搜索空间会增加( n- 1)倍,所以当问题空间较大时,在有限时间内,无法得出最优解。在实际应用中,找出接近最优解的较优解往往能够满足实际需要,如何在减小搜索空间的情况下找出高质量的较优解,成了研究的方向。利用了蚁群搜索食物的过程与物流配送问题的相似性,通过人工模拟蚂蚁搜索食物的过程来求解货物配送的问题。实际应用中,每一个节点会面临很多的分支选择,问题的求解空间将会变得很大,以至于穷举寻找真正的最优解变得不可能,这时用蚂蚁算法求出的解往往并不

8、是最优解,而是接近最优解的较优解。设m 表示蚁群中蚂蚁的数量, n表示城市的数量, cij = cji ( i, j = 1, 2, , n) ,表示城市i和城市j之间的代价,eij表示城市i和j间的边，i j ( t) 表示t时刻在eij上残余的信息素的量，ij=1/cij ,是自定义可调整的参数,用于调节ij和ij的关系,pkij表示第k只蚂蚁选择边eij的概率, jk 表示第k只蚂蚁还未访问过的城市,各条路径上信息量都为0。每只蚂蚁将按照（1）式计算所得的概率,从(1)式可以看出,蚂蚁选择路径的概率随着ij增大而增加,随着cij的增大而减小。并根据程序产生的随机数,决定下一步的方向,直到

9、完成周游路径。每当所有蚂蚁完成一次循环后,按照(2)式(3) 式对路径信息量进行更新,式中的kij表示第k只蚂蚁在本次循环中在eij上留下的信息量,表示信息素蒸发系数，其中 (4) 式公式中q是一常数,表示每只蚂蚁周游一遍留下的信息素总量。当每只蚂蚁都完成一次上述操作时,就称该算法进行了一次周游。循环以上步骤,直到周游次数达到指定次数或在一定时间内没有新的更优解出现。23 算法的实现设计搜索最优解的算法的流程如下：1输入城市数据。2初始化等参数, m , n, q。3每只蚂蚁随机分配到各个城市并开始周游城市。4若一次周游没完成,选择下一个城市。5对每只蚂蚁经过的路径执行局部更新规则,得到新的最

10、优解,并对最优解进行更新。6若尚未达到指定周游次数,转到3。7输出最优解。算法中的核心部分是蚂蚁如何选取下一个城市,详细说明如下：蚂蚁k对城市i选择下一步的依据：根据(1)式计算蚂蚁选择不同城市的概率,其中j 表示本次周游尚未访问的城市集合,然后由计算机产生随机数rand ( ) ,根据下面规则进行城市选择,令p =rand ( ) ，sigma ( pki ) = pkij , (其中j =min ( j ) ) ,然后按照(5)式对城市进行选择：(5)式24 蚂蚁算法的优点与不足241 优势根据上述蚁群算法的求解流程,可知用蚂蚁算法能够极大的缩小求解搜索范围,算法复杂度从o ( ( n -

11、 1) ! )降低到o (nc*m *n2 ) ,由于大规模的并行计算,使蚁群算法能够在较大的空间中搜索理想的解;由于采用正反馈机制,收敛速度加快;使用构造性的贪婪算法,能在搜索的早期阶段找到较好的可接受的解。242 不足蚁群算法本质上和模拟退火算法、遗传算法等随机搜索算法一样,容易陷入局部极小点,存在扩大搜索空间与寻找最优解之间的矛盾,仿真实验表明,当搜索空间较小时,难以搜索到满意解,而若要增大搜索空间以提高搜索到最优解的概率,机器运算次数将迅速增多。243 改进的方法：优选各种参数通过大量仿真实验,发现诸如信息素的消散速度,在城市数量一定的情况下,蚂蚁的数量对于算法的影响都至关重要。244

12、 优选参数参数m研究发现,在其他参数不变的情况下,当蚂蚁数量太少,向最优解收敛很慢,在重复同样代数情况下,由于蚂蚁数量少,在能导致最优路径的那些边(优选边)走过的次数较少,难以留下较多的信息素,不利于算法迅速向最优解收敛,而且当优选边在数代之内不能被再次选择时,其信息素将挥发殆尽,从而造成之前数代蚂蚁的优选结果浪费,造成最优路径值的剧烈震荡。当m 值太大,首先,会增加运算量;其次,因为在最初的几代因为选择路径的随机性比较大,最初的最优值因为蚂蚁多以至于得到强化的速度太快,容易造成局部最优解。参数当太小时, 后代蚁会受到前辈蚂蚁的路线严重影响,早期收敛减慢,后期容易陷入局部最优, 当过大,初期收

13、敛虽然很快,但早期的优选边会因为挥发太快而失去,从而影响最优解的搜索速度。3系统部分31 软件结构：我们知道一个好的软件必然有一个好的设计，在软件开始的设计过程中，引入了一个分层的概念，整个软件被从逻辑上分为4个层次，如图2-1：（图3-1）ui 层：负责与用户的交流，它包括地图的显示，参数的输入等。可视化数据处理层：负责把从文件处理层和计算子层取得的数据与供ui层显示的可视数据进行相互转化，它包括了一个计算子层，用于利用蚁群算法计算最优的路径，在计算子层之上有一个数据接口，它负责matlab中使用的数据和vc中使用的数据间的相互转化。文 件 处 理 层：负责把文件中的数据载入内存中。通 用

14、层：它维护整个系统运行过程中的各种数据结构，并提供一些通用的方法。在图2-1中我们可以看到，ui层，可视化数据处理层，文件处理层之间是用虚线连接的，这是因为这三个层次间并没有实际的数据流，它们之间的数据交换都是通过共享通用层维护的数据来实现的，这样做的目的是为了减小系统的开销，因为这三个层次之间传递的数据流是相当庞大的。32 软件的实现321 工具与原理该系统使用了microsoft公司的visual c+6.0和mathworks公司的matlab6.5来实现。它的原理是由matlab生成实现蚁群算法的dll（动态链接库）,vc+则实现整个程序的界面，并通过调用matlab生成的dll实现利

15、用蚁群算法计算最优路径的功能。图2-2为系统的主界面。(图3-2)322 特点与实现原理3221 核心算法使用了matlab生成的动态链接库matlab作为当今世界上应用最为广泛的数学软件，具有非常强大的数值计算、数据分析处理、系统分析、图形显示甚至符号运算的功能。它是一个完整的数学平台，在这个平台上，用户只需寥寥数语就可以完成十分复杂的功能，大大提高了工程分析计算、图像处理的效率。但是matlab强大的功能只能在它所提供的平台上才能使用。这样当我们需要将在matlab下已开发完毕的蚁群算法应用到开发这个系统所使用的visual c+的环境下时就带来了问题，幸好的是matlab的compile

16、r可以将*.m文件编译成*.dll文件嵌入到vc+的程序中，我们按照以下步骤生成dll：1建立matlab的编译环境，在matlab命令行下输入以下命令并按提示完成：mbuild -setup2使用matlab的mcc命令生成dll：mcc b csglsharedlib:acatsplib acatsp其中acatsp是在matlab下已经完成了的实现蚁群算法的函数，acatsplib是生成的dll文件(包括引入库lib文件)的文件名，运行结束后生成了很多的文件，其中acatsplib.dll，acatsplib.lib，acatsplib.h是我们所需要的。接下来，我们按照以下的步骤在vc

17、中使用刚才生成的dll文件：1配制vc的环境(1)设置include和library目录在vc+ide中选择tools-options-directories。在showdirectorisfor：中选择includefiles，添加如下两个目录：externincludeexternincludecpp在showdirectorisfor:中选择libraryfiles，添加如下两个目录：externlibwin32externlibwin32microsofmsvc6这里假设为你的matlab的安装目录。这些操作只需要一次，vc+ide就会自动记录。自动应用到每一个工程（project）。

18、(2)工程(project)本身的一些设置在vc+ide中选择project-setting-c/c+；在category中选择codegeneration，在userun-timelibrary中选择multithreaded dll；在category中选择preprocessor，在preprocessordefinitions中添加msvc,mswind,ibmpc；在vc+ide中选择project-settings-lin，在categories中选择input，在ignorelibraries:中填入：msvcrt.lib；2将刚才matlab生成的acatsplib.dll,a

19、catsplib.lib,acatsplib.h导入vc工程，并在使用的地方包含头文件#include acatsplib.h3在使用之前还需要对acatsplib.dll进注册，使用完毕之后需要对其进行释放。注册使用函数acatsplibinitiallize(),释放使用函数acatsplibterminate()。4由于matlab和vc他们对于矩阵的存储方式是不同的(matlab中是先列后行，而vc是先行后列)，而且在生成的acatsplib.dll中的函数所接受和返回的参数是mxarray 型数据,因此我们在使用时必须把vc和matlab中的数据进行相互的转换，具体的转换过程请参看程

20、序visualdata.cpp中的calcoptimal()函数。由于核心的算法是封装在动态链接库中的，这使得核心算法独立于主程序，换句话说，如果要改进核心的算法，只需要替换掉主程序调用的dll文件即可，使得主程序的修改代价为零，这便于以后的升级。3222 显示坐标系相对于用户透明经纬度坐标系是用户在实际使用中最熟悉的坐标系，而在vc中是不能直接使用这种坐标系的，因而在程序中使用了坐标的映射机制，将经纬度坐标系转化为可以用于显示的坐标系，并且使显示坐标系的缩放和平移相对与经纬度坐标系无关，从而使得显示坐标系相对于用户透明，用户可以随意的使用经纬度坐标系并且对地图进行缩放和平移。我们首先看一下v

21、c默认的坐标系，如图2-3：(图3-3)下面是我们需要映射的可缩放平移的坐标系，如图2-4：(图3-4)其中dsize是表征缩放程度的变量；dxval是表征x向平移程度的变量；dyval是表征y向平移程度的变量；rc.width表示可视区的宽度；rc.height表示可视区的高度。我们使用以下步骤实现映射：1改变vc默认的映射模式，使用以下语句使其x向为从左向右增加，y向为从下向上增加，并且保证可视区位于坐标系的中央：setmapmode(mm_anisotropic);setviewportorg(rc.left+dsize,rc.bottom-dsize);setwindowext(1,-

22、1);2根据地图绘制区大小计算各城市的显示坐标。3根据平移程度在地图绘制区绘制出各个城市点。4当需要对地图进行缩放或平移时只需改变dsize，dxval，dyval值即可。3223 消除闪烁在完成使用地图缩放拖动的功能的时候，发现在缩放拖动的过程中地图闪烁现象非常严重，仔细分析后发现造成闪烁的主要是这两个方面的原因：1在windows中，当窗口由于任何原因需要重绘时，系统总是先用背景色（在这里是白色）将显示区清除，然后才调用onpaint进行绘图，而背景色往往与绘图内容反差很大，这样在短时间内背景色与显示图形的交替出现，使得显示窗口看起来在闪。2由于要绘制的对象比较复杂，系统不能够在很短的时间

23、内全部绘出，造成了比较大的反差，致使画面闪烁。那么为了消除闪烁，采用了以下两个方法：1重载onerasebkgnd(cdc* pdc)。这个函数就是用来处理刷新背景的消息，将所有的绘图全部绘在背景上，而在onpaint中不做任何事情，这样在重绘时系统就会使用已经绘上地图的cdc刷新背景，因而没有反差也就不会造成闪烁。2使用双缓冲技术。首先我在内存环境中建立一个绘图区域，然后在这个绘图区域上绘制复杂的图形，等图形全部绘制完毕的时候，再一次性的把内存中绘制好的图形复制到屏幕上，由于这种复制是非常规的内存对拷，速度很快，从而消除了闪烁。3224 自定义代价表达式要允许用户自定义表达式就必须解决好程序

24、对于用户输入的表达式的处理，在这里，我选用的是以波兰表达式的形式计算表达式的值，并且在表达式中支持两个变量distance和cost，表达式的计算按照以下的步骤进行：1对于表达式字符串的检查：检查输入的表达式是否正确，包括括号是否配对、库函数是否正确。2将算术表达式字符串转化成波兰表达式。3求波兰式的值。4返回计算得到的表达式值。具体的计算步骤参见程序mathstring.cpp中的注释。由于允许用户自定义代价表达式，这极大的提高了系统的灵活性，例如：例1：如果用户不希望从城市a直接到达城市b，那么他可以设代价表达式为“distance+cost”并且将a到b间的代价系数设为一个很大的数（比如

25、999999），这样运行出的结果就不会出现从a 到b的直接通路。例2：如果用户希望以最短的时间完成整个陪送的过程，那么他可以设置代价表达式为“distance/cost”，再将每个城市间的代价系数设为两个城市间的平均速度，这时的运行结果就会体现出最短的时间。以上的例子只是起到抛砖引玉的作用，只要用户善于开发利用，就可以实现很多很复杂的功能。3225 可设定界面和默认参数用户可以根据自己的喜好设定界面和默认参数，比如说标识城市标志的大小和颜色，路径的颜色等。3226 可保存地图用户可以在任何时候保存已显示出的地图，这样当再次察看最优路径的时候只需要打开保存下来的地图图片即可，不需要用户重新计算。

26、4小结经过一段时间的设计、编码和测试，系统能够按照功能需求正常运行，如图（3-5）为系统运行的结果。（图3-5）从图中我们可以看出系统选择的是一个依附在所选城市边缘的环状路径，由于所选用的代价只是两个城市间的距离，根据经验我们知道这类环状路径一般来说是较优的。由于起初没有找到一家真正的物流公司收集需求，该系统不能真正的应用于实际，不过它的底层功能（包括核心算法的代码以及数据接口等）比较完善，在将来有需求的时候可以很容易的进行二次开发而使其商业化。参考文献 1 dorigo m , caro g d. the ant colony optimization meta-heuristic. new

27、 ldeas in optimization,1999:1- 27. 2 dorigo m , gambardella l m. ant colonies for the traveling salesman problem. biosystems,1997,43: 73- 81. 3 jayaraman v k, kulkarnib d, karale s, et al. ant colony framework for optimal design and scheduling of batch plants. computers and chemical engineering, 200

28、0,7 (24) : 1901- 1912. 4 dorigo m , bonabeau e, theraulaz g. ant algorithms and stigmergy. future generation computer systems, 2000,6(16): 851- 871. 5 张纪会, 高齐圣, 徐心和. 自适应蚁群算法. 控制理论与应用, 2000,5: 181- 182. 6 陈骏坚, 李腊元. 用新型蚂蚁算法求解qosr 问题.武汉理工大学学报: 交通科学与工程版, 2005,29(3) : 342-345.the realization of logistics

29、 software based on aco（wangchao, anhui agricultural university, 230036）【abstract】along with the economical development, exchange strengthening, logistics receive attention from more and more people, logistics technology also changes everyday. how to use one kind of technology to reduce the cost of l

30、ogistics? how to make it acceptable for the people who are not familiar with computer employed in logistics? the mentioned questions become the focus of peoples attention. because too many people concerned about the aco model, logistics software based on aco on the market is not a lot, the practical

31、 application of such software is not only resolve calculation for the minimum price by aco, also solve for the visual data before and after calculation, we can not expect the user who face to a lot of float have a good feeling. this paper from the algorithms and systems two aspects introduces the de

32、velopment process of logistics software based on aco. in the calculation model selection, logistics and distribution eventually to return to the consignor city, which formed in the road on a loop, therefore, we select the model which is more popular and used to solve the tsp by aco. user coordinate

33、system uses the longitude and latitude coordinates which the users are more familiar with. through the entire software system, users can easily get the price he expects the optimal path and does not have to care about complicated calculation process.【key words】aco logistics cost optimal path visual

34、data附录(主要代码)蚁群算法（acatsp.m）%=% shortest_route 最优路径% c n个城市代价表，nn的矩阵% nc_max 最大迭代次数% m 蚂蚁个数% alpha 表征信息素重要程度的参数% beta 表征启发式因子重要程度的参数% rho 信息素蒸发系数% q 信息素增加强度系数%=function shortest_route=acatsp(c,nc_max,m,alpha,beta,rho,q)%初始化等参数, m , n, qn=size(c,1);%n表示问题的规模（城市个数）d=c;for i=1 : n d(i,i)=eps;endeta=1./d;

35、%eta为启发因子，这里设为代价的倒数tau=ones(n,n);%tau为信息素矩阵tabu=zeros(m,n);%存储并记录路径的生成nc=1;%迭代计数器r_best=zeros(nc_max,n);%各代最佳路线l_best=inf.*ones(nc_max,1);%各代最佳路线的长度l_ave=zeros(nc_max,1);%各代路线的平均长度while nc=rand);to_visit=j(select(1);tabu(i,j)=to_visit;endendif nc=2tabu(1,:)=r_best(nc-1,:);end%对每只蚂蚁经过的路径执行局部更新规则,得到新的

36、最优解l=zeros(m,1);for i=1:mr=tabu(i,:);for j=1:(n-1)l(i)=l(i)+d(r(j),r(j+1);endl(i)=l(i)+d(r(1),r(n);endl_best(nc)=min(l);pos=find(l=l_best(nc);r_best(nc,:)=tabu(pos(1),:);l_ave(nc)=mean(l);nc=nc+1%对最优解进行更新delta_tau=zeros(n,n);for i=1:mfor j=1:(n-1) delta_tau(tabu(i,j),tabu(i,j+1)=delta_tau(tabu(i,j),

37、tabu(i,j+1)+q/l(i);enddelta_tau(tabu(i,n),tabu(i,1)=delta_tau(tabu(i,n),tabu(i,1)+q/l(i);endtau=(1-rho).*tau+delta_tau;%路径表清空tabu=zeros(m,n);end%返回结果shortest_route=r_best(pos(1),:)坐标映射(distributionmanageview.cpp)/1建立显示坐标系/2在内存中根据显示坐标和缩放平移程度绘出个坐标点/3将在第2步中绘出的图形拷贝到屏幕上bool cdistributionmanageview:oneras

38、ebkgnd(cdc* pdc) cdc memdc; memdc.createcompatibledc(null);/建立相兼容的内存缓冲cstring colorstr;colorref color;/城市的颜色getprivateprofilestring(system,cityclr,ffffff,colorstr.getbuffer(10),10,ccommon:inifilepath);sscanf(colorstr.getbuffer(colorstr.getlength(),%x,&color);cbrush citycolor(color);/已选城市的颜色getprivateprofilestring(system,selclr,00000ff,colorstr.getbuffer(10),10,ccommon:inifilepath);sscanf(colorstr.getbuffer(colorstr.getlength(),%x,&color);cbrush selectedcitycolor(color);getprivateprofilestring(system,pathclr,00000ff,colorstr.getbuffer(10),10,ccommon:inifilepath);sscanf(co