Application of Genetic Algorithms for the Optimization of Combinatorial Problems

Abstract

[EN] Genetic algorithms (GA) are a good technique for obtaining near-optimal solutions to problems with no known strategy, saving computational power. However, without the adequate configuration of parameters, a GA will not operate as efficiently as it should. An incorrect parameterization can avoid the algorithm to find good solutions. In this project we have designed, implemented and evaluated a GA and studied its parameterization for solving a combinatorial problem, specifically the Travelling Salesman Problem. We will, given a problem configuration, present the best GA parameterization; the one that obtains solutions with better quality while consuming less computational power.

[ES] Los algoritmos genéticos (AG) son una buena técnica para obtener soluciones casi óptimas para problemas sin una estrategia conocida, ahorrando potencia de cálculo. Sin embargo, sin la configuración adecuada de los parámetros, un AG no funcionará tan eficientemente como debería. Una parametrización incorrecta puede evitar que el algoritmo encuentre buenas soluciones. En este proyecto hemos diseñado, implementado y evaluado un AG y estudiado su parametrización para resolver un problema combinatorio, específicamente el Problema del Viajante de Comercio. Dada una configuración de problema, presentaremos la mejor parametrización del AG; es decir, la que obtiene soluciones de mejor calidad y consume menos potencia de cálculo.

[CA] Els algoritmes genètics (AG) són una bona tècnica per a obtindre solucions quasi òptimes per a problemes sense una estratègia coneguda, estalviant potència de càlcul. No obstant això, sense la configuració adequada dels paràmetres, un AG no funcionarà tan eficientment com deuria. Una parametrización incorrecta pot evitar que l’algoritme trobe bones solucions. En aquest projecte hem disenyat, implementat i evaluat un AG i estudiat la seua parametrización per a resoldre un problema combinatori, específicament el Problema del Viatjant de Comerç. Donada una configuració de problema, presentarem la millor parametrización de l’AG; és a dir, la que obté solucions de millor qualitat i consumix menys potència de càlcul.