运用含复杂网络结构的多种群遗传算法求解FJSP

石宇强，田永政，张雨琦，石小秋

西南科技大学 制造科学与工程学院，四川 绵阳621000

遗传算法[1]（Genetic Algorithm，GA）是历史上备受关注的进化算法之一。标准GA 在求解组合优化等问题上具有独特的优势，但是极易早熟收敛。为了克服这一缺点，多种群遗传算法（Multi-population Genetic Algorithm，MGA）随之出现，并获得了广泛的关注和应用[2-4]。MGA将标准GA的单种群划分为多个子群，保证了种群的多样性，每个子群内的个体按照标准GA 进化，精英个体在子群间迁徙传播优势基因，从而避免早熟收敛[5-6]。如文献[2]利用MGA 实现非线性动力学模型参数的辨识，预测橡胶波形发生器产生的冲击脉冲。文献[3]采用MGA 对常用的多孔吸声结构参数进行优化。但是，传统MGA的子群数有限，且大多忽略了子群结构对算法性能的影响。如果把子群以及它们之间的交流（优势基因的传播）分别看作节点和边，那么MGA就是一个复杂网络，代表了不同子群间的相互作用关系[7-8]。以往研究表明，复杂网络的集体行为会受到网络结构的显著影响[9-13]。类似地，MGA中子群间的交流构成的网络结构也将影响其寻优行为，进而影响MGA 的性能。

复杂网络可以描述自然界和人类社会中各种复杂系统[14]。其研究在许多领域都得到了应用，如金融网络[15]、蛋白质网络[16]、供需网络[17]等。在进化计算领域，许多研究者也利用复杂网络对GA 等进化算法进行了研究。文献[18]将进化算法的动态可视化为复杂网络，提出网络进化算法框架，并应用于GA、粒子群算法和差分进化算法中。文献[19]简述了进化算法的动态性如何转化为复杂网络，并根据其网络特征改进了自组织迁移算法、人工蜂群算法和GA 等算法。文献[20]在蚁群算法的基础上，在状态转移规则等中加入节点度系数，将改进算法用于移动Agent 问题中，显著提高了移动Agent的迁移效率。文献[21]利用复杂网络分析了不同的随机化对差分进化算法的影响。文献[22]提出了一种基于复杂网络的差分进化动力学建模方法，揭示了差分进化收敛速度与加权聚类系数之间的联系。文献[23]提出了一种动态小世界网络来优化粒子群算法，提高了算法性能。文献[24]将差分进化算法中个体看作节点，动力学传播方向看作边，提出利用个体的目标函数值及网络参数信息依概率选取目标向量的机制，改变不同函数类型的收敛速度。文献[25]将GA进化过程建模为复杂网络，并设计一种自组织动态网络结构，有效提高了GA的性能。文献[26]利用不同网络模型作为算法的底层结构，研究了不同网络结构对进化算法动态性能的影响，发现网络特性对算法的动态性和解的多样性有显著的影响。文献[27]提出了一种基于复杂网络的粒子群算法，并将该算法用于改进AdaBoost算法，缩短了样本训练时间，提高了人脸检测率。

总的来说，现有研究利用复杂网络来改进进化算法或者研究网络结构对进化算法的影响时，它们大多是对算法个体间优势基因的传播构成的网络进行研究，鲜有研究考虑子群间优势基因的传播构成的网络结构对算法的影响，且较少考虑网络结构参数的变化对算法的影响并从实际问题的角度进行分析。因此，不同网络结构参数下网络结构控制子群间优势基因的传播对MGA寻优性能的影响尚不清楚。现实生活中，许多网络的节点度分布服从幂律分布，即无标度网络[28]。现实复杂网络的标度指数各不相同，有的网络有核心节点存在但不具有无标度特性[29-30]。因此，本文利用不同标度指数的无标度网络，或有核心节点但不具有无标度特性的网络来设计MGA，得到一种含复杂网络结构的多种群遗传算法（Multi-population Genetic Algorithms with Complex Network Structures，MGA-CNS），然后以经典的柔性作业车间调度问题（Flexible Job shop Scheduling Problem，FJSP）[31]为例，利用MGA-CNS 来解决一个FJSP 基准测试问题，研究在解决实际问题时不同网络结构参数对算法性能的影响。最后，将参数优化后的MGA-CNS来求解更多FJSP 实例并与多种其他算法进行比较，验证其有效性。

