Feature-based search space characterisation for data-driven adaptive operator selection

Mehmet Emin Aydin, Rafet Durgut, Abdur Rakib, Hisham Ihshaish

Research output: Contribution to journalArticlepeer-review

44 Downloads (Pure)

Abstract

Combinatorial optimisation problems are known as unpredictable and challenging due to their nature and complexity. One way to reduce the unpredictability of such problems is to identify features and the characteristics that can be utilised to guide the search using domain-knowledge and act accordingly. Many problem solving algorithms use multiple complementary operators in patterns to handle such unpredictable cases. A well-characterised search space may help to evaluate the problem states better and select/apply a neighbourhood operator to generate more productive new problem states that allow for a smoother path to the final/optimum solutions. This applies to the algorithms that use multiple operators to solve problems. However, the remaining challenge is determining how to select an operator in an optimal way from the set of operators while taking the search space conditions into consideration. Recent research shows the success of adaptive operator selection to address this problem. However, efficiency and scalability issues still persist in this regard. In addition, selecting the most representative features remains crucial in addressing problem complexity and inducing commonality for transferring experience across domains. This paper investigates if a problem can be represented by a number of features identified by landscape analysis, and whether an adaptive operator selection scheme can be constructed using Machine Learning (ML) techniques to address the efficiency and scalability issues. The proposed method determines the optimal categorisation by analysing the predictivity of a set of features using the most well-known supervised ML techniques. The identified set of features is then used to construct an adaptive operator selection scheme. The findings of the experiments demonstrate that supervised ML algorithms are highly effective when building adaptable operator selectors.
Original languageEnglish
Pages (from-to)99-114
Number of pages16
JournalEvolving Systems
Volume15
Issue number1
Early online date22 Dec 2023
DOIs
Publication statusPublished - Feb 2024

Bibliographical note

This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article’s Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article’s Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/

Keywords

  • Adaptive Operator Selection
  • Search Space Characterisation
  • Supervised Machine Learning
  • Artificial Bee Colonies
  • Binary Optimisation

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint

Dive into the research topics of 'Feature-based search space characterisation for data-driven adaptive operator selection'. Together they form a unique fingerprint.

Cite this