Accesos directos a las distintas zonas del curso
Ir a los contenidos
Ir a menú navegación principal
Ir a menú pie de página
Subject's code : 31101220
Este tema se divide en los siguientes apartados:
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
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.
2.1 Introducción
2.2 Componentes principales de los algoritmos evolutivos
2.3 Cómo trabaja un algoritmo evolutivo
2.4 Algoritmos evolutivos vs. otras técnicas de optimización global
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.
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
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.
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
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.
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
En este tema se describe 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.
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)
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. También deberá estudiarse en profundidad una de las variantes de este paradigma conocida como Evolución Gramatical (del inglés Grammatical Evolution).
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
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.
8.1 Introducción
8.2 Ejemplos alternativos a la aproximación estática
8.3 Aspectos relevantes para clasificar las técnicas de control dinámico de parámetros
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.
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
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í.
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 diseño de algoritmos meméticos
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).
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
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.
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
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.
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
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.
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
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).
