Preventing premature convergence to local optima in genetic algorithms via random offspring generation

Abstract

The Genetic Algorithms (GAs) paradigm is being used increasingly in search and optimization problems. The method has shown to be efficient and robust in a considerable number of scientific domains, where the complexity and cardinality of the problems considered elected themselves as key factors to be taken into account. However, there are still some insufficiencies; indeed, one of the major problems usually associated with the use of GAs is the premature convergence to solutions coding local optima of the objective function. The problem is tightly related with the loss of genetic diversity of the GA's population, being the cause of a decrease on the quality of the solutions found. Out of question, this fact has lead to the development of different techniques aiming to solve, or at least to minimize the problem; traditional methods usually work to maintain a certain degree of genetic diversity on the target populations, without affecting the convergence process of the GA. In one's work, some of these techniques are compared and an innovative one, the Random Offspring Generation, is presented and evaluated in its merits. The Traveling Salesman Problem is used as a benchmark.