Graph Based Evolutionary Algorithms

Graph Based Evolutionary Algorithms

Steven M. Corns (Iowa State University, USA), Daniel A. Ashlock (University of Guelph, Canada) and Kenneth Mark Bryden (Iowa State University, USA)
DOI: 10.4018/978-1-59904-996-0.ch017
OnDemand PDF Download:


This chapter presents Graph Based Evolutionary Algorithms. Graph Based Evolutionary Algorithms are a generic enhancement and diversity management technique for evolutionary algorithms. These geographically inspired algorithms are different from other methods of diversity control in that they not only control the rate of diversity loss at low runtime cost but also allow for a means to classify evolutionary computation problems. This classification system enables users to select an algorithm a priori that finds a satisfactory solution to their optimization problem in a relatively small number of fitness evaluations. In addition, using the information gathered by evaluating several problems on a collection of graphs, it becomes possible to design test suites of problems which effectively compare a new algorithm or technique to existing methods.
Chapter Preview


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.

Complete Chapter List

Search this Book:
Table of Contents
Alfonso Araque Almendros
Ana B. Porto Pazos, Alejandro Pazos Sierra, Washington Buño Buceta
Chapter 1
Eduardo Malmierca, Nazareth P. Castellanos, Valeri A. Makarov, Angel Nuñez
It is well know the temporal structure of spike discharges is crucial to elicit different types of neuronal plasticity. Also, precise and... Sample PDF
Corticofugal Modulation of Tactile Responses of Neurons in the Spinal Trigeminal Nucleus: A Wavelet Coherence Study
Chapter 2
Didier Le Ray, Morgane Le Bon-Jego, Daniel Cattaert
Computational neuroscience has a lot to gain from invertebrate research. In this chapter focusing on the sensory-motor network that controls leg... Sample PDF
Neural Mechanisms of Leg Motor Control in Crayfish: Insights for Neurobiologically-Inspired Autonomous Systems
Chapter 3
Oscar Herreras, Julia Makarova, José Manuel Ibarz
Neurons send trains of action potentials to communicate each other. Different messages are issued according to varying inputs, but they can also mix... Sample PDF
Forward Dendritic Spikes: A Mechanism for Parallel Processing in Dendritic Subunits and Shifting Output Codes
Chapter 4
Gheorghe Paun, Mario J. Perez-Jimenez
This chapter is a quick survey of spiking neural P systems, a branch of membrane computing which was recently introduced with motivation from neural... Sample PDF
Spiking Neural P Systems: An Overview
Chapter 5
Juan Ramón Rabuñal Dopico, Javier Pereira Loureiro, Mónica Miguélez Rico
In this chapter, we state an evolution of the Recurrent ANN (RANN) to enforce the persistence of activations within the neurons to create activation... Sample PDF
Simulation of the Action Potential in the Neuron's Membrane in Artificial Neural Networks
Chapter 6
Ana B. Porto Pazos, Alberto Alvarellos González, Alejandro Pazos Sierra
The Artificial NeuroGlial Networks, which try to imitate the neuroglial brain networks, appeared in order to process the information by means of... Sample PDF
Recent Methodology in Connectionist Systems
Chapter 7
José A. Fernández-León, Gerardo G. Acosta, Miguel A. Mayosky, Oscar C. Ibáñez
This work is intended to give an overview of technologies, developed from an artificial intelligence standpoint, devised to face the different... Sample PDF
A Biologically Inspired Autonomous Robot Control Based on Behavioural Coordination in Evolutionary Robotics
Chapter 8
Enrique Mérida-Casermeiro, Domingo López-Rodríguez, J.M. Ortiz-de-Lazcano-Lobato
In this chapter, two important issues concerning associative memory by neural networks are studied: a new model of hebbian learning, as well as the... Sample PDF
An Approach to Artificial Concept Learning Based on Human Concept Learning by Using Artificial Neural Networks
Chapter 9
Enrique Fernández-Blanco, Julian Dorado, Nieves Pedreira
The artificial embryogeny term overlaps all the models that try to adapt cellular properties into artificial models. This chapter presents a new... Sample PDF
Artificial Cell Systems Based in Gene Expression Protein Effects
Chapter 10
Computing vs. Genetics  (pages 165-181)
José M. Barreiro, Juan Pazos
This chapter first presents the interrelations between computing and genetics, which both are based on information and, particularly... Sample PDF
Computing vs. Genetics
Chapter 11
Iara Moema Oberg Vilela
This chapter discusses guidelines and models of Mind from Cognitive Sciences in order to generate an integrated architecture for an artificial mind... Sample PDF
Artificial Mind for Virtual Characters
Chapter 12
Zhijun Yang, Felipe M.G. França
As an engine of almost all life phenomena, the motor information generated by the central nervous system (CNS) plays a critical role in the... Sample PDF
A General Rhythmic Pattern Generation Architecture for Legged Locomotion
Chapter 13
Marcos Gestal, José Manuel Vázquez Naya, Norberto Ezquerra
Traditionally, the Evolutionary Computation (EC) techniques, and more specifically the Genetic Algorithms (GAs), have proved to be efficient when... Sample PDF
Genetic Algorithms and Multimodal Search
Chapter 14
Jesús M. Miró, Alfonso Rodríguez-Patón
Synthetic biology and biomolecular computation are disciplines that fuse when it comes to designing and building information processing devices. In... Sample PDF
Biomolecular Computing Devices in Synthetic Biology
Chapter 15
Alejandro Rodríguez, Alexander Grushin, James A. Reggia
Drawing inspiration from social interactions in nature, swarm intelligence has presented a promising approach to the design of complex systems... Sample PDF
Guiding Self-Organization in Systems of Cooperative Mobile Agents
Chapter 16
Agostino Forestiero, Carlo Mastroianni, Fausto Pupo, Giandomenico Spezzano
This chapter proposes a bio-inspired approach for the construction of a self-organizing Grid information system. A dissemination protocol exploits... Sample PDF
Evaluating a Bio-Inspired Approach for the Design of a Grid Information System: The SO-Grid Portal
Chapter 17
Steven M. Corns, Daniel A. Ashlock, Kenneth Mark Bryden
This chapter presents Graph Based Evolutionary Algorithms. Graph Based Evolutionary Algorithms are a generic enhancement and diversity management... Sample PDF
Graph Based Evolutionary Algorithms
Chapter 18
Daniela Danciu
Neural networks—both natural and artificial, are characterized by two kinds of dynamics. The first one is concerned with what we would call... Sample PDF
Dynamics of Neural Networks as Nonlinear Systems with Several Equilibria
Chapter 19
Jianhua Yang, Evor L. Hines, Ian Guymer, Daciana D. Iliescu, Mark S. Leeson, Gregory P. King, XuQuin Li
In this chapter a novel method, the Genetic Neural Mathematical Method (GNMM), for the prediction of longitudinal dispersion coefficient is... Sample PDF
A Genetic Algorithm-Artificial Neural Network Method for the Prediction of Longitudinal Dispersion Coefficient in Rivers
Chapter 20
Malcolm J. Beynon, Kirsty Park
This chapter employs the fuzzy decision tree classification technique in a series of biological based application problems. With its employment in a... Sample PDF
The Exposition of Fuzzy Decision Trees and Their Application in Biology
About the Contributors