Genetic AlgorithmThe genetic algorithm applies concepts from evolutionary biology and at-tempts to find a good solution by mimicking the process of natural selectionand the “survival of the fittest”. The algorithm can be outlined as follows.• The potential solutions are viewed as members of a population. Eachsuch member can be described, for example, by a vector. Initially wecan start with a random population, i.e., a set of random vectors.• In each iteration certain operations are executed that randomly changethe population. Two fundamental operations are:– Mutation. This means that some randomly chosen individuals(vectors) undergo random changes. For example, some of theirbits (in case of binary vectors) are reversed.– Crossover. Two randomly selected individuals (vectors) “mate”and create offsprings that inherit the combined properties of theparents. For example, the components of the offspring vectors areobtained by swapping some components of the parent vectors.• After each round of random changes the fitness of each individual isevaluated by a fitness function that can measure how good is eachsolution vector. Those that are not fit enough, die, while the fit onessurvive.• The population evolves through such iterations. After a large numberof iterations one can hope that the arising population already containsgood solutions with high fitness value.Advantages of Genetic Algorithms• Offers a chance that the initial solutions evolve into good ones that areclose 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 algo-rithms).• There is no general way of estimating the number of iterations neededfor a problem, so we cannot easily decide how close is the result to aglobal optimum.ExerciseAssume that in a Genetic Algorithm the fitness of each individual memberof the population can be modeled as a random variable that is uniformlydistributed in the interval [0, 1]. Further asssume that for each individualthis random variable is independent from the others. We are looking for asolution (an individual) with as high fitness value as possible. The initialpopulation has size n. After each iteration of modifying the population viamutation and crossover operations we only keep the n fittest individuals, therest “die”. Which of the following is correct?1. The maximum fitness value found in the population will converge to 1,as the number of iterations grow. The reason is that the fittest individ-ual in the current population always survives when we keep only the nfittest. Since the fitness in our case is modeled as an independent, uni-formly distributed random variable in [0, 1], therefore, the probabilitythat we have an individual with fitness in [1 − ², 1] tends to 1 for every² > 0, if the number of iterations grow.2. Since there is no general performance guarantee for the Genetic Algo-rithm, therefore, we can never gurantee any kind of convergence.3. The convergence of the maximum occuring fittness to 1 under the givenassumptions is only guaranteed if n also grows with the
View Full Document