Path Optimization for Multiple Objectives in Directed Graphs using Genetic Algorithms

Abstract — This paper presents a genetic algorithmic ap-proach for finding efficient paths in directed graphs when optimizing multiple objectives. Its aim is to provide solutions for the game of Animat where an agent must evolve paths to achieve the greatest amount of bombs in the fewest moves as possible. The nature of this problem suggests agents with memory abilities to choose different edges from a vertex v such that each time v is reached, the agent can avoid cycles and be encouraged to keep searching for bombs all over the directed graph. This approach was tested on several random scenarios and also on specially designed ones with very encouraging results. The multi-objective genetic algorithm chosen to evolve paths was SPEA2 using one-point crossover and low mutation to allow genetic diversity of the population and an enhanced convergence rate. Results are compared with an implementation for the same game using Ant Colony Optimization. I