Sequence-Based Selection Hyper-Heuristic Model via MAP-Elites
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, othe...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
IEEE
2021-01-01
|
| Series: | IEEE Access |
| Subjects: | |
| Online Access: | https://ieeexplore.ieee.org/document/9520416/ |
| _version_ | 1818692674666889216 |
|---|---|
| author | Melissa Sanchez Jorge M. Cruz-Duarte Jose C. Ortiz-Bayliss Ivan Amaya |
| author_facet | Melissa Sanchez Jorge M. Cruz-Duarte Jose C. Ortiz-Bayliss Ivan Amaya |
| author_sort | Melissa Sanchez |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-12-17T13:01:33Z |
| format | Article |
| id | doaj.art-88f377b35e304fe58d452933bccb7ed1 |
| institution | Directory Open Access Journal |
| issn | 2169-3536 |
| language | English |
| last_indexed | 2024-12-17T13:01:33Z |
| publishDate | 2021-01-01 |
| publisher | IEEE |
| record_format | Article |
| series | IEEE Access |
| spelling | doaj.art-88f377b35e304fe58d452933bccb7ed12022-12-21T21:47:21ZengIEEEIEEE Access2169-35362021-01-01911650011652710.1109/ACCESS.2021.31068159520416Sequence-Based Selection Hyper-Heuristic Model via MAP-ElitesMelissa Sanchez0https://orcid.org/0000-0003-4067-2488Jorge M. Cruz-Duarte1https://orcid.org/0000-0003-4494-7864Jose C. Ortiz-Bayliss2https://orcid.org/0000-0003-3408-2166Ivan Amaya3https://orcid.org/0000-0002-8821-7137School of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Nuevo Leon, MexicoSchool of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Nuevo Leon, MexicoSchool of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Nuevo Leon, MexicoSchool of Engineering and Sciences, Tecnologico de Monterrey, Monterrey, Nuevo Leon, MexicoAlthough 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.https://ieeexplore.ieee.org/document/9520416/MAP-elitesbalanced partitionhyper-heuristiccombinatorial optimizationheuristic |
| spellingShingle | Melissa Sanchez Jorge M. Cruz-Duarte Jose C. Ortiz-Bayliss Ivan Amaya Sequence-Based Selection Hyper-Heuristic Model via MAP-Elites IEEE Access MAP-elites balanced partition hyper-heuristic combinatorial optimization heuristic |
| title | Sequence-Based Selection Hyper-Heuristic Model via MAP-Elites |
| title_full | Sequence-Based Selection Hyper-Heuristic Model via MAP-Elites |
| title_fullStr | Sequence-Based Selection Hyper-Heuristic Model via MAP-Elites |
| title_full_unstemmed | Sequence-Based Selection Hyper-Heuristic Model via MAP-Elites |
| title_short | Sequence-Based Selection Hyper-Heuristic Model via MAP-Elites |
| title_sort | sequence based selection hyper heuristic model via map elites |
| topic | MAP-elites balanced partition hyper-heuristic combinatorial optimization heuristic |
| url | https://ieeexplore.ieee.org/document/9520416/ |
| work_keys_str_mv | AT melissasanchez sequencebasedselectionhyperheuristicmodelviamapelites AT jorgemcruzduarte sequencebasedselectionhyperheuristicmodelviamapelites AT josecortizbayliss sequencebasedselectionhyperheuristicmodelviamapelites AT ivanamaya sequencebasedselectionhyperheuristicmodelviamapelites |