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

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