综上所述，为了了解在不同网络结构参数下网络结构控制子群间优势基因的传播对MGA 寻优性能的影响，本文进行了以下研究：（1）提出一种含复杂网络结构的多种群遗传算法；（2）通过仿真控制网络结构参数的变化，研究网络结构参数对算法寻优性能的影响。

1 模型与算法

1.1 柔性作业车间调度问题

FJSP由Brucker等[31]提出，可以简单地描述为：在一个车间有m 台机器(M1,M2,…,Mm) 对n 个工件(J1,J2,…,Jn) 进行加工。其中，每个工件Ji有若干个工序，分别记为：Oi1,Oi2,…,Oini。每个工序可以在一个候选机器集上进行加工，第i 个工件第j 个工序的候选机器集记为Sij，其在第k 台机器(Mk)上进行加工的时间表示为Pijk。每台机器一次只能加工一个工序，同一工序可在多台机器上进行加工，但每个工序每次只能在一台机器上加工。FJSP 可以分为两个子问题：一是为每个工件的每个工序选择合适的机器，另一个是为分配给同一机器的所有工序安排合适的加工顺序。FJSP通常有最小化最大完工时间和最小化最大机器工作载荷等优化目标。本文以研究算法性能为目的，因此选择最常用的最小化最大完工时间为优化目标，FJSP 的数学模型如下所示[7]：

公式（1）表示目标函数，即最小化最大完工时间。Fij和Fmax分别表示工序Oij的完工时间和所有作业的最大完工时间。公式（2）表示工艺约束，确保了同一工件的所有工序的正确加工顺序，当工序Oij在第k 台机器上进行加工时，Xijk等于1，否则为0。公式（3）表示每个工序每次只能在一台机器上加工，Bijk和Fijk分别表示工序Oij在第k 台机器上的加工开始时间和加工完成时间。公式（4）表示每台机器一次只能加工一个工序。其中，符号“∧”和“∨”分别表示逻辑与和逻辑或。表1给出了一个FJSP例子。

表1 一个FJSP例子

在表1的例子中，给出了三个工件，六台机器，每个工件都有两个工序。其中，数字0表示该工序不能在对应的机器上进行加工，其余数字表示工序Oij在机器Mk上的加工时间。比如，第五行第一列的0 表示第三个工件的第一个工序O31不能在机器M1上进行加工，第二行第一列的8表示第一个工件的第二个工序O12在机器M1上的加工时间为8。

1.2 含复杂网络结构的多种群遗传算法

生成无标度网络的模型中，最经典的当属BA 模型[28]。BA 模型的主要特点是增长和优先连接，其节点度(K)服从幂律分布：K-γ（γ 为标度指数）。然而，由BA模型所生成的无标度网络的标度指数接近一个常数(γ=3)，但实际复杂网络的标度指数各不相同，也有的网络不具有无标度特性，但总有核心节点的存在[29-30]。因此，本文利用文献[29]和[32]提到的参数可控的复杂网络模型，生成不同标度指数的无标度网络，或生成含有核心节点但不具有无标度特性的网络，以研究不同网络结构参数对MGA的影响规律。该模型可描述如下：

从一个初始规模为m0（初始节点数为m0）的全连接网络开始，每一时间步t 引入一个新节点j，每个新节点j 与m(≤m0)个老节点相连接，不允许重边与自环。老节点i 被选择的概率与其产生核(Ai)有关，表示为：

式（6）中，∀k 表示求和号涵盖所有老节点，Ai表示为：

其中，α 和β 是两个可控参数，Ki为节点度（节点i 的邻居节点数量）。当β 不变时，不同的α 值可生成不同标度指数的无标度网络。当α 不变时，不同的β 值可生成含有核心节点但不具有无标度特性的网络。图1 绘出了具有12个节点的无标度网络示意图。

图1（a）绘出了其网络结构，图1（b）中，横轴按节点度对12个节点进行排序，纵轴表示相应的节点度。

图1 一个含有12个节点的无标度网络

