Gentic Algorithm Report

GENETIC ALGORITHMS

ACKNOWLEDGEMENT

I thank my seminar guide, Lecturer, CUSAT, for her proper guidance, and valuable suggestions. I am indebted to the HOD, Computer Science division and division other faculty members for giving me an opportunity to learn and do this seminar. If not for the above mentioned people my seminar would never have been completed successfully. I once again extend my sincere thanks to all of them.

ROHITH NANDAKUMAR

College Of Engineering Adoor Computer Science & Engg.

1 Department of

GENETIC ALGORITHMS

ABSTRACT A genetic algorithm (GA) is a search technique used in computing to find exact or approximate solutions to optimization and search problems. Genetic algorithms are categorized as global search heuristics. Genetic algorithms are a part of evolutionary computing, which is a rapidly growing area of artificial intelligence. It uses techniques inspired by evolutionary biology such as inheritance, mutation, selection, and crossover. The basic concept of GAs is designed to simulate processes in natural system necessary for evolution, specifically those that follow the principles first laid down by Charles Darwin of survival of the fittest. As such they represent an intelligent exploitation of a random search within a defined search space to solve a problem. GAs have been used for problem-solving and for modeling. GAs are applied to many scientific, engineering problems, in business and entertainment, including: •

Optimization: GAs have been used in a wide variety of optimization tasks such as traveling salesman problem (TSP), circuit design, job shop scheduling and video & sound quality optimization.

•

Machine and robot learning: GAs have been used for many machine- learning applications, including classification and prediction, and protein structure prediction. GAs have also been used to design neural networks, to evolve rules for learning classifier systems or symbolic production systems, and to design and control robots.

•

Models of social systems: GAs have been used to study evolutionary aspects of social systems, such as the evolution of cooperation, the evolution of communication, and trail-following behavior in ants.

College Of Engineering Adoor Computer Science & Engg.

2 Department of

GENETIC ALGORITHMS

CONTENTS

ACKNOWLEDGMENT ABSTRACT 1. INTRODUCTION 2. BIOLOGICAL BACKGROUND 3. SEARCH SPACE 4. GENETIC ALGORITHM 5. OPERATORS OF GA 6. SELECTION 7. ENCODING 8. CROSSOVER AND MUTATION 9. APPLICATIONS OF GA 10. CONCLUSION REFERENCES

1. INTRODUCTION

College Of Engineering Adoor Computer Science & Engg.

3 Department of

GENETIC ALGORITHMS Genetic Algorithms have been widely studied, experimented and applied in many fields in engineering worlds. Not only does GAs provide alternative methods to solving problem, it consistently outperforms other traditional methods in most of the problems link. Many of the real world problems involved finding optimal parameters, which might prove difficult for traditional methods but ideal for GAs. However, because of its outstanding performance in optimization, GAs has been wrongly regarded as a function optimizer. In fact, there are many ways to view genetic algorithms. GAs were introduced as a computational analogy of adaptive systems. They are modeled loosely on the principles of the evolution via natural selection, employing a population of individuals that undergo selection in the presence of variation-inducing operators such as mutation and recombination (crossover). A fitness function is used to evaluate individuals, and reproductive success varies with fitness. The Basic Algorithm 1. Randomly generate an initial population M(0) 2. Compute and save the fitness u(m) for each individual m in the current population M(t) 3. Define selection probabilities p(m) for each individual m in M(t) so that p(m) is proportional to u(m) 4. Generate M(t+1) by probabilistically selecting individuals from M(t) to produce offspring via genetic operators 5. Repeat step 2 until satisfying solution is obtained.

The paradigm of GAs described above is usually the one applied to solving most of the problems presented to GAs. Though it might not find the best solution, more often than not, it would come up with a partially optimal solution. Idea of evolutionary computing was introduced in the 1960s by I. Rechenberg in his work "Evolution strategies" (Evolutionsstrategie in original). His idea was then developed by other researchers. Genetic Algorithms were invented by John Holland and developed by him and his students and colleagues. This lead to Holland's book "Adaption in Natural and Artificial Systems" published in 1975. In 1992 John Koza has used genetic algorithm to evolve programs to perform certain tasks. He called his method "genetic programming" (GP). LISP programs were used, because programs in this language can be expressed in the form of a "parse tree", which is the object the GA works on. Methodology Genetic algorithms are implemented in a computer simulation in which a population of abstract representations (called chromosomes or the genotype of the genome) of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem evolves toward better solutions. Traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible. The evolution College Of Engineering Adoor Computer Science & Engg.

4 Department of

GENETIC ALGORITHMS usually starts from a population of randomly generated individuals and happens in generations. In each generation, the fitness of every individual in the population is evaluated, multiple individuals are stochastically selected from the current population (based on their fitness), and modified (recombined and possibly randomly mutated) to form a new population. The new population is then used in the next iteration of the algorithm. Commonly, the algorithm terminates when either a maximum number of generations has been produced, or a satisfactory fitness level has been reached for the population. If the algorithm has terminated due to a maximum number of generations, a satisfactory solution may or may not have been reached. Genetic algorithms find application in bioinformatics, phylogenetics, computational science, engineering, economics, chemistry, manufacturing, mathematics, physics and other fields. A typical genetic algorithm requires: 1. a genetic representation of the solution domain, 2. a fitness function to evaluate the solution domain. A standard representation of the solution is as an array of bits. Arrays of other types and structures can be used in essentially the same way. The main property that makes these genetic representations convenient is that their parts are easily aligned due to their fixed size, which facilitates simple crossover operations. Variable length representations may also be used, but crossover implementation is more complex in this case. Tree-like representations are explored in genetic programming and graphform representations are explored in evolutionary programming. The fitness function is defined over the genetic representation and measures the quality of the represented solution. The fitness function is always problem dependent. For instance, in the knapsack problem one wants to maximize the total value of objects that can be put in a knapsack of some fixed capacity. A representation of a solution might be an array of bits, where each bit represents a different object, and the value of the bit (0 or 1) represents whether or not the object is in the knapsack. Not every such representation is valid, as the size of objects may exceed the capacity of the knapsack. The fitness of the solution is the sum of values of all objects in the knapsack if the representation is valid or 0 otherwise. In some problems, it is hard or even impossible to define the fitness expression; in these cases, interactive genetic algorithms are used. Once we have the genetic representation and the fitness function defined, GA proceeds to initialize a population of solutions randomly, then improve it through repetitive application of mutation, crossover, inversion and selection operators. Initialization Initially many individual solutions are randomly generated to form an initial population. The population size depends on the nature of the problem, but typically contains several hundreds or thousands of possible solutions. Traditionally, the population is generated randomly, covering the entire range of possible solutions (the search space). Occasionally, the solutions may be "seeded" in areas where optimal solutions are likely to be found.

College Of Engineering Adoor Computer Science & Engg.

5 Department of

GENETIC ALGORITHMS Selection During each successive generation, a proportion of the existing population is selected to breed a new generation. Individual solutions are selected through a fitness-based process, where fitter solutions (as measured by a fitness function) are typically more likely to be selected. Certain selection methods rate the fitness of each solution and preferentially select the best solutions. Other methods rate only a random sample of the population, as this process may be very time-consuming. Most functions are stochastic and designed so that a small proportion of less fit solutions are selected. This helps keep the diversity of the population large, preventing premature convergence on poor solutions. Popular and well-studied selection methods include roulette wheel selection and tournament selection.

Reproduction Main articles: crossover (genetic algorithm) and mutation (genetic algorithm) The next step is to generate a second generation population of solutions from those selected through genetic operators: crossover (also called recombination), and/or mutation. For each new solution to be produced, a pair of "parent" solutions is selected for breeding from the pool selected previously. By producing a "child" solution using the above methods of crossover and mutation, a new solution is created which typically shares many of the characteristics of its "parents". New parents are selected for each child, and the process continues until a new population of solutions of appropriate size is generated. Although reproduction methods that are based on the use of two parents are more "biology inspired", recent researches more than two "parents" are better to be used to reproduce a good quality chromosome. These processes ultimately result in the next generation population of chromosomes that is different from the initial generation. Generally the average fitness will have increased by this procedure for the population, since only the best organisms from the first generation are selected for breeding, along with a small proportion of less fit solutions, for reasons already mentioned above. Termination This generational process is repeated until a termination condition has been reached. Common terminating conditions are: •

A solution is found that satisfies minimum criteria

•

Fixed number of generations reached

•

Allocated budget (computation time/money) reached

•

The highest ranking solution's fitness is reaching or has reached a plateau such that successive iterations no longer produce better results

•

Manual inspection

•

Combinations of the above

College Of Engineering Adoor Computer Science & Engg.

6 Department of

GENETIC ALGORITHMS

1. BIOLOGICAL BACKGROUND Chromosome All living organisms consist of cells. In each cell there is the same set of chromosomes. Chromosomes are strings of DNA and serves as a model for the whole organism. A chromosome consists of genes, blocks of DNA. Each gene encodes a particular protein. Basically, it can be said, that each gene encodes a trait, for example color of eyes. Possible settings for a trait (e.g. blue, brown) are called alleles. Each gene has its own position in the chromosome. This position is called locus. Complete set of genetic material (all chromosomes) is called genome. Particular set of genes in genome is called genotype. The genotype is with later development after birth base for the organism's phenotype, its physical and mental characteristics, such as eye color, intelligence etc.

Reproduction During reproduction, first occurs recombination (or crossover). Genes from parents form in some way the whole new chromosome. The new created offspring can then be mutated. Mutation means, that the elements of DNA are a bit changed. These changes are mainly caused by errors in copying genes from parents.

College Of Engineering Adoor Computer Science & Engg.

7 Department of

GENETIC ALGORITHMS The fitness of an organism is measured by success of the organism in its life.

2. SEARCH SPACE If we are solving some problem, we are usually looking for some solution, which will be the best among others. The space of all feasible solutions (it means objects among those the desired solution is) is called search space (also state space). Each point in the search space represents one feasible solution. Each feasible solution can be "marked" by its value or fitness for the problem. We are looking for our solution, which is one point (or more) among feasible solutions - that is one point in the search space. The looking for a solution is then equal to a looking for some extreme (minimum or maximum) in the search space. The search space can be whole known by the time of solving a problem, but usually we know only a few points from it and we are generating other points as the process of finding solution continues.

Example of a search space The problem is that the search can be very complicated. One does not know where to look for the solution and where to start. There are many methods, how to find some suitable solution (i.e. not necessarily the best solution), for example hill climbing, tabu search, simulated annealing and genetic algorithm. The solution found by these methods is often considered as a good solution, because it is not often possible to prove what the real optimum is.

NP-hard Problems College Of Engineering Adoor Computer Science & Engg.

8 Department of

GENETIC ALGORITHMS Examples of difficult problems, which cannot be solved in "traditional" way, are NP problems. There are many tasks for which we know fast (polynomial) algorithms. There are also some problems that are not possible to be solved algorithmically. For some problems was proved that they are not solvable in polynomial time. But there are many important tasks, for which it is very difficult to find a solution, but once we have it, it is easy to check the solution. This fact led to NP-complete problems. NP stands for nondeterministic polynomial and it means that it is possible to "guess" the solution (by some nondeterministic algorithm) and then check it, both in polynomial time. If we had a machine that can guess, we would be able to find a solution in some reasonable time. Studying of NP-complete problems is for simplicity restricted to the problems, where the answer can be yes or no. Because there are tasks with complicated outputs, a class of problems called NP-hard problems has been introduced. This class is not as limited as class of NP-complete problems. For NP-problems is characteristic that some simple algorithm to find a solution is obvious at a first sight - just trying all possible solutions. But this algorithm is very slow (usually O(2n)) and even for a bit bigger instances of the problems it is not usable at all. Today nobody knows if some faster exact algorithm exists. Proving or disproving this remains as a big task for new researchers. Today many people think, that such an algorithm does not exist and so they are looking for some alternative methods example of these methods are genetic algorithms. Examples of the NP problems are satisfiability problem, travelling salesman problem or knapsack problem.

3. GENETIC ALGORITHM Basic Description Genetic algorithms are inspired by Darwin's theory about evolution. Solution to a problem solved by genetic algorithms is evolved. Algorithm is started with a set of solutions (represented by chromosomes) called population. Solutions from one population are taken and used to form a new population. This is motivated by a hope, that the new population will be better than College Of Engineering Adoor Computer Science & Engg.

9 Department of

GENETIC ALGORITHMS the old one. Solutions which are selected to form new solutions (offspring) are selected according to their fitness - the more suitable they are the more chances they have to reproduce. This is repeated until some condition (for example number of populations or improvement of the best solution) is satisfied. Outline of the Basic Genetic Algorithm 1. [Start] Generate random population of n chromosomes (suitable solutions for the problem) 2. [Fitness] Evaluate the fitness f(x) of each chromosome x in the population 3. [New population] Create a new population by repeating following steps until the new population is complete 1. [Selection] Select two parent chromosomes from a population according to their fitness (the better fitness, the bigger chance to be selected) 2. [Crossover] With a crossover probability cross over the parents to form a new offspring (children). If no crossover was performed, offspring is an exact copy of parents. 3. [Mutation] With a mutation probability mutate new offspring at each locus (position in chromosome). 4. [Accepting] Place new offspring in a new population 4. [Replace] Use new generated population for a further run of algorithm 5. [Test] If the end condition is satisfied, stop, and return the best solution in current population 6. [Loop] Go to step 2

This outline of basic GA is very general. There are many things that can be implemented differently in various problems. First question is how to create chromosomes, what type of encoding choose. With this is connected crossover and mutation, the two basic operators of GA. Encoding, crossover and mutation are introduced in next chapter. Next question is how to select parents for crossover. This can be done in many ways, but the main idea is to select the better parents (in hope that the better parents will produce better offspring). Also you may think, that making new population only by new offspring can cause lost of the best chromosome from the last population. This is true, so the so called elitism is often used. This means, that at least one best solution

College Of Engineering Adoor Computer Science & Engg.

10 Department of

GENETIC ALGORITHMS is copied without changes to a new population, so the best solution found can survive to end of run.

1. OPERATORS OF GA Overview As you can see from the genetic algorithm outline, the crossover and mutation are the most important part of the genetic algorithm. The performance is influenced mainly by these two operators. Before we can explain more about crossover and mutation, some information about chromosomes will be given. Encoding of a Chromosome The chromosome should in some way contain information about solution which it represents. The most used way of encoding is a binary string. The chromosome then could look like this:

College Of Engineering Adoor Computer Science & Engg.

11 Department of

GENETIC ALGORITHMS Chromosome 1 1101100100110110 Chromosome 2 1101111000011110 Each chromosome has one binary string. Each bit in this string can represent some characteristic of the solution. Or the whole string can represent a number. Of course, there are many other ways of encoding. This depends mainly on the solved problem. For example, one can encode directly integer or real numbers; sometimes it is useful to encode some permutations and so on. Crossover After we have decided what encoding we will use, we can make a step to crossover. Crossover selects genes from parent chromosomes and creates a new offspring. The simplest way how to do this is to choose randomly some crossover point and everything before this point, copy from a first parent and then everything after it copy from the second parent. Crossover can then look like this ( | is the crossover point): Chromosome 1 Chromosome 2 Offspring 1 Offspring 2

11011 | 00100110110 11011 | 11000011110 11011 | 11000011110 11011 | 00100110110

There are other ways how to make crossover, for example we can choose more crossover points. Crossover can be rather complicated and very depends on encoding of the encoding of chromosome. Specific crossover made for a specific problem can improve performance of the genetic algorithm. Mutation After a crossover is performed, mutation take place. This is to prevent falling all solutions in population into a local optimum of solved problem. Mutation changes randomly the new offspring. For binary encoding we can switch a few randomly chosen bits from 1 to 0 or from 0 to 1. Mutation can then be following: Original offspring 1 Original offspring 2 Mutated offspring 1 Mutated offspring 2

1101111000011110 1101100100110110 1100111000011110 1101101100110110

The mutation depends on the encoding as well as the crossover. For example when we are encoding permutations, mutation could be exchanging two genes

College Of Engineering Adoor Computer Science & Engg.

12 Department of

GENETIC ALGORITHMS

2. SELECTION As we already know the chromosomes are selected from the population to be parents to crossover. The problem is how to select these chromosomes. According to Darwin's evolution theory the best ones should survive and create new offspring. There are many methods how to select the best chromosomes, for example roulette wheel selection, Boltzman selection, tournament selection, rank selection, steady state selection and some others. Some of them will be described in this chapter. Roulette Wheel Selection This is a way of choosing members from the population of chromosomes in a way that is proportional to their fitness. It does not guarantee that the fittest member goes through to the next generation, merely that it has a very good chance of doing so. It works like this: Imagine that the population’s total fitness score is represented by a pie chart, or roulette wheel. Now you assign a slice of the wheel to each member of the population. The size of the slice is proportional to that chromosomes fitness score. i.e. the fitter a member is the bigger the slice of pie it gets. Now, to choose a chromosome all you have to do is spin the ball and grab the chromosome at the point it stops.

College Of Engineering Adoor Computer Science & Engg.

13 Department of

GENETIC ALGORITHMS Then a marble is thrown there and selects the chromosome. Chromosome with bigger fitness will be selected more times.

This can be simulated by following algorithm. 1. [Sum] Calculate sum of all chromosome fatnesses in population - sum S. 2. [Select] Generate random number from interval (0,S) - r. 3. [Loop] Go through the population and sum fatnesses from 0 - sum s. When the sum s is greater, then r, stop and return the chromosome where you are. Of course, step 1 is performed only once for each population. Rank Selection The previous selection will have problems when the finesses differ very much. For example, if the best chromosome fitness is 90% of the entire roulette wheel then the other chromosomes will have very few chances to be selected. Rank selection first ranks the population and then every chromosome receives fitness from this ranking. The worst will have fitness 1, second worst 2 etc. and the best will have fitness N (number of chromosomes in population). You can see in following picture, how the situation changes after changing fitness to order number.

Situation before ranking (graph of finesses)

Situation after ranking (graph of order numbers)

College Of Engineering Adoor Computer Science & Engg.

14 Department of

GENETIC ALGORITHMS After this all the chromosomes have a chance to be selected. But this method can lead to slower convergence, because the best chromosomes do not differ so much from other ones. Steady-State Selection This is not particular method of selecting parents. Main idea of this selection is that big part of chromosomes should survive to next generation. GA then works in a following way. From every generation, are selected a few (good with high fitness) chromosomes for creating a new offspring. Then some (bad - with low fitness) chromosomes are removed and the new offspring is placed in their place. The rest of population survives to new generation. Elitism Idea of elitism has been already introduced. When creating new population by crossover and mutation, we have a big chance, that we will lose the best chromosome. Elitism is name of method, which first copies the best chromosome (or a few best chromosomes) to new population. The rest is done in classical way. Elitism can very rapidly increase performance of GA, because it prevents losing the best found solution.

1. ENCODING Introduction

College Of Engineering Adoor Computer Science & Engg.

15 Department of

GENETIC ALGORITHMS Encoding of chromosomes is one of the problems, when you are starting to solve problem with GA. Encoding very depends on the problem. In this chapter will be introduced some encodings, which have been already used with some success. Binary Encoding Binary encoding is the most common, mainly because first works about GA used this type of encoding. In binary encoding every chromosome is a string of bits, 0 or 1. Chromosome A 101100101100101011100101 Chromosome B 111111100000110000011111 Example of chromosomes with binary encoding Binary encoding gives many possible chromosomes even with a small number of alleles. On the other hand, this encoding is often not natural for many problems and sometimes corrections must be made after crossover and/or mutation. Example of Problem: Knapsack problem The problem: There are things with given value and size. The knapsack has given capacity. Select things to maximize the value of things in knapsack, but do not extend knapsack capacity. Encoding: Each bit says, if the corresponding thing is in knapsack. Permutation Encoding Permutation encoding can be used in ordering problems, such as travelling salesman problem or task ordering problem. In permutation encoding, every chromosome is a string of numbers, which represents number in a sequence. Chromosome A 1 5 3 2 6 4 7 9 8 Chromosome B 8 5 6 7 2 3 1 4 9 Example of chromosomes with permutation encoding Permutation encoding is only useful for ordering problems. Even for this problems for some types of crossover and mutation corrections must be made to leave the chromosome consistent (i.e. have real sequence in it). Example of Problem: Travelling salesman problem (TSP) The problem: There are cities and given distances between them. Travelling salesman has to visit all of them, but he does not to travel very much. Find a sequence of cities to minimize travelled distance.

College Of Engineering Adoor Computer Science & Engg.

16 Department of

GENETIC ALGORITHMS Encoding: Chromosome says order of cities, in which salesman will visit them.

Value Encoding Direct value encoding can be used in problems, where some complicated value, such as real numbers, is used. Use of binary encoding for this type of problems would be very difficult. In value encoding, every chromosome is a string of some values. Values can be anything connected to problem, form numbers, real numbers or chars to some complicated objects. Chromosome A 1.2324 5.3243 0.4556 2.3293 2.4545 Chromosome B ABDJEIFJDHDIERJFDLDFLFEGT Chromosome C (back), (back), (right), (forward), (left) Example of chromosomes with value encoding

Value encoding is very good for some special problems. On the other hand, for this encoding is often necessary to develop some new crossover and mutation specific for the problem. Example of Problem: Finding weights for neural network The problem: There is some neural network with given architecture. Find weights for inputs of neurons to train the network for wanted output. Encoding: Real values in chromosomes represent corresponding weights for inputs. Tree Encoding Tree encoding is used mainly for evolving programs or expressions, for genetic programming. In tree encoding every chromosome is a tree of some objects, such as functions or commands in programming language. Chromosome A

Chromosome B

College Of Engineering Adoor Computer Science & Engg.

17 Department of

GENETIC ALGORITHMS

(+ x (/ 5 y))

( do_until step wall )

Example of chromosomes with tree encoding Tree encoding is good for evolving programs. Programming language LISP is often used to this, because programs in it are represented in this form and can be easily parsed as a tree, so the crossover and mutation can be done relatively easily. Example of Problem: Finding a function from given values. The problem: Some input and output values are given. Task is to find a function, which will give the best (closest to wanted) output to all inputs. Encoding: Chromosomes are functions represented in a tree.

2. CROSSOVER AND MUTATION Introduction Crossover and mutation are two basic operators of GA. Performance of GA very much depend on them. Type and implementation of operators depends on encoding and also on a problem. There are many ways how to do crossover and mutation. In this chapter are only some examples and suggestions how to do it for several encoding. Binary Encoding Crossover Single point crossover - one crossover point is selected, binary string from beginning of chromosome to the crossover point is copied from one parent, the rest is copied from the second parent

College Of Engineering Adoor Computer Science & Engg.

18 Department of

GENETIC ALGORITHMS 11001011+11011111 = 11001111 Two point crossover - two crossover point are selected, binary string from beginning of chromosome to the first crossover point is copied from one parent, the part from the first to the second crossover point is copied from the second parent and the rest is copied from the first parent

11001011 + 11011111 = 11011111

Uniform crossover - bits are randomly copied from the first or from the second parent

11001011 + 11011101 = 11011111 Arithmetic crossover - some arithmetic operation is performed to make a new offspring

11001011 + 11011111 = 11001001 (AND) Mutation Bit inversion - selected bits are inverted

11001001 => 10001001

College Of Engineering Adoor Computer Science & Engg.

19 Department of

GENETIC ALGORITHMS

Permutation Encoding Crossover Single point crossover - one crossover point is selected, till this point the permutation is copied from the first parent, then the second parent is scanned and if the number is not yet in the offspring it is added Note: there are more ways how to produce the rest after crossover point (1 2 3 4 5 6 7 8 9) + (4 5 3 6 8 9 7 2 1) = (1 2 3 4 5 6 8 9 7) Mutation Order changing - two numbers are selected and exchanged (1 2 3 4 5 6 8 9 7) => (1 8 3 4 5 6 2 9 7) Crossover All crossovers from binary encoding can be used Mutation Adding a small number (for real value encoding) - to selected values is added (or subtracted) a small number (1.29 5.68 2.86 4.11 5.55) => (1.29 5.68 2.73 4.22 5.55)

3. APPLICATIONS OF GENETIC ALGIORITHMS Genetic algorithms has been used for difficult problems (such as NP-hard problems), for machine learning and also for evolving simple programs. They have been also used for some art, for evolving pictures and music.

College Of Engineering Adoor Computer Science & Engg.

20 Department of

GENETIC ALGORITHMS Advantage of GAs is in their parallelism. GA is travelling in a search space with more individuals (and with genotype rather than phenotype) so they are less likely to get stuck in a local extreme like some other methods. They are also easy to implement. Once you have some GA, you just have to write new chromosome (just one object) to solve another problem. With the same encoding you just change the fitness function and it is all. On the other hand, choosing encoding and fitness function can be difficult. Disadvantage of GAs is in their computational time. They can be slower than some other methods. But with today’s computers it is not so big problem. Some applications where GAs are used: •

Nonlinear dynamical systems - predicting, data analysis

•

Designing neural networks, both architecture and weights

•

Robot trajectory

•

Evolving LISP programs (genetic programming)

•

Strategy planning

•

Finding shape of protein molecules

•

TSP and sequence scheduling

•

Functions for creating images

GA on optimization and planning: Travelling Salesman Problem The TSP is interesting not only from a theoretical point of view, many practical applications can be modeled as a travelling salesman problem or as variants of it, for example, pen movement of a plotter, drilling of printed circuit boards (PCB), realworld routing of school buses, airlines, delivery trucks and postal carriers. Researchers have tracked TSPs to study bimolecular pathways, to route a computer networks' parallel processing, to advance cryptography, to determine the order of thousands of exposures needed in X-ray crystallography and to determine routes searching for forest fires (which is a multiple-salesman problem partitioned into single TSPs). Therefore, there is a tremendous need for algorithms.

In the last two decades an enormous progress has been made with respect to solving travelling salesman problems to optimality which, of course, is the ultimate goal of every researcher. One of landmarks in the search for optimal solutions is a 3038-city problem. This progress is only partly due to the increasing hardware power of computers. Above all, it was made possible by the development of mathematical theory and of efficient algorithms. Here, the GA approach is discussed. There are strong relations between the constraints of the problem, the representation adopted and the genetic operators that can be used with it. The goal of traveling Salesman Problem is to devise a travel plan (a tour) which minimizes the total distance travelled. TSP is NP-hard (NP stands for non-deterministic polynomial time)

College Of Engineering Adoor Computer Science & Engg.

21 Department of

GENETIC ALGORITHMS - it is generally believed cannot be solved (exactly) in time polynomial. The TSP is constrained: • •

The salesman can only be in a city at any time. Cities have to be visited once and only once.

When GAs applied to very large problems, they fail in two aspects: 1. They scale rather poorly (in terms of time complexity) as the number of cities increases. 2. The solution quality degrades rapidly. To use a standard GA, the following problems have to be solved: •

A binary representation for tours is found such that it can be easily translated into a chromosome.

•

An appropriate fitness function is designed, taking the constraints into account.

Non-permutation matrices represent unrealistic solutions, that is, the GA can generate some chromosomes that do not represent valid solutions. This happens: • in the random initialization step of the GA. • as a result of genetic operators (mutation and crossover). Thus, permutation matrices are used. Two tours including the same cities in the same order but with different starting points or different directions are represented by different matrices and hence by different chromosomes, for example: tour (23541) = tour (12354)

However, the ordinary genetic operators generate too many invalid solutions, leading to poor results. Alternative solutions to TSP require new representations (Position Dependent Representations) and new genetic operators. Evolutionary Divide and Conquer (EDAC) This approach, EDAC, has potential for any search problem in which knowledge of good solutions for sub problems can be exploited to improve the solution of the problem itself. The idea is to use the Genetic Algorithm to explore the space of problem subdivisions rather than the space of solutions themselves, and thus capitalize on the near linear scaling qualities generally inherent in the divide and conquer approach. The basic mechanisms for dissecting a TSP into sub problems, solving the sub problems and then patching the sub tours together to form a global tour, have been obtained from the cellular dissection algorithms of Richard Karp. Although solution quality tends to be rather poor, Karp`s algorithms possess an attractively simple

College Of Engineering Adoor Computer Science & Engg.

22 Department of

GENETIC ALGORITHMS geometrical approach to dissection, and offer reasonable guarantees of performance. Moreover, EDAC approach is intrinsically parallel. The EDAC approach has lifted the application of GAs to TSP an order or magnitude larger in terms of problem sizes than permutation representations. Experimental results demonstrate the successful properties for EDAC on uniform random points and PCB problems in the range 500 - 5000 cities. GA in Business and Their Supportive Role in Decision Making Genetic Algorithms have been used to solve many different types of business problems in functional areas such as finance, marketing, information systems, and production/ operations. Within these functional areas, GAs have performed a variety of applications such as tactical asset allocation, job scheduling, machine-part grouping, and computer network design. Finance Applications Models for tactical asset allocation and international equity strategies have been improved with the use of GAs. They report an 82% improvement in cumulative portfolio value over a passive benchmark model and a 48% improvement over a nonGA model designed to improve over the passive benchmark. Genetic algorithms are particularly well-suited for financial modeling applications for three reasons: 1. They are payoff driven. Payoffs can be improvements in predictive power or returns over a benchmark. There is an excellent match between the tool and the problems addressed. 2. They are inherently quantitative, and well-suited to parameter optimization (unlike most symbolic machine learning techniques). 3. They are robust, allowing a wide variety of extensions and constraints that cannot be accommodated in traditional methods." Information Systems Applications Distributed computer network topologies are designed by a GA, using three different objective functions to optimize network reliability parameters, namely diameter, average distance, and computer network reliability. The GA has successfully designed networks with 100 order of nodes. GA has also been used to determine file allocation for a distributed system. The objective is to maximize the programs' abilities to reference the file s located on remote nodes. The problem is solved with the following three different constraint sets: 1. There is exactly one copy of each file to be distributed. 2. There may be any number of copies of each file subject to a finite memory constraint at each node.

College Of Engineering Adoor Computer Science & Engg.

23 Department of

GENETIC ALGORITHMS 3. The number of copies and the amount of memory are both limited. Production/Operation Applications Genetic Algorithm has been used to schedule jobs in a sequence dependent setup environment for a minimal total tardiness. All jobs are scheduled on a single machine; each job has a processing time and a due date. The setup time of each job is dependent upon the job which immediately precedes it. The GA is able to find good, but not necessarily optimal schedules, fairly quickly. GA is also used to schedule jobs in non-sequence dependent setup environment. The jobs are scheduled on one machine with the objective of minimizing the total generally weighted penalty for earliness or tardiness from the jobs' due dates. However, this does not guarantee that it will generate optimal solutions for all schedules.

GA is developed for solving the machine-component grouping problem required for cellular manufacturing systems. GA provides a collection of satisfactory solutions for a two objective environment (minimizing cell load variation and minimizing volume of inter cell movement), allowing the decision maker to then select the best alternative. Role in Decision Making Applying the well established decision processing phase model of Simon (1960), Genetic Algorithms appear to be very well suited for supporting the design and choice phases of decision making. •

In solving a single objective problem, GA designs many solutions until no further improvement (no increase in fitness) can be achieved or some predetermined number of generations has evolved or when the allotted processing time is complete. The fit solution in the final generation is the one that maximizes or minimizes the objective (fitness) function; this solution can be thought of as the GA has recommended choice. Therefore with single objective problems the user of GA is assisted in the choice phase of decision processing.

•

When solving multi-objective problems, GA gives out many satisfactory solutions in terms of the objectives, and then allows the decision maker to select the best alternative. Therefore GAs assist with the design phase of decision processing with multi-objective problems.

GAs can be of great assistance for examining alternatives since they are designed to evaluate existing potential solutions as well to generate new (and better) solutions for evaluation. Thus GAs can improve the quality of decision making.

College Of Engineering Adoor Computer Science & Engg.

24 Department of

GENETIC ALGORITHMS

Learning Robot behavior using Genetic Algorithms Robot has become such a prominent tool that it has increasingly taken a more important role in many different industries. As such, it has to operate with great efficiency and accuracy. This may not sound very difficult if the environment in which the robot operates remain unchanged, since the behaviors of the robot could be pre-programmed. However, if the environment is ever-changing, it gets extremely difficult, if not impossible, for programmers to figure out every possible behaviors of the robot. Applying robot in a changing environment is not only inevitable in modern technology, but is also becoming more frequent. This has obviously led to the development of a learning robot. The approach to learning behaviors, which lead the robot to its goal, described here reflects a particular methodology for learning via simulation model. The motivation is that making mistakes on real system can be costly and dangerous. In addition, time constraints may limit the extent of learning in real world. Since learning requires experimenting with behaviors that might occasionally produce undesirable results if applied to real world. Therefore the current best behavior can be placed in the real, on-line system, while learning continues in the off-line system. Previous studies have shown that knowledge learned under simulation is robust and might be applicable to the real world if the simulation is more general (add more noise and distortion). If this is not possible, the differences between the real world and the simulation have to be identified. GAs' Role Genetic Algorithms are adaptive search techniques that can learn high performance knowledge structures. The genetic algorithms' strength come from the implicitly parallel search of the solution space that it performs via a population of candidate solutions and this population is manipulated in the simulation. The candidate solutions represent every possible behavior of the robot and based on the overall performance of the candidates, each could be assigned a fitness value. Genetic operators could then be applied to improve the performance of the population of behaviors. One cycle of testing all of the competing behavior is defined as a generation, and is repeated until a good behavior is evolved. The good behavior is then applied to the real world. Also because of the nature of GA, the initial knowledge does not have to be very good. The system described has been used to learn behaviors for controlling simulate autonomous underwater vehicles, missile evasion, and other simulated tasks. Future

College Of Engineering Adoor Computer Science & Engg.

25 Department of

GENETIC ALGORITHMS work will continue examining the process of building robotic system through evolution. We want to know how multiple behaviors that will be required for a higher

level task interact, and how multiple behaviors can be evolved simultaneously. We are also examining additional ways to bias the learning both with initial rule sets, and by modifying the rule sets during evolution through human interaction. Other open problems include how to evolve hierarchies of skills and how to enable the robot to evolve new fitness functions as the need for new skill arises. Genetic Algorithms for Object Localization in a Complex Scene Robot Vision In order to provide machines with the ability to interact in complex, real-world environments, and sensory data must be presented to the machine. One such module dealing with sensory input is the visual data processing module, also known as the computer vision module. A central task of this computer vision module is to recognize objects from images of the environment. There are two different parts to computer vision modules, namely segmentation and recognition. Segmentation is the process of finding interested objects while recognition works to see if the located object matches the predefined attributes. Since images cannot be recognized until they have been located and separated from the background, it is of paramount importance that this vision module is able to locate different objects of interest for different systems with great efficiency. GA parameters The task of locating a particular object of interest in a complex scene is quite simple when cast in the framework of genetic algorithms. The brute force-force method for finding an object in a complex scene is to examine all positions and sizes, with varying degrees of occlusion of the objects, to determine whether the extracted sub image matches a rough notion of what is being sought. This method is immediately dismissed as it is far too computational expensive to achieve. The use of genetic methodology, however, can raise the brute-force setup to an elegant solution to this complex problem. Since the GA approach does well in very large search spaces by working only with a sample available population, the computational limitation of the brute-force method using full search space enumeration does not apply. An experiment was actually carried out based on the following technique, GAs optimized for Portability and Parallelism developed at Michigan State University. It has been shown that the genetic algorithm perform better in finding areas of interest even in a complex, real-world scene. Genetic Algorithms are adaptive to their environments, and as such this type of method is appealing to the vision community who must often work in a changing environment. However, several improvements must be made in order that GAs could be more generally applicable. Grey coding the field would greatly improve the mutation operation while combing segmentation with

College Of Engineering Adoor Computer Science & Engg.

26 Department of

GENETIC ALGORITHMS recognition so that the interested object could be evaluated at once. Finally, timing improvement could be done by utilizing the implicit parallelization of multiple independent generations evolving at the same time. Artificial Life Genetic algorithms are currently the most prominent and widely used computational models of evolution in artificial-life systems. These decentralized models provide a basis for understanding many other systems and phenomena in the world. Researches on GAs in alife give illustrative examples in which the genetic algorithm is used to study how learning and evolution interact, and to model ecosystems, immune system, cognitive systems, and social systems. Artificial-life programmers claim that, with the help of the increasingly advanced technology, they will soon go beyond merely modeling or simulating living organisms and actually create life. The claim is not simply that one could design an artificial life with the help of a computer, and then build it out of organic molecules. They claim that one could create living organism simply by programming a computer in a right way. If today's virus is not alive, tomorrows will be. Computer equivalent of worm, frog would soon be rampaging in the networks. This claim is known as "strong Alife", as opposed to “weak A-life". Other Applications of Genetic Algorithms Automotive Design Using Genetic Algorithms [GAs] to both design composite materials and aerodynamic shapes for race cars and regular means of transportation (including aviation) can return combinations of best materials and best engineering to provide faster, lighter, more fuel efficient and safer vehicles for all the things we use vehicles for. Rather than spending years in laboratories working with polymers, wind tunnels and balsa wood shapes, the processes can be done much quicker and more efficiently by computer modeling using GA searches to return a range of options human designers can then put together however they please.

Engineering Design Getting the most out of a range of materials to optimize the structural and operational design of buildings, factories, machines, etc. is a rapidly expanding application of GAs. These are being created for such uses as optimizing the design of heat exchangers, robot gripping arms, satellite booms, building trusses, flywheels,

College Of Engineering Adoor Computer Science & Engg.

27 Department of

GENETIC ALGORITHMS turbines, and just about any other computer-assisted engineering design application. There is work to combine GAs optimizing particular aspects of engineering problems to work together, and some of these can not only solve design problems, but also project them forward to analyze weaknesses and possible point failures in the future so these can be avoided. Robotics Robotics involves human designers and engineers trying out all sorts of things in order to create useful machines that can do work for humans. Each robot's design is dependent on the job or jobs it is intended to do, so there are many different designs out there. GAs can be programmed to search for a range of optimal designs and components for each specific use, or to return results for entirely new types of robots that can perform multiple tasks and have more general application. GA-designed robotics just might get us that nifty multi-purpose, learning robots we've been expecting any year now since we watched the Jetsons as kids, who will cook our meals, do our laundry and even clean the bathroom for us! Evolvable Hardware Evolvable hardware applications are electronic circuits created by GA computer models that use stochastic (statistically random) operators to evolve new configurations from old ones. As the algorithm does its thing in the running model, eventually a circuit configuration will come along that does what the designer wants. Think of reconfigurable circuits in something like a space robot. It could use a built-in GA library and simulator to re-design itself after something like radiation exposure that messes up its normal configuration, or encounters a novel situation in which it needs a function it doesn't already have. Such GAs would enable self-adaptation and self-repair. Optimized Telecommunications Routing GAs are being developed that will allow for dynamic and anticipatory routing of circuits for telecommunications networks. These could take notice of your system's instability and anticipate your re-routing needs. Using more than one GA circuitsearch at a time, soon your interpersonal communications problems may really be all in your head rather than in your telecommunications system. Other GAs are being developed to optimize placement and routing of cell towers for best coverage and ease of switching. Joke and Pun Generation Among the linguistic applications of GAs - including a JAPE (automated pun generator) inspired STANDUP program to design communications strategies for people working with children who suffer communications disabilities - are GAs that search for jokes and puns. These come under the heading of "artificial creativity" and AI, but could prove very useful to class clowns and wannabe punsters whose public reputations depend upon being funnier than they actually are. These clever GAs will let you input a word you wish to pun or a subject you'd like to joke about, and will return a variety of solutions that just might lead to a lucrative career on the comedy club circuit! Trip, Traffic and Shipment Routing College Of Engineering Adoor Computer Science & Engg.

28 Department of

GENETIC ALGORITHMS New applications of a GA known as the "Traveling Salesman Problem" or TSP can be used to plan the most efficient routes and scheduling for travel planners, traffic routers and even shipping companies. The shortest routes for traveling. The timing to avoid traffic tie-ups and rush hours. Most efficient use of transport for shipping, even to including pickup loads and deliveries along the way. The program can be modeling all this in the background while the human agents do other things, improving productivity as well! Chances are increasing steadily that when you get that trip plan packet from the travel agency, a GA contributed more to it than the agent did. Computer Gaming Those who spend some of their time playing computer Sims games (creating their own civilizations and evolving them) will often find themselves playing against sophisticated artificial intelligence GAs instead of against other human players online. These GAs have been programmed to incorporate the most successful strategies from previous games - the programs 'learn' - and usually incorporate data derived from game theory in their design. Game theory is useful in most all GA applications for seeking solutions to whatever problems they are applied to, even if the application really is a game. Biomimetic Invention Biomimicry or biomimetics is the development of technologies inspired by designs in nature. Since GAs are inspired by the mechanisms of biological evolution, it makes sense that they could be used in the process of invention as well. GAs rely primarily on something called implicit parallelism (like to like), using mutation and selection in secondary roles

toward a design solution. GA programmers are working on applications that not only analyze the natural designs themselves for a return on how they work, but can also combine natural designs to create something entirely new that can have exciting applications. Encryption and Code Breaking On the security front, GAs can be used both to create encryption for sensitive data as well as to break those codes. Encrypting data, protecting copyrights and breaking competitors' codes have been important in the computer world ever since there have been computers, so the competition is intense. Every time someone adds more complexity to their encryption algorithms, someone else comes up with a GA that can break the code. It is hoped that one day soon we will have quantum computers that will be able to generate completely indecipherable codes. Of course, by then the 'other guys' will have quantum computers too, so it's a sure bet the spy vs. spy games will go on indefinitely.

College Of Engineering Adoor Computer Science & Engg.

29 Department of

GENETIC ALGORITHMS Computer-Aided Molecular Design The de novo design of new chemical molecules is a burgeoning field of applied chemistry in both industry and medicine. GAs are used to aid in the understanding of protein folding, analyzing the effects of substitutions on those protein functions, and to predict the binding affinities of various designed proteins developed by the pharmaceutical industry for treatment of particular diseases. The same sort of GA optimization and analysis is used for designing industrial chemicals for particular uses, and in both cases GAs can also be useful for predicting possible adverse consequences. This application has and will continue to have great impact on the costs associated with development of new chemicals and drugs. Optimizing Chemical Kinetic Analysis In the not-so rarified realm of fuels and engines for combustion technologies, GAs are proving very useful toward optimizing designs in transportation, aerospace propulsion and electrical generation. By being able to predict ahead of time the chemical kinetics of fuels and the efficiency of engines, more optimal mixtures and designs can be made available quicker to industry and the public. Some computer modeling applications in this area also simulate the effectiveness of lubricants and can pinpoint optimized operational vectors, and may lead to greatly increased efficiency all around well before traditional fuels run out.

Gene Expression Profiling The development of microarray technology for taking 'snapshots' of the genes being expressed in a cell or group of cells has been a boon to medical research. GAs have been and are being developed to make analysis of gene expression profiles much quicker and easier. This helps to classify what genes play a part in various diseases, and further can help to identify genetic causes for the development of diseases. Being able to do this work quickly and efficiently will allow researchers to focus on individual patients' unique genetic and gene expression profiles, enabling the hopedfor "personalized medicine" we've been hearing about for several years.

College Of Engineering Adoor Computer Science & Engg.

30 Department of

GENETIC ALGORITHMS

CONCLUSION If the conception of a computer algorithms being based on the evolutionary of organism is surprising, the extensiveness with which this algorithms is applied in so many areas is no less than astonishing. These applications, be they commercial, educational and scientific, are increasingly dependent on this algorithms, the Genetic Algorithms. Its usefulness and gracefulness of solving problems has made it a more favorite choice among the traditional methods, namely gradient search, random search and others. GAs are very helpful when the developer does not have precise domain expertise, because GAs possess the ability to explore and learn from their domain. We would witness some developments of variants of GAs to tailor for some very specific tasks. This might defy the very principle of GAs that it is ignorant of the problem domain when used to solve problem. But we would realize that this practice could make GAs even more powerful. It is reasonable to predict that in a few years time Genetic Programming will be able to routinely and competently solve important problems for us, in a variety of application domains with human-competitive performance. Genetic programming will then become an essential collaborator for many human activities. This will be a remarkable step forward towards achieving true human-competitive machine intelligence.

College Of Engineering Adoor Computer Science & Engg.

31 Department of

GENETIC ALGORITHMS

REFRENCES

1. Wikipedia - http://en.wikipedia.org/wiki/Genetic_algorithm 2. Holland J.H., Adaptation in natural and artificial system. 3. Goldberg D., Genetic Algorithms, Addison Wesley. 4. Obitko (http://www.obitko.com/tutorials/genetic-algorithms/index.php) 5. http://www.doc.ic.ac.uk/~nd/surprise_96/journal/vol4/tcw2/report.html

College Of Engineering Adoor Computer Science & Engg.

32 Department of