多智能体协同进化算法及其在物流配送中的应用，本文主要内容关键词为：体协论文,算法论文,物流配送论文,智能论文，此文献不代表本站观点，内容供学术参考，文章仅供参考阅读下载。
如何运用进化算法解决社会生活中的各类问题已成为管理科学、运筹学、系统工程和计算机科学的研究课题，其原因在于进化算法是一种强有力的、应用范围十分广泛的随机搜索优化技术，它对许多传统方法难以解决的问题非常有效。在大多数优化问题中，常常都带有复杂的约束条件，简单的进化算法不能有效的解决这类优化问题。因此，结合具体问题的特性研究新算法就成为进化算法研究的热点。协同进化算法是近年来计算智能研究的一个热点，将单一种群推广到多个种群，进而建立个体或种群之间的竞争、合作关系，使之适应复杂系统的动态进化环境，以达到种群优化的目标。协同进化算法与一般的进化算法的根本差别在于它的进化过程，在协同进化中，一个个体的适应度的计算是在与其它个体的交互过程中进行的，依赖于不同的问题，交互伙伴可以是同一种群的个体或者是不同种群的个体。
混合策略协同进化算法属于协同进化算法的一种改进形式，它研究适应度（值）互相耦合的两个或多个种群的同时进化。目前进化算法研究的一种趋势是不断地提出新的搜索策略，然后在一些测试问题集合上进行试验，从而说明新策略的效果比原有搜索策略好。每个策略都只适用于某一特定问题集，没有一种策略能成功的解决所有问题。通过利用混合策略的方式集成现有算法研究中的不同策略，有可能改进现有算法的效率。本论文的目标是集成现有算法中的几种优势策略，利用混合策略的思想结合具体问题设计多智能体协同进化算法，来提高算法的性能，并通过相关实验来验证我们提出方法的可行性。
1 多智能体协同进化算法
本章主要说明本文的多智能体协同进化算法的详细设计过程。包括：（1）多智能体协同进化算法的优化框架；（2）多种群间的竞争机制；（3）多种群间的共享机制。
1.1 多智能体协同进化算法的优化框架
在自然界中，不同地域的生物有不同的特点和进化程度，从大自然中争取资源为己所用；另外，这些生物之间又通过信息交换、取长补短、共同进步。本文提出的多种群协同优化方法是借鉴自然界中的这一现象设计出来的。整个算法由计算环境中的多个普通种群和一个优良种群构成，各个普通种群进行竞争，从计算环境中得到计算资源；一旦某个种群获得计算资源，它便进行一次自己的进化进程。各个普通种群将进化得到的优良个体贡献出来，组成优良种群，普通种群可以从中获取优良个体，以改善本种群的品质。在本文的多智能体协同进化算法中，每个智能体对应于一个种群，多个智能体对应于多个不同的种群；这些不同的种群均采用不同的进化方法和参数设置推进各自的进化进程，同时这些不同的种群又通过相互的资源竞争、信息共享及自学习能力，共同推动着整体算法的进化进程。
本文多智能体协同进化算法的优化框架如图1所示。图1中的每个种群就对应于一个智能体，每类进化算法对应于采用不同参数设置的一种进化算法。如遗传算法的A、B、C、D类；蚁群算法的A、B、C、D类。在多智能体协同进化算法中，主要通过各种不同的遗传算法和蚁群算法来完成各个普通种群的进化。各种遗传算法（蚁群算法）的不同，可以体现在进化机制、优化算子和控制参数等方面的差异。图2描述了多智能体协同进化算法的具体执行流程。
1.2 多种群间的竞争方法
在多群体优化方法中，种群的竞争力取决于种群的最佳适应度值和成长性这两个因素，竞争力强的种群将有较大的获得计算资源的概率。在寻找最大适应度值时，当一个种群的最佳适应度值较小时，表明该种群仍处于进化进程的初始阶段，距离最优解较远，应将资源较多地分配给距离最优解较近的种群；另一方面，当一个种群再无成长性或成长性较差时，如果该种群还没有达到最优解，表明它可能出现早熟现象，趋于局部最优，这时将资源较多地分配给成长性好的种群；这样，一个最佳适应度值大同时成长性好的种群将优先获得计算资源分配。种群的成长性可定义为：
1.3 多种群间的共享机制
信息不对称的核心在于信息资源使用的差异。信息资源有许多不同于物质资源的特性，最重要的一点就是它的共享性。信息资源的共享常常是双向的，信息的提供者同时也是信息的获取者。信息资源的可交互性使信息的共享在交互的过程中不断升值，最终使所有的参与者都从共享中得到最大的收益。在本文的多智能体协同进化算法中，笔者模拟这种社会现象，构建了优良种群和普通种群。优良种群由各个普通种群中适应度值较优的若干个个体组成，是一个优良种子库，供各种群的进化进程共享。
良种迁移：指普通种群在自己的进化进程中，直接从优良种群中引进若干优良个体代替本种群中的较劣个体。如果一个种群采用遗传算法进行进化，这里的良种迁移就是指直接从优良种群中引进若干优良个体代替本种群中的较劣个体，然后再进行后续的选择、交叉和变异操作。如果一个种群采用蚁群算法进行进化，这里的良种迁移就是指直接从优良种群中引进若干优良个体代替本种群中的较劣个体，然后再进行信息素的更新。
良种交叉：普通种群在自己的进化进程中，从优良种群中选取若干优良种子个体和普通种群中的个体进行交叉繁殖，用交叉生成的较优个体取代普通种群中原来的个体。良种交叉策略只用在采用遗传算法进行进化的种群中。如果一个种群采用遗传算法进行进化，那么进化过程中的选择操作、变异操作保持不变，交叉操作时，从优良种群中选取若干优良种子个体和普通种群中的个体进行交叉繁殖，用交叉生成的较优个体取代普通种群中原来的个体。
2 MACA在物流配送中的应用
设物流中心和20个客户分布在一个边长为25km的正方形地域内，每个客户的货物需求量和供应量均不超过2.5吨，物流中心有10台配送车辆，车辆的最大载重量均为10吨，车辆一次配送的最大行驶距离均为62.5千米。笔者利用计算机随机产生了物流中心和20个客户的位置坐标以及各客户的货物需求量和供应量，其中物流中心的坐标为（4.0km，17.63km），20个客户的坐标及其货物需求量和供应量见表1。在上述已知条件的基础上，笔者又用计算机随机产生了20个客户的需求时间窗和供应时间窗（见表2）。设配送车辆在配送过程中的平均行驶速度为20km／h，配送车辆在客户处的装货和卸货时间不计。要求根据上述条件，合理安排车辆的配送路线，使配送的总里程最短。
在求解这个实例时，需要通过拆分客户的方法，将原来包括20个客户的两个时间窗口问题转化为一个包括40个客户的单个时间窗口问题。转化为单个时间窗口问题后，客户1－20表示需求客户，其位置、货物需求量、需求时间窗分别取原问题中客户1－20的位置、货物需求量和需求时间窗，其货物供应量均为0；客户21－40表示供应客户，其位置、货物供应量、供应时间窗分别取原问题中客户1－20的位置、货物供应量和供应时间窗，其货物需求量均为0；根据物流中心与客户的坐标，可以计算出物流中心与客户之间及客户相互之间的直线距离，再根据配送车辆的平均行驶速度就可以计算出配送车辆在物流中心与客户之间以及在各客户间的行驶时间。这样处理后就可以利用本文的多智能体协同进化算法对该实例进行求解。
为了消除优化过程中的随机性，笔者采用多智能体协同进化算法对本实例随机求解10次，得到的计算结果如表3所示。从表3中可以看出：用多智能体协同进化算法对本实例的10次求解中，都得到了质量较高的解，其配送的总距离的平均值为202.89千米，平均使用的车辆数为5.4辆，比已知条件平均节省4.6辆车。其中第4次得到的解的质量最高，其配送里程为190.63千米，该方案对应的六条配送路径分别为：
路径1：0－8－28－13－19－39－22－16－36－4－5－0；
路径2：0－14－6－15－35－26－0；
路径3：0－9－29－38－18－34－0；
路径4：0－33－25－24－37－17－2－3－23－10－30－11－31－0；
路径5：0－32－12－0；
路径6：0－40－20－21－1－7－27－0。
上述各路径中的客户序号是客户拆分以后的单个时间窗口问题的客户序号，根据客户拆分的规则，可将上述路径中的客户序号还原为原问题中的客户序号。下面仅以路径1来进行说明之：对应原问题，路径1表示配送车辆从物流中心出发，先到客户8送货并取货，再到客户13送货，再到客户19送货并取货，再到客户2取货，再到客户16送货并取货，再到客户4送货，再到客户5送货，最后回到物流中心。根据上述配送路径方案和问题的时间窗口约束条件，可以进一步得到各台配送车辆的行车时间安排。多智能体协同进化算法的计算结果也较稳定，10次求解中，最差解的配送里程比最优解多14.0％。从计算效率看，10次求解的平均计算时间为11.83秒，计算效率较高。通过以上实验计算可以看出：用多智能体协同进化算法求解第三方物流配送中的车辆路由问题，可以取得很好的计算结果，且算法的计算结果较稳定，计算效率也较高。
3 结束语
算法混合的思想已发展成为提高算法优化性能的一个重要而又有效的途径，其出发点就是使各种单一算法相互取长补短，产生更好的优化性能。在协同进化研究的基础上，本文提出了多智能体协同进化的思想。多智能体协同进化算法就是设计一种人工的进化博弈系统，使得系统的动力学满足一定的要求，使得系统达到一种策略的均衡。多智能体协同进化算法同传统的进化算法不同的地方是：在传统的进化算法中个体通常假定只使用一种固定的策略，而在多智能体协同进化算法中个体可以使用不同的策略，而且根据使用的效果可以进行动态调整。本文的研究工作从更宏观、更本质的角度模拟自然进化原理与机制，模拟生物智能的生成过程，使所设计的算法更具有所期望的某种特别性态。