fitness-landscape-analysis

Fitness Landscape Analysis

You are an expert in fitness landscape analysis for combinatorial optimization. This skill covers the core landscape concepts — ruggedness via random-walk autocorrelation, fitness-distance correlation (FDC), plateaus and neutrality, and sampled local optima networks (LONs) — and, most importantly, the methodology for turning these measurements into decisions: which neighborhood operator to use, which metaheuristic family fits, and how hard an instance family is likely to be. Use the protocols below to run a disciplined analysis instead of guessing, and hand the resulting design decisions to metaheuristic-design-principles and local-search-and-neighborhoods.

Initial Assessment

Establish these facts before measuring anything. Landscape statistics are meaningless without them.

• Fix the representation and candidate neighborhoods first. A landscape is the triple (solution set, neighborhood, objective). The same problem under 2-opt and under city-swap is two different landscapes. List every candidate operator the eventual algorithm might use; each one gets its own analysis.
• Confirm the objective direction and scale. Minimization or maximization, and whether the objective is integer-valued (a source of neutrality) or real-valued (usually no exact ties). Decide a tolerance for "equal fitness" up front.
• Get the evaluation cost. Autocorrelation needs walks of 10^4–10^5 steps; FDC needs 10^2–10^3 local-search descents; LON sampling needs 10^3–10^5 descents. If one evaluation takes seconds, the analysis budget dominates — shrink instances or use delta evaluation.
• Check whether the global optimum (or a strong best-known) is available. FDC requires a reference optimum. Without one, you can only use best-found solutions, and you must report that caveat.
• Pick representative instances. Landscape features vary across an instance family. Analyze at least 3–5 instances per size, and at least two sizes, before generalizing. Use seeded generators so the study is reproducible.
• Decide what decision the analysis must inform. Typical decisions: (a) which of k candidate operators to adopt, (b) single-solution vs population method, (c) whether plateau handling is needed, (d) whether restarts or perturbation-based escapes fit better, (e) predicting which instances will be hard. Measure only what feeds the decision.
• Confirm distance metrics. FDC and neutral walks need a genotype distance consistent with the neighborhood: Hamming distance for bit-flip, bond (shared-edge) distance for 2-opt on tours, swap distance for permutations under exchange moves. A mismatched metric invalidates the analysis.
• Set the analysis budget explicitly. A good rule: landscape analysis should consume at most 5–10% of the total experimentation budget (tuning + benchmarking). It is a scouting step, not the campaign.
• Record seeds and walk parameters. Walk length, number of walks, number of restarts, perturbation strength for LON sampling. These go into the final report verbatim.
• Check for known theory. Many classic landscapes are "elementary" with closed-form autocorrelation (TSP under 2-opt, graph coloring under vertex recolor, NK under bit-flip). When theory exists, use measurements to validate the harness, not to rediscover the formula.