Research on the performance of multi-population genetic algorithms with different complex network structures
Autor: | Dingshan Deng, Yong-lai Wei, Xiaoqiu Shi, Wei Long, Yanyan Li |
---|---|
Rok vydání: | 2020 |
Předmět: |
0209 industrial biotechnology
Job shop scheduling Computer science Evolutionary algorithm Computational intelligence Hamming distance 02 engineering and technology Complex network Average path length Theoretical Computer Science 020901 industrial engineering & automation Genetic algorithm 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Geometry and Topology Algorithm Software Premature convergence |
Zdroj: | Soft Computing. 24:13441-13459 |
ISSN: | 1433-7479 1432-7643 |
DOI: | 10.1007/s00500-020-04759-1 |
Popis: | Genetic algorithm is a frequently used evolutionary algorithm that cannot avoid premature convergence. Multi-population is usually used to overcome this disadvantage, obtaining multi-population genetic algorithm (MGA). If sub-populations and communications among them are considered as nodes and edges, respectively, an MGA can be represented as a complex network. After reviewing previous researches, we find that the network structures used to design MGAs are limited and some parameters (SPS, sub-population size, and SPN, sub-population number) under a certain total individual number (TIN) are always ignored. Using seven network structures (BAnet, BDnet, CTnet, ERnet, HAnet, LCnet, and SWnet) to design MGAs that are used to solve some flexible job shop scheduling problems, how the network structures and parameters affect the performances of MGAs is addressed. The simulation results indicate that: (i) the MGA with ERnet rather than the famous BAnet often performs well although their performances are problem-dependent; (ii) the Hamming distance index proposed here can properly capture the phenomenon that the smaller the average path length, the higher the propagation rate; and (iii) under a certain TIN, their performances first increase and then decrease gradually as SPN increases, and their performances first increase rapidly and then remain almost unchanged as SPS increases. |
Databáze: | OpenAIRE |
Externí odkaz: |