Computación Evolutiva:
Enfoque alternativo para abordar problemas complejos de:
Búsqueda
Aprendizaje
Trabaja a través de modelos computacionales de procesos evolutivos
Algoritmos evolutivos:
Implantaciones concretas de tales modelos
Propósito: guiar una búsqueda estocástica
haciendo evolucionar un conjunto de estructuras y
seleccionando de modo iterativo las más adecuadas
Contexto
Forma parte de un conjunto de metodologías de resolución que remedan con mayor o menor exactitud procesos naturales: COMPUTACIÓN NATURAL
Por ejemplo:
Redes Neuronales
Solidificación Simulada
Algoritmos Genéticos
Clasificación de procedimientos de optimización
Basada en la naturaleza de las soluciones
NUMÉRICOS (completamente especificada en términos de un conjunto de m parámetros)
COMBINATORIOS (basadas en el orden)
Clasificación de procedimientos de optimización
Basada en el grado de aleatoriedad que se le da al proceso de búsqueda
DETERMINISTAS (procedimiento de búsqueda dirigido: en las mismas condiciones de partida proporciona idénticos resultados)
Requiere mucho conocimiento adicional de la función objetivo
ALEATORIAS (al azar: usa argumentos estadísticos) No requiere ninguna información adicional; se puede aplicar a cualquier tipo de problema
ESTOCÁSTICAS (orientadas: la componente determinista orienta la dirección de búsqueda, y la aleatoria se encarga de la búsqueda local )
Clasificación de procedimientos de optimización
Basada en la información disponible sobre la función a optimizar
BÚSQUEDAS CIEGAS (el proceso a optimizar funciona como caja negra)
BÚSQUEDAS HEURÍSTICAS (se dispone de cierta información explícita sobre el proceso a optimizar.)
Se la aprovecha para guiar la búsqueda
Teoría moderna de optimización
Añadir conocimiento específico a un problema
En problemas reales de mediana complejidad resulta muy difícil
Es fundamental:
Cuánto añadir?
Cómo añadirlo?
El conocimiento específico sólo sirve cuando es de muy buena calidad
Cuidado! Acentúa la tendencia a estancar la búsqueda en óptimos locales
Las técnicas clásicas de búsqueda determinística y analítica no suelen ser de gran utilidad
Esto obliga a desarrollar nuevos paradigmas
Menos analíticos
Más sintéticos
LA BÚSQUEDA DE ANALOGÍAS CON LA NATURALEZA ES MÁS UNA NECESIDAD QUE UNA PREFERENCIA ESTÉTICA
No se persigue una simulación de los procesos naturales
Es más bien una emulación de dichos procesos
Un AE será tanto mejor cuanto mejores resultados proporcione en la resolución del problema planteado
Independientemente de su fidelidad a la biología
La mayoría son enfoques simplistas desde el punto de vista biológico
Pero lo suficientemente complejos como para proporcionar mecanismos de búsqueda robustos y potentes
Estructura genérica de los AEs
AE es cualquier procedimiento estocástico de búsqueda basado en el principio de evolución.
Principio de Evolución:
Supervivencia del más apto
Adaptación al entorno
Los más aptos tienen
más posibilidades de sobrevivir
más oportunidades de transmitir sus características a las generaciones siguientes
Población: conjunto de candidatos a soluciones de un problema
Al ejecutar un AE una población de individuos es sometida a
una serie de transformaciones con las que se actualiza la búsqueda
y después de un proceso de selección que favorece a los mejores individuos
GENERACION
TRANSFORMACIÓN
SELECCIÓN
Estructura
La CE trata de desarrollar mecanismos estocásticos de búsqueda en paralelo con los que mejorar las técnicas clásicas de búsqueda determinista
Para que la mejora sea efectiva, tales mecanismos deben estar dirigidos (procedimiento de selección)
Herramientas para poder emular un proceso de evolución de un AE
Individuos: población de posibles soluciones debidamente representadas
Selección: procedimiento basado en la APTITUD de los individuos
Transformación: construcción de nuevas soluciones a partir de las disponibles
Implantación sobre este esquema:
BeginAlgorithm (EvolutionAlgorithm)
P[0]=InitPop(); Población Inicial
FitP[0]=EvalPop(P[0]); Aptitudes iniciales
for (t=0; t