Evolutionary algorithm | EPFL Graph Search

In computational intelligence (CI), 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. Candidate solutions to the optimization problem play the role of individuals in a population, and the fitness function determines the quality of the solutions (see also loss function). Evolution of the population then takes place after the repeated application of the above operators. Evolutionary algorithms often perform well approximating solutions to all types of problems because they ideally do not make any assumption about the underlying fitness landscape. Techniques from evolutionary algorithms applied to the modeling of biological evolution are generally limited to explorations of microevolutionary processes and planning models based upon cellular processes. In most real applications of EAs, computational complexity is a prohibiting factor. In fact, this computational complexity is due to fitness function evaluation. Fitness approximation is one of the solutions to overcome this difficulty. However, seemingly simple EA can solve often complex problems; therefore, there may be no direct link between algorithm complexity and problem complexity. The following is an example of a generic single-objective genetic algorithm. Step One: Generate the initial population of individuals randomly. (First generation) Step Two: Repeat the following regenerational steps until termination: Evaluate the fitness of each individual in the population (time limit, sufficient fitness achieved, etc.) Select the fittest individuals for reproduction. (Parents) Breed new individuals through crossover and mutation operations to give birth to offspring. Replace the least-fit individuals of the population with new individuals. Similar techniques differ in genetic representation and other implementation details, and the nature of the particular applied problem.