Genetic Algorithm

Genetic Algorithm (GA) is an evolutionary algorithm based on the "survival of the fittest" principle observed in biological evolution. It was first proposed by Professor J. Holland at the University of Michigan in 1967.

The algorithm begins with a population representing potential solutions to a problem, where each individual in the population is encoded through genes. The initial step involves mapping phenotypes to genotypes through encoding operations. In code implementation, this typically requires defining a chromosome structure - often represented as binary strings or real-valued vectors - that encodes problem parameters. After generating the initial population (usually created randomly within specified bounds), the algorithm evolves better approximations generation by generation according to natural selection principles. In each generation, individuals are selected based on their fitness scores calculated through an objective function. Genetic operators including crossover (combining parental chromosomes) and mutation (introducing random changes) are applied to create new populations. The crossover operation can be implemented using techniques like single-point crossover where segments of parent chromosomes are exchanged, while mutation randomly alters certain genes with a low probability. This evolutionary process causes subsequent generations to become better adapted to the problem environment, similar to natural evolution. The optimal individual in the final population, after decoding (converting chromosomes back to solution parameters), can be considered as an approximate optimal solution. However, genetic algorithms have limitations: when dealing with large search spaces, they may require substantial computation time to converge. Additionally, algorithm performance heavily depends on parameter selection - different settings for population size, mutation rate, and crossover probability can yield significantly different results. Therefore, careful parameter tuning through techniques like grid search or adaptive methods is essential when applying genetic algorithms to problem-solving.