---
# System prepended metadata

title: Practica 16 Algoritmos Genéticos

---

# Practica 16 Algoritmos Genéticos
### Solución de problemas mediante Algoritmos Genéticos
**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/practica16)

<br>

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


### **1. Analice detalladamente las seis funciones definidas en el documento “Funciones de prueba.pdf”.**

Las funciones encontradas en el documento "Funciones de prueba.pdf" son las siguientes:
**Función Alpine 1:**
$$
f_1(x)=\sum_{i=1}^{D}{\;|\; x_i\sin(x_i)+0.1x_i \;|\;}
$$
Punto mínimo: $x^*=f(0,0)$ y valor mínimo: $f(x^*)=0$

**Función Dixon & Price:**
$$
f_2(x)=(x_1-1)^2+\sum_{i=2}^{D}{i(2 \sin(x_i)\;-\;x_{i-1})^2}
$$
Punto mínimo: $x^*=f(2(\frac{2^i-2}{2^i}))$ y valor mínimo: $f(x^*)=0$

**Función Quintic:**
$$
f_3(x)=\sum_{i=1}^{D}{\;|\; x^5_i-3x^4_i+4x^3_i-2x^2_i-10x_1-4 \;|\;}
$$
Punto mínimo: $x^*=f(-1\;or\;2)$ y valor mínimo: $f(x^*)=0$

**Función Schwefel 2.23:**
$$
f_4(x)=\sum_{i=1}^{D}{x^{10}_i}
$$
Punto mínimo: $x^*=f(0,0)$ y valor mínimo: $f(x^*)=0$

**Función Streched V Sine Wave:**
$$
f_5(x)=\sum_{i=1}^{D-1}{(x^2_{i+1}+x^2_i)^{0.25} \Big[\sin^2\{50(x^2_{i+1}+x^2_i)^{0.1}\}+0.1\Big] }
$$
Punto mínimo: $x^*=f(0,0)$ y valor mínimo: $f(x^*)=0$

**Función Sum Squares:**
$$
f_6(x)=\sum_{i=1}^{D}{ix^2_i}
$$
Punto mínimo: $x^*=f(0,0)$ y valor mínimo: $f(x^*)=0$

<br>

### **2. Implemente dichas funciones..**

**Función Alpine 1:**
$$
f_1(x)=\sum_{i=1}^{D}{\;|\; x_i\sin(x_i)+0.1x_i \;|\;}
$$


```python=
#funcion alpine1
def f(x):
  total = 0
  for xi in x:
    total += abs(xi*math.sin(xi)+0.1*xi)
  return total
```



**Función Dixon & Price:**
$$
f_2(x)=(x_1-1)^2+\sum_{i=2}^{D}{i(2 \sin(x_i)\;-\;x_{i-1})^2}
$$

```python=
#funcion dixon and price
def f(x):
  total = 0
  binomio = (x[0]-1)**2
  for i in range(1,len(x)):
    total += i*((2*math.sin(x[i])-x[i-1])**2)
  
  total = binomio + total
  return total
```

**Función Quintic:**
$$
f_3(x)=\sum_{i=1}^{D}{\;|\; x^5_i-3x^4_i+4x^3_i-2x^2_i-10x_1-4 \;|\;}
$$

```python=
#funcion quintic
def f(x):
  total = 0
  for xi in x:
    total += abs((xi**5)-(3*xi**4)+(4*xi**3)-(2*xi**2)-(10*xi)-4)
  return total
```

**Función Schwefel 2.23:**
$$
f_4(x)=\sum_{i=1}^{D}{x^{10}_i}
$$

```python=
#funcion schwefel 2.23
def f(x):
  total = 0
  for xi in x:
    total += xi**10
  return total
```

**Función Streched V Sine Wave:**
$$
f_5(x)=\sum_{i=1}^{D-1}{(x^2_{i+1}+x^2_i)^{0.25} \Big[\sin^2\{50(x^2_{i+1}+x^2_i)^{0.1}\}+0.1\Big] }
$$

