Computacion evolutiva aplicaciones

La Mejor Solución Evolutiva al Dilema del Prisionero Iterado
Angel Kuri Morales Centro de Investigación en Computación Instituto Politécnico Nacional México D.F. akuri@pollux.cic.ipn.mx Resumen En este trabajo hacemos una presentación del programa que resultó ganador del concurso del Dilema del Prisionero Iterado (DPI) que fue abierto a la comunidad internacional durante el evento Congress onEvolutionary Computation 2000 (CEC2000), celebrado en la ciudad de San Diego, California del 16 al 19 de julio del 2000. En la primera parte de nuestro trabajo hacemos una introducción al problema del DPI. En la segunda parte describimos el algoritmo que se usó para atacar el problema planteado durante CEC2000. Este algoritmo está basado en técnicas de Algoritmos Genéticos coevolutivos. En latercera parte se presentan algunas conclusiones y se plantean trabajos futuros. Palabras Clave. Cooperación, dilema, algoritmos genéticos, coevolución, CEC2000. 1. Planteamiento y Antecedentes En este trabajo tratamos un problema clásico de la teoría de juego que vierte una nueva luz en muchos de los problemas que han ocupado a filósofos éticos y políticos [1][2] a través de la historia. El interés queha despertado permite, incluso, plantear una ética que se puede encontrar expuesta en Internet [3][4]. Este problema se refiere a una situación en la cual hay que decidir cuál es la opción racional para un individuo como parte de un grupo y para el grupo en su totalidad. Nos ayuda a entender cómo tales dilemas se pueden resolver para obtener el mayor beneficio individual y colectivo. Aunque elplanteamiento del problema se hace en términos de un juego, sus implicaciones van mucho más allá de éste. Por ejemplo, a la luz del DPI se ha analizado el problema de la carrera armamentista [5], la correcta selección de proveedores de bienes y servicios en una economía de libre mercado [6] y la política de asignación de fondos para el desarrollo de la ciencia [7], entre otros. 1.1 El dilema delprisionero iterado El problema denominado Dilema del Prisionero toma su nombre de la siguiente situación hipotética: “En una celda la policía mantiene a dos presos políticos. El interrogador está intentando persuadirlos a confesar que son miembros de un partido ilegal de la oposición. Los presos saben que si ninguno de ellos confiesa, el investigador no podrá levantar cargos pero éste podría proseguirel interrogatorio durante tres meses antes de dejarlos ir. Si uno de ellos confiesa implicando al otro, el primero (que confesó) será liberado inmediatamente y Jesús Gutiérrez García Centro de Investigación en Computación Instituto Politécnico Nacional México D.F. jgg@pollux.cic.ipn.mx

1

el otro será condenado a ocho meses de prisión. Por otra parte, si ambos confiesan será tomada encuenta su ayuda y tendrán cinco meses de prisión cada uno. Los prisioneros son interrogados por separado. No saben si el otro a confesado o no, pero a ambos se les informa del trato que, por separado, se ha ofrecido a cada uno. El dilema es: ¿Cuál es la mejor estrategia? ¿Confesar (abandonar a la contraparte) o no confesar (cooperar con la contraparte)?” Este dilema puede plantearse como un “juego” enel que se califica a los jugadores de acuerdo con la siguiente tabla de ponderación. Dependiendo de la respuesta de ambos prisioneros cada uno de ellos obtendrá una puntuación. En el caso que ha sido descrito, esta puntuación refleja las pérdidas derivadas de una posible respuesta., tal como se muestra en la tabla T.1.1.1. En este caso el objetivo es minimizar la pérdida. Alternativamente, elproblema puede plantearse como la obtención de un beneficio, en cuyo caso buscaríamos maximizar la ganancia. Jugada Puntos Prisionero Prisionero Prisionero Prisionero 1 2 1 2 Coopera Abandona 8 0 Coopera Coopera 3 3 Abandona Abandona 5 5 Abandona Coopera 0 8 Tabla T.1.1.1. Tabla de Ponderación del DP Este problema se denomina “Dilema del Prisionero Iterado” si el proceso se repite varias veces. El...