Red de la trayectoria de búsqueda de las metaheurísticas

Abstract

En este Trabajo de Fin de Máster se habla del estudio que se ha realizado de las Redes de las Trayectorias de Búsqueda aplicado a algoritmos que resuelven problemas de espacio continuo y a algoritmos que resuelven problemas de espacios discretos. El propósito de las Redes de las Trayectorias de Búsqueda es poder analizar y comparar como los algoritmos se comportan, viendo sus tendencias, su exploración y explotación del espacio de búsqueda. Se han implementado tres algoritmos que resuelven cinco problemas en el espacio continuo. Los algoritmos implementados han sido el Particle Swarm Optimization, Diferential Evolution y Iterated Local Search, que usa el algoritmo Limited-BroydenFletcher-Goldfarb-Shanno en el paso de búsqueda local. Los problemas que resuelven, en dos dimensiones, son las funciones a minimizar llamadas Michalewikz, Schwefel 1.2 (Quadratic), Rana, Salomon, y Schwefel. También se han implementado tres algoritmos que pueden resolver problemas combinatorios. Los algoritmos implementados han sido Ant Colony Optimization, Biased Random Key Genetic Algorithm, y Iterated Local Search. El problema que resuelven es el de la p-mediana para el caso cuando p = 6. Se usa un particionamiento del espacio de búsqueda, tanto para los problemas de espacio continuo como para los problemas combinatorios, para poder encontrar soluciones de diferentes algoritmos que se aproximan entre si y poder estudiar su comportamiento relativo uno al otro. Se ha encontrado que se puede perder mucha información debido al particionamiento.---ABSTRACT---In this Masters Thesis we will be studying the use of Search Trajectory Networks applied to algorithms that solve problems in continuous space and algorithms that solve combinatorial problems. The purpose of the Search Trajectory Network is analyzing and comparing the behaviour of algorithms, study their tendencies, their exploration and exploitation of the search space. There are three algorithms and five probems that have been implemented for continuous search spaces. The implemented algorithms are Particle Swarm Optimization, Diferential Evolution and Iterated Local Search, which uses the Limited-BroydenFletcher-Goldfarb-Shanno algorithms for the local search step. The problems that have been solved, in two dimensions, are the functions that need to be minimized called Michalewikz, Schwefel 1.2 (Quadratic), Rana, Salomon, and Schwefel. There are also threee algorithms that have been implemented for combinatorials problems. The implemented algorithms are Ant Colony Optimization, Biased Random Key Genetic Algorithm, and Iterated Local Search. The problem that has been solved is the p-median problem for p = 6. A search space partitioning is used, for continuous optimization and combinatorial optimization, to be able to find solutions of different algorithms that are close to each other and study their behaviour relative to each other. It was found that there is great information loss due to the search space partitioning.