Kick Method (Iterated Local Search)

Run greedy local search to a local optimum, "kick" the solution to nearby state, run local search again, keep the best.

Intuition

This is the simplest member of a family called Iterated Local Search (ILS).

The algorithm

KICK_METHOD(initial S1):
    S1 ← improve(S1)              // greedy descent to local optimum (LM1)
    S_best ← S1
    repeat:
        S2 ← kick(S1)              // random K-step perturbation
        S2 ← improve(S2)           // descend again to LM2
        if cost(S2) < cost(S_best):
            S_best ← S2
        S1 ← S2
    until stop
    return S_best

Two building blocks:

• improve — your usual local search (e.g., for TSP, do random pair swaps and accept improvements until no improvement found).
• kick — a stronger random move than a single swap. Usually: pick a random K, perform K random swaps in a row (without checking if it improves).

Worked example (TSP, from your notes)

Initial tour T1:    [7, 3, 9, 4, 8, 6, 1, 5, 0, 2]    distance = D1

Improve(T1) → T2 (local minimum, distance smaller than T1)

Kick(T2):
    pick K = 4 (random)
    perform 4 random swaps on T2 → tour T3

Improve(T3) → T4

Compare cost(T2) and cost(T4); keep the better one as the new T2.
Repeat from "Kick".

Tuning the kick strength

• K too small (e.g., 1 swap) → after the next descent, you fall back into the same valley. No escape.
• K too large → you end up in essentially a random starting point. You lose all the work from before. Like restarting from scratch.
• Sweet spot — K is large enough to escape the current basin but small enough that you stay in a related region (a "promising" zone of the search space).

For TSP, K = 3 to 6 random 2-opt moves often works well.

Exam tips