APLICACIONES PRÁCTICAS DE LA COMPUTACIÓN EVOLUTIVA

Introducción

Los Algoritmos Evolutivos (AE) son métodos de búsqueda pertenecientes al campo de la Computación Evolutiva (CE), una de las ramas de la Inteligencia Artificial. Están fuertemente inspirados en los mecanismos de la evolución biológica. Así, a partir de un conjunto inicial de individuos, es decir, soluciones potenciales pertenecientes al espacio de búsqueda de soluciones del problema, el AE selecciona y mezcla aquellas de mayor calidad, provocando que, tras sucesivas iteraciones, aumente la calidad del conjunto de soluciones, en general, y la de la mejor solución, en particular.

Durante varias décadas los AE's se han utilizado, y se siguen utilizando, de forma exitosa para resolver problemas de optimización en áreas tan diversas como planificación, control, diseño o clasificación, entre otros. Los AE's empiezan a ser competitivos cuando los problemas manejados poseen espacios de búsqueda extensos y no lineales, donde otros métodos de optimización tradicionales no son capaces de encontrar soluciones en un tiempo razonable.

Objetivo

Se proponen un conjunto de problemas característicos en el campo de la CE. El alumno deberá elegir uno de ellos y plantear una solución justificada en términos de alguno de los diferentes paradigmas existentes en CE, tales como algoritmos genéticos, estrategias evolutivas o programación genética, entre otros.

Requisitos

No es imprescindible que el alumno tenga conocimientos previos en el área de Computación Evolutiva. En este caso, durante el desarrollo de este proyecto, el alumno adquirirá también los fundamentos básicos de esta disciplina y de alguno de sus paradigmas clásicos.

Es obligatorio un dominio del idioma inglés a nivel de traducción, ya que la mayor parte de la bibliografía a utilizar está en este idioma.

Metodología

Antes de ejecutar un AE para resolver un problema de optimización, existen una serie de decisiones a tomar, son los siguientes:

1. En primer lugar, y en función de las características del problema a resolver, hay que decantarse por un tipo específico de AE, de entre los distintos paradigmas existentes.
   

2. En este punto, hay que elegir la forma de representar computacionalmente las soluciones pertenecientes al espacio de búsqueda del problema. Esta elección estará en parte condicionada por el tipo de algoritmo elegido en el paso anterior, ya que cada paradigma evolutivo tiene un esquema genérico de representación. Incluso, al abordar este paso, podría ser necesario volver al paso anterior para cambiar el tipo de AE inicialmente elegido.
   

3. Seguidamente, se ha de formalizar todas las especificaciones del problema original en términos de una función matemática, denominada función de adaptación, cuyo dominio de definición vendrá dado por la forma de representación elegida en el paso anterior.
   

4. A continuación, se ha de elegir o diseñar los operadores de variación adecuados a las especificaciones del problema y la forma de representación elegida.
   

5. Finalmente, habrá que decidir el valor del conjunto de parámetros típicos asociados al paradigma evolutivo elegido. Estos parámetros hacen referencia, por ejemplo, a la frecuencia de aplicación de cada operador de variación o a la condición de finalización del algoritmo.
   

Teniendo en cuenta las decisiones tomadas en los cinco pasos anteriores, el alumno procederá a la implementación del algoritmo evolutivo. Después de la implementación, el alumno deberá:

• Comprobar que el algoritmo resuelve o, al menos, se aproxima a la solución del problema.

• Utilizar índices de medidas de prestaciones para valorar la bondad del algoritmo implementado.

• Si fuera necesario, plantear posibles mejoras e implementarlas. Seguidamente se volvería a medir las prestaciones del algoritmo mejorado y se compararían con las del algoritmo original.

• Se podría plantear también la comparativa del AE implementado con otro método no evolutivo.

Duración del Proyecto

La duración del proyecto dependerá de los conocimientos previos del alumno en el área y de su dedicación. El periodo podría variar desde seis meses a un año.

Problemas Propuestos

• Aplicación de algoritmos genéticos al problema del cortado de patrones en dos dimensiones

• Resolución de Sudokus (en breve)

• El alumno podrá plantear también un problema para ser resuelto mediante AE's. En este caso, deberá recibir previamente el visto bueno por parte del profesor.

Bibliografía

General: con carácter general, el alumno no familiarizado con los aspectos básicos de la CE y los diferentes tipos de AE's, podrá consultar el siguiente libro introductorio:

• A. E. Eiben and J.E. Smith. Introduction to Evolutionary Computing. Springer, 2003.
  

Específica: con carácter específico, y dependiendo del tipo de problema, el alumno también podría manejar artículos científicos.