A graph based evolutionary algorithm

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.