Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems.
A genetic algorithm (GA) cannot always avoid premature convergence, and multi-population is usually used to overcome this limitation by dividing the population into several sub-populations (sub-population number) with the same number of individuals (sub-population size). In previous research, the qu...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Public Library of Science (PLoS)
2020-01-01
|
| Series: | PLoS ONE |
| Online Access: | https://doi.org/10.1371/journal.pone.0233759 |
| _version_ | 1818729617780899840 |
|---|---|
| author | Xiaoqiu Shi Wei Long Yanyan Li Dingshan Deng |
| author_facet | Xiaoqiu Shi Wei Long Yanyan Li Dingshan Deng |
| author_sort | Xiaoqiu Shi |
| collection | DOAJ |
| description | A genetic algorithm (GA) cannot always avoid premature convergence, and multi-population is usually used to overcome this limitation by dividing the population into several sub-populations (sub-population number) with the same number of individuals (sub-population size). In previous research, the questions of how a network structure composed of sub-populations affects the propagation rate of advantageous genes among sub-populations and how it affects the performance of GA have always been ignored. Therefore, we first propose a multi-population GA with an ER network (MPGA-ER). Then, by using the flexible job shop scheduling problem (FJSP) as an example and considering the total individual number (TIN), we study how the sub-population number and size and the propagation rate of advantageous genes affect the performance of MPGA-ER, wherein the performance is evaluated by the average optimal value and success rate based on TIN. The simulation results indicate the following regarding the performance of MPGA-ER: (i) performance shows considerable improvement compared with that of traditional GA; (ii) for an increase in the sub-population number for a certain TIN, the performance first increases slowly, and then decreases rapidly; (iii) for an increase in the sub-population size for a certain TIN, the performance of MPGA-ER first increases rapidly and then tends to remain stable; and (iv) with an increase in the propagation rate of advantageous genes, the performance first increases rapidly and then decreases slowly. Finally, we use a parameter-optimized MPGA-ER to solve for more FJSP instances and demonstrate its effectiveness by comparing it with that of other algorithms proposed in other studies. |
| first_indexed | 2024-12-17T22:48:44Z |
| format | Article |
| id | doaj.art-8dd76fcdfa6648d5b68710972efd6f11 |
| institution | Directory Open Access Journal |
| issn | 1932-6203 |
| language | English |
| last_indexed | 2024-12-17T22:48:44Z |
| publishDate | 2020-01-01 |
| publisher | Public Library of Science (PLoS) |
| record_format | Article |
| series | PLoS ONE |
| spelling | doaj.art-8dd76fcdfa6648d5b68710972efd6f112022-12-21T21:29:44ZengPublic Library of Science (PLoS)PLoS ONE1932-62032020-01-01155e023375910.1371/journal.pone.0233759Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems.Xiaoqiu ShiWei LongYanyan LiDingshan DengA genetic algorithm (GA) cannot always avoid premature convergence, and multi-population is usually used to overcome this limitation by dividing the population into several sub-populations (sub-population number) with the same number of individuals (sub-population size). In previous research, the questions of how a network structure composed of sub-populations affects the propagation rate of advantageous genes among sub-populations and how it affects the performance of GA have always been ignored. Therefore, we first propose a multi-population GA with an ER network (MPGA-ER). Then, by using the flexible job shop scheduling problem (FJSP) as an example and considering the total individual number (TIN), we study how the sub-population number and size and the propagation rate of advantageous genes affect the performance of MPGA-ER, wherein the performance is evaluated by the average optimal value and success rate based on TIN. The simulation results indicate the following regarding the performance of MPGA-ER: (i) performance shows considerable improvement compared with that of traditional GA; (ii) for an increase in the sub-population number for a certain TIN, the performance first increases slowly, and then decreases rapidly; (iii) for an increase in the sub-population size for a certain TIN, the performance of MPGA-ER first increases rapidly and then tends to remain stable; and (iv) with an increase in the propagation rate of advantageous genes, the performance first increases rapidly and then decreases slowly. Finally, we use a parameter-optimized MPGA-ER to solve for more FJSP instances and demonstrate its effectiveness by comparing it with that of other algorithms proposed in other studies.https://doi.org/10.1371/journal.pone.0233759 |
| spellingShingle | Xiaoqiu Shi Wei Long Yanyan Li Dingshan Deng Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems. PLoS ONE |
| title | Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems. |
| title_full | Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems. |
| title_fullStr | Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems. |
| title_full_unstemmed | Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems. |
| title_short | Multi-population genetic algorithm with ER network for solving flexible job shop scheduling problems. |
| title_sort | multi population genetic algorithm with er network for solving flexible job shop scheduling problems |
| url | https://doi.org/10.1371/journal.pone.0233759 |
| work_keys_str_mv | AT xiaoqiushi multipopulationgeneticalgorithmwithernetworkforsolvingflexiblejobshopschedulingproblems AT weilong multipopulationgeneticalgorithmwithernetworkforsolvingflexiblejobshopschedulingproblems AT yanyanli multipopulationgeneticalgorithmwithernetworkforsolvingflexiblejobshopschedulingproblems AT dingshandeng multipopulationgeneticalgorithmwithernetworkforsolvingflexiblejobshopschedulingproblems |