# 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 \;|\;}
$$

#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}
$$

#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 \;|\;}
$$

#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}
$$

#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] }
$$

#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}
$$

#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$.

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)]

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.

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

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$:



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$:



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$:



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$:



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>