Resumen

Los problemas se pueden clasificar en conjuntos o clases de complejidad [InAlg01]. En este proyecto de grado, se estudiar ́an los problemas pertenecientes a la clase NP. Un problema pertenece a la clase NP si no es posible generar una soluci ́on con un algoritmo determinista en tiempo polinomial. Estos problemas son de gran comple- jidad y por ello es necesario investigar nuevos par ́ametros, de manera que se pueda predecir lo dif ́ıcil que es resolver una instancia concreta de un problema. En el campo de la Matem ́atica y la F ́ısica existe un fen ́omeno denominado Percolaci ́on el cual describe, para un sistema, la transici ́on de un estado en otro. [Perc02] En este proyecto se buscar ́a si hay fen ́omenos similares a la percolaci ́on en los proble- mas intratables, cuando se intentan resolver con algoritmos gen ́eticos, para entender cu ́an dif ́ıcil es el problema concreto. La idea surge al leer el libro Investigations del bi ́ologo Stuart Kauffman [Kau00]; en el cual se plantea una forma de navegar por el espacio de soluciones de un problema complejo - en ese caso Job Shop Scheduling -, basado en transiciones de fase. El prop ́osito de este proyecto es caracterizar la aplicaci ́on de la t ́ecnica de Percolaci ́on a problemas de tipo NP. Los objetivos del mismo son: • Aplicar la t ́ecnica de Percolaci ́on. iii • Determinar la dimensi ́on fractal de los problemas Traveling Salesman Problem, K-SAT y Knapsack. • Determinar que correlaci ́on existe entre la dificultad de un problema y el grado de percolaci ́on del mismo, aplic ́andolo a los problemas: Traveling Salesman Problem, K-SAT y Knapsack. • Desarrollar un algoritmo gen ́etico que permita aplicar de forma sencilla la t ́ecnica de percolaci ́on para controlar la presi ́on selectiva. • Comparar los resultados obtenidos en los problemas Traveling Salesman Pro- blem, K-SAT y Knapsack aplicando la t ́ecnica de percolaci ́on y cuando no se aplica. El documento se estructura de la siguiente forma: Cap ́ıtulo 1. Se muestra la definici ́on de la Clase NP y se explican cada uno de los problemas a tratar en este proyecto de grado: Traveling Salesman Problem, K-SAT y Knapsack. Cap ́ıtulo 2. Se explica el concepto de Algoritmo Gen ́etico, as ́ı mismo se muestra su estructura y funcionamiento. Cap ́ıtulo 3. Se presenta la definici ́on del concepto de Percolaci ́on y su clasificaci ́on. Cap ́ıtulo 4. Se muestra la definici ́on del concepto Fractal, sus caracter ́ısticas y al- gunos ejemplos. Cap ́ıtulo 5. Se describen los Generadores de Problemas para cada tipo de problema (Traveling Salesman Problem, K-SAT y Knapsack). Cap ́ıtulo 6. Se presenta una explicaci ́on de c ́omo se realizaron cada uno de los Algo- ritmos Gen ́eticos para resolver cada problema; se muestra el c ́alculo de la percolaci ́on iv y su aplicaci ́on en los Algoritmos Gen ́eticos. Cap ́ıtulo 7. Se muestran las pruebas realizadas con cada algoritmo y las conclu- siones. Referencias Bibliogr ́aficas. Anexos.