资料：多种群蚁群算法

1、X,双（多）蚁群算法上一章已介绍了多种改进的蚁群算法，均是基于单种群的蚁群算法优化，而对蚁群算法的优化可从另一角度进行一一双（多）种群蚁群算法。X.1双（多）蚁群算法介绍双蚁群系统由KAWAMURA于2000年提出，通过蚁群间的互动分享信息素，在充分利 用局部最优解的同时扩大搜索空间，经证明双蚁群系统比单蚁群系统效果更佳。国内，2006 年郏宣耀和滕少华也曾提出一种双种群改进蚁群算法，将两个蚂蚁群体分别独立金华，并定 期交换信息素，这一方法缓解了因信息素浓度失衡而造成的局部收敛，有效改进算法的搜索 性能，实验结果表明该算法有效可行。双（多）种群蚁群算法主要在基础蚁群算法的基础上增加一个或多个蚂

2、蚁种群，以基本 蚁群算法为标准构建多个蚂蚁种群，通过多个蚂蚁种群分别进行路径搜索，从而使得搜索的 不确定性增加，蚂蚁的路径探索效应增加，最终达到提高最优解的概率。同时，多种群蚁群 算法增加了各蚁群间的“互动”以加快其收敛速度，主要表现为信息素的交互媒介效应一一 正效应与负效应：信息素的正效应使蚂蚁倾向于将本种群搜索所得较优解分享给其他种群， 以便其他种群进行信息素更新；信息素的负效应使蚂蚁倾向于不受其他种群解的影响，也不 与其他种群分享本种群搜索获得的解空间。X. 2多种群蚁群算法一一以旅行商问题为例根据上节介绍，多种群蚁群算法具有信息素的交互媒介效应，故算法需要设置专门参数 以控制信息素的正

3、效应及负效应的强弱。本节以旅行商问题为例介绍多种群蚁群算法，对以 下符号进行定义：符号说明m每个汇总群中蚂蚁的个数M蚂蚁种群的个数（。t时刻位于城市i的蚂蚁的个数d. ij城市i与城市，之间的距离q ij路径（L，）的能见度，即为启发信息. tj路径（L /）上的信息素强度，即信息素信息A.ij蚂蚁k在路径（L，）上释放的信息素量蚂蚁k从城市i移动到城市，的概率X.2.1信息素更新机制多种群蚁群系统基于单种群蚁群系统，需对多个种群分别进行信息素更新，其更新机制可表现为：(X.1)zi (t + n) = zi (t) + Xm /(，t (X.1)ijij ，=1 ij vJ其中，区冲，t +

4、 n)表示第个种群的第k只蚂蚁在完成从i到/的路径后在路径(L j)上 释放的信息素，它的大小根据完整路径的质量而定，路径越短，释放的信息素越多，表示为:学(C，t + n) =(X.2)Q/Cik，如果学(C，t + n) =(X.2)、0,否则其中，Q为一正常数，E表示第个种群的第k只蚂蚁完成的完整路径的长度，即Tik 中所有边的长度之和。与单种群蚁群算法一样，蚂蚁在路径，)上释放的信息素大小取决 于。，)所在的完整路径TB的长度。X.2.2信息素挥发机制为了避免过早收敛，多种群蚁群算法基于单种群蚁群算法也有信息素挥发效应，其挥发 机制表现为：Tij(t + 1) = (1- P) Tij

