Multiresolution aspects in genetic algorithms

The goal of this research was to introduce and study the multiresolution paradigm within the framework of genetic algorithms, a very popular and yet intriguing search and optimization method inspired from the rules of evolutionary genetics. It is generally accepted that genetic algorithms are methods with great potential in search and optimization problems, due to their robustness, good capabilities of exploring large search spaces, and, to some degree, immunity to the effect of premature convergence. However, their typically high computational cost has severely restricted their access to areas of large interest, such as image processing. A wide variety of adaptations are reported in the literature that attempt to compensate for these limitations. However, the eventual increase in performance obtained by these adaptations was achieved at the expense of some intrinsic features of genetic algorithms. This research introduces a much more general concept, namely the multiresolution genetic algorithms, built on the foundations of a coarse-to-fine evolution strategy implemented by a novel genetic operator called cloning. The cloning operator cannot be described by a general formula and the actual mechanism associated with cloning is application dependent. Several experiments and different cloning techniques have been performed and are comparatively discussed. The cloning operator can perform well in a large variety of conditions, as demonstrated by the experiments performed and reported in this study. Three classes of distinct applications were employed and comparative experiments were performed in order to evaluate the performances of the genetic algorithm with cloning against those of a standard genetic algorithm. The results clearly demonstrate that the cloning operator improves dramatically the convergence speed of the process. Furthermore, cloning was a good solution in an experiment of solving the shortest path problem in planar graphs although resolution does not have a physical meaning in this application.; This conclusion proves that the novel genetic operator introduced in this study is robust and has general applicability. The cloning operator demonstrated that it could be an important factor in enhancing the performances of genetic algorithms in a variety of applications and, therefore, will have relevance to further research in this area.