如前所述，MGA将标准GA的单种群划分为多个子群，这些子群构成节点，子群之间优势基因的传播构成边，不同的连接构成了不同的网络结构。MGA 中所有子群的数量称为子群数，每个子群的个体数量称为子群大小[7]。MGA 在执行过程中，首先进行种群初始化，生成N 个子群，每个子群的大小为S。然后，所有子群中的个体都同时进化，都会根据适应度函数来评价个体，根据精英制选择精英个体，精英个体在子群间迁徙，从而优势基因在不同子群之间进行传播，产生新一代子群，实现优胜劣汰的进化过程，直到得到最优解。

本文利用上述网络模型生成的网络来设计MGA，控制子群间优势基因的传播，得到MGA-CNS。节点就是MGA-CNS 的子群，用V 表示节点集合；边就是子种群间优势基因的传播，用E 表示边集合；若节点Vi与Vj连接构成边eij，则eij∈E 。MGA-CNS 的流程图如图2所示，具体步骤如下：

步骤1 初始化，根据编码规则随机初始化N 个子群，每个子群中的个体数量为S。

步骤2 判断是否达到最大迭代次数，如果当前迭代次数(Inow)等于最大迭代次数(Imax)，则输出最优解，并结束计算，否则，转向步骤3。

图2 MGA-CNS的流程图

步骤3 用解码算法计算每个子群中个体的适应度，将精英个体保存到精英集合中。

步骤4 根据适应度，采用标准的竞标赛方法选择每个子群的下一代个体。

步骤5 将得到的个体随机进行交叉，产生新的个体。

步骤6 将得到的个体根据变异概率(Pr)进行变异产生新的个体。

步骤7 随机选择一个子群（节点Vi），根据设计的网络，找到节点Vi的所有邻居节点，找到这些节点（包含节点Vi）中最好的精英个体，将它放入这些节点中，并保持它们的子群规模不变。返回步骤2。

图3 给出了一个含四个子群的MGA-CNS，每个子群含有四个个体，个体间通过遗传算子进化，子群间通过精英个体的迁徙传播优势基因。

图3 MGA-CNS的示意图

1.3 MGA-CNS解决FJSP

MGA-CNS 在求解FJSP 时，包含四个主要的操作，分别是编码、解码、交叉和变异。

1.3.1 编码

使用MGA-CNS 解决FJSP 时，第一步是知道如何得到一个暂定的编码解。文献[5]中描述了使用整数编码方法来获得编码解。整数编码分为两个阶段：第一个阶段为机器编码，第二个阶段为工序编码。

在机器编码阶段，用一个整数串表示编码解；整数串的数量表示所有工件的工序总数量，整数的位置表示工序，整数的数值代表候选机器中加工该项工序的机器序号。例如表1 中的FJSP 例子，一共有六个工序，一个编码解为（3 3 2 1 3 1）。这个整数串里一共有六个整数，代表一共有六个工序。第一个整数3 代表了工序O11在候选机器中的第三台机器中进行加工，即机器M5而不是M3。第二个整数3 代表了工序O12在机器M6上进行加工，以此类推。

在工序编码阶段，用一个整数串表示编码解，整数串的数量表示所有工件的工序总数量，整数的位置表示加工顺序，整数的值表示工序号。如果一个工件有n 个工序，那么这个工件号就会出现n 次。例如表1中的例子，工序编码解为（2 1 2 3 1 3）。这个整数串里一共有六个整数，代表一共有六个工序。1、2、3分别出现了两次，这代表工件1、2、3分别有两项工序。第一个整数2 代表这次加工工序O21，第二个整数1 代表这次加工工序O11，第三个整数2代表这次加工工序O22，以此类推。

将两个阶段得到的机器编码解和工序编码解结合起来考虑会得到，先是在机器M2上加工工序O21，然后，在机器M5上加工工序O11，接着在机器M1上加工工序O22，以此类推。从而，整数串（3 3 2 1 3 1 2 1 2 3 1 3）代表了一个个体。

1.3.2 解码

