Content area
Full Text
Abstract
The optimization by genetic algorithms often comes along with premature convergence bias, especially in the multimodal problems. In the paper, we propose and test two mechanisms to avoid the premature convergence of genetic algorithms by preserving the population diversity in two different manners. These are the dynamic application of many genetic operators, based on the average progress, and the population partial reinitialization. The mechanisms were tested by implementing them in the NSGA_II algorithm, applied to one of the most difficult job shop scheduling test problems, ft10. The comparative analysis between the new algorithm and the NSGA_II in the absence of the submitted mechanisms, alongside with an elitist and the canonic genetic algorithm, proves the usability of both proposed mechanisms.
Key words: genetic algorithms, optimization, progress of the genetic operators, job shop scheduling
(ProQuest: ... denotes formula omitted.)
Introduction
Over the last thirty years, the genetic algorithms and their hybrids have been applied to various optimization problems, by reason of their multiple advantages: free derivative characteristics, simple preparation of the optimization model, the parallel nature of the search etc. One crucial issue for the genetic algorithm success, especially for the difficult problems, is to avoid the premature convergence of the algorithm to suboptimal regions.
The premature convergence of a genetic algorithm arises when the genes of some high rated individuals quickly attain to dominate the population, constraining it to converge to a local optimum. In this case, the genetic operators can not produce any more descendents better that the parents (Fogel, 1994); the algorithm ability to continue the search for better solutions is therefore substantially reduced.
To avoid the premature convergence, in a genetic algorithm is imperative to preserve the population diversity during the evolution. In other words, the population diversity ensures avoiding the premature convergence. Among the methods used for this, we can enumerate: restricted selection, dynamic application of mutation, constraints for crossover and mutation probabilities, stochastic universal sampling, variable fitness assignment, population partial reinitialization, individuals grouping methods, restricted mating, elitism, symbiogenesis, species conserving techniques, ranking sort based on Pareto dominance, local search based on diversity. All these methods are heuristics by definition and their effects vary for different problems.
In the real world, there are difficult instances where no single method...