Background

 2.1 Introduction to the field

There currently are three main types of search methods: calculus-based, enumerative and random. They have been very useful in solving a variety of problems that involve searching.

Figure 2.1 - Single-peak functions

Calculus-based methods are commonly used for searching relatively smooth search spaces. They relay on searching by solving mathematical formulas and can be extremely efficient and useful in single-peak (single optima, uni-modal) function (Figure 2.1) domains since they employ the notion of hill climbing by seeking the best in a “neighbourhood” of solutions [Fryer and Greenman, 1987].

If the problem domain subject to search has multiple peaks (multiple optima, multi-modal function) like a low peak first and then a much higher one, these search methods might find the small peak and miss the big one (Figure 2.2).

Figure 2.2 - Multiple peak function

Also many real word search spaces are far too complex and full of discontinuities [Goldberg, 1998]. Therefore calculus based search methods are not suitable for all domains.

Enumerative search methods use a simple technique of looking at objective function values (possible solutions) at every point in a finite or bounded infinite search space, taking one at a time. This technique however lacks efficiency and many practical spaces are simply too big. Even some of the best enumerative schemes like the dynamic programming break down on problems of moderate size [Goldberg, 1989]. This makes this search method unsuitable for many real problem domains.

Random search methods have increased in popularity in the past 20 years, as the limitations of calculus-based and enumerative techniques became obvious [Goldberg, 1989]. In the long run however these techniques are expected to do no better than the enumerative searches [Goldberg, 1989].

The problem associated to these search methods is that they are not robust (effective and efficient) [Goldberg, 1989]. They are still useful and many hybrid combinations have been successful in many applications, however as more complex problems are tackled other methods will be necessary [Goldberg, 1989].

Many of the traditional methods work well in narrow problem domains but are equally inefficient across a broad spectrum [Goldberg, 1989]. A robust method is needed that will work well across a broad spectrum of problems. It is believed that genetic algorithms can be that robust method.

Recently the No Free Lunch Theorem [Wolpert and Macready, 1995] states that all search algorithms perform the same when they are averaged over all possible functions. This implies that if a genetic algorithm is compared to some other algorithm like the random search, and the genetic algorithm performs better on some class of problems, then the other algorithm necessarily performs better on problems outside that problem class. This suggests that it is essential to incorporate knowledge of the problem in the search algorithm [5]. Hence a more flexible genetic algorithm that could be fine-tuned to particular class of problems could perform better.

 

2.2 Genetic Algorithms

 

Genetic algorithms were developed by John Holland at the University of Michigan in the early 1970’s. The initial inspiration for genetic algorithms came from the process observed in natural evolution.

Genetic algorithms use terminology borrowed from natural genetics. An individual represents a potential solution for a given problem.  A group of individuals is called a population. The basic idea is that the genetic pool (the whole set of genes – characteristics in a population) of a given population contains the solution or a solution better than the individuals in the population currently represent. This solution is not “active” because the genetic combination it relies on is split between several individuals. By using a process that mimics the Darwinian evolutionary theory (only the strongest survive) and recombining the individuals it that population the target solution might be found.

Every individual in the environment has a set of characteristics. A genotype is the device that encodes the characteristics of that individual and identifies that individual. A decoded genotype represents the individual’s observable state or traits and is called phenotype. Evolution itself is a process that operates on the genotype rather than on the actual individuals they encode.

A genotype is made up of one or more chromosomes that encode groups of characteristics about the individual. Often genotypes are referred to as chromosomes in genetic algorithms since mostly one-chromosome individuals are considered (haploid chromosomes) [Michalewicz, 1999]. This report considers the terms genotype and chromosome with different meanings. The chromosomes themselves are made up of a number of genes. Each of these genes encodes one or several characteristics of an individual. The colour of the eyes is an example for a gene in the human DNA. Figure 2.3 shows how the data is structured in genetic algorithms.

 

A living being is partly created by decoding genotypes. Natural selection is the link between genotypes and the performance of their decoded structures - phenotypes. The processes of natural selection cause those genotypes that encode successful structures to reproduce more often than those that don’t. Evolution takes place at the process of reproduction. Using this process genes from two parents’ genotypes are used to create new offspring. This is also referred to as mating or recombination. Mutations may cause some of the genes of the children to be different from those of either of the parents.

Biological evolution has no memory itself. All the information needed to produce individuals that will function well in their environment is contained in the gene pool – the whole set of genes carried by the individuals in a population – and the structure of the genotype decoders.

These features of evolution inspired Holland and made him believe that these techniques used in a computer algorithm might produce a method for solving complex problems in the way that nature has done – through evolution.

