Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/84195

Finding edge-disjoint paths with artificial ant colonies
Blesa Aguilera, Maria Josep; Blum, Christian
Universitat Politècnica de Catalunya. Departament de Llenguatges i Sistemes Informàtics; Universitat Politècnica de Catalunya. ALBCOM - Algorismia, Bioinformàtica , Complexitat i Mètodes Formals
One of the basic operations in communication networks consists in establishing routes for connection requests between physically separated network nodes. In many situations, either due to technical constraints or to quality-of-service and survivability requirements, it is required that no two routes interfere with each other. These requirements apply in particular to routing and admission control in large-scale, high-speed and optical networks. The same requirements also arise in a multitude of other applications such as real-time communications, vlsi design, scheduling, bin packing, and load balancing. This problem can be modeled as a combinatorial optimization problem as follows. Given a graph G representing a network topology, and a collection T = f(s1; t1) : : : (sk; tk)g of pairs of vertices in G representing connection request, the maximum edge-disjoint paths problem is an NP-hard problem that consists in determining the maximum number of pairs in T that can be routed in G by mutually edge-disjoint si - ti paths. We propose an ant colony optimization (aco) algorithm to solve this problem. aco algo- rithms are approximate algorithms that are inspired by the foraging behavior of real ants. The decentralized nature of these algorithms makes them suitable for the application to problems arising in large-scale environments. First, we propose a basic version of our algorithm in order to outline its main features. In a subsequent step we propose several extensions of the basic algorithm and we conduct an extensive parameter tuning in order to show the usefulness of those extensions. In comparison to a multi-start greedy approach, our algorithm generates in general solutions of higher quality in a shorter amount of time. In particular the run-time behaviour of our algorithm is one of its important advantages.
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica
Ant colony optimization
Maximum edge-disjoint paths problem
info:eu-repo/semantics/publishedVersion
Informe
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Hernández Pibernat, Hugo; Baumgartner, Tobias; Blesa Aguilera, Maria Josep; Blum, Christian; Kröller, Alexander; Fekete, Sandor P.
Blum, Christian; Blesa Aguilera, Maria Josep; Calvo, Borja
Blum, Christian; Yábar Vallès, Mateu; Blesa Aguilera, Maria Josep