A diversity-aware memetic algorithm for the linear ordering Problem

Lázaro Lugo

doi:10.1007/s12293-022-00378-5

Return

A diversity-aware memetic algorithm for the linear ordering Problem

2022-10-16

PRE

Lázaro Lugo

Carlos Segura *

Gara Miranda

DOI：10.1007/s12293-022-00378-5

Original

Original request for help

Save

Abstract

En 中文

The Linear Ordering Problem (LOP) is a very popular NP-hard combinatorial optimization problem with many practical applications that may require the use of large instances. The Linear Ordering Library (LOLIB) gathers a set of standard benchmarks that are widely used in validating solvers for the LOP. Among them, xLOLIB2 collects some of the largest and most challenging instances in the current literature. In this work, we present new best-known solutions for each of the 200 complex instances that comprise xLOLIB2 and for the other 93 instances of the benchmarks with smaller sizes. This important advance in the field of LOP has been made possible due to the development of a novel memetic algorithm (MA) that was designed by taking into account some of the weaknesses of state-of-the-art LOP solvers. In particular, one of the keys to success is that the novel proposal allows for a gradual shift from exploration to exploitation. This is done using the novel Best Non-Penalized (BNP) replacement strategy. BNP selects the survivors by taking into account the quality, the Spearman's footrule distance, the stopping criterion, and the elapsed period of execution simultaneously. The novel diversity-aware proposal is called the memetic algorithm with explicit diversity management (MA-EDM) and extensive comparisons against state-of-the-art techniques provide insights into the reasons for the superiority of MA-EDM.

Keywords:

Linear ordering problem

Diversity-aware optimizers

Memetic algorithms

Combinatorial optimization