A genetic algorithm for linear ordering problem using an approximate fitness evaluation
Jinhyun Kim, Byung-Ro Moon · 2014
Genetic algorithms are widely used to solve combinatorial optimization problems, but they often take a long time. Usually, generating and evaluating a large number of different solutions spend most of the running time. We propose a genetic algorithm for the linear ordering problem which uses an approximate fitness evaluation. We use a part of the edges to compute the fitness function value, and the number of the edges for this is gradually increased during the evolutionary process. We present experimental results on the benchmark library LOLIB. The approximation scheme reduced the running time without loss of solution quality in general.