文章基本信息

标题：Generating Local Search Neighborhood with Synthesized Logic Programs
本地全文：下载
作者：Mateusz Ślażyński ; Salvador Abreu ; Grzegorz J. Nalepa 等
期刊名称：Electronic Proceedings in Theoretical Computer Science
电子版ISSN：2075-2180
出版年度：2019
卷号：306
页码：168-181
DOI：10.4204/EPTCS.306.22
语种：English
出版社：Open Publishing Association
摘要：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.