More Web Proxy on the site http://driver.im/

research-article

Open access

A Study of Ant-Based Pheromone Spaces for Generation Perturbative Hyper-Heuristics

Authors:

Nelishia PillayAuthors Info & Claims

GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

Pages 84 - 92

https://doi.org/10.1145/3583131.3590367

Published: 12 July 2023 Publication History

Abstract

Recent work has shown the potential of ant algorithms for generation constructive hyper-heuristics. This paper extends the previous research by presenting a novel ant algorithm that is used to drive the heuristic search for a generation perturbative hyper-heuristic, the other type of generation hyper-heuristic. The ant-based generation perturbative hyper-heuristic is presented and compared against existing heuristics in two combinatorial domains, the movie scene scheduling and capacitated vehicle routing problems, to assess the heuristic generation efficacy. The comparison is further extended by assessing the effect of different pheromone maps (1D, 2D and 3D) on the ant-based hyper-heuristic, an important factor in the previous study. The results showed that, in both domains, the hyper-heuristic was able to generate perturbative heuristics that were competitive or better than the existing heuristics. Furthermore, the type of pheromone map was relevant to the hyper-heuristic performance as the 3D map performed best for the first domain and the 1D map for the second, confirming the trend shown in previous research, as well as the validity of ant algorithms for generation perturbative hyper-heuristics.

Supplementary Material

PDF File (p84-singh-suppl.pdf)

Supplemental material.

Download
441.23 KB

References

[1]

