Improving the Performance of Genetic Algorithms in Automated Discovery of Parameters

Abstract

Genetic Algorithms are generally compute intensive procedures that require the evaluation of many candidate solutions to a given problem. In the application area we study (routing and scheduling), the genetic algorithm sets parameters for a mathematical heuristic. To reduce the computational overhead of this approach, we developed three mechanisms for improving the performance of the genetic search. First, we employ a method of using multiple sharing evaluation functions, permitting the parallel investigation of multiple peaks in the search space. Second, we carry out function evaluation in parallel, using a network of heterogeneous processors. Third, a neural network system is employed to inject heuristic knowledge into the initial population of the genetic algorithm, resulting in relatively fast convergence. When the methods are used together, the result is high quality solutions with considerable speedup in computational time. Our overall system, called XVRP-PGA, is a distributed software system that demonstrates the increased efficiency of genetic algorithms in the automated discovery of parameters for mathematical heuristics, in the domain of computer-aided vehicle routing and scheduling problems.