Genetic Algorithm

The genetic algorithm, introduced by Holland (1975) and popularised by Goldberg (1989), is a population-based metaheuristic. The algorithm maintains many candidate solutions (individuals) simultaneously; each individual is encoded as a chromosome (binary, integer, permutation, or real-valued). Each iteration applies three core operators: selection (roulette wheel, tournament, or rank-based), crossover (one-point, multi-point, uniform, or PMX/OX for permutations), and mutation (bit-flip, swap, inversion). The fitness function derives from the objective and drives selection pressure. Elitism preserves the best individuals; diversity-preservation mechanisms such as niching and crowding prevent premature convergence. Convergence theory rests on the schema theorem (Holland 1975), although the No Free Lunch theorem (Wolpert and Macready 1997) shows no metaheuristic dominates on all problems. The multi-objective extension NSGA-II (Deb Pratap Agarwal Meyarivan 2002) is the industry standard for approximating Pareto fronts. Permutation problems (TSP, scheduling) require specialised operators. Genetic algorithms do not guarantee a global optimum; they deliver good solutions in reasonable time and are preferred for mixed-integer, combinatorial, and black-box problems. References: Goldberg (1989), Eiben and Smith (2015).