In the past several years, evolutionary algorithms such as simulated annealing and the genetic algorithm have received increasing recognition for their ability to optimize arbitrary functions. These algorithms rely on the process of Darwinian evolution, which promotes highly successful solutions that result from random variation. This variation is produced by the random operators of mutation and/or recombination. These operators make no attempt to determine which alleles or combinations of alleles are most likely to yield overall fitness improvement. This thesis will explore the benefits that can be gained by utilizing a direct analysis of the correlations between fitness and alleles or allele combinations to intelligently and purposefully design new highly-fit solutions. An algorithm is developed in this thesis that explicitly analyzes allele-fitness distributions and then uses the information gained from this analysis to purposefully construct new individuals bit by bit''. Explicit measurements of gene significance'' (the effect of a particular gene upon fitness) allows the algorithm to adaptively decide when conditional allele-fitness distributions are necessary in order to correctly track important allele interactions. A new operator---the restriction'' operator---allows the algorithm to simply and quickly compute allele selection probabilities using these conditional fitness distributions. The resulting feedback from the evaluation of new individuals is used to update the statistics and therefore guide the creation of increasingly better individuals. Since explicit analysis and creation is used to guide this evolutionary process, it is not a form of Darwinian evolution. It is a pro-active, contrived process that attempts to intelligently create better individuals through the use of a detailed analysis of historical data. It is therefore a eugenic evolutionary process, and thus this algorithm is called the Eugenic Algorithm'' (EuA). The EuA was tested on a number of benchmark problems (some of which are NP-complete) and compared to widely recognized evolutionary optimization techniques such as simulated annealing and genetic algorithms. The results of these tests are very promising, as the EuA optimized all the problems at a very high level of performance, and did so much more consistently than the other algorithms. In addition, the operation of EuA was very helpful in illustrating the structure of the test problems. The development of the EuA is a very significant step to statistically justified combinatorial optimization, paving the way to the creation of optimization algorithms that make more intelligent use of the information that is available to them. This new evolutionary paradigm, eugenic evolution will lead to faster and more accurate combinatorial optimization and to a greater understanding of the structure of combinatorial optimization problems.

PDF, PS

Masters Thesis, Department of Computer Sciences, The University of Texas at Austin, 1998. 126. Technical Report AI98-268.

@MastersThesis{prior:ms, title={Eugenic Evolution For Combinatorial Optimization}, author={John W. Prior}, school={Department of Computer Sciences, The University of Texas at Austin}, pages={126}, note={Technical Report AI98-268}, url="http://nn.cs.utexas.edu/?prior:ms98", year={1998} }