Parameter-Less Population Pyramid for Permutation-Based Problems
| Autor: | Marcin M. Komarnicki, Szymon Wozniak, Michal W. Przewozniczek |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
050101 languages & linguistics
Theoretical computer science Optimization problem Job shop scheduling Computer science 05 social sciences Evolutionary algorithm 02 engineering and technology Linkage (mechanical) law.invention Permutation Estimation of distribution algorithm law Discrete optimization 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing 0501 psychology and cognitive sciences Statistical hypothesis testing |
| Zdroj: | Parallel Problem Solving from Nature – PPSN XVI ISBN: 9783030581114 PPSN (1) |
| DOI: | 10.1007/978-3-030-58112-1_29 |
| Popis: | Linkage learning is frequently employed in state-of-the-art methods dedicated to discrete optimization domains. Information about linkage identifies a subgroup of genes that are found dependent on each other. If such information is precise and properly used, it may significantly improve a method’s effectiveness. The recent research shows that to solve problems with so-called overlapping blocks, it is not enough to use linkage of high quality – it is also necessary to use many different linkages that are diverse. Taking into account that the overlapping nature of problem structure is typical for practical problems, it is important to propose methods that are capable of gathering many different linkages (preferably of high quality) to keep them diverse. One of such methods is a Parameter-less Population Pyramid (P3) that was shown highly effective for overlapping problems in binary domains. Since P3 does not apply to permutation optimization problems, we propose a new P3-based method to fill this gap. Our proposition, namely the Parameter-less Population Pyramid for Permutations (P4), is compared with the state-of-the-art methods dedicated to solving permutation optimization problems: Generalized Mallows Estimation of Distribution Algorithm (GM-EDA) and Linkage Tree Gene-pool Optimal Mixing Evolutionary Algorithm (LT-GOMEA) for Permutation Spaces. As a test problem, we use the Permutation Flowshop Scheduling problem (Taillard benchmark). Statistical tests show that P4 significantly outperforms GM-EDA for almost all considered problem instances and is superior compared to LT-GOMEA for large instances of this problem. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|