Genetic algorithms and applications in evolutionary computation

Schools of Evolutionary Computation

Evolutionary Computation is a field of artificial intelligence that is used to solve many real-life problems. It is based on the biological evolution process that uses many optimization techniques like self-organization, genetic algorithms, swarm intelligence, evolutionary programming, genetic programming, cultural algorithms and harmony search algorithms. Yao (1999; p.1) has explained evolutionary computation as, "Evolutionary computation is the study of computational systems which use ideas and get inspiration from natural evolution and adaptation. It aims at understanding such computational systems and developing more robust and efficient ones for solving real-world problems."

In the world of computer science, evolutionary computation is used to make search more precise and effective. These different techniques make it possible to get accurate results for the given set of keywords. This improved search can make a huge difference because of the voluminous amount of information that is available around the world. These techniques also help to reduce the amount of time for each search. Out of the different evolutionary computation techniques, genetic algorithms, genetic programming and evolutionary programming are more extensively used.

Genetic Algorithm

Genetic Algorithms are based on Darwin's Theory of Evolution. It was developed by John Holland during 1960s at the University of Michigan in Ann Arbor. This algorithms follows the principle that the best or fittest model is the best way to design a robust system that is adaptive to changing needs.

In this algorithm, a basic set of solutions are taken and this is called the population. The individual solutions are the strings or chromosomes. Out of these, the best and fittest chromosomes are taken to form new populations to produce a set of solutions that are better than the previous solution. This iterative process is continued until a solution that matches the specified constraints is obtained. This is a simple, yet powerful means of finding solutions for a problem.

The distinguishing features of the genetic algorithms are its three features -- the representation: bit strings, method of selection: proportional selection and the method of producing variations: crossover. (Back, Fogel & Michaelwicz, 2000). Another salient feature of this type of algorithm is that it uses the time-tested principles of evolution, namely mutation, selection and reproduction. One major advantage of this algorithm is its parallel processing. The offspring work in a parallel fashion making it faster to get accurate results and less time-consuming than serial processing. This also makes it possible to solve problems without knowing anything at the start of the process. So, it works well in most of the situations and has a lot of real-world applications.

Genetic algorithms is used in a wide range of industries like automotive design, robotics, telecommunications and routing problems, gaming, encryption and even in investment ideas and strategies. Each of these applications has a different process and a different goal. In the automotive industry, it can be used to come up with the best design and materials for different race cars to get the best performance from them. While the robotics industry uses genetic algorithms to come up with the optimal solutions from the vast available set of solutions, the finance industry is likely to use it to identify pit holes or problems that can prevent catastrophes like the current economic meltdown. According to Mitchell (1998, p.16), "GAs have been used to evolve computer programs for specific tasks, and to design computational structures such as cellular automata and sorting networks." These algorithms can also be used to find the best route in telecommunications, aviation and shipping.

Despite these numerous applications, they are not without criticism. The different parameters like the size of the population, crossover, choice of strings and the rate of mutation must be controlled to get the best results. It can also result in a problem called premature convergence in which one fitter individual can dominate the others and this can lead to a localized solution instead of searching the entire population. These are some of the drawbacks of this technique.

Evolutionary Programming

Evolutionary programming is another optimization technique that is a slight variant of the genetic algorithms. Instead of focusing on the genetic factors of evolution, the evolutionary programming technique lays more emphasis on the behavioral relationship between the parent and offspring. The process is very similar to the other techniques. A random sample is selected and out of this each solution is reproduced to a new population. The fitness of each solution is computed and a tournament selection process is followed to pick the fittest or the best solution. Under this solution, an individual or parent is chosen based on how many other individuals it was able to beat during the tournament.

A notable feature of evolutionary programming is that it does not user crossover as a genetic factor in the process of mutation and reproduction. Its major advantage is that there is no fixed representation like encoding the solutions as bit strings. Also, since crossover is not used as a genetic operator, minor variations in the offspring does not lead to major variations. This also avoids the problem of premature convergence.

It can be applied to a wide range of fields like transportation, pharmaceutical, military planning, games, control systems, earthquake determination, sensor array localization, integer optimization, optical systems, image resolution, face recognition systems and even to monitor blood pressure during surgery. (McDonnell, Reynolds & Fogel, 1995).

Despite this extensive application, there are also some problems and issues that come with it. The primary issue is the fitness assessment. When a tournament selection is used, it only determines the best of the existing solutions and not necessarily the optimal solution. It also looks at fitness "as a single resource that has to be shared by individuals occupying the same environmental niche." (McDonnell, Reynolds & Fogel, 1995, p.110). These factors make it difficult to determine the optimal solution every time.

Conclusion

In short, these three techniques of evolutionary computation have changed the world in many ways. They are in the nascent stages of development and as they grow, they are expected to make major break-through in our understanding of problems and our ability to find solutions for these problems quickly and efficiently.