Considerations for rapidly converging genetic algorithms designed for application to problems with expensive evaluation functions

Author

Richard Patrick Rankin

Abstract

"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.

Advisor(s)

Wilkerson, Ralph W.

Committee Member(s)

Zobrist, George W. (George Winston), 1934-
Ho, C. Y. (Chung You), 1933-1988
St. Clair, Daniel C.
Insall, Matt

Department(s)

Computer Science

Degree Name

Ph. D. in Computer Science

Comments

A report which is substantially this dissertation is available here for download.

Publisher

University of Missouri--Rolla

Publication Date

Spring 1993

Pagination

viii, 102 pages

Note about bibliography

Includes bibliographical references (pages 94-101).

Rights

© 1993 Richard Patrick Rankin, All rights reserved.

Document Type

Dissertation - Restricted Access

File Type

text

Language

English

Thesis Number

T 6546

Print OCLC #

29303042

Recommended Citation

Rankin, Richard Patrick, "Considerations for rapidly converging genetic algorithms designed for application to problems with expensive evaluation functions" (1993). Doctoral Dissertations. 1012.
https://scholarsmine.mst.edu/doctoral_dissertations/1012