Multiple-gain Estimation for Running Time of Evolutionary Combinatorial Optimization

Min Huang, Pengxiang Chen, Han Huang, Tonli He, Yushan Zhang, Zhifeng HaoarXiv 2025 · OpenReview

TL;DR

This paper introduces a "multiple-gain model" to more accurately estimate the running time of evolutionary algorithms for combinatorial optimization problems. By extending the "average gain model," this new approach provides tighter theoretical bounds and a more unified framework for analyzing algorithm performance, validated through experiments on classic problems.

What Problem Does This Paper Address?

Estimating how long evolutionary algorithms (EAs) will take to find a solution for combinatorial optimization problems is crucial for understanding their efficiency and improving them. However, analyzing these algorithms is challenging, especially when dealing with problems where the "fitness" (how good a solution is) can fluctuate unpredictably. Existing methods, like the "average gain model," struggle with this variability. This paper aims to bridge this gap by proposing a more robust method that can handle these fitness fluctuations, leading to more accurate running time predictions for a wider range of combinatorial optimization problems.

Methods

The core contribution is the multiple-gain model, an enhancement of the existing "average gain model." The average gain model looks at the fitness improvement in a single step. The multiple-gain model, however, considers the cumulative fitness gain over multiple steps (parameterized by 'k'). This allows it to smooth out the effects of fluctuating fitness values and provide a more stable estimate of the algorithm's progress.

The paper develops theoretical frameworks (Theorems 1-8 and Corollaries) based on this multiple-gain model to derive upper bounds for the Expected First Hitting Time (EFHT) – the average number of iterations to find the global optimum. These theorems are then applied to specific combinatorial problems:

  • (1+1) EA for the Onemax problem: A simpler problem used to demonstrate the model's ability to provide briefer proofs and consistent results with existing bounds.
  • (1+1) EA for the knapsack problem with favorably correlated weights: The model yields tighter upper bounds than previous work.
  • (1+1) EA for general k-MAX-SAT problems: The paper provides the first closed-form expression for the EFHT upper bound for this class of problems.

Datasets

The paper does not introduce new datasets. Instead, it uses well-established combinatorial optimization problems as benchmarks:

  • Onemax problem: A simple problem where the goal is to maximize the number of '1's in a binary string.
  • Knapsack problem with favorably correlated weights: A classic optimization problem involving selecting items with values and weights to maximize total value within a weight constraint.
  • k-MAX-SAT problem: A generalization of the satisfiability problem, aiming to satisfy the maximum number of clauses in a Boolean formula.

The experiments evaluate the theoretical bounds against simulated runs of these problems.

Key Insights and Ideas

  • The "multiple-gain" concept is key: By looking at fitness gains over k steps instead of just one, the model becomes more resilient to the noisy fitness landscapes common in combinatorial optimization. This is the fundamental improvement over the "average gain" model.
  • Unified framework: The multiple-gain model offers a more general approach to analyzing running times, reducing the need for highly problem-specific analyses.
  • Tighter bounds and simpler proofs: The model not only provides more accurate theoretical bounds but also simplifies the mathematical proofs for existing results and establishes new ones for complex problems.
  • Experimental validation is crucial: The paper strongly emphasizes that theoretical results are backed by experimental simulations, showing a high correlation between predicted and actual running times.

Key Results

The paper presents several significant theoretical results:

  • A briefer proof for the time complexity of (1+1) EA on the Onemax problem, consistent with known O(n log n) bounds.
  • Two tighter average-case upper bounds for (1+1) EA on the knapsack problem with favorably correlated weights, improving upon existing results.
  • A closed-form expression for the average-case upper bound of EFHT for (1+1) EA on general k-MAX-SAT problems, a novel contribution.
  • Experimental results show a high correlation (typically > 0.91) between the theoretical upper bounds (EFHT1, EFHT2) and the actual estimated running times (To, Tmax) across all tested problems, validating the model's accuracy.

Limitations and Future Work

  • Focus on single-objective optimization: The current work is limited to single-objective problems. The authors suggest that extending the multiple-gain model to multi-objective optimization problems would be a valuable future direction.
  • Parameter selection: While the model provides a framework, selecting the optimal 'k' parameter and estimating 'klow' (a lower bound for k) can still require experimental effort.
  • Theoretical vs. Practical: While the theoretical bounds are proven to be upper bounds, the gap between the theoretical bound and the actual running time can still be significant in practice, especially for complex problems. Future work could focus on refining these bounds or developing tighter lower bounds.

Summary updated

Abstract

The running-time analysis of evolutionary combinatorial optimization is a fundamental topic in evolutionary computation. Its current research mainly focuses on specific algorithms for simplified problems due to the challenge posed by fluctuating fitness values. This paper proposes a multiple-gain model to estimate the fitness trend of population during iterations. The proposed model is an improved version of the average gain model, which is the approach to estimate the running time of evolutionary algorithms for numerical optimization. The improvement yields novel results of evolutionary combinatorial optimization, including a briefer proof for the time complexity upper bound in the case of (1+1) EA for the Onemax problem, two tighter time complexity upper bounds than the known results in the case of (1+$\lambda$) EA for the knapsack problem with favorably correlated weights and a closed-form expression of time complexity upper bound in the case of (1+$\lambda$) EA for general $k$-MAX-SAT problems. The results indicate that the practical running time aligns with the theoretical results, verifying that the multiple-gain model is more general for running-time analysis of evolutionary combinatorial optimization than state-of-the-art methods.
BibTeX
@misc{huang2025multiple,
  author = {Min Huang and Pengxiang Chen and Han Huang and Tonli He and Yushan Zhang and Zhifeng Hao},
  title = {{Multiple-gain Estimation for Running Time of Evolutionary Combinatorial Optimization}},
  year = {2025},
  eprint = {2501.07000},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2501.07000},
}
Figure