DROPS

Document

Poster Abstract

DOI: 10.4230/LIPIcs.GD.2024.51

Evolutionary Algorithms for One-Sided Bipartite Crossing Minimisation (Poster Abstract)

Authors: Jakob Baumann, Ignaz Rutter, and Dirk Sudholt

Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

Abstract

Evolutionary algorithms (EAs) are universal solvers inspired by principles of natural evolution. In many applications, EAs produce astonishingly good solutions. To complement recent theoretical advances in the analysis of EAs on graph drawing [Baumann et al., 2024], we contribute a fundamental empirical study. We consider the so-called One-Sided Bipartite Crossing Minimisation (OBCM): given two layers of a bipartite graph and a fixed horizontal order of vertices on the first layer, the task is to order the vertices on the second layer to minimise the number of edge crossings. We empirically analyse the performance of simple EAs for OBCM and compare different mutation operators on the underlying permutation ordering problem: exchanging two elements (exchange), swapping adjacent elements (swap) and jumping an element to a new position (jump). EAs using jumps easily outperform all deterministic algorithms in terms of solution quality after a reasonable number of generations. We also design variations of the best-performing EAs to reduce the execution time for each generation. The improved EAs can obtain the same solution quality as before and run up to 100 times faster.

Cite as

Jakob Baumann, Ignaz Rutter, and Dirk Sudholt. Evolutionary Algorithms for One-Sided Bipartite Crossing Minimisation (Poster Abstract). In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 51:1-51:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{baumann_et_al:LIPIcs.GD.2024.51,
  author =	{Baumann, Jakob and Rutter, Ignaz and Sudholt, Dirk},
  title =	{{Evolutionary Algorithms for One-Sided Bipartite Crossing Minimisation}},
  booktitle =	{32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)},
  pages =	{51:1--51:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-343-0},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{320},
  editor =	{Felsner, Stefan and Klein, Karsten},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.51},
  URN =		{urn:nbn:de:0030-drops-213353},
  doi =		{10.4230/LIPIcs.GD.2024.51},
  annote =	{Keywords: Mutation Operator, Layered Graphs, Crossing Minimisation}
}

Search Results

Documents authored by Baumann, Jakob

Evolutionary Algorithms for One-Sided Bipartite Crossing Minimisation (Poster Abstract)

Abstract

Cite as

Thanks for your feedback!

Could not send message