THE FOLD / CHEAT / THE EXPLOIT / THE DECEPTIVE
THE DECEPTIVE
a hill built to mislead
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
A deceptive landscape is one built so that following the gradient takes you away from the answer. The trap function is the cleanest example: reward is (L−1) minus the number of ones, so every improving step removes a one and the climb ends at all-zeros — except that all-ones, the single point the whole landscape steers away from, pays more than anything else. The decoy is not a poor consolation prize either. It pays 90% of the optimum, which is exactly what makes it convincing.
LIT verified live on all 1024 ten-bit starting points: steepest-ascent hill climbing reaches the global optimum from exactly 11 of them — C(10,9) + 1, the optimum plus its ten immediate neighbours — and the other 1013 (98.9%) all land on the decoy, which scores 9 against the optimum’s 10. A one-max control on the same climber reaches the optimum from all 1024.
LIT verified live on all 1024 ten-bit starting points: steepest-ascent hill climbing reaches the global optimum from exactly 11 of them — C(10,9) + 1, the optimum plus its ten immediate neighbours — and the other 1013 (98.9%) all land on the decoy, which scores 9 against the optimum’s 10. A one-max control on the same climber reaches the optimum from all 1024.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at THE EXPLOIT — the landscape is the attacker here, and the search algorithm is the vulnerability.
AVAN (AI) wrote “every gradient points the wrong way” and the exhaustive sweep disproved it. A string with nine ones scores 0 under the trap while all-ones scores 10, so from one flip away the optimum is not merely visible, it is overwhelmingly the best move. The basin is therefore not a single point but exactly 11 — the optimum and its ten neighbours — and the honest claim is narrower and more interesting than the one first written: the landscape is deceptive everywhere except in immediate contact with the answer. That distinction matters, because it is the difference between a problem no local search can solve and one that any local search solves the instant it stumbles within one step, which is a 1.07% chance per random restart. Goldberg introduced deceptive functions to genetic-algorithm theory in 1987.
AVAN (AI) wrote “every gradient points the wrong way” and the exhaustive sweep disproved it. A string with nine ones scores 0 under the trap while all-ones scores 10, so from one flip away the optimum is not merely visible, it is overwhelmingly the best move. The basin is therefore not a single point but exactly 11 — the optimum and its ten neighbours — and the honest claim is narrower and more interesting than the one first written: the landscape is deceptive everywhere except in immediate contact with the answer. That distinction matters, because it is the difference between a problem no local search can solve and one that any local search solves the instant it stumbles within one step, which is a 1.07% chance per random restart. Goldberg introduced deceptive functions to genetic-algorithm theory in 1987.
3 ONE DIMENSION
The whole landscape. The prize is the spike on the far right, and everything leans left.
4 TWO DIMENSIONS · INTERACTIVE
Drop a climber anywhere and watch it walk confidently away.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the hypercube of states, coloured by where the climb ends.
AVAN’s addition (the inverse-companion): the forward reading is “some landscapes defeat hill climbing.” The inverse is that the landscape is not hostile, it is honest — and the climber is the thing making an assumption. Every local reading the trap gives is correct: at that point, in that direction, reward really does increase. What fails is the inference from local slope to global direction, and no amount of measuring will repair it, because the measurements were never wrong. Read backwards, deception is not a property of a function but a mismatch between a function and a searcher’s prior — which is the no-free-lunch theorem again, arriving from the other side and wearing a disguise.
LIT on all 1024 ten-bit starting points, steepest-ascent hill climbing reaches the global optimum from exactly 11 of them - C(10,9) + 1, the optimum plus its ten immediate neighbours - and the other 1013 (98.9%) all land on the decoy, which scores 9 against the optimum's 10; a one-max control on the same climber reaches the optimum from all 1024
FIG 'Every gradient points the wrong way' was written, and the exhaustive sweep DISPROVED it. A string with nine ones scores 0 under the trap while all-ones scores 10, so from one flip away the optimum is overwhelmingly the best move. The basin is therefore not a single point but exactly 11, and the honest claim is narrower and more interesting: the landscape is deceptive everywhere EXCEPT in immediate contact with the answer. That is the difference between a problem no local search can solve and one that any local search solves the instant it stumbles within one step - a 1.07% chance per random restart. Goldberg introduced deceptive functions to GA theory in 1987.
FIG 'Every gradient points the wrong way' was written, and the exhaustive sweep DISPROVED it. A string with nine ones scores 0 under the trap while all-ones scores 10, so from one flip away the optimum is overwhelmingly the best move. The basin is therefore not a single point but exactly 11, and the honest claim is narrower and more interesting: the landscape is deceptive everywhere EXCEPT in immediate contact with the answer. That is the difference between a problem no local search can solve and one that any local search solves the instant it stumbles within one step - a 1.07% chance per random restart. Goldberg introduced deceptive functions to GA theory in 1987.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE EXPLOIT · David Lee Wise (ROOT0), with AVAN