Genetic Algorithms and Their Applications

Genetic algorithms are population-based stochastic optimization methods inspired by evolutionary selection. Their practical value does not come from reproducing biology literally, but from maintaining a set of candidate solutions, evaluating them with an objective function, and repeatedly applying selection and variation operators.

Unit 1: Optimization and Evolutionary Computation

Optimization problem

An optimization problem searches for parameter values that minimize or maximize an objective:

f(P1, P2, ..., PN)

The objective may be an analytical function, a simulation, an experiment, or a measurement process. Depending on context it may be called an objective, cost, loss, or fitness function.

Optimization problems differ along several axes: continuous versus discrete variables, static versus dynamic objectives, constrained versus unconstrained domains, deterministic versus stochastic evaluation, and low- versus high-dimensional search spaces.

Gradient-based local methods can converge rapidly when derivatives are available and the objective has suitable regularity. Population-based stochastic methods trade additional evaluations for broader exploration. Neither class provides a universal guarantee of finding the global optimum.

Evolutionary computation

The main historical families are genetic algorithms, genetic programming, evolutionary programming, and evolution strategies. Modern implementations often combine ideas from these families.

Biological concepts and their computational counterparts:

• Chromosome: The encoded form of a candidate solution.
• Gene: A single position representing a decision variable or encoded value.
• Allele: A possible value of a gene.
• Genotype: The encoded representation of the solution.
• Phenotype: The decoded solution represented in the problem domain.
• Fitness: The quality assigned to a candidate solution by the objective function.

The analogy is intentionally limited. A computational chromosome need not model diploidy, dominance, biological mutation rates, or real genetic mechanisms.

Search space and fitness landscape

A binary chromosome of length l defines 2^l possible bit strings. Mapping each candidate to its fitness creates a fitness landscape. Multimodality, plateaus, discontinuities, noise, constraints, and interactions between variables determine how difficult that landscape is to search.

Genetic algorithms are most useful when exhaustive search is infeasible and derivative information is unavailable, unreliable, discontinuous, or expensive. They are usually a poor choice for small, smooth problems already handled efficiently by deterministic numerical optimization.

Unit 2: Binary-Coded Genetic Algorithms

A conventional cycle is:

define representation and objective
generate initial population
repeat:
    evaluate fitness
    select parents
    recombine
    mutate
    form the next generation
    test termination criteria

For a parameter in [a, u] encoded with m bits, the representable resolution is:

(u - a) / (2^m - 1)

and decoding can be written as:

x = a + integer(bits) * (u - a) / (2^m - 1)

Standard binary coding may create a Hamming cliff: adjacent numerical values can require many simultaneous bit changes. Gray coding avoids this specific discontinuity because adjacent encoded integers differ by one bit.

Initialization, selection, crossover and mutation

Initialization should provide sufficient diversity without violating hard constraints. Selection creates reproductive pressure toward fitter candidates. Crossover recombines parental material, while mutation introduces local variation and helps prevent irreversible loss of alleles.

Mutation rates that are too low can allow diversity to collapse; rates that are too high can make the process resemble random search. Crossover and mutation therefore cannot be tuned independently from population size, representation, selection pressure, and replacement strategy.

Unit 3: Real-Coded Genetic Algorithms

Binary encoding is unnecessary when decision variables are naturally continuous. Real-coded chromosomes represent parameters directly:

x = [x1, x2, ..., xn]

Common recombination operators generate offspring between or around parental values. Mutation may use Gaussian, uniform, polynomial, or adaptive perturbations. Boundary handling must be defined explicitly: clipping, reflection, resampling, repair, or a constraint-aware operator can produce materially different search behavior.

Unit 4: Selection Methods and Selection Pressure

Fitness-proportionate selection assigns probability according to relative fitness, but it is sensitive to scaling and can behave poorly when fitness values are negative or tightly clustered.

Ranking selection operates on order rather than raw magnitude. Tournament selection chooses the best individual from a random subset and provides a simple way to control pressure through tournament size.

Elitism preserves one or more of the best solutions. It prevents regression of the best-known objective value, but excessive elitism can accelerate premature convergence.

Unit 5: Representation

Representation determines neighborhood structure. Binary strings, integer vectors, real vectors, permutations, trees, and problem-specific structures require different operators.

A representation is effective when small genetic changes tend to produce meaningful changes in the phenotype and when crossover can preserve useful partial structures. Variable interaction, often discussed as epistasis, must therefore be considered together with encoding and operator design.

Unit 6: Parameters, Complexity and Convergence

For population size N, generation count G, and fitness-evaluation cost C(f), the dominant runtime is often approximately:

