Genetic AlgorithmGenetic AlgorithmGenetic AlgorithmAdvantages of Genetic AlgorithmsDisadvantages of Genetic AlgorithmsGenetic Algorithm•The genetic algorithm applies concepts from evolutionary biology and attempts to find a good solution by mimicking the process of natural selection and the “survival of the fittest”. The algorithm can be outlined as follows.Genetic Algorithm•The potential solutions are viewed as members of a population. Each such member can be described, for example, by a vector. Initially we can start with a random population, i.e., a set of random vectors.•In each iteration certain operations are executed that randomly change the population. Two fundamental operations are:–Mutation. This means that some randomly chosen individuals (vectors) undergo random changes. For example, some of their bits (in case of binary vectors) are reversed.–Crossover. Two randomly selected individuals (vectors) “mate” and create offsprings that inherit the combined properties of the parents. For example, the components of the offspring vectors are obtained by swapping some components of the parent vectors.Genetic Algorithm•After each round of random changes the fitness of each individual is evaluated by a fitness function that can measure how good is each solution vector. Those that are not fit enough, die, while the fit ones survive.•The population evolves through such iterations. After a large number of iterations one can hope that the arising population already contains good solutions with high fitness value.Advantages of Genetic Algorithms•Offers a chance that the initial solutions evolve into good ones that are close to optimal.•The evolving population tends to have more and more fit individuals, so the algorithm may find many good solutions, not just one.Disadvantages of Genetic Algorithms•Nothing is guaranteed formally (usual problem with heuristic algorithms).•There is no general way of estimating the number of iterations needed for a problem, so we cannot easily decide how close is the result to a global
View Full Document