An algorithm dealing with strings of binary digits called genotypes (using one chromosome) was introduced by Holland; this algorithm solved the problem of finding good genotypes by blindly manipulating the bits in them. Exactly like nature; the algorithm did not know the meaning of the binary digits. Only information about how good each genotype is was given to the algorithm so that the genotypes with good evaluation can reproduce more often than the ones with bad evaluation.

According to Davis [Davis, 1991] even though the algorithm was simple it proved adapt at solving extremely difficult problems.

There have been several modifications produced and upgrades of the basic algorithm, these have proven to find widespread application in business, science and engineering circles [Goldberg, 1989]. Genetic algorithms are theoretically and empirically proven to provide robust search in complex spaces [Goldberg, 1989].

 

2.3 How Genetic Algorithms work

At the start of every genetic algorithm there is a group of initial solutions under consideration called the population, which are usually generated using a random process. Each individual solution from the population in the genetic algorithm is encoded in the genotype, element or string.

There is a decoding function that decodes each genotype to its representation – phenotype. The phenotype is fed to a fitness evaluation function that determines how good a solution the genotype represents. A genotype represents the individual solution according to the representation technique used by the genetic algorithm while a phenotype represents the solution in the format to be fed to the function. The genotype representation technique is called schema [Goldberg, 1989].

For each genotype, a fitness value indicates how good a solution it can. The intent of the process is to end up with a population containing genotypes with better fitness than the ones in the initial population up to the point that a genotype encoding a good enough (according to the criteria set) solution is generated, if the domain has a such a solution.

 

A weighted random (also known as roulette wheel selection) selection based on the fitness of the chromosomes selects two parent genotypes, i.e. fitter genotypes will have a greater chance of being selected over the weaker ones. A reproduction technique called crossover (figure 2.4) combines the information from the two parent genotypes to get one or more children genotypes. The simplest form of crossover chops the parent chromosomes at a randomly selected point and swaps the parts between the two chromosomes combining the head of the first parent with the tail of the second one and vice versa.

After the new child genotype is created there is a chance its structure to be slightly modified by a process called mutation. The chance of mutation (figure 2.5) is calculated by using a weighted random algorithm, where the chances for a mutation to go ahead are usually small. If however a child will be mutated, a random algorithm is used to determine which parts of the genotype and with how will be altered. The child’s genotype then is evaluated for fitness, i.e. executed to see how good a solution it can provide.

 

The children are then used to form a new population. Some parents with high fitness can go directly to the new population without altering their genetic structure. Hence their genetic structure is preserved to benefit future generations. This is called elitism. The process of producing populations of offspring is then repeated until a specific constraint is met, e.g. after a set number of iterations or when a specific fitness criteria is met. This approach is known as the traditional to genetic algorithm.

Many genetic algorithm implementations are very specific for a domain. This is because in real life many domains do not cover all value combinations (are discontinuous) i.e. not any combination of chromosomes produces a valid child.

 

An example is the travelling salesman problem. Each genotype represents a sequence of cities to be visited once only. Crossover of two sequences does not normally produce a sequence in which a city appears just once, so a special crossover operator must be defined (figure 2.6). This makes some genetic algorithms specific to their fitness function and too complex for most users.

 

Genetic algorithms are widely used in optimisation searches. They help in problem areas where the number of constrains is too big for humans to efficiently evaluate. Genetic algorithms have been used in design of buildings, cars, electronic components etc.

A simple general-purpose genetic algorithms tool where the user should not need to know a great deal about genetic algorithms, and yet be able to benefit from their elegance and robust performance could help to developers.

 

2.4 Choice of Genetic Algorithm

 

There are many different implementations of genetic algorithms based on Holland’s theory. Some of the major variations are illustrated on figure 2.7 using a tree diagram. The different techniques illustrated there can also be combined and rearranged in different ways and order. Some techniques are very problem specific and therefore not very appropriate for the project.

Figure 2.7 – Genetic algorithms tree diagram

 

At the root of the tree is the traditional genetic algorithm approach previously. Each layer of the tree represents different techniques used for a feature of genetic algorithms. For matters of simplicity mostly techniques to be used in this project will be considered.

