Michael Brenndoerfer | Data & AI, Private Equity, Technology

Michael Brenndoerfer

Local Search and Simulated Annealing › Visualizing Local Search

Michael BrenndoerferOctober 29, 20264 min read

Machine Learning from ScratchAll chapters

Part 15 of 15Heuristic and Evolutionary Optimization

Chapter 90Local Search and Simulated Annealing › Visualizing Local Search

Reading section 5 of 10 · Visualizing Local Search · 4 minSection 5 of 10 · 4 min

Section 5 of 10 · 4 min read

Local Search and Simulated Annealing › Visualizing Local SearchSection view · Sections in this chapter5 / 10 ↓

Sections in this chapter10

Reading tools Definitions, links & notes

Choose your expertise level to adjust how many terms are explained. Beginners see more tooltips, experts see fewer to maintain reading flow. Hover over underlined terms for instant definitions.

Article links

Make inline references clickable

Notes & comments

Notes & commentsLeave notes and join the discussionSelection toolbarShow comment actions when selecting text. Turn off for the browser menu only.Comment indicatorsShow small counts beside annotated passagesPassage highlightsGently shade annotated text selections

We can see the mechanism directly on this instance. Before plotting, compute the nearest-neighbor tour and its best single-reversal neighbor, so the figure cells only render precomputed results.

PythonIn [13]
CollapseExpandnn_perm = nearest_neighbor()

best_nb, best_nb_score = None, np.inf
for i in range(8):
    for j in range(i + 1, 8):
        p = list(nn_perm)
        p[i : j + 1] = p[i : j + 1][::-1]
        p = tuple(p)
        s = objective(p)
        if s < best_nb_score - 1e-15:
            best_nb, best_nb_score = p, s

base = objective(nn_perm)
deltas = []
for i in range(8):
    for j in range(i + 1, 8):
        p = list(nn_perm)
        p[i : j + 1] = p[i : j + 1][::-1]
        p = tuple(p)
        deltas.append(objective(p) - base)
deltas.sort()

The next two plots show the nearest-neighbor routes and the routes after the best single reversal, on matching axes.

PythonIn [14]
CollapseExpanddef draw_routes(ax, perm):
    from book_plot_style import PALETTE, polish_axes

    for index, route in enumerate((perm[:4], perm[4:])):
        pts = [0] + list(route) + [0]
        ax.plot(
            COORDS[pts, 0],
            COORDS[pts, 1],
            color=PALETTE[("primary", "teal")[index]],
            lw=1.1,
            marker="o",
            markersize=4,
            label=f"Route {index + 1}",
        )
    ax.scatter(
        *COORDS[0],
        s=65,
        marker="s",
        color=PALETTE["amber"],
        zorder=4,
        label="Depot",
    )
    for customer in range(1, 9):
        ax.annotate(
            str(customer),
            COORDS[customer],
            xytext=(5, 5),
            textcoords="offset points",
        )
    ax.set_aspect("equal")
    ax.set_xlim(-0.5, 8.8)
    ax.set_ylim(-0.5, 6.8)
    ax.set_xlabel("x (distance units)")
    ax.set_ylabel("y (distance units)")
    ax.legend(
        loc="upper center", bbox_to_anchor=(0.5, -0.21), ncol=3, frameon=False
    )
    polish_axes(ax)

VisualizationOut [15]
CollapseExpand

Two closed depot routes, colored blue and teal. Route one visits 1, 7, 8, 3; route two visits 6, 5, 4, 2. — Nearest-neighbor permutation decoded into two four-customer depot routes. Colors distinguish the vehicles; customer labels preserve the contract's coordinate identifiers. The total distance is 40.8563.

VisualizationOut [16]
CollapseExpand

Route one visits 1, 3, 8, 7 before returning to the depot. Route two still visits 6, 5, 4, 2. — The best single reversal changes route one to 1, 3, 8, 7 while route two is unchanged. Total distance falls by 2.4637 to 38.3926; the shorter depot return compensates for a longer entering edge.

For the nearest-neighbor tour there are $\binom{8}{2} = 28$ distinct reversals. We score all of them and plot the change in objective $\Delta = f(\pi') - f(\pi)$ sorted from most improving to most worsening. Any bar below the zero line is a downhill move that hill climbing could accept immediately. The bars above the line are moves that hill climbing must reject but annealing may accept with some probability. This neighborhood contains one improving move and three changes that are zero within the comparison tolerance. After moving, hill climbing must scan the new neighborhood before declaring a local minimum; the budgeted implementation then restarts rather than ending the experiment.

VisualizationOut [17]
CollapseExpand

Sorted reversal changes: one negative bar, three at zero within the stated tolerance, and 24 positive bars. — Objective changes for all 28 reversals of the nearest-neighbor permutation. One improves the score, three have zero change within 1e-12, and 24 worsen it. These diagnostics are outside the search budgets.

These figures together summarize why each method behaves as it does. Within each epoch, hill climbing accepts only a scan-selected move that lowers the current score by more than $\epsilon$ . It can stop with tiny negative bars still present, and the evaluation budget can end before a complete scan establishes even that stopping condition. Annealing occasionally climbs a small positive bar early on, which can drop it into a different basin with a lower floor. Neither strategy guarantees success. Both depend on how many evaluations they get and how good their starting point is.

Comments

Add to the conversation

A question, a correction, or an example from your own work.

No comments yet. Be the first to share your thoughts!

Comments

Add to the conversation

Stay up to date