Graph Based Evolutionary Algorithms

Introduction

Graph based evolutionary algorithms (GBEAs) are a diversity management technique for evolutionary algorithms which places the members of the evolving population on the vertices of a combinatorial graph. They also provide a generic improvement by reducing the number of fitness evaluations required to find an acceptable solution at exceedingly low runtime cost through the selection of the correct graph as a population structure. The combinatorial graph provides a geography for the evolving population of solutions. Different graphs yield different levels of diversity preservation. The level of preservation needed for effective solution is problem specific. The amount of diversity present in a population initially is related to population size, but, even in a large population, this initial diversity can disappear rapidly. Graph based evolutionary algorithms impose restrictions on mating and placement within the evolving population (new structures are placed in their parents’ graph neighborhood). This simulates natural obstacles (like geography) or social obstacles (like the mating dances of some bird species) to mating (Kimura & Crow, 1963; Wright, 1986).

The GBEA technique differs from other AI enhancements to search and optimization in that they are a minor algorithmic modification that can be added to any evolutionary algorithm without requiring complex pre-calculation, costly additional data structures, or extensive modifications of the algorithm being enhanced. Only the adjacency matrix of a combinatorial graph need be added, and it is used only to limit mate choice – typically replacing a single call to a randomization algorithm. GBEAs are an exceptionally simple enhancement, provided the correct graph for a given problem is known.

When Evolutionary Algorithms (EAs) are used as an optimization process, populations of potential solutions are evolved to search a solution space for an acceptable answer. This often avoids problems with convergence to local optima that are found in gradient search methods (Goldberg, 1989) and enables the search of discrete spaces. These methods have provided novel and superior solutions for a wide range of problems in physics, engineering, biology, economics and many other areas (Blaize, Knight, & Rasheed, 1998; Fabbri, 1997; Keane, 1994; Vavak, Jukes, & Fogarty, 1997). A key issue when applying EAs is how to maintain sufficient diversity. When diversity loss is too rapid, an ineffective search of the solution space may occur, leading to premature convergence. When diversity is preserved too aggressively, the algorithm may converge slowly or not at all. The right amount of diversity is problem specific. A rule of thumb is that the need to preserve diversity increases with problem complexity and deceptiveness (Bryden, Ashlock, Corns, & Willson, 2006).

There are several available methods for preserving diversity, including EcoGAs (Davidor, 1993), island GAs (Whitley & Starkweather, 1990), niching (Goldberg, 1989), and taboo search (Goldberg, 1989). EcoGAs and Island GAs are essentially the same as a type of GBEA, albeit using a less diverse class of graphs. EcoGAs use a grid shaped graph, and Island GAs use clusters of complete graphs connected through controlled migration events. Niching and taboo search require comparison of solutions in the evolving population either to all other solutions in the population or a taboo list, and so incur additional computational costs. GBEAs have exceedingly low computational overhead because of the fashion in which they mimic passive methods of diversity preservation found in nature.

Carefully choosing the connectivity of the combinatorial graphs used permits the level of diversity preservation to be increased or decreased (Bryden et al., 2006). Greater diversity causes more candidate solutions to evolve within the population. They may compete or cooperate (by juxtaposing compatible sub-structures) as they explore the search space. This can also result in finding multiple solutions for multi-modal problems.