为了获得最终可行的解决方案，需要对编码的个体进行解码。文献[5]提出的解码算法被用于从个体中获得解决方案。还以表1 的FJSP 为例，考虑个体（3 3 2 1 3 1 2 1 2 3 1 3），可以得到的解为一个矩阵M′=[2 1 2 3 0 0；1 1 5 2 0 0；2 2 1 1 0 0；3 1 5 3 0 0；1 2 6 1 0 0；3 2 1 1 0 0]。第一个整数表示工件号，第二个整数表示该工件的工序号，第三个整数表示加工该工序的机器号，第四个整数表示在该机器上的加工开始时间，第五个整数表示在该机器上的加工结束时间。例如（2 1 2 3 0 0）就表示的是第二个工件的第一个工序由第二台机器M2加工，加工时间为P212=3。但开始和结束时间未知（用0表示），以此类推。

开始和结束时间初始化都为0。用Bijk表示工序Oij的加工开始时间，Fijk表示工序Oij的加工结束时间，加工结束时间等于加工开始时间加上加工时间。分为四种情况讨论，如表2所示。所有情况要保证考虑到了所有M′行。

表2 一个FJSP例子

1.3.3 交叉

交叉和编码一样分为两个阶段，第一个阶段为机器交叉，第二个阶段为工序交叉。在机器交叉阶段，随机生成两个小于工序总数的整数，以这两个随机整数为节点实现两点交叉，如图4（a）。在工序交叉阶段，如文献[5]所描述，随机选择两个个体（父代1和父代2），所有工序被随机分成两组（第一组和第二组），那么子代1和子代2分别继承父代1和父代2的属于组1和组2的整数，同时保留这些整数的位置，子代1 和子代2 分别继承父代2和父代1 的不属于组1 和组2 的整数，并保留这些整数的序列，如图4（b）。

图4 交叉运算

1.3.4 变异

变异保持了个体的多样性，是MGA-CNS的主要算子之一。变异也分为两个阶段。第一个阶段是机器变异阶段，第二个阶段是工序变异阶段。在机器变异阶段，根据变异概率随机选择几个个体，然后在选中的每个个体中再随机选择几个位置，用几个小于机器总数的整数来替换这几个位置上的整数。在工序变异阶段，也是根据变异概率随机选择几个个体，随机产生两个小于工序总数的整数，这两个整数代表了被选中个体上的两个位置数，同时代替被选中个体这两个位置上的整数。

1.4 评价指标

标准GA 按与个体适应度成正比的概率来决定当前种群中每个个体能遗传到下一代种群中的机会多少。在MGA-CNS 中，除了考虑个体适应度以外，还要考虑子群的适应度。正如文献[7]所描述的，MGA 的本质是一种随机搜索算法，具有一些控制条件，算法的个体总数(TIN) 越大，算法的性能应该越好。因为，当TIN 越大时，算法搜索的次数就越多，就应该能找到更优的解。MGA-CNS的TIN 计算公式如下：

S 代表子群大小，N 代表子群数，TG 代表相应MGACNS 的总代数。当某一变量改变时，TIN 会有很大的不同。例如，有A和B两个MGA-CNS，A和B的TG 都为100，但是它们的S 和N 不同，A的S 和N 为40，40，B的S 和N 为400，400，那么A和B的TIN 分别为160 000和16 000 000。理论上说，B能找到更优的解，但如果它们找到相同的解，则A 要好得多，因为它找到同样优的解所用的搜索次数更少。

如文献[5]中所述，他们在解决FJSP时，采用的最大的TIN 是100万。为了使子群拥有更多交流机会，本文采用的最大的TIN 为200 万。如前所述，FJSP 的目标是尽量缩短最大完工时间。因此，使用基于TIN 的最大完工时间来评估MGA-CNS的性能，其中较小的最大完工时间表示较好的MGA-CNS。每个算法独立运行Nt次，得到的最大完工时间的平均值称为平均最优值，用于评估MGA-CNS的性能。并且，还通过计算成功率(SR)来评价MGA-CNS 的优劣，成功率越高，则表示算法越好。成功率的计算公式如下：

这里的Ns表示式中所用算法在Nt次运行中能够找到所解决的FJSP的最优解的次数。

2 仿真研究

2.1 实验设置

使用一个10×10FJSP 实例[7]来测试MGA-CNS，研究所使用网络的结构参数是怎样影响MGA-CNS 的性能。分别进行以下几个实验：

