Sequence-Based Selection Hyper-Heuristic Model via MAP-Elites

Melissa Sanchez

doi:10.1109/ACCESS.2021.3106815

Sequence-Based Selection Hyper-Heuristic Model via MAP-Elites

2021-01-01

6

OA

AI

José Carlos Ortíz-Bayliss

I

Iván Amaya *

DOI：10.1109/ACCESS.2021.3106815

原文链接

查看原文

摘要

En 中文

Although the number of solutions in combinatorial optimization problems (COPs) is finite, some problems grow exponentially and render exact approaches unfeasible. So, approximate methods, such as heuristics, are customary. Each heuristic usually specializes in specific kinds of problems. Hence, other approaches seek to merge their strengths. One of them is selection hyper-heuristics. However, they usually provide scarce information about their sensitivity. Illumination algorithms may fix this issue since they focus on exploration rather than exploitation while preserving the best solutions under different criteria. Still, literature falls short when merging both approaches, representing a knowledge gap. This work tests the feasibility of using an illumination algorithm, MAP-Elites (ME), for tuning a sequence-based selection hyper-heuristic model for Balanced Partition problems. We choose ME since other researchers have successfully applied it to a different COP. So, we may achieve a hyper-heuristic that represents the best combination of heuristics while simultaneously gaining intel on the performance of diverse alternatives. Our approach operates by creating a multi-dimensional map, where each design variable represents the application of a heuristic. Afterward, ME generates mutated sequences and tests them to determine if they represent a better-performing solution. We consider 1500 instances that include easy and hard instances, analyzed under different scenarios to test our approach. We also include limit instances that are neither easy nor hard. Our resulting data support the proposed approach, as it performs toe-to-toe with a synthetic oracle and may even outperform it. This represents an outstanding result, since a brute-force approach is needed to achieve such an oracle. So, merging ME and hyper-heuristics is a path worth pursuing. We also present how each parameter affects the model performance and identify the critical and virtually irrelevant ones. This serves as the groundwork for future works that focus on exploiting the most relevant parameters.

Keyword:

Optimization

Lighting

Portfolios

Merging

Training

Task analysis

Sensitivity

MAP-elites

balanced partition

hyper-heuristic

combinatorial optimization

heuristic

Sequence-Based Selection Hyper-Heuristic Model via MAP-Elites

摘要

AI总结

期刊

机构

引用论文