Evolutionary algorithm

Introduction

Natural selection favors individuals who can adapt to the environment best (survival of the fittest). Phenotypic traits are those behavioral and physical features of an individual that directly affect its response to the environment, determining its fitness. If the environment evaluates phenotypic traits favorably, then these traits are propagated by the individual's offspring, otherwise they are discarded by dying without offspring. Small variations in phenotypic traits occur from generation to generation, which get evaluated by the environment.

The process of evolution can be depicted as adaptive landscape, where \((x,y)\) values correspond to biological traits, and \(z\) values is the evaluated fitness. Multimodal problems have several local optimum, whereas unimodal problems have only one local and global optimum. Genetic drift allows individuals to climb downhill.

Changes in the genetic material of a population can only come from random mutations and natural selection, not from individual learning. The selection is based at the phenotypic level on actual performance in the environment.

There are two great problem solvers:

• The human brain
• The evolution

The evolutionary computing can solve the following problems:

• Optimization problems: input is unknown (Keane et al. 1996, evolved antenna)
• Modeling problems: model is unknown (Freitas 2002, Schulenburg 2001, and Schulenburg 2007). The benefit of evolutionary computing is that the model's rules are transparent compared to neural networks.
• Simulation problems: output is unknown (Tesfatsion 1998 and Tesfatsion 2001 based on Sugarscape world (Epstein 1996))

The genetic algorithm was initially proposed by John Holland in 1992 in his book Adaptation in natural and artificial systems suitable for studying adaptive behavior.

Evolutionary algorithm

BEGIN
    INITIALIZE population with random candidate solutions;
    EVALUATE each candiate;
    REPEAT UNTIL ( TERMINATION CONDITION is satisfied ) DO
        1. SELECT parents;
        2. RECOMBINE pairs of parents;
        3. MUTATE the resulting offspring;
        4. EVALUATE new candidates;
        5. SELECT individuals for the next generation;
    OD
END

Components of evolutionary algorithm

Object forming possible solutions are referred to as phenotypes, while their encoding (individuals) are called genotypes. The mapping of a set of phenotypes to the set of genotypes is called representation or encoding. The mapping from genotypes to phenotypes is called decoding. The space of possible solutions is the phenotype space. The space where the evolutionary search actually takes place is called the genotype space.

Evaluation function or fitness function represents the requirements the population should adapt to. In optimization problem the evaluation function is called the objective function.

A population is a multiset of genotypes. Individuals are static objects, but the population changes and adapts. The population size is almost always constant and does not change during evolution. The diversity of a population measures the number of different solutions.

An individual becomes a parent if it has been selected to create offspring through undergoing variation. High-quality individuals have more chance to becoming parents than those with low quality, however low quality individuals are given a small chance too, otherwise the search may get stuck in the local optimum.

In phenotype space variation operators create new individuals from old ones, generating new candidate solutions. Mutation is a stochastic unary variation operator which is applied to one genotype to create an offspring. Recombination or crossover is a ctochastic binary variation operator which merges information from two parent genotypes with random drawings into one or two offspring genotypes. It is possible to recombine more than two parents to produce offspring with a positive effect (Eiben, pp. 289-307), however in nature it does not happen. Recombination is the superior form of reproduction because higher organisms reproduce sexually while lower organisms reproduce asexually (Maynard-Smith 1978 and Maynard-Smith and Szathmary 1995).

Survivor selection or environment selection is a deterministic process of distinguishing individuals based on their quality. It is called after the creation of offspring from selected parents. Survivor selection is based on the fitness of individuals and their age.

Initialization may be problem-specific but mostly is simply done by random generation of the first population.

Termination condition ideally would be the discovery of a solution within a given precision. However, EAs are stochastic and could not stop. Therefore, we have the following options for the termination of the algorithm: 1. Maximum CPU time limit 2. Number of fitness evaluations 3. Patience threshold of little improvement of fitness 4. Threshold of population diversity drop

The eight queens problem