实验1 子群大小S 对MGA-CNS性能的影响；

实验2 子群数N 对MGA-CNS性能的影响；

实验3 可控参数α 对MGA-CNS性能的影响；

实验4 可控参数β 对MGA-CNS性能的影响；

实验5 初始网络规模m0对MGA-CNS性能的影响。

为了保证实验的准确性，在分别测试网络结构参数S、N、α、β 和m0对MGA-CNS的影响时，除了被测参数按规则变化外，其余参数均保持不变。

2.2 子群大小S 对MGA-CNS性能的影响

研究子群大小S 对MGA-CNS 性能的影响。相关参数的设置如下：Pr=0.08,N=100,TIN=2 000 000，α=1,β=1,m0=2,S 以20 为步长从10 变化到200，Nt=20。图5 给出了平均最优值和成功率随S 的变化情况。

如图5 所示，当S=20 时，MGA-CNS 的性能较差，平均最优值为8.9，成功率为40%。随着子群大小的扩大，MGA-CNS 的性能变好。当S=60 时，平均最优值为7.5，成功率为50%。当子群大小在60 到100 之间扩大时，MGA-CNS 性能逐渐变差。当S=100 时，平均最优值为7.7，成功率为30%。当子群大小大于100 时，随着子群大小的扩大，平均最优值减小，成功率增加。因此，子群大小最好大于100，并且子群越大，MGA-CNS性能越好。

图5 平均最优值和成功率随子群大小的变化情况

2.3 子群数N 对MGA-CNS性能的影响

研究子群数N 对MGA-CNS 性能的影响。相关参数的设置如下：Pr=0.08,S=40,TIN=2 000 000,α=1,β=1,m0=2,N 以10 为步长从10 变化到200，Nt=20。图6给出了平均最优值和成功率随N 的变化情况。

图6 平均最优值和成功率随子群数的变化情况

如图6所示，当N=10 时，平均最优值为8.95，成功率为45%，MGA-CNS 的性能较差。随着N 的增加，MGA-CNS的性能变好。当N=70 时，平均最优值为8.1，成功率为90%。随着N 的进一步增大，平均最优值逐渐减小，但是成功率也逐渐降低。因此，为了使MGA-CNS的性能较好，N 不能取值过小，更不能取值过大。

2.4 参数α 对MGA-CNS性能的影响

研究可控参数α 对MGA-CNS 性能的影响。相关参数的设置如下所示：Pr=0.08,S=40,N=100,TIN=2 000 000,β=1,m0=2,α 从0.1变化到20，当从0.1变化到1时，步长为0.1，当从1变化到20时，步长为2，Nt=20。如文献[29]所述，通过调整α 的值可以生成不同标度指数的网络。当α 从0 变化到1 时，标度指数从无穷大趋近于3，由于0 到1 的区间较小，因此以0.1 为步长；当α大于1 时，标度指数小于3，此时α 可调区间较大，因此以2为步长。图7给出了平均最优值和成功率随α 的变化情况。

图7 平均最优值和成功率随α 的变化情况

在图7 中，当α=0.1 时，平均最优值为7.75，成功率为35%，MGA-CNS 的性能较好。当α 大于0.3 时，平均最优值显著上升，而成功率显著下降，这说明MGA-CNS的性能也显著下降。随着α 的增加，平均最优值总体呈上升趋势，而成功率总体呈下降趋势（不考虑α=7 时的异常，见图7（b）中标注点）。这意味着，当α 较大时，MGA-CNS的性能反而会降低。当α=0.2 时，MGA-CNS的性能达到最优，平均最优值为7.65，成功率为40%，但α 在区间[0.1，0.3]变化时，算法性能波动不大，α=0.2 的左右两个区间表现相同的趋势，都具有较好的性能。因此，为了获得更好的MGA-CNS，α 不能太大，更具体地说，当α 的值不大于0.3时，MGA-CNS的性能更好。

2.5 参数β 对MGA-CNS性能的影响

研究可控参数β 对MGA-CNS 性能的影响。相关参数如下：Pr=0.08,S=40,N=100,TIN=2 000 000,α=1,m0=2,β 从0.2变化到3，步长为0.2，Nt=20。图8给出了平均最优值和成功率随β 的变化情况。

