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

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

TL;DR

This paper introduces "Sputnik," a novel hyper-heuristic that accelerates Multi-Objective Evolutionary Algorithms (MOEAs) by intelligently selecting mutation operators, inspired by artificial mutation in biology. By learning from past mutation effectiveness, Sputnik significantly reduces the time and computational resources needed to find optimal trade-offs in complex problems, as demonstrated on a cloud reasoning engine.

What Problem Does This Paper Address?

Multi-Objective Evolutionary Algorithms (MOEAs) are powerful tools for tackling problems with multiple, often conflicting, objectives. They are inspired by Darwinian natural selection, where populations evolve over generations to find optimal solutions. However, a key challenge with MOEAs is their computational cost. The "natural selection" process, particularly mutation, can be slow and inefficient, leading to many "deadborn" solutions that waste computational resources. This is a significant hurdle for real-time applications where quick, acceptable solutions are crucial. The paper aims to bridge this gap by accelerating MOEA convergence without sacrificing solution quality.

Methods

The core contribution is the "Sputnik" hyper-heuristic. Unlike traditional MOEAs that rely on random mutation operators, Sputnik employs an "artificial mutation" strategy. This involves:

  • Learning Mutation Impact: Sputnik continuously monitors the impact of different mutation operators on the fitness functions. It calculates the "delta impact" – the change in average fitness score between generations – for each operator.
  • Selective Operator Choice: Based on this learned impact, Sputnik dynamically selects mutation operators. It prioritizes operators that have historically led to better improvements.
  • Elitist and Caste Strategies: Two selection strategies are proposed:
  • Elitist Strategy: Always chooses the operator with the highest positive delta impact.
  • Caste Strategy: Partitions selection probability among operators with positive impact, offering more equity.
  • Maintaining Equity: A small probability (10%) is maintained for random operator selection to prevent the exclusion of less-tested operators and ensure diversity.
  • Integration with MOEAs: Sputnik acts as a meta-algorithm, guiding the mutation process of existing MOEA frameworks.

Datasets

Not discussed in the paper. The evaluation was performed on a simulated cloud reasoning engine.

Key Insights and Ideas

  • Biology as Inspiration for Efficiency: The paper effectively draws a parallel between artificial mutation in modern biology (e.g., using X-rays to induce specific genetic changes) and the need for more targeted, efficient mutation in MOEAs. This moves beyond the direct analogy of natural selection to a more pragmatic, goal-oriented approach.
  • The Cost of Randomness: The research highlights how random mutation, while mimicking natural processes, can be a significant bottleneck in computational performance, leading to wasted resources.
  • Learning for Optimization: The core idea of Sputnik is that by learning from past performance, an algorithm can make smarter choices about which operators to use, leading to faster convergence.
  • Balancing Efficiency and Diversity: The inclusion of both elitist and caste strategies, along with a small probability for random selection, demonstrates a thoughtful approach to balancing the drive for rapid improvement with the need to maintain population diversity.

Key Results

The paper presents experimental results on a cloud reasoning engine prototype, comparing Sputnik (with both elitist and caste strategies) against a standard random mutation operator selection.

  • Reduced Generations: Sputnik significantly reduces the number of generations required to reach an acceptable trade-off. In one experiment, Sputnik achieved a target hypervolume (90% of the best solution) in 176 generations, compared to 279 generations for random selection, representing a reduction of approximately 37%.
  • Comparable Solution Quality: Sputnik strategies achieved comparable or even better hypervolume scores (a measure of Pareto-front quality) than random selection. The caste strategy, in particular, showed potential for improving hypervolume scores due to operator diversity.
  • Effectiveness Across MOEAs: When integrated with popular MOEA algorithms like NSGA-II, Sputnik (both configurations) consistently outperformed their standard counterparts in achieving better trade-offs faster, as shown in Table 1.

Limitations and Future Work

  • Limitations: The paper acknowledges that while elitist strategies converge slightly faster, the caste strategy might achieve better hypervolume scores due to its inherent diversity. The evaluation was conducted on a specific cloud reasoning engine prototype.
  • Future Work: The authors plan to:
  • Evaluate the relevancy of Sputnik's heuristic on crossover operations.
  • Classify elitist strategies to analyze their impact on solution diversity.

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},
}

Loading related content...

Figure