Algoritmos Genéticos

Introducción

Inspirados en mecanismos naturales. El mejor avanza y transmite sus características.

Funcionan bien en problemas complejos y multiobjetivos, sobre todo de optimización.

Son técnicas guiadas con un componente aleatorio, evitamos quedarnos estancados en un mínimo local, pues recorremos gran parte del espacio de búsqueda. La aleatoriedad mejora la exploración.

Equilibrio entre exploración (método de búsqueda) y explotación (método de mejora). AG buenos exploradores (búsqueda global), algoritmos de búsqueda local buenos explotadores.

Terminología

Evolución Natural           Resolución del Problema

Medio                                               Problema

Individuo                                          Candidato a solución

Cromosoma                                     Solución codificada

Gen                                                    Parte de solución codificada

Aptitud                                              Calidad de solución

Selección natural                            Reutilización de buenas soluciones

Fenotipo                                           Característica (físico)

Genotipo                                          Código de característica

Selección                                          Identificar mejores soluciones (no siempre)

Reproducción                                  Cruzar y transmitir características para mejorarlas

Mutación                                          Variación en características que crean nuevas 

Competición                                    Comparar soluciones en situaciones particulares    

Diseño

Diseñar y construir cromosoma.

Elegir codificación adecuada.

Diseñar y construir función de evaluación cuidadosamente

Seleccionar operadores

Elegir mecanismo de reemplazamiento de población

Elegir parámetros que controlan funcionamiento de AG 

Imponer criterios de terminación.

                                                                           

Aclaraciones

Generación aleatoria en un rango

Función de evaluación devuelve aptitud bruta de cada cromosoma y se asigna probabilidad de reproducción.

Criterios de selección posibles: proporcional(por probabilidad), rango, ruleta (posición por cada individuo), universal estocástico(todos comprobados a la vez), por torneo (se comparan individuos).

Cruzamiento: Intercambio de genotipo mezclando 2 individuos aleatoriamente, no todos los seleccionados se cruzan.

Mutación:  Variación aleatoria en el genotipo que restaura la diversidad. La tasa de mutación debe ser pequeña, sino no funciona. 

Reemplazamiento: generacional (se sustituyen todos), steady state (se sustituye un %), elitismo (preservar mejores cromosomas)

Criterios de terminación: max nº de iteraciones, poca mejora tanto en población como mejor individuo, tiempo de cómputo máximo.

Presentación y análisis: comparar evolución de variables significativas (aptitud media, aptitud del mejor,...)

Validación de resultados: Entre 10 y 15 ejecuciones con mismos parámetros, obtención de valores medios.