A fast genetic algorithm for the Maximum Cut-Clique problem.

Abstract

En esta tesis se presenta un problema reciente de teoría de grafos conocido como Máximo Clique-Corte o MCC. Dado un grafo simple, se desea hallar un subgrafo completo tal que el corte inducido por sus nodos tenga máximo cardinal. Este problema combinatorio fue introducido por P. Martins en 2012, y encuentra aplicaciones en el Análisis de Mercados, donde interesa la correlación de artículos de venta. La correspondiente versión de decisión del MCC pertenece a la categoría de problemas NP-Completos. Como consecuencia, los métodos exactos resultan computacionalmente prohibitivos para grafos de gran tamaño. En la literatura científica se dispone de heurísticas previas que explotan aleatoriedad con distintas estructuras de vecindad, como GRASP/VND o ILS. En esta tesis se presenta una nueva solución basada en Algoritmos Genéticos. Un estudio comparativo comprueba que la propuesta es altamente competitiva con trabajos anteriores, siendo su mayor fortaleza la eficiencia computacional.