A Confidence-Driven Evolutionary Algorithm for Noisy Optimization with Joint Chance Constraints

Real-world optimization problems often involve black-box functions and uncertainties in their evaluation, widely referred to as noisy optimization problems (NOPs). Evolutionary algorithms (EA), including Evolutionary Strategies (ES) and genetic algorithms (GA) have been commonly adopted to solve these problems in the contemporary literature. An ongoing challenge is the computational expense involved, given the number of evaluations required for good fitness estimation and ranking. Two fundamental methods commonly used for fitness estimation for NOPs are implicit averaging and explicit averaging. Explicit averaging uses resampling of solutions to improve the estimates, while implicit averaging typically uses a large population size with low resampling. Implicit averaging has been shown to have theoretical advantages for certain cases, which has motivated some recent approaches to use them. However, a recent study demonstrated that its performance is highly dependent on certain assumptions about the function, such as steepness and constant noise level, which may not apply for majority of the real world problems. Moreover, most existing algorithms have only considered homoscedastic noise, where the amplitude of variation is uniform across the entire search space, as opposed to more generic case of heteroscedastic noise. To address these issues, we introduce a set of heteroscedastic test problems and propose a novel confidence ranking method that employs a computationally efficient explicit averaging strategy with sampling budget adaptation. It is implemented within the Covariance Matrix Adaptation ES (CMA-ES) and GA frameworks to demonstrate its effectiveness and versatility. The resulting algorithm is evaluated on a range of problems with both homoscedastic and heteroscedastic noise, and it demonstrates superior performance compared to state-of-the-art approaches.

Chance-constrained stochastic programs (CCSPs) require solutions that satisfy uncertain constraints with high probability. Standard approaches either embed scenarios directly into optimization by considering sample average approximation (SAA)-based reformulations, growing prohibitively expensive and often failing to find feasible solutions; or employ conservative reformulations that guarantee feasibility but sacrifice objective quality by design. We propose ACCESS (Adaptive Chance-Constrained Exploration via Structured Sampling), a structured sampling framework that decouples optimization from feasibility evaluation. First, high-quality candidate solutions are generated by solving many inexpensive single-scenario subproblems, avoiding sampling directly in the constrained high-dimensional solution space. Second, feasibility is assessed separately via large-scale batched simulation over a massive number of scenarios, which is naturally amenable to GPU parallelism. That reduces the search from a high-dimensional solution space to a two-dimensional parameter space controlling conservatism and scenario diversity; while concentrating on candidates near the feasibility boundary, where high-quality feasible solutions lie. We also introduce a variant, ACCESS($δ$), which provides certified feasibility guarantees with probability $1-δ$. Experiments across three benchmark classes and five scenario distributions show that ACCESS matches or exceeds the best objective found by any method in nearly every setting, while ACCESS($δ$) is empirically feasible on every instance. The conservative reformulations remain several percent worse in objective, and SAA is frequently infeasible while taking an order of magnitude longer on the harder benchmarks.

This paper presents novel method for distribution-free robust trajectory optimization and control of discrete-time, nonlinear, and non-Gaussian stochastic systems, with closed-loop guarantees on chance constraint satisfaction. Our framework employs conformal inference to generate coverage-based confidence sets for the closed-loop dynamics around arbitrary reference trajectories, by constructing a joint nonconformity score to quantify both the validity of contraction (i.e., incremental stability) conditions and the impact of external stochastic disturbance on the closed-loop dynamics, without any distributional assumptions. Via appropriate constraint tightening, chance constraints can be reformulated into tractable, statistically valid deterministic constraints on the reference trajectories. This enables a formal pathway to leverage and validate learning-based motion planners and controllers, such as those with neural contraction metrics, in safety-critical real-world applications. Notably, our statistical guarantees are non-diverging and can be computed with finite samples of the underlying uncertainty, without overly conservative structural priors. We demonstrate our approach in motion planning problems for designing safe, dynamically feasible trajectories in both numerical simulation and hardware experiments.