From fitness landscapes evolution to automatic local search algorithm generation. (23rd November 2020)

• Record Type: Journal Article
• Authors: Hénaux, Vincent; Goëffon, Adrien; Saubion, Frédéric
• Editors: Hoos, Holger; Jourdan, Laetitia; Kessaci, Marie‐Eléonore; Stützle, Thomas; Veerapen, Nadarajen
• Is Part Of: International transactions in operational research. Volume 29:Number 5(2022)
• Page Start: 2737
• Page End: 2760
• Publication Date: 2020-11-23
• Subjects: local search -- hill‐climbing -- fitness landscapes -- NK model -- evolution strategies -- discrete optimization; Operations research -- Periodicals; 003
• DOI: 10.1111/itor.12906
• Languages: English
• ISSNs: 0969-6016

Abstract

Abstract: Solving an optimization problem with local search algorithms consists of evolving a solution by means of an evaluation function, which is usually directly derived from the objective function of the problem. The resolution difficulties appear when the fitness landscape naturally induced by the problem instance is not perfectly exploitable, has a certain level of ruggedness, and therefore has many local optima. We propose here to shift the problem of searching a solution, from searching an evaluation function that maximizes the efficiency of the corresponding local search algorithm. In particular, we propose an evolution strategy scheme designed to evolve fitness functions and their corresponding fitness landscapes. The purpose is to generate a local search algorithm guided by an evolved fitness function specifically dedicated to tackling the problem instance to solve. Here, we focus on hill‐climbing algorithms and NK landscapes and show that such a strategy can be efficient to generate relevant search algorithms whose components are not problem‐specific.