O(G * N * C(f))

In engineering optimization C(f) may represent a finite-element simulation, physical experiment, or other expensive evaluation. In such cases, reducing the number of evaluations matters more than micro-optimizing crossover.

Useful techniques include memoization of repeated candidates, surrogate models, parallel evaluation, early rejection, and adaptive stopping.

Premature convergence occurs when diversity disappears before the population reaches a satisfactory region. Monitoring genotype diversity, phenotype diversity, fitness variance, and improvement rate gives more information than a fixed generation limit alone.

Unit 7: Constraints and Penalty Functions

Constrained problems may be handled through repair operators, feasibility-preserving representations, rejection, ranking rules, or penalty functions.

A penalty formulation can be written as:

F(x) = f(x) + λ * violation(x)

for minimization. The penalty coefficient must balance objective quality against feasibility. A fixed coefficient is simple but can be brittle; adaptive penalties or feasibility-first comparison rules are often more robust.

Unit 8: Combinatorial Problems and Permutations

For problems such as the Traveling Salesperson Problem, a chromosome is often a permutation. Ordinary one-point crossover can create duplicate cities and omit others, so permutation-specific operators are required.

Examples include partially matched crossover, order crossover, cycle crossover, swap mutation, insertion mutation, and inversion mutation. The representation should preserve the invariant that every element appears exactly once.

Unit 9: Theoretical Foundations

Schema theory studies subsets of strings sharing patterns at selected positions. Holland's schema theorem describes expected propagation of short, low-order, above-average schemata under simplified assumptions. It is historically important, but it should not be treated as a complete explanation of modern genetic-algorithm behavior.

The No Free Lunch results establish that, averaged uniformly over all possible objective functions, no optimizer is universally superior. Practical performance therefore comes from matching algorithmic bias to problem structure.

Deceptive functions, Royal Road functions, building-block hypotheses, linkage, and exact population models are useful for studying when recombination helps or fails.

Unit 10: Applications

Genetic and evolutionary methods are used in engineering design, scheduling, parameter estimation, control, feature selection, strategy search, symbolic program evolution, neural architecture or parameter evolution, and multi-objective optimization.

The correct engineering question is not whether a genetic algorithm can encode the problem, but whether it reaches solutions of sufficient quality with acceptable evaluation cost compared with deterministic optimization, local search, mixed-integer programming, Bayesian optimization, differential evolution, CMA-ES, or problem-specific heuristics.

Unit 11: Evolution as a Modeling Tool

Evolutionary algorithms can also be used as computational models. Co-evolution, sexual selection, ecological competition, learning-evolution interaction, and evolving cellular automata allow hypotheses about adaptive systems to be tested in controlled simulations.

Such simulations are models, not direct evidence that biological evolution follows the same simplified computational rules.

Unit 12: Related Evolutionary Methods

Differential Evolution

Differential Evolution constructs trial vectors from scaled differences between population members. It is especially effective for many continuous black-box optimization problems and requires no binary encoding.

CMA-ES

Covariance Matrix Adaptation Evolution Strategy adapts a multivariate search distribution. The covariance matrix learns correlations between variables, allowing the search distribution to rotate and stretch according to the local landscape.

Multi-objective optimization

When objectives conflict, a single optimum may not exist. The relevant solution set is the Pareto front: solutions for which no objective can be improved without worsening at least one other objective.

Core Concepts and Quick Reference

A genetic algorithm should be treated as an optimization framework with explicit design decisions:

problem definition
→ representation
→ objective and constraints
→ initialization
→ selection pressure
→ variation operators
→ replacement
→ diversity control
→ termination
→ comparison with strong baselines

Reproducible experiments require recording the random seed, implementation version, parameter configuration, stopping rule, and evaluation budget.

References

• Çunkaş, Mehmet. Genetik Algoritmalar ve Uygulamaları Ders Notları. Selçuk University, Faculty of Technical Education, Department of Electronics and Computer Education, Spring 2006.
• Holland, John H. Adaptation in Natural and Artificial Systems. University of Michigan Press, 1975.
• Goldberg, David E. Genetic Algorithms in Search, Optimization, and Machine Learning. Addison-Wesley, 1989.
• Mitchell, Melanie. An Introduction to Genetic Algorithms. MIT Press, 1996.
• Eiben, A. E.; Smith, J. E. Introduction to Evolutionary Computing. Springer.
• Storn, R.; Price, K. “Differential Evolution – A Simple and Efficient Heuristic for Global Optimization over Continuous Spaces.” Journal of Global Optimization, 1997.