Skip to content
Tutorials Center
My learning

Topics

Lesson 9 of 36 ยท Representation and Fitness

Population Initialization and Diversity

Learn how to create the first generation of a genetic algorithm, measure population diversity with Hamming and Euclidean distance, and detect premature convergence.

A genetic algorithm can only recombine what already exists in its population. If the first generation is poor, or if the population quickly becomes full of near-identical individuals, the search stalls no matter how clever the operators are. This lesson covers how to create a good starting population, how to measure diversity, and what to do when diversity disappears.

Initialization strategies

Uniform random initialization is the default: fill each gene with a random allele (random bits, random numbers in the bounds, a shuffled permutation). It is unbiased and covers the space broadly. For most problems it is exactly what you want.

Alternatives exist when you know something about the problem:

  • Seeding with known good solutions, for example the output of a greedy heuristic, last year's schedule or a previous run. Seeding speeds convergence but can cause the population to cluster around the seed. Mix a few seeds with many random individuals.
  • Heuristic initialization: build each individual with a randomized constructive method (a nearest-neighbour tour started from a random city).
  • Latin hypercube or low-discrepancy sampling: for real-valued genes, spreads the initial points more evenly than plain random sampling.
  • Feasible-only initialization: generate individuals that already satisfy the constraints, which saves the early generations from wasting time on invalid solutions.

Seeded individuals are not free: a very strong seed can dominate selection and wipe out diversity in a few generations. Keep seeds to a small fraction of the population.

Population size

The population needs enough individuals to cover the space. Rules of thumb:

  • Bit strings: 50 to 200 individuals for chromosomes of up to a few hundred bits; more for deceptive or rugged problems.
  • Real vectors: 10 * dimensions is a common starting point.
  • Permutations: a few hundred for tours of 50 to 100 cities.

Bigger populations explore more but cost more per generation. Compare configurations at equal numbers of fitness evaluations, not equal generations.

Comparing random and stratified starts

For real-valued problems, plain random sampling leaves gaps and clumps. A simple stratified scheme divides each variable's range into N slices, takes one random point from each slice and shuffles slice order between variables (a Latin hypercube). The result has no two individuals in the same slice for any variable.

Python Random versus Latin hypercube coverage

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The Latin hypercube always covers every slice (0 empty), while plain random sampling leaves between three and four of the ten slices empty on average. For a 100-individual population in 30 dimensions the difference is smaller, so do not expect miracles, but it never hurts.

Measuring diversity

Diversity is how different the individuals are from each other. Measure it so that you know when the search is running out of material.

  • Bit strings: average Hamming distance between pairs, or gene-wise entropy.
  • Real vectors: average Euclidean distance between individuals, or the standard deviation of each gene.
  • Permutations: the fraction of distinct neighbour pairs (edges) in the population, or the number of unique tours.
  • Any representation: the number of unique individuals, and the gap between the best and average fitness.

A convenient bit-string measure is per-position agreement: if at some position 95 % of individuals hold the same bit, that gene has effectively converged.

Python Diversity collapsing over generations

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

In the run with strong selection and no mutation, the average Hamming distance falls quickly and many genes freeze at a single value. Once a gene has converged without mutation, it can never change again. Gentle selection with mutation keeps the population varied for longer.

Preventing premature convergence

When diversity vanishes before a good solution is found, the GA has converged prematurely. Techniques for keeping diversity (the first one is the cheapest):

  1. Lower the selection pressure: smaller tournaments, rank selection (Chapter 3).
  2. Raise mutation a little, or use adaptive mutation.
  3. Larger population.
  4. Reject duplicates: do not admit a child that is identical to an existing individual.
  5. Niching and fitness sharing: penalize individuals that crowd a similar region so several peaks stay alive.
  6. Island model: run several populations that occasionally exchange individuals (a few migrants every 10 to 20 generations).
  7. Restarts and immigration: when diversity falls below a threshold, replace part of the population with fresh random individuals.

Keeping the population varied

Softer selection Small tournaments
More mutation Fresh genes every step
Island model Separate groups, few migrants
Immigration Add random newcomers

Watch best-versus-average fitness to know when to act.

1 / 2

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why mix seeded individuals with random ones?

    Seeds speed things up but a very strong one is copied everywhere within a few generations, so keep them a small share of the population.
  2. 2. Which measure fits a population of bit strings?

    Hamming distance counts differing bits and shows how spread out the population is. Euclidean distance suits real vectors.
  3. 3. What does a Latin hypercube start guarantee?

    It splits each variable's range into N slices and places exactly one individual in each, so the coverage per variable is even.
  4. 4. Which choice is most likely to cause premature convergence?

    Strong selection quickly fills the population with copies of a few individuals, and without mutation lost gene values can never return.

Summary

  • Initialize uniformly at random by default; seed or construct heuristically only with care.
  • Choose population sizes by problem scale and compare setups at equal evaluation counts.
  • Latin hypercube sampling gives more even coverage for real-valued genes.
  • Measure diversity (Hamming or Euclidean distance, unique count, converged genes, best-versus-average gap).
  • Fight premature convergence with softer selection, mutation, bigger populations, niching, islands and immigration.

Next: Roulette Wheel Selection