用蚁群算法实现自动化仓库拣选路径的优化 毕业论文.doc

用蚁群算法实现自动化仓库拣选路径的优化摘要 蚁群算法是一种解决tsp问题的良好方法，算法的主要特点是：正反馈、分布式计算、与某种启发式算法相结合。该算法共有三种形式。本文通过对比试验，选择了一种应用到解决自动化仓库的路径优化问题中。计算机仿真结果表明了该算法的有效性。关键词 蚁群算法，自动化仓库，固定货架，路径优化1 引 言 自动化立体仓库是现代物资存取技术与自动化技术相结合的高新技术产物，是物流自动化的显著标志，它一般由多排立体的固定货架及堆垛机系统、输送系统、分拣系统、计算机管理与监控系统等部分组成，一般具有单元出（入）库、拣选出（入）库、盘库和倒库等多种作业方式。 在各种作业方式中，拣选出（入）库作业是一类重要的作业方式。拣选入（出）库是指堆垛机从巷道口出发，一次存取若干个货位，然后返回巷道口，并将货箱送到出货台。这就存在一个优化问题：如何选择作业排序可使堆垛机走过的路径或作业时间最短？这个问题是提高仓库效率的关键。目前针对它已有许多解法，如穷举搜索法（exhaustive search method）, 贪心法（greedy method）, 动态规划法（dynamic programming method）分支界定法（branch-and-bound），遗传算法（genetic agorithm）等。本文使用了一种新的算法蚁群算法，该算法是一种新型的模拟进化算法，该算法比较容易实现，而且比较灵活，经过仿真试验，证明是一种有效的方法。2 优化问题的建模仓库货架主要分为固定货架和旋转货架。固定货架以其占用空间少、存储容量大而广泛应用于自动化立体仓库中。本文以固定货架为例说明问题。 图1 具有4层12列的固定货架 如上图所示，每个单元货位中放一种货物，在拣选入（出）库作业时，由管理计算机控制堆垛机从出货台出发，根据计算机中的货单要求去存取m个货位，再回到出货台待命。因为堆垛机可同时在水平、垂直两个方向运行，所以堆垛机从货位运行到货位所需要得时间是： 其中为,两点的坐标，为堆垛机的水平、垂直速度。可见堆垛机所需最短时间问题，可转化为包括出货台在内的点数为nm1的旅行商问题。3 算法原理蚁群算法是受到对真实的蚁群行为的研究启发而提出的。仿生学家经过大量细致观察研究发现，蚂蚁个体之间是通过一种称为外激素的物质进行信息传递的，蚂蚁在运动过程中，能够在它所经过的路径上留下外激素，而且蚂蚁在运动过程中能够感知这种物质，并且以此指导自己的运动方向，所以，大量的蚂蚁组成的蚁群的集体行为便表现出一种信息正反馈现象。我们并不想完全模拟蚁群，而是对使用人工蚁群方法来解决优化问题感兴趣因此，我们的蚁群与实际的蚁群有三个主要的区别： e人工蚁群具有记忆性，人工蚁群不是完全盲目的， d人工蚁群处在离散的时间环境中。 h c 虽然有区别，我们仍然可以用蚂蚁群的行为来形象地说明人工蚁群 b 算法的原理。如图2所示，设，0.5。我们假定在每个离散的等时间间隔：，有个 a蚂蚁从到达，同时有个蚂蚁从到，每只蚂蚁的速度为 图2，并且，每有一只蚂蚁经过时，在时间留下信息素密度为。 蚂蚁在选择路径时，那些有更多蚂蚁曾经选择过的路径（也就是具有更高信息素密度的路径），被再次选中的可能性最大。当时，没有信息素，有只蚂蚁分别在和。蚂蚁走哪条道路是完全随机的。因此，在每个点上蚂蚁将有只经过，另外只经过。当时有只蚂蚁从到，它们发现指向道路上的信息素密度是，是由从出发的蚂蚁留下的；指向道路上的信息素密度是，其中是由出发蚂蚁留下，另外是从出发经过已经到达的蚂蚁留下。因此，选择经过到的可能性就更大，从出发到的只蚂蚁也面临着同样的选择，由此产生一个正反馈过程，选择经过的蚂蚁越来越多，直到所有的蚂蚁都选择这条较近的道路。蚁群算法就是利用蚂蚁的这一特性，解决最优化问题。4 蚁群算法的实现运用蚁群算法。设为堆垛机从货位运动到所耗费的时间，。设 表示时刻位于货位的蚂蚁的个数，蚂蚁总数，表示时刻在连线上残留的信息量，初始时刻各条路径上的信息量为（为常数）。用参数表示信息量的保留度，则经过个时刻后，路径上的信息量根据下式作调整： 表示第只蚂蚁在本次循环中留在路径上的信息量，表示本次循环所有经过的蚂蚁留在上的信息量。 定义。蚂蚁（，）在运动过程中，表示在时刻蚂蚁由位置转移到位置的概率： 我们用记录蚂蚁目前已经走过的货位集合，allow表示蚂蚁下一步允许选择的货位集合，它等于全部的货位集合除去第只蚂蚁已走过的集合。 定义为第只蚂蚁在本次循环中耗费的时间和。 用蚁群算法解决存取路径问题是一个递推过程 ，当时，将蚂蚁放在各货位，设定每条路径上的信息量初值，每只蚂蚁根据公式决定的概率从货位到货位。表示曾经有多少蚂蚁经过路径（，）；说明较近的货位有更大的可能性被选中。，用来控制两者对蚂蚁选择的影响力程度。经过一个循环后，根据公式计算更新每条路径的信息量。将所有的复原，最后求出本次循环的所耗费的最短时间。这个过程不断重复，直到所有的蚂蚁都选择同样的路径，或者循环次数达到预先设定的最高次数。根据货单要求，存取n个货物算法设计如下： 初始化： 设定，循环计数器，对每条路径设定初始信息量c,将只蚂蚁放在个货位上（为了使问题简化，设定）。 设定集合的索引，对从到，把第只蚂蚁放在起始位置，对应的设定集合 重复下面的步骤，直到集合tabu满为止（这一步将重复次）：设定；对从到，根据公式确定的概率，选择下一步移动的目标货位在时间时，第只蚂蚁所在的货位是；将第只蚂蚁移到；把加入到集合中。 对从到：将第只蚂蚁从移动到；计算第只蚂蚁所耗费的时间和，并更新最小时间和；对每条路径（，）：； 对每条路径（，）根据计算；设定；设定；对每条路径（，），设定。 如果，则清空所有的集合转到第二步；否则，得出最优的路径。在这儿我们介绍的是ant-cycle算法，这种算法，每当结束一个循环后，根据公式计算。另外还有两种蚁群算法，不需要等到循环结束，每一步都更新，一种称为ant-density,公式：=另一种称为ant-quantity,公式：=5 实验结果及分析我们分别采用ant-cycle、ant-quantity、ant-density算法，以存取30个货位为例，使用visual c+6.0在pentium550pc机上运行通过，我们对各参数分别设如下值进行仿真0，0.5,1,2,5,0,1,2,5,0.3,0.5,0.8,0.9,100,1000,2000，3000，1，100，1000。取有代表性的结果列表如下：表1 三种蚁群算法的优化结果对比表算法最优路径耗时（秒）ant-cycleant-quantityant-density1112101010100010001000193.437199.569208.758表2 不同的参数所得优化结果对比表最优路径耗时（秒）0.31500653.4810.520.51200262.7940.520.510200262.8840.520.5100200261.766150.5100200232.196150.5100500226.652150.51001000193.941通过大量的实验我们得出如下结论：（1）ant-cycle算法与另外两种算法相比，具有更好的优化效果；（2）决定信息量对路径选择的影响程度，决定从运行到所耗时间对选择的影响程度。经过试验发现当，时可以取得较好解；（3）的值对结果并没有多大的影响；（4）循环次数越多，最优化结果越好，但是达到次以后，在提高循环次数就没有太明显的影响。当=1，=5，如下图所示，图3为最优化结果随循环次数下降曲线，图4为=1000时，所得出的最优路径曲线： 图3 最优化结果进化曲线 图4 所找到的最优路径6 结 论自动化立体仓库的路径优化问题一直阻碍存取货物效率的提高。蚁群算法具有全局优化特性，是解决tsp问题的有效算法。本文将这一算法应用到立体仓库的路径优化中，通过对比试验，选择了其中的ant-cycle算法；找到了一组效果较好的参数。仿真实验说明了算法的有效性。参 考 文 献1 colorni a,dorigo m.maniezzo v.distributed optimization by ant colonies.proc 1st europen conf artificial life.pans,france:elsevier,1991:134-1422 colorni a,dorigo m,maniezzo v.aninvestigation of some properties of an ant algorithm.proc ppsn92:509-5203 marco dorigo,vittorio maniezzo,alberto colorni.ant system:optimization by a colony of cooperating agents.ieee transactions on systems,man,and cybernetics-part b: cybernetics,vol.26,no.1,february 1996:29-414 g.d.caro,m.dorigo,”antnet:a mobile agents approach to adaptive routing”,technical report iridla 97-125 林家恒.双伺服机分层旋转货架拣选路径优化的两级遗传算法.控制与决策，1997，4：332336 order picking path optimization for automatic warehouse by ant algorithms abstract ant algorithm is a good method to solve tsp problem.the main characteristics of this algorithm are positive feedback,distributed computation,and the use of a constructive greedy heuristic.the algorithm have three models.through the contrast expe