An example of evolutionary approach is a problem of placing eight no-checking queens on a regular 8 by 8 chessboard. The phenotype \(p\) in phenotype space \(P\) represents one board configuration. The quality \(q(p)\) of any phenotype \(p \in P\) can be quantified by the number of checking queen pairs. \(q(p) = 0\) indicates a good solution. The fitness of a genotype \(g\) can be expressed as a function of \(q(p)\):

• an inverse (with zero special case handling)
• \(1 / (q(p) + \epsilon)\)
• \(-q(p)\)
• \(M - q(p)\), where \(M \ge \max \{q(p) | p \in P\}\)

A genotype or chromosome is a permutation of the numbers \(1, \ldots, 8\), with a a genotype \(g = [i_1, \ldots, i_8]\) be a vector to denote a unique board configuration. By using this representation, we embed a constraint: no two queens could appear in the same column or row. We also need to introduce diagonal constraints. The mapping from the genotype space \(G\) to phenotype space \(P\) is also straightforward.

For mutation we can randomly select two positions in a given chromosome and swap their values. A good crossover mechanism could be the following:

1. Select a position for crossover point
2. Cut both parents into two segments at this position
3. Copy the first segment of parent 1 into child 1 and
the first segment of parent 2 into child 2
4. Copy the second segment of parent 1 to child 2 and
the second segment of parent 2 to child 1

In each evolutionary cycle we will select two parents to produce two children, increasing population by two new individuals. Parents selection is done by choosing five individuals randomly from the population and taking the best two as parents. Survivor selection mechanism (replacement strategy) deletes two individuals with worst fitness at the end of the cycle.

We initialize the population with random permutations and terminate the search when we find a solution, or when 10,000 fitnes evaluations have elaped, whichever happens sooner. We choose a population of size 100. We apply mutations with a probability of 80% after crossover.

Algorithm specification

0-1 knapsack problem

The genotype is encoded as a binary vector, one for taking the item, and zero for omitting the item. The genotype space \(G\) is the set of all \(2^n\) such vectors. The phenotype is decoded from genotype by going from the first component to the last, turning the components that exceed the capacity of the knapsack to zero.

The quality of a given solution is calculated by taking a dot product of two vectors, the phenotype and the items value vector:

$$Q_p = v \cdot p$$

We choose the recombination operator to be one point crossover, which means we align two parents, pick a random point along their length, and eachange the tails of the parents at that point. We will do this with 70% probability, otherwise just copy the two parents. For mutation operator we use bit-flipping: at each genotype position we ivert the value with a small probability.

We use taurnament for selecting the parents, where each time we pick two membersof the population at random with replacement, and the one with highest value \(Q_p\) wins the taurnament and becomes a parent. For survival selection we use a generational scheme, where the population in each iteration is discarded and replaced by their offspring.

Initializaiton is done randomly. Since we don't know the maximum value that we can achieve, we terminate the algorithm when no improvement in the fitness has been observed for 25 generations.

The population size will be 500. Mutation rate will be \(p_m = 1/n\), that is we change on average one value in every offspring.

Algorithm specification

The operation of EA

The first stage of EA is called exploration, which means we generate new individuals in the untested regions of the search space. The second stage is exploitation, where individuals are concentrated in the proximity of known good solutions. There is a trade-off between the two: too much exploration leads to inefficient search, and too much of exploitation leads to the tendency to focus the search too soon.

Premature convergence is the effect of losing population diversity in local optimum. Anytime behavior of EA means that we can stop anytime with good solution because the iterative improvement degrades with time. In this sense, it is not necessary to seed the initial population with better than random individuals (called heuristic initialization), because the first few iterations are the most efficient. We generally do not want to wait too long before termination because of lack of improvement of the fitness at later stages.

EA performs better than random search and worse than problem tailored methods, however no free lunch theorem debunks this notion (Wolpert and Macready 1997).

Exhaustive enumeration is a well-known solution to any problem, while branch and bound algorithms are suitable to solve any problem that could be expressed in mathematical formula. However, many problems have an exponential growth as the number of variables increases, what makes it impracticle for finding the global optimal solution.

Simulated annealing uses randomized heuristics to find a solution, however it will not tell whether the solution is a global optimum, just the best seen so far.