Research Output

Automatic Generation of Constructive Heuristics for Multiple Types of Combinatorial Optimisation Problems with Grammatical Evolution and Geometric Graphs

  In many industrial problem domains, when faced with a combinatorial optimisation problem, a “good enough, quick enough” solution to a problem is often required. Simple heuristics often suffice in this case. However, for many domains, a simple heuristic may not be available, and designing one can require considerable expertise. Noting that a wide variety of problems can be represented as graphs, we describe a system for the automatic generation of constructive heuristics in the form of Python programs by mean of grammatical evolution. The system can be applied seamlessly to different graph-based problem domains, only requiring modification of the fitness function. We demonstrate its effectiveness by generating heuristics for the Travelling Salesman and Multi-Dimensional Knapsack problems. The system is shown to be better or comparable to human-designed heuristics in each domain. The generated heuristics can be used ‘out-of-the-box’ to provide a solution, or to augment existing hyper-heuristic algorithms with new low-level heuristics.

  • Date:

    08 March 2018

  • Publication Status:

    Published

  • Publisher

    Springer International Publishing

  • DOI:

    10.1007/978-3-319-77538-8_40

  • Library of Congress:

    QA75 Electronic computers. Computer science

  • Dewey Decimal Classification:

    005 Computer programming, programs & data

  • Funders:

    Edinburgh Napier Funded

Citation

Stone, C., Hart, E., & Paechter, B. (2017). Automatic Generation of Constructive Heuristics for Multiple Types of Combinatorial Optimisation Problems with Grammatical Evolution and Geometric Graphs. In Applications of Evolutionary Computation, 578-593

Authors

Keywords

heuristics, grammatical evolution, combinatorial optimisation

Monthly Views: