蚁群算法在物流系统优化中的应用.pptVIP

[63]李军军.微粒群优化算法的改进与应用[D ].上海:上海海事大学，2005[64]付宇.蚁群优化算法的改进及应用[D ].上海:上海海事大学，2006 1)在算法中，当采用中心点蚂蚁跳跃来选择各自管辖销售点时，求得的最优解为组合方案一 其配送组合方案为:选择网点号为0，1，7的三点作为配送中心，0号中心负责管辖5，4，11号销售需求点，并给它们供货;1号中心负责管辖2，3，8号点，7号中心负责管辖6，9，10号点，三个配送中心除了要满足自身产品需求量外，还得负责各自所管辖点的需求量，并且总量都不超过其最大容量13个单位，满足条件的最小费用为161。 2)当采用需求点蚂蚁来跳跃寻求各自中心点时，不但找到了1)中的组合方案和最优解，还得到了另外以下四组组合方案 组合方案二 组合方案三 组合方案三 组合方案五 从该实例的求解结果来看，本章所设计的蚁群算法不仅得到了最优解，还得到了更多的组合解方案，证明了本章所设计的算法是行之有效的，能够比较好地解决该类实际应用中的组合优化问题。 LOGO 蚁群算法在物流系统优化中的应用 ——配送中心选址问题 算法举例 框架 蚁群算法概述 蚁群算法模型 物流系统中配送中心选择问题 蚁群算法应用与物流配送中心选址 蚁群算法简介 蚁群算法(Ant Algorithm简称AA)是近年来刚刚诞生的随机优化方法，它是一种源于大自然的新的仿生类算法。由意大利学者Dorigo最早提出，蚂蚁算法主要是通过蚂蚁群体之间的信息传递而达到寻优的目的，最初又称蚁群优化方法 (Ant Colony Optimization简称ACO)。由于模拟仿真中使用了人工蚂蚁的概念，因此亦称蚂蚁系统 (Ant System，简称AS)。 蚁群觅食 图1 How do I incorporate my LOGO and URL to a slide that will apply to all the other slides? On the [View] menu, point to [Master], and then click [Slide Master] or [Notes Master]. Change images to the one you like, then it will apply to all the other slides. [ Image information in product ] Image : www.wizdata.co.kr Note to customers : This image has been licensed to be used within this PowerPoint template only. You may not extract the image for any other use. 蚁群算法是利用群集智能（swarm intelligence）解决组合优化问题的典型例子，作为一种新的仿生类进化算法，该算法模仿蚂蚁觅食时的行为，按照启发式思想，通过信息传媒—菲洛蒙(Pheromone)的诱导作用，逐步收敛到问题的全局最优解，迄今为止，蚂蚁算法己经被用于TSP问题，随后应用在二次分配问题(QAP)、工件排序问题、车辆调度等问题。 ACO优化机理 蚂蚁有能力在没有任何提示下找到从其巢穴到食物源的最短路径，并且能随环境的变化而变化，适应性的有哪些信誉好的足球投注网站新的路径，产生新的选择。其根本原因是蚂蚁在寻找食物源时，能在其走过的路上释放特殊的信息素(Pheromone)，随着时间的推移该物质会逐渐挥发，后来的蚂蚁选择该路径的概率与当时这条路径上该物质的强度成正比。当一定路径上通过的蚂蚁越来越多时，其留下的信息素轨迹也越来越多，后来蚂蚁选择该路径的概率也越高，从而更增加了该路径的信息素强度，而强度大的信息素会吸引更多的蚂蚁，从而形成一种正反馈机制。通过这种正反馈机制，蚂蚁最终可以发现最短路径。特别地，当蚂蚁巢穴与食物源之间出现障碍物时，蚂蚁不仅可以绕过障碍物，而且通过蚁群信息素轨迹在不同路径上的变化，经过一段时间的正反馈，最终收敛到最短路径上。 人工蚂蚁运动图 图2 人工蚂蚁运动图 图3 在图中a点为食物源，而b点位蚂蚁巢穴，蚂蚁正往返于食物与巢穴之间，其路径为一条直线，如图2.1所示。假设在某一时刻在蚂蚁的路径中突然出现了一个障碍物，原有的路径被切断，这样，从a到b的蚂蚁就必须决定应该往左还是往右走，如图2.2所示。而从b到a的蚂蚁也必须选择一条路径。这种决定会受到各条路径上以往蚂蚁留下的信息素物质浓