多智能体协同进化算法及其在物流配送中的应用

      如何运用进化算法解决社会生活中的各类问题已成为管理科学、运筹学、系统工程和计算机科学的研究课题，其原因在于进化算法是一种强有力的、应用范围十分广泛的随机搜索优化技术，它对许多传统方法难以解决的问题非常有效。在大多数优化问题中，常常都带有复杂的约束条件，简单的进化算法不能有效的解决这类优化问题。因此，结合具体问题的特性研究新算法就成为进化算法研究的热点。协同进化算法是近年来计算智能研究的一个热点，将单一种群推广到多个种群，进而建立个体或种群之间的竞争、合作关系，使之适应复杂系统的动态进化环境，以达到种群优化的目标。协同进化算法与一般的进化算法的根本差别在于它的进化过程，在协同进化中，一个个体的适应度的计算是在与其它个体的交互过程中进行的，依赖于不同的问题，交互伙伴可以是同一种群的个体或者是不同种群的个体。

      混合策略协同进化算法属于协同进化算法的一种改进形式，它研究适应度（值）互相耦合的两个或多个种群的同时进化。目前进化算法研究的一种趋势是不断地提出新的搜索策略，然后在一些测试问题集合上进行试验，从而说明新策略的效果比原有搜索策略好。每个策略都只适用于某一特定问题集，没有一种策略能成功的解决所有问题。通过利用混合策略的方式集成现有算法研究中的不同策略，有可能改进现有算法的效率。本论文的目标是集成现有算法中的几种优势策略，利用混合策略的思想结合具体问题设计多智能体协同进化算法，来提高算法的性能，并通过相关实验来验证我们提出方法的可行性。

      1 多智能体协同进化算法

      本章主要说明本文的多智能体协同进化算法的详细设计过程。包括：（1）多智能体协同进化算法的优化框架；（2）多种群间的竞争机制；（3）多种群间的共享机制。

      1.1 多智能体协同进化算法的优化框架

      在自然界中，不同地域的生物有不同的特点和进化程度，从大自然中争取资源为己所用；另外，这些生物之间又通过信息交换、取长补短、共同进步。本文提出的多种群协同优化方法是借鉴自然界中的这一现象设计出来的。整个算法由计算环境中的多个普通种群和一个优良种群构成，各个普通种群进行竞争，从计算环境中得到计算资源；一旦某个种群获得计算资源，它便进行一次自己的进化进程。各个普通种群将进化得到的优良个体贡献出来，组成优良种群，普通种群可以从中获取优良个体，以改善本种群的品质。在本文的多智能体协同进化算法中，每个智能体对应于一个种群，多个智能体对应于多个不同的种群；这些不同的种群均采用不同的进化方法和参数设置推进各自的进化进程，同时这些不同的种群又通过相互的资源竞争、信息共享及自学习能力，共同推动着整体算法的进化进程。

      

      本文多智能体协同进化算法的优化框架如图1所示。图1中的每个种群就对应于一个智能体，每类进化算法对应于采用不同参数设置的一种进化算法。如遗传算法的A、B、C、D类；蚁群算法的A、B、C、D类。在多智能体协同进化算法中，主要通过各种不同的遗传算法和蚁群算法来完成各个普通种群的进化。各种遗传算法（蚁群算法）的不同，可以体现在进化机制、优化算子和控制参数等方面的差异。图2描述了多智能体协同进化算法的具体执行流程。

      1.2 多种群间的竞争方法

      在多群体优化方法中，种群的竞争力取决于种群的最佳适应度值和成长性这两个因素，竞争力强的种群将有较大的获得计算资源的概率。在寻找最大适应度值时，当一个种群的最佳适应度值较小时，表明该种群仍处于进化进程的初始阶段，距离最优解较远，应将资源较多地分配给距离最优解较近的种群；另一方面，当一个种群再无成长性或成长性较差时，如果该种群还没有达到最优解，表明它可能出现早熟现象，趋于局部最优，这时将资源较多地分配给成长性好的种群；这样，一个最佳适应度值大同时成长性好的种群将优先获得计算资源分配。种群的成长性可定义为：

      

      

      1.3 多种群间的共享机制

      信息不对称的核心在于信息资源使用的差异。信息资源有许多不同于物质资源的特性，最重要的一点就是它的共享性。信息资源的共享常常是双向的，信息的提供者同时也是信息的获取者。信息资源的可交互性使信息的共享在交互的过程中不断升值，最终使所有的参与者都从共享中得到最大的收益。在本文的多智能体协同进化算法中，笔者模拟这种社会现象，构建了优良种群和普通种群。优良种群由各个普通种群中适应度值较优的若干个个体组成，是一个优良种子库，供各种群的进化进程共享。

      良种迁移：指普通种群在自己的进化进程中，直接从优良种群中引进若干优良个体代替本种群中的较劣个体。如果一个种群采用遗传算法进行进化，这里的良种迁移就是指直接从优良种群中引进若干优良个体代替本种群中的较劣个体，然后再进行后续的选择、交叉和变异操作。如果一个种群采用蚁群算法进行进化，这里的良种迁移就是指直接从优良种群中引进若干优良个体代替本种群中的较劣个体，然后再进行信息素的更新。