Agenda Introducción Cómo funcionan Ejemplo Por qué funcionan Algoritmos genéticos paralelos
Introducción Provienen de la familia de modelo computacional basado en la evolución Introducidos por Holland en 1975 Proveen una solución potencial a un problema específico en una estructura tipo cromosoma y aplican operadores de recombinación para preservar la información crítica Cualquier modelo basado en población que usa selección y recombinación para generar nuevos elementos en el espacio de búsqueda
Introducción Población Conjunto de soluciones potenciales, donde la población inicial puede ser elegida randómicamente Cambia con el tiempo pero su tamaño se mantiene Individuo Elemento de la población Cada individuo es representado por una cadena de caracteres
Introducción Crossover Dos nuevos individuos pueden ser obtenidos de dos padres en el mating pool, recombinando a ambos padres Mutación Individuos en el mating pool también pueden cambiar a través de mutación randómica Resultado -> Un nueva generación El proceso se repite y converge a una población con individuos muy similares entre si
Algoritmo genético Canónico Los individuos son cadenas binarias de largo fijo codificadas según el problema a resolver En general las poblaciones iniciales se eligen de forma randómica Luego de creada la población inicial se le aplica a cada individuo la función de evaluación En base al resultado de dicha función se calcula el fitness Fitness = fi/f
Algoritmo genético Canónico Una vez calculado el fitness de cada individuo, se pasa a la selección para generar la generación intermedia Los individuos con mayor nivel de fitness son copiados en la generación intermedia Stochastic Sampling with Replacement Remainder Stochastic Sampling
Algoritmo genético Canónico Crossover Se eligen pares de individuos randómicamente que serán recombinados con una probabilidad p Se elige un punto aleatorio del individuo y se intercambian sus partes Mutación Es aplicada con una probabilidad muy baja a cada bit Diferentes variantes Generar un nuevo bit Invertir un bit
Algoritmo Repetir para cada individuo i evaluar y calcular fitness f(i) Crear mating pool de tamaño N basado en los valores de fitness f(i) para i=1 hasta (N/2) quitar pares de individuos {j,k} del mating pool recombinar usando los individuos j y k aplicar mutación Hasta ‘condición de parada’
| Página siguiente |