JP / EN
Optimization

Genetic Algorithm

A derivative-free search that evolves a population of candidate solutions

1. What Is a Genetic Algorithm?

A genetic algorithm (GA) is an optimization method inspired by biological evolution. Rather than updating a single point, it maintains a population of candidate solutions and creates new candidates while favoring those that score well.

Because it does not require derivatives of the objective function, it can be applied to complicated functions and combinatorial choices. The representation and evaluation of each candidate must still be designed for the problem at hand.

2. One Generation at a Time

The algorithm evaluates each candidate, selects promising parents, then uses crossover to combine their information and mutation to introduce random changes. It may also preserve the best candidate directly, a practice known as elitism.

  1. Initial populationCreate candidates
  2. EvaluationScore each one
  3. SelectionChoose parents
  4. Crossover & mutationCreate offspring
  5. Next generationUpdate population

Repeat evaluation → selection → crossover and mutation → next generation until a stopping condition is met.

Figure 1: The basic GA cycle. A generation limit or a long period without improvement can serve as a stopping condition.

For minimization, candidates with smaller objective values are more promising. Selecting only the very best, however, can remove diversity from the population. Selection strength and mutation size therefore matter.

3. Watching the Candidates Move

As a one-dimensional example, minimize the following function on a bounded interval. Its quadratic term and periodic ripples give it a nontrivial shape. The global minimum is f(x) = 0 at x = 1.

f(x) = (x − 1)2 + 0.7 sin2(4(x − 1)),   −0.7 ≤ x ≤ 2.7

The figure shows one fixed-seed run with 18 real-valued candidates. Each generation uses tournament selection among three candidates, arithmetic crossover, Gaussian mutation, and preservation of one best candidate.

Objective-function curve and positions of 18 candidates at generations 0, 5, and 15. They gather near the minimum at x equals 1.
Figure 2: Candidate positions for the same objective function. They start spread out and concentrate near x = 1 by generations 5 and 15. Small vertical offsets make overlapping points visible; mutation can still produce outliers.

Improvement is visible in this run, but the outcome is not identical every time. Different initial populations and random draws change the search path.

4. Strengths and Limitations

  • Flexibility: GA searches without derivatives and can explore several regions at once. Candidates can represent real numbers, orders, or combinations.
  • Cost: Every candidate is evaluated in every generation, which can be expensive when the objective function is slow.
  • Diversity: If candidates become too similar, the population may converge prematurely to a locally good solution. Mutation and selection pressure help control this.
  • No guarantee: An improving best score does not prove that the global optimum has been found. Multiple runs and comparison with other methods are useful.

To assess a GA run, look at both the best objective value and the spread of candidates over time. That shows whether the search is still exploring or merely gathering around one point.