5、(t)以.3)其中，p为信息素的挥发率。此处不同种群的信息素挥发率相同，即所有种群在同样时 间内挥发同样多的信息素，对不同问题可对不同种群设定不同的挥发系数，但目前并没有任 何研究表明设定不同种群信息素挥发率可以提高算法的性能。X.2.3蚂蚁路径搜索行为(I，上)表示第个种群的第k只蚂蚁，则蚂蚁(I，上)在选择完城市i后选择城市，的概率表 示为：(，jEgP(t) = .n1(X.4)I 0，/ 任 Nik叫i(t) = nrr.(t) + D(l)a(l，r- (l(X.5)lJr = 1 lJbJ其中，哗为第个种群的第k个蚂蚁在城市i时可以选择的城市的集合，该集合排除了已 经经过的城市以及

6、与城市i不相邻的城市。n.(t)表示了第个种群的第k个蚂蚁在城市i时对 城市/的倾向程度。a(l，r)为一预设参数，它决定蚂蚁种群Z和种群之间信息素效应的类型 和种群r对种群的影响程度。若a(l，r)的值为正，则种群和种群之间存在信息素正效应， 即种群的信息素更新在一定程度上取决于种群广搜索的解的质量，种群r中质量较好的解的 路径在种群Z中也会得到较多的信息素；相反，若al , r的值为负，则种群Z和种群r之间存 在信息素负效应，即种群/倾向于排斥种群r对它的信息素的影响，种群中的蚂蚁会避免经 过种群r中蚂蚁走过的路径。al，厂的绝对值越大，信息素的正效应或负效应越大，若 al，厂的值为零，则

7、种群1和种群r之间不存在信息素效应，等同于独立的单种群蚁群算法。D /为迟钝因子，用来防止信息素为零的情况。勺/为启发信息，可以设定为j = 1/djj，根 据文献资料，启发信息对TSP问题很重要，设定为边的距离的倒数优于设定为常数。夕Z表 示启发信息在第Z个种群的蚂蚁搜索决策中的重要程度。X.3基于多种群蚁群算法的总工期及平均权重延迟最优化项目调度问题在生活中普遍存在，在各种项目计划中通常采用的工具有关键路径法与计 划评审技术等，但这两种方法均忽略了项目中资源的限制，因而对存在资源约束的项目的调 度往往不能取得很好的结果。在现实中，资源供给往往是有限的，项目在每一阶段可利用的资源不可能无限制

8、，因此 资源是实际项目中不得不考虑的问题。为了让项目调度考虑资源约束从而更加接近实际情况， 便产生了资源受限项目调度问题(resource-constrained Project scheduling Problem, RCPSP)。资源受限项目调度问题，涉及一系列的具体任务(activities)与一个有限的资(resources) 集合，这些任务之间存在逻辑上的关系，同时每项任务的执行又需要特定数量的全部或部分 资源，而项目调度就是要合理分配这些资源，安排这些任务的开始时间，从而优化既定的一 个或若干个目标函数。本节利用多种群蚁群算法对多目标资源受限项目调度问题中的经典问题一一总工期及 平

9、均权重延迟最优化进行建模及算法实现描述，该问题目标为项目总工期最小化，且同时平 均权重延迟最小化。X.3.1信息素更新机制与TSP问题类似，信息素更新机制可表现为：Ti. t + n = Rj t + Z1 专t，t + n(X.6)其中，扩，t + n表示第Z个种群的第k只蚂蚁在完成从i到/的路径后在路径i，j上 释放的信息素，它的大小根据完整解的质量而定，解的质量越好，释放的信息素越多，对于 不同种群，其信息素更新规则也会有不同。对第一个种群，信息素更新规则表示为：(X.7 )蜜蛀 t n _（Q1/CT*，如果，J在总工期为CT(X.7 )七，I0,否则其中，Q1为一正常数，CT*表示第

10、k只蚂蚁完成的调度方案的总工期。蚂蚁在路径i , j 上释放的信息素大小取决于i , j所在的调度方案的总工期。对第二个种群，类似地有：最 七九_ （Q2/MWLk，如果i，j在平均加权任务延迟为MWLk的调度方案上% ，I0,否则（X.8）其中，Q2为一正常数，MWLk表示第k只蚂蚁完成的调度方案的平均加权任务延迟。蚂 蚁在路径i，j上释放的信息素大小取决于i，j所在的调度方案的平均加权任务延迟。X.3.2信息素挥发机制上节提到，不同种群的信息素挥发率相同，故为了避免过早收敛，两个种群的信息素挥发机制均表现为：T. t + 1 = 1-p - T. t（X.9）其中，P为信息素的挥发率。X.

11、3.3蚂蚁路径搜索行为与上节中TSP问题类似，在蚂蚁的路径搜索行为中，甩，k表示第个种群的第k只蚂 蚁，则蚂蚁1，k在选择完任务i后选择任务，的概率表示为：（，j G N*t =1（X.10）I 0，/ 任 Nikn. t = （HM 1 官 t +D lal， q.印（X.11）ijr_1L ijij其中，评为第个种群的第k个蚂蚁在任务i时可以选择的任务的集合，该集合排除了已 经完成的任务以及与任务i不存在紧前关系的任务。n. t表示了第个种群的第k个蚂蚁在完 成任务i时对选择任务，的倾向程度。al，r、D I及8 l意义与上节TSP问题中相同。财为 启发信息，由于本问题为多目标资源受限项目调度问题，对应不同的目标函数，其值设定不 同，即：对第一个种群，目标函数为总工期最小化，基于最迟完成时间优先原则的启发信息设定 为：V呼+。 E其中，N普表示第个种群的第k只蚂蚁在完成任务i以后可供选择的任务集合。LF表示 第个种群的第k只蚂蚁完成的任务九的最晚结束时间。e是一个参数，其值为正，目的是在蚂 蚁刚开始搜索时，让每个任务都有一定的概率被搜索。对第二个种群