Generating Local Search Neighborhood with Synthesized Logic Programs

Mateusz Ślażyński
(AGH University of Science and Technology)
Salvador Abreu
(University of Évora and LISP )
Grzegorz J. Nalepa
(AGH University of Science and Technology)

Local Search meta-heuristics have been proven a viable approach to solve difficult optimization problems. Their performance depends strongly on the search space landscape, as defined by a cost function and the selected neighborhood operators. In this paper we present a logic programming based framework, named Noodle, designed to generate bespoke Local Search neighborhoods tailored to specific discrete optimization problems. The proposed system consists of a domain specific language, which is inspired by logic programming, as well as a genetic programming solver, based on the grammar evolution algorithm. We complement the description with a preliminary experimental evaluation, where we synthesize efficient neighborhood operators for the traveling salesman problem, some of which reproduce well-known results.

In Bart Bogaerts, Esra Erdem, Paul Fodor, Andrea Formisano, Giovambattista Ianni, Daniela Inclezan, German Vidal, Alicia Villanueva, Marina De Vos and Fangkai Yang: Proceedings 35th International Conference on Logic Programming (Technical Communications) (ICLP 2019), Las Cruces, NM, USA, September 20-25, 2019, Electronic Proceedings in Theoretical Computer Science 306, pp. 168–181.
Published: 19th September 2019.

ArXived at: https://dx.doi.org/10.4204/EPTCS.306.22 bibtex PDF
References in reconstructed bibtex, XML and HTML format (approximated).
Comments and questions to: eptcs@eptcs.org
For website issues: webmaster@eptcs.org