CHAPTER 1
A BRIEF INTRODUCTION TO EVOLUTIONARY AND OTHER NATURE-INSPIRED ALGORITHMS

Nasimul Noman

School of Electrical Engineering and Computer Science, Faculty of Engineering and Built Environment, The University of Newcastle, New South Wales, Australia
and
The Priority Research Centre for Bioinformatics, Biomarker Discovery and Information-Based Medicine, The University of Newcastle, New South Wales, Australia

Hitoshi Iba

Department of Information and Communication Engineering, Graduate School of Information Science and Technology, The University of Tokyo, Bunkyo, Tokyo, Japan

1.1 INTRODUCTION

When we look at nature, everything seems to be working very systematically. All natural phenomena, ranging from molecular level to ecological level, and from individual level to population level, are functioning effectively. The flawless operation of various natural systems becomes possible due to some underlying governing rules.

From the beginning of human history, people have borrowed ideas and mimicked different natural processes in solving their daily-life problems. With the progress of civilization, we started to analyze and understand the basic laws and fundamental mechanisms behind natural phenomena and imitate those in designing artificial systems. With the beginning of information era, researchers started to investigate these natural processes from the perspective of information processing. We started to mimic how information is stored, processed, and transferred in natural systems in developing new techniques for solving complex problems. Today, a broad field of research is involved in the design, development, and study of intelligent computational systems that are inspired by the mechanisms and principles (often highly simplified versions of those) observed in various natural processes.

Perhaps, the largest natural information processing system that we have studied most widely and understand reasonably is evolution. Evolution refers to the scientific theory that explains how biological hierarchy of DNA, cells, individuals, and populations slowly change over time and give rise to the fantastic diversity that we see around us. Through the evolutionary process, the changes taking place in an organism's genotypes give rise to optimized phenotypic behaviors. Therefore, evolution can be considered as a process capable of finding optimized, albeit not optimal, solutions for problems.

Evolutionary computation (EC) is a branch of computer science, dedicated to the study and development of search and optimization techniques which draw inspiration from Darwinian theory of evolution and molecular genetics. The incremental growth of the field resulted in algorithms with different flavors although all of them utilize the in silico simulation of natural evolution. Classically, the most prominent types of evolutionary computation are genetic algorithms (GA), genetic programming (GP), Evolutionary Strategy (ES) and Evolutionary Programming (EP). Although, at the beginning, each class of algorithms had their distinct characteristics, lately, because of hybridization and concept borrowing, it is difficult to categorize some new algorithms as a specific class of EC.

After natural evolution, the artificial intelligence community has been heavily influenced by the social behavior emerged, through information processing and sharing, among relatively simpler life forms. Social insects like ants, termites and bees exhibit remarkable intelligence in improving their way of life, for example, retrieval of food, reducing the threat of predator, division of labour, or nest building. They possess impressive problem-solving capabilities through collaboration and cooperation among fellow members which themselves have very limited intelligence. Many computational algorithms and problem-solving techniques, commonly known as swarm intelligence, have been developed by simulating the coordination and teamwork strategies in social insects.

Other than evolutionary computation and swarm intelligence, many other computational algorithms have been proposed which are inspired by different natural phenomenon such as immune systems of vertebrate, biological nervous systems, chemical systems, or the behavior of different animals such as bat, firefly, and cuckoo. There exist a lot of variation and differences among these algorithms in terms of problem representation and solution searching mechanism; however, the common connection among them is that all of these algorithms extract metaphor and inspiration from nature. These classes of algorithms are commonly known as nature-inspired algorithms or bio-inspired algorithms. In this book, we will mostly focus on evolutionary computation and a few other swarm and nature-inspired algorithms; therefore, we will commonly refer to them as evolutionary computation.

Because of their robust and reliable search performance, these algorithms are preferred for solving many complex problems where traditional computational approaches are found to be inadequate. Gene regulatory networks (GRNs) are complex, nonlinear systems with incomplete understanding of their underlying mechanism at molecular level. Consequently, evolutionary and other nature-inspired algorithms are preferred as the computational approach in different research in GRN which is the topic of this book. Therefore, in this first chapter, we present a gentle introduction of evolutionary and other nature-inspired computation so that the readers can have a better understanding of the more advanced versions of these algorithms presented in subsequent chapters. After the generalized introduction, we also discuss relative advantages/disadvantages and application areas of these algorithms.

1.2 CLASSES OF EVOLUTIONARY COMPUTATION

1.2.1 Genetic Algorithms

Genetic algorithms, which are typical examples of evolutionary computation, have the following characteristics:

• Work with a population of solutions in parallel
• Express candidate solutions to a problem as a string of characters
• Use mutation and crossover to generate next-generation solutions

Elements comprising GAs are data representation (genotypes or phenotypes), selection, crossover, mutation, and alternation of generations. How to implement these elements is a significant issue that determines the search performance. Each element is explained below.

1.2.1.1 Data Representation

Data structures in GAs are genotypes (GTYPE) and phenotypes (PTYPE). GTYPE corresponds to genes of organisms, and indicates strings expressing candidate solutions (bit strings with fixed length). Genetic operators, such as crossover and mutation which are discussed later, operate on GTYPE. The implementer can determine how to convert candidate solutions to strings. For instance, GTYPE may be a candidate solution converted into an array of concatenated integers.

On the other hand, PTYPE corresponds to individual organisms, and indicates candidate solutions to a problem based on interpretation of GTYPE. The fitness value that indicates the quality of a candidate solution is calculated using PTYPE.

1.2.1.2 Selection

In GAs, individuals that adapt better to the environment leave many children and others are eliminated in line with Darwinian evolution theory. Individuals that adapt to the environment are candidate solutions that score highly regarding the problem, and the fitness function determines the score. Various methods of selecting parent individuals that generate children comprising the next generation have been proposed. Among these, the roulette selection (each individual generates children with a probability proportional to its fitness value) and the tournament selection (a number of individuals are selected at random and the best individual is chosen as the parent, and this procedure is repeated as necessary) are frequently used.

The elite strategy (best individual always remains in the next generation) is often used in addition to these selection methods. This strategy does not reduce the fitness value of the best individual in subsequent generations (as long as the environment to be evaluated does not change). However, using the elite strategy too much in the initial stages of a search may lead to premature convergence, which means convergence to a local solution.

1.2.1.3 Crossover

Crossover is an analogy of sexual reproduction, and is an operation that mates two parent individuals to generate new children. There are a number of crossover methods with different granularity when splitting individuals; examples are one-point crossover and uniform crossover.

One-point crossover selects a crossover point at random and switches parts of two parent individuals at this crossover point for generating children. Figure 1.1 is an example of a one-point crossover. The point between bits 3 and 4 is chosen as the crossover point, and two children are generated. Two-point crossover, where two crossover points are chosen and two switches are made, and multiple-point crossover with three or more crossover points are also possible.

Figure 1.1 One-point crossover in a genetic algorithm.

Uniform crossover is the most refined crossover method where the parent value to inherit is determined for each bit. Hitchhiking is a problematic phenomenon regarding crossover in GAs, in which unnecessary bits existing around a good partial solution spread as parasites to the good partial solution regardless of whether the fitness value is good or not. In general, uniform...