基于人工蜂群算法的物流配送系统设计.doc

基于人工蜂群算法的物流配送系统设计 目 录学校代码： 10246学 号： 硕 士 学 位 论 文（专 业 学 位）基于人工蜂群算法的物流配送系统设计Design for the Logistics Distribution System Based on Artificial Bee Colony院 系：软件学院专 业： 软件工程姓 名：指 导 教 师： 完 成 日 期： 2015年2月10日目 录摘 要IIIABSTRACTIV第一章 引 言11.1 车辆路径规划问题的研究现状11.2 通韵物流配送系统路径管理存在的问题41.3 本文的主要内容51.4 本文的篇章结构7第二章 人工蜂群算法基础82.1 群体智能算法82.2 人工蜂群算法102.3 人工蜂群算法的基本流程11第三章 通韵物流配送系统需求分析143.1 物流配送系统的主要功能143.1.1 车辆任务信息维护模块153.1.2 车辆调度管理模块173.1.3 车辆追踪管理模块193.2 物流配送系统的核心流程203.2.1 配送货物到站流程213.2.2 货物配送调度流程223.2.3 快件收取调度流程243.3 物流配送系统的安全需求27第四章 通韵物流配送系统设计284.1 物流配送系统的整体架构284.2 车辆配送基础信息管理子系统设计314.2.1 客户预约管理314.2.2 货物仓储管理324.2.3 配送机构信息管理334.3 车辆路径规划子系统设计334.3.1 车辆行驶区域限制344.3.2 基于人工蜂群算法的静态路径优化344.3.3 启发式动态路径调整414.4 车辆实时监控子系统设计414.4.1 车辆载货信息管理424.4.2 车辆在途状态管理424.4.3 车辆历史路径管理424.5 与同类系统的比较434.6 通韵物流配送系统的应用效果44第五章 结 论465.1 通韵物流配送系统的特色465.2 不足与展望47参考文献48致 谢50基于人工蜂群算法的物流配送系统设计 摘 要摘 要得益于电子商务在国内的兴起，国内物流快递近几年来发展迅速。但于此同时物流快递市场正逐渐趋于饱和，快递行业面临的挑战越来越严苛，快递公司间的竞争也变得越来越激烈。各家公司都在研究如何保持自身优势，扩大市场份额。通韵公司是一家中型民营快递公司，公司核心竞争力在于其在成本上的优势。而对车辆路径进行科学优化是降低公司运营成本的重要手段之一。但在以往通韵公司对车辆路径的管理更多的依赖于人工，其结果并不合理，过于粗糙，难以应对公司业务上的快速变动，造成了快件配送在时间和成本上巨大的浪费，不能满足公司的发展要求。如何优化车辆路径，降低公司配送成本，提高公司配送效率，成了公司发展道路上的一个巨大问题。首先讨论了通韵公司的现状及其在车辆路径管理上的不足。明确了设计开发一个基于人工蜂群算法来规划管理车辆路径的物流配送系统对于公司的重要性。以此为基础，讨论整个物流配送系统的主要功能，将主要功能划分为车辆任务信息维护模块、车辆调度管理模块以及车辆追踪管理模块，随后分析确定了通韵物流配送系统的配送货物到站流程、货物配送调度流程以及快件收取调度流程等主要核心流程。在需求分析的基础之上，设计了系统的整体架构，并对车辆配送基础信息管理、车辆路径规划以及车辆实时监控三个核心子系统进行详细设计。其中重点介绍了如何通过人工蜂群算法对车辆路径进行规划。最后对系统的特色和应用效果进行了简要分析总结,对系统未来进行了展望。关键词 群体智能，人工蜂群算法，路径规划，物流配送系统，货物配送IIIABSTRACTWith the growth of electronic commerce in China, express delivery has maintained rapid development. However, at the same time, express delivery gets saturated .It has increased requirements for the services. Express company competition is becoming increasingly fierce. Companies are trying to find out how to keep their advantages and expand their market share. Tongyun is a medium-sized private express company. Its core competitiveness is its low-cost. Scientific plan for routes is one of the most important ways to reduce the company cost. But in the past, Tongyun plans routes manually which wastes lots of money and time and cant accommodate itself to the changed situation. The company wants to know how to plan routes scientifically to reduce the companys delivery cost and raise the delivery speed.First of all, the situation of Tongyun and its disadvantages on planning routes are analyzed. It is necessary for the company to have a logistics system which can plan routes with Artificial Bee Colony. On this basis, the main features of vehicles task information, vehicle scheduling and vehicle tracking are discussed. And the core process of freight arrival, freight delivery scheduling and freight reception scheduling are identified. Based on the requirements analysis, the system framework is designed. And vehicle delivery information, vehicle routes plan and vehicle monitoring are designed in detail. How to plan routes with Artificial Bee Colony is discussed especially. Finally, the benefit and the feature of the system are summarized, and the prospect of the system is discussed.Key words Swarm Intelligence ,Artificial Bee Colony, Routes Planning, Logistics Distribution System, Freight Distribution基于人工蜂群算法的物流配送系统设计 第一章 引 言第一章 引 言随着电子商务在我国的快速兴起，我国的快递行业得到了迅猛的发展。2011年我国快递业务量就已经位居世界第三。而到了2013年，我国的快递业务量就超越了美日两国，达到了92.9亿件，成为了快件量第一大国，快件收入也达到了1442亿元。这期间仅仅花费了两年时间1, 2。在这个快速发展的行业当中，民营快递行业以其成本优势在快递市场上获得了一席之地，与外企国企在快递市场上同台竞争。快递在货物量巨大的同时，对时间和安全也有一定要求。它需要在整个快递环节中频繁地传递大量信息。因此，快递必须依靠信息系统。如果没有信息系统，一个公司是无法参与快递行业的。因此快递行业的企业无论大小，基本上都有信息系统平台，通过平台对信息进行管理。很多信息系统平台的发展却并不够成熟，还单纯地局限于由信息平台来进行各种信息的增删改查上面，并不能够对系统内部所存储的信息进行处理，将其用在日常业务的规划预测上。车辆配送快件就是很多公司缺少规划的环节。对车辆路径进行科学合理的规划，有助于降低公司运营成本，提高效率。因此建设一个能够规划车辆路径的物流配送系统，有助于企业保持成本优势，提高企业竞争力，值得企业研究。1.1 车辆路径规划问题的研究现状车辆对货物进行配送是一个快递公司业务运作中的重要环节。科学合理地对车辆路径进行规划可以有效减少配送时间，降低配送成本。车辆路径规划问题（Vehicle Routing Problem,VRP）是一个经典的NP Hard问题3，最早由Dantzing和Ramser在1959年提出，他们基于线性规划对车辆路径进行了优化4。由于问题涉及到了统筹学和组合优化领域，一经提出就引起了很多学科专家的兴趣，一直是这两个领域的前沿问题。问题一般可定义为：对一系列的装货点或者卸货点，组织适当的行车路径，使车辆有序地通过它们，在满足一定的约束条件下，达到一定的目标。自被提出开始，车辆路径规划问题就被按照很多标准分类过。按照装卸任务不同，可分为装货问题、卸货问题以及装卸混合问题。按任务的特征分类，有对弧服务问题和对点服务问题以及混合问题。按车辆是否满载，可分为车辆满载问题和非满载问题。按车辆类型分可分为单车型问题和多车型问题。按车辆是否返回配送中心，分为不返回配送中心以及返回配送中心问题。按配送中心数量分，可分为单配送中心问题与多配送中心问题。按已知信息的特征分类为静态问题和动态问题等等5。经过多年研究，由于问题分类或是角度的不同，不同研究者对车辆路径规划这种整数规划问题，提出了不同的数学模型，尝试用各种不同的算法来获得这个问题的最优解或是较优解。一般而言这些算法可分为两类：精确算法（exact algorithm）和启发式算法（heuristic algorithm）。 （1）精确算法精确算法即通过严格的数学证明和推导的求解步骤来得出可行解，从理论上讲可以获得最优解。但精确算法的问题在于对于VRP这种典型的NP Hard问题很难避免指数爆炸，只适合于小规模的问题，对于大规模问题就很难在有效时间内得到满意解。精确算法的目标是获得最优解，其解的质量要高于启发式算法，是车辆路径规划问题研究初期所重视的研究方向。精确算法有分枝定界法和动态规划法等。分支定界法由Laporte在1986年首先提出。分支定界法基于分而治之的原则，将问题分解为多个子问题，求解子问题的最优解。Lee等人则通过建立动态规划模型搜索最短路径6。总体而言由于精确算法的求解时间太长，面对车辆路径规划问题的指数爆炸现象时无能为力，近几年来已非研究重点。（2）启发式算法启发式算法并不要求最优解，它尝试通过改进初始解或是全局搜索来获得较优解。一般启发式算法可分为传统启发式算法（classic-heuristic algorithm）和元启发式算法（meta-heuristic algorithm）两种。由于仅需要获得较优解。启发式算法能够在有效时间内获得满意解6。传统启发式算法的做法一般分为两种。一种是基于直观或者经验来将还未安排的任务点插入已经构造的路径中去，被叫做构造型启发式算法。构造型启发式算法比较经典的有插入算法、C-W节约算法、先对节点聚类后进行路径规划的算法以及先路径规划后将路径分割的算法。另一种则是从一个可行初始解出发，始终通过不断地局部扰乱或是调整来尝试获得更优解，被叫做改进型启发式算法，比较常用的有Petal算法、 Sweep算法和Or-Opt交换算法等6。由于传统启发式算法仅仅要求获得较优解，免除了严格的数学步骤计算，因此求解时间的大大减少，但由于其往往从一个初始解出发，通过既定策略对初始解进行优化，因此其并行性不高，全局搜索能力不强。元启发式算法又可以叫智能优化算法，是一种模拟自然界过程、生物行为或者人脑思考模式的算法。它的主要特征是通过全局搜索来获得解。它为求解车辆路径规划问题提供了新方向。随着人工智能领域研究热度的不断上升，元启发式算法已经成为了车辆路径规划问题的主要研究方向。元启发式算法本质上是一种随机搜索算法，它对问题的数学描述不要求可凸性等条件。而且算法不是依靠单一的初始解而是从多个解构成的种群出发。因此元启发式算法的全局搜索能力强、通用性强，适于并行处理，非常适合用来求解复杂的应用问题。下面介绍三种元启发式算法：遗传算法、粒子群算法以及人工蜂群算法。遗传算法由J. Holland于1975年首先提出的，是一种通过模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程来在解空间中搜索最优解的方法。它使用种群代表一组解，每个解又被称为染色体。算法通过通过种群中染色体间的两两配对交叉以及染色体的自身变异等遗传操作生成新的种群，在经历过一定的迭代代数后，输出当前种群中的最优解作为算法的解。遗传算法最早由J. Lawrence用于解决带时间窗的车辆路径规划问题。经过多年的研究，很多学者对遗传算法进行了改进。戴树贵等通过在路径中已有的相邻客户间，按极角顺序插入位置处于这两个客户间的客户以及使用2-OPT优化算法优化路径这两种做法，来提高遗传算法的局部搜索能力。田景文等通过将BP神经网络与遗传算法相结合的方式来解决车辆路径规划问题，克服了遗传算法局部搜索能力差，易早熟，总体可行解质量不高的问题6。粒子群算法最早由Kennedy和Eberhart于1995年提出。它模拟鸟群觅食中迁徙和聚集的过程。每个备选解被称为粒子，多个粒子共存合作寻优。每个粒子根据自身历史中最优解以及相邻粒子群的最优解，在解空间中寻找更好的位置，搜索最优解。它基于个体组成的群落和个体间的交互来获得最优解，具有收敛性快和健壮性高的特点。李宁等人尝试通过粒子群算法求解带有时间窗的车辆路径问题，设计了粒子构造方法，和算法过程，并分析了粒子群算法相对与其它演化算法的优势。徐杰等人设计了一种混合粒子群算法来解多目标车辆路径规划问题，通过引入变异算子避免算法收敛到非劣最优解集，改进了粒子群算法。王华东等人通过对粒子群算法的惯性权重进行动态修改，使得粒子群算法能够跳出局部最优解，避免了早熟，可以得到全局最优的结果并加快其搜索速度6。人工蜂群算法（Artificial Bee Colony，ABC）最早由Karaboga D在2005年提出。算法模拟了蜂群的觅食过程，是一种基于群体智能的非数值优化算法，全局寻优能力强。算法通过引领蜂、观察蜂以及侦查蜂三种角色的分工协作来寻找最优蜜源也就是最优解。每个解都相当于一个食物源。食物源的收益率越高就代表着解的质量越高，越能吸引蜜蜂。通过不断迭代最终获得最优解。王连稳等人通过人工蜂群算法求解随机需求的车辆路径规划问题。苏晓勤等人通过2-OPT改进了人工蜂群算法，并通过改进的人工蜂群算法求解旅行商问题。王志刚等人给出了车辆路径问题中的食物源编码方式，然后通过人工蜂群算法求解车辆路径规划问题。作为一种新兴的算法，人工蜂群算法收敛速度快，全局搜索能力强，但其操作都为实数操作，需要一个好的编码方案将其离散化，从而用于解决车辆路径调度问题。作为一家早期建立的中型快递公司，通韵公司从很早就开始逐步建立了自己的物流信息平台。从开始单纯的车辆和人员的信息管理系统，到成为一个可以全程跟踪车辆，实时反馈车辆状态，集信息管理，车辆调度，车辆监控于一身的综合型物流配送系统。系统很好地为公司的日常配送业务提供了技术支持，为广大客户提供了方便快捷的服务。尽管物流配送系统所能提供的功能已经很多，所支持的环节也很复杂，物流配送系统本身依然局限于对信息的增删改查上面，并不能对系统本身掌握的信息进行一个很好地分析处理，缺乏智能化。车辆路径规划管理就是一个很欠缺的方面，通韵公司仍然还在依靠人工进行路径管理。随着竞争的日益激烈和业务的不断发展，人工规划管理已经很难满足公司在时间和成本上的要求，因此公司急需使得物流配送系统具备路径规划管理功能。1.2 通韵物流配送系统路径管理存在的问题通韵公司的调度中心在管理车辆路径时所需要考虑的因素很多。首先，每个客户点所需要完成的业务量每天都在发生变化。客户点和客户点间的业务量也并不相同，业务量分布不均匀。其次，配送车辆的数量多，型号多，载重各有不同。车辆报废或是添置新的车辆也使得车队规模处于不断变化中。调度中心在调度协调这些车辆的任务时耗费了大量精力。最后，由于客户点多，客户点间的车辆路径可行方案有很多。调度中心难以在短时间内敲定车辆路径方案。调度中心一般都是通过人工统计，计算各个客户点的业务量历史均值，然后将彼此距离近的客户点划分为一个分区将其分配给某辆车，由该辆车提供分区内部的配送与取货服务。分区总的业务量接近所分配车辆的载重上限。至于分区中配送车辆的行驶路径则交由快递员自己决定，调度中心只负责配送任务和取货任务的下达。这种分区划分形式的管理方式并不科学。由于实际车辆数，客户点的实际业务量都时刻处在变动中。划定分区时，调度中心无法对其进行全盘考虑，只能通过留有余量来应对。而对于快递员来说，常常要面对诸如道路拥堵，调度中心下达取货任务等情况，需要不断地调整自己的车辆路径，造成其车辆路径缺乏统筹规划，导致了配送成本浪费。这种基于历史数据，仅仅对客户点进行简单聚类，将其划分为一个个的分区，由快递员自己根据客户点距离远近来决定路径的管理方式主要存在如下问题：（1） 路径管理对配送车辆利用率不高由于配送车辆的配置是基于历史数据的均值来进行的。那么为了满足日常业务中业务数量的变动，在调度中心划定分区时是留有余量的。如果实际业务中的数量超过了预期的数量，就会使得配送车辆需要多跑一轮或是临时调配其他车辆来完成。而如果远远低于预期数量，又会大大增加配送车辆的空载率。而客户点的业务量每天都在发生变化。调度中心很难找到一个适中的余量值来达到两者兼顾的要求。配送车辆利用率不高的问题会导致配送成本的上升。（2） 路径管理难以应对业务变动中国的快递市场处于迅猛的发展中。公司的业务发展也很迅速。客户点数量和客户点的业务量常常发生变化，需要经常调整。而且还会遇到类似有配送车辆损坏，配送车辆需要临时变动等突发情况。由于路径管理自身基本是由人工完成的。如果要调整车辆路径，就需要重新统计客户点信息，划分分区，更新分区信息。这需要花费大量的时间和精力。因此频繁调整车辆路径，以应对业务变动并不实用。（3） 路径管理很难支持取货需求与配送需求不同，取货需求常常是在车辆配送途中发生的。无论是调度中心还是快递员都无法在开始配送时，将其考虑进去。因此车辆在配送途中的车辆路径是要发生变化的。但是车辆的路径是由快递员自己决定的。调度中心在取货需求出现时，无法完全把握配送车辆的状态，并不清楚车辆正在驶往哪个客户点，后续的完整路径又会经过哪些客户点，不能帮助快递员调整后续路径，只能够将取货任务下达给快递员，由快递员自己调整。要解决这些问题，就需要建立一个物流配送信息系统，基于实时业务数据，GIS数据，车辆信息数据等各项数据，通过人工蜂群算法，科学合理地管理安排车辆路径。本文就构建了一个基于人工蜂群算法进行路径管理的物流配送系统。系统通过系统内部的各项数据信息，对车辆路径进行实时调整。提高车辆的利用率，避免配送车辆超载或是空载的情况发生。系统能够应对业务变动，迅速调整路径方案以适应业务需求。在出现取货需求时，调度中心可以把握车辆的后续路径，车辆实时状态等信息，基于这些信息，将取货点插入车辆原有路径中去，生成新的路径，并通知快递员。1.3 本文的主要内容车辆配送环节作为每个快递公司的都有的环节，如果能够对其路径进行优化可以大大降低公司成本，提高公司竞争优势。车辆路径规划问题作为最早在1959年提出经典NP Hard问题，一经提出就吸引了众多学者的目光。不同研究者按照不同的角度对车辆路径规划问题进行了扩展和分类。一般而言要解决车辆路径规划问题，算法分为精确算法和启发式算法两种。精确算法可以得到最优解但是难以避免指数爆炸的情况，无法用于大规模运算，近几年来很少有人研究。启发式算法又可分为传统启发式算法和元启发式算法。传统启发式算法分为构造型启发式算法和改进型启发式算法。其往往从一个初始解出发，导致其并行性和全局搜索能力不强。元启发式算法通过模拟自然界过程、生物行为或者人脑思考模式对问题的解空间进行全局搜索。元启发式算法从一个种群出发，其全局搜索能力强，适于并行计算，易于实现，适合解决大型复杂类型的问题，已经是车辆路径问题研究的主要方向。人工蜂群算法作为新兴的元启发式算法，以其收敛速度块，全局搜索能力强的特点被选为系统的车辆路径规划算法。在群体智能中，群体内部的个体的智能是十分有限的，所遵循的规则也很简单。整个群体的控制是呈分布式的，而非集中式的。这使得群体智能能够适应网络环境的工作状态，具有良好的健壮性，灵活性。并且由于个体简单，算法本身也易于实现。之所以群体能够在宏观上表现出有序性，学习性，适应性等智能特性，产生涌现现象，都有赖于群体内部简单个体间的联系。而这种联系是建立在群体智能的自组织性和劳动分工的两大特征上的。蜂群具有群体智能的两大特征，内部个体间可以相互联系，相互影响。因此蜂群具有群体智能。人工蜂群算法通过模仿蜂群的采蜜行为，将整个过程分为初始化阶段，引领蜂阶段，观察蜂阶段以及侦查蜂阶段，在经过这几个阶段的多次迭代后，使得人工蜂群算法可以获得最优解。通韵物流配送系统的面向用户多，机构多，因此功能点也多，本文通过分析将功能点划分为了三个主要功能模块：车辆任务信息维护模块、车辆调度管理模块以及车辆追踪管理模块。随后，本文分析确定了通韵物流配送系统的的配送货物到站流程，货物配送调度流程以及快件收取调度流程三个核心流程。本文对各类用户在配送各个环节上的不同需求进行了描述，并详细说明了系统的安全需求。在需求分析的结果之上，本文设计了整个系统的架构。整个系统采用基于面向服务的架构，以满足系统服务灵活扩展的需求。系统的核心系统被划分为了车辆配送基础信息管理子系统、车辆路径规划子系统以及车辆实时监控子系统。车辆配送基础信息管理子系统负责维护路径规划时所需的基础信息，包含客户预约管理、货物仓储管理以及配送机构信息管理。车辆路径规划子系统则主要负责的是对车辆路径进行规划，包含有车辆行驶区域限制，基于人工蜂群算法的静态路径优化和启发式动态路径调整。车辆实时监控子系统可以对在途车辆进行监控，包括车辆载货信息管理，车辆在途状态管理以及车辆历史路径管理。本文重点介绍了如何使用人工蜂群算法对车辆的路径进行规划，并做了仿真实验，证明人工蜂群算法的可行性。本文还将通韵物流配送系统与同类系统进行了对比分析，简要介绍了系统的应用结果，最后总结归纳了通韵物流配送系统的特点和不足，展望了系统发展的下一步前景。1.4 本文的篇章结构本文共分五章。本文首先简要介绍了路径规划问题的研究背景，引出了本文的主要工作内容，分析了通韵公司在路径规划管理上所面临的问题和不足。然后对路径规划的人工蜂群算法进行了介绍，接着对整个物流配送系统进行功能划分，确定了核心业务流程。在此基础上，对系统进行了整体架构设计，并对核心子系统进行了详细设计。最后归纳总结了系统的特色，分析了系统的不足之处，展望了下一步研究的方向。详细内容如下：第一章首先简要介绍了路径规划问题的研究现状。由此引出了本文工作的主要内容，即要想保持成本优势，通韵公司必须解决自己管理车辆路径依赖人工管理所造成的问题。由此突出了本文的现实意义。第二章介绍了群体智能的特征，以此分析人工蜂群算法的基本特点，最后介绍了人工蜂群算法的具体步骤。人工蜂群算法作为物流配送系统中规划路径的主要算法，是本文的基础和重点研究方向。第三章对通韵物流配送系统有关路径规划的方面进行了需求分析，讨论了功能框架，介绍了各个功能模块，并在此基础上画出了用例图，最后分析确定了系统的核心业务的流程。第四章则基于第三章的需求分析对系统的整体架构进行了设计，对与路径规划相关的车辆配送基础信息管理子系统、车辆路径规划子系统以及车辆实时监控子系统进行了详细设计，并与同类系统进行了对比，介绍了系统应用情况。第五章对本文的工作内容进行了总结和归纳。分析了系统的特色，指出了不足，对系统下一步的发展进行了展望。7基于人工蜂群算法的物流配送系统设计 第二章 人工蜂群算法基础第二章 人工蜂群算法基础人们很早就发现自然界存在着一种神奇的现象：在一个生物群落中，单个个体的智力十分低下，但是整个生物群落却表现出了高度的智能性和组织性。蜜蜂就是一个很典型的例子，单个蜜蜂的智力有限，但是通过蜜蜂和蜜蜂间的信息传递，整个蜂群却能够完成很复杂的活动，体现出了优秀的智能性和组织性。这就引起了人们的兴趣，如果能够将这种原理应用到实际问题中，就可以通过较为简单的算法，来求解复杂问题。群体智能算法由此应运而生。蜜蜂是一种高度社会化的生物，在蜂群内部各种类型的蜜蜂有着严密的社会分工以完成复杂的活动。很多学者都对它的各种行为模式进行了研究，以期望能够通过模仿这种行为来解决复杂问题。经过研究，蜂群的很多行为被借鉴到了算法中，来解决实际问题，都取得了不错的效果，有模仿蜜蜂哺育幼虫的9，也有通过模仿蜂群繁殖的蜂群进化遗传算法（Bee Evolutionary Genetic Algorithm，BEGA）10。这里介绍的是人工蜂群算法。人工蜂群算法通过模拟蜂群的采蜜行为来求解问题。最早由Karaboga D在2005年提出，参考了由Tereshko和Loengarov提出的蜂群采蜜模型11。人工蜂群算法具有收敛速度快，参数少，操作简单，容易实现的优点，一经提出就吸引了很多人的注意。2.1 群体智能算法群体智能（Swarm Intelligence）作为一个新兴的领域，从80年代被提出开始，就一直是各个学科研究人员研究的热点和前沿领域。大量简单个体组成的群体合作完成原本需要由单个复杂个体完成的任务。而前者比后者往往更有健壮性，而且易于实现。群体智能一般分为如下两种:由一群简单的智能体（Agent）涌现出来的集体的智能（Collective Intelligence）12，或是将群体中的个体看作粒子而非智能体。前者以蚁群算法(Ant Colony Optimization，ACO)为代表，人工蜂群算法也是属于这类，而后者则以粒子群算法(Particle Swarm Optimization，PSO)为代表。群体智能将群体内部的成员看成是简单单一的个体，每个个体可以拥有学习能力，合作完成复杂任务，解决具体问题。群体智能采用的是分布式控制，不存在集中控制，也没有全局模型。因此它适合网络环境下的工作状态，拥有良好的健壮性。一个或几个个体的故障不会影响到这个群体的解的质量。整个群体智能的智能主体在求解问题的过程中，体现出了自身的自主性、反应性、学习性和自适应性等智能特性。虽然群体体现出了智能特性，但并不意味着群体中的个体智能十分高超。相反，群体智能中的个体的能力或是所需要遵循的规则必须十分简单，这才使得群体智能易于实现。整个群体智能的复杂的智能行为需要依靠群体中简单个体的相互交互来体现。群体的复杂智能体现出了群体智能在宏观上的有序性。这种大量个体协作体现出的宏观有序性被称为涌现现象。对于群体智能而言，仅仅研究个体的行为不可能了解群体的情况，单独研究个体性质也无法研究群体的整体性质。因此对涌现现象的研究必须既研究各个个体，又研究各个个体间的联系13。可以这么说群体智能的核心机制是简单个体是凭借局部联系来产生群体行为14。而这种联系是建立在群体的两个重要特征，自组织性（Self-Organization）以及劳动分工（Division Of Labor）上的。自组织性一般而言体现在如下几个方面：（1） 正反馈，群体之中的每个简单个体会通过遵循群体中已有的结构或者信息来决定自己的行动，表现出某种行为，并且个体自身会释放出某种信息素。这种信息素又会指引其它个体。从而使得某种行为通过这种不断的反馈刺激来得到了加强。大量群体中的个体依照这种正反馈刺激的指引，追随某些个体一开始的随机行为，使得群体在整体上呈现出一种结构。这是群体的学习能力的体现，其呈现出来的结构能够促进和加强群体适应环境。（2） 负反馈，如果某种正反馈所造成的行为或是结构与现实要求或是约束产生了偏差，那就需要用到负反馈来平衡正反馈，消除这种偏差。负反馈使得整个群体能够保证稳定。例如为了避免对某种资源消耗过度，那么在资源过少时，需要用到负反馈来降低因为正反馈而造成的对该种资源的采集行为。由此可见通过负反馈机制控制群体行为对于管理群体及其资源来讲是至关重要的。（3） 变动，群体中某些个体的随机行为，例如随机的位置变动，误差或是任务变换等。这些随机行为在发生时并不影响群体的整体行为。但这些行为如果发现了可以更加适应环境的新结构，那么通过个体间的联系，就能由正反馈机制来加强这种结构，从而打破现有结构。这种随机性非常重要，它确保了群体在不断寻找新结构当中，促进了群体行为结构的进化。在算法中，就能够确保整个算法在持续搜索和引入新的解，由现有解向最优解收敛。（4） 多重交互，群体中的个体之间存在着多重交互的关系。通过多重交互，个体用来向其他个体接收或是发送信息，实现信息共享，从而使得信息能够遍布整个群体。与个体间的直接接触相比，更为神奇的是个体间的“间接接触”又被可称作“共识主动性”（Stigmergy）。在这种机制下，群体中的个体感知环境后做出相应的反应，而这种反应又会作用于环境，通常情况下这种机制是由各种各样的信息素来体现的。Grass首先提出了Stigmergy机制，并用它来解释白蚁如何在筑巢任务中的相互协作15。Stigmergy机制能够在宏观上将个体行为和群体行为联系起来。个体行为作用于环境，使得环境产生变化，进而作用于其他个体，使其行为发生变化。通过这种个体和环境之间的相互作用，使得个体和个体间可以产生联系，进而协作完成任务。换句话说，个体和个体间通过环境这个媒介相互交流交互。由于不是直接联系，避免了个体和个体间的直接接触，使得群体在个体数目增幅程度很大的情况下，其通信开销增幅却很小。也因此在群体进行的各种任务中，Stigmergy机制都是群体中个体之间必要的通信机制。除了自组织外，拥有智能的群体还有个重要特征。群体中某些类别的个体需要执行一些专门的任务。不同类别的个体执行不同的任务，分工协作一起完成复杂的任务。这被称作劳动分工。通过将任务分类，然后将任务分配给特定类别的个体，有效地降低单个个体的复杂程度，使得个体无需具备复杂的智能，保证了个体的易于实现。2.2 人工蜂群算法蜜蜂是一种典型的社会化昆虫。单个个体的智能有限，但是通过担任不同角色的蜜蜂间进行分工协作，整个蜂群在采蜜过程中表现出了惊人的智慧。人工蜂群算法就是通过对蜂群采蜜行为的模仿来搜索最优的蜜源也就是最优解17。人工蜂群算法的组成部分有三个，分别为食物源，蜜蜂角色以及行为模式。这三个部分共同组成了完整的人工蜂群算法。下面就对它们一一介绍。（1）食物源食物源（Food Sources）代表的是可行解。每个食物源的位置都代表着一个可行解。对于蜂群来讲每个食物源都有其价值18。在自然界中每个食物源的价值是由很多因素共同决定的，例如食物源离蜂巢距离远近，食物源所含花蜜多少，食物源采蜜的难易等。对于人工蜂群算法而言，食物源的价值可由食物源的收益率（Profitability）也就是食物源代表的解的适应度来决定。收益率越高的食物源其代表的解也就越靠近最优解。根据食物源收益率的高低，食物源又可以分为富源（Rich Food Sources）和贫源（Poor Food Sources）。（2）蜜蜂角色蜂群按照其角色不同可以分为雇佣蜂（Employed Bees）和非雇佣蜂（Unemployed Bees）。雇佣蜂又被叫做引领蜂与正在被采集的食物源相对应。雇佣蜂在完成采蜜后，回到蜂巢，在舞蹈区通过跳舞向蜂群反馈食物源相关信息（如距离、方向和收益率等）。蜂巢内的其它蜜蜂按照一定的概率接收这些信息。非雇佣蜂主要用来发现和开采食物源。非雇佣蜂又可以分为观察蜂（Onlookers）和侦查蜂（Scouts）。观察蜂在舞蹈区观察引领蜂分享的食物源信息，按照一定概率接收，如果接收到信息就前往该食物源采蜜。侦查蜂则用于搜索新的食物源19。引领蜂可以保存较好的食物源，具有精英作用，而观察蜂则起到了加速算法收敛于较好的食物源上的作用20。（3）行为模式蜂群的行为模式可分为三种：搜索食物源、招募观察蜂前往采蜜以及放弃食物源21。搜索食物源主要是进行寻找新的食物源的活动。如果食物源是富源，由于蜂群倾向于采集富源，因此富源会产生正反馈，招募更多的观察蜂前往采蜜。而如果食物源是贫源，则通常会产生负反馈，导致蜂群放弃该食物源22。蜜蜂间相互交换信息是蜂群在整个采蜜过程中形成群体智能最重要的一步。引领蜂主要在蜂巢前的舞蹈区内完成信息的交互。引领蜂通过在舞蹈区进行摇摆舞来传递有关食物源质量的信息。舞蹈时间与食物源的质量成正比。质量越高，舞蹈时间越长。每个观察蜂在舞蹈区能够观察大量的舞蹈信息，并根据舞蹈信息所表达的食物源质量高低来选择食物源，前去采蜜。食物源质量越高，被观察蜂选到的几率就越大，就能吸引到更多的蜜蜂前去采蜜。引领蜂、观察蜂、侦查蜂的分工协作完成采蜜行为表明蜂群具有了劳动分工的特征。而蜂群也表现出了自组织性的四个特性。正反馈促使大量的观察蜂聚集在价值高的食物源处。而负反馈则使得当蜜蜂面对价值低的食物源中时，停止采蜜，寻找新的食物源。变动表现在侦查蜂寻找新的食物源是一个随机搜索的过程。多重交互则体现在引领蜂在蜂巢中通过摇摆舞向观察蜂传递有关食物源的信息。这使得蜂群满足群体内部个体可以进行联系，相互影响的条件。由此可见，蜂群是一个具有群体智能的生物群体。人工蜂群算法可以用来解决实际问题。2.3 人工蜂群算法的基本流程作为一种迭代算法，人工蜂