Los algoritmos genéticos (AG) son algoritmos de búsqueda heurística adaptativa que pertenecen a la mayor parte de los algoritmos evolutivos. En cada generación, los cromosomas (nuestra solución candidata) sufren mutación, cruce y selección para producir una mejor población cuyos cromosomas estén más cerca de nuestra solución deseada. El operador de mutación es un operador unario y solo necesita un padre para trabajar. Lo hace seleccionando algunos genes de nuestro cromosoma seleccionado (padre) y luego aplicando el operador de mutación deseado sobre ellos.
En este artículo, hablaré sobre cuatro algoritmos de mutación para parámetros de valor real:
1) mutación uniforme
2) no uniforme
3) mutación de límite
4) mutación gaussiana
Aquí estamos considerando un cromosoma con n números reales (que son nuestros genes) y x i representa un gen e i pertenece a [1,n].
Mutación Uniforme –
En la mutación uniforme seleccionamos un gen aleatorio de nuestro cromosoma, digamos xi y le asignamos un valor aleatorio uniforme.
Sea x i dentro del rango [a i ,b i ] luego asignamos U(a i ,b i ) a x i
U(a i ,b i ) denota un número aleatorio uniforme dentro del rango [a i ,b yo ].
Algorithm – 1. Select a random integer number i from [1,n] 2. Set xi to U(ai,bi).
Mutación límite –
En la mutación límite, seleccionamos un gen aleatorio de nuestro cromosoma, digamos xi y le asignamos el límite superior o el límite inferior de xi .
Sea x i dentro del rango [a i ,b i ] luego asignamos a i o b i a x i .
También seleccionamos una variable r= U(0,1) (r es un número entre 0 y 1).
Si r es mayor o igual a 0,5, asigne bi a x i , de lo contrario asigne a i a x i .
Algorithm –
1. select a random integer number i form [1,n]
2. select a random real value r from (0,1).
3. If(r >= 0.5)
Set xi to bi
else
Set xi to ai
Mutación no uniforme –
En la mutación no uniforme, seleccionamos un gen aleatorio de nuestro cromosoma, digamos xi y le asignamos un valor aleatorio no uniforme.
Sea x i dentro del rango [a i ,b i ] luego le asignamos un valor aleatorio no uniforme.
Usamos una función,
f(G)=(r2*(1-G/Gmax))b ,
donde r2 = un número aleatorio uniforme entre (0,1)
G = el número de generación actual
Gmax = el número máximo de generaciones
b = un parámetro de forma
Aquí seleccionamos un número aleatorio uniforme r1 entre (0,1).
Si r es mayor o igual a 0,5 asignamos (b i -x i ) * f(G) a x i , de lo contrario asignamos (a i + x i ) * f(G).
Algorithm –
1. Select a random integer i within [1,n]
2. select two random real values r1 ,r2 from (0,1).
3. If(r1 >= 0.5)
Set xi to (bi-xi) * f(G)
else
Set xi to (ai+ xi) * f(G)
Mutación Gaussiana –
Gaussian Mutation hace uso de la función de error de Gauss. Es mucho más eficiente en la convergencia que los algoritmos mencionados anteriormente. Seleccionamos un gen aleatorio digamos x i que pertenece al rango [a i ,b i ]. Sea x’ i la descendencia mutada . Cada variable tiene un operador de fuerza de mutación (σ i ). Usamos σ= σ i /(b i -a i ) como un parámetro fijo no dimensionalizado para todas las n variables;
Así, la descendencia x’ i viene dada por —
x’i= xi + √2 * σ * (bi-ai)erf-1(u’i)
Aquí erf() denota la función de error gaussiano.
erf(y)=2⁄√π ∫y0 e-t2 dt
Para el cálculo u i ‘ primero seleccionamos un valor aleatorio u i dentro del rango (0,1) y luego usamos la siguiente fórmula
if(ui>=0.5)
u’i=2*uL*(1-2*ui)
else
u’i=2*uR*(2*ui-1)
De nuevo, u L y u R vienen dados por la fórmula
uL=0.5(erf( (ai-xi)⁄(√2(bi-ai)σ) )+1) uR=0.5(erf( (bi-xi)⁄(√2(bi-ai)σ) )+1)
Referencias:
1. https://www.iitk.ac.in/kangal/papers/k2012016.pdf
2. https://en.wikipedia.org/wiki/Mutation_(genetic_algorithm)
3. http://read.pudn .com/downloads152/ebook/662702/gaotv5.pdf