Algoritmos evolucionários eficientes para otimização de redes

Abstract

This work presents new tools to help in the solution of network optimization problems. Firstly, some concepts of continuous spaces have been extended to the discrete space, where the networks are defined. These concepts grant to the network space interesting properties, such as spatial representations, relative position calculus, distance measurements and direction definitions. They make possible the implementation of techniques which are usually employed only in continuous problems, such as dispersion analysis, local searches, unidimensional optimizations, etc, which can be embedded in optimization algorithms through evolutionary operators. These operators are used to build two algorithms: a Genetic Algorithm and a Clonal Selection Algorithm. These algorithms have been employed for optimization of two classical problems which are known to be difficult, and two practical cases. Besides, three problem specific algorithms are presented, for three situations of distribution system design: joint facility location and network topology design, multi-objective design of distribution systems and system expansion scheduling. These algorithms are based on operators which have been built taking into account the characteristics of problem. The results show that the developed tools are useful for network optimization, and that they can obtain good solutions in problems which could not be solved by traditional methods.