Local search pivoting rules and the landscape global structure
| Autor: | Gabriela Ochoa, Sara Tari |
|---|---|
| Přispěvatelé: | Université du Littoral Côte d'Opale (ULCO) |
| Rok vydání: | 2021 |
| Předmět: |
Mathematical optimization
business.industry Iterated local search Fitness landscape Computer science Binary number Sample (statistics) 0102 computer and information sciences 02 engineering and technology 01 natural sciences Visualization Local optimum 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering Benchmark (computing) [INFO]Computer Science [cs] 020201 artificial intelligence & image processing Local search (optimization) business ComputingMilieux_MISCELLANEOUS |
| Zdroj: | GECCO GECCO '21: Genetic and Evolutionary Computation Conference GECCO '21: Genetic and Evolutionary Computation Conference, Jul 2021, Lille France, France. pp.278-286, ⟨10.1145/3449639.3459295⟩ |
| Popis: | In local search algorithms, the pivoting rule determines which neighboring solution to select and thus strongly influences the behavior of the algorithm and its capacity to sample good-quality local optima. The classical pivoting rules are first and best improvement, with alternative rules such as worst improvement and maximum expansion recently studied on hill-climbing algorithms. This article conducts a thorough empirical comparison of five pivoting rules (best, first, worst, approximated worst and maximum expansion) on two benchmark combinatorial problems, NK landscapes and the unconstrained binary quadratic problem (UBQP), with varied sizes and ruggedness. We present both a performance analysis of the alternative pivoting rules within an iterated local search (ILS) framework and a fitness landscape analysis and visualization using local optima networks. Our results reveal that the performance of the pivoting rules within an ILS framework may differ from their performance as single climbers and that worst improvement and maximum expansion can outperform classical pivoting rules. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|