Mohamed Bader-El-Den and Riccardo Poli. 2008. Generating SAT Local-Search Heuristics Using a GP Hyper-Heuristic Framework. In Artificial Evolution, Nicolas Monmarché, El-Ghazali Talbi, Pierre Collet, Marc Schoenauer, and Evelyne Lutton (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 37--49.

[2]

Edmund Burke, Graham Kendall, Jim Newall, Emma Hart, Peter Ross, and Sonia Schulenburg. 2003. Hyper-Heuristics: An Emerging Direction in Modern Search Technology. Springer US, Boston, MA. 457--474 pages.

[3]

G. Clarke and J. W. Wright. 1964. Scheduling of vehicles from a central depot to a number of delivery points. Operations Research 12, 4 (1964), 568--581.

Digital Library

[4]

M. Dorigo. 1992. Optimization, Learning and Natural Algorithms. Ph. D. Dissertation. Politecnico di Milano.

[5]

Marco Dorigo and Gianni Di Caro. 1999. Ant colony optimization: A new meta-heuristic. IEEE. 2 (02 1999), 1477 Vol. 2.

[6]

Milton Friedman. 1937. The Use of Ranks to Avoid the Assumption of Normality Implicit in the Analysis of Variance. J. Amer. Statist. Assoc. 32, 200 (1937), 675--701.

[7]

Alex S. Fukunaga. 2008. Automated Discovery of Local Search Heuristics for Satisfiability Testing. Evolutionary Computation 16, 1 (2008), 31--61.

Digital Library

[8]

L. M. Gambardella and Marco Dorigo. 1996. Solving symmetric and asymmetric TSPs by ant colonies. In Proceedings of IEEE International Conference on Evolutionary Computation. IEEE, Nagoya, Japan, 622--627.

[9]

M. Gendreau, G. Laporte, and J.-Y. Potvin. 2001. Metaheuristics for the Capacitated VRP. Society for Industrial and Applied Mathematics, USA, 129--154.

[10]

H. B. Mann and D. R. Whitney. 1947. On a Test of Whether one of Two Random Variables is Stochastically Larger than the Other. Ann. Math. Statist. 18, 1 (03 1947), 50--60.

[11]

Supplementary Material. 2022. Ant-Based Generation Perturbative Hyper-Heuristics Supplement Material. https://drive.google.com/file/d/1xsSOWXv4n5jEKkz6LV6IACwOkHdwQIFg/view?usp=share_link

[12]

N. Pillay and R. Qu. 2018. Hyper-Heuristics: Theory and Applications. Springer, Pretoria, South Africa.

[13]

Nelishia Pillay and Rong Qu. 2021. Assessing hyper-heuristic performance. Journal of the Operational Research Society 72, 11 (2021), 2503--2516.

[14]

Nasser R. Sabar, Masri Ayob, Graham Kendall, and Rong Qu. 2013. Grammatical Evolution Hyper-Heuristic for Combinatorial Optimization Problems. IEEE Transactions on Evolutionary Computation 17, 6 (2013), 840--861.

Digital Library

[15]

Emilio Singh and Nelishia Pillay. 2021. Ant-Based Hyper-Heuristics for the Movie Scene Scheduling Problem. In Artificial Intelligence and Soft Computing: 20th International Conference, ICAISC 2021, Virtual Event, June 21--23, 2021, Proceedings, Part II. Springer-Verlag, Berlin, Heidelberg, 342--353.

Digital Library

[16]

Emilio Singh and Nelishia Pillay. 2022. A study of ant-based pheromone spaces for generation constructive hyper-heuristics. Swarm and Evolutionary Computation 72 (2022), 101095.

[17]

I Xavier and E Queiroga. 2014. CVRPLIB. http://vrp.atd-lab.inf.puc-rio.br/index.php/en/

Cited By

Klar RAndersson AFredriksson AAngelakis V(2024)Container Relocation and Retrieval Tradeoffs Minimizing Schedule Deviations and RelocationsIEEE Open Journal of Intelligent Transportation Systems10.1109/OJITS.2024.34131975(360-379)Online publication date: 2024
https://doi.org/10.1109/OJITS.2024.3413197
Alkhamis AHosny M(2023)A Multi-Objective Simulated Annealing Local Search Algorithm in Memetic CENSGA: Application to Vaccination Allocation for InfluenzaSustainability10.3390/su15211534715:21(15347)Online publication date: 27-Oct-2023
https://doi.org/10.3390/su152115347

Index Terms

A Study of Ant-Based Pheromone Spaces for Generation Perturbative Hyper-Heuristics
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

Ant-Based Generation Constructive Hyper-heuristics for the Movie Scene Scheduling Problem
Theory and Practice of Natural Computing
Abstract
The task of generation constructive hyper-heuristics concerns itself with generating new heuristics for problem domains via some kind of mechanism that combines low-level heuristic components into new heuristics. The movie scene scheduling problem ...
Ant based hyper heuristics with space reduction: a case study of the p-median problem
PPSN'10: Proceedings of the 11th international conference on Parallel problem solving from nature: Part I

Recent years have witnessed great success of ant based hyper heuristics applying to real world applications. Ant based hyper heuristics intend to explore the heuristic space by traversing the fully connected graph induced by low level heuristics (LLHs). ...
A comparative study of hyper-heuristics for solving the school timetabling problem
SAICSIT '13: Proceedings of the South African Institute for Computer Scientists and Information Technologists Conference

Hyper-heuristics have proven to be an effective means of obtaining generalized solutions to optimization problems. One such domain in which they have been a success is educational timetabling. However, all the research in this area has focused on ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

GECCO '23: Proceedings of the Genetic and Evolutionary Computation Conference

July 2023

1667 pages

ISBN:9798400701191

DOI:10.1145/3583131

Chair:
Sara Silva,
Program Chair:
Luís Paquete

Copyright © 2023 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Sponsors

SIGEVO: ACM Special Interest Group on Genetic and Evolutionary Computation

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 12 July 2023

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

GECCO '23

Sponsor:

SIGEVO

GECCO '23: Genetic and Evolutionary Computation Conference

July 15 - 19, 2023

Lisbon, Portugal

Acceptance Rates

Overall Acceptance Rate 1,669 of 4,410 submissions, 38%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

2
Total Citations
View Citations
181
Total Downloads

Downloads (Last 12 months)126
Downloads (Last 6 weeks)16

Reflects downloads up to 04 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Klar RAndersson AFredriksson AAngelakis V(2024)Container Relocation and Retrieval Tradeoffs Minimizing Schedule Deviations and RelocationsIEEE Open Journal of Intelligent Transportation Systems10.1109/OJITS.2024.34131975(360-379)Online publication date: 2024
https://doi.org/10.1109/OJITS.2024.3413197
Alkhamis AHosny M(2023)A Multi-Objective Simulated Annealing Local Search Algorithm in Memetic CENSGA: Application to Vaccination Allocation for InfluenzaSustainability10.3390/su15211534715:21(15347)Online publication date: 27-Oct-2023
https://doi.org/10.3390/su152115347

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Table of Contents