Analysis of the (1+1)-EA-ES-Bilevel on Mixed Discrete-Continuous Optimization Problems with Interactions
Timo Kötzing, Jurek Sander
原文摘要
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 $Θ(n_d \cdot \log n_d \cdot n_c \cdot \log(R/\sqrtε))$, where $n_d$ is the number of discrete variables, $n_c$ 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.
cs.NE