Title

Replicators, majorization and probabilistic databases: New approaches for the analysis of evolutionary algorithms

Date of Award

1998

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Kishan Mehrotra

Keywords

Majorization, Replicators, Probabilistic databases, Evolutionary algorithms

Subject Categories

Computer Sciences

Abstract

The research described in this thesis is a novel examination of evolutionary algorithms using three inter-related frameworks: Replicator models, Majorization processes, and Probabilistic database theory. Each framework is used to study a particular problem in the area of evolutionary algorithms, thereby illustrating the kind of problems for which the framework may apply. Thus, replicator selection models are used to study the optimization capabilities of evolutionary algorithms. New techniques are developed to use replicator selection systems to discover sub-optimal solutions for large graph instances (50,000 nodes plus) of the NP-complete graph bisection problem. Majorization theory is used to develop a unified interpretation of selection, mutation and crossover operators as majorization processes, differing in directionality and dimensionality. Probabilistic databases are used to analyze the problem of dependency in genetic algorithms (GAs). Specifically, the selection and crossover operators are shown to increase functional and multivalued dependencies in a GA population. The problem of deception is re-analyzed in the context of Saari's method and its deep connection with Simpson's paradox and other decision-theoretic issues exhibited. In place of deception, the database theoretic concept of reconstructability is offered as a theoretically more tractable and practically more meaningful substitute.

Access

Surface provides description only. Full text is available to ProQuest subscribers. Ask your Librarian for assistance.

http://libezproxy.syr.edu/login?url=http://proquest.umi.com/pqdweb?did=732842201&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS