Enhanced genetic algorithms in constrained search spaces with emphasis in parallel environments
Venkataramana Kommu, Irith Pomeranz · 1993
This thesis investigates the applicability of an adaptive approach based on evolution, the Genetic Algorithms, towards problems occurring in the area of design automation. Due to advances in fabrication technology, the designs have become large and complex and there has been considerable interest in developing an efficient heuristic methodology to solve these problems. The Genetic Algorithm is a potentially efficient algorithm to solve these problems, because it explores various solution sub-spaces in parallel. However, the design problems have constrained search spaces and a direct application of the Genetic Algorithm to these problems will not produce competent solutions. This thesis investigates methods to enhance the performance of the Genetic Algorithms in these search spaces both theoretically and in application domains. Distributed computing over a network of work stations has become an attractive idea because of easy availability of work stations. The Genetic Algorithm is easily parallelizable and the process of genetic optimization can be further improved in a parallel environment. This forms our motivation behind the study of the Parallel Genetic Algorithm, and its properties. A theoretical investigation of the Parallel Genetic Algorithm was carried out by extending the decision theory model, then k-armed bandit model, to the parallel environment. The results show that the Parallel Genetic Algorithm is indeed more efficient that the sequential Genetic Algorithm in its search. The theoretical investigation also provides criteria for a proper selection of the parameters of the Parallel Genetic Algorithm. In addition to the theoretical investigations, this thesis describes the application of the Genetic Algorithm and the Parallel Genetic Algorithm to the Vertex Cover and the Circuit Segmentation problems. Two applications of the Circuit Segmentation problem, for pseudo-exhaustive testing and for technology mapping in field-programmable gate arrays are detailed. Our implementation of the Genetic Algorithm to these problems also provide guidelines that could be used to solve other applications using the Genetic Algorithm. Experimental results are presented to demonstrate the effectiveness of our methods in solving these constrained problems.