Genetic algorithms and simulation applied to optimization: The stochastic shortest path model

This dissertation develops a new genetic algorithm for solving the shortest path problem. The goal of such an algorithm is to determine the best routes to follow when multiple option decisions are available. The algorithm is applied using simulation on a network model containing stochastic elements. The paths and the corresponding total costs are obtained by adding node by node until the target node is reached. An important milestone in the development of such an algorithm is the definition of a dynamic structure for the network codification. Previous genetic algorithms applied to the optimization of network problems have used a fixed length vector representing the paths (chromosomes). However for the shortest path problem a dynamic structure reduces the chromosome size, the number of possible combinations and the searching time, making it more efficient. The new approach also replaces Goldberg's original random number generator by using one of the most recent developments in random number generators written by Matsumoto (1996). The program is codified using C++ with the standard library, compatible with the standard GCC and MS-Visual C++ compilers. The results suggest that smaller populations may be used in the genetic algorithm's parameters because of the reduced number of combinations created with the dynamic structure. The tests performed over networks with stochastic conditions reduced the amount of modeling time because there is no need to change the original procedure or basic definition of the network. The simulation procedure to create the paths also accounts for dependency among the involved nodes in a path.