Route Planning with GA*

In previous work we proposed a new evolutionary algorithm, GA*, which incorporates features of both the classical search algorithm A* and genetic algorithms. In this paper we describe the application of GA* to a hard optimisation problem, route planning in complex terrains for Computer Generated Forces (CGF). We report the performance of the algorithm on a large number of route-planning problems and compare its performance with that of a standard GA and classical search techniques. Our results indicate that the plans produced by GA* are comparable in cost with those produced by a standard GA but require an order of magnitude fewer fitness evaluations, resulting in a significant speedup