Genetic algorithms with dynamic structures: a new approach for solving network problems

摘要

Networks offer a good tool for the evaluation of manufacturing and service decisions. The cost involved in the optimization of routes, assemblies, projects, sequences, schedules and other applications is usually affected by variable and probabilistic conditions. This paper presents a new algorithm called "Stochastic Shortest Path Genetic Algorithm" (SSPGA). This algorithm is an optimization technique that uses simulation and genetic algorithms. Simulation creates the necessary dynamic conditions to add variability and probability to a model. SSPGA uses dynamic structures that can be shared by deterministic and probabilistic networks and also for creating the set of possible solutions that evolve in a guided search. SSPGA reduces the required memory cells compared with matrix techniques and traditional chromosome representations. Network models such as the shortest path may use dynamic structures because a shortest path usually involves a subset of the nodes contained in a network. The tests performed over networks with stochastic conditions reduced the processing time and the amount of modeling time because there is no need to change the original procedure or basic definition of the network. Previous attempts to solve the shortest path problem used algorithms that limited their capacity for making changes and sometimes created intractable models.