cs.NENov 18, 2026

Analysis of the (1+1)-EA-ES-Bilevel on Mixed Discrete-Continuous Optimization Problems with Interactions

Authors: Timo Kötzing, Jurek Sander

Organizations: Hasso Plattner Institute, University of Potsdam, Potsdam, Germany

Abstract

Mixed discrete-continuous optimization problems can pose challenges -- especially for previous integrated approaches -- when interactions cause beneficial discrete changes to be rejected before sufficient continuous adjustment. We introduce ProximityOneMax as a simple benchmark with pairwise discrete-continuous interactions. On this function, we prove an exponential lower bound on the expected time for the (1+1)-EA-ES-Integrated to reach the target accuracy when initialized near a continuous optimum for a suboptimal discrete configuration with a sufficiently small step size. Experiments show frequent entries into such states from random initialization. We introduce the (1+1)-EA-ES-Bilevel, which uses an upper-level (1+1)-EA to optimize discrete variables and a lower-level (1+1)-ES to optimize continuous variables for each fixed discrete offspring before selection. For several interaction benchmarks and sufficiently small target values ε>0ε> 0 that require an optimal discrete configuration, using fixed continuous initialization and a suitable fixed budget per lower-level call, we prove that the expected number of fitness evaluations to reach objective value at most εε is Θ(nd⋅log⁡nd⋅nc⋅log⁡(R/ε))Θ(n_d \cdot \log n_d \cdot n_c \cdot \log(R/\sqrtε)), where ndn_d is the number of discrete variables, ncn_c is the number of continuous variables, and RR bounds the distances from the fixed continuous starting point to all relevant continuous optima for fixed discrete configurations.

Figures & tables

Explore similar work

CardsList
  1. Mixed-Categorical Black-Box Optimization via Information-Geometric Bilevel Decomposition

    Jun 11, 2026Marc Ong, Shinichi Shirakawa, Youhei AkimotoBlack-Box OptimizationBilevel Optimization

  2. Convergence Analysis of Evolution Strategies for Mixed-Integer Optimization

    May 20, 2026Ryoki Hamano, Kento Uchida, Shinichi ShirakawaEvolutionary OptimizationEvolution Strategies

  3. Block-Bench: A Framework for Controllable and Transparent Discrete Optimization Benchmarking

    Apr 8, 2026Furong Ye, Frank Neumann, Thomas Bäck +1Benchmark DesignSynthetic Benchmark Generation