在图8 中，当β=0.2 时，平均最优值为7.7，成功率为35%，此时，MGA-CNS的性能最优。随着β 的增加，平均最优值总体呈上升趋势，它先随着β 的增加而增加，当β 在2.2和2.8之间扩大时，平均最优值随之减小，之后，平均最优值又随着β 的增加而增加。与平均最优值相反，成功率呈下降趋势，特别是，当β 大于0.8 时（图8中圆圈标注点），成功率显著下降，当β 大于1时，成功率的波动较小，基本趋于稳定（不考虑β=3 和3.2时的异常，见图8 中矩形标注点）。这意味着，MGACNS 的性能先随着β 的增加而下降，然后随着β 的增加而增加，再随之下降，总体呈下降趋势。根据平均最优值和成功率的变化可看出，β 在区间[0.2，0.8]变化时，MGA-CNS 可获得较好的性能，且越往后，MGACNS的性能越差。因此，为了获得更好的MGA-CNS，β的取值不能太大，更具体地说，当β 的值不大于0.8时可以得到较好的MGA-CNS。

图8 平均最优值和成功率随β 的变化情况

2.6 初始网络规模m0 对MGA-CNS性能的影响

研究初始网络规模m0对MGA-CNS 性能的影响。相关参数的设置如下：Pr=0.08,S=40,N=100,TIN=2 000 000,α=1,β=1,m0从2变化到10，步长为1，Nt=20。图9给出了平均最优值和成功率随m0的变化情况。

图9 平均最优值和成功率随初始网络规模的变化情况

如图9 所示，随着m0的增加，平均最优值在7.9 和8.2 之间波动，成功率在5%和20%之间波动。当m0=4时，平均最优值取得最小值为7.9，成功率取得最大值为20%，此时，MGA-CNS 的性能较好。仔细观察可以发现，虽然平均最优值一直在上下波动，但总体呈上升趋势，而成功率波动较小，基本趋于稳定。这意味着，MGA-CNS 的性能随着m0的增加而下降。因此，为了获得更好的MGA-CNS，m0的取值不能太大，当m0不大于4时可以得到较好的MGA-CNS。

2.7 MGA-CNS求解FJSP的有效性

以文献[33]提到的18个FJSP实例为例，验证MGACNS 的有效性。通过前文的研究，确定相关参数：Pr=0.08,S=200,N=70,TIN=2 000 000,α=0.2,β=0.2,m0=4,Nt=20。表3给出了用MGA-CNS求解文献[33]提到的18个FJSP实例与文献[34-37]所提算法求解的比较结果。图10给出了求解MFJS08得到的甘特图。

图10 MFJS08实例的甘特图

表3中，文献[34]有AIS和HHS两种算法，符号“—”表示原文没有给出相应数据。用MGA-CNS 求解MFJS02 时最优值为446，比文献[34]的448 更优；求解MFJS05 时最优值为514，比文献[34]的527 更优；求解MFJS06 时最优值为634，比文献[34]的635 更优；求解MFJS04 时最优值为554，比文献[35]的564 更优；求解MFJS07时最优值为881，比文献[35]的928更优；说明了MGA-CNS的有效性。

2.8 结果分析

标准GA 有一个非常明显的缺点，就是过早收敛。GA 靠交叉算子把父代的优势基因遗传给子代，使优势基因很快就积累起来，而很少破坏它们，这导致GA 可以非常快速地获得局部最优值。在之前的很多文献中都提出了很多解决这个问题的办法，而本文提到的MGA-CNS也同样是为了解决GA过早收敛的问题。当MGA-CNS的不同子群彼此交流时，优势基因不仅能够在子群内进行传播，而且还能在子群之间进行传播。子群之间优势基因的传播主要受其网络结构控制，已有研究表明，网络平均路径长度越小，优势基因传播速率越高[29]。本文研究了五个网络结构参数（S、N、α、β 和m0）分别在其余参数都不改变的情况下对MGA-CNS的影响。