The top layer of the tree illustrates the different types of gene representation techniques (schema). The initial gene representation technique used by Holland was binary. Gene representation using binary alphabet (nodes and ones) is appropriate for many problems but standard binary does not always indicate how close the values it represents actually are to each other. The numbers 3 and 4 are quite close in value but when represented in binary 011 and 100, they look quite different. An attempt to tackle this problem is Gray coding. It is a representation technique again using binary alphabet, but in slightly different way, so that values close in value will have similar representation using Gray coding [Michalewicz, 1999]. Using Gray coding 3 and 4 are represented as 010 and 110 respectively. The algorithms for transforming standard binary to Gray code and vice versa are simple and will be discussed in the design chapter in more detail.

An alternative representation of genes is using strings. Then instead of using binary alphabet characters and words can be used to define the characteristics of an element. For the purpose of this project Gray code will be used.

The second layer of the tree illustrates some of the different population replacement techniques. The traditional approach to genetic algorithms assumes that all children elements produced should be part of a new population; different to the one the parent elements are part of. Hence when the population of children is full then this population’s elements are used as parents for the next population of children and so on. A subset of the population’s parents can be used to mate as opposed to the whole population so that the elements, which are believed to be better, reproduce more. This subset is called the mating pool.

An important feature of this technique is the so-called elitism. If elitism is used that means that some of the best elements of the population with parents, will directly be placed in the new generation of children without crossover or mutation. This is done sometimes to ensure the best elements are not lost.

Another population replacement technique uses just one population. The population is sorted according the fitness of its elements. No mating pool is used and mating is done one at the time. After every mating the children’s fitness is evaluated i.e. their strength as a solutions to the problem. Then they are added to the same population where their parent elements came from. The children’s position in the population is determined by their fitness – the fitter the higher they will be added in the population, shifting the rest of the elements down. Then the element with the lowest fitness measure will be removed from the population and hence the population size will be kept the same. This population replacement technique is more widely used in genetic algorithms than the previous and it will be used for this project.

The next layer of the tree (Figure 2.7) illustrates two common genotype fitness determination techniques. So far in this document the word “fitness” was used to describe the general representation of an element’s strength. The traditional approach to genetic algorithms uses the so-called fitness technique to compare the elements’ strengths. The logic behind it is quite simple. After the strength value for each element is obtained the sum of all the strengths of all the elements in the population are added up. The fitness value for each genotype (element) is determined by dividing its strength value with the total strength of the whole population. Its “strength” is meant to be the numeric value obtained from executing the function or domain under consideration (fitness function) while the given phenotype (element) was the input to this function. The “fitness” on the other hand is the value used by the genetic algorithm to compare an element to another during population sorting, parent selection, etc. This classification technique is also referred to as “rough fitness”.

The possible problem with this technique is that in a population where a few elements are by far stronger than the rest they will have very high probability of being used as parents. Only few iterations of the genetic algorithm might be enough to converge the population towards the very fit elements and then the same problem as with the two peaks (Figure 2.2) and hill climbing emerges i.e. premature convergence.

To avoid too early convergence in the population when a super fit element is present another technique can be used. It is called ranking or linear normalisation and it evenly distributes the strength measure so that a super strong element cannot dominate a whole population easily. The whole idea is that the measure between each element in a population sorted, according to strength should be the same, no matter how stronger an element is compared to its adjacent. A brief example is shown on figure 2.8 [7].

Figure 2.8 – Example of fitness calculation

 

For the purpose of the project the ranking technique was chosen so that convergence of the population towards a few super-fit elements in the early process of the genetic algorithm is avoided.

The next layer down the tree diagram (Figure 2.7) illustrates two techniques for parent selection. The first, so called tournament technique uses totally random selection to chose a number of chromosomes and then pick the fittest of them as the first parent and then repeat the process to find a second parent. The number of chromosomes entering the tournament can be any number between 2 and the total number of the population.

Another technique for parent chromosome selection can be the weighted random technique, or so called roulette wheel parent selection. With this technique even though the parents are selected at random, the fitter elements have a greater chance of being selected than the weaker ones. This is simply implemented by assigning value ranges in the random selection space according to the fitness or ranking of each element i.e. the fitter ones get greater value ranges and the not so fit get a smaller value range.

Genetic algorithms start with a population of elements representing a number of potential solutions to the problem at hand. By applying crossover and mutation to some of the genotypes an element or group of elements is hoped to emerge as the optimal (best) solution to the problem at hand. There are many types of crossover and mutation methods used in genetic algorithms and some of them are specific to the problem and gene representation technique (schema) [Goldberg, 1989].

Crossover is an important genotype recombination technique. Lets consider a genotype with only one chromosome. A simple type of crossover is the single point crossover (Figure 2.4).

