Competition between Dandelion and Prufer encoded genetic algorithms for solving the clustered minimum routing tree problem

Abstract.

This study introduces a comparative evaluation of genetic algorithms using Prüfer and Dandelion encodings to tackle the Clustered Minimum Routing Tree (CluMRT) problem. This problem generalizes the traditional Minimum Routing Tree (MRT) problem by considering a graph where vertices are organized into predefined clusters. It aims to identify a minimum-cost routing tree while ensuring that each cluster remains connected as a subgraph. The proposed solution employs a two-level approach: a macro-level genetic algorithm (GA) framework using Dandelion encoding to generate cluster-spanning trees and micro-level algorithms designed to construct feasible solutions for the CluMRT problem based on these trees. Computational experiments conducted on a range of benchmark instances from existing literature demonstrate the strength of this methodology. Notably, the Dandelion-encoded GA consistently outperformed both the Prüfer-encoded GA and the current leading algorithms across nearly all test cases. These conclusions are further supported by statistical analyses, affirming the superior performance of the Dandelion-based approach.