Title:
|
A biased random-key genetic algorithm for the capacitated minimum spanning tree problem
|
Author:
|
Ruiz Ruiz, Hector Efrain; Albareda Sambola, Maria; Fernández Aréizaga, Elena; Resende, Mauricio G. C.
|
Other authors:
|
Universitat Politècnica de Catalunya. Departament d'Estadística i Investigació Operativa; Universitat Politècnica de Catalunya. GNOM - Grup d'Optimització Numèrica i Modelització |
Abstract:
|
This paper focuses on the capacitated minimum spanning tree(CMST)problem.Given a central
processor and a set of remote terminals with specified demands for traffic that must flow between the central processor and terminals,the goal is to design a minimum cost network to carry this demand.
Potential links exist between any pair of terminals and between the central processor and the terminals.
Each potential link can be included in the design at a given cost.The CMST problem is to design a
minimum-cost network connecting the terminals with the central processor so that the flow on any arc of the network is at most Q. A biased random-keygenetic algorithm(BRKGA)is a metaheuristic for combinatorial optimization which evolves a population of random vectors that encode solutions to the combinatorial optimization problem.This paper explores several solution encodings as well as different
strategies for some steps of the algorithm and finally proposes a BRKGA heuristic for the CMST problem.
Computational experiments are presented showing the effectivenes sof the approach:Seven newbest-
known solutions are presented for the set of benchmark instances used in the experiments. |
Abstract:
|
Peer Reviewed |
Subject(s):
|
-Àrees temàtiques de la UPC::Matemàtiques i estadística::Investigació operativa -Combinatorial optimization -Heuristic -Computer algorithms -Optimization -Combinatorial optimization -Networks -Graphs -Trees -Spanning trees -Capacitated minimumspanningtree -Heuristics -Biased random-keygeneticalgorithm -Optimització combinatòria -Heurística -Algorismes genètics |
Rights:
|
|
Document type:
|
Article - Submitted version Article |
Share:
|
|