Desarrollo y Evaluación de Algoritmos Genéticos Multiobjetivo. Aplicación al problema del viajante

Abstract

[ES] En este TFG se plantea resolver el problema del viajante con m ultiples objetivos a optimizar, como extensi on del problema b asico. Al respecto, se analizar an las propiedades del mismo, as como las referentes a los problemas multiobjetivo en general. Tras ello, se desarrollar a un m etodo metaheur stico que permita obtener soluciones factibles y optimizadas. Para este cometido, se prev en estudiar y aplicar diferentes aproximaciones de algoritmos gen eticos multiobjetivo, analizando y comentando los rasgos generales correspondientes, sus ventajas e inconvenientes. Finalmente, se implementar an los algoritmos analizados anteriormente, sobre los que aplicar an diversas m etricas de evaluaci on a n de comparar los diferentes resultados obtenidos. Con ello, se podr an determinar las variantes de algoritmos gen eticos multiobjetivo m as e caces para resolver adecuadamente el problema del viajante con m ultiples objetivos.

[CA] En aquest TFG es planteja resoldre el problema del viatger amb diversos objetius a optimitzar, com extensi o del problema b asic. Al respecte, s'analitzaran les propietats del mateix, aix com les referents als problemes multiobjectiu en general. Despr es, es desenvolupar a un m etode metaheur stic que permetr a obtindre solucions factibles i optimitzades. Per aconseguir-ho, es preveu estudiar i aplicar diferents aproximacions d'algorismes gen etics multiobjectiu, analitzant y comentant les caracter stiques generals corresponents, els seus avantatges e inconvenients. Finalment, s'implementaran els algorismes analitzats anteriorment, sobre els que s'aplicaran diverses m etriques d'evaluaci o a de comparar els diferents resultats obtinguts. Amb aix o, es podran determinar les variants d'algorismes gen etics multiobjectiu m es efectives per resoldre de forma satisfactoria el problema del viatger amb m ultiples objectius.

[EN] In this project it is proposed to solve the traveler salesman problem with multiple objectives to be optimized, as an extension of the basic problem. In this regard, the properties of the same will be analyzed, as well referring to the multiobjective problems in general. After that, a metaheuristic method will be developed to obtain feasible and optimized solutions. For this purpose, it is planned to study and apply di erent approaches of multiobjective genetic algorithms, analyzing and commenting their general features, advantages and disadvantages. Finally, the algorithms analyzed above will be implemented, on which various evaluation metrics will be applied in order to compare the di erent results obtained. With this, the most e ective variants of multiobjective genetic algorithms can be determined to adequately solve the traveler salesman problem with multiple objectives.