- author = "Alberto Bartoli and Andrea {De Lorenzo} and Eric Medvet and Fabiano Tarlao",
- title = "Playing Regex Golf with Genetic Programming",
- booktitle = "GECCO '14: Proceeding of the sixteenth annual conference on genetic and evolutionary computation conference",
- year = "2014",
- editor = "Christian Igel and Dirk V. Arnold and Christian Gagne and Elena Popovici and Anne Auger and Jaume Bacardit and Dimo Brockhoff and Stefano Cagnoni and Kalyanmoy Deb and Benjamin Doerr and James Foster and Tobias Glasmachers and Emma Hart and Malcolm I. Heywood and Hitoshi Iba and Christian Jacob and Thomas Jansen and Yaochu Jin and Marouane Kessentini and Joshua D. Knowles and William B. Langdon and Pedro Larranaga and Sean Luke and Gabriel Luque and John A. W. McCall and Marco A. {Montes de Oca} and Alison Motsinger-Reif and Yew Soon Ong and Michael Palmer and Konstantinos E. Parsopoulos and Guenther Raidl and Sebastian Risi and Guenther Ruhe and Tom Schaul and Thomas Schmickl and Bernhard Sendhoff and Kenneth O. Stanley and Thomas Stuetzle and Dirk Thierens and Julian Togelius and Carsten Witt and Christine Zarges",
- pages = "1063--1070",
- organisation = "SIGEVO",
- address = "Vancouver, BC, Canada",
- publisher = "ACM",
- publisher_address = "New York, NY, USA",
- keywords = "genetic algorithms, genetic programming",
- month = "12-16 " # jul,
- isbn13 = "978-1-4503-2662-9",
-
URL = "
http://machinelearning.inginf.units.it/publications/international-conference-publications/playingregexgolfwithgeneticprogramming",
-
URL = "http://doi.acm.org/10.1145/2576768.2598333",
-
DOI = "
doi:10.1145/2576768.2598333",
-
abstract = "Regex golf has recently emerged as a specific kind of
code golf, i.e., unstructured and informal programming
competitions aimed at writing the shortest code solving
a particular problem. A problem in regex golf consists
in writing the shortest regular expression which
matches all the strings in a given list and does not
match any of the strings in another given list. The
regular expression is expected to follow the syntax of
a specified programming language, e.g., Javascript or
PHP.
In this paper, we propose a regex golf player internally based on Genetic Programming. We generate a population of candidate regular expressions represented as trees and evolve such population based on a multi-objective fitness which minimises the errors and the length of the regular expression.
We assess experimentally our player on a popular regex golf challenge consisting of 16 problems and compare our results against those of a recently proposed algorithm---the only one we are aware of. Our player obtains scores which improve over the baseline and are highly competitive also with respect to human players. The time for generating a solution is usually in the order of tens minutes, which is arguably comparable to the time required by human players.",
- notes = "Also known as \cite{2598333} GECCO-2014 A joint meeting of the twenty third international conference on genetic algorithms (ICGA-2014) and the nineteenth annual genetic programming conference (GP-2014)",
