• English
    • français
  • Help
  •  | 
  • Contact
  •  | 
  • About
  •  | 
  • Login
  • HAL portal
  •  | 
  • Pages Pro
  • EN
  •  / 
  • FR
View Item 
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
  •   LillOA Home
  • Liste des unités
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Inferring Future Landscapes: Sampling the ...
  • BibTeX
  • CSV
  • Excel
  • RIS

Document type :
Article dans une revue scientifique
DOI :
10.1162/evco_a_00271
Title :
Inferring Future Landscapes: Sampling the Local Optima Level
Author(s) :
Thomson, Sarah [Auteur]
University of Stirling
Ochoa, Gabriela [Auteur]
University of Stirling
Verel, Sébastien [Auteur]
Laboratoire d'Informatique Signal et Image de la Côte d'Opale [LISIC]
Veerapen, Nadarajen [Auteur]
Operational Research, Knowledge And Data [ORKAD]
Journal title :
Evolutionary Computation
Pages :
621-641
Publisher :
Massachusetts Institute of Technology Press (MIT Press)
Publication date :
2020-12
ISSN :
1063-6560
English keyword(s) :
Combinatorial Optimisation
Fitness Landscapes
Local Optima Networks
Funnel Landscapes
HAL domain(s) :
Informatique [cs]/Intelligence artificielle [cs.AI]
Mathématiques [math]/Optimisation et contrôle [math.OC]
English abstract : [en]
Connection patterns among Local Optima Networks (LONs) can inform heuristic design for optimisation. LON research has predominantly required complete enumeration of a fitness landscape, thereby restricting analysis to ...
Show more >
Connection patterns among Local Optima Networks (LONs) can inform heuristic design for optimisation. LON research has predominantly required complete enumeration of a fitness landscape, thereby restricting analysis to problems diminutive in size compared to real-life situations. LON sampling algorithms are therefore important. In this paper, we study LON construction algorithms for the Quadratic Assignment Problem (QAP). Using machine learning, we use estimated LON features to predict search performance for competitive heuristics used in the QAP domain. The results show that by using random forest regression, LON construction algorithms produce fitness landscape features which can explain almost all search variance. We find that LON samples better relate to search than enumerated LONs do. The importance of fitness levels of sampled LONs in search predictions is crystallised. Features from LONs produced by different algorithms are combined in predictions for the first time, with promising results for this 'super-sampling': a model to predict tabu search success explained 99% of variance. Arguments are made for the use-case of each LON algorithm and for combining the exploitative process of one with the exploratory optimisation of the other.Show less >
Language :
Anglais
Peer reviewed article :
Oui
Audience :
Internationale
Popular science :
Non
Collections :
  • Centre de Recherche en Informatique, Signal et Automatique de Lille (CRIStAL) - UMR 9189
Source :
Harvested from HAL
Files
Thumbnail
  • https://direct.mit.edu/evco/article-pdf/28/4/621/1859008/evco_a_00271.pdf
  • Open access
  • Access the document
Thumbnail
  • https://direct.mit.edu/evco/article-pdf/28/4/621/1859008/evco_a_00271.pdf
  • Open access
  • Access the document
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-03035340/document
  • Open access
  • Access the document
Thumbnail
  • https://direct.mit.edu/evco/article-pdf/28/4/621/1859008/evco_a_00271.pdf
  • Open access
  • Access the document
Thumbnail
  • https://direct.mit.edu/evco/article-pdf/28/4/621/1859008/evco_a_00271.pdf
  • Open access
  • Access the document
Thumbnail
  • https://hal.archives-ouvertes.fr/hal-03035340/document
  • Open access
  • Access the document
Thumbnail
  • https://direct.mit.edu/evco/article-pdf/28/4/621/1859008/evco_a_00271.pdf
  • Open access
  • Access the document
Thumbnail
  • https://direct.mit.edu/evco/article-pdf/28/4/621/1859008/evco_a_00271.pdf
  • Open access
  • Access the document
Université de Lille

Mentions légales
Université de Lille © 2017