An Online Learning-based Metaheuristic for Solving Combinatorial Optimization Problems

EasyChair Preprint 2766

Abstract

Combinatorial optimization problems (COPs) are a complex class of optimization problems
with discrete decision variables and finite search space. They have a wide application in many
real-world problems, including transportation, scheduling, network design, assignment, and so
on. Many COPs belong to the NP-Hard class of problems, which require exponential time
to be solved to optimality. For these problems, metaheuristics (MHs) provide acceptable
solutions in reasonable computation times, and are often good substitutes for exact algorithms.

Machine learning (ML) techniques are also good approaches for solving COPs. In this
regard, the hybridization of ML techniques with MHs is an emerging research field that has
attracted numerous researchers in recent years. ML techniques can be used to improve
the performance of MHs, particularly for solving complex COPs. In the hybrid framework,
ML techniques are used to extract knowledge from available data, and inject it into MHs, with
the aim of reducing computational time, and improving solutions quality.

The goal of this contribution is twofold: 1) Proposing a state of the art review on hybridization
methods between MHs and ML; and 2) Introducing the concept of a novel approach focused on
online learning in population-based MHs.

Keyphrases: Hybridization, Metaheuristics, combinatorial optimization, machine learning

@booklet{EasyChair:2766,
  author    = {Maryam Karimi-Mamaghan and Mehrdad Mohammadi and Bastien Pasdeloup and Romain Billot and Patrick Meyer},
  title     = {An Online Learning-based Metaheuristic for Solving Combinatorial Optimization Problems},
  howpublished = {EasyChair Preprint 2766},
  year      = {EasyChair, 2020}}