Hybrid Optimization (Greedy + Random)

A stripped-down simulated annealing: keep a probability of accepting bad moves, decay it over time.

Intuition

The big idea

Pure greedy gets stuck. Pure random wanders forever. Mix them: most of the time accept only improvements (greedy), but with a controlled probability, also accept a worse solution (random). Slowly decrease that probability — you explore early, exploit late.

The algorithm

HYBRID(initial_solution, initial_cost, Pr_initial):
    current ← initial_solution
    best ← current
    Pr ← Pr_initial            // e.g., 0.80

    do:
        for i = 1..MaxTries:
            new ← perturb(current)
            if cost(new) is better than cost(current):
                current ← new
                if cost(new) is better than cost(best):
                    best ← new
            else:
                r ← random in [0, 1]
                if r < Pr:
                    current ← new                 // accept bad move
                    if cost(new) is better than cost(best):
                        best ← new
        Pr ← 0.9 * Pr           // decay probability
    while (Pr > 0.001)

    return best

Worked example (TSP)

Start: random tour, distance = 100 miles. best = 100.
Pr = 0.80   (80% chance to accept a bad move)

Iter 1: swap two cities → new distance 96.
        96 < 100 → accept. current = 96. best = 96.

Iter 2: swap two cities → new distance 130.
        130 > 96 → bad. draw r = 0.7.
        0.7 < 0.80 → accept anyway. current = 130. best still 96.

Iter 3: swap → 90. better → current = 90, best = 90.
…
After MaxTries iterations: Pr ← 0.9 * 0.80 = 0.72
Repeat the inner loop with the new Pr.
…
Stop when Pr < 0.001 — by then we only take improvements.
Return best.

vs. Simulated Annealing

	Hybrid (this)	Simulated Annealing
Bad-move acceptance	Constant probability Pr per outer iter	Probability depends on ΔC and T (Boltzmann)
Cooling parameter	Pr	T
Cooling rule	`Pr ← 0.9 · Pr`	`T ← α · T` (or other schedule)
Sensitive to ΔC?	No — only to whether new is worse	Yes — small worsening more likely accepted than large
Tuning effort	Lower — fewer params	Higher — 4 params

The hybrid is essentially SA without the ΔC-sensitivity in the acceptance probability. Simpler, often nearly as effective.

Exam tips

Frequently asked

"Trace one outer iteration of the Hybrid algorithm" — show the inner MaxTries-loop with current/best updates, then the Pr decay.
"What does Pr control?" — willingness to accept worse solutions; high Pr = exploration, low Pr = exploitation.
"How is this different from SA?" — Hybrid: acceptance probability doesn't depend on how much worse. SA: it does, via e^−ΔC/T.
"Why decay Pr?" — early exploration, then convergence.