Files in this item



application/pdf8114463.pdf (6MB)Restricted to U of Illinois
(no description provided)PDF


Title:Evolutionary Structure and Search
Author(s):Rada, Roy Frank
Department / Program:Computer Science
Discipline:Computer Science
Degree Granting Institution:University of Illinois at Urbana-Champaign
Subject(s):Computer Science
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.
Issue Date:1981
Description:169 p.
Thesis (Ph.D.)--University of Illinois at Urbana-Champaign, 1981.
Other Identifier(s):(UMI)AAI8114463
Date Available in IDEALS:2014-12-13
Date Deposited:1981

This item appears in the following Collection(s)

Item Statistics