Adaptive Simulated Annealing

Restart Schedules for Adaptive Simulated Annealing: In Variable Annealing Length and Parallelism in Simulated Annealing, I introduced a restart-based and parallel extension of Modified Lam simulated annealing that eliminates the need to know the annealing length in advance, enabling a fully parameter-free SA with strong anytime performance. I introduced two versions of the restart schedule. Variable Annealing Length (VAL) is for sequential SA, and consists of an exponentially increasing restart schedule. I then generalize it to Parallel VAL (P-VAL), where multiple independent Modified Lam annealers run in parallel, each following a coordinated pattern of increasing run lengths. This design mitigates the risk of misestimating available computation time: short early runs provide rapid improvements, while longer later runs exploit extended time when available. Experiments on a difficult NP-hard scheduling problem with sequence-dependent setup times show that VAL and P-VAL significantly outperform fixed-length restart strategies during most of the run, with P-VAL dominating parallel baselines early and maintaining strong anytime behavior throughout. The result is a practical, parallelizable simulated annealing framework that preserves the adaptive strengths of Modified Lam while removing its last remaining parameter.

Self-Tuning Lam Annealing: My article Self-Tuning Lam Annealing: Learning Hyperparameters While Problem Solving introduces Self-Tuning Lam Annealing, a novel adaptive simulated annealing schedule that automatically learns its own hyperparameters during the early phase of a run, enabling rapid convergence to Lam and Delosme's idealized acceptance-rate trajectory regardless of cost-function scale or run length. Building on the Modified Lam -- which, despite being described as parameter-free, relies on fixed constants that can slow convergence or behave inconsistently across problem domains -- the Self-Tuning Lam uses early search feedback to tune the exponential-moving-average acceptance-rate estimator, initial temperature, and temperature-adjustment rate. Experiments across discrete, continuous, and NP-hard optimization problems show that the method consistently achieves its target behavior almost immediately, improving robustness and reducing sensitivity to problem characteristics. The implementation is released as part of the Chips-n-Salsa open-source library, along with full experimental data and analysis code to support reproducibility.

Optimized Modified Lam Annealing: In Optimizing the Modified Lam Annealing Schedule, I present a streamlined, performance-optimized variant of the Modified Lam annealing schedule, reducing its computational overhead while preserving its adaptive behavior. By relocating the schedule's expensive exponentiation operations outside the main simulated-annealing loop and replacing them with lightweight multiplications, the optimized version eliminates roughly 0.5N exponentiations per run, yielding substantial runtime improvements that are typically 15-35% faster depending on run length and restart strategy. Experiments across multiple run lengths and restart configurations confirm statistically significant speedups, especially for long runs or multistart SA, where cached exponentiation results amplify the gains. I integrated both the original and optimized schedules into the Chips-n-Salsa library and provide full open-source experimental code and data, demonstrating that careful engineering of annealing-schedule internals can meaningfully accelerate simulated annealing without altering its search dynamics.

Multi-Heuristic Search

In my PhD dissertation, Boosting Stochastic Problem Solvers Through Online Self-Analysis of Performance, I developed a framework called Quality Distribution Based Search Control (QD-BEACON) that uses online-generated statistical models of search performance to effectively combine multiple search heuristics. This research lead to a pair of papers published after my dissertation that focus on two of the primary outcomes of my dissertation research. First, heuristic-guided stochastic search algorithms (such as value-biased stochastic sampling), when given a strong heuristic, sample from the extreme of the distribution of solution qualities for the problem. This enables utilizing extreme value theory to model the performance of the stochastic search algorithm. Second, an analysis of a new form of multiarmed bandit that I named the Max K-Armed Bandit lead to a strategy for allocating trials among a set of heuristics. The allocation strategy utilizes the online-learned extreme value models of the heuristics. The papers presenting these two results are discussed further below.

Max K-Armed Bandit: My paper The Max K-Armed Bandit: A New Model of Exploration Applied to Search Heuristic Selection was awarded the 2005 AAAI Outstanding Paper Award. In this paper, we introduced the Max K-Armed Bandit, a new variation of the multiarmed bandit designed for settings such as multistart stochastic search, where the objective is to maximize the best single reward obtained rather than the cumulative reward. Building on extreme value theory and assuming that heuristic-biased stochastic search samples from the extremes, we derived that the optimal exploration strategy allocates trials to the currently observed best heuristic at a rate that grows double exponentially relative to the others, a result formalized in both the two-armed and K-armed cases. This motivates a Boltzmann exploration policy with an exponentially decaying temperature. Experiments on two NP-hard scheduling domains, weighted tardiness sequencing and resource constrained project scheduling with time windows (RCPSP/max), show that this double-exponential allocation strategy consistently outperforms both slower and faster allocation rates, validating the theoretical model and demonstrating its practical value for heuristic selection in stochastic search.

