Skip navigation

The use of some non-minimal representations to improve the effectiveness of genetic algorithms

The use of some non-minimal representations to improve the effectiveness of genetic algorithms

Robbins, Phil (1995) The use of some non-minimal representations to improve the effectiveness of genetic algorithms. PhD thesis, University of Greenwich.

[img] PDF
Phil_F._Robbins_1995.pdf - Published Version
Restricted to Repository staff only until 16 March 2019.
Available under License Creative Commons Attribution Non-commercial No Derivatives.

Download (6MB)

Abstract

In the unitation representation used in genetic algorithms, the number of genotypes that map onto each phenotype varies greatly. This leads to an attractor in phenotype space which impairs the performance of the genetic algorithm. The attractor is illustrated theoretically and empirically. A new representation, called the length varying representation (LVR), allows unitation chromosomes of varying length (and hence with a variety of attractors) to coexist. Chromosomes whose lengths yield attractors close to optima come to dominate the population. The LVR is shown to be more effective than the unitation representation against a variety of fitness functions. However, the LVR preferentially converges towards the low end of phenotype space. The phenotype shift representation (PSR), which retains the ability of the LVR to select for attractors that are close to optima, whilst using a fixed length chromosome and thus avoiding the asymmetries inherent in the LVR, is defined. The PSR is more effective than the LVR and the results compare favourably with previously published results from eight other algorithms. The internal operation of the PSR is investigated. The PSR is extended to cover multi-dimensional problems.

The premise that improvements in performance may be attained by the insertion of introns, non-coding sequences affecting linkage, into traditional bit string chromosomes is investigated. In this investigation, using a population size of 50, there was no evidence of improvement in performance. However, the position of the optima relative to the hamming cliffs is shown to have a major effect on the performance of the genetic algorithm using the binary representation, and the inadequacy of the traditional crossover and mutation operators in this context is demonstrated. Also, the disallowance of duplicate population members was found to improve performance over the standard generational replacement strategy in all trials.

Item Type: Thesis (PhD)
Additional Information: uk.bl.ethos.262615
Uncontrolled Keywords: genetic algorithms, length varying representation, problem solving, computer software, optimization, imitation representation, attractor in imitation, space, cardinality, linkage, epistasis, introns, hamming cliff, reproduction strategies,
Subjects: Q Science > QA Mathematics
Q Science > QA Mathematics > QA76 Computer software
Pre-2014 Departments: School of Computing & Mathematical Sciences
School of Computing & Mathematical Sciences > Department of Mathematical Sciences
Last Modified: 13 Mar 2018 16:12
Selected for GREAT 2016: None
Selected for GREAT 2017: None
Selected for GREAT 2018: None
URI: http://gala.gre.ac.uk/id/eprint/6281

Actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics