A Methodology to Determine the Subset of Heuristics for Hyperheuristics through Metaearning for Solving Graph Coloring and Capacitated Vehicle Routing Problems

Complexity 2021:1-22 (2021)
  Copy   BIBTEX

Abstract

In this work, we focus on the problem of selecting low-level heuristics in a hyperheuristic approach with offline learning, for the solution of instances of different problem domains. The objective is to improve the performance of the offline hyperheuristic approach, identifying equivalence classes in a set of instances of different problems and selecting the best performing heuristics in each of them. A methodology is proposed as the first step of a set of instances of all problems, and the generic characteristics of each instance and the performance of the heuristics in each one of them are considered to define the vectors of characteristics and make a grouping of classes. Metalearning with statistical tests is used to select the heuristics for each class. Finally, we used the Naive Bayes to test the set instances with k-fold cross-validation, and we compared all results statistically with the best-known values. In this research, the methodology was tested by applying it to the problems of capacitated vehicle routing and graph coloring. The experimental results show that the proposed methodology can improve the performance of the offline hyperheuristic approach, correctly identifying the classes of instances and applying the appropriate heuristics in each case. This is based on the statistical comparison of the results obtained with those of the state of the art of each instance.

Links

PhilArchive



    Upload a copy of this work     Papers currently archived: 90,221

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

Similar books and articles

Heuristics and Meta-heuristics in Scientific Judgement.Spencer Phillips Hey - 2016 - British Journal for the Philosophy of Science 67 (2):471-495.
Heuristics refound.William C. Wimsatt - 2000 - Behavioral and Brain Sciences 23 (5):766-767.
Effective coloration.Dwight R. Bean - 1976 - Journal of Symbolic Logic 41 (2):469-480.
Feasible Graphs and Colorings.Douglas Cenzer & Jeffrey Remmel - 1995 - Mathematical Logic Quarterly 41 (3):327-352.
Heuristics in technoscientific thinking.Michael E. Gorman - 2000 - Behavioral and Brain Sciences 23 (5):752-752.

Analytics

Added to PP
2021-04-27

Downloads
8 (#1,133,785)

6 months
7 (#174,572)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations