Genetic Algorithm is a programming technique who forms its basis from the biological evolution. Genetic Algorithm is basically used as a problem solving strategy in order to provide with a optimal solution. They are the best way to solve the problem for which little is known. They will work well in any search space because they form a very general algorithm. The only thing to be known is what the particular situation is where the solution performs very well, and a genetic algorithm will generate a high quality solution. Genetic algorithms use the principles of selection and evolution to produce several solutions to a given problem.
The input to the GA is a set of potential solutions to that problem, encoded in some fashion, and a metric called a fitness function that allows each candidate to be quantitatively evaluated. These candidates may be solutions already known to work, with the aim of the GA being to improve them, but more often they are generated at random.
The GA then evaluates each candidate according to the fitness function activity; the candidate with good fitness has high chances to get selected than the one with average fitness. Various functions is basically used to test the fitness of any particular individual. These individuals with high fitness can be termed as promising candidates.
These promising candidates are kept and allowed to reproduce. From them multiple copies are made, but the copies are not perfect; random changes are introduced during the copying process. These digital offspring then go on to the next generation, forming a new pool of candidate solutions, and are subjected to a second round of fitness evaluation. Those candidate solutions which were worsened, or made no better, by the changes to their code are again deleted; but again, purely by chance, the random variations introduced into the population may have improved some individuals, making them into better, more complete or more efficient solutions to the problem at hand. Again these winning individuals are selected and copied over into the next generation with random changes, and the process repeats. The expectation is that the average fitness of the population will increase each round, and so by repeating this process for hundreds or thousands of rounds, very good solutions to the problem can be discovered.
Genetic algorithms have proven to be an enormously powerful and successful problem-solving strategy. Genetic algorithms have been used in a wide variety of fields to find solutions to problems that are more difficult than those faced by human designers. Thus, the solutions they come up with are often more efficient, more elegant, or more complex than anything comparable a human engineer would produce.
Functionality of Genetic Algorithm
1. Selection-
There are many different techniques which a genetic algorithm can use to select the individuals to be copied over into the next generation.
Elitist selection: The fittest members of each generation are guaranteed to be selected.
Fitness-proportionate selection: More fit individuals are more likely, but not certain, to be selected.
Roulette-wheel selection: A form of fitness-proportionate selection in which the chance of an individual's being selected is proportional to the amount by which its fitness is greater or less than its competitors' fitness
Scaling selection: As the average fitness of the population increases, the strength of the selective pressure also increases and the fitness function becomes more discriminating. This method can be helpful in making the best selection later on when all individuals have relatively high fitness and only small differences in fitness distinguish one from another.
Tournament selection: Subgroups of individuals are chosen from the larger population, and members of each subgroup compete against each other. Only one individual from each subgroup is chosen to reproduce.
2. Crossover :
Once the individuals have been selected the next thing is to produce the offspring. The most common solution for this is something called crossover, and while there are many different kinds of crossover, the most common type is single point crossover. In single point crossover, chooses a locus at which you swap the remaining alleles from one parent to the other.
The children take one section of the chromosome from each parent. The point at which the chromosome is broken depends on the randomly selected crossover point. This particular method is called single point crossover because only one crossover point exists. Sometimes only child 1 or child 2 is created, but oftentimes both offspring are created and put into the new population. Crossover does not always occur, however. Sometimes, based on a set probability, no crossover occurs and the parents are copied directly to the new population. The probability of crossover occurring is usually 60% to 70%.
3. Mutation :
After selection and crossover, we get new population full of individuals. Some are directly copied, and others are produced by crossover. In order to ensure that the individuals are not all exactly the same, you allow for a small chance of mutation. You loop through all the alleles of all the individuals, and if that allele is selected for mutation, you can either change it by a small amount or replace it with a new value.The probability of mutation is usually between 1 and 2 tenths of a percent. Mutation is fairly simple. We just change the selected alleles based on what you feel is necessary and move on. Mutation is, however, vital to ensuring genetic diversity within the population.
Issues of Genetic Algorithm:
1. Certain optimization problems (they are called variant problems) cannot be solved by means of genetic algorithms. This occurs due to poorly known fitness functions which generate bad chromosome blocks in
spite of the fact that only good chromosome blocks cross-over.
2. There is no absolute assurance that a genetic algorithm will find a global optimum. It happens very often when the populations have a lot of subjects.
3. In case of Clinical decision support system GA faces lack of transparency that is used for the decision support systems making it undesirable for physicians.
The main challenge in using genetic algorithms is in defining the fitness criteria. In order to use a genetic algorithm, there must be many components such as multiple drugs, symptoms, treatment therapy and so on must be available in order to solve a problem.
4. In case of research study which investigated the possibility of automating parameter selection for an EEG-based P300-driven Brain-Computer Interface (BCI) Genetic Algorithm required lengthy execution times which render it infeasible for online utilization.
The GA method was subsequently replaced by the less execution time-intensive N-fold cross-validation (NFCV) for the meta-optimization of feature extraction and pre-processing parameters using Fisher’s Linear Discriminant Analysis (FLDA).
5. GA also faces Scalability Issues of Exchanging Building Blocks.
6. Like other artificial intelligence techniques, the genetic algorithm cannot assure constant optimization response times. Even more, the difference between the shortest and the longest optimization response time is much larger than with conventional gradient methods. This unfortunate genetic algorithm property limits the genetic algorithms' use in real time applications.
7. Genetic algorithm applications in controls which are performed in real time are limited because of random solutions and convergence, in other words this means that the entire population is improving, but this could not be said for an individual within this population. Therefore, it is unreasonable to use genetic algorithms for on-line controls in real systems without testing them first on a simulation model.