Genetic Algorithm

• A genetic algorithm (GA) is a higher level method to produce/ generate a sufficiently good solution to an optimization problem, inspired by the process of natural selection that belongs to the larger class of evolutionary algorithms (EA).
• Genetic algorithms are commonly used to generate high-quality solutions to optimization and search problems by relying on biologically inspired operators such as mutation, crossover and selection.
• John Holland introduced genetic algorithms in 1960 based on the concept of Darwin’s theory of evolution

Evolutionary algorithms (EA):

In artificial intelligence (AI), an evolutionary algorithm (EA) is a subset of evolutionary computation, a generic population-based metaheuristic optimization algorithm. An EA uses mechanisms inspired by biological evolution, such as reproduction, mutation, recombination, and selection.

Evolutionary algorithms have three main characteristics:

· Population-Based: Evolutionary algorithms are to optimize a process in which current solutions are bad to generate new better solutions. The set of current solutions from which new solutions are to be generated is called the population.

· Fitness-Oriented: If there are some several solutions, how to say that one solution is better than another? There is a fitness value associated with each individual solution calculated from a fitness function. Such fitness value reflects how good the solution is.

· Variation-Driven: If there is no acceptable solution in the current population according to the fitness function calculated from each individual, we should make something to generate new better solutions. As a result, individual solutions will undergo a number of variations to generate new solutions.

In a genetic algorithm, a population of candidate solutions (called individuals, creatures, or phenotypes) to an optimization problem is evolved toward better solutions. Each candidate solution has a set of properties (its chromosomes or genotype) which can be mutated and altered; traditionally, solutions are represented in binary as strings of 0s and 1s, but other encodings are also possible.

The process of natural selection starts with the selection of fittest individuals from a population. They produce offspring which inherit the characteristics of the parents and will be added to the next generation. If parents have better fitness, their offspring will be better than parents and have a better chance at surviving. This process keeps on iterating and at the end, a generation with the fittest individuals will be found.

Six phases are considered in a genetic algorithm:

· Initial population

· Fitness function

· Selection

· Crossover

· Mutation

· Termination

flowchart for process in a genetic algorithm

Initial Population:

The process begins with a set of individuals which is called a Population. Each individual is a solution to the problem you want to solve. An individual is characterized by a set of parameters (variables) known as Genes. Genes are joined into a string to form a Chromosome (solution). There are different representations available for the chromosome and the selection of the proper representation is problem specific. The good representation is what makes the search space smaller and thus easier search.

The representations available for the chromosome including:

· Binary: Each chromosome is represented as a string of zeros and ones

· Permutation: Useful for ordering problems such as travelling salesman problem

· Value: The actual value is encoded as it is

Indivudal will have a chromosome, and chromosomes will have genes

Fitness Function:

The fitness function determines how fit an individual is (the ability of an individual to compete with other individuals). It gives a fitness score to each individual. The probability that an individual will be selected for reproduction is based on its fitness score.

Selection:

The idea of selection phase is to select the fittest individuals and let them pass their genes to the next generation. Two pairs of individuals (parents) are selected based on their fitness scores. Individuals with high fitness have more chance to be selected for reproduction.

Crossover:

Crossover is the most significant phase in a genetic algorithm. For each pair of parents to be mated, a crossover point is chosen at random from within the genes. Types of crossover techniques are:

· Single-point crossover

· Two-point and k-point crossover

· Uniform crossover

·Crossover for ordered lists

Mutation:

In certain new offspring formed, some of their genes can be subjected to a mutation with a low random probability. Mutation alters one or more gene values in a chromosome from its initial state. In mutation, the solution may change entirely from the previous solution. Hence GA can come to a better solution by using mutation.

different mutation types are :-

· Bit string mutation

· Flip Bit

Boundary

Non-Uniform

Uniform

Gaussian

Shrink

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