Representation, Fitness, and Selection
The Three Design Pillars
Representation
A representation is the format used to encode a candidate solution. Common representations include binary strings, real-valued vectors, permutations, trees, graphs, and neural network parameters.
Fitness Evaluation
Fitness evaluation translates a candidate into a numerical score. In simple problems, fitness may equal objective value. In harder problems, it may combine performance, penalties, and constraints.
Selection Terms
Common Representations
Binary string
- Simple and compact
- Good for discrete decisions
- May require decoding
Real vector
- Natural for continuous optimization
- Easy to mutate with Gaussian noise
- Common in ES and CMA-ES
Selection Pressure
Selection pressure controls how strongly better solutions are favored. Too little pressure can make progress slow; too much pressure can reduce diversity and cause premature convergence.
Tournament Selection Pseudocode
-
1
Step 1: Randomly sample k individuals from the population.
-
2
Step 2: Evaluate or compare their fitness.
-
3
Step 3: Select the best among the k sampled individuals.
-
4
Step 4: Repeat until enough parents are chosen.
Which representation is often most natural for optimizing continuous parameters?
Continuous optimization methods typically operate on real-valued vectors.
Correct answer: Real-valued vector
What is elitism in one short phrase?
Elitism preserves the current best candidates.
Correct answer: Keeping the best solutions unchanged.
What is a risk of overly strong selection pressure?
Strong pressure can cause premature convergence.
Correct answer: Loss of diversity
Selection Formula Idea
For roulette selection, a candidate with fitness may be selected with probability when all fitness values are nonnegative.