How to exploit fitness landscape properties of timetabling problem: A newoperator for quantum evolutionary algorithm

Research output: Contribution to journalArticlepeer-review

2 Downloads (Pure)

Abstract

The fitness landscape of the timetabling problems is analyzed in this paper to provide some insight into theproperties of the problem. The analyses suggest that the good solutions are clustered in the search space andthere is a correlation between the fitness of a local optimum and its distance to the best solution. Inspiredby these findings, a new operator for Quantum Evolutionary Algorithms is proposed which, during the searchprocess, collects information about the fitness landscape and tried to capture the backbone structure of thelandscape. The knowledge it has collected is used to guide the search process towards a better region in thesearch space. The proposed algorithm consists of two phases. The first phase uses a tabu mechanism to collectinformation about the fitness landscape. In the second phase, the collected data are processed to guide thealgorithm towards better regions in the search space. The algorithm clusters the good solutions it has foundin its previous search process. Then when the population is converged and trapped in a local optimum, itis divided into sub-populations and each sub-population is designated to a cluster. The information in thedatabase is then used to reinitialize the q-individuals, so they represent better regions in the search space.This way the population maintains diversity and by capturing the fitness landscape structure, the algorithmis guided towards better regions in the search space. The algorithm is compared with some state-of-the-artalgorithms from PATAT competition conferences and experimental results are presented.
Original languageEnglish
Article number114211
Number of pages22
JournalExpert Systems with Applications
Volume168
Early online date4 Nov 2020
DOIs
Publication statusE-pub ahead of print - 4 Nov 2020

Keywords

  • Fitness landscape analysis
  • Quantum evolutionary algorithms
  • Timetabling-coloring

Fingerprint

Dive into the research topics of 'How to exploit fitness landscape properties of timetabling problem: A newoperator for quantum evolutionary algorithm'. Together they form a unique fingerprint.

Cite this