Login | Register

Problem structure and evolutionary algorithm difficulty

Title:

Problem structure and evolutionary algorithm difficulty

Khor, Susan Lay Choo (2008) Problem structure and evolutionary algorithm difficulty. PhD thesis, Concordia University.

[img]
Preview
Text (application/pdf)
NR45680.pdf - Accepted Version
12MB

Abstract

This study reexamines the Hierarchical-If-And-Only-If (HIFF) problem (of which there are two versions--discrete and continuous) introduced by Watson et al. (1998) to distinguish the evolutionary capability of hill climbers from genetic algorithms. It finds that it is possible to relax some of the conditions stipulated for the structure of the HIFF problem without destroying the ability of the modified problem to distinguish the evolutionary capability of hill climbers from genetic algorithms. In particular, full inter-dependency between problem variables is not necessary, i.e. there need not be an iff constraint between every distinct variable pair. In addition, by reducing variable-to-variable inter-dependencies, the modified HIFF problem becomes more solvable by upGA, a genetic algorithm which does not explicitly maintain population genetic diversity. This is because the modified HIFF problem (called HIFF-M) permits mutation to be effective in a genetic algorithm. The maintenance of sufficient population genetic diversity through means other than mutation was a key component of genetic algorithm success in Watson's work on the HIFF problem. The modular structure of the HIFF problem, along with the inter-dependencies between modules, is credited for the ability of the HIFF problem to distinguish the evolutionary capability of hill climbers from genetic algorithms. However, when the genetic algorithm in question is upGA, this study finds that degree distribution type is a better indicator than modularity of when a problem will be easier for a genetic algorithm than a hill climber to solve. In general, problems with real-world type degree distributions were more easily solved by upGA than by the random mutation hill climber or the macro-mutation hill climber. Suggestions are made for further research in this direction. This study also examines the relationship between hierarchical levels in different HIFF problems. It finds differences in the speed at which levels can optimize relative to one another, the degree of inter-level inter-dependency, and the degree of top-down inter-level conflict. The consequences of these differences for evolutionary algorithm difficulty are discussed.

Divisions:Concordia University > Gina Cody School of Engineering and Computer Science > Computer Science and Software Engineering
Item Type:Thesis (PhD)
Authors:Khor, Susan Lay Choo
Pagination:xvi, 305 leaves : ill. ; 29 cm.
Institution:Concordia University
Degree Name:Ph. D.
Program:Computer Science and Software Engineering
Date:2008
Thesis Supervisor(s):Grogono, P
ID Code:975969
Deposited By: Concordia University Library
Deposited On:22 Jan 2013 16:18
Last Modified:18 Jan 2018 17:41
Related URLs:
All items in Spectrum are protected by copyright, with all rights reserved. The use of items is governed by Spectrum's terms of access.

Repository Staff Only: item control page

Downloads per month over past year

Research related to the current document (at the CORE website)
- Research related to the current document (at the CORE website)
Back to top Back to top