Evolving Weighted and Directed Graphs with Constrained Properties
Sydney Leither, Vincent R. Ragusa, Emily L. Dolson · Proceedings of the Genetic and Evolutionary Computation Conference Companion · 2024
Research across a range of fields sometimes requires graphs with specific properties or structures for purposes such as hypothesis testing and simulation. Random graph models are the current state-of-the-art approach; they generate distributions of graphs with certain properties. Unfortunately, random graph models can only generate specific classes of graphs. We present a genetic algorithm that evolves weighted and directed graphs with arbitrary properties specified by the user. Using NSGA-II, we evolve a population of graphs by treating each of the specified graph properties as an objective to optimize. We propose a modified version of the diversity maintenance component of NSGA-II and several graph-targeted mutation and crossover operators. Our algorithm successfully evolves graphs with multiple interacting properties while maintaining diversity in the properties not under selection. This tool allows for highly customizable and fine-grained generation of graphs with arbitrary properties.