.png){kind=icon}
.png){kind=icon}
Return
A diversity-aware memetic algorithm for the linear ordering Problem
.png){kind=icon}
PRE
AI
DOI：10.1007/s12293-022-00378-5.png)
.png){kind=icon}
Original request for help.png){kind=icon}
Share.png){kind=icon}
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
Journal
IF:
2.3
Papers:
447
Citations:
718