@inproceedings{04aa665061c84ab8bf6da9a5f0baccd5,
title = "Probabilistic Graph Programs for Randomised and Evolutionary Algorithms",
abstract = "We extend the graph programming language GP 2 with probabilistic constructs: (1) choosing rules according to user-defined probabilities and (2) choosing rule matches uniformly at random. We demonstrate these features with graph programs for randomised and evolutionary algorithms. First, we implement Karger{\textquoteright}s minimum cut algorithm, which contracts randomly selected edges; the program finds a minimum cut with high probability. Second, we generate random graphs according to the G(n, p) model. Third, we apply probabilistic graph programming to evolutionary algorithms working on graphs; we benchmark odd-parity digital circuit problems and show that our approach significantly outperforms the established approach of Cartesian Genetic Programming.",
author = "Timothy Atkinson and Detlef Plump and Susan Stepney",
note = "This is an author-produced version of the published paper. Uploaded in accordance with the publisher{\textquoteright}s self-archiving policy. Further copying may not be permitted; contact the publisher for details",
year = "2018",
month = jun,
day = "19",
doi = "10.1007/978-3-319-92991-0_5",
language = "English",
isbn = "978-3-319-92990-3",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer",
pages = "63--78",
editor = "Jens Weber and Leen Lambers",
booktitle = "Graph Transformation - 11th International Conference, ICGT 2018, Held as Part of STAF 2018, Proceedings",
address = "Germany",
}