💻 computer science

Which Optimizer, At What Budget? A Tournament of Optimizers for Search-Based SE

This paper demonstrates that no single optimizer is universally optimal for software engineering configuration tasks, as the best choice depends on the labeling budget, and proposes a cost-effective table lookup method using two task attributes to predict the optimal optimizer with accuracy comparable to a hindsight oracle.

Original authors: Kishan Kumar Ganguly, Tim Menzies

Published 2026-07-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Kishan Kumar Ganguly, Tim Menzies

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to tune a super-complex video game. You have 460 different switches, dials, and hidden codes. Changing just one setting might require the computer to rebuild the entire game and run a massive test to see if it works better. You can't try every single combination because there are more possibilities than there are stars in the sky. So, you need a smart "tuner" (an optimizer) to guess which settings are worth testing.

The problem? There are dozens of different tuners available, and nobody knows which one is the best for your specific game. Some experts say, "Just use this famous one!" But this paper says, "Hold on, that's a trap."

The Great Optimizer Tournament

The authors, Kishan Kumar Ganguly and Tim Menzies, decided to settle this by running a massive tournament. They didn't just pick a few; they gathered 20 different optimizers and pitted them against 106 different software engineering tasks.

They didn't just run the tournament once. They tested it at four different "budgets" (how many times the computer is allowed to try a setting): 30, 50, 100, and 200 tries. To run all these tests, they burned through 14,000 CPU hours. That's a lot of computer time!

The Big Surprise: There Is No "Best" Tuner

Here is the most important thing they found: No single optimizer wins everything.

In fact, the "champion" changes depending on how much time (or budget) you have.

When you are broke on time (only 30 tries): The winner is a clever, fast learner called EZR. It's like a scout that quickly checks the most promising areas.
When you have plenty of time (200 tries): The winner switches to a brute-force powerhouse called Differential Evolution (DE). It's like a team of explorers that slowly but surely maps out the whole map.

The paper measured that for 58% of the tasks, the best optimizer changed at least once as the budget grew. If you picked the "champion" for a small budget and stuck with it for a big budget, you would be wrong on up to half of your tasks.

The "One-Size-Fits-All" Myth

The authors also tested a popular idea: that complex "Multi-Objective" tuners (which try to balance many goals at once) are always better than simple "Single-Objective" tuners.

The Result: They were wrong. At the same budget, the simple tuners often beat the complex ones.
The Catch: To catch up to a simple tuner that had 200 tries, a complex tuner needed 1,000 tries (five times more work) to get the same result.

The "Magic Map" vs. The "Crystal Ball"

So, how do you know which tuner to pick without spending 14,000 hours?

The Failed Crystal Ball:
Scientists often try to predict the winner by analyzing the "shape" of the problem using complex math (called instance clustering). The authors tried this, too.

The Result: It failed miserably. It only predicted the right winner 44.2% of the time. It's like trying to guess the winner of a race by looking at the color of the runners' shoes; it just doesn't work.

The Winning Magic Map:
Instead of complex math, the authors found a simple cheat sheet based on two things you can see immediately in your data table:

Do your goals fight each other? (e.g., making the game faster but also cheaper?)
What kind of numbers are your settings? (Are they simple Yes/No switches, or big, messy numbers?)

By looking at these two things plus your budget, they created a Heatmap Guide.

If you have a small budget and simple settings, pick EZR.
If you have a big budget or complex settings, pick DE or SMAC.

This simple guide was surprisingly accurate. It matched or beat a "hindsight oracle" (a perfect predictor that already knows the answer) on 74.2% of the tasks, without needing to run any expensive tests first.

The Takeaway

The paper concludes that choosing an optimizer isn't about finding the one "magic tool." It's about matching the tool to your budget and the shape of your data.

Don't waste money on complex math to analyze your problem before you start.
Do look at your data table, check your budget, and use the simple guide.
Remember: If you only have a few tries, use a fast scout. If you have many tries, use a thorough explorer.

The authors suggest that in the future, we might build a "meta-scheduler" that starts with the scout and then hands off to the explorer as the budget grows, getting the best of both worlds. But for now, the simple guide is the best way to save time and get good results.

Technical Summary: Which Optimizer, At What Budget?

Problem Statement

Configuring modern software systems is an unavoidable, expensive, and error-prone task due to the vast configuration spaces (e.g., a single database with 460 binary options creates a space larger than the number of stars in the sky). Search-Based Software Engineering (SBSE) addresses this via black-box optimization, where a fitness function scores configurations and a search algorithm explores the space. However, practitioners face an overwhelming choice of over 20 available optimizers. Current selection guidance is often misleading; for instance, NSGA-II is widely recommended, yet other algorithms can achieve similar results with significantly fewer evaluations.

A critical gap exists: SBSE lacks a systematic way to organize optimizers by the assumptions they encode, and there is no cheap, budget-aware rule for selecting an optimizer for a specific task. The "labeling budget" (the number of evaluations an engineer can afford) is a first-class variable; a single evaluation can cost hours of expert time or full system builds. Consequently, the "best" optimizer for a task at a budget of 30 evaluations may differ entirely from the best at 200 evaluations.

