Download What is an Evolutionary Algorithm?
Document related concepts
Transcript
¿Qué es un Algoritmo Evolutivo? Computación Evolutiva Dr. Gregorio Toscano Pulido Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Las siguientes diapositivas fueron tomadas de las notas de A.E. Eiben, J.E. Smith (Capítulo 2 de su libro Introction to Evolutionary Computing) Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Contenido Esquema básico de un AE Componentes básicos – Representación / Evaluación / Población / Selección / Recombinación / Mutación / Selección de sobrevivientes/ Término Ejemplos : eight queens / knapsack Comportamiento típico de AEs CE en el contexto de optimización global – Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Métafora de la CE Una población de individuos existe en un ambiente con recursos limitados Compiten por dichos recursos causa selección de los invididuos más aptos (son aquellos que están mejor adaptados al ambiente) Estos individuos actuan como semillero para la generación de nuevos invididuos a través de recombinación y mutación Los nuevos individuos evalúan su aptitud y compiten (posiblemente también contra los padres) por la superviviencia. A través del tiempo la selección natural causa un incremento en la aptitud de la población Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Los AEs caen en la categoría de algoritmos de “generación y prueba” Son algoritmos basados en población y estocásticos Los operadores de variación (recombinación y mutación) crean la diversidad necesaria y de ese modo facilitan el cambio La sección reduce la diversidad y actúa como una fuerza que incrementa la calidad Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Esquema general de un AE Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Pseudo-código típico de un EA Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? ¿Cuáles son los diferentes tipos de AEs? Hitóricamente diferentes sabores de AEs han sido asociados con diferentes representaciones – – – – Como mejor estrategia siga: – – Cadenas binarias : Algoritmos genéticos Vectores de valores reales: Estrategias evolutivas Máquinas de estado finito: Programación Evolutiva Árboles LISP: Programación Genética Escoja la represenciación que se ajusta más a su problema Escoja operadores de variación que se ajuste a la representación Los operadores de selección son independientes de la representación (únicamente usan la aptitud) Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Representaciones Soluciones candidatas (individuos) existen en el espacio genotípico Son codificados en cromosomas, los cuales existen en el espacio genotípico – – Codificación: fenotipo=> genotipo (no necesariamente uno a uno) Decodificación: genotipo=>fenotipo (debe ser uno a uno) Cromosomas contienen genes, los cuales están en posiciones llamadas loci (sing. locus) y tienen valores (alelos) Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Función de Evaluación (Aptitud) Representa el requerimiento a la que la población necesita adaptarse también es conocida como función calidad o función objetivo Asigna un único valor real a cada fenotipo, el cual forma las bases para la selección – Entre más valores diferentes mejor Típicamente hablamos de que la apttud tiene que ser maximizada Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Población Mantiene a las posibles soluciones Usualmente tiene un tamaño fijo y es un conjunto de genotipos Algunos AEs sofisticados declaran un espacio estructural en la población e.g. un grid Los operadores de selección usualmente toman toda la población en cuenta i.e. las probabilidades de reproducción son relativas a la generación actual La Diversidad de una población se refiere a número de diferentes aptitudes/fenotipos/genotipos actuales Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Mecanismo de Selección de Padres Asigna diferentes probabilidades a los individuos para ser padres (dependiendo de su aptitud) Usualmente son probabilísticos – Usualmente las soluciones de mayor calidad son padres más frecuentemente que las de baja calidad pero no es garantizado – Aún el peor en la generación actual tiene una probabilidad de no-cero de llegar a convertirse en padre Esta naturaleza estocástica puede ayudar a escapar de óptimo local Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Operadores de variación Su rol es generar nuevas soluciones candidatas Usualmente son divididas en dos tipos de acuerdo a su aridad (número de entradas): – – – Aridad 1 : operadores de mutación Aridad >1 : operadores de recombinación Aridad = 2 típicamente llamada cruza Hay mucho debate sobre la importancia relativa de la recombinación y la mutación – – Actualmente la mayoría de los AEs usan ambas Escoger un operador de variación específico depende de la representación Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Mutación Actúa sobre un genotipo y entrega otro Elementos de aleatoridad es indispensable y lo diferencia de otros operadores heurísticos unarios La importancia atribuida depende de en la representación y dialecto: – – – GAs Binarios – operador responsible de preservar e introducir diversidad PE para MEF’s/ variables continuas – sólamente como un operador de búsqueda PG – dificilmente usado Puede garantizar percolación de espacios de búsqueda y por lo tanto pruebas de convergencia Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Recombinación Transmite información de padres a hijos La información que será transmitida es estocástica La mayoría de los hijos podrían ser peores o iguales a los padres La esperanza es que si se combinan elementos del genotipo que mejoren los rasgos, algunos hijos sean mejores Principalmente han sido usados por milenios por agricultores y ganaderos Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Selección de sobrevivientes También se le conoce como reemplazo La mayoría de los AEs usan una población fija de tal manera no pueden pasar padres e hijos a la siguiente generación Usualmente determinística – Basado en aptitud : e.g., jerarquizar padres e hijos y tomar el mejor – Basados en edad: haz tantos hijos como padres y elimina los padres Algunas veces se realiza una combinación (elitismo) Computación Evolutiva ¿Qué es un Algoritmo Evolutivo? Inicialización/Término La inicialización usualmente es aleatoria – – Se necesita asegurar tanto la dispersión como la mezcla de los posibles valores de los alelos Puede incluir soluciones existentes, o usar heurísticas específicas para sembrar la población El término es verificado cada generación – – – – Se alcazó alguna aptitud (conocida/esperada) Se alzanzó algún máximo valor permitido de generaciones Se alcanzó algún mínimo valor de diversidad Se alcanzó algún número de generaciones sin mejorar la aptitud