```python=
#funcion strched V sine wave
def f(x):
  total = 0
  for i in range(0,len(x)-1):
    total += (((x[i+1]**2)+(x[i]**2))**0.25)*(math.sin(50*(((x[i+1]**2) +
                x[i]**2)**0.1))**2+(0.1))   
  return total
```

**Función Sum Squares:**
$$
f_6(x)=\sum_{i=1}^{D}{ix^2_i}
$$

```python=
#funcion sum squares
def f(x):
  total = 0
  for i,xi in enumerate(x):
    total += (i+1)*(xi**2)
  return total
```

<br>

### **3. Implemente al menos 6 versiones de Algoritmos Genéticos (3 de modelo estacionario, 3 de modelo generacional) para la solución de los problemas de minimización de las funciones anteriores. Considere $D=10$ y posteriormente $D=30$ dimensiones.**

Las siguientes funciones implementan los modelos estacionario y generacional respectivamente para la minimización de una función $f$; se utilizaron los operadores de selección proporcional y de cruce blx-$\alpha$.

```python=
def funciones_GA_est(dimension, pop_size, reemplazos, probcruce, probmut, alpha):
    
    pop = RandomPop(pop_size,dimension)
    fit = [0]*len(pop)
    
    for i in range(0,len(pop)):
        fit[i] = f(pop[i])

    pop = sort_pop(pop,fit)
    
    for k in range(0,reemplazos):
        
        parents = selection_prop(pop)
        
        ran = random.random()
        if ran < probcruce:
            childs = blx(parents[0],parents[1],alpha)
        else:
            childs = copy.deepcopy(parents)
        
        for i in range(0,dimension):
            ran0 = random.random()
            ran1 = random.random()
            if ran0 < probmut:
                childs[0] = mutation(childs[0],i)
            if ran1 < probmut:
                childs[1] = mutation(childs[1],i)
        
        if f(childs[0]) <= f(childs[1]):
            pop[pop_size-1] = childs[0]
        else:
            pop[pop_size-1] = childs[1]
        
        for i in range(0,len(pop)):
            fit[i] = f(pop[i])
            
        pop = sort_pop(pop,fit)
        
    mejor = pop[0]
    
    return [mejor,round(f(mejor),3)]
```

```python=
def funciones_GA_gen(dimension, pop_size, generaciones, probcruce, probmut, alpha):
    
    pop = RandomPop(pop_size,dimension)
    fit = [0]*pop_size
    
    for i in range(0,len(pop)):
        fit[i] = f(pop[i])

    pop = sort_pop(pop,fit)
    
    mejor0 = best(pop)
    
    for k in range(0,generaciones):
        
        newpop = []
        
        while len(newpop) < pop_size:
        
            parents = selection_prop(pop)
            ran = random.random()
            if ran < probcruce:
                childs = blx(parents[0],parents[1],alpha)
            else:
                childs = copy.deepcopy(parents)
        
            for i in range(0,dimension):
                ran0 = random.random()
                ran1 = random.random()
                if ran0 < probmut:
                    childs[0] = mutation(childs[0],i)
                if ran1 < probmut:
                    childs[1] = mutation(childs[1],i)
        
            newpop.append(childs[0])
            newpop.append(childs[1])
        
        mejor = best(newpop)
        pop = copy.deepcopy(newpop)
               
        if f(mejor) <= f(mejor0):
            mejor0 = copy.deepcopy(mejor)
        
        for i in range(0,pop_size):
            fit[i] = f(pop[i])
            
        pop = sort_pop(pop,fit)
        
    return [mejor0,round(f(mejor0),3)]
```

Las siguientes funciones implementan los modelos estacionario y generacional respectivamente para la minimización de una función $f$; se utilizaron los operadores de selección por torneo y de cruce uniforme.

