Premature Convergence and Deception for GA

Premature Convergence

In genetic algorithms, premature convergence is defined as the population losing diversity too early such that the search collapses into a suboptimal region.

Symptoms:

• Many identical or near-identical individuals
• No fitness improvement despite crossover and mutation

Common causes:

• Excessive selection pressure
• Small population size
• Strong elitism

Deception

A problem is deceptive when partial patterns look beneficial, but assembling them steers search away from the global optimum.

Selection amplifies locally attractive structure, but reducing diversity makes it harder to escape the trap.

For example, consider this 3-bit deceptive trap:

• Let $u$ = number of ones in a 3-bit block.
• Define:

$$f(u)=\{\begin{array}{llc}4,& u=0& \text{(000 is global)}\\ u,& u\in \{1,2,3\}& \text{(more 1s looks better)}\end{array}$$

Then, consider the fitness by the number of $1$s:

Selection favors increasing $u$, but the global optimum is at $u=0$.