The first part of the genotype of each of the two parents is combined with the other parent’s second part of the genotype so that two new children are created. The point at which the genotype is split is called the point of crossover. The point of crossover can be specified or selected at random for every crossover or for every genetic algorithm execution. Sometimes the children happen to have the exact same genes as their parents after crossover.

A more complex way of recombining the genes of a genotype is by using a multiple point crossover techniques.

 

A two-point crossover is illustrated on figure 2.9. Multiple point crossovers are also known as n-point crossovers and have a variety of forms. The crossover points can be selected at random or be specified using a masking pattern (Used for uniform crossover) [Michalewicz, 1999].

Another method of crossover is the so-called heuristic crossover. In heuristic crossover the parent phenotypes are fed to a function that generates a single offspring using a computational method. The function itself depends on the application of the genetic algorithm and the schema. It is believed that heuristic crossover fine tunes the offspring produced and helps the search to go in the most promising direction [Michalewicz, 1999].

 

Mutation is another recombination technique. It is used to make sure all the elements in a population are not homogeneous and diversity is maintained. Mutation can help genetic algorithms escape local optima in the search for the global optima. There are different methods of mutation and mutation is performed differently on different schema (gene representation alphabets). Only binary mutation will be considered in this document since that is what is used for this project.

Mutation is done to the offspring child’s genotype; performed at random according to a selected mutation rate that is usually ranges not higher than 30%. Binary mutation is performed by either randomly generating a new bit for the gene to be mutated or flipping it (changing the gene from 0 to 1 and vice versa) [Man et al., 1999].

A simple mutation method that changes a genotype only very slightly is the last bit flip mutation (figure2.5). It mutates the genotype by just flipping its last bit [Man et al., 1999].

A more commonly used mutation method is the single point random mutation. Also known as uniform mutation it involves the flipping of one randomly picked bit of the genotype [Michalewicz, 1999].

A more complicated mutation method is the multiple point mutation. It involves the flipping of a number of bits at a number of points of a genotype [Michalewicz, 1999].

 

So far a genotype with a single chromosome was considered only. When a genotype has more than one chromosome the genetic operators i.e. crossover and mutation can be done at genotype level. Then the chromosomes as groups will be ignored and recombination of genes can be done without considering the chromosome boundaries. Even if some chromosomes use different alphabets for their genes this will work for a population of genotypes with identical representation parameters i.e. same number of chromosomes and fixed size of chromosomes (figure 2.10).

 

This approach however does not allow for different chromosomes being recombined using different crossover methods. In order to make that feasible each chromosome can be recombined separately and after all the chromosomes of a genotype have been recombined a child produced. Using this method the recombination ability of the previous method are still feasible and yet more complicated crossovers can be done. For example the 2-point crossover on figure 2.10 can be done using single point crossovers on the individual chromosomes. However when crossover is done at the chromosome level different chromosomes can use different crossover methods. Similarly mutation can be done individually for every chromosome allowing for fine-tuned process.

An important part of the genetic algorithm is the termination criteria i.e. when to stop reproducing the individuals. Some problems tackled by genetic algorithms are aiming for a specific, optimal solution. A genetic algorithm usually terminates when such an optimal solution for the problem tackled is found. Alternatively when the existence of an optimal solution cannot be determined the genetic algorithm can be terminated is other criteria are satisfied. A commonly used criteria is the number of fitness evaluations. A genetic algorithm can be specified to terminate after a specified number of fitness evaluations of children have been done, even if an optimal solution to the problem tackled is not found.

Another termination criteria can be a specified average fitness of the population. When the specified fitness becomes the average fitness of the population the genetic algorithm can be terminated.

Sometimes after a number of iterations a population starts to converge towards a specific solution i.e. most of the individuals in the population have a very similar fitness. In situations like that usually a local or a global optima is approached or found by most of the solutions in the population and continuous executions of the genetic algorithm would not generate better solutions because the genetic pool (the gene combinations available in that population) is very homogeneous (similar). There is a termination criteria that would stop the genetic algorithm executing when such a situation is approached. The difference between the fitness of the best and worst individuals of the initial population is recorded at the start of the genetic algorithm. Then after every successive generation (when new children are added to the population) this difference is likely to decrease since the evolutionary process is likely to encourage fitter individuals to reproduce rather than less fit ones. The change of this difference can be monitored and when it becomes smaller than a specified percentage of that difference in the initial population, the genetic algorithm can be terminated even if an optimal solution is not found.

Some genetic algorithm implementations record the recombination parameters for every individual [Davis, 1991]. Hence a different recombination technique can be used for every offspring. Also each crossover and mutation method is dynamically graded so that methods that yield fit genotypes are used more often.