Multi-Agent Election-Based Hyper-Heuristics

Vinicius Renan de Carvalho, Jaime Simão SichmanIJCAI 2018 · DOI

TL;DR

This paper introduces an agent-based hyper-heuristic framework that uses a "voting" system to dynamically select the best multi-objective evolutionary algorithm (MOEA) for a given problem during the optimization process. This aims to reduce the manual effort of choosing and tuning MOEAs, potentially leading to better solutions by combining the strengths of different algorithms.

What Problem Does This Paper Address?

Many real-world problems involve optimizing multiple, often conflicting, objectives simultaneously. Multi-Objective Evolutionary Algorithms (MOEAs) are powerful tools for tackling these challenges, but selecting the right MOEA and its configuration for a specific problem is a difficult and time-consuming task. This is partly due to the "No Free Lunch" theorem, which suggests no single algorithm excels at all problems. Hyper-heuristics, which are "heuristics to choose heuristics," offer a way to automate this selection process. However, existing hyper-heuristics often require offline training or tuning. This paper addresses the need for an online hyper-heuristic that can adapt its MOEA selection strategy in real-time as the optimization progresses, without prior knowledge of the problem.

Methods

The proposed approach is an agent-based system with three types of agents:

  • MOEA Agents (Candidates): These are the individual MOEAs (e.g., NSGA-II, SPEA2) that compete to solve the multi-objective optimization problem (MOP).
  • Voter Agents: These agents evaluate the solutions generated by the MOEA agents using various quality indicators. Each voter agent might use a different criterion, providing diverse perspectives on performance.
  • HH Agent (Hyper-Heuristic Agent): This central agent orchestrates the election process. It collects the rankings from the Voter Agents and uses a social choice voting method (like Copeland, Borda, or Kemeny-Young) to determine which MOEA agent is the "winner."

The workflow is as follows:

  1. MOEA agents generate offspring solutions.
  2. Voter agents evaluate these solutions and rank the MOEA agents based on their respective criteria.
  3. The HH agent aggregates these rankings to declare a winner.
  4. The winning MOEA agent receives a larger portion of the population to work with in the next generation, while others get a smaller share. This dynamic allocation aims to leverage the strengths of the currently best-performing MOEA.

The system initially splits the population uniformly and only begins the voting process after a certain number of generations to allow MOEA agents to establish initial performance.

Datasets

The paper mentions evaluating their approach on:

  • WFG continuous optimization benchmark: This is a standard benchmark suite for testing multi-objective optimization algorithms.
  • Multi-objective Travel Salesperson Problem (moTSP): This is a discrete optimization problem, indicating an effort to move beyond continuous domains.

The authors note that previous work used GD and IGD indicators, which require prior knowledge of the Pareto front, making them less suitable for real-world problems. Their current work aims to remove these dependencies.

Key Insights and Ideas

  • Dynamic MOEA Selection: The core idea is to treat MOEA selection as a competitive election, where algorithms "campaign" by producing solutions, and "voters" (quality indicators) decide the winner.
  • Agent-Based Architecture: Using autonomous agents for MOEAs and voters provides a flexible and modular framework for managing the selection process.
  • Social Choice Theory Integration: Applying voting methods from social choice theory offers a principled way to aggregate diverse performance evaluations into a single decision.
  • Adaptive Resource Allocation: Dynamically allocating more computational resources (population share) to the winning MOEA allows the system to adapt to the problem's characteristics as it evolves.
  • Bridging Continuous and Discrete: The move from purely continuous benchmarks (WFG) to include a discrete problem (moTSP) is a significant step towards broader applicability.

Key Results

The paper presents "partial results" and indicates that their previous work using Copeland voting and quality indicators found competitive results against other MOEAs on WFG benchmarks. More recent experiments, removing GD/IGD and testing Borda and Kemeny-Young voting methods on WFG and moTSP, showed that the Borda voting procedure was the best, achieving competitive results in 89 out of 90 tested problems.

Limitations and Future Work

Limitations: * The paper focuses on "partial results," suggesting a comprehensive evaluation is still ongoing. * The current number of MOEA candidates is relatively small (implied to be less than 10 in previous work, with a goal to increase it). * While moTSP is a discrete problem, the breadth of discrete problems tested is not fully detailed.

Future Work: * Explore more voting methods: The authors intend to investigate additional voting procedures. * Increase the number of MOEA candidates: They plan to scale up the competition to include up to 10 MOEA agents. * Expand benchmark suite: The goal is to test on a wider range of benchmarks and real-world problems. * Further refine quality indicators: Investigating new or more suitable quality indicators for voter agents is likely.

Summary updated

BibTeX
@inproceedings{carvalho2018multi,
  author = {Vinicius Renan de Carvalho and Jaime Simão Sichman},
  title = {{Multi-Agent Election-Based Hyper-Heuristics}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2018},
  doi = {10.24963/ijcai.2018/833},
}
Figure