# Practica 11 - Algoritmos Genéticos
### Operadores de selección en 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/practica11)

<br>

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

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

**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>

<br>

### **3. Enuncie las semejanzas y diferencias en los modelos generacional y estacionario.**

* Modelo generacional: En cada iteración del algoritmo, la población es completamente reemplazada por su descendencia.

* Modelo estacionario: En cada iteración del algoritmo, mediante el uso de algún mecanismo de muestreo (un operador de selección), se eligen dos padres de la población y se les aplica un operador de cruce, dando lugar a uno o dos hijos, los cuales reemplazaran respectivamente a uno o dos individuos de la población original.

La principal semejanza entre ambos modelos es el reemplazo de algunos individuos (todos en el caso del modelo generacional) de la población por la descendencia; siendo justamente este proceso el que da lugar a la evolución de la población. Por otra parte, la principal diferencia entre ambos modelos es justamente la cantidad de individuos reemplazados en cada iteración del algoritmo; en el caso del modelo estacionario, esto puede dar lugar a una convergencia rápida (presión selectiva) si se reemplaza a los individuos menos aptos.

<br>

### **4. Explique el funcionamiento del operador de selección por muestreo aleatorio universal.**

El **selección por muestreo aleatoria universal** (URS) es bastante similar a la selección por ruleta, la cual se detalla más adelante. Este operador consiste asignar una probablidad de selección proporcional al valor del fitnes del cromosoma. Posteriormente se gira la ruleta una unica vez usando multiples puntos de selección espaciados equitativamente al rededor de la ruleta (con un angulo entre ellas de $\frac{2\pi}{k}$, donde $k$ representa al número de elementos que deben seleccionarse). De esta manera, todos los individuos se seleccionan al mismo tiempo, por lo tanto, todos los padres se eligen en un solo giro de la ruleta. Las flechas se mueven como $rand$ x $\frac{2\pi}{k}$ en cada elemento. A continuación, se muestra un diagrama.

<div style = 'text-align:center;'>
<img src="https://i.imgur.com/zOiJn3g.png" width="300px"><br>
Figura 2. Descripción ilustrativa del operador de selección por por muestreo aleatorio universal.
</div>

<br>

### **5. Explique el funcionamiento del operador de selección por torneo.**

La **selección por torneo** (TS), es un operador de selección basado en el fitnets de cada individuo de la población. Este operador consiste en seleccionar al individuo de mejor fitness entre $k$ individuos previamente escogidos aletoriamente. El valor de $k$ se denomica tamaño del torneo. A mayor valor de $k$, mayor presión selectiva y vicerversa.

Por ejemplo, si se tiene un valor de $k=3$ significa que escogeremos de manera aleatoria a *3* individuos dentro de la población. De estos *3* individuos escogidos se selecciona al de mayor fitness; es decir, si dentro de los *3* individuos escogidos se tienen los siguientes fitnes ($f_1=6$, $f_2=9$ y $f_3=5$) se seleccionará al individuo con el valor de fitnes $f_2=9$.

<br>

### **6. Explique el funcionamiento del operador de selección proporcional.**

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>

### **7. Explique el funcionamiento del operador de selección por ruleta.**

La **selección por ruleta**, es un operador de seleccipon basado en el fitnets de cada individuo de la población. Este operador consiste asignar una probablidad de selección proporcional al valor del fitnes del cromosoma. Posteriormene, para realizar la selección se mueve una única flecha de manera aleatoria ($rand$ X $2\pi$), por lo tanto, si la fecha cae en una región $j$ se selecciona al individuo $j$ de esa región. Se puede analizar como una ruleta, donde existe un punto de selección, para después girar la ruleta y seleccionar al individuo donde cayo el punto de selección. A continuación, se puede apreciar un ejemplo ilustrativo.

<div style = 'text-align:center;'>
<img src="https://i.imgur.com/H5WTOYq.png" width="300px"><br>
Figura 3. Descripción ilustrativa del operador de selección por ruleta.
</div>

<br>

Se puede observar como en el caso de la *Figura 3* que la flecha de selección cayó en la región **B**; es decir, en este caso se selecciona al individuo **B**.

<br>

### **8. Explique el funcionamiento del operador de selección por emparejado variado inverso (NAM).**

El operador de selección NAM consiste en elegir de entre la población a un individuo $P_{1}$ de manera aleatoria, el cual fungirá como uno de los padres. Después, elegir $N$ individuos también de manera aleatoria y seleccionar de entre estos al que sea más diferente a $P_{1}$, para que funja como el segundo padre $P_{2}$. Este operador de selección fomenta la diversidad en la población.

Cabe destacar que, cuando se menciona que el segundo padre $P_{2}$ tiene que ser el individuo más diferente a $P_{1}$, esta diferencia se mide de manera diferente en cada representación. Si los cromosomas tienen una representación binaria, entonces la diferencia puede medirse con la distancia de Hamming; en el caso de la representación real, la diferencia puede medirse usando la distancia euclideana; por último, para una representación de orden, la diferencia puede medirse usando una distancia entre permutaciones, por ejemplo la distancia Kendall tau.

<br>

### **9. Proponga las estructuras de datos necesarias para la implementación de los operadores de selección.**

**Operador de selección por torneo:**

Se utilizarán dos variables, una variable $k$, el cual determina el número de individuos a escoger aleatoriamente y una variable $champion$, el cual almacenará al individuo seleccionado en el torneo. Asímismo, se utilizará un arreglo $scores$ de dimensión $k$, el cual contendra el fitness de los concursantes.

**Operador de selección por proporción:**

Para este operador se utilizará un arreglo $proporcion$ del tamaño de la población para representar la probabilidad de selección. Asímismo, se utilizará una variable $seleccionado$, el cual almacenará al individuo seleccionado en la proporción.

**Operador de selección por ruleta:**

Para este operador se utilizará un arreglo $proporcion$ del tamaño de la población para representar la probabilidad de selección. Asímismo, se utilizará una variable $seleccionado$, el cual almacenará al individuo seleccionado por la ruleta.

<br>

### **10. Implemente tres de los operadores antes mencionados.**

Para implementar los operadores usamos funciones implementadas en tareas anteriores.

**Operador de selección por torneo:**

#funcion alpine1
#CREAR POBLACION DE TAMAÑO 10
tpoblacion = 10
poblacion = generapoblacion(tpoblacion)
scorepoblacion = [0]*tpoblacion
for i in range(0,tpoblacion):
    scorepoblacion[i] = getStateScore(poblacion[i])
    
#OPERADOR POR TORNEO
k = 3
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
for i,p in enumerate(posiciones):
    concursantes[i] = scorepoblacion[p]

mejorfitness = min(concursantes)
elindividuo = posiciones[concursantes.index(min(concursantes))]

**Operador de selección por proporción:**

#OPERADOR PROPORCIONAL
proporcion = [0]*tpoblacion
for i in range(0,len(scorepoblacion)):
    proporcion[i] = scorepoblacion[i]/sum(scorepoblacion)

ordenadoproporcion = sorted(proporcion)

**Operador de selección por ruleta:**

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

**[3]** Yu & Gen. Introduction to Evolutionary Algorithms. 2010. Capítulos 1 al 3.

**[4]** Burke & Kendall. Search Metodologies. 2005 Capítulo 4.