# Practica 14 Algoritmos Genéticos
### Solución de problemas mediante Algoritmos Genéticos Generacionales
**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/practica14)
<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 generacional.**
**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$
**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 ruleta.
```python=
def ruleta(poblacion,npadres):
#OPERADOR POR RULETA
#practicamente es elejir al padre aleatoriamente
padres = []
for i in range(0,npadres):
#elejir no los mismos padres
while True:
indicesindividuos = np.arange(0,tpoblacion,1)
ppadre = random.choices(indicesindividuos,k=1)
padre = poblacion[ppadre[0]]
if padre not in padres:
break
padres.insert(i, padre)
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):
while True:
random_position = random.randint(0, len(state)-1)
random_mutation = random.randint(0,available_objects[2][random_position])
state[random_position] = random_mutation
if isValidState(state):
break
return state
```
Por último, implementación el algoritmo genético generacional para el problema de la mochila.
```python=
def GA_mochila(poblacion,ngeneraciones):
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 = []
for j in range(0,int(tpoblacion/2)):
padres = ruleta(poblacion,2)
#cruzamos
hijos_aux = uniforme(padres)
hijos.append(hijos_aux[0])
hijos.append(hijos_aux[1])
#mutamos padres e hijos
for j in range(0,len(poblacion)):
poblacion[j] = mutacion_uniforme(poblacion[j])
for j in range(0,len(hijos)):
hijos[j] = mutacion_uniforme(hijos[j])
#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
```
**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 10
ngeneraciones = 100
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])
[poblacion_final,resultado] = GA_mochila(poblacion, ngeneraciones)
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, 1, 0] w: 383 score: 555
[1, 0, 0, 1, 0, 1] w: 412 score: 941
[1, 1, 1, 1, 0, 0] w: 221 score: 660
[0, 0, 1, 1, 1, 0] w: 433 score: 715
[0, 0, 1, 1, 0, 1] w: 453 score: 951
[0, 0, 1, 0, 0, 0] w: 50 score: 160
Población resultante:
[1, 1, 0, 1, 1, 1] w: 651 score: 1446
[0, 1, 1, 1, 1, 0] w: 442 score: 865
[0, 0, 1, 1, 1, 1] w: 683 score: 1306
[0, 0, 1, 1, 1, 1] w: 683 score: 1306
[0, 0, 1, 1, 1, 1] w: 683 score: 1306
[0, 0, 1, 1, 1, 1] w: 683 score: 1306
Mejor de la poblacion: [1, 1, 0, 1, 1, 1] score: 1446
```
#### **Problema del viajero vendedor**
Primero definimos una función para medir la longitud de un estado (individuo), es decir su fitness. Después, una función que nos devuelva el mejor individuo de una población basado en ese fitness.
```python=
def longitud_total(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 best(pop,longitudes):
m = len(pop)
l = [0]*m
for i in range(0,m):
l[i] = longitud_total(pop[i],longitudes)
x = min(l)
ind = l.index(x)
return pop[ind]
```
Ahora definimos la función objetivo, siendo ésta la mínima longitud de la población.
```python=
def test_pop(pop,longitudes):
m = len(pop)
x = [0]*m
for i in range(0,m):
x[i] = longitud_total(pop[i],longitudes)
y = min(x)
return y
```
La siguiente función crea una población inicial aleatoria.
```python=
def RandomOrderPop(size,n):
if size <= m.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
```
Ahora se define el operador de cruce, en este caso el *Uniform order-bases crossover*.
```python=
def UOX(P1,P2):
n = len(P1) #longitud del cromosoma de los padres
C = [0]*n #vector de cruce
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]
```
Y por supuesto el operador de mutación, en este caso el operador *swap*.
```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
```
Por último, la solución del problema del viajero vendedor usando GA.
```python=
def viajero_GA(ciudades,longitudes,pop_size,generaciones):
n = len(ciudades)
pop = RandomOrderPop(pop_size,n)
newpop = [[0]*n for _ in range(pop_size)]
l = m.inf
for k in range(0,generaciones):
mejor0 = best(pop,longitudes)
l0 = longitud_total(mejor0,longitudes)
if l0 <= l:
mejor = list(mejor0)
l = longitud_total(mejor,longitudes)
print(str(mejor) + ", Longitud: "
+ str(round(longitud_total(mejor,longitudes),2)))
for i in range(0,len(pop)-1):
ran = random.random()
if ran > 0.1:
c = UOX(pop[i],pop[i+1])
newpop[i] = c[0]
newpop[i+1] = c[1]
else:
newpop[i] = pop[i]
newpop[i+1] = pop[i+1]
for i in range(0,len(newpop)):
for j in range(0,n):
ran = random.random()
if ran > 0.9:
swap(newpop[i],j)
random.shuffle(newpop)
for i in range(0,len(pop)):
pop[i] = newpop[i]
if test_pop(pop,longitudes) < longitud_total(mejor,longitudes):
mejor = list(best(pop,longitudes))
print(str(mejor) + ", Longitud: "
+ str(round(longitud_total(mejor,longitudes),2)))
return [mejor,round(longitud_total(mejor,longitudes),2)]
```
Ejemplo:
**input:**
```python=
n = 6
ciudades = list(range(0,n))
l = [[m.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,6,20)
dibujarGrafo(l,sol,True)
```
**output:**
```python=
[4, 1, 3, 0, 2, 5], Longitud: inf
[1, 3, 2, 0, 5, 4], Longitud: inf
[0, 5, 3, 2, 4, 1], Longitud: inf
[0, 3, 2, 5, 4, 1], Longitud: 90.6
[0, 3, 2, 5, 4, 1], Longitud: 90.6
[0, 3, 2, 5, 4, 1], Longitud: 90.6
[0, 3, 2, 5, 4, 1], Longitud: 90.6
[0, 3, 2, 5, 4, 1], Longitud: 90.6
[1, 4, 3, 0, 5, 2], Longitud: 79.1
[1, 4, 3, 0, 5, 2], Longitud: 79.1
[1, 4, 3, 0, 5, 2], Longitud: 79.1
[1, 4, 3, 0, 5, 2], Longitud: 79.1
[1, 4, 3, 0, 5, 2], Longitud: 79.1
[1, 4, 3, 0, 5, 2], Longitud: 79.1
[1, 4, 3, 0, 5, 2], Longitud: 79.1
[1, 4, 3, 0, 5, 2], Longitud: 79.1
[3, 0, 1, 2, 5, 4], Longitud: 73.2
[3, 0, 1, 2, 5, 4], Longitud: 73.2
[3, 0, 1, 2, 5, 4], Longitud: 73.2
[4, 5, 2, 1, 0, 3], Longitud: 73.2
[0, 1, 2, 5, 4, 3], Longitud: 73.2
```
#### **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
```python=
def newGeneration(population, born):
return elitistReplacement(population, born)
```
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, 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):
mom,dad = selectParents(population)
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(50, 4, 15)
print("Result=", best, ", fitness=", f(best))
```
Como podemos ver, generación tras generación obtenemos mejores resultados conforme evoluciona nuestra población, aunque también es posible ver que mientras más avanzan las generaciones el reemplazo elitista repercute en la diversidad de la población, que en el caso de la función elegida no repercute de gran forma en los resultados, pero en otros casos podría tener un gran impacto reducir la diversidad. Esto también puede depender respecto al tamañi de la población respecto a la taza de natalidad.
```txt
Gen # 0 fitness= 94.12411922047724 , best= [4.471066135752764, -4.746415027719628, 0.15500638378833997, -3.15489220507078, 1.7204195739825785, -1.383048006067579, -2.4321614392164808, -5.00362031378105, 1.135304131708315, 2.1247713124498873]
Gen # 1 fitness= 94.12411922047724 , best= [4.471066135752764, -4.746415027719628, 0.15500638378833997, -3.15489220507078, 1.7204195739825785, -1.383048006067579, -2.4321614392164808, -5.00362031378105, 1.135304131708315, 2.1247713124498873]
Gen # 2 fitness= 28.32306906796426 , best= [-0.791780844334526, -3.5978131929484967, -0.9903295990688274, 2.0657539312346076, 1.18272331886803, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 3 fitness= 28.32306906796426 , best= [-0.791780844334526, -3.5978131929484967, -0.9903295990688274, 2.0657539312346076, 1.18272331886803, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 4 fitness= 28.32306906796426 , best= [-0.791780844334526, -3.5978131929484967, -0.9903295990688274, 2.0657539312346076, 1.18272331886803, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 5 fitness= 28.32306906796426 , best= [-0.791780844334526, -3.5978131929484967, -0.9903295990688274, 2.0657539312346076, 1.18272331886803, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 6 fitness= 28.32306906796426 , best= [-0.791780844334526, -3.5978131929484967, -0.9903295990688274, 2.0657539312346076, 1.18272331886803, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 7 fitness= 28.32306906796426 , best= [-0.791780844334526, -3.5978131929484967, -0.9903295990688274, 2.0657539312346076, 1.18272331886803, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 8 fitness= 28.32306906796426 , best= [-0.791780844334526, -3.5978131929484967, -0.9903295990688274, 2.0657539312346076, 1.18272331886803, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 9 fitness= 28.32306906796426 , best= [-0.791780844334526, -3.5978131929484967, -0.9903295990688274, 2.0657539312346076, 1.18272331886803, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 10 fitness= 28.32306906796426 , best= [-0.791780844334526, -3.5978131929484967, -0.9903295990688274, 2.0657539312346076, 1.18272331886803, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 11 fitness= 20.604067552019742 , best= [2.775223567475745, 0.8050352579895392, -1.5024972514951493, 1.2790644687992665, -0.5056185389083225, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 12 fitness= 20.604067552019742 , best= [2.775223567475745, 0.8050352579895392, -1.5024972514951493, 1.2790644687992665, -0.5056185389083225, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 13 fitness= 20.604067552019742 , best= [2.775223567475745, 0.8050352579895392, -1.5024972514951493, 1.2790644687992665, -0.5056185389083225, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 14 fitness= 20.604067552019742 , best= [2.775223567475745, 0.8050352579895392, -1.5024972514951493, 1.2790644687992665, -0.5056185389083225, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 15 fitness= 20.604067552019742 , best= [2.775223567475745, 0.8050352579895392, -1.5024972514951493, 1.2790644687992665, -0.5056185389083225, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 16 fitness= 20.604067552019742 , best= [2.775223567475745, 0.8050352579895392, -1.5024972514951493, 1.2790644687992665, -0.5056185389083225, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 17 fitness= 20.604067552019742 , best= [2.775223567475745, 0.8050352579895392, -1.5024972514951493, 1.2790644687992665, -0.5056185389083225, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 18 fitness= 20.604067552019742 , best= [2.775223567475745, 0.8050352579895392, -1.5024972514951493, 1.2790644687992665, -0.5056185389083225, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 19 fitness= 20.604067552019742 , best= [2.775223567475745, 0.8050352579895392, -1.5024972514951493, 1.2790644687992665, -0.5056185389083225, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 20 fitness= 20.604067552019742 , best= [2.775223567475745, 0.8050352579895392, -1.5024972514951493, 1.2790644687992665, -0.5056185389083225, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, 2.364394272027215]
Gen # 21 fitness= 14.890838727267017 , best= [-0.2978401054706089, -0.2705532511166817, -3.0214596771574485, 1.0559593121719792, -0.3347883017254305, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, -1.3630749910274993]
Gen # 22 fitness= 14.890838727267017 , best= [-0.2978401054706089, -0.2705532511166817, -3.0214596771574485, 1.0559593121719792, -0.3347883017254305, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, -1.3630749910274993]
Gen # 23 fitness= 14.890838727267017 , best= [-0.2978401054706089, -0.2705532511166817, -3.0214596771574485, 1.0559593121719792, -0.3347883017254305, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, -1.3630749910274993]
Gen # 24 fitness= 14.890838727267017 , best= [-0.2978401054706089, -0.2705532511166817, -3.0214596771574485, 1.0559593121719792, -0.3347883017254305, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, -1.3630749910274993]
Gen # 25 fitness= 14.890838727267017 , best= [-0.2978401054706089, -0.2705532511166817, -3.0214596771574485, 1.0559593121719792, -0.3347883017254305, 0.7469562759487189, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, -1.3630749910274993]
Gen # 26 fitness= 12.6957880723491 , best= [0.8655287407076102, -2.0768976134359267, -0.8172439834172804, -0.6744711650927966, 1.6105643203397997, -0.3190493087116666, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, -1.3630749910274993]
Gen # 27 fitness= 12.6957880723491 , best= [0.8655287407076102, -2.0768976134359267, -0.8172439834172804, -0.6744711650927966, 1.6105643203397997, -0.3190493087116666, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, -1.3630749910274993]
Gen # 28 fitness= 12.6957880723491 , best= [0.8655287407076102, -2.0768976134359267, -0.8172439834172804, -0.6744711650927966, 1.6105643203397997, -0.3190493087116666, 0.8527182134026416, 0.919181623613067, 0.6201925205343999, -1.3630749910274993]
Gen # 29 fitness= 11.560142189847856 , best= [2.230546581038729, -0.1341013047676456, -1.7294888745844812, 1.2198711680671652, -0.37305472020980524, -0.45755029482478526, 0.45806894589787805, 0.7943293833543343, 0.928465781070997, 0.1903849103525519]
Gen # 30 fitness= 10.598750755944753 , best= [0.6500093884510586, -1.51510410836805, -1.8471850085918784, 0.3010681245730836, 0.8648652227091942, -0.36656929651346737, -1.2301121671938893, 0.7449987249652918, 1.0875394670314296, 0.4946287305124851]
Gen # 31 fitness= 10.598750755944753 , best= [0.6500093884510586, -1.51510410836805, -1.8471850085918784, 0.3010681245730836, 0.8648652227091942, -0.36656929651346737, -1.2301121671938893, 0.7449987249652918, 1.0875394670314296, 0.4946287305124851]
Gen # 32 fitness= 10.598750755944753 , best= [0.6500093884510586, -1.51510410836805, -1.8471850085918784, 0.3010681245730836, 0.8648652227091942, -0.36656929651346737, -1.2301121671938893, 0.7449987249652918, 1.0875394670314296, 0.4946287305124851]
Gen # 33 fitness= 7.495188780949849 , best= [1.1792698353461504, -0.16059848896165363, -1.0734933973720802, -0.643754819988397, 1.5177250447715038, 0.43012740968341734, -0.8512542434500698, 0.7531869936350255, 0.8551002577059483, -0.01707144067951294]
Gen # 34 fitness= 7.495188780949849 , best= [1.1792698353461504, -0.16059848896165363, -1.0734933973720802, -0.643754819988397, 1.5177250447715038, 0.43012740968341734, -0.8512542434500698, 0.7531869936350255, 0.8551002577059483, -0.01707144067951294]
Gen # 35 fitness= 7.495188780949849 , best= [1.1792698353461504, -0.16059848896165363, -1.0734933973720802, -0.643754819988397, 1.5177250447715038, 0.43012740968341734, -0.8512542434500698, 0.7531869936350255, 0.8551002577059483, -0.01707144067951294]
Gen # 36 fitness= 7.495188780949849 , best= [1.1792698353461504, -0.16059848896165363, -1.0734933973720802, -0.643754819988397, 1.5177250447715038, 0.43012740968341734, -0.8512542434500698, 0.7531869936350255, 0.8551002577059483, -0.01707144067951294]
Gen # 37 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 38 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 39 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 40 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 41 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 42 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 43 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 44 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 45 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 46 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 47 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 48 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Gen # 49 fitness= 3.9834127433232247 , best= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181]
Result= [0.9360788614163618, 0.48737731862900713, -0.7602181293765934, -0.1037230185246672, 0.9201188529598655, -0.14836588180243435, 0.4496057956369439, 0.7778523228295469, 0.775563414725732, -0.06010850768465181] , fitness= 3.9834127433232247
```
<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.
Sign in with Wallet
Connect another wallet