Benchmarks

bbob-mixint

COCO's bbob-mixint suite (Tušar et al., GECCO 2019) has 24 functions where 80% of the variables are integers with 2 to 16 values. Plain CMA-ES often stalls on this suite, because its step size becomes smaller than the integer grid. CMA-ES with margin (Hamano et al., GECCO 2022) prevents this with a lower bound on the marginal probabilities. In PolyStep, the caller sets the radius. Here the radius decreases geometrically, and the run restarts when the radius becomes too small.

We ran dimensions 5 and 10, instances 1-15, one run each, with a budget of 10^4 * dim evaluations. PolyStep used PolyStepES with the box bounds, a repair that rounds the integer coordinates, a geometric radius decay and random restarts. We tuned its three settings on dimension 20, which is not in the table: epsilon = 0.1, a start radius equal to the mean box width, and decay 0.95. The two baselines are the archived COCO runs of CMA-ES with margin (2022) and pycma (2019). We did not tune them. benchmark/ contains all files to run the experiment again.

The table gives the fraction of solved (function, instance, target) triples for 51 targets from 10^2 to 10^-8, after 100, 1000 and 10^4 evaluations per dimension:

Up to 1000 * dim evaluations, PolyStep solves approximately as many targets as the better CMA-ES, or more. Most of its advantage comes from the multimodal functions. With the full budget, it ties CMA-ES with margin. It is worse than pycma, by .02 in dimension 5 and by .08 in dimension 10. It is weakest on separable functions, where both CMA-ES variants reach all targets in dimension 5. The results for the conditioning groups are mixed, so the table does not include them. The script prints them.

This is a small pilot (15 runs per function and dimension), not a ranking. The plots are the COCO runtime ECDFs. After the budget of each algorithm (the cross), cocopp extends the curves with simulated restarts.

Examples

The scripts in examples/ compare PolyStep with tuned baselines on OR and decision-focused learning problems. The home page gives their results.