---
# System prepended metadata

title: Practica 15 Algoritmos Genéticos

---

# Practica 15 Algoritmos Genéticos
### Solución de problemas mediante Algoritmos Genéticos Estacionarios
**Profesora**: Dra. Yenny Villuendas Rey <br>
**Escuelas**: <br> $^{1}$ Escuela Superior de Cómputo del IPN <br> $^{2}$ Centro de Investigación en Computación del IPN <br>
**Equipo**: <br>
- $^{1}$ Enya Quetzalli Gómez Rodríguez
- $^{2}$ Luis Fernando Quezada Mata
- $^{2}$ Osvaldo David Velázquez González

[Ver en línea](https://hackmd.io/@metah/practica15)

<br>

<style tyle="text/css">
p {
text-align: justify;
}
</style>


### **1. Enuncie las ventajas y desventajas de los Algoritmos Genéticos.**

**Ventajas [1, 2]:**
* <div class=text-justify>Es fácilmente paralelizable, pueden explorar el espacio de soluciones en múltiples direcciones al mismo tiempo.</div>
* <div class=text-justify>Los algoritmos GA  realizan  un  amplia  exploración, logrando espacar eficientemente de los óptimos locales y alcanzar el óptimo global.</div>
* <div class=text-justify>Se puede encontrar una solución sin un análisis profundo previo del problema.</div>
* <div class=text-justify>Los algortimos GA trabajan bien en problemas complejos y cambiantes, así como aquéllos en los que la función objetivo es discontinua, ruidosa, o que tiene muchos óptimos locales, ademas de poner soportar las optimizaciones multi-objetivo.</div>
* <div class=text-justify>Los algoritmos GA puede operar en varias representaciones.</div>

**Desventajas [1, 2]:**

* <div class=text-justify>La función objetvo es muy sensible para los algotimos GA, ya que si se elige mal o se define incorrectamente, puede que sea incapaz de encontrar una solución al problema. </div>
* <div class=text-justify>La elección de los parámentros (tamaño de la población, cruzamiento, selección de padres, mutación, entre otras más) de los algoritmos GA puede llegar a ser muy complejo. Una mala elección en los parámetros puede provocar un mal desempeño.</div>
* <div class=text-justify>Consumen mucho tiempo de ejecución y potencia de cómputo</div>
* <div class=text-justify>Existe el riesgo de encontrarse con una convergencia prematura; es decir, se puede reproducir abundantemente un individuo haciendo que merme la diversidad de la población demasiado pronto, provocando que converja hacia un óptimo local, el cual representa a ese individuo. </div>

<br>

### **2. Diga las diferencias entre fenotipo y genotipo.**

El fenotipo es una posible solución del problema, está posible solución puede tomar varias formas, como números reales o enteros. Por otro lado, el genotipo (tambien llamado cromosoma) esta constituido apartir del fenotipo, el cual es su representación (codigicación) de sus caracteristicas. El genotipo o cromosoma se representan generalmente como cadenas, donde cada componente representa un gen; es decir, una de las variables del problema a resolver. A continuación, se plasma un ejemplo. 

<div style = 'text-align:center;'>
<img  src="https://i.imgur.com/T62m4GR.png" width="400px"><br>
Figura 1. Descripción grafica del fenotipo, genotipo, cromosoma y gen.
</div>

### **3. Mencione 3 operadores de Mutación. Explique el funcionamiento de uno de ellos.**

* <div class=text-justify> Mutación de un gen para representación binaria.</div>
* <div class=text-justify> Mutación uniforme para representación real.</div>
* <div class=text-justify> Mutación SWAP para representación de orden.</div>

La **mutación de un gen** es un operador de mutación para representaciones binarias que consiste en seleccionar aleatoriamente un locus en el cromosoma del individuo en cuestión y negar el gen correspondiente.

Considere el siguiente caso para ejemplificar el operador de mutación de un gen. Supóngase que el cromosoma del individuo al que se le aplicará el operador de mutación es el siguiente:

\begin{equation}
x = (1,1,0,1,0,0,1)
\end{equation}

Se elige entonces un locus aleatorio (en este caso entre $1$ y $7$), supóngase $5$; entonces, se niega el gen en la posición $5$ del cromosoma (marcado en rojo):

\begin{align}
x = (1,1,0,1,\color{red}0,0,1)
\\
x' = (1,1,0,1,\color{red}1,0,1)
\end{align}

en donde $x'$ denota el cromosoma ya mutado.

<br>

### **4. Mencione 3 operadores de Cruzamiento. Explique el funcionamiento de uno de ellos.**

* <div class=text-justify> Operador de cruce en dos puntos para representación binaria. </div>
*  Operador de cruce BLX-$\alpha$ para representación real.
* <div class=text-justify> Operador de cruce OX para representación de orden.</div>

El **operador de cruce OX** es utilizado  para representaciones de orden (como en el problema del viajero vendedor). Éste consiste en seleccionar aleatoriamente dos puntos de corte en un cromosoma; después, copiar la subsecuencia de genes entre estos dos puntos del cromosoma de uno los padres ($P_{1}$) al cromosoma del hijo ($c_{1}$); y por último, colocar los genes del segundo padre ($P_{2}$) después del segundo punto de corte del cromosoma de $c_{1}$, conservando estos el mismo orden que tenían en $P_{2}$ pero omitiendo aquellos que fueron copiados de $P_{1}$. Para obtener un segundo hijo ($c_{2}$) se cambian los roles de los padres y se aplica el mismo procedimiento con los mismos puntos de corte.

Considere el siguiente caso para ejemplificar el operador de cruce OX. Se seleccionan dos padres $P_{1}$ y $P_{2}$:

\begin{align}
P_{1} = (5,4,3,6,1,2)
\\
P_{2} = (3,1,6,2,5,4)
\end{align}

Se eligen aleatoriamente dos puntos de corte (en este caso entre $1$ y $5$), supónganse $3$ y $5$; entonces, se copia a $c_{1}$ la subsecuencia de genes de $P_{1}$ (marcada en rojo) entre estos dos puntos:

\begin{align}
P_{1} = (5,4,3,\color{red}6,\color{red}1,2)
\\
c_{1} = (\_,\_,\_,\color{red}6,\color{red}1,\_)
\end{align}

Por último, después del segundo punto de corte se colocan en $c_{1}$ los genes de $P_{2}$ (marcados en verde) en el mismo orden que aparecen en su cromosoma, omitiendo aquellos que fueron copiados de $P_{1}$ (marcados en rojo):

\begin{align}
P_{2} = (\color{green}3,1,6,\color{green}2,\color{green}5,\color{green}4)
\\
c_{1} = (\color{green}2,\color{green}5,\color{green}4,\color{red}6,\color{red}1,\color{green}3)
\end{align}

Para obtener un segundo hijo $c_{2}$ se repite el mismo procedimiento usando los mismos puntos de corte e intercambiando el rol de los padres, dando lugar en este caso a:

\begin{align}
P_{2} = (3,1,6,\color{green}2,\color{green}5,4)
\\
P_{1} = (5,\color{red}4,\color{red}3,\color{red}6,\color{red}1,2)
\\
c_{2} = (\color{red}3,\color{red}6,\color{red}1,\color{green}2,\color{green}5,\color{red}4)
\end{align}

<br>

### **5. Mencione 3 operadores de Selección. Explique el funcionamiento de uno de ellos.**

* <div class=text-justify> Selección por torneo (TS).</div>
* <div class=text-justify> Selección proporcional (PS).</div>
* <div class=text-justify> Selección por ruleta.</div>

La **selección proporcional** o PS para abreviar, es un operador de selección basado en el fitness de cada individuo en la población. Éste consiste en ordenar a los individuos en función de su fitness y asociar una probabilidad de selección a cada uno dependiendo del orden, es decir, individuos con un fitness altos tendrán una probabilidad alta de ser seleccionados, mientras que individuos con un fitness bajo tendrán una probabilidad baja.

La implementación se realiza como sigue. Dados una población $\mathcal{P}$ y un individuo $i \in \mathcal{P}$, y denotando por $f_{j}$ al fitness de cualquier individuo $j \in \mathcal{P}$, la probabilidad de selección del individuo $i$ se define como:

\begin{equation}
p_{i} = \frac{f_{i}}{\displaystyle\sum_{j \in \mathcal{P}} f_{j}}.
\end{equation}

<br>

### **6. Valore qué impacto tiene el tamaño de la población en la convergencia de un Algoritmo Genético.**

El tamaño de la población de un algoritmo genético es un parámetro sumamente importante, el cual puede afectar al desempeño de dicho algoritmo. La población está constituida por un conjunto de cromosomas, los cuales representan las posibles soluciones del problema. Si el tamaño de la población es muy pequeña, la población de soluciones contiene poca diversidad, el cual puede ocacionar una convergencia prematura, provocando un atascamiento en un óptimo local. **[1]**

<br>

### **7. Dados los problemas resueltos en la clase práctica 2, proponga las estructuras de datos necesarias para su implementación mediante un algoritmo genético estacionario.**

**Problema de la mochila**
 
Se utilizo una matriz *poblacion* de $m \times n$, donde el valor de $m$ refiere a la cantidad de individuos de la población y $n$ a la cantidad de genes que tendra cada individuo.

 
**Problema del viajero vendedor**

Usando $n$ como el número de ciudades y $m$ como la cantidad de individuos en la población:

ciudades - arreglo 1D de longitud $n$
longitudes - arreglo 2D de $n \times n$
población - arreglo 2D de $m \times n$
parents - arreglo 2D de $2 \times n$
childs - arreglo 2D de $2 \times n$
  
**Minimizar función**

$x$ - arreglo con valores reales (persona) de tamaño *gens*
población - arreglo de personas ($x$) de tamaño *people*

<br>

### **8. Diseñe la interfaz de usuario para la solución de los problemas planteados.**

#### **Problema de la mochila**

Primero definimos una función para medir el fitness de un estado (individuo). Asímismo, agregamos las funciones necesarias para el problema de la mochila.
```python=
import random
import copy
import numpy as np

def getscorepoblacion(poblacion):
    dimension = len(poblacion)
    scorepoblacion = [0]*dimension
    for i in range(0,dimension):
        scorepoblacion[i] = getStateScore(poblacion[i])
    return scorepoblacion

def backpackWeight(items): 
  weight = 0
  for i in range(0,len(items)):
    weight += items[i] * available_objects[0][i]
  return weight

def backpackBenefit(items):
  benefit = 0
  for i in range(0,len(items)):
    benefit += items[i] * available_objects[1][i]
  return benefit

def getStateScore(state):
  return backpackBenefit(state)

def isValidState(state):
  if backpackWeight(state) < max_weight_supported_by_backpack and
                            sum(state) < max_number_of_elements_in_backpack:
    return True
  return False

def randomState():
  random.seed(a=None)
  state = [0]*len(available_objects[0])
  while True:
    for i in range(0, len(state)):
      state[i] = random.randint(0,available_objects[2][i])
    if isValidState(state):
      break
  return state
```
Posteriormente, creamos a la poblacion iniciar de manera aleatoria.
```python=
def generapoblacion(sizepopulation):
    population = [0]*sizepopulation
    for i in range(0,sizepopulation):
        while True:
            new = randomState()
            if new not in population:
                break
        population[i] = new
    return population
```
Debido a que vamos a utilizar a la población completa para el cruzamiento, agregamos la funcion del operador de selección por torneo. 
```python=
#OPERADORES DE SELECCION PARA ALGORITMOS GENETICOS
def torneo(poblacion,npadres,k):
    #OPERADOR POR TORNEO
    padres = [] 
    for j in range(0,npadres):
        posiciones = [0]*k
        for i in range(0,k):
            while True:
                posicion = random.randint(1, tpoblacion)
                if posicion-1 not in posiciones:
                    break
            posiciones[i] = posicion-1
            
        concursantes = [0]*k
        #se selecciona al de mejor fitness, el de mayor beneficio
        for i,p in enumerate(posiciones):
            concursantes[i] = scorepoblacion[p]
            
        mejorfitness = max(concursantes)
        ppadre = posiciones[concursantes.index(mejorfitness)]
        padres.insert(j, poblacion[ppadre])
    return padres
```
Asímismo, implementamos los operadores de cruzamiento uniforme, de remplazo elitista y de mutación uniforme.
```python=
#OPERADOR DE CRUZAMIENTO UNIFORME - binario
def uniforme(padres):
    #se crea un vector de cruce (0,1) aleatoriamente
    sizepadres = len(padres[0])
    vector_cruce = [0]*sizepadres
    hijo1 = [0]*sizepadres
    hijo2 = [0]*sizepadres
    for i in range(0, sizepadres):
            vector_cruce[i] = random.randint(0, 1)
            #creamos el hijo1
            if vector_cruce[i] == 0: #copiar de padre0
                hijo1[i] = padres[0][i]
                hijo2[i] = padres[1][i]
            elif vector_cruce[i] == 1: #copiar de padre1
                hijo1[i] = padres[1][i]
                hijo2[i] = padres[0][i]
                
    hijos = [hijo1, hijo2]
    return hijos
```
```python=
#remplazo elitista
def elitist(poblacion,hijos):
    scorepoblacion = getscorepoblacion(poblacion)
    scorehijos = getscorepoblacion(poblacion)
    
    todos = np.array(poblacion + hijos)
    scoretodos = scorepoblacion + scorehijos
    scorearray = np.array(scoretodos)
    mejores = np.argsort(-1*scorearray)
    
    new_poblacion_indices = mejores[0:tpoblacion]
    new_poblacion = todos[new_poblacion_indices].tolist()
    score_new_poblacion = getscorepoblacion(new_poblacion)
    return new_poblacion
```
```python=
def mutacion_uniforme(state,pro_mut):
    tam_state = len(state)
    while True:
        for i in range(0,tam_state):
            ran = random.random()
            if ran < pro_mut:
                random_mutation = random.randint(0,available_objects[2][i])
                state[i] = random_mutation
        if isValidState(state):
            break
    return state
```

Por último, se implementa el algoritmo genético estacionario para el problema de la mochila.
```python=
def GAE_mochila(poblacion,ngeneraciones,pro_cruza,pro_mutp,pro_muth):
    
    resultado = [0]*len(available_objects[0])
    for i in range(0,ngeneraciones):
        #seleecionamos a los padres a cruzar(se usara a toda la poblacion)
        #aleatorio
        hijos = []
        #padres = ruleta(poblacion,2)
        padres = torneo(poblacion,2,3)
        ran = random.random()
        if ran < pro_cruza:
            #cruzamos
            hijos = uniforme(padres)
        #mutamos padres e hijos
        for j in range(0,len(poblacion)):
            poblacion[j] = mutacion_uniforme(poblacion[j],pro_mutp)
        for j in range(0,len(hijos)):
            hijos[j] = mutacion_uniforme(hijos[j],pro_muth)
        #remplazamos, nos quedamos con los mejores (elitista)
        new_poblacion = elitist(poblacion, hijos)
        new_score = getscorepoblacion(new_poblacion)
        poblacion = new_poblacion
        
    aux_poblacion = np.array(poblacion)
    scorearray = np.array(new_score)
    mejores = np.argsort(-1*scorearray)
    mejor_indice = mejores[0]
    resultado = aux_poblacion[mejor_indice].tolist()
    return new_poblacion,resultado
```
Ejemplo

**Input:**
```python=
#INPUT
#Datos de entrada del problema
max_number_of_elements_in_backpack = 10
max_weight_supported_by_backpack = 700
available_objects = [
  [  9,  9, 50,153,230,250],  #Weight
  [150,150,160,200,355,591],  #Benefit
  [  1,  1,  1,  1,  1,  1]   #Max Items
]

#CREAR POBLACION DE TAMAÑO 6
tpoblacion = 6
poblacion = generapoblacion(tpoblacion)
scorepoblacion = getscorepoblacion(poblacion)

print("Poblacion Inicial:")
for i in range(0,tpoblacion):
    print(poblacion[i], "w: ", backpackWeight(poblacion[i]), "\tscore: ",
                                                    scorepoblacion[i])

#este es para la probabilidad de cruzamiento
ngeneraciones = 100
pro_cruza = 0.9    
pro_mutp = 0.6
pro_muth = 0.2
[poblacion_final,resultado] = GAE_mochila(poblacion, ngeneraciones, pro_cruza, 
                                                            pro_mutp, pro_muth)

scorepoblacion_final = getscorepoblacion(poblacion_final)
print("\nPoblación resultante:")
for i in range(0,tpoblacion):
    print(poblacion_final[i], "w: ", backpackWeight(poblacion_final[i]), 
                                        "\tscore: ", scorepoblacion_final[i])

scoreresultado = getStateScore(resultado)
print("Mejor de la poblacion:", resultado, "\tscore: ", scoreresultado)
```
**Output:**
```python=
Poblacion Inicial:
[0, 0, 0, 1, 0, 0] w:  153 	score:  200
[0, 1, 1, 0, 0, 0] w:  59 	score:  310
[0, 1, 0, 1, 1, 1] w:  642 	score:  1296
[1, 0, 1, 0, 1, 0] w:  289 	score:  665
[1, 1, 0, 1, 1, 0] w:  401 	score:  855
[0, 1, 0, 1, 0, 0] w:  162 	score:  350

Población resultante:
[0, 1, 1, 1, 1, 1] w:  692 	score:  1456
[1, 0, 1, 1, 0, 1] w:  462 	score:  1101
[0, 1, 1, 1, 0, 1] w:  462 	score:  1101
[1, 1, 1, 1, 1, 0] w:  451 	score:  1015
[1, 0, 1, 0, 0, 1] w:  309 	score:  901
[1, 0, 0, 1, 1, 0] w:  392 	score:  705
Mejor de la poblacion: [0, 1, 1, 1, 1, 1] 	score:  1456
```

#### **Problema del viajero vendedor**

Comenzamos por definir la función que calcula el fitness; es decir, la longitud total del recorrido. Además, definimos también una función para ordenar a la población dependiendo de su fitness:

```python=
def fitness(estado,longitudes):
    
    n = len(estado)
    lon = [0]*(n-1)
    
    for i in range(0,n-1):
        lon[i] = longitudes[estado[i]][estado[i+1]]
    
    total = sum(lon)
    total = total + longitudes[estado[0]][estado[n-1]]
    
    return total
```

```python=
def sort_pop(pop,fitness):
    
    zipped_lists = zip(fitness,pop)
    sorted_zipped_lists = sorted(zipped_lists)
    sorted_pop = [element for _, element in sorted_zipped_lists]
    
    return sorted_pop
```

Después, definimos la función para generar una población aleatoria, así como los operadores de selección (proporcional), cruce (uniform order-based crossover) y mutación (swap):

```python=
def RandomOrderPop(size,n):

    if size <= math.factorial(n):
        C = [0]*n
        Pop = []
        k = 0

        while len(Pop) < size:
            k = k+1
            if k == size**2:
                break
            C = random.sample(range(0,n),n)
            if Pop.count(C) == 0:
                Pop.append(list(C))
    
    else:
        print("No se puede")
    
    return Pop
```

```python=
def selection_prop(pop,longitudes):
    
    m = len(pop)
    
    fit = [0]*m
    prob = [0]*m
    parents = []
    
    for i in range(0,m):
        fit[i] = fitness(pop[i],longitudes)
    
    for i in range(0,m):
        prob[i] = (1/(m-1))*(1-(fit[i]/sum(fit)))
    
    j = 0
    x = 0
    while len(parents) < 2:
    
        if x == 2*m:
            z = 0
            while len(parents) < 2:
                if prob[z] > 0:
                    parents.append(pop[z])
                z = z+1
                if z == m:
                    break
                
            k = random.randint(0,m-1)
            if len(parents) == 0:
                parents.append(pop[k])
                parents.append(pop[(k+1)%m])
            elif len(parents) == 1:
                parents.append(pop[k])
        
        ran = random.random()
        if ran < prob[j]:
            parents.append(pop[j])
            
        j = (j+1)%m
        x = x+1
    
    return parents
```

```python=
def UOX(P1,P2):
    
    n = len(P1)
    C = [0]*n 

    for i in range(0,n):
        C[i] = random.randint(0,1)
    
    C1 = ['x']*n
    C2 = ['x']*n

    for i in range(0,n):
        if C[i] == 1:
            C1[i] = P2[i]
            C2[i] = P1[i]
    
    for i in range(0,n):
        if C[i] == 0:
            j = 0
            k = 0
            while C1[i] == 'x':
                if C1.count(P1[j]) == 0:
                    C1[i] = P1[j]
                j = j+1
            while C2[i] == 'x':
                if C2.count(P2[k]) == 0:
                    C2[i] = P2[k]
                k = k+1

    return [C1,C2]
```

```python=
def swap(estado,pos):
    
    n = len(estado)
    
    a = pos
    while a == pos:
        a = random.randint(0,n-1)
        cambiar = [pos,a]
    
    a = estado[cambiar[0]]
    b = estado[cambiar[1]]
    
    estado[cambiar[0]] = b
    estado[cambiar[1]] = a
    
    return estado
```

Por último, definimos la función que implementa el GA para resolver el problema del viajero vendedor:

```python=
def viajero_GA(ciudades,longitudes,pop_size,reemplazos,probcruce,probmut):
    
    n = len(ciudades)
    pop = RandomOrderPop(pop_size,n)
    fit = [0]*pop_size
    
    for i in range(0,pop_size):
        fit[i] = fitness(pop[i],longitudes)
    
    pop = sort_pop(pop,fit)
    
    for k in range(0,reemplazos):
        
        parents = selection_prop(pop,longitudes)
        
        ran = random.random()
        if ran < probcruce:
            childs = UOX(parents[0],parents[1])
        else:
            childs = copy.deepcopy(parents)
        
        for i in range(0,n):
            ran0 = random.random()
            ran1 = random.random()
            if ran0 < probmut:
                childs[0] = swap(childs[0],i)
            if ran1 < probmut:
                childs[1] = swap(childs[1],i)
        
        if fitness(childs[0],longitudes)<=fitness(childs[1],longitudes):
            pop[pop_size-1] = childs[0]
        else:
            pop[pop_size-1] = childs[1]
        
        for i in range(0,pop_size):
            fit[i] = fitness(pop[i],longitudes)
        
        pop = sort_pop(pop,fit)
        
        print(str(pop[0])+"" +str(round(fitness(pop[0],longitudes),2)))
        
    mejor = pop[0]
    print(str(mejor) + str(round(fitness(mejor,longitudes),2)))
    
    return [mejor,round(fitness(mejor,longitudes),2)]
```

Ejemplo

**Input:**
```python=
n = 6 
ciudades = list(range(0,n))

l = [[math.inf]*n for _ in range(n)]

l[0][1] = 15.0
l[0][3] = 10.0
l[0][5] = 20.0
l[1][2] = 13.5
l[1][4] = 8.2
l[2][3] = 32.1
l[2][5] = 18.0
l[3][4] = 9.4
l[4][5] = 7.3

for i in range(0,n):
    for j in range(0,i):
        l[i][j] = l[j][i]
        
sol = viajero_GA(ciudades,l,7,50,0.9,0.1)
dibujarGrafo(l,sol,True)
```
**Output:**
```python=
[0, 1, 5, 2, 3, 4] inf
[0, 1, 2, 4, 3, 5] inf
[0, 1, 2, 4, 3, 5] inf
[0, 1, 2, 4, 3, 5] inf
[0, 1, 2, 4, 3, 5] inf
[0, 1, 2, 4, 3, 5] inf
[0, 1, 2, 3, 4, 5] 97.3
[0, 1, 2, 3, 4, 5] 97.3
[0, 1, 2, 3, 4, 5] 97.3
[0, 1, 2, 3, 4, 5] 97.3
[0, 1, 2, 3, 4, 5] 97.3
[0, 1, 2, 3, 4, 5] 97.3
[0, 3, 2, 1, 4, 5] 91.1
[0, 3, 2, 1, 4, 5] 91.1
[0, 3, 2, 1, 4, 5] 91.1
[0, 3, 2, 1, 4, 5] 91.1
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[4, 5, 2, 3, 0, 1] 90.6
[2, 5, 0, 3, 4, 1] 79.1
[2, 5, 0, 3, 4, 1] 79.1
[2, 5, 0, 3, 4, 1] 79.1
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
[4, 5, 2, 1, 0, 3] 73.2
```

![](https://i.imgur.com/ZEu4Dge.jpg)


#### **Minimizar función**

Primero importaremos nuestras librerías y definiremos la cantidad de genes (tamaño de x).
```python=
import random
import copy
gens = 10
```

Esta es nuestra función objetivo
```python=
def f(x):
  sum = 0
  for xi in x:
    sum += xi*xi
  return sum
```

Aqui crearemos a una nueva persona en el algoritmo 
```python=
def newPerson():
  person = [0]*gens
  for i in range(0, gens):
    person[i] = random.uniform(-10,10)
  return person
```

Y aqui una nueva población
```python=
def generatePopulation(people):
  population = []
  for i in range(0, people):
    population.append(newPerson())
  return population
```

Esta función nos devolverá el elemento de la población con mejor fitness
```python=
def max(population, f):
  best, mx = population[0], f(population[0])
  for i in range(1,len(population)):
    if f(population[i]) < mx:
      best,mx = population[i], f(population[i])
  return best
```

Esta función regresa a un individuo basandose en una selección proporcional
```python=
def proportionalSelection(population):
  populationFitness = sum(f(person) for person in population)
  proportion = [f(person)/populationFitness for person in population]
  acum,goal = 0, random.uniform(0,1)
  for i in range(0, len(proportion)):
    acum += proportion[i]
    if goal <= acum:
      return population[i]
```

Y esta otra, un individuo por selección de torneo
```python=
def tournamentSelection(population, K=3):
  return max(random.choices(population, k=K),f)
```

Para la selección de padres, elegiremos uno por seleccion proporcional y otro por torneo
```python=
def selectParents(population):
  mom = proportionalSelection(population)
  dad = tournamentSelection(population)
  return mom,dad
```

Para las operaciones de cruzamientro tendremos la de cruza aritmetica
```python=
def arithmeticCross(mom,dad):
  baby = []
  for i in range(0, len(mom)):
    baby.append((mom[i]+dad[i])/2)
  return baby
```

Y la cruza por punto de corte
```python=
def cutpointCross(mom,dad):
  cutpoint = random.randint(1,len(mom)-1)
  baby = []
  for i in range(0,cutpoint):
    baby.append(mom[i])
  for i in range(cutpoint, len(mom)):
    baby.append(dad[i])
  return baby
```

Para la cruza de los padres, elegiremos aleatoriamente entre los dos metodos de cruza.
```python=
def crossParents(mom, dad):
  op = random.randint(0,1)
  if op == 0:
    return arithmeticCross(mom,dad)
  if op == 1:
    return cutpointCross(mom,dad)
```

Para la mutación de genes usaremos una probilidad pequeña como 10%
```python=
def mutateGens(baby):
  for i in range(0, len(baby)):
    if random.uniform(0,1) > 0.9:
      baby[i] = random.uniform(-10,10)
  return baby
```

Para el reemplazo de la población, realizaremos un reemplazo elitista
```python=
def elitistReplacement(population, born):
  population = sorted(population, key=f, reverse=True)
  for i in range(0, len(born)):
    population[i] = born[i]
  random.shuffle(population)
  return population
```

Para crear una nueva generación únicamente utilizamos el reemplazo elitista pero en esta ocasion dividiendo la cantidad de nacidos a la mitad, de forma que solo los mejores reemplazan elementos de la población.
```python=
def newGeneration(population, born):
  born = sorted(born, key=f, reverse=True)
  return elitistReplacement(population, born[:len(born)//2])
```

Para el algoritmo genético, tendremos como parámetros el número de generaciones, la cantidad de nacimientos por generacion y el tamaño de la población. 
```python=
def ga(generations, natality, people, match, verbose=True):
  population = generatePopulation(people)
  best = max(population, f)

  for i in range(0, generations):
    if verbose: print("Gen #", i, " fitness=", f(best), ",\tbest=", best)
    born = []
    for j in range(0, natality*2):
      mom,dad = selectParents(population)
      if random.uniform(0,1) > match: continue
      baby = crossParents(mom,dad)
      baby = mutateGens(baby)
      born.append(baby)
    population = newGeneration(population, born)
    best = max(population, f)
  
  return best
```

Ejecutamos el algoritmo
```python=
best = ga(40, 1, 10)
print("Result=", best, ", fitness=", f(best))
```

Como podemos ver, este modelo si tiene mejoras a lo largo de varias generaciones, pero no es una mejora sustancial debido a la poca cantidad de individuos que reemplazan elementos de la población. Esto genera un avance muy lento en la población pero preserva la diversidad de la población por lo que en funciones complejas y con una gran cantidad de generaciones, este modelo podría ser capaz de pasar un mínimo local sin mucho problema, a pesar de que su convegencia a una solución sea lenta. 
```txt
Gen # 0  fitness= 216.07091575920234 ,	best= [-9.653411460949046, -0.47961722868279466, -3.057623466087252, 1.8412329698608438, -2.150220676759769, 7.065890086147139, 3.2879057126948155, 1.4895170949115766, -3.3999652092788484, -5.547461571287473]
Gen # 1  fitness= 216.07091575920234 ,	best= [-9.653411460949046, -0.47961722868279466, -3.057623466087252, 1.8412329698608438, -2.150220676759769, 7.065890086147139, 3.2879057126948155, 1.4895170949115766, -3.3999652092788484, -5.547461571287473]
Gen # 2  fitness= 216.07091575920234 ,	best= [-9.653411460949046, -0.47961722868279466, -3.057623466087252, 1.8412329698608438, -2.150220676759769, 7.065890086147139, 3.2879057126948155, 1.4895170949115766, -3.3999652092788484, -5.547461571287473]
Gen # 3  fitness= 216.07091575920234 ,	best= [-9.653411460949046, -0.47961722868279466, -3.057623466087252, 1.8412329698608438, -2.150220676759769, 7.065890086147139, 3.2879057126948155, 1.4895170949115766, -3.3999652092788484, -5.547461571287473]
Gen # 4  fitness= 216.07091575920234 ,	best= [-9.653411460949046, -0.47961722868279466, -3.057623466087252, 1.8412329698608438, -2.150220676759769, 7.065890086147139, 3.2879057126948155, 1.4895170949115766, -3.3999652092788484, -5.547461571287473]
Gen # 5  fitness= 216.07091575920234 ,	best= [-9.653411460949046, -0.47961722868279466, -3.057623466087252, 1.8412329698608438, -2.150220676759769, 7.065890086147139, 3.2879057126948155, 1.4895170949115766, -3.3999652092788484, -5.547461571287473]
Gen # 6  fitness= 216.07091575920234 ,	best= [-9.653411460949046, -0.47961722868279466, -3.057623466087252, 1.8412329698608438, -2.150220676759769, 7.065890086147139, 3.2879057126948155, 1.4895170949115766, -3.3999652092788484, -5.547461571287473]
Gen # 7  fitness= 216.07091575920234 ,	best= [-9.653411460949046, -0.47961722868279466, -3.057623466087252, 1.8412329698608438, -2.150220676759769, 7.065890086147139, 3.2879057126948155, 1.4895170949115766, -3.3999652092788484, -5.547461571287473]
Gen # 8  fitness= 216.07091575920234 ,	best= [-9.653411460949046, -0.47961722868279466, -3.057623466087252, 1.8412329698608438, -2.150220676759769, 7.065890086147139, 3.2879057126948155, 1.4895170949115766, -3.3999652092788484, -5.547461571287473]
Gen # 9  fitness= 216.07091575920234 ,	best= [-9.653411460949046, -0.47961722868279466, -3.057623466087252, 1.8412329698608438, -2.150220676759769, 7.065890086147139, 3.2879057126948155, 1.4895170949115766, -3.3999652092788484, -5.547461571287473]
Gen # 10  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 11  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 12  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 13  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 14  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 15  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 16  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 17  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 18  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 19  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 20  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 21  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 22  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 23  fitness= 124.86687481416344 ,	best= [-5.730975670106978, -3.2919381973671706, 1.8372140824591163, 5.903845696845178, -4.0587453090881125, 4.376298088970843, -0.21633339542592323, 1.2384625679081367, -2.2780130116949016, -0.7482343158829776]
Gen # 24  fitness= 63.40273012917453 ,	best= [-2.7410824495651473, 2.0546271331397534, -2.7679311863697453, -1.2736677226458082, 3.476740147227103, -0.2924878344049091, -1.4200478354127477, -1.0040595903751095, 2.601809762002798, 4.518481516979467]
Gen # 25  fitness= 63.40273012917453 ,	best= [-2.7410824495651473, 2.0546271331397534, -2.7679311863697453, -1.2736677226458082, 3.476740147227103, -0.2924878344049091, -1.4200478354127477, -1.0040595903751095, 2.601809762002798, 4.518481516979467]
Gen # 26  fitness= 63.40273012917453 ,	best= [-2.7410824495651473, 2.0546271331397534, -2.7679311863697453, -1.2736677226458082, 3.476740147227103, -0.2924878344049091, -1.4200478354127477, -1.0040595903751095, 2.601809762002798, 4.518481516979467]
Gen # 27  fitness= 63.40273012917453 ,	best= [-2.7410824495651473, 2.0546271331397534, -2.7679311863697453, -1.2736677226458082, 3.476740147227103, -0.2924878344049091, -1.4200478354127477, -1.0040595903751095, 2.601809762002798, 4.518481516979467]
Gen # 28  fitness= 63.40273012917453 ,	best= [-2.7410824495651473, 2.0546271331397534, -2.7679311863697453, -1.2736677226458082, 3.476740147227103, -0.2924878344049091, -1.4200478354127477, -1.0040595903751095, 2.601809762002798, 4.518481516979467]
Gen # 29  fitness= 63.40273012917453 ,	best= [-2.7410824495651473, 2.0546271331397534, -2.7679311863697453, -1.2736677226458082, 3.476740147227103, -0.2924878344049091, -1.4200478354127477, -1.0040595903751095, 2.601809762002798, 4.518481516979467]
Gen # 30  fitness= 63.40273012917453 ,	best= [-2.7410824495651473, 2.0546271331397534, -2.7679311863697453, -1.2736677226458082, 3.476740147227103, -0.2924878344049091, -1.4200478354127477, -1.0040595903751095, 2.601809762002798, 4.518481516979467]
Gen # 31  fitness= 63.40273012917453 ,	best= [-2.7410824495651473, 2.0546271331397534, -2.7679311863697453, -1.2736677226458082, 3.476740147227103, -0.2924878344049091, -1.4200478354127477, -1.0040595903751095, 2.601809762002798, 4.518481516979467]
Gen # 32  fitness= 63.40273012917453 ,	best= [-2.7410824495651473, 2.0546271331397534, -2.7679311863697453, -1.2736677226458082, 3.476740147227103, -0.2924878344049091, -1.4200478354127477, -1.0040595903751095, 2.601809762002798, 4.518481516979467]
Gen # 33  fitness= 38.46749558168905 ,	best= [0.22109826622441875, 1.565265856176504, 2.5724581055764366, 0.04264384821784539, 2.1812583021171075, 0.8295228604812483, 1.2620600986261208, 0.41576038732595033, 1.6623421179743598, 4.401609372614979]
Gen # 34  fitness= 38.46749558168905 ,	best= [0.22109826622441875, 1.565265856176504, 2.5724581055764366, 0.04264384821784539, 2.1812583021171075, 0.8295228604812483, 1.2620600986261208, 0.41576038732595033, 1.6623421179743598, 4.401609372614979]
Gen # 35  fitness= 38.46749558168905 ,	best= [0.22109826622441875, 1.565265856176504, 2.5724581055764366, 0.04264384821784539, 2.1812583021171075, 0.8295228604812483, 1.2620600986261208, 0.41576038732595033, 1.6623421179743598, 4.401609372614979]
Gen # 36  fitness= 38.46749558168905 ,	best= [0.22109826622441875, 1.565265856176504, 2.5724581055764366, 0.04264384821784539, 2.1812583021171075, 0.8295228604812483, 1.2620600986261208, 0.41576038732595033, 1.6623421179743598, 4.401609372614979]
Gen # 37  fitness= 38.46749558168905 ,	best= [0.22109826622441875, 1.565265856176504, 2.5724581055764366, 0.04264384821784539, 2.1812583021171075, 0.8295228604812483, 1.2620600986261208, 0.41576038732595033, 1.6623421179743598, 4.401609372614979]
Gen # 38  fitness= 38.46749558168905 ,	best= [0.22109826622441875, 1.565265856176504, 2.5724581055764366, 0.04264384821784539, 2.1812583021171075, 0.8295228604812483, 1.2620600986261208, 0.41576038732595033, 1.6623421179743598, 4.401609372614979]
Gen # 39  fitness= 38.46749558168905 ,	best= [0.22109826622441875, 1.565265856176504, 2.5724581055764366, 0.04264384821784539, 2.1812583021171075, 0.8295228604812483, 1.2620600986261208, 0.41576038732595033, 1.6623421179743598, 4.401609372614979]
Result= [0.22109826622441875, 1.565265856176504, 2.5724581055764366, 0.04264384821784539, 2.1812583021171075, 0.8295228604812483, 1.2620600986261208, 0.41576038732595033, 1.6623421179743598, 4.401609372614979] , fitness= 38.46749558168905
```

<br>

### **Referencias**

**[1]** Katoch, S., Chauhan, S. S., & Kumar, V. (2020). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 1-36.

**[2]** Natyhelem G. L. (2006). Algoritmos Genéticos. Universidad Nacional de Colombia. Escuela de Estadística, , 1-36.




