Competition between Dandelion and Prüfer encoded genetic algorithms for solving the clustered minimum routing tree problem
Competition between Dandelion and Prüfer encoded genetic algorithms for solving the clustered minimum routing tree problem
Cosmin Sabo, Petrică C. Pop, Bogdan Teglaș, Adrian Petrovan
Abstract. The Clustered Minimum Routing Tree Problem (CluMRTP) is a challenging extension of the classical Minimum Routing Tree Problem in which the vertices of a graph are partitioned into clusters, and the objective is to find a minimum-cost routing tree such that each cluster forms a connected subgraph. This paper sets up a computational competition between two powerful tree-encoding strategies inside genetic algorithms: Dandelion-encoded and Prüfer-encoded representations. Each encoding is used to drive a hybrid genetic algorithm that combines macro-level evolution of the inter-cluster tree with local-level construction of intra-cluster connectivity. Through extensive experiments on benchmark instances, the relative strengths and weaknesses of the two encodings are analysed in terms of solution quality, convergence behaviour and robustness. The results provide concrete guidance for the choice of tree encoding when designing evolutionary algorithms for the CluMRTP and related network design problems.
Keywords: clustered minimum routing tree problem; genetic algorithms; Dandelion encoding; Prüfer encoding; combinatorial optimization
📋 Cite this publication
Cosmin Sabo, Petrică C. Pop, Bogdan Teglaș, Adrian Petrovan, "Competition between Dandelion and Prüfer encoded genetic algorithms for solving the clustered minimum routing tree problem", Carpathian Journal of Mathematics, vol. 41, no. 4, 2025, pp. 1045–1059, 2023. DOI: https://doi.org/10.37193/CJM.2025.04.13.
Reference: Carpathian Journal of Mathematics, vol. 41, no. 4, 2025, pp. 1045–1059. DOI: 10.37193/CJM.2025.04.13
Advancements in Machine Learning Algorithms for Precision Crop Yield Prediction: A Comprehensive Review with focus on European Union
Advancements in Machine Learning Algorithms for Precision Crop Yield Prediction: A Comprehensive...
TPC Net: An Efficient CNN Architecture for Tomato Plant Disease and Pest Classification
TPC Net: An Efficient CNN Architecture for Tomato Plant Disease and Pest ClassificationOvidiu...
Enhancing API Security Testing against BOLA and Authentication Vulnerabilities through an LLM-Enhanced Framework
Enhancing API Security Testing against BOLA and Authentication Vulnerabilities through an...
A new vision of social behavior on genetic algorithm performance
A new vision of social behavior on genetic algorithm performanceAndreea Tatar, Nicolae Fat, Adrian...
Evaluation of Feature Selection Methods in Estimation of Precipitation Based on Deep Learning Artificial Neural Networks
Precipitation is the most important element of the water cycle and an indispensable element of water resources management. This paper aims to model the monthly precipitation in 8 precipitation observation stations. The effects and role of different feature weights pre-processing methods (Weight by deviation, Weight by PCA, Weight by correlation, and Weight by Support Vector Machine) on artificial intelligence modeling were investigated.
A Comparison of different crossover operators in genetic algorithms for clusters shortest-path tree problem
The clustered shortest-path tree (CluSPT) problem is an extension of the classical shortest path problem, given a graph with the nodes partitioned into several mutually exclusive and collectively exhaustive clusters looks for a shortest-path spanning tree from a predefined source node to all the other nodes of the graph, with the property that every cluster should generate a connected subgraph.
A comprehensive survey on the generalized traveling salesman problem
The generalized traveling salesman problem (GTSP) is an extension of the classical traveling salesman
problem (TSP), and it is among the most researched combinatorial optimization problems due to its theoretical properties, complexity aspects, and real-life applications in various areas: location-routing problems, material flow design problem, distribution of medical supplies, urban waste collection management, airport selection and routing the courier airplanes, image retrieval and ranking, digital garment manufacturing, etc.
A hybrid based genetic algorithm for solving the clustered generalized traveling salesman problem
We study the clustered generalized traveling salesman problem (CGTSP), which is an extension of the generalized traveling salesman problem (GTSP), which in turn generalizes the well-known traveling salesman problem (TSP).
0 Comments