Practica 12 Algoritmos Genéticos

# Practica 12 Algoritmos Genéticos ### Operadores de cruzamiento en Algoritmos Genéticos **Profesora**: Dra. Yenny Villuendas Rey **Escuelas**: $^{1}$ Escuela Superior de Cómputo del IPN $^{2}$ Centro de Investigación en Computación del IPN **Equipo**: - $^{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/practica12) <style tyle="text/css"> p { text-align: justify; } </style> ### **1. Explique el funcionamiento del operador de cruzamiento de un punto de corte.** El operador de cruzamiento de un punto de corte funciona de la siguiente manera. Cada cromosoma se corta en un punto seleccionado (para así dividir el cromosoma en dos), posteriormente se recombinan las dos partes creadas para así poder obtener a los descendientes, una parte abarca desde el inicio del cromosoma hasta el punto de corte y la otra parte abarca desde el punto de corte hasta el final del cromosoma. A continuación se ilustra un ejemplo. Se seleccionan dos cromosomas padres $P_1$ y $P_2$ de dimensión 6, para el cruzamiento. $$ P_{1} = (5,4,3,6,1,2) \\ P_{2} = (3,1,6,2,5,4) $$ Se selecciona un punto de corte aleatorio dentro de la dimensión de los cromosomas (en este caso entre 1 y 6), supóngase que se selecciona el punto 4; entonces, se copia a un hijo $C_1$ la subsecuencia de genes de $P_1$ (marcada en rojo) entre el punto de corte y el inicio del cromosoma. Posteriormente, se copia a ese hijo $C_1$ la subsecuencia de genes de $P_2$ (marcada en verde), el cual abarca desde el siguiente gen en el punto de corte hasta el último gen del cromosoma. Para obtener a un segundo hijo $C_2$ se repite el mismo procedimiento usando el mismo punto de corte e intercambiando el rol de los padres. $$ P_{1} = (\color{red}5,\color{red}4,\color{red}3,\color{red}6,1,2) \\ P_{2} = (3,1,6,2,\color{green}5,\color{green}4) $$ Por lo tanto, el cruzamiento resultaría de la siguiente forma: $$ C_{1} = (\color{red}5,\color{red}4,\color{red}3,\color{red}6,\color{green}5,\color{green}4) \\ C_{2} = (\color{green}3,\color{green}1,\color{green}6,\color{green}2,\color{red}1,\color{red}2) $$ ### **2. Explique el funcionamiento del operador de cruzamiento de dos puntos de corte.** El operador de cruzamiento de dos puntos de corte funciona de la siguiente manera. Cada cromosoma se corta en dos puntos seleccionados del cromosoma (para así dividir el cromosoma en dos), posteriormente se recombinan las dos partes creadas para así poder obtener a los descendientes, una parte abarca los genes dentro de los puntos de corte del cromosoma y la otra parte abarca los genes fuera de estos puntos de corto del cromosoma. A continuación se ilustra un ejemplo. Se seleccionan dos cromosomas padres $P_1$ y $P_2$ de dimensión 8, para el cruzamiento. $$ P_{1} = (5,4,3,6,1,2,7,8) \\ P_{2} = (3,1,6,2,5,4,8,9) $$ Se seleccionan dos puntos de corte aleatorio dentro de la dimensión de los cromosomas (en este caso entre 1 y 8), supóngase que se seleccionan los puntos 4 y 7; entonces, se copia a un hijo $C_1$ la subsecuencia de genes de $P_1$ (marcada en rojo) entre estos dos puntos. Posteriormente, se colocan en $C_1$ los genes del padre $P_2$ (marcados en verde), omitiendo todos aquellos que fueron copiados de $P_1$. Para obtener a un segundo hijo $C_2$ se repite el mismo procedimiento usando los mismos puntos de corte e intercambiando el rol de los padres. $$ P_{1} = (\color{red}5,\color{red}4,\color{red}3,6,1,2,7,\color{red}8) \\ P_{2} = (3,1,6,\color{green}2,\color{green}5,\color{green}4,\color{green}8,9) $$ Por lo tanto, el cruzamiento resultaría de la siguiente forma: $$ C_{1} = (\color{red}5,\color{red}4,\color{red}3,\color{green}2,\color{green}5,\color{green}4,\color{green}8,\color{red}8) \\ C_{2} = (\color{green}3,\color{green}1,\color{green}6,\color{red}6,\color{red}1,\color{red}2,\color{red}7,\color{green}9) $$ ### **3. Explique el funcionamiento del operador de cruzamiento uniforme.** El operador de cruce uniforma no divide el cromosoma en segmentos, sino que trata a cada gen por separado; es decir, por cada gen de los cromosomas padres se decide aleatoriamente (teniendo las mismas probabilidades de pertenecer a uno u otro padre) si se incluirá o no ese gen en la descendencia del nuevo hijo. De igual forma, en la selección aleatoria de los genes de los padres que se incluirán en la descendencia, se les puede agregar una mayor probabilidad a uno de los padres, para así tener más genes de ese padre en la descendencia del nuevo hijo. Para producir un segundo hijo se intercambian los roles de los padres. A continuación se ilustra un ejemplo. Se seleccionan dos cromosomas padres $P_1$ y $P_2$ de dimensión 6, para el cruzamiento. $$ P_{1} = (5,4,3,6,1,2) \\ P_{2} = (3,1,6,2,5,4) $$ Para facilitar la selección de los genes de los padres a heredar a sus hijos, se puede crear un vector de cruce con valores binarios (0 y 1), el cual indicará si el gen situado en esa posición se copia del primer padre (valor 1) o por el contrario se copia del segundo padre (valor 0). Un vector de cruce puede ser el siguiente: $$ C = (1,1,0,1,0,0) $$ Por lo tanto, en el hijo $C_1$ los genes en color rojo vendran del padre $P_1$ mientras que los genes en color verde se heredan del padre $P_2$. Para generar un segundo hijo $C_2$, unicamente se intercambian los roles de los padres. Los hijos son de la siguiente forma $$ C_1 = (\color{red}5,\color{red}4,\color{green}6,\color{red}6,\color{green}5,\color{green}4) \\ C_2 = (\color{green}3,\color{green}1,\color{red}3,\color{green}2,\color{red}1,\color{red}2) $$ ### **4. Explique el funcionamiento del operador de cruzamiento aritmético.** El operador de cruce aritmetico o recombinación aritmética consiste en combinar ambos padres para obtener una nueva posible solución (hijo) apartir de sus valores reales. Existen muchos operadores específicos para la codificación real; sin embargo, un operador sencillo seria combinar a ambos padres calculando su valor promedio aritmetico entre cada gen. A continuación se ilustra un ejemplo. Se seleccionan dos cromosomas padres $P_1$ y $P_2$ de dimensión 6, para el cruzamiento. $$ P_{1} = (5,4,3,6,1,2) \\ P_{2} = (3,1,6,2,5,4) $$ Para obtener a su (único) hijo $c_1$ se realiza el cálculo de la siguiente manera: $$ C_{1} = \left( \frac{5+3}{2},\frac{4+1}{2},\frac{3+6}{2},\frac{6+2}{2},\frac{1+5}{2},\frac{2+4}{2} \right) $$ Por tanto, el cromosoma del hijo resulta de la siguiente forma: $$ C_{1} = (4,2.5,4.5,4,3,3) $$ ### **5. Explique el funcionamiento del operador de cruzamiento blx-α.** El operador blx-$\alpha$ es un operador de cruze para representaciones reales. Dados dos padres: \begin{align} P_{1} = (p_{11},\dots,p_{1n}), \\ P_{2} = (p_{21},\dots,p_{2n}), \end{align} el operador blx-$\alpha$ genera dos descendientes: \begin{align} C_{1} = (c_{11},\dots,c_{1n}), \\ C_{2} = (c_{21},\dots,c_{2n}), \end{align} con $c_{ij}$ generado aleatoriamente en el intervalo $\left[ P_{min} - \lambda \cdot \alpha , P_{max} + \lambda \cdot \alpha \right]$, donde: \begin{align} P_{max} &= \max\left\lbrace p_{ij} \: : \: i=1,2 \, \wedge \, j=1,\dots,n \right\rbrace, \\ P_{min} &= \min\left\lbrace p_{ij} \: : \: i=1,2 \, \wedge \, j=1,\dots,n \right\rbrace, \\ \lambda &= P_{max} - P_{min}, \\ \alpha &\in \left[ 0,1 \right]. \end{align} ### **6. Explique el funcionamiento del operador de cruzamiento Simulated Binary Crossover (SBX).** El operador SBX es un operador de cruze para representaciones reales que busca preservar dos características del operador de cruzamiento de un punto de corte para representaciones binarias: la distribución probabilistica del factor de extensión y que el promedio de la descendencia sea el mismo que el de los padres. El operador SBX actúa como sigue. Dados dos padres: \begin{align} P_{1} = (p_{11},\dots,p_{1n}), \\ P_{2} = (p_{21},\dots,p_{2n}), \end{align} el operador SBX genera dos descendientes: \begin{align} C_{1} = (c_{11},\dots,c_{1n}), \\ C_{2} = (c_{21},\dots,c_{2n}), \end{align} con \begin{align} c_{1j} = \bar{p}_{j} - \frac{1}{2} \beta \left| p_{2j} - p_{1j} \right|, \\ c_{2j} = \bar{p}_{j} + \frac{1}{2} \beta \left| p_{2j} - p_{1j} \right|, \end{align} donde $\bar{p}_{j} = \frac{p_{1j} + p_{2j}}{2}$ y $\beta$ es un número aleatorio que sigue la siguiente función de distribución de probabilidad **[1]**: \begin{equation} \rho(\beta)= \begin{cases} 0.5(n+1)\beta^{n}, \qquad \quad \beta\leq 1 \\ \\ 0.5(n+1)\beta^{-(n+2)}, \quad \beta > 1 \end{cases} \end{equation} ### **7. Explique el funcionamiento del operador de cruzamiento Uniform Order-Based Crossover.** El operador de cruce *Uniform Order-Based Crossover* es la versión para representaciones de orden del operador de cruzamiento uniforme visto en la sección 3. El primer paso es elegir aleatoriamente para cada gen si este se conservará en la misma posición o no, es decir, se crea un vector binario de cruce $C$, en el que una componente igual a $0$ representa que esa posición no se conserva, mientras que una componente igual $1$ representa que sí. Después, denotando por $P_{1}$ y $P_{2}$ a los padres y por $C_{1}$ y $C_{2}$ a los hijos, aquellas posiciones que se conservan (los 1's en $C$) son copiadas de $P_{1}$ a $C_{2}$ y de $P_{2}$ a $C_{1}$. Por último, los espacios vacíos en cada hijo $C_{i}$ son rellenados con los genes que faltan, respetando el orden que estos tienen en el cromosoma de su respectivo padre $P_{i}$. El siguiente ejemplo ilustra el funcionamiento del operador *Uniform Order-Based Crossover*. Se seleccionan dos cromosomas padres $P_1$ y $P_2$ de dimensión 6, para el cruzamiento: $$ P_{1} = (5,4,3,6,1,2), \\ P_{2} = (3,1,6,2,5,4). $$ Supóngase el siguiente vector de cruce: $$ C = (1,1,0,1,0,0). $$ Entonces, los genes en las posiciones $1$, $2$ y $4$ se conservan, y se copian los respectivos genes de $P_{1}$ a $C_{2}$ y de $P_{2}$ a $C_{1}$, es decir: $$ C_1 = (3,1,\_,2,\_,\_), \\ C_2 = (5,4,\_,6,\_,\_). $$ Por último, rellenamos los espacios vacíos con los genes del padre correspondiente, respetando el orden en su cromosoma, dando lugar a: $$ C_1 = (3,1,5,2,4,6), \\ C_2 = (5,4,3,6,1,2). $$ ### **8. Explique el funcionamiento del operador de cruzamiento Order-Based Crossover.** El operador de cruce *Order-Based Crossover (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} ### **9. Proponga las estructuras de datos necesarias para la implementación de los operadores de cruzamiento.** **Operador de cruzamiento aritmetico** Para este operador se utilizará un arreglo $hijo$ de dimensión $n$, el cual esta dado por la longitud de los cromosomas de los individuos de la población. Este arreglo almacenara al hijo ($c_1$) obtenido en el cruzamiento. **Operador de cruzamiento uniforme** Para este operador se utilizaran tres arreglos de dimensión $n$, el cual esta dado por la longitud de los cromosomas de los individuos de la población. Dos arreglos son para los cromosomas de los hijos obtenidos ($c_1$ y $c_2$). El tercer arreglo $vector$_$cruce$ es un vector binario, el cual se utiliza como vector de cruce, para indicar cual gen de los padres seran heredados a los hijos, este vector se genera de manera aleatoria. **Operador *Uniform Order-Based Crossover*** Para este operador se necesitan tres arreglos de longitud $n$, siendo ésta la longitud de los cromosomas de los individuos en la población a considerar. El primer arreglo es para el vector de cruce $C$ con entradas binarias aleatorias. El segundo y tercer arreglos son para los cromosomas de los hijos $C_{1}$ y $C_{2}$. El input para este operador consiste únicamente de dos arreglos de longitud $n$: $P_{1}$ y $P_{2}$, cada uno representando el cromosoma del padre correspondiente. ### **10. Implemente al menos tres de los operadores antes mencionados, considerando su aplicación en problemas de optimización con representaciones binarias, reales y de orden.** Para implementar los operadores usamos funciones implementadas en tareas anteriores. **Operador de cruzamiento aritmetico** Para implementar el cruzamiento aritmetico se tienen a los siguientes padres. $$ P_{1} = (5,4,3,6,1,2) \\ P_{2} = (3,1,6,2,5,4) $$Posteriormente se cruzan ambos padres ($P_1$ y $P_2$) para generar al unico hijo ($c_1$) como se ilustro en el punto 4 del documento. ```python= #OPERADOR DE CRUZAMIENTO ARITMETICO def aritmetico(padres): sizepadres = len(padres[0]) npadres = len(padres) hijo = [0]*sizepadres for i in range(0,sizepadres): suma = 0 for j in range(0,npadres): suma += padres[j][i] hijo[i] = suma/npadres return hijo ``` **Input:** ```python= P1 = [5,4,3,6,1,2] P2 = [3,1,6,2,5,4] padres = [P1,P2] hijo = aritmetico(padres) print("Padre1:", P1, "Padre2:", P2) print("Hijo:", hijo) ``` **Output:** ```python= Padre1: [5, 4, 3, 6, 1, 2] Padre2: [3, 1, 6, 2, 5, 4] Hijo: [4.0, 2.5, 4.5, 4.0, 3.0, 3.0] ``` **Operador de cruzamiento uniforme** Para implementar el cruzamiento uniforme se tienen a los siguientes padres. $$ P_{1} = (1,0,0,1,1,1) \\ P_{2} = (1,0,0,1,0,1) $$ Posteriormente se cruzan ambos padres ($P_1$ y $P_2$) para generar a los hijos ($c_1$ y $c_2$). ```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) if vector_cruce[i] == 0: #copiar de padre1 hijo1[i] = padres[0][i] hijo2[i] = padres[1][i] elif vector_cruce[i] == 1: #copiar de padre2 hijo1[i] = padres[1][i] hijo2[i] = padres[0][i] return hijo1, hijo2, vector_cruce ``` **Input:** ```python= P1 = [1,0,0,1,1,1] P2 = [1,0,0,1,0,1] padres = [P1,P2] #cruzamos a los padres hijo1, hijo2, vector_cruce = uniforme(padres) print("Padre1:", padres[0], "Padre2:", padres[1]) print("Vector de cruce:", vector_cruce) print("Hijo1:", hijo1, "Hijo2:",hijo2) ``` **output:** ```python= Padre1: [1, 0, 0, 1, 1, 1] Padre2: [1, 0, 0, 1, 0, 1] Vector de cruce: [0, 0, 1, 0, 1, 1] Hijo1: [1, 0, 0, 1, 0, 1] Hijo2: [1, 0, 0, 1, 1, 1] ``` **Operador *Uniform Order-Based Crossover*** ```python= def UOX(P1,P2): n = len(P1) #longitud del cromosoma de los padres C = [0]*n #vector de cruce #componentes binarias aleatorias for i in range(0,n): C[i] = random.randint(0,1) C1 = [0]*n #hijos C2 = [0]*n #copiar genes de acuerdo al vector for i in range(0,n): if C[i] == 1: C1[i] = P2[i] C2[i] = P1[i] #rellenar espacios con los genes del padre faltante for i in range(0,n): if C[i] == 0: j = 0 k = 0 while C1[i] == 0: if C1.count(P1[j]) == 0: C1[i] = P1[j] j = j+1 while C2[i] == 0: if C2.count(P2[k]) == 0: C2[i] = P2[k] k = k+1 return [C1,C2] ``` **input:** ```python= P1 = [5,4,3,6,1,2] P2 = [3,1,6,2,5,4] print("Hijo1: " + str(UOX(P1,P2)[0])) print("Hijo2: " + str(UOX(P1,P2)[1])) ``` **output:** ```python= Hijo1: [3, 5, 6, 2, 4, 1] Hijo2: [5, 4, 3, 6, 1, 2] ``` ### **Referencias** **[1]** Kalyanmoy Deb and Ram Bhushan Agrawal (1995). Simulated Binary Crossover for Continuous Search Space. Complex Systems 9, 115-148. **[2]** Katoch, S., Chauhan, S. S., & Kumar, V. (2020). A review on genetic algorithm: past, present, and future. Multimedia Tools and Applications, 1-36. **[3]** Natyhelem G. L. (2006). Algoritmos Genéticos. Universidad Nacional de Colombia. Escuela de Estadística, , 1-36. **[4]** Yu & Gen. Introduction to Evolutionary Algorithms. 2010. Capítulos 1 al 3. **[5]** Burke & Kendall. Search Metodologies. 2005 Capítulo 4.