Toward the Design of Efficient Pivoting Rules for Local Search
| Autor: | Adrien Goëffon, Sara Tari, Matthieu Basseur |
|---|---|
| Rok vydání: | 2016 |
| Předmět: |
Mathematical optimization
Fitness landscape business.industry Computer science 0102 computer and information sciences 02 engineering and technology 01 natural sciences Field (computer science) Identification (information) Local optimum 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Local search (optimization) business Metaheuristic |
| Zdroj: | GECCO (Companion) |
| Popis: | Despite the huge number of studies in the metaheuristic field, it remains difficult to understand the relative impact of their elementary components. A major aspect determining the general efficiency of metaheuristics resides in the way to exploit a neighborhood structure to move within a search space. In particular, the study of iterative improvement neighborhood searches (climbers) provides guidelines to better understand local searches behavior. Several studies clearly state that some climbing strategies are more suited than classical best and first improvement, on which most local searches are based. Here, we are interested in determining empirically climbing strategies that allow the attainment of high quality local optima. First, we study alternative move selection criteria that globally outperform best and first improvement. Unfortunately, these strategies are time-consuming and consequently reduce their possibilities of integration into advanced metaheuristics. Then, we investigate ways to reduce their computational cost by approximation. Empirical studies on NK landscapes allow the identification of move criteria that offer good tradeoffs between the quality of the local optima attained and the computational time needed to reach them. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|