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 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⋅lognd⋅nc⋅log(R/ε)), where nd is the number of discrete variables, nc is the number of continuous variables, and R bounds the distances from the fixed continuous starting point to all relevant continuous optima for fixed discrete configurations.
Figures & tables
Figure 1. Pairwise landscape for w=0.5 . The two bands correspond to xi∈{0,1} , the color represents the objective value, and the arrows indicate the negative gradient with respect to yi . A flip from xi=0 to xi=1 shifts the continuous optimum from yi=1 to yi=0 . The dashed line marks the equal-value threshold yswitch=(1+w)/2 . Two horizontal heat-map bands are shown over the continuous variable yi. The lower band corresponds to xi=0 and has its minimum at yi=1, whereas the upper band corresponds to xi=1 and has its minimum at yi=0. Horizontal arrows point toward the respective continuous minima. A vertical arrow illustrates a bit flip at fixed yi, which changes the direction of continuous optimization. A dashed vertical line at yi=0.75 marks the point at which both bit values have equal objective value. The conditional minimum \Bracketsxi,yi=(0,1) and the global minimum \Bracketsxi,yi=(1,0) are highlighted by separate markers.
Benchmark
w
y∗(x)
SphereOneMax ( Sadowski, 2020 )
1
0nc
Type-II ( Akimoto et al., 2025 )
1
ϕ∗(x)=aV∗x+b∗
ProximityOneMax
w>0
1−x
Table 1. Specializations of GeneralizedProximityOneMax . For ProximityOneMax , nd=nc=N .
Figure 2. Observed trap-entry frequencies of the (1+1)-EA-ES-Integrated on ProximityOneMax , using 100 independent runs per (N,w) and a budget of 500N iterations per run. Each line represents one weight. Line plot of observed trap-entry frequencies against the number of variable pairs N. Five curves show weights 0.1, 0.3, 0.5, 0.7, and 0.9. Frequencies increase with N and are lower for larger weights under the tested settings.
Mixed categorical-continuous optimization arises in many practical domains, yet remains challenging. In the black-box setting, evolution strategy-based approaches have shown promise in extending the efficiency and robustness of the CMA-ES to mixed-variable spaces. However, these methods exhibit worsened performance when strong categorical-continuous interactions are present, as their underlying search distributions assume independence between categorical and continuous variables. To address this limitation, we propose a bilevel optimization framework that explicitly captures such interactions by optimizing over categorical variables in an outer loop, and over continuous variables conditioned on each categorical configuration in an inner loop. We formulate each level of the bilevel problem as a stochastic relaxation under information-geometric optimization. To mitigate the high computational cost inherent to bilevel optimization, we introduce a warm-starting strategy that accelerates the lower-level search by selecting the best among multiple cached configurations and updating the cache after each iteration. Experimental results on binary-continuous domain demonstrate that the proposed method outperforms existing state-of-the-art approaches in interaction-handling capability while also being more computationally efficient across benchmarks encompassing both previously reported and newly proposed types of interaction.
Marc Ong, Shinichi Shirakawa, Youhei Akimoto
University of Tsukuba, Tsukuba, Japan · Yokohama National University, Yokohama, Japan · RIKEN Center for Advanced Intelligence Project, Tokyo, Japan
Mixed-integer extensions of evolution strategies (ES) that discretize selected coordinates of sampled continuous vectors often impose a lower bound on the standard deviation of integer variables to prevent premature convergence. While these methods show promising empirical results, this handling can slow the convergence of continuous variables, and its impact has lacked a clear theoretical account. In this paper, we provide a convergence analysis of evolution strategies for mixed-integer optimization, inspired by the drift analysis of the (1+1)-ES in the continuous domain. Specifically, we consider two (1+1)-ES variants for mixed-integer domains: (1+1)-LB-ES, which introduces a lower bound on the standard deviation for integer variables, and (1+1)-LUB-ES, which combines both lower and upper bounds to enhance the convergence of the continuous variables. Focusing on the optimization phase after the integer variables have been optimized, we rigorously analyze their convergence behavior on a benchmark function designed for mixed-integer domains. Our results show that (1+1)-LB-ES can suffer from premature convergence when the number of integer variables is large, while (1+1)-LUB-ES achieves linear convergence under suitable parameter settings. These findings provide theoretical insights into the impact of integer handling on convergence performance and guidance for the design of mixed-integer ES.
We present a novel approach for constructing discrete optimization benchmarks that enables fine-grained control over problem properties, and such benchmarks can facilitate analyzing discrete algorithm behaviors. We build benchmark problems based on a set of block functions, where each block function maps a subset of variables to a real value. Problems are instantiated through a set of block functions, weight factors, and an adjacency graph representing the dependency among the block functions. Through analyzing intermediate block values, our framework allows to analyze algorithm behavior not only in the objective space but also at the level of variable representations in the obtained solutions. This capacity is particularly useful for analyzing discrete heuristics in large-scale multi-modal problems, thereby enhancing the practical relevance of benchmark studies. We demonstrate how the proposed approach can inspire the related work in self-adaptation and diversity control in evolutionary algorithms. Moreover, we explain that the proposed benchmark design enables explicit control over problem properties, supporting research in broader domains such as dynamic algorithm configuration and multi-objective optimization.
Furong Ye, Frank Neumann, Thomas Bäck +1
LIACS, Leiden University, Leiden, the Netherlands · Optimisation and Logistics, School of Computer Science and Information Technology, Adelaide University, Adelaide, Australia