Computer Engineering and Applications ›› 2021, Vol. 57 ›› Issue (2): 257-266.DOI: 10.3778/j.issn.1002-8331.2006-0313

Previous Articles     Next Articles

Solving FJSP by Multi-population Genetic Algorithms with Complex Network Structure

SHI Yuqiang, TIAN Yongzheng, ZHANG Yuqi, SHI Xiaoqiu   

  1. School of Manufacturing Science and Engineering, Southwest University of Science and Technology, Mianyang, Sichuan 621000, China
  • Online:2021-01-15 Published:2021-01-14

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

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

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

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用于求解更多的柔性作业车间调度问题并与多种其他算法比较,验证了其有效性。

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