```python=
def GAE(ngeneraciones,pro_cruza,pro_muth):
    poblacion = generapoblacion(tpoblacion)
    scorepoblacion = getscorepoblacion(poblacion)
    
    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 hijos
        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(scorearray)
    mejor_indice = mejores[0]
    resultado = aux_poblacion[mejor_indice].tolist()
    return resultado,new_poblacion
```
```python=
def GAG(ngeneraciones,pro_cruza,pro_muth):
    poblacion = generapoblacion(tpoblacion)
    scorepoblacion = getscorepoblacion(poblacion)
    
    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 = torneo(poblacion,2,3)
            ran = random.random()
            if ran < pro_cruza:
                #cruzamos
                hijos_aux = uniforme(padres)
                hijos.append(hijos_aux[0])
                hijos.append(hijos_aux[1])
        #mutamos hijos
        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 resultado,new_poblacion
```

<br>

### **4. Reporte los resultados obtenidos. Para ello, realice 20 ejecuciones independientes, con la siguiente configuración:**

### b) Muestre el mejor, peor, promedio, mediana y desviación estándar de los resultados en las 20 ejecuciones.
### Para d = 10

Las siguientes tablas muestran los resultados obtenidos utilizando el operador de selección proporcional y el operador de cruce blx-$\alpha$:

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

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


Las siguientes tablas muestran los resultados obtenidos utilizando el operador de selección por torneo y el operador de cruce uniforme:

**d=10 (Estacionario)**
| Función | Mejor | Peor | Promedio | Mediana | Desvianción Estándar|
| ------- | ----- | ---- | -------- | ------- | --------------------|
|Alpine 1	|0.19	|1.47	|0.69	|0.59	|0.33|
|Dixon & Price	|8.8	|39.9|23.2	|23.3|	8.9|
|Quintic|	9.5	|47.7|	24|	22.4|	11.34|
|Schwefel 2.23	|0	|45.7	|6.5	|0.6	|12.7|
|Streched V Sine Wave	|1.72|	3.37|	2.4	|2.4|	0.33|
|Sum Squares	|2.22	|23.9|	10.6	|10.02	|5.26|


**d=10 (Generacional)**
| Función | Mejor | Peor | Promedio | Mediana | Desvianción Estándar|
| ------- | ----- | ---- | -------- | ------- | --------------------|
|Alpine 1	|0.04	|0.16	|0.08	|0.07	|0.03|
|Dixon & Price	|1.67	|33.1|10	|7.74|	7.78|
|Quintic|	0.95	|5.79|	2.39|	1.9|	1.26|
|Schwefel 2.23	|0	|0.27	|0.05	|0.008	|0.078|
|Streched V Sine Wave	|1.14|	2.63|	1.91	|1.94|	0.44|
|Sum Squares	|0.67	|6.17|	2.8	|2.36	|1.6|



<br>

### Para d = 30

Las siguientes tablas muestran los resultados obtenidos utilizando el operador de selección proporcional y el operador de cruce blx-$\alpha$:

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

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


Las siguientes tablas muestran los resultados obtenidos utilizando el operador de selección por torneo y el operador de cruce uniforme:

**d=30 (Estacionario)**
| Función | Mejor | Peor | Promedio | Mediana | Desvianción Estándar|
| ------- | ----- | ---- | -------- | ------- | --------------------|
|Alpine 1	|10.3	|18.4	|12.8	|12.8	|1.86|
|Dixon & Price	|648.2	|1273.9|1007.8	|1009.8|	174.3|
|Quintic|	900.4	|4822.9|	2038.8|	1696.6|	1117.8|
|Schwefel 2.23	|16736	|5300784	|163874	|232476	|1181286|
|Streched V Sine Wave	|11.43|	15.38|	12.7	|12.3|	1.1|
|Sum Squares	|624	|1321|	899	|887	|149|


