liveBook · Manning

Hamming cliff

As explained in Optimization Algorithms: AI techniques for design, planning, and control problems

A representation discontinuity in which a small encoded change, such as flipping one bit, causes a large change in the decoded solution value or fitness.

A hamming cliff occurs when a small chromosome change causes a large decoded-value or fitness change. In binary genetic algorithms, flipping a single most-significant bit can abruptly disrupt the search space and encourage premature convergence. section 8.1

A boundary between adjacent values

Binary representations of decimal 7 and 8 are 0111 and 1000, so moving between adjacent values changes several bits. Their Gray-code representations, 0100 and 1100, differ by only one bit, creating a smoother genotype-to-phenotype transition. section 8.1

Gray coding mitigates the problem because successive values differ by one bit. Real-valued encoding provides another alternative, especially for continuous variables, by avoiding disruptive binary decoding changes. section 8.1 section 8.9

How Optimization Algorithms: AI techniques for design, planning, and control problems covers it

How deep it goes
Explains causes, most-significant-bit effects, fitness consequences, and Gray-code or real-valued mitigations.
Examples
Uses decimal-to-binary-to-Gray tables, XOR conversion, a ticket-pricing example, and Hamming-distance figures.
What it assumes
Assumes binary chromosomes, crossover, mutation, decoded values, and fitness in genetic algorithms.
What you can do after
Evaluate binary encodings and select Gray-code or real-valued alternatives to reduce disruptive search-space changes.
How it connects
Connects binary encoding with genetic algorithms, crossover, mutation, fitness landscapes, Gray code, and real-valued encoding.
Cover of Optimization Algorithms: AI techniques for design, planning, and control problems
liveBookmanning.com
Read Optimization Algorithms: AI techniques for design, planning, and control problems on liveBook Get the book at manning.com

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Optimization Algorithms: AI techniques for design, planning, and control problems. The section links point to the parts of the book it draws on.