How Genetic Algorithms Solve Complex Problems: A Deep Dive into Intelligent Optimization

Intelligent Optimization Algorithms

Intelligent optimization algorithms, also known as modern heuristic algorithms, are globally optimizing, highly versatile methods suitable for parallel processing. They are grounded in rigorous theory and can theoretically find optimal or near‑optimal solutions within a bounded time.

Common Intelligent Optimization Algorithms

Genetic Algorithm (GA)

Simulated Annealing (SA)

Tabu Search (TS)

Characteristics of Intelligent Optimization Algorithms

All share the trait of starting from any solution set and, according to a defined mechanism, exploring the entire search space with a certain probability, thereby achieving global optimization performance.

Genetic Algorithm

Origin

The genetic algorithm was first introduced in 1975 by Prof. J. Holland of the University of Michigan in his book "Adaptation in Natural and Artificial Systems," drawing inspiration from natural selection and genetic mechanisms.

Search Mechanism

It simulates reproduction, crossover, and mutation processes. Each iteration retains a population of candidate solutions, selects superior individuals based on a fitness measure, and applies genetic operators (selection, crossover, mutation) to generate a new generation, repeating until a convergence criterion is met.

Basic Genetic Algorithm (SGA)

Also called Simple Genetic Algorithm, it was summarized by Goldberg as the most fundamental form, with simple evolutionary operations that serve as the foundation for many variants.

Components of SGA

Encoding (initial population generation)

Fitness function

Genetic operators (selection, crossover, mutation)

Execution parameters

Fitness and Fitness Function

The quality of an individual solution is evaluated by its fitness value; higher fitness indicates a better solution. The fitness function maps each candidate to a real‑valued measure, driving natural selection in the algorithm.

Population

A population is a randomly generated set of individuals (chromosomes). Its size is the population size, representing a small subset of the entire search space.

Genetic Operators

Three operators act on chromosomes: selection‑reproduction, crossover, and mutation.

Selection‑Reproduction Operator and Selection Probability

Selection‑reproduction mimics natural selection by copying chromosomes with higher fitness more often. The probability of selecting a chromosome is proportional to its fitness relative to the total fitness of the population, implementing a roulette‑wheel (proportional) selection scheme.

Roulette‑wheel selection can be visualized by dividing a unit circle into sectors proportional to each chromosome’s selection probability; a random spin determines which chromosome is chosen.

Implementation steps:

Generate a uniform random number in [0,1].

If the number falls within a chromosome’s cumulative probability interval, select that chromosome.

Crossover Operator

Crossover exchanges genetic material between two paired chromosomes according to a crossover probability, creating new offspring. SGA typically uses single‑point crossover.

Example: swapping the last four bits of a chromosome produces two new chromosomes.

Mutation Operator

Mutation alters one or more bits of a chromosome based on a mutation probability, introducing new genetic material and maintaining population diversity. In SGA, basic bit‑flip mutation is used.

For binary‑encoded chromosomes, a 0 may become 1 and vice versa.

Execution Parameters

Population size (M)

Number of generations (termination condition, e.g., 100‑500)

Crossover probability (0.4‑0.9)

Mutation probability (0.001‑0.01)

Basic Genetic Algorithm Procedure

Define a fitness function over the search space and set population size, crossover rate, mutation rate, and number of generations.

Randomly generate an initial population and initialize the generation counter.

Evaluate the fitness of each chromosome.

If termination criteria are met, output the best chromosome and stop.

Perform selection based on selection probabilities to create a mating pool.

Apply crossover to selected pairs according to the crossover rate, producing offspring.

Apply mutation to offspring according to the mutation rate.

Replace the current population with the new offspring and repeat from step 3.

When applying genetic algorithms to real problems, one must also define a representation scheme for solutions, a suitable fitness calculation method, and appropriate termination conditions.

Characteristics of Genetic Algorithms

Search operates on a population of solutions in parallel rather than a single point.

Uses probabilistic transformation rules instead of deterministic ones.

Fitness functions are not constrained by continuity or differentiability, making the approach widely applicable.

Employs encoded parameter sets rather than direct manipulation of problem parameters.