Cauchy annealing schedule: an annealing schedule for Boltzmann selection scheme in evolutionary algorithms

Ambedkar Dukkipati, M. Narasimha Murty, Shalabh Bhatnagar

Introduction

In the field of Evolutionary Algorithms (EAs), the selection mechanism is the primary driver of optimization, determining which individuals contribute to the next generation. While various selection schemes exist, Boltzmann selection is theoretically prized for its ability to balance exploration (searching new areas) and exploitation (refining known solutions) using an "inverse temperature" parameter, $\gamma$.

Despite its elegance, Boltzmann selection has historically been difficult to implement because it requires a carefully tuned "annealing schedule"—a plan for how $\gamma$ should increase over time. If selection pressure increases too quickly, the algorithm suffers from premature convergence; if it increases too slowly, the search stagnates. This paper addresses this challenge by introducing the Cauchy Annealing Schedule, a mathematically rigorous framework that transforms Boltzmann selection into a practical and powerful optimization tool.

The Challenge of Selection Pressure

Selection in EAs typically falls into two categories:

  1. Proportionate Selection: Individuals are chosen based on their relative fitness. While simple, it often leads to stagnation or premature convergence in complex landscapes.
  2. Boltzmann Selection: This method uses the parameter $\gamma$ to control selection intensity. A low $\gamma$ allows weaker individuals to survive, maintaining genetic diversity, while a high $\gamma$ enforces strict selection of the fittest.

The fundamental problem is that $\gamma$ cannot remain static. Much like the cooling process in physical annealing, the selection pressure must evolve. However, finding the right schedule for $\gamma$ has traditionally relied on trial and error rather than mathematical principles.

The Cauchy Annealing Framework

The authors propose a shift in perspective: instead of focusing on individual selection probabilities, they treat the population's fitness as a Normalized Fitness Distribution (NFD). By viewing selection as an operator that transforms one distribution into another, they can apply tools from real analysis and metric space theory.

1. Measuring Selection Strength

The authors introduce a metric ($d$) to measure the "distance" between the population distribution before and after selection. This distance represents the actual strength of the selection pressure applied at any given step.

2. The Cauchy Criterion

The core innovation of this paper is the application of the "Cauchy sequence" concept. The authors hypothesize that for an evolutionary process to converge reliably to a global optimum, the change in selection pressure must decrease as the generations progress. This ensures that the population is not "shocked" by sudden jumps in selection intensity, which often cause the loss of the genetic diversity required to escape local optima.

3. The Derived Schedule

Based on this criterion, the authors derive a specific annealing schedule: $$\gamma_n = \sum_{k=1}^n g_k, \text{ where } g_k = \frac{g_0}{k^\alpha}$$ In this formula, $\alpha > 1$ ensures that the sequence of selection pressures is a Cauchy sequence. This allows the total selection pressure ($\gamma$) to grow, but ensures the rate of growth slows down over time, providing a "smooth" transition from exploration to exploitation.

Experimental Validation

The Cauchy Annealing Schedule was evaluated using four classic, high-dimensional benchmark functions designed to challenge optimization algorithms:

  • Rastrigin’s Function: Contains a high density of local optima.
  • Griewangk’s Function: Features a complex "web" of optima created by a product component.
  • Ackley’s Function: Known for a flat outer region and a very steep central peak.
  • Schwefel’s Function: A deceptive landscape where the second-best optimum is geographically far from the global optimum.

The experiments utilized a search space of $2^{75}$ and a population size of 150, comparing the Cauchy-Boltzmann approach against standard proportionate selection and fixed-temperature Boltzmann selection.

Key Insights and Results

  • Superior Convergence: Across all benchmark functions, the Cauchy Annealing Schedule reached significantly better (lower) fitness values than competing methods.
  • Robustness to Complexity: As the problem dimensionality ($l$) increased, the performance gap between the Cauchy schedule and standard methods widened. While fixed-temperature selection often stalled, the Cauchy schedule continued to find improvements.
  • The Importance of "Smoothness": The results suggest that successful convergence is not just about increasing selection pressure, but about the rate of that increase. The parameter $\alpha$ (found to be most effective between 1.1 and 1.5) acts as a "speed limit" that prevents the premature loss of diversity.
  • Stability: The Cauchy schedule demonstrated less sensitivity to initial random conditions, providing more predictable and reliable results across multiple runs.

Conclusion and Future Directions

The Cauchy Annealing Schedule provides a theoretical bridge between real analysis and evolutionary computation. By treating selection as a distribution shift and applying the Cauchy criterion, the authors have turned a previously "black box" parameter into a mathematically grounded tool.

Future work remains in exploring how this schedule interacts with other genetic operators, such as mutation and crossover rates. Additionally, the authors suggest that proving the mathematical "completeness" of the NFD metric space could eventually lead to a definitive proof of convergence for this class of evolutionary algorithms.

Summary updated

BibTeX
@inproceedings{dukkipati2004cauchy,
  author = {Ambedkar Dukkipati and M. Narasimha Murty and Shalabh Bhatnagar},
  title = {{Cauchy annealing schedule: an annealing schedule for Boltzmann selection scheme in evolutionary algorithms}},
  booktitle = {IEEE CEC},
  year = {2004},
  doi = {10.1109/cec.2004.1330837},
}
Figure