Title

Linkage crossover operator for genetic algorithms

Date of Award

1999

Degree Type

Dissertation

Degree Name

Doctor of Philosophy (PhD)

Department

Electrical Engineering and Computer Science

Advisor(s)

Chilukuri K. Mohan

Keywords

Linkage, Crossover operator, Genetic algorithms

Subject Categories

Computer Sciences | Electrical and Computer Engineering | Engineering | Physical Sciences and Mathematics

Abstract

Problem-specific knowledge is often implemented in search algorithms using heuristics to determine which search paths are to be explored at any given instant. As in other search methods, utilizing this knowledge will lead a genetic algorithm (GA) faster towards better results. In many problems, crucial knowledge is to be found not in individual components, but in interrelations between those components. For such problems, we develop an interrelation (linkage) based crossover operator that has the advantage of liberating GAs from the constraints imposed by the fixed representations generally chosen for problems. The strengths of linkages between components of a chromosomal structure can be explicitly represented in a linkage matrix and used in the reproduction step to generate new individuals.

For some problems, such a linkage matrix is known a priori from the nature of the problem. In other cases, the linkage matrix may be learned by successive minor adaptations during the execution of the evolutionary algorithm. We present four linkage adaptation procedures that work along with the linkage based crossover.

We demonstrate the success of such an approach for several benchmark problems representing two types of problems: One where the linkage structure is well-defined and is easily represented as linkage matrix in advance, and another where the linkage structure is not well-known. Linkage adaptation procedures show success in learning the right linkage structure for a given problem, and obtaining better results than the standard crossover operators. This approach is shown to be robust to different variations of GA parameter values.

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=731782751&sid=1&Fmt=2&clientId=3739&RQT=309&VName=PQD

Link to Full Text

Share

COinS