A Genetic Algorithm for Finding Regular Graphs with Minimum Average Shortest Path Length

The problem of finding a simple regular graph with the specified order and degree that minimizes the average shortest path length has a long history in graph theory. Recently this problem has attracted a great deal of attention in relation to the design of computer networks in data centers. In this paper, we propose a genetic algorithm for finding an approximate solution to this problem. Because the search space is the set of all simple regular graphs with the specified order and degree, conventional genetic algorithms cannot be directly applied. We propose in this paper new crossover and mutation operators that guarantee the simplicity and regularity of graphs. We also evaluate the effectiveness of the proposed method experimentally.