Abstract:

Multi-population is an effective method to overcome the premature convergence of Genetic Algorithm（GA）. However, the traditional Multi-population Genetic Algorithms（MGAs） seldom consider the influence of the structure of sub-populations on the performance of MGAs and the number of sub-populations is limited. Therefore, in order to make up for the above shortcomings, the Multi-population Genetic Algorithms with Complex Network Structures（MGA-CNS） are proposed. Taking the Flexible Job shop Scheduling Problem（FJSP） as an example, the effects of network structure parameters, such as sub-population size, sub-population number, controllable parameter [(α)], controllable parameter [(β)] and initial network size on the performance of the MGA-CNS are studied. The simulation results indicate that：the larger the sub-population size, the better the performance of MGA-CNS; the sub-population number should not be too small or too large; the value of [α] should not be too large, which should not be greater than 0.3; the value of [β] should not be too large, which should not be greater than 0.8; and the initial network size should not be greater than 4. Finally, the MGA-CNS is used to solve more FJSP and compared with many other algorithms to verify its effectiveness.

Key words: complex networks, multi-population, genetic algorithm, flexible job shop scheduling problem

摘要：

多种群是为了克服遗传算法易早熟收敛而提出的一种有效方法，但是传统的多种群遗传算法较少考虑子群结构对算法性能的影响，且算法子群数有限。因此，为了弥补以上不足，提出一种含复杂网络结构的多种群遗传算法（Multi-population Genetic Algorithms with Complex Network Structures，MGA-CNS），以求解柔性作业车间调度问题为例，研究子群大小、子群数、可控参数[(α)]、可控参数[(β)]以及初始网络规模对MGA-CNS寻优性能的影响。仿真表明：子群大小越大，MGA-CNS的性能越好；子群数不能取值过小，更不能取值过大；[α]的值不能太大，以不大于0.3为宜；[β]的取值也不能太大，以不大于0.8为宜；初始网络规模以不大于4为宜。将参数优化后的MGA-CNS用于求解更多的柔性作业车间调度问题并与多种其他算法比较，验证了其有效性。

关键词: 复杂网络, 多种群, 遗传算法, 柔性作业车间调度问题