如2.2 节所述，在一定的TIN 下，随着S 的增大，MGA-CNS 的性能先逐渐提高，然后逐渐降低，当S 大于100后，MGA-CNS的性能又逐渐提高。S 越大，平均最优值越小，成功率越高，此时更容易得到最优解，MGA-CNS 的性能就越好。因为，当S 很小时，子群中个体的数量较少，此时基因池较单一，存在多样性不足的问题，容易早熟收敛，所以此时的算法性能较差；而随着S 的增加，子群中的个体数量增加，子群中的多样性得到了保持，所以算法性能越来越好。

表3 比较结果

如2.3 节所述，在一定的TIN 下，随着N 的增大，MGA-CNS 的性能先逐渐提高，随后又逐渐降低，为了使MGA-CNS的性能较好，N 不能取值过小，更不能取值过大。这是因为，当N 值很小时，子群个数过少，不利于子群之间的交流，但是又因为每个子群的规模适当，所以MGA-CNS的性能不会太差。随着N 的增大，子群个数变多，更有利于保持种群多样性，所以MGACNS的性能逐渐变好，但是当N 进一步增大时，一次迭代所用的个体数很多，又因N 是一个定值，所以总的迭代次数很少，个体来不及积累优势基因，MGA-CNS 的性能也就变差。因此，可以得出如文献[38]所述的结论：在一定的总个体数下，多代寻优是合理的策略。

如2.4 节所述，在一定的TIN 下，随着α 的增大，MGA-CNS 的性能逐渐降低。因此，为了获得更好的MGA-CNS，α 的取值不能太大，更具体地说，当α 的值不大于0.3时，MGA-CNS的性能更好。因为，当α 较小时，网络中具有更多的高节点度的节点，网络的连接性更好，网络的平均路径长度较小，从而子群间优势基因的传播速率较高，更有利于保持种群多样性且较快地获得最优解，所以α 的取值不能太大。

如2.5 节所述，在一定的TIN 下，随着β 的增大，MGA-CNS 的性能先逐渐降低，再逐渐提高，然后又逐渐降低，总体呈下降趋势。为了获得更好的MGA-CNS，β 的取值不能太大，当β 不大于0.8 时，MGA-CNS 的性能较好。因为，当β 较大时，网络中会出现一个凝聚点，这个节点几乎与其他所有节点连接[32]。此时，网络的平均路径长度非常小，子群间优势基因传播速率非常高，MGA-CNS将非常快速地获得局部最优值，从而导致早熟收敛。所以，当β 大于0.8时算法性能会变差。

如2.6 节所述，在一定的TIN 下，随着m0的增大，MGA-CNS 的性能逐渐降低。因此，为了获得更好的MGA-CNS，m0取值不能太大，当m0不大于4时可以得到较好的MGA-CNS。这是因为，当m0越大时，新引入的节点与网络中具有高节点度的节点连接的概率越大，这意味着优势基因将很少传播到其他的子群，便无法从其他精英个体中获益，所以，m0取值不能太大。

3 总结

GA 在处理组合优化等问题上具有独特的优势，但是却容易出现早熟收敛的问题。为了克服这一缺点，多种群是一种有效的方法。但以往研究中，往往忽略了子群间优势基因的传播构成的网络结构对算法的影响，没有考虑到某些网络结构参数（S、N、α、β 和m0）对MGA 的影响。因此，本文设计了一种含复杂网络结构的多种群遗传算法（MGA-CNS）来对这五个参数对算法性能的影响规律进行研究。

仿真结果表明，子群大小S 的取值最好大于100，并且S 越大，MGA-CNS的性能越好；为了使MGA-CNS的性能较好，子群数N 不能取值过小，更不能取值过大；可控参数α 的值不能太大，更具体地说，当α 不大于0.3时，MGA-CNS的性能更好；可控参数β 的取值不能太大，当β 不大于0.8 时，可以得到较好的MGA-CNS；为了获得更好的MGA-CNS，初始网络规模m0的取值也不能太大，当m0不大于4时，MGA-CNS的性能更好。

本文研究了用MGA-CNS 解决组合优化问题时不同网络结构参数对算法的影响，但是在优化问题中还有连续优化问题。另外，多种群能够改善GA 的性能，而入侵杂草优化算法（Invasive Weed Optimization，IWO）[39]的改善不能仅靠多种群[5]，所以在今后的研究中会对连续优化问题和IWO的性能改善进行进一步的研究。