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