Methodology

The authors conducted a large-scale empirical study involving 106 SE optimization tasks from the MOOT repository, spanning seven domains (e.g., software configuration, performance tuning, project health). The study evaluated 20 black-box optimizers across four labeling budgets (30, 50, 100, and 200 evaluations), repeated over 20 random seeds, consuming approximately 14,000 CPU hours.

Assumption-Indexed Tournament

Rather than creating a simple leaderboard, the authors organized the optimizers into a tournament tree based on seven landscape assumptions derived from the literature (Table III). Each branch of the tree isolates a specific assumption (e.g., local continuity, population-based building blocks, surrogate feasibility, low intrinsic dimensionality).

Single-Objective Tree (TREE 1): Ranks trajectory, population, model-based, and sampler methods.
Multi-Objective Tree (TREE 2): Ranks Pareto-based methods.
Grand Final: Compares the single-objective and multi-objective champions.

Evaluation Metrics

Scoring: Configurations were scored by their normalized Euclidean distance to the "heaven" point (ideal value for all objectives). For multi-objective tasks, the single best returned configuration was used to determine the winner, though frontier-aware metrics (IGD, GD, Hypervolume) were used as sanity checks.
Regret Reduction: Performance was measured by the fraction of the gap between random search and the best possible setting that was closed ( $\rho$ ).
Statistical Analysis: Results were analyzed using Scott-Knott clustering with bootstrap testing and Cliff's delta effect sizes to determine statistically distinct groups.

Key Results

RQ1: Is Optimization Worth Doing?

Yes. Even with very few labels, optimization yields significant gains. At a budget of 30 evaluations, the best optimizers close 31% of the gap between random guessing and the optimal setting. At 200 evaluations, this gap closes to 75%.

RQ2: Does the Budget Change the Winner?

Yes, significantly. The "best" optimizer migrates as the budget increases:

Scarce Budgets ( $B \le 50$ ): EZR (a geometric active learner based on proximity) is the dominant winner.
Plentiful Budgets ( $B \ge 100$ ): DE (Differential Evolution) becomes the dominant winner.
Instability: On up to 50% of tasks, the optimizer selected as "best" at one budget falls outside the top statistical tier at another. Across the four budgets, 58% of tasks changed their best optimizer at least once.

RQ3: Do These Optimizers Really Differ?

The differences are less pronounced than the literature suggests.

Ties: The majority of head-to-head matches result in statistical ties. At affordable engineering budgets, many distinct algorithms deliver indistinguishable results.
Single vs. Multi-Objective: Contrary to the common belief that multi-objective methods are superior for multi-goal tasks, single-objective methods (EZR, DE) consistently matched or beat multi-objective methods (NSGA-II, SPEA2) at equal budgets. Multi-objective methods required roughly 5x the budget (e.g., 1000 samples) to match the performance of single-objective methods at 200 samples.

RQ4: Can We Cheaply Predict the Winner?

Instance Clustering Failed: Attempts to predict the winner using complex instance-space features (e.g., fitness-distance correlation, PCA geometry) achieved only 44.2% accuracy, failing to separate tasks into clean "footprints."
The Cheap Guide Succeeded: A guide based on two cheap-to-obtain task attributes (objective conflict: single vs. multi; input space shape: binary/SAT vs. numeric size) plus the labeling budget achieved 74.2% accuracy. This guide ties or beats a "hindsight oracle" (which knows the test data) on held-out tasks without requiring any additional probes.

Key Contributions

A Catalog of Assumptions: Organized 20 optimizers into a taxonomy based on seven underlying landscape assumptions, moving beyond tool-centric leaderboards.
A Reusable Tournament Rig: An assumption-indexed, budget-indexed tournament framework covering 106 tasks and 20 optimizers, representing the largest SBSE study of its kind.
A Validated Selection Guide: A practical, budget-aware guide (visualized as a heatmap) that allows practitioners to select an optimizer by reading two structural attributes from their data table.
Open Science: The full tournament and replication package are open-sourced.

Significance and Claims

The paper argues that optimizer selection in SBSE should be treated as a budget-dependent scheduling problem rather than a one-shot tool selection. The primary finding is that the "best" optimizer is not static; it migrates from geometric active learners (like EZR) when data is scarce to model-free evolutionary algorithms (like DE) when data is plentiful.

The authors claim that the standard approach of using expensive instance clustering features to predict winners is ineffective at SE budgets. Instead, they propose a "warm handoff" strategy: use EZR to cheaply locate good regions early in the budget, then hand off to DE as the budget grows. This guide allows practitioners to make high-confidence decisions (matching a hindsight oracle on ~75% of tasks) using only structural attributes available before any optimization begins.

The study concludes that while no single optimizer wins everywhere, a simple, cheap rule based on task structure and budget can effectively guide practitioners, rendering expensive, data-heavy instance analysis unnecessary for the majority of SE tasks.