Considerations for rapidly converging genetic algorithms designed for application to problems with expensive evaluation functions
"A genetic algorithm is a technique designed to search large problem spaces using the Darwinian concepts of evolution. Solution representations are treated as living organisms. The procedure attempts to evolve increasingly superior solutions. As in natural genetics, however, there is no guarantee that the optimum organism will be produced.
One of the problems in producing optimal organisms in a genetic algorithm is the difficulty of premature convergence. Premature convergence occurs when the organisms converge in similarity to a pattern which is sub-optimal, but insufficient genetic material is present to continue the search beyond this sub-optimal level, called a local maximum.
The prevention of premature convergence of the organisms is crucial to the success of most genetic algorithms. In order to prevent such convergence, numerous operators have been developed and refined. All such operators, however, rely on the property of the underlying problem that the evaluation of individuals is a computationally inexpensive process.
In this paper, the design of genetic algorithms which intentionally converge rapidly is addressed. The design considerations are outlined, and the concept is applied to an NP-Complete problem, known as a Crozzle, which does not have an inexpensive evaluation function. This property would normally make the Crozzle unsuitable for processing by a genetic algorithm. It is shown that a rapidly converging genetic algorithm can successfully reduce the effective complexity of the problem"--Abstract, page iii.
Wilkerson, Ralph W.
Zobrist, George W. (George Winston), 1934-
Ho, C. Y. (Chung You), 1933-1988
St. Clair, Daniel C.
Ph. D. in Computer Science
University of Missouri--Rolla
viii, 102 pages
Note about bibliography
Includes bibliographical references (pages 94-101).
© 1993 Richard Patrick Rankin, All rights reserved.
Dissertation - Restricted Access
Print OCLC #
Link to Catalog Record
Electronic access to the full-text of this document is restricted to Missouri S&T users. Otherwise, request this publication directly from Missouri S&T Library or contact your local library.http://merlin.lib.umsystem.edu/record=b2668555~S5
Rankin, Richard Patrick, "Considerations for rapidly converging genetic algorithms designed for application to problems with expensive evaluation functions" (1993). Doctoral Dissertations. 1012.
Share My Dissertation If you are the author of this work and would like to grant permission to make it openly accessible to all, please click the button above.
A report which is substantially this dissertation is available here for download.