|
|
 |
|
COMPUTACIÓN EVOLUTIVA
Profesorado
| Coordinador: Severino Fernández Galán (Dpto. Inteligencia Artificial,
UNED) |
| Profesores: |
| Enrique Javier Carmona Suárez (Dpto. Inteligencia Artificial, UNED) |
|
|
|
|
Ficha técnica:
| Tipo | Optativa |
|
| Cuatrimestre | Primero |
| Créditos/horas totales | 6/150 |
| Horas de estudio teórico | 60 |
| Horas de prácticas | 40 |
| Horas complementarias | 50 |
DESCRIPCIÓN DE LA ASIGNATURA
Prerrequisitos recomendables
No es necesario adquirir ninguna competencia previa para abordar con
garantías de éxito el aprendizaje de las técnicas que se tratan en
el presente curso.
Objetivos generales de la materia
Esta asignatura ofrece una completa y exhaustiva introducción al campo
de la computación evolutiva, incluyendo el estudio de sus variantes
más importantes: algoritmos genéticos, estrategias evolutivas, programación
evolutiva y programación genética.
Al igual que en el campo de la ingeniería, donde la propia Naturaleza
sirve a menudo de fuente de inspiración, el desarrollo de métodos
automáticos de resolución de problemas en ciencias de la computación
también puede apoyarse en la imitación de procesos naturales. En concreto,
la computación evolutiva se basa en la imitación de los procesos evolutivos
que ocurren en la Naturaleza. Desde un punto de vista computacional,
los algoritmos evolutivos aportan ventajas en cuanto a robustez y
aplicabilidad a un amplio espectro de problemas.
El enfoque evolutivo para la resolución automática de problemas ha
sido aplicado con éxito a tareas de optimización, diseño, planificación
y control, entre otras. Un conjunto representativo de aplicaciones
de dichas tareas se estudia en la presente asignatura debido, por
un lado, a la amplia atención que han recibido a lo largo de los años
por parte de la comunidad científica internacional y, por otro lado,
como motivación para que el alumno investigue la aplicación de algoritmos
evolutivos en la resolución de problemas que sean de su interés.
Destrezas y competencias
Se especifican detalladamente en la sección 1.9 atendiendo a una clasificación
por temas.
Contextualización de la materia en el conjunto del Master
Esta asignatura pertenece al módulo "Métodos de solución
de problemas en inteligencia artificial" dentro de la especialidad
IA.1: "Sistemas inteligentes de diagnóstico, planificación
y control" de la titulación de posgrado "Máster
de inteligencia artificial avanzada. Fundamentos, métodos y aplicaciones".
Los métodos evolutivos constituyen una importante opción para la resolución
de problemas en inteligencia artificial. En muchas ocasiones representan
una alternativa a métodos específicos diseñados para resolver de forma
especializada cierta tarea. Por ello, no sería exagerado afirmar que
esta asignatura está relacionada en mayor o menor medida con el resto
de asignaturas del programa. A modo de ejemplo, se pueden aplicar
técnicas evolutivas en razonamiento aproximado, aprendizaje automático,
visión artificial, robótica o minería de datos.
1 MEDIOS DE ESTUDIO
1.1 Metodología docente
La general del presente programa de posgrado. Al tratarse de un máster
orientado a la investigación, las actividades de aprendizaje giran
en torno al estado del arte en cada una de las materias del curso
y a los problemas que se puedan abordar en el proyecto final, sobre
el que se realizará la evaluación. La asignatura no tiene clases presenciales.
Los contenidos teóricos se impartirán a distancia, de acuerdo con
las normas y estructuras de soporte telemático de enseñanza en la
UNED.
1.2 Material de estudio
El material de estudio que se utilizará a lo largo del curso se compone
de una bibliografía general de consulta (especificada en la sección
1.15), la plataforma aLF para aprendizaje y colaboración a través
de internet y, por último, la versión actual de un entorno de programación
para la implementación de algunas de las actividades prácticas del
curso, por ejemplo, JAVA (Software Development Kit).
1.3 Materiales y recursos de apoyo
Los alumnos dispondrán de una plataforma para aprendizaje y colaboración
a través de internet, denominada aLF.
1.4 BIbliografia general de consulta
Bibliografía básica:
Introduction to Evolutionary Computing
A. E. Eiben y J. E. Smith
Springer, 2003
Bibliografía complementaria:
Genetic Algorithms + Data Structures Evolution Programs
Z. Michalewicz
Springer, 1996 (Third, Revised, and Extended Edition)
Genetic Algorithms in Search, Optimization, and Machine Learning
D. E. Goldberg
Addison-Wesley, 1989
Evolutionary computing
A.E. Eiben y M. Schoenauer
Information Processing Letters, 82(1): 1-6, 2002
1.5 Tutorización
Existe a disposición de los alumnos un horario de tutorización telefónica
con los profesores de la asignatura.
Horario: lunes de 16.00 a 20.00 hrs.
Tfnos.de contacto:
Enrique J. Carmona Suárez: 91 3987301
Severino Fernández Galán: 91 3987300
Además, el alumno podrá dirigir sus dudas cualquier día de la semana
a las siguientes direcciones de correo electrónico:
Enrique J. Carmona Suárez: ecarmona@dia.uned.es
Severino Fernández Galán: seve@dia.uned.es
2 ESTRUCTURA DEL CURSO
2.1 Estructura y contenido teórico
Tema 1 Introducción
1.1 Historia de la computación evolutiva
1.2 Inspiración en Biología
1.3 Motivos para trabajar con computación evolutiva
1.4 Ejemplos de aplicaciones de la computación evolutiva
Tema 2 Qué es un algoritmo evolutivo
2.1 Introducción
2.2 Componentes principales de los algoritmos evolutivos
2.3 Cómo trabaja un algoritmo evolutivo
2.4 Algoritmos evolutivos v.s. otras técnicas de optimización global
Tema 3 Algoritmos genéticos
3.1 Representación de los individuos
3.2 Selección de los padres
3.3 Recombinación
3.4 Mutación
3.5 Selección de supervivientes
Tema 4 Estrategias evolutivas
4.1 Introducción
4.2 Representación y auto-adaptación
4.3 Mutación y auto-adaptación
4.4 Recombinación
4.5 Selección de padres
4.6 Selección de supervivientes
Tema 5 Programación evolutiva
5.1 Desarrollo histórico
5.2 Representación de los individuos
5.3 Selección de padres y recombinación
5.4 Mutación
5.5 Selección de supervivientes
Tema 6 Programación genética
6.1 Representación
6.2 Mutación
6.3 Recombinación
6.4 Selección de padres
6.5 Selección de supervivientes
6.6 Inicialización
6.7 El efecto "engorde" (bloat)
Tema 7 Aprendizaje en sistemas clasificadores
7.1 Introducción
7.2 Sistema clasificador genérico
7.3 Ejemplo de sistema clasificador: el multiplexor
7.4 El sistema clasificador ZCS
7.5 El sistema clasificador XCS
7.6 Extensiones de los sistemas clasificadores
7.7 Enfoque tipo Pittsburgh
Tema 8 Control de parámetros en algoritmos evolutivos
8.1 Introducción
8.2 Aspectos relevantes para clasificar las técnicas de control dinámico
de parámetros
8.3 Ejemplos alternativos a la aproximación estática
Tema 9 Problemas multimodales y distribución espacial
9.1 Mantenimiento de la diversidad en problemas multimodales
9.2 Métodos implícitos para el mantenimiento de la diversidad
9.3 Métodos explícitos para el mantenimiento de la diversidad
9.4 Algoritmos evolutivos para problemas multiobjetivo
Tema 10 Hibridación con otras técnicas: algoritmos meméticos
10.1 Introducción
10.2 Uso de conocimiento del dominio y/o métodos de hibridación en
algoritmos evolutivos
10.3 Algoritmos de búsqueda local
10.4 Memes y algoritmos meméticos
10.5 Estructura de un algoritmo memético
10.6 Algunas cuestiones prácticas para el de diseño de algoritmos
meméticos
Tema 11 Teoría
11.1 Teorema del esquema
11.2 Análisis de algoritmos evolutivos basado en sistemas dinámicos
11.3 Análisis de algoritmos evolutivos basado en cadenas de Markov
11.4 Otros métodos de análisis de algoritmos evolutivos
Tema 12 Manejo de restricciones
12.1 Introducción
12.2 Clasificación de problemas con restricciones
12.3 Formas conceptualmente diferentes de manejar restricciones
12.4 Mecanismos para manejar restricciones en algoritmos evolutivos
Tema 13 Formas especiales de evolución
13.1 Ejemplos de formas especiales de evolución
13.2 Coevolución
13.3 Evolución interactiva
13.4 Optimización de funciones no estacionarias
Tema 14 Trabajando con algoritmos evolutivos
14.1 Introducción: ¿Qué se quiere que haga un algoritmo evolutivo?
14.2 Medidas de prestaciones
14.3 Problemas test para comparación de resultados experimentales
2.2 Objetivos por tema y orientaciones breves
Tema 1 Introducción
Objetivos:
El objetivo de este tema es proporcionar una visión de conjunto sobre
la computación evolutiva. Dicha visión de conjunto incluye una perspectiva
histórica del campo, una descripción de su relación con otras ciencias
en las que se inspira (principalmente la Biología), un análisis de
por qué resulta interesante resolver ciertas tareas tomando como punto
de partida el enfoque proporcionado por la computación evolutiva y,
finalmente, una ordenación del tipo de problemas que se pueden resolver
mediante computación evolutiva, basada en la naturaleza del problema
en relación a sus entradas, salidas y modelo interno.
Orientaciones:
Inicialmente se realiza un estudio del desarrollo histórico de la
computación evolutiva y sus variantes, en la sección "Historia
de la computación evolutiva". Esta sección se debe estudiar
en detalle, ya que sirve de introducción a las distintas variantes
de la computación evolutiva que se tratarán en los temas 3 a 7. A
continuación se repasan las bases biológicas en las que se inspira
la computación evolutiva, en la sección "Inspiración en Biología".
En esta sección habrá partes que el alumno tenga dificultades para
entender. Si es así, se recomienda releer dichas partes y, si finalmente
la dificultad en el entendimiento persiste, la mejor opción es proseguir
el estudio sin estancarse en los apartados más complicados. En la
sección "Motivos para trabajar con computación evolutiva"
se analizan las razones que hacen de la computación evolutiva un método
de interés para la resolución de problemas. Esta sección se debe estudiar
en detalle, ya que ayuda a encontrar sentido al estudio global de
la presente asignatura. Finalmente, se dan ejemplos de aplicaciones
en la sección "Ejemplos de aplicaciones de la computación
evolutiva". Debido al interés práctico de esta sección, se
recomienda su estudio en detalle. Es importante en esta sección que
el alumno realice un esfuerzo de generalización en la definición de
problemas, que ayude posteriormente a una más fácil clasificación
de los mismos.
Tema 2 Qué es un algoritmo evolutivo
Objetivos:
El principal objetivo de este tema es definir y caracterizar de forma
genérica a los Algoritmos Evolutivos (AE). Para ello:
1.Se analizará el denominado algoritmo evolutivo canónico, un esquema
general que forma la base común de las distintas variantes vinculadas
a la familia de los AE's.
2.Se describirán los componentes principales de todo AE y las propiedades
más relevantes relacionadas con el cómo trabajan este tipo de algoritmos.
3.Finalmente, teniendo en cuenta la estrecha relación de este tipo
de algoritmos con la tarea de optimización, se analizará la relación
existente entre los AE's y otras técnicas de optimización global.
Orientaciones:
El estudio de este tema se hará básicamente a partir del texto de
referencia indicado en la bibliografía básica [Eiben&Smith-03],
y de acuerdo a las siguientes indicaciones: En la primera sección
de introducción, se debe aprender el esquema general que subyace en
todo algoritmo evolutivo, cuales son las etapas que lo componen y
cómo se secuencian en el tiempo. Esta sección se corresponde íntegramente
con los contenidos del epígrafe 2.2 del texto base. El estudio de
la sección 2.1 se hará a partir del epígrafe 2.3 del texto base. En
este caso, es importante retener los distintos componentes, mecanismos
y operadores que forman parte de los AE's porque son conceptos que,
en los temas siguientes, se utilizarán constantemente. Los dos ejemplos
mostrados en el epígrafe 2.4 del texto base son de recomendada lectura
puesto que muestran, desde un punto de vista práctico, cómo se resuelve
el problema de la codificación de los individuos y el de la elección
de los operadores y mecanismos de selección más adecuados en función
de las características del problema que se quiere resolver. El estudio
del epígrafe 2.5 permite obtener una visión clara de algunas propiedades
de comportamiento típicas de los AE's (sección 3). En particular,
cómo evolucionan los distintos individuos de la población y cómo evoluciona
el mejor individuo obtenido en cada generación, en ambos casos, a
medida que transcurre el tiempo de ejecución. Finalmente, el estudio
del epígrafe 2.6 del texto base, que engloba la sección 2.4 del temario,
permitirá situar el concepto de AE en un contexto más amplio y conocer
su relación con otras técnicas globales de optimización.
Tema 3 Algoritmos genéticos
Objetivos:
Este tema describe el tipo de algoritmo evolutivo más ampliamente
utilizado: los algoritmos genéticos. Se explican en detalle las principales
características de los algoritmos genéticos en lo que se refiere a
representación de individuos, inicialización de la población, selección
de padres, recombinación, mutación y selección de supervivientes.
A modo de ilustración, también se hace referencia a algunas aplicaciones
en optimización de funciones reales y planificación.
Orientaciones:
Es importante estudiar en detalle cada una de las secciones contenidas
en este tema, ya que tratan cuestiones fundamentales dentro del campo
de los algoritmos genéticos, que en muchas ocasiones también resultan
de interés para otros tipos de algoritmos evolutivos. Nos referimos
principalmente a los métodos relacionados con la selección y variación
de individuos, que se estudian por primera vez en este tema y vuelven
a ser tratados en los temas 4 a 8 en gran medida y en el resto de
temas en menor medida.
Inicialmente, en la sección "Representación de los individuos"
se revisan los diferentes tipos de representación de individuos en
algoritmos evolutivos. El alumno debe poner especial atención a las
representaciones binarias y a las que usan permutaciones, ya que son
las más frecuentes en algoritmos genéticos. En la sección "Selección
de los padres", el alumno encontrará que aparecen ciertos
conceptos básicos relacionados con la teoría de la probabilidad. En
las dos secciones siguientes, "Recombinación" y
"Mutación", se describen una serie de métodos de
diferente complejidad para llevar a cabo el proceso de variación de
los individuos de la población. Cada método ofrece una serie de ventajas
particulares al ser implementado en un algoritmo genético particular.
Finalmente, la sección "Selección de supervivientes"
es importante porque está relacionada con el tipo de regeneración
de los individuos seguida en la población tras cada ciclo del algoritmo
genético. No registra el mismo comportamiento un algoritmo genético
en el que todos los individuos son reemplazados en cada generación
que aquél en que sólo se reemplaza una pequeña proporción de los individuos
de la población.
Tema 4 Estrategias evolutivas
Objetivos:
El objetivo fundamental de este tema es describir las principales
características de otra de las variantes pertenecientes a la familia
de los AE's, la conocida con el nombre de Estrategias Evolutivas
(EE).
Como objetivo adicional, se describirá y ejemplificará el concepto
de auto-adaptación de parámetros. Un procedimiento éste íntimamente
ligado al esquema de funcionamiento de las EE's y que permite aprender
en cada momento del ciclo de ejecución los valores de ciertos parámetros
del propio algoritmo.
Orientaciones:
El estudio de este tema se hará básicamente a partir del texto de
referencia indicado en la bibliografía básica [Eiben&Smith-03],
y de acuerdo a las siguientes indicaciones. En primer lugar es fundamental
entender el papel de la operación mutación dentro de este tipo de
estrategias. Ya no sólo porque es el operador principal de variación
utilizado, sino también porque el mecanismo de mutación (los parámetros
que lo definen) se incluye dentro del cromosoma para, junto con la
solución, hacerlo evolucionar. En este sentido, el estudio y la comprensión
de los epígrafes 4.3. y 4.4 del libro base es clave. Dichos epígrafes
abarcarían las secciones 4.1 a 4.3 del temario. En cuanto a los procesos
de recombinación y selección (secciones 4.4 a 4.7), decir que si bien
adoptan formas diferentes a los utilizados en los algoritmos genéticos,
no revisten mucha dificultad ni desde el punto de vista de su comprensión
ni desde el de una posible implementación de dichos procedimientos.
Estos mecanimos se estudiarán a partir de los epígrafes 4.5, 4.6 y
4.7 del texto base. Finalmente, se recomienda al alumno la lectura
de los dos ejemplos descritos en el epígrafe 4.9 del texto base.
Tema 5 Programación evolutiva
Objetivos:
En este tema se explica un nuevo tipo de algoritmo evolutivo: la programación
evolutiva. Se analizan sus principales características en relación
a la representación de individuos, la inicialización de la población,
la selección de padres, la recombinación, la mutación y la selección
de supervivientes. El alumno observará que se hace una clara distinción
entre programación evolutiva clásica, en la que los individuos se
representan mediante máquinas de estados finitos, y la programación
evolutiva actual, más cercana a las estrategias evolutivas.
Orientaciones:
El estudio de este tema se puede dividir en dos partes claramente
diferenciadas: en primer lugar, la de la programación evolutiva clásica
y, en segundo lugar, la de las tendencias actuales en programación
evolutiva. Tanto en una parte como en la otra se debe analizar el
tipo de representación de individuos utilizado, la forma de realizar
la selección de padres, los operadores de variación (recombinación
y mutación) empleados y, finalmente, el modo de llevar a cabo la selección
de supervivientes.
Tema 6 Programación genética
Objetivos:
El principal objetivo de este tema es describir el fundamento de la
programación genética (PG), haciendo hincapié en los distintos mecanismos
de reemplazo, operadores de variación y forma de representación utilizados
por este tipo de algoritmos.
Orientaciones:
El estudio del presente tema requiere un especial dedicación al epígrafe
6.3 del texto base (sección 6.1 del temario) puesto que analiza la
forma de representación utilizada en el paradigma de la PG, y que
es totalmente diferente a la utilizada en el resto de variantes de
AE's. Los epígrafes 6.4 a 6.6 (ambos inclusive) siguen el esquema
general de los tres capítulos anteriores y describen los operadores
de variación y mecanismos de selección y de inicialización utilizados,
esta vez, en PG. Dichos epígrafes abarcan las secciones 6.2 a 6.6
del temario. Resulta interesante estudiar el denominado efecto "engorde"
(sección 6.7 del temario) propio de esta variante, y consecuencia
directa de la no limitación a un tamaño fijo de los individuos de
la población. Para ello, el alumno deberá estudiar el epígrafe 6.9
del texto base. Finalmente, los epígrafes 6.10 y 6.11 del texto base
dan cuenta de ejemplos de aplicación de la PG a tipos de problemas
concretos. Se recomienda su lectura.
Para aquel alumno que quiera profundizar en este paradigma es de obligada
consulta las cuatro referencias bibliográficas a los libros del padre
de la programación genética, John Koza, [1, 2, 3, 4] (véase resumen
del contenido del tema 6 de la asignatura), en especial las dos primeras.
Tema 7 Aprendizaje en sistemas clasificadores
Objetivos:
Este tema describe un tipo de algoritmo evolutivo relacionado con
los sistemas basados en reglas y el aprendizaje por refuerzo: los
sistemas clasificadores. Se diferenciarán dos tipos de enfoques en
sistemas clasificadores: el tipo Michigan, que será del que nos ocupemos
más ampliamente en este tema, y el tipo Pittsburgh. Se explicarán
las características genéricas de los sistemas clasificadores tipo
Michigan y algunos ejemplos o variantes de los mismos.
Orientaciones:
En la sección "Introducción" se realizan una serie
de consideraciones previas sobre los sistemas clasificadores en general.
Nótese la distinción que se realiza en esta sección entre el enfoque
tipo Michigan y el enfoque tipo Pittsburgh. En la sección "Sistema
clasificador genérico" se describen las características comunes
de los sistemas clasificadores tipo Michigan, que son los que se estudian
con más detalle en este tema. Las tres secciones siguientes son de
especial interés debido a que describen un ejemplo de aplicación de
los sistemas clasificadores tipo Michigan, el multiplexor, y dos variantes
de los mismos, los sistemas ZCS y XCS. La sección "Extensiones
de los sistemas clasificadores" sugiere diferentes formas
de ampliar la semántica de las reglas utilizadas en los sistemas clasificadores
estándar. Finalmente, en la sección "Enfoque tipo Pittsburgh"
se resumen las características del otro enfoque importante existente
para el diseño de sistemas clasificadores.
Tema 8 Control de parámetros en algoritmos evolutivos
Objetivos:
El principal objetivo de este tema es comparar las dos grandes aproximaciones
utilizadas a la hora de inicializar y controlar los valores de parámetros
de un algoritmo evolutivo: la estática y la dinámica.
Asumiendo la aproximación dinámica como la estrategia más competitiva,
el segundo objetivo del presente tema es enumerar un conjunto de características
en base a las cuales poder establecer una clasificación de las distintas
técnicas pertenecientes a esta aproximación.
Orientaciones:
Para abordar el estudio de este tema hay que tener en cuenta que existen
dos partes bien diferenciadas. Aquella que desde un punto de vista
teórico clasifica las estrategias existentes en la literatura relativas
al control de parámetros en AE's (sección 8.2 del temario) y que
se corresponde con el estudio del epígrafe 8.4. Y aquella otra (sección
8.3) que, desde una perspectiva práctica, ejemplifica y describe detalladamente
algunas de las estrategias pertenecientes a cada una de las clases
establecidas en la jerarquía obtenida durante la descripción teórica,
y cuyo estudio se realizará a partir de los epígrafes 8.3 y 8.5 del
texto base. Finalmente, se recomienda la lectura de los epígrafes
8.1 y 8.6 del libro de texto que marcan el principio inicial y final,
respectivamente del tema, sirviendo el primero como cauce para introducir
el tema y, el segundo, como discusión final del mismo.
Tema 9 Problemas multimodales y distribución espacial
Objetivos:
El objetivo de este tema es doble:
1.Por un lado, se explican una serie de técnicas para la resolución
de problemas multimodales mediante algoritmos evolutivos. Los problemas
multimodales se caracterizan por la presencia, además del óptimo global,
de varias soluciones que son óptimos locales. En este tipo de problemas
se persigue hallar una serie de soluciones de calidad diferentes,
que además sean óptimos locales. Por tanto, se hace necesario mantener
la diversidad de la población de cara a que no haya una convergencia
prematura a uno de los óptimos locales.
2.Por otro lado, se describen los problemas multiobjetivo, en los
que también se hace necesario el mantenimiento de la diversidad en
la población para poder encontrar una serie de soluciones de calidad
a los mismos. En un problema multiobjetivo no hay un único objetivo
que determine la calidad de los individuos, sino que hay varios objetivos,
en muchas ocasiones contrapuestos entre sí.
Orientaciones:
El estudio de este tema se puede dividir en dos partes bien diferenciadas:
por un lado, la de los problemas multimodales y diferentes técnicas
para el mantenimiento de la diversidad de la población en los mismos
y, por otro lado, la de los problemas multiobjetivo, en los que cobran
también importancia los métodos para el mantenimiento de la diversidad
descritos en la parte anterior.
Tras definir los problemas multimodales en la primera sección, se
dedican sendas secciones a la explicación de métodos implícitos y
explícitos para el mantenimiento de la diversidad en una población.
Para finalizar el tema se definen los problemas multiobjetivo y los
tipos existentes más importantes de algoritmos evolutivos para problemas
multiobjetivo.
Tema 10 Hibridación con otras técnicas: algoritmos
Objetivos:
A nivel general, el principal objetivo de este tema es el estudio
de aquellas aproximaciones basadas en AE's que o bien son hibridadas
con otras técnicas o bien incorporan conocimiento específico del dominio
del problema.
A nivel particular, el objetivo es centrarse en dar a conocer las
características y estructura de uno de los máximos representantes
en aplicar las dos estrategias mencionadas anteriormente, los algoritmos
meméticos (AM).
Orientaciones:
A modo de introducción (sección 10.1), se recomienda un estudio detallado
de cuáles son las motivaciones que dan lugar a la aparición de los
algoritmos meméticos (estudio de epígrafe 10.2 del texto base) y de
los distintos mecanismos utilizados para transformar un AE estándar
en un AM (epígrafe 10.4 de texto base). Los contenidos de este último
epígrafe abarcan las secciones 10.2, 10.4 y 10.5 del temario. En los
epígrafes 10.5 y 10.6 del texto base, íntimamente relacionados con
la sección 10.6 del temario, el alumno encontrará una breve descripción
de diferentes propuestas prácticas existentes en la literatura relacionadas
con el mundo de los AM's y a los que el alumno deberá dedicar una
atenta lectura. Finalmente, el alumno no familiarizado con las denominadas
estrategias de búsqueda local, debería también abordar el estudio
del epígrafe 10.3 del texto base, correspondiente a la sección 10.3
del temario.
Tema 11 Teoría
Objetivos:
El objetivo de este tema es describir distintos métodos teóricos para
el análisis del comportamiento de un algoritmo evolutivo, principalmente
de un algoritmo genético.
Orientaciones:
La primera sección de este tema, denominada ?Teorema del esquema?,
está dedicada a la demostración de un teorema al que históricamente
se le ha dado gran importancia dentro del campo de la computación
evolutiva. El resto de secciones se ocupan de diferentes enfoques
para el análisis de algoritmos evolutivos, basados respectivamente
en: sistemas dinámicos, cadenas de Markov, mecánica estadística y
métodos reduccionistas. Mientras que la sección del teorema del esquema
se debe estudiar en profundidad, el resto de secciones son de carácter
introductorio.
Tema 12 Manejo de restricciones
Objetivos:
Son varios los objetivos planteados por este tema:
1.Establecer una clasificación de distintos tipos de problemas en
los que se manejan restricciones.
2.Describir conceptualmente dos formas genéricas de abordar, mediante
algoritmos evolutivos, problemas que manejan restricciones.
3.Mostrar un conjunto de estrategias prácticas que particularizan
y ejemplifican las dos formas genéricas citadas anteriormente.
Orientaciones:
El estudio del presente tema se aborda desde dos perspectivas. Desde
un punto de vista teórico, el alumno debería estudiar minuciosamente
las secciones 12.2 y 12.3 del temario, la primera para aprender a
distinguir entre diferentes tipos de problemas que manejan restricciones
(estudiar a partir del epígrafe 12.2 del texto base), y la segunda
para aprender a formalizar el cómo abordar cada uno de ellos mediante
AE´s (estudiar el epígrafe 12.3 del texto base). Finalmente, los epígrafes
12.4 y 12.5 del texto base se corresponden con la sección 12.4 del
temario y requerirán de una lectura atenta para conocer, desde un
punto de vista práctico, algunas de las estrategias y mecanismos implementados
en este contexto. En este sentido, se recomienda revisitar la sección
8.5.2 del texto base, donde ya se adelantaban ejemplos prácticos de
cómo abordar el manejo de restricciones.
Tema 13 Formas especiales de evolución
Objetivos:
El objetivo de este tema es describir tres formas especiales de evolución.
La primera de ellas se caracteriza por la existencia de varias poblaciones
de manera que la evolución de una población influye en la evolución
del resto. Dicha influencia puede ser cooperativa o competitiva. En
la segunda forma especial de evolución que se describe en el presente
tema, el usuario juega un papel fundamental en la selección de los
mejores individuos. Dicha selección se lleva a cabo exclusivamente
a partir de las preferencias del usuario, que tiene una interacción
directa con el sistema. Por último, existen ciertos problemas que
se caracterizan por dar lugar a una función de adaptación que varía
con el tiempo. Estos problemas requieren técnicas evolutivas especiales
para seguir la pista del óptimo global.
Orientaciones:
Existen tres partes bien diferenciadas en el presente tema. En la
primera se describe la coevolución, un tipo de evolución en el que
diferentes poblaciones evolucionan por separado, aunque existe una
importante influencia de cada población sobre el resto. Existen formas
de coevolución de naturaleza completamente opuesta: unas se basan
en la cooperación entre las distintas poblaciones y otras se basan
en la competición entre las mismas.
La segunda parte del tema se dedica a la evolución interactiva, en
la que el usuario se integra en el sistema para decidir según sus
preferencias qué individuos son los mejor adaptados y cuáles no. Este
tipo de evolución encuentra aplicación directa en dominios como el
diseño o el arte.
La última parte del tema hace referencia a los dominios dinámicos
o no estacionarios. En dichos dominios no se puede definir una función
de adaptación que permanezca invariable a lo largo del tiempo. Por
tanto, el óptimo global o los óptimos locales irán cambiando su localización
en la población y se requerirán técnicas especiales para seguirles
la pista.
Tema 14 Trabajando con algoritmos evolutivos
Objetivos:
Los principales objetivos que se abordan en el presente tema son los
siguientes:
1.Ilustrar el hecho de que diferentes tipos de problemas (objetivos)
implican diferentes formas de diseñar y trabajar con AE's.
2.Enumerar y describir distintos índices para medir las prestaciones
de un AE.
3.Describir distintas estrategias para realizar comparaciones experimentales
entre distintos AE's (benchmarking).
Orientaciones:
El alumno deberá realizar un estudio detallado de los epígrafes 14.2.
14.3 y 14.4 del texto base. El primero le ayudará a identificar el
tipo de prestaciones a medir en un AE en función de los objetivos
que demanda el problema a resolver (sección 14.1 del temario). Con
el estudio del segundo epígrafe aprenderá un conjunto de índices típicos
utilizados para medir cuantitativamente las prestaciones de un AE
(sección 14.2 del temario). Y con el estudio del tercer epígrafe indicado,
se familiarizará con el uso de varias estrategias para comparar distintos
tipo de AE's (sección 14.3 del temario). Finalmente, se recomienda
la lectura de los contenidos del epígrafe 14.5 del texto base en el
que el alumno encontrará un ejemplo de aplicación relacionado con
los asuntos descritos a lo largo del tema.
3 Actividades y plan de trabajo
3.1 Actividades prácticas programadas
- Búsqueda de información en la web de distintos recursos relacionados
con la computación evolutiva
- Familiarización con entornos para el diseño y ejecución de algoritmos
evolutivos
- Programación de algoritmos evolutivos
3.2 Otras actividades prácticas programadas
- Lectura de bibliografía complemetaria
- Lectura de artículos
- Escritura de un informe técnico sobre una tema concreto
- Preparación de las diapositivas correspondientes a la presentación
oral de un tema
3.3 Plan de trabajo
El estudio de los contenidos teóricos y la realización de actividades
se repartirán entre siete periodos que abarcan desde el 15 de Noviembre
hasta el 30 de Junio. Durante el último periodo, que coincide con
el mes de Junio, se consensuará y revisará el esquema de proyecto
que el alumno deberá haber presentado en su versión definitiva el
15 de Septiembre para su evaluación. La secuencia de la planificación
temporal es la siguiente:
15 Noviembre a 15 de Diciembre: Temas 1, 2 y 3.
16 de Diciembre a 31 de Enero: Temas 4 y 5,
1-28 de Febrero: Temas 6 y 7.
1-31 de Marzo: Tema 8 y 9.
1-30 de Abril: Tema 10, 11 y 12.
1-31 de Mayo: Tema 13 y 14.
1-30 de Junio: Consenso y revisión del esquema de proyecto fin de
curso.
15 de Septiembre: Recepción de la versión final del proyecto para
evaluación.
4 Evaluación
El procedimiento de evaluación se llevará a cabo principalmente a
partir de la realización por parte del alumno de un trabajo final,
aunque también se tendrán en cuenta las actividades realizadas a lo
largo del curso. Dicho trabajo consistirá en la elaboración de un
informe técnico sobre una parte del temario de la asignatura que sea
consensuada entre el alumno y el equipo docente. El informe deberá
revisar el estado del arte sobre un apartado concreto del temario
de la asignatura y dar sugerencias sobre posibles mejoras que den
lugar a futuras líneas de investigación. Dichas mejoras deberían quedar
fundamentadas a partir de un estudio teórico o de la aplicación a
un problema concreto.
En la evaluación del trabajo final se valorará: la claridad y concisión
en la redacción, la adecuada y exhaustiva clasificación de las distintas
metodologías pertenecientes al estado del arte del tema estudiado
(incluyendo las aparecidas en años más recientes), la crítica fundamentada
de dichas metodologías identificando ventajas e inconvenientes y,
finalmente, la capacidad innovadora del alumno mediante la sugerencia
de un nuevo método o la mejora de otro ya existente.
El alumno redactará un trabajo de entre 45 y 55 páginas (tamaño DIN-A4,
a doble espacio y tamaño de letra 11pt.) que contenga al menos los
siguientes apartados:
- Título y autor
- Resumen no mayor de 250 palabras del contenido del trabajo
- Introducción al tema tratado en el trabajo
- Trabajo relacionado que detalle el estado del arte sobre el tema
elegido
- Crítica donde aparezca un juicio personal del alumno sobre las ventajas
e inconvenientes de los métodos descritos en el apartado anterior
y sugerencias de posibles mejoras a los mismos
- Resultados donde se expliquen las mejoras sugeridas en el apartado
anterior, si es posible apoyadas en un detallado estudio teórico,
empírico o mixto
- Líneas futuras de investigación que indiquen cómo se podría continuar
la investigación iniciada por parte del alumno y qué resultados de
interés son previsibles
- Conclusiones obtenidas
- Referencias bibliográficas mencionadas en el texto del trabajo
Reseña del profesorado
CARMONA SUÁREZ, ENRIQUE JAVIER:
Doctor por la UNED (Departamento de Inteligencia Artificial, año 2003).
Desde ese mismo año es profesor titular de escuela universitaria en
dicho departamento, en el que imparte docencia en las carreras de
Ingeniería Técnica en Informática de Sistemas y de Ingeniería Informática.
Sus principales líneas de investigación se centran en el área del
aprendizaje automático y en la aplicación de sus distintas técnicas
(algoritmos evolutivos, redes neurofuzzy árboles de decisión, etc.)
a distintos campos: minería de datos, medicina, visión artificial
y video-vigilancia.
e.mail:ecarmona@dia.uned.es
Web personal:http://www.ia.uned.es/personal/ejcarmona
FERNÁNDEZ GALÁN, SEVERINO:
Doctor por la UNED (Departamento de Inteligencia Artificial, año 2003).
Desde ese mismo año es profesor titular de escuela universitaria en
dicho departamento, en el que imparte docencia en las carreras de
Ingeniería Técnica en Informática de Sistemas y de Ingeniería Informática.
Sus principales líneas de investigación se centran en la computación
evolutiva y las redes bayesianas.
e.mail: seve@dia.uned.es
Web personal: http://www.ia.uned.es/personal/seve
| |
|
|
