This item is only available for download by members of the University of Illinois community. Students, faculty, and staff at the U of I may log in with your NetID and password to view the item. If you are trying to access an Illinois-restricted dissertation or thesis, you can request a copy through your library's Inter-Library Loan office or purchase a copy directly from ProQuest.
Permalink
https://hdl.handle.net/2142/66449
Description
Title
Evolutionary Structure and Search
Author(s)
Rada, Roy Frank
Issue Date
1981
Department of Study
Computer Science
Discipline
Computer Science
Degree Granting Institution
University of Illinois at Urbana-Champaign
Degree Name
Ph.D.
Degree Level
Dissertation
Keyword(s)
Computer Science
Language
eng
Abstract
Can machines with evolutionary properties be useful? In addressing this question, this paper covers two major topics. First, the major barriers to the design of general-purpose evolutionary machines are analyzed. Then, in a constrained problem, evolution is viewed as a search for an optimum in a vast space. Classes of search algorithms are defined, and the performance of each algorithm is related to the structure in search spaces.
I have formalized a framework from which attempts to design evolutionary systems might proceed. Of particular importance are the criteria, based on the notion of perpetuation, which a system's behavior must satisfy in order to be considered evolutionary. By my standards, no computer programs have been designed that manifest meaningful evolutionary behavior.
Evolutionary systems are commonly considered to have two fundamental properties: (1)elements (or organisms) in the system reproduce with mutation and (2)only the fit elements survive. I propose that evolutionary systems have a third property--the property of gradualness. A system has gradualness, if, and only if, small changes in an element usually lead to small changes in that element's fitness. Computer programs seem to lack this property, as one randomly changed instruction usually changes program behavior drastically.
For the constrained problem the elements of the power set S are the alternatives in a search space. Each element of the set has a value, and the goal of a search is to find an element with near-maximum value. The ease of the search depends on the relationships between elements and their values. If high-valued elements of cardinality i (recall that elements of S are themselves sets) are subsets of high-valued elements of cardinality i + l, then the search space has a kind of structure that should facilitate search.
A search algorithm might generate a series, S'(l),...,S'(k), of samples in S, where all the elements in S'(i) have cardinality i. I propose several classes of search algorithms, where each algorithm A(j) in the class A generates S'(i + l) by performing various operations on the j highest-valued elements in S'(i). The set SA(j) of search spaces on which A(j) performs optimally is different from the set SA(j + l) of search spaces on which A(j + l) performs optimally. The average structure in SA(j) is greater than the average structure in SA(j + l).
A theory of searching might be developed from the structure-search approach. The approach can also be directly applied to practical problems. Relationships between structure and search are evident in combinatorial problems (such as the traveling salesman) and in artificial intelligence problems (such as automated medical diagnosis).
In summary of the two major points, this paper: (1)presents an intellectual synthesis of work on evolutionary machines that shows the need for gradualness in evolutionary spaces, and (2)defines a set of search algorithms and search spaces and then relates performance of the algorithms to the structure of the search spaces.
Use this login method if you
don't
have an
@illinois.edu
email address.
(Oops, I do have one)
IDEALS migrated to a new platform on June 23, 2022. If you created
your account prior to this date, you will have to reset your password
using the forgot-password link below.