Convergence Analysis of Evolution Strategies for Mixed-Integer Optimization

Problem
This paper addresses the gap in theoretical understanding of the convergence behavior of evolution strategies (ES) when applied to mixed-integer optimization problems. While existing methods have shown empirical success, they often impose constraints on the standard deviation of integer variables to mitigate premature convergence, which can adversely affect the convergence of continuous variables. The authors note that the impact of these constraints on convergence has not been rigorously analyzed, particularly in the context of mixed-integer domains. This work is presented as a preprint and has not yet undergone peer review.

Method
The authors propose a convergence analysis of two variants of the (1+1)-ES tailored for mixed-integer optimization: (1+1)-LB-ES and (1+1)-LUB-ES. The (1+1)-LB-ES variant introduces a lower bound on the standard deviation for integer variables, while (1+1)-LUB-ES incorporates both lower and upper bounds to improve the convergence of continuous variables. The analysis is grounded in drift analysis techniques typically used in continuous optimization. The authors focus on the optimization phase after integer variables have been optimized, rigorously analyzing the convergence behavior on a benchmark function specifically designed for mixed-integer domains. The theoretical framework is built upon established principles of ES, adapted to account for the unique challenges posed by mixed-integer settings.

Results
The findings indicate that (1+1)-LB-ES is prone to premature convergence, particularly when the number of integer variables is large, which can hinder the overall optimization process. In contrast, (1+1)-LUB-ES demonstrates linear convergence under appropriate parameter settings. The authors provide specific convergence rates and conditions that delineate the performance of both strategies, offering a quantitative comparison against traditional ES methods. The results suggest that the choice of bounds on integer variables significantly influences the convergence dynamics of the algorithm, providing a clearer understanding of how these constraints affect optimization outcomes.

Limitations
The authors acknowledge that their analysis is limited to specific benchmark functions and may not generalize across all mixed-integer optimization problems. They also note that the theoretical results are contingent on the proper tuning of parameters, which may not be straightforward in practice. Additionally, the paper does not explore the performance of these strategies in high-dimensional spaces or with varying distributions of integer variables, which could further impact convergence behavior.

Why it matters
This work has significant implications for the design and application of evolution strategies in mixed-integer optimization contexts. By providing a theoretical foundation for understanding the convergence behavior of ES with respect to integer constraints, the authors offer valuable insights that can inform the development of more effective optimization algorithms. The findings may lead to improved strategies for handling mixed-integer problems in various domains, including engineering design, logistics, and resource allocation, where such optimization challenges are prevalent.

Authors: Ryoki Hamano, Kento Uchida, Shinichi Shirakawa
Source: arXiv:2605.21000
URL: https://arxiv.org/abs/2605.21000v1