A Multi-parent Memetic Algorithm for the Linear Ordering Problem
This work addresses a classic combinatorial optimization problem, offering incremental improvements for researchers and practitioners in optimization.
The paper tackles the Linear Ordering Problem by proposing a multi-parent memetic algorithm, which improved solutions for 66 out of 255 instances with unknown optima and matched previous best results for 163 instances.
In this paper, we present a multi-parent memetic algorithm (denoted by MPM) for solving the classic Linear Ordering Problem (LOP). The MPM algorithm integrates in particular a multi-parent recombination operator for generating offspring solutions and a distance-and-quality based criterion for pool updating. Our MPM algorithm is assessed on 8 sets of 484 widely used LOP instances and compared with several state-of-the-art algorithms in the literature, showing the efficacy of the MPM algorithm. Specifically, for the 255 instances whose optimal solutions are unknown, the MPM is able to detect better solutions than the previous best-known ones for 66 instances, while matching the previous best-known results for 163 instances. Furthermore, some additional experiments are carried out to analyze the key elements and important parameters of MPM.