Please use this identifier to cite or link to this item: http://hdl.handle.net/10397/2762
Title: A graph based evolutionary algorithm
Authors: Wong, Shing-yue Samuel
Keywords: Hong Kong Polytechnic University -- Dissertations
Evolutionary computation
Neural networks (Computer science)
Genetic programming (Computer science)
Graph algorithms
Issue Date: 2009
Publisher: The Hong Kong Polytechnic University
Abstract: A number of different Evolutionary Algorithms (EAs) have been developed to evolve different kinds of graph structures. The most common being those that evolve Artificial Neural Network (ANN) architectures and those that evolve trees. In other words, these EAs can only be used to evolve specific graph topologies and they cannot be easily adapted to evolve graphs in general. Given that many data structures can be represented as graphs, a general EA that can tackle graphs with no specialized topology can have many useful real world applications. Towards this goal, this thesis proposes a general EA for graphs called EvoGraph. EvoGraph can be used to evolve all kinds of graphs by encoding them in adjacency matrices. Like other heuristic search algorithms, evolutionary search in a space of graphs also faces the challenge of a tremendously expanded search space when there is an increase in the number of nodes in a graph. Though this can be mitigated by increasing the population size to provide a larger variety of building blocks for the search, this increase in population size is limited, however, by constraints in computational resources. To address this problem, it should be noted that previous work has shown that uniform crossover in Genetic Algorithm (GA) could be rather efficient for heuristic searches in a large search space with a relatively small population. This operator ensures that all alleles have the same chance of being swapped during crossover and it also ensures that a relatively high degree of disruption be introduced to ensure the generation of novel chromosomes. Based on such a principle, EvoGraph's reproduction operators are also designed to resemble uniform crossover and mutation crossover in linear-string GA. The application of a single crossover operator in EvoGraph can achieve the same effect of more than one reproduction operation in a Genetic Programming (GP) and Evolutionary Programming (EP). EvoGraph can be shown to be very effective at various tasks involving the evolution of graphs in general and trees and ANN architectures in particular. EvoGraph is applied to solve a wide range of graph based heuristic problems considered in this thesis. They include architectural topology design, space frame design, creative art painting, molecular design and peer-to-peer overlay network design.
Description: x, 234 p. : ill. ; 30 cm.
PolyU Library Call No.: [THS] LG51 .H577P COMP 2009 Wong
URI: http://hdl.handle.net/10397/2762
Rights: All rights reserved.
Appears in Collections:Thesis

Files in This Item:
File Description SizeFormat 
b23067147_link.htmFor PolyU Users 162 BHTMLView/Open
b23067147_ir.pdfFor All Users (Non-printable) 3.52 MBAdobe PDFView/Open
Show full item record

Page view(s)

464
Last Week
1
Last month
Checked on Dec 4, 2016

Download(s)

471
Checked on Dec 4, 2016

Google ScholarTM

Check



Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.