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

Stone, Christopher; Hart, Emma; Paechter, Ben

Abstract

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.

Citation

Stone, C., Hart, E., & Paechter, B. (2018). 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). https://doi.org/10.1007/978-3-319-77538-8_40

• Conference Name: 21st International Conference, EvoApplications 2018
• Conference Location: Parma, Italy
• Start Date: Apr 4, 2018
• End Date: Apr 6, 2018
• Acceptance Date: Jan 3, 2018
• Online Publication Date: Mar 8, 2018
• Publication Date: 2018
• Deposit Date: Aug 20, 2018
• Electronic ISSN: 1611-3349
• Volume: 10784
• Pages: 578-593
• Series Title: Lecture Notes in Computer Science
• Series ISSN: 0302-9743
• Book Title: Applications of Evolutionary Computation
• ISBN: 9783319775371; 9783319775388
• DOI: https://doi.org/10.1007/978-3-319-77538-8_40
• Keywords: heuristics, grammatical evolution, combinatorial optimisation
• Public URL: http://researchrepository.napier.ac.uk/Output/1281618