Reactive Search: Automating the Art of Heuristics for MAX-SAT

TL;DR

Classic local search algorithms often require a "magic" parameter set by an expert to work well. This paper introduces Reactive Search (RS), an adaptive version of Tabu Search that monitors its own history to tune itself on the fly. By detecting cycles and adjusting search prohibition periods dynamically, it crushes static heuristics like GSAT on the Maximum Satisfiability (MAX-SAT) problem.

The Motivation: Moving Beyond Manual Tuning

In the mid-90s, local search algorithms like Simulated Annealing and Tabu Search were the kings of combinatorial optimization. However, they had a fatal flaw: The Prohibition Tenure ($T$).

• If $T$ is too small, the algorithm gets stuck in a loop, visiting the same states.
• If $T$ is too large, it becomes overly constrained and misses great solutions nearby.

Most researchers tuned these parameters through tedious trial and error. Battiti and Protasi asked a radical question: Why not let the algorithm observe its own "frustration" and adjust $T$ itself?

Methodology: The "Reactive" Loop

The core innovation is a feedback loop based on History Sensitivity.

1. The Reactive Tabu Mechanism

The algorithm maintains a hash table of previously visited configurations.

• Cycle Detection: If the current state has been visited before, the algorithm senses a cycle.
• Response: It immediately increases the prohibition period ($T$) to "force" the search into unvisited territory (Diversification).
• Decay: If a long period passes without cycles, $T$ is gradually decreased (Intensification).

2. Proactive Diversification (Escape Moves)

If the cycle persists despite a large $T$, the algorithm triggers an "Escape" move—a sequence of random steps to jump into a different basin of attraction in the landscape.

Figure 1: The conceptual flow of Reactive Search, showing the interaction between local search and history-based control.

Experiments: Putting RTS to the Test

The authors tested RTS on several MAX-SAT instances, including random $k$-SAT and structured problems. They compared it against GSAT (Greedy Local Search) and Simulated Annealing (SA).

Key Finding: Robustness over Scale

Unlike his counterparts, RTS didn't need to be re-tuned for different problem sizes. Whether dealing with 100 or 500 variables, the adaptive mechanism found the correct "rhythm" for the search.

Table 1: Performance comparison. Note that NOB (the authors' variant) and RTS consistently show lower error rates and faster convergence times compared to standard SA or GSAT.

Mathematical Intuition

The paper provides a rigorous analysis of the "Hamming distance" movement. By modeling the search as a stochastic process, they demonstrate that RTS ensures that the expected time to revisit a configuration grows exponentially with $T$, effectively "repelling" the search from local optima.

Critical Analysis & Future Outlook

Pros:

• Eliminates the "Human-in-the-loop" requirement for parameter tuning.
• The use of hashing for history tracking was highly efficient for the hardware of that era.

Cons/Limitations:

• Storing history in a hash table can become memory-intensive for extremely high-dimensional spaces (though the authors argue that only recent history is needed).

Why it matters today: Reactive Search was a precursor to modern Hyperparameter Optimization (HPO) and Meta-Learning. Today's AI researchers use similar "reactive" ideas when adjusting learning rates (like Adam or ReduceLROnPlateau) or in neuroevolutionary algorithms.

Conclusion

Reactive Search proved that an algorithm that "remembers" its past is significantly more powerful than one that simply wanders. By treating the search parameter as a dynamic variable to be optimized internally, it paved the way for more autonomous AI solvers.

Senior Academic Editor Note: This paper remains a classic case study in why "learning to learn" is more efficient than "hardcoding to solve."