**d=30 (Generacional)**
| Función | Mejor | Peor | Promedio | Mediana | Desvianción Estándar|
| ------- | ----- | ---- | -------- | ------- | --------------------|
|Alpine 1	|1.77	|4.68	|3.4	|3.4	|0.71|
|Dixon & Price	|191	|635|340	|330|	105|
|Quintic|	99	|189|	146|	146|	23.7|
|Schwefel 2.23	|80	|5303	|1312	|635	|1555|
|Streched V Sine Wave	|7.09|	10.3|	8.3	|8.2|	0.88|
|Sum Squares	|96.7	|195|	149.1	|149.1	|33.1|





<br>

### c) Muestre el mejor, peor, promedio, mediana y desviación estándar de los tiempos de ejecución (en segundos) en las 20 ejecuciones
### Para d = 10

Las siguientes tablas muestran los tiempos de ejecución obtenidos utilizando el operador de selección proporcional y el operador de cruce blx-$\alpha$:

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

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


Las siguientes tablas muestran los resultados obtenidos utilizando el operador de selección por torneo y el operador de cruce uniforme:

**d=10 (Estacionario)**
| Función | Mejor | Peor | Promedio | Mediana | Desvianción Estándar|
| ------- | ----- | ---- | -------- | ------- | --------------------|
|Alpine 1	|0.16	|0.069	|0.09	|0.08	|0.025|
|Dixon & Price	|0.10	|0.28	|0.16	|0.158|	0.04|
|Quintic|	0.2	|0.4|	0.26|	0.23|	0.062|
|Schwefel 2.23	|0.084	|0.053	|0.06	|0.06	|0.0075|
|Streched V Sine Wave	|0.3|	0.54|	0.37	|0.34|	0.061|
|Sum Squares	|0.069	|0.20|	0.114	|0.108	|0.03|

**d=10 (Generacional)**
| Función | Mejor | Peor | Promedio | Mediana | Desvianción Estándar|
| ------- | ----- | ---- | -------- | ------- | --------------------|
|Alpine 1	|0.2	|0.33	|0.25	|0.23	|0.036|
|Dixon & Price	|0.321	|0.742	|0.41	|0.369|	0.11|
|Quintic|	0.77	|0.55|	0.61|	0.60|	0.05|
|Schwefel 2.23	|0.15	|0.084	|0.109	|0.1	|0.0198|
|Streched V Sine Wave	|0.33|	0.84|	0.5	|0.51|	0.13|
|Sum Squares	|0.1	|0.14|	0.12	|0.13	|0.01|



<br>

### Para d = 30

Las siguientes tablas muestran los tiempos de ejecución obtenidos utilizando el operador de selección proporcional y el operador de cruce blx-$\alpha$:

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

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


Las siguientes tablas muestran los resultados obtenidos utilizando el operador de selección por torneo y el operador de cruce uniforme:

**d=30 (Estacionario)**
| Función | Mejor | Peor | Promedio | Mediana | Desvianción Estándar|
| ------- | ----- | ---- | -------- | ------- | --------------------|
|Alpine 1	|0.18	|0.33	|0.23	|0.22	|0.04|
|Dixon & Price	|0.28	|0.56|0.35	|0.34|	0.07|
|Quintic|	0.55	|1.03|	0.67|	0.63|	0.124|
|Schwefel 2.23	|0.14	|0.24	|0.17	|0.16	|0.02|
|Streched V Sine Wave	|0.78|	1|	0.85	|0.84|	0.06|
|Sum Squares	|0.19	|0.53|	0.27	|0.24	|0.08|


**d=30 (Generacional)**
| Función | Mejor | Peor | Promedio | Mediana | Desvianción Estándar|
| ------- | ----- | ---- | -------- | ------- | --------------------|
|Alpine 1	|0.51	|0.83	|0.61	|0.57	|0.09|
|Dixon & Price	|0.85	|1.13|0.96	|0.93|	0.09|
|Quintic|	1.47	|2.25|	1.6|	1.57|	0.16|
|Schwefel 2.23	|0.47	|0.61	|0.52	|0.5	|0.03|
|Streched V Sine Wave	|2.08|	2.54|	2.14	|2.08|	0.13|
|Sum Squares	|0.58	|0.88|	0.64	|0.62	|0.07|


<br>