Modeling Search Performance with Extreme Value Theory: The AAAI 2005 paper that introduced the Max K-Armed Bandit relied on our earlier result on modeling stochastic search performance with extreme value theory, presented at CP-2004 in the paper Heuristic Selection for Stochastic Search Optimization: Modeling Solution Quality by Extreme Value Theory. In that paper, I developed a framework for integrating multiple search heuristics within a stochastic sampling algorithm by modeling each heuristic's solution-quality distribution using extreme value theory (EVT). Motivated by the observation that strong heuristics generate "good" solutions that are statistically rare (e.g., the average solution given by a stochastic sampler guided by a strong domain heuristic was found to be over 9 standard deviations better than the average random solution), we treat each iteration's solution as a sample from the tail of the global solution-quality distribution and fit a Generalized Extreme Value (GEV) model to estimate each heuristic's probability of producing an improvement. We also developed a complementary kernel density estimator tuned for GEV-like distributions. These online-learned models drive a Boltzmann exploration strategy that adaptively selects heuristics across restarts. Validated on the NP-hard RCPSP/max scheduling problem, the EVT-motivated approach proves competitive with, and sometimes superior to, the best known heuristic algorithms, demonstrating that modeling solution quality via EVT enables effective, instance-specific hybridization of multiple heuristics.

Automated Parameter Control

At the Thirty-First International Florida Artificial Intelligence Research Society Conference, I presented a paper, Impact of Random Number Generation on Parallel Genetic Algorithms, that explored optimizing genetic algorithm performance by optimizing how randomized behavior is implemented. This research especially focused on an adaptive genetic algorithm where control parameters evolve during the search. This paper investigates how random number generation affects the runtime and efficiency of both sequential and parallel genetic algorithms, showing that implementation-level choices can yield surprisingly large performance gains. I developed a multi‑population parallel GA (pGA) for the NP-hard weighted tardiness scheduling problem with sequence-dependent setups, adapting earlier genetic algorithms with both static and adaptive control parameters, and demonstrated that the adaptive pGA achieves linear to slightly superlinear speedup relative to its sequential counterpart. A central finding is that genetic algorithms spend so much time generating random numbers that replacing Java's default Random class with faster alternatives, such as ThreadLocalRandom or SplittableRandom, and using the ziggurat method instead of the polar method for Gaussian mutation, can improve runtime dramatically. A genetic algorithm's speed can vary by as much as 25%, and a pGA by as much as 20%, simply through choice of pseudorandom number generator (PRNG). Experiments confirm that careful PRNG selection accelerates both standalone random-number workloads and full GA/pGA runs, while preserving solution quality, underscoring that PRNG choice is a critical but often overlooked factor in evolutionary computation performance.

Earlier at the 9th International Conference on Bio-inspired Information and Communications Technologies, I presented Genetic Algorithm Parameter Control: Application to Scheduling with Sequence-Dependent Setups. In this research, I developed a genetic algorithm with adaptive control parameters for the NP-hard problem of weighted tardiness scheduling with sequence-dependent setups, eliminating the need for manual parameter tuning. Instead of fixing crossover and mutation rates ahead of time, the genetic algorithm encodes these parameters within each individual and evolves them during search using Gaussian mutation, allowing the algorithm to simultaneously optimize both the scheduling solution and its own internal behavior. Using a permutation representation with Non-Wrapping Order Crossover (NWOX) and insertion mutation, the adaptive genetic algorithm rapidly converges on effective parameter values and consistently outperforms a manually tuned genetic algorithm across benchmark instances, often achieving lower tardiness, finding more optimal solutions, and doing so with less computational time. The results show that dynamic parameter control not only improves performance but also adapts meaningfully to instance characteristics (e.g., tighter vs. looser due dates), demonstrating a practical and efficient alternative to traditional trial-and-error genetic algorithm tuning.

Automated Parameter Tuning

I presented the paper, Modeling GA Performance for Control Parameter Optimization, at GECCO-2000. In this paper, we focused on the classic issue of tuning genetic algorithm control parameters (e.g., population size, crossover rate, mutation rate, etc) by using a meta-level genetic algorithm whose fitness evaluations come from a trained neural network rather than costly runs of the actual genetic algorithm. We demonstrated this approach on a genetic algorithm that we designed for the largest common subgraph problem, first hand-tuning its parameters as a baseline, then training a neural network on 1000 randomly sampled parameter sets to predict genetic algorithm accuracy and runtime, and finally letting the meta-level genetic algorithm evolve improved parameter sets using that neural network as a cheap fitness proxy. The resulting parameter sets significantly outperform the hand-tuned baseline, and the optimized genetic algorithm is shown to be competitive with, and for larger graphs substantially faster than, an existing hill-climbing algorithm, all while requiring far fewer actual genetic algorithm evaluations than a standard meta-level genetic algorithm search would need.