Skip to content

Research at St Andrews

A combined approach for analysing heuristic algorithms

Research output: Contribution to journalArticlepeer-review

Author(s)

Jeroen Corstjens, Nguyen Dang, Benoît Depaire, An Caris, Patrick De Causmaeckers

School/Research organisations

Abstract

When developing optimisation algorithms, the focus often lies on obtaining an algorithm that is able to outperform other existing algorithms for some performance measure. It is not common practice to question the reasons for possible performance differences observed. These types of questions relate to evaluating the impact of the various heuristic parameters and often remain unanswered. In this paper, the focus is on gaining insight in the behaviour of a heuristic algorithm by investigating how the various elements operating within the algorithm correlate with performance, obtaining indications of which combinations work well and which do not, and how all these effects are influenced by the specific problem instance the algorithm is solving. We consider two approaches for analysing algorithm parameters and components—functional analysis of variance and multilevel regression analysis—and study the benefits of using both approaches jointly. We present the results of a combined methodology that is able to provide more insights than when the two approaches are used separately. The illustrative case studies in this paper analyse a large neighbourhood search algorithm applied to the vehicle routing problem with time windows and an iterated local search algorithm for the unrelated parallel machine scheduling problem with sequence-dependent setup times.
Close

Details

Original languageEnglish
Pages (from-to)591–628
Number of pages38
JournalJournal of Heuristics
Volume25
Issue number10
Early online date10 Aug 2018
DOIs
Publication statusPublished - 1 Oct 2019

    Research areas

  • Functional analysis of variance, fANOVA, Multilevel regression, Algorithm performance, Vehicle routing problem with time windows, Large neighbourhood search, Iterated local search, Unrelated parallel machine scheduling problem

Discover related content
Find related publications, people, projects and more using interactive charts.

View graph of relations

Related by author

  1. Discriminating instance generation from abstract specifications: a case study with CP and MIP

    Akgün, Ö., Dang, N., Miguel, I., Salamon, A. Z., Spracklen, P. & Stone, C., 2020, Integration of Constraint Programming, Artificial Intelligence, and Operations Research: 17th International Conference, CPAIOR 2020, Vienna, Austria, September 21–24, 2020, Proceedings. Hebrard, E. & Musliu, N. (eds.). Cham: Springer, p. 41-51 11 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 12296 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  2. Athanor: high-level local search over abstract constraint specifications in Essence

    Attieh, S., Dang, N., Jefferson, C., Miguel, I. & Nightingale, P., 10 Aug 2019, Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI-19). Kraus, S. (ed.). International Joint Conferences on Artificial Intelligence, p. 1056-1063 8 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  3. Hyper-parameter tuning for the (1+ (λ, λ)) GA

    Dang, N. & Doerr, C., 13 Jul 2019, Proceedings of the Genetic and Evolutionary Computation Conference (GECCO '19). New York: ACM, p. 889-897 9 p.

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  4. Automatic streamlining for constrained optimisation

    Spracklen, P., Dang, N., Akgun, O. & Miguel, I. J., 2019, Principles and Practice of Constraint Programming: 25th International Conference, CP 2019, Stamford, CT, USA, September 30 – October 4, 2019, Proceedings. Schiex, T. & de Givry, S. (eds.). Cham: Springer, p. 366-383 18 p. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); vol. 11802 LNCS).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

  5. Instance generation via generator instances

    Akgun, O., Dang, N., Miguel, I. J., Salamon, A. Z. & Stone, C. L., 2019, Principles and Practice of Constraint Programming: 25th International Conference, CP 2019, Stamford, CT, USA, September 30 – October 4, 2019, Proceedings. Schiex, T. & de Givry, S. (eds.). Cham: Springer, p. 3-19 (Lecture Notes in Computer Science (Programming and Software Engineering); vol. 11802).

    Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related by journal

  1. Response to 'On Method Overfitting'

    Gent, I. P., Apr 1999, In: Journal of Heuristics. 5, p. 109-111 3 p.

    Research output: Contribution to journalArticlepeer-review

  2. Heuristic Solution of Open Bin Packing Problems

    Gent, I. P., 1998, In: Journal of Heuristics. 3, p. 299-304

    Research output: Contribution to journalArticlepeer-review

ID: 258216742

Top