Please use this identifier to cite or link to this item:

http://hdl.handle.net/10609/81834
Title: Camí més curt utilitzant intel·ligència d'eixam
Author: Gelabert Marí, Llorenç
Director: Jiménez García, Brian
Tutor: Marco Galindo, María Jesús
Others: Universitat Oberta de Catalunya
Keywords: swarm intelligence
decentralized system
algorithms
Issue Date: 30-Jun-2018
Publisher: Universitat Oberta de Catalunya
Abstract: The final objective of this Master's Final Project is to obtain an algorithm, based on a graph and two nodes, origin and destination, which can find a route with a minimum weight that connects them. To achieve this, it will be necessary to test multiple configurations for the different input parameters of the new implemented algorithm. Thus, a good combination between a good definition and implementation of the algorithm and the configuration used will lead us to successfully complete the project. We will also need to generate, or obtain from other projects, the definition of one or more graphs on which to apply the algorithm. Because our algorithm is not deterministic, but based on probabilities, it is not always expected to get the best, least weighted route, as a deterministic algorithm like Dijkstra's algorithm would do. Our algorithm has some advantages over these algorithms, and it is adaptability or the capacity to rebuild a new best route in changing environments without having to start the path calculation from the beginning. A set of successful configurations has been achieved. Their achieved paths are around 10% above the value of the best route. Since our algorithm can be applied to any type of graph, it is very difficult to get a configuration that always works. Some configurations have a good behavior with graphs with a large number of edges, and others with graphs with many cycles.
Language: Catalan
URI: http://hdl.handle.net/10609/81834
Appears in Collections:Bachelor thesis, research projects, etc.

Share:
Export:
Files in This Item:
File Description SizeFormat 
lgelabertmTFM0618memòria.pdfMemòria del TFM657.75 kBAdobe PDFView/Open

This item is licensed under a Creative Commons License Creative Commons