PDF de programación - Introducción a los algoritmos genéticos

Introducción a los

algoritmos genéticos

Siro Moreno

1/18

Evolución Natural

Selección Natural

Reproducción

3/18

Algoritmos genéticos

• Objetivo: optimizar algo
• Individuo: posible solución

Ejemplo:

• Objetivo: optimizar resistencia aerodinámica

4/18

Individuos

• Conjunto de individuos = población
• Definidos por parámetros.

Ejemplo

5/18

Base
Nitrogenada

ATA GTC CCA TGG ATT GTA ACG GCG

Gen

Traits /
Características

Performances /
Desempeños

Fitness /
Aptitud

6/18

1

Bit

100110100110101100

Gen

Transcripción

x_point_1 = 0.3456

Problema

aero_lift = f(x,y,z)

Traits /Características

Performances / Desempeños

Función de Fitness

fitness = f(results)

Fitness /Aptitud

7/18

Transcripción

Tipo

Efecto de
cambio de 1 bit

Probabilidad
de valores

Bits con peso

Bits sin peso

8/18

Función de Fitness

• La función más importante del algoritmo
• Condensa en un solo valor la calidad de una

solución.

• Suele contener condicionales para desechar

zonas no interesantes.

9/18

Bucle principal: Generación

Población inicial

Análisis

Reproducción

Selección

José Carlos Cortizo Pérez

order_242

Grendelkhan

10/18

Selección

• Mortalidad diferencial, aleatoria o semi-

aleatoria

• Elegir qué individuos mueren y cuáles se

reproducen

• Equilibrio:

– Suficientes plazas para la siguiente generación
– Pérdida de información

11/18

Reproducción

• Reproducción diferencial, aleatoria o semi-

aleatoria.

• Genera una población nueva
para la siguiente generación.

• 2 fases:

– Cruzamiento
– Mutación

• Si se conservan pocos de la

generación anterior: Elite Clones

12/18

Cruzamiento

• Padre 1 : 10010100101010010101
• Padre 2 : 10101001100101001100
• Hijo: 10110100101101001101



• Parámetros:

– Número de puntos de corte
– Posición de los puntos de corte

13/18

Mutación

• Añade variedad al acervo genético (gene pool)
• Permite explorar soluciones nuevas



• Antes de la mutación: 1001010010101
• Después de la mutación:1011010010001



14/18

Apertura y cierre del algoritmo

• Población inicial aleatoria



• Criterio de parada:

– Número de generaciones
– Estabilidad

15/18

Modular el algoritmo:

El dilema exploración-explotación

• Exploración:

– Buscar soluciones nuevas
– Escapar de máximos locales
– Añade ruido

• Explotación

– Afinar los máximos encontrados
– Conservarlos
– Atasca en máximos locales

Foto: Rob Young

16/18

Python

• Fáciles de programar:

– Individuo: objeto
– ADN: lista, tupla, np array, etc.
– Genes, traits, performances: diccionarios
– Población: lista de objetos

• DEAP (Distributed Evolutionary Algorithms in

Python)
– Google -> “genetic algorithm python”

17/18

Muchas gracias