Abstract
Multi-objective evolutionary algorithms (MOEAs) are increasingly applied to software engineering problems requiring simultaneous optimization of conflicting objectives. While theoretically suitable for runtime optimization, traditional MOEAs often suffer from slow convergence due to the generation of "deadborn" solutions through random mutation. This paper introduces Sputnik, a hyper-heuristic that leverages artificial selective mutation to accelerate convergence. By tracking the historical efficiency of mutation operators, Sputnik prioritizes those that most effectively improve solution fitness. Evaluated on a cloud-reasoning engine, Sputnik demonstrates a significant reduction in resolution time without sacrificing solution quality.
Introduction
In runtime environments, such as cloud resource management, systems must make complex decisions—balancing cost and performance—within seconds. Traditional MOEAs mimic Darwinian natural selection, relying on random mutation and crossover. However, natural selection is inherently slow. The computational resources wasted on ineffective mutations can be prohibitive in time-sensitive scenarios.
Sputnik addresses this gap by shifting from "natural" random evolution to "artificial" targeted mutation. Inspired by modern biology's use of artificial selection to achieve specific purposes, Sputnik transforms mutation operators from random variables into learned tools that must "earn" their usage based on historical performance.
The Sputnik Hyper-heuristic
Sputnik is designed as a "smart" layer that integrates with existing MOEAs. Its core mechanism involves monitoring the "delta impact" of each mutation operator—measuring how much a specific mutation improves the average fitness of the population across generations.
As shown in the figure above, the Sputnik process consists of three main steps:
- Operators Ranking: Ranking mutation operators according to their impact on fitness scores.
- Strategy Selection: Choosing between an Elitist strategy (prioritizing the single best-performing operator) or a Caste strategy (assigning probabilities based on relative performance).
- Probability Setting: Determining the selection probability for each operator. To maintain search space diversity and avoid local optima, Sputnik reserves a 10% probability for pure random mutation.
Experimental Setup
The effectiveness of Sputnik was evaluated using a simulated Cloud Reasoning Engine. The scenario involved a hybrid cloud environment with 100 virtual nodes. The algorithm aimed to minimize two conflicting objectives:
- Cost: The total number of active virtual machines.
- Latency: The average communication delay between software components.
Sputnik was benchmarked against standard versions of popular MOEAs, including NSGA-II, $\epsilon$-MOEA, and SPEA 2, using the Polymer model@runtime framework.
Results and Discussion
The experimental results highlight a substantial performance boost. Sputnik achieved "acceptable" solutions (90% of the optimal hypervolume) in just 176 generations, compared to 279 generations for the standard random mutation approach—a 37% improvement in convergence speed.
Crucially, this speedup does not come at the expense of solution quality. Sputnik achieved hypervolume scores between 0.77 and 0.81, comparable to or slightly exceeding the random baseline of 0.78. As illustrated in the convergence graph, both Sputnik strategies (Caste and Elitist) reach higher hypervolume levels significantly faster than the random baseline. While the Elitist strategy is often faster initially, the Caste strategy provides a robust balance of speed and long-term solution quality by maintaining a diverse set of effective operators.
Conclusion
Sputnik demonstrates that by moving away from biological randomness toward engineering-focused artificial mutation, MOEAs can be made significantly more efficient for runtime applications. Future work will explore applying similar elitist selection logic to crossover operators and conducting deeper longitudinal analyses of population diversity.
Reference: El Kateb, D., Fouquet, F., Le Traon, Y., & Bourcier, J. (2014). Sputnik: Elitist Artifical Mutation Hyper-heuristic for Runtime Usage of Multi-objective Evolutionary Algorithms. arXiv:1402.4442v1 [cs.SE].
Summary updated