Genetic Algorithms and Evolutionary Optimization

Evolution as an Optimization Algorithm

Natural evolution has solved an optimization problem of colossal complexity: creating beings capable of surviving in a changing environment. The mechanism: random mutations, gene recombination (crossover), natural selection. Genetic Algorithms (GA) imitate this process for optimization purposes. Instead of a single “particle” in the solution space—there is an entire “population” evolving over time. This enables a global search: different individuals explore different parts of the space.

Structure of a Genetic Algorithm

Chromosome (individual): the encoding of a solution as a vector. For the TSP— a permutation of cities. For the knapsack problem—a binary string.

Fitness: value of the objective function. In GA, we usually work with maximization, so: fitness = −cost for minimization problems.

Main GA cycle:

1. Initialization: generate initial population P₀ of N random solutions

2. Evaluation: compute fitness(s) for each s ∈ P

3. Selection: select “parents” proportionally to fitness

   • Roulette wheel selection: P(select s) = fitness(s) / Σ fitness. Analogue of “spinning a roulette wheel”
   • Tournament selection: randomly select k individuals, the best wins. Parameter k reflects “selection pressure”

4. Crossover (recombination): create offspring from a pair of parents

5. Mutation: randomly modify some offspring

6. Replacement: form a new population from offspring (+ some parents)

7. Repeat until stopping criterion is reached (generations or time)

Operators for TSP

Problem: chromosome = permutation of cities π = (π₁, π₂, ..., πₙ). Crossover must produce valid permutations (each city appears exactly once).

Order Crossover (OX):

1. Select a random segment [l, r] from parent P1
2. Copy π₁[l..r] into the offspring at the same positions
3. Fill the remaining positions from P2 in order of appearance (skipping already included elements)

Example: P1 = (1,2,3,4,5), P2 = (3,4,1,5,2), segment [2,4].

Offspring: ( _, 2, 3, 4, _ ). From P2 in order 3,4,1,5,2, skipping 2,3,4: take 1, 5. Offspring = (1, 2, 3, 4, 5). (In this case, no change, real examples are more complex.)

Mutation for TSP:

• Swap: randomly swap two cities
• Insertion: extract one city and insert it into another place
• Inversion (2-opt): reverse a random subroute

Mutation probability is usually low: 0.01–0.05.

Theoretical Foundations: Schema Theorem

Schema H: string from {0, 1, *}, where * is “don’t care” (any value). Example: H = (1, *, 0, *) describes all strings starting with 1 and having 0 at the 3rd position.

Order of schema o(H) = number of fixed positions (non-*). Length of defining segment l(H) = distance between the outermost fixed positions.

Schema Theorem (Holland): schema H with above-average fitness f̄(H) > f̄_pop (mean over the population) grows exponentially in the next generation:

E[m(H, t+1)] ≥ m(H,t) · f̄(H)/f̄ · (1 − p_c · l(H)/(n−1)) · (1 − p_m)^{o(H)}

where m(H,t) is the number of individuals of schema H at time t, p_c is the crossover probability, p_m is the mutation probability.

Interpretation: “good, short, reliable” schemata grow exponentially. This is the basis of the “building blocks” theory.

Memetic Algorithms (MA)

GA searches for “good” regions of the space, but does not fully “refine” locally. Solution: Memetic Algorithm = GA + Local Search:

For every offspring obtained via crossover/mutation, launch a local search (2-opt for TSP).

Result: MA for TSP is significantly better than pure GA or pure LS:

• Pure GA: searches space globally, but solutions are not fully “refined”
• Pure LS: gets stuck in local optima
• MA: global search + local “polishing”

Example: LKH (Lin-Kernighan-Helsgott) for TSP uses MA: GA for combining good tours + LK for local search. The best practical algorithm for TSP.

NSGA-II: Multi-Criteria Optimization

Often, it is necessary to optimize several conflicting criteria simultaneously (cost vs. quality, risk vs. return). There is no single optimum—there is the Pareto front: solutions where none of the criteria can be improved without worsening another.

NSGA-II (Non-dominated Sorting GA, Deb 2002): the standard for multi-criteria GA optimization.

Selection operators:

• Non-domination rank: solutions are ranked by “domination level”: rank 1 = not dominated by anyone, rank 2 = dominated only by rank 1, etc.
• Crowding distance: distance to neighbors on the front. Preference is given to “less crowded” zones—diversity.

NSGA-II Applications: aerospace engineering (structural optimization), chemical industry (reactor optimization), finance (risk-return frontier), electronics (circuit design optimization). It is the industrial standard in multi-criteria optimization.