TL;DR
Meta Multi-Objectivization (MMO) is a powerful technique for jumping out of local optima in software engineering (SE) optimization by adding an auxiliary objective. This paper generalizes MMO across diverse SE domains and introduces L2RAC, a tool that automatically selects the best auxiliary objective for a given problem, significantly outperforming state-of-the-art optimizers while saving massive computational costs.
What Problem Does This Paper Address?
Search-based software engineering (SBSE) often deals with discrete, rugged landscapes where optimizers easily get trapped in "local optima"—solutions that are better than their immediate neighbors but globally suboptimal. Meta Multi-Objectivization (MMO) was recently proposed to mitigate this by transforming a single-objective problem into a bi-objective one using an auxiliary objective.
However, MMO was originally tailored specifically for software configuration tuning. Its effectiveness depends heavily on the choice of the auxiliary objective and how it correlates with the target. Until now, there was no clear guidance on how to pick the right auxiliary objective for the wide variety of SE optimization tasks, often leaving researchers to rely on expensive trial-and-error.
Methods
The researchers first provide a theoretical foundation, proving that MMO's success hinges on "Property 3": the correlation between the target and auxiliary objectives must be uncertain. If they are too perfectly correlated (positively or negatively), the geometric transformation fails to create the necessary diversity to escape local traps.
To automate the selection process, they developed L2RAC (Learning to Rank Auxiliary Choices). L2RAC works in four stages:
- Sampling: It takes a small sample of solutions from a new problem case.
- Feature Extraction: It computes 25 "landscape features" (e.g., skewness, kurtosis, dominance ratios) that characterize the problem's difficulty and structure.
- Ranking: Using a pre-trained LambdaRank model, it ranks seven different forms of auxiliary objectives (such as Gaussian Noise, Age, or Grid Diversity).
- Recommendation: It recommends the top-ranked auxiliary objective to be used with a standard multi-objective optimizer like NSGA-II.
Datasets
The authors conducted a large-scale empirical study covering 212 cases across nine diverse SE optimization problems:
- Requirements & Planning: Next Release Problem (NRP), Software Project Scheduling (SPS).
- Testing: Software Product Lines Testing (SPLT).
- Maintenance: Third Party Library Migration (TPLM).
- Performance & Cloud: Software Configuration Tuning (SCT), Workflow Scheduling (WS), Web Service Composition (WSC).
- Prediction: Software Effort Estimation (SEE), Software Defect Prediction (SDP).
Key Insights and Ideas
- No Universal Best Objective: The study reveals that no single auxiliary objective dominates across all SE problems. For instance, using an "Original" problem property works well for the Next Release Problem but fails completely for Defect Prediction.
- The "Aha" of Property 3: The theoretical proof shows that linear, monotonic correlations are the enemy of MMO. The best auxiliary objectives are those that introduce non-linear relationships, effectively "shaking up" the search space.
- Landscape-Awareness: The success of L2RAC proves that the "shape" of an optimization landscape (quantified by features like nearest better clustering) is a strong predictor of which auxiliary objective will help an optimizer navigate it.
Key Results
- Dominating the Baselines: When specialized with the right auxiliary objective, MMO outperformed state-of-the-art (SOTA) domain-specific optimizers in 79% of cases and general-purpose optimizers (like SWAY) in 94% of cases.
- High Recommendation Accuracy: L2RAC achieved up to a 60% improvement in ranking accuracy (NDCG) compared to random guessing.
- Massive Efficiency Gains: L2RAC saves up to 99% of the computational cost that would otherwise be spent on trial-and-error. In one example (Workflow Scheduling), it reduced the time to find the best configuration from 58 days to just 11.5 days.
Limitations and Future Work
The authors acknowledge that their current approach selects a static auxiliary objective before the search begins. A promising future direction is Adaptive MMO, where the auxiliary objective could be dynamically switched or reweighted during the optimization process as the population moves through different regions of the landscape. Additionally, while this work focuses on single-objective target problems, extending the specialized MMO framework to inherently multi-objective SE tasks remains an open challenge.
Summary updated