Artificial Mutation inspired Hyper-heuristic for Runtime Usage of Multi-objective Algorithms

Donia El Kateb, François Fouquet, Johann Bourcier, Yves Le Traon

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.

The Sputnik integration process within a standard MOEA loop, highlighting the three-step mutation operator selection based on historical performance.

As shown in the figure above, the Sputnik process consists of three main steps:

  1. Operators Ranking: Ranking mutation operators according to their impact on fitness scores.
  2. Strategy Selection: Choosing between an Elitist strategy (prioritizing the single best-performing operator) or a Caste strategy (assigning probabilities based on relative performance).
  3. 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.

Comparison of Hypervolume convergence over generations for Random, Sputnik (Caste), and Sputnik (Elitist) strategies.

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

Abstract

In the last years, multi-objective evolutionary algorithms (MOEA) have been applied to different software engineering problems where many conflicting objectives have to be optimized simultaneously. In theory, evolutionary algorithms feature a nice property for runtime optimization as they can provide a solution in any execution time. In practice, based on a Darwinian inspired natural selection, these evolutionary algorithms produce many deadborn solutions whose computation results in a computational resources wastage: natural selection is naturally slow. In this paper, we reconsider this founding analogy to accelerate convergence of MOEA, by looking at modern biology studies: artificial selection has been used to achieve an anticipated specific purpose instead of only relying on crossover and natural selection (i.e., Muller et al [18] research on artificial mutation of fruits with X-Ray). Putting aside the analogy with natural selection , the present paper proposes an hyper-heuristic for MOEA algorithms named Sputnik 1 that uses artificial selective mutation to improve the convergence speed of MOEA. Sputnik leverages the past history of mutation efficiency to select the most relevant mutations to perform. We evaluate Sputnik on a cloud-reasoning engine, which drives on-demand provisioning while considering conflicting performance and cost objectives. We have conducted experiments to highlight the significant performance improvement of Sputnik in terms of resolution time.
BibTeX
@inproceedings{kateb2013artificial,
  author = {Donia El Kateb and François Fouquet and Johann Bourcier and Yves Le Traon},
  title = {{Artificial Mutation inspired Hyper-heuristic for Runtime Usage of Multi-objective Algorithms}},
  booktitle = {HAL},
  year = {2013},
}
Figure