DISEÑO DE UN ALGORITMO INMUNE ARTIFICIAL PARA RESOVER TRAVELING TOURNEMENT PROBLEM

Abstract

La motivación de esta tesis es evaluar la aplicabilidad de los sistemas inmunes artificiales para resolver problemas combinatoriales, especialmente en el ámbito de la planificación deportiva. Ademas se desea estudiar las características propias del diseo de éstos, para contribuir al estudio de la capacidad de los sistemas inmunes artificiales para resolver problemas de optimización combinatoriales. Los Sistemas Inmunes Artificiales son un nuevo paradigma en inteligencia artificial, se inspiran en el conjunto de mecanismos que conforman el sistema inmune natural, los cuales permiten a los organismos vivos defenderse de elementos extraos que ponen en peligro su normal funcionamiento. Los sistemas inmunes artificiales han demostrado sus capacidades para ser aplicados en la resolución de diferentes tipos de problemas computacionales, entre ellos los de optimización. Traveling Tournament Problem (TTP) y Relaxed Traveling Tournament Problem (RTTP) son dos problemas de planificación deportiva que abstraen características comunes en la planificación de torneos. Ambos combinan problemas de factibilidad y optimización, poseen un gran espacio de búsqueda y son conocidos por su dificultad de resolución. En esta tesis se estudian los sistemas inmunes artificiales en el contexto de la resolución de los problemas de optimización combinatoria! descritos. Se realiza una breve revisión de los sistemas inmunes artificiales y su aplicaciones, haciendo especial énfasis en los problemas de optimización. Se presenta ademas, Traveling Tournament Problem y Relaxed Traveling Tournament Problem y sus respectivos estados del arte. Se proponen dos sistemas inmunes artificiales, uno para resolver TTP y otro para RTTP. Finalmente, se evalúan los algoritmos propuestos utilizando diferentes instancias de los problemas a resolver.