Genetic Algorithm

GENETIC ALGORITHM

Genetic algorithms are based on the theory of natural selection and work on generating a set of random solutions and making them compete in an area where only the fittest survive. Each solution in the set is equivalent to a chromosome. Genetic algorithm learning methods are based on models of natural adaption and evolution. These learning methods improve their performance through processes which model population genetics and survival of the fittest. In the field of genetics, a population is subjected to an environment which places demands on the members. The members which adapt well are selected for matting and reproduction. Generally genetic algorithm uses three basic genetic operators like reproduction, crossover and mutation. These are combined together to evolve a new population. Starting from a random set of solutions the algorithm uses these operators and the fitness function to guide its search for the optimal solution. The fitness function guesses how good the solution in question is and provides a measure to its capability. The genetic operators copy the mechanisms based on the principles of human evolution. The main advantage of the genetic algorithm formulation is that fairly accurate results may be obtained using a very simple algorithm. The genetic algorithm is a method of finding a good answer to a problem, based on the feedback received from its repeated attempts at a solution. The fitness function is a judge of the GA’s attempts for a problem. GA is incapable to derive a problem’s solution, but they are capable to know from the fitness function.

Genetic algorithm starts with a fixed size population of data structure which is used to perform some given tasks. After the structure performs the given task or problem, they are rated on their performance by some utility value and a new generation of data structure then created. The new generation is created by mapping with the high performing structure to produce offspring. The offsprings or the children and their parents are retained for the next generation while the poorer performers are not included. Mutations are also performed on the best programming structures to ensure that the full space of possible structure is reachable. This process is repeated for a number of generations until the resultant population consists of only the highest performing structures. Matting between two strings is accomplished with the crossover operation which randomly selects a bit position in the eight bit string and concatenates the head of one parent to the tail of the second parent to produce the off string. Inversion is another type of genetic operation which is applied to a single string.

The GA goes through the following cycle: Generate, Evaluate, Assignment of values, Mate and Mutate. One criteria is to let the GA run for a certain number of cycles. A second one is to allow the GA to run until a reasonable solution is found. Also mutation is a operation, which is used to ensure that all locations of the rule space are reachable, that every potential rule in the rule space is available for evaluation. The mutation operator is typically used only infrequently to prevent random wondering in the search space. Let us focus on the genetic algorithm described as follows.

Step 1:

Generate the initial population.

Step 2:

Calculate the fitness function of each individuals.

Step 3:

Some sort of performance utility values or the fitness values are assigned to individuals.

Step 4:

New populations are generated from the best individuals by the process of selection.

Step 5:

Perform the crossover and mutation operation.

Step 6:

Replace the old population with the new individuals.

Step 7:

Perform step-2 until the goal is reached.

In its simplest form, the standard genetic algorithm is a method of stochastic optimization for discrete programming problems of the form.

In this case f: Ω  R is called the fitness function and the n-dimensional binary vectors in Ω are called strings. The most noticeable difference between the standard genetic algorithm and the methods of optimization is that at each stage of the computation, genetic algorithms maintain a collection of samples