Breve introducción a Algoritmos Genéticos
Tags: machinelearning, datascience, python
Published: 2020-01-24 17:20:54



(el contenido también se encuentra disponible en formato de [IPython notebook](https://colab.research.google.com/drive/13jNL0kJeutrybEwhKcMGyhUlQSAslWRP))

## ¿Qué es un algoritmo genético?

Un algoritmo genético es un método para resolver un problema inspirado en el proceso de [selección natural](https://es.wikipedia.org/wiki/Selecci%C3%B3n_natural) propuesto por Charles Darwin:

> As many more individuals of each species are born than can possibly survive; and as, consequently, there is a frequently recurring struggle for existence, it follows that any being, if it vary however slightly in any manner profitable to itself, under the complex and sometimes varying conditions of life, will have a better chance of surviving, and thus be naturally selected. From the strong principle of inheritance, any selected variety will tend to propagate its new and modified form

Hay muchas variaciones de dichos algoritmos pero todos siguen a grandes rasgos este patrón:

1. Generar una población de individuos (o _cromosomas_ en el léxico de los algoritmos genéticos)

2. Evaluar a los individuos de la población por una métrica de aptitud (conocido como _fitness_)

3. Sólo quedarse con los N sujetos de la población _más aptos_

4. Crear una nueva generación de individuos a partir de los más aptos a través de:


  1. cross breeding: "cruza" entre individuos
    
  2. mutations: mutaciones aleatorias

    
5. Volver a __paso 2__ y repetir


### ¿Qué problemas se pueden resolver?

Los problemas atacados por estos algoritmos son en general de optimización de funciones (más adelante veremos como esto se puede generalizar a soluciones más interesantes), por ejemplo, dada una función:

y = 8x - 2x^2


```python
def f(x): return 8 * x - 2 * x**2 
```

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/0qry9gjbq5q9s77wupz5.png)

Nos interesaría encontrar el punto máximo, es decir el valor de `x` que maximiza `y`.

Vamos a usar un algoritmo genético para esto, apoyándonos en la [librería __evol__ de python](https://github.com/godatadriven/evol)

### Paso 1: Primera Generación

Para comenzar tenemos que armar una primera generación de individuos o cromosomas, en este caso __los individuos serían distintos valores de `x`__.

Imaginemos que no sabemos dónde está el máximo de la función pero tenemos una vaga idea de _en qué rango puede estar_. Para este ejemplo vamos a suponer que el valor está entre -1.000.000 (menos un millón) y 1.000.000 (un millón).

Nuestra primera generación tomará valores aleatorios en este intervalo:

```python
np.random.seed(1234) # make results reproducible.


def random_guy(): return np.random.randint(low=-1_000_000, high=1_000_000)


initial_generation_size = 100
first_generation = [random_guy() for _ in range(initial_generation_size)]
```

Con esto podemos crear nuestro objeto `Population`. También le pasamos la función a optimizar ($f(x)$ definida más arriba) y le aclaramos a `evol` si la idea es maximizar o minimizar dicha función:

```python
pop = Population(chromosomes=first_generation, eval_function=f, maximize=True)
```

### Supervivencia del más apto

De nuestra población inicial queremos quedarnos sólo con el 10% que mejor performó, los más aptos. Para esto tenemos la función `survive`:


```python
survivors = pop.survive(fraction=0.1)
```

### CrosBreeding y Mutaciones

Con los sobrevivientes vamos a crear una nueva generación, producto de _breeding_ y mutaciones aleatorias. 

Para esto tenemos que definir tres funciones:

1) una para elegir dos padres del conjunto de supervivientes (lo haremos al azar)

2) otra para definir cómo dos individuos de la población crean un nuevo individuo 😏

3) una última para determinar las mutaciones aleatorias

Entonces:

```python

def pick_parents(population):
    mom, dad = np.random.choice(population, size=2)
    return mom, dad


# the child is the mean between two parents.
def make_child(mom, dad):
    return (mom + dad) / 2


# add gaussian noise with mean zero.
def random_noise(individual, sigma):
    noise = np.random.normal(loc=0, scale=10) * sigma
    return individual + noise


new_generation = survivors.breed(parent_picker=pick_parents, combiner=make_child).mutate(random_noise, sigma=1)
```

### It's evolution, baby

Con la nueva generación podemos repetir el proceso indefinidamente (seleccionar, cruzar, mutar). 

Vamos a hacerlo unas cuantas veces y nos quedamos con el individuo más apto de cada generación:


```python
def fittest(generation):
    fit = sorted(generation.evaluate(), key=lambda x: x.fitness)[-1]
    return fit.chromosome


generations = 120
fittest_of_each_gen = []

gen = new_generation
for _ in range(generations):
    survivors = gen.survive(fraction=0.1)
    new_gen = survivors.breed(parent_picker=pick_parents, combiner=make_child).mutate(random_noise, sigma=1)
    fittest_of_each_gen.append(fittest(new_gen))
    gen = new_gen
```


### Analizando los resultados

Volvamos otra vez a la función original y sobre la línea agreguemos los "mejores exponentes" de cada generación.

Las generaciones van de menor a mayor desde el azul (cool) al rojo (warm). También graficamos el error, o sea qué tan alejados estamos del valor máximo real, en función del número de generación:

![Alt Text](https://thepracticaldev.s3.amazonaws.com/i/tdwkdv0nb2ow44u98bii.png)

Como vemos aproximadamente __en la generación 100__ el valor empieza a converger con el máximo real.

### Conclusión

Pero, ¿Tiene sentido utilizar está técnica? después de todo, sabemos que la forma de encontrar el mínimo de una función como 

`f(x) = 8x - 2x^2`

es tomar su derivada

`f'(x) = 8 - 4x`

y encontrar el valor donde el gradiente es cero, en este caso 

`f'(x) = 8 - 4 * 2 = 0`

La respuesta es que, si bien para este caso es un _overkill_, los algoritmos genéticos son un __método numérico__ que nos permite encontrar resultados aceptables en funciones no diferenciables o de las que no se conoce un __método análitico__.


### Próximamente

Con esto concluimos esta breve introducción.

En un próximo post, analizaremos como performa este mismo algoritmo genético para resolver el conjunto de ecuaciones que [presentó el ministro de educación](https://twitter.com/trottanico/status/1216136074390581248) hace unas semanas:

<img src="https://i.imgur.com/nScQcJY.png" width=500>