Algoritmos de optimización de la población: Algoritmo genético binario (Binary Genetic Algorithm, BGA). Parte I

Contenido:

1. Introducción
2. Formas de representar atributos: real y binario
3. Ventaja de la representación con código binario de Gray
4. Métodos de selección
5. Tipos de método de cruce
6. Tipos de método de "mutación"
7. Conclusiones

1. Introducción

En este artículo, detallaremos los métodos y técnicas utilizados en los algoritmos genéticos, que pueden servir como herramientas y bloques de construcción para crear diversos algoritmos de optimización en soluciones personalizadas. El objetivo de este artículo será describir y ofrecer herramientas para el estudio de problemas de optimización en cualquier algoritmo de optimización, no solo en los genéticos.

2. Formas de representar atributos: real y binario

Los parámetros de los problemas de optimización suelen denominarse "características" y deben representarse de una forma determinada para poder utilizarse en la lógica de un algoritmo de optimización. En genética, estos rasgos se dividen en fenotipo y genotipo. El fenotipo representa el aspecto del parámetro a optimizar y el genotipo representa la forma en que se representa en el algoritmo. En la mayoría de los algoritmos de optimización, el fenotipo coincide con el genotipo y se representa como un número real. Un gen es un parámetro optimizable, y a su vez un cromosoma es un conjunto de genes, es decir, un conjunto de parámetros optimizables.

La representación de datos reales se usa para representar números fraccionarios. Los números reales pueden tener una parte decimal y una parte fraccionaria separadas por un punto decimal, por ejemplo, "3,14" y "0,5" son números reales.

Por su parte, la representación binaria de datos usa el sistema numérico binario, en el que los números se representan mediante dos símbolos: "0" y "1" y cada dígito se denomina bit. Por ejemplo, el número "5" puede representarse en forma binaria como "101".

La principal diferencia entre la representación de datos reales y binarios es la manera en que se codifican los números. Los números reales suelen codificarse usando normas como la IEEE 754, que define formatos para representar números de coma flotante. En MQL5, el tipo de datos "double" se usa para números reales, que pueden describir un total de 16 dígitos significativos en un número. Esto significa que el número total de dígitos no puede ser superior a dieciséis, por ejemplo, "9 999 999 999 999 999.0" y "9 999 999.999 999 99" y "0.999 999 999 999 999 9" tienen dieciséis dígitos "9" en el número total de dígitos antes y después del punto decimal. Más adelante veremos por qué es importante.

Los números reales son prácticos para escribir programas y en la vida cotidiana, mientras que la representación binaria se usa para trabajar en sistemas informáticos y realizar operaciones de bajo nivel, como operaciones lógicas y operaciones a nivel de bits.

En el contexto de los algoritmos de optimización, incluido el algoritmo genético, los datos pueden representarse como números reales o binarios, que se usan para codificar soluciones y realizar operaciones con ellas.

La ventaja de usar números reales en los algoritmos de optimización es la posibilidad de trabajar con valores de parámetros continuos. La representación real permite utilizar números para codificar características y realizar operaciones de búsqueda de soluciones directamente sobre esos números. Por ejemplo, si la solución es un vector con valores numéricos, cada elemento del vector podrá codificarse con un número real.

Sin embargo, la representación real tiene desventajas. Los elementos individuales del problema de optimización pueden ser independientes y representar espacios multidimensionales no superpuestos. Esto crea dificultades para localizar la solución global, pues la búsqueda puede verse obstaculizada por la partición del espacio en subespacios independientes.

La ventaja de la representación de características binarias es la posibilidad de combinar todas las características en una única descripción completa de espacios multidimensionales no superpuestos. Esto permite enlazar espacios multidimensionales individuales en un espacio de búsqueda común. La representación binaria también facilita la realización de operaciones elementales a nivel de bits, como el operador de "mutación", ya que, a diferencia de los números reales, en los que se requieren operaciones adicionales que demandan mucho trabajo, estas se realizan más fácilmente con la representación binaria.

Las desventajas de la representación binaria en el algoritmo de optimización son la necesidad de convertir a números reales, sobre los que opera en última instancia el problema de optimización, y la presencia de operaciones adicionales que consumen mucho tiempo, como el almacenamiento de la representación de bits como un array de longitud significativa.

Así, los números reales ofrecen la flexibilidad de trabajar con valores continuos, mientras que la representación binaria permite combinar características en una única entidad y realizar operaciones bit a bit sobre ellas con mayor eficacia. Los algoritmos de optimización, aparte de los genéticos, bien pueden usar los dos modos de representación para obtener las ventajas de ambos.

3. Ventaja de la representación con código binario de Gray

A pesar de todas sus ventajas, la representación binaria tiene un inconveniente importante: dos números decimales cercanos en la representación binaria pueden diferir en varios bits a la vez. Por ejemplo, en un código binario, pasar de 7 (0111) a 8 (1000) implica cambiar los cuatro bits. Esto significa que se requiere un número diferente de operaciones de bits entre distintos números cercanos, lo cual conduce a una probabilidad desigual de resultados en el espacio de búsqueda, la aparición de una especie de "bandas de alta probabilidad" y viceversa, de "puntos ciegos" en los parámetros optimizados.

Por ejemplo, si queremos realizar una operación aritmética con dos números que solo difieren en una unidad en la representación decimal, en la representación binaria podría ser necesario cambiar varios bits. Como resultado, la probabilidad de obtener el número correcto después de la operación será desigual, a diferencia de otro par de números, porque el cambio de cada bit afecta al resultado final. Este fenómeno puede resultar especialmente problemático al realizar cálculos en coma flotante, donde la precisión de la representación de los números es importante y pequeños cambios en la representación decimal de los números pueden provocar cambios significativos en su representación binaria y, como consecuencia, en los resultados del cálculo.

En la representación binaria mediante el código de Gray, también conocida como código binario reflexivo, cada número se representa como un conjunto de bits, pero cada número sucesivo difiere del anterior solo en un bit cambiado. Esto ofrece una secuencia transitiva suave de números, esta propiedad se denomina "propiedad de distancia unitaria".

Ya hemos comentado que el número "double" solo puede representarse con 16 cifras significativas. Veamos un ejemplo para entender mejor cómo puede repercutir esto en la práctica.

Supongamos que tenemos un número con 15 "0" y "1" significativos en la decimosexta cifra: "0.0000000000000001". Ahora sumemos 1,0 a ese número y obtendremos "1.0000000000000000". Observe que el dígito "1" de la decimosexta cifra ha desaparecido, y nos quedan 15 cifras significativas después de la coma. Al añadir un nuevo dígito a la parte entera de un número "double", las cifras significativas se desplazarán hacia la izquierda. Por ello, si tenemos una parte entera distinta de cero, no podremos garantizar la precisión hasta el decimosexto decimal.

En la representación binaria, y en particular cuando se usa el código de Gray, podemos evitar el problema de la pérdida de precisión en los dígitos si nos lo proponemos o si una tarea concreta lo requiere. Veamos este aspecto con mayor atención.

Las computadoras trabajan con programas y números en representación binaria porque es la forma más eficaz y natural que tienen las máquinas de procesar la información. Sin embargo, para facilitar la comprensión y la escritura de algoritmos de optimización de alto nivel, necesitaremos un esfuerzo adicional para trabajar con números en forma binaria, especialmente en el caso de los números negativos y los números con partes fraccionarias.

Para trabajar con números en forma binaria, existen diversas bibliotecas y herramientas en el nivel superior de programación que facilitan el procesamiento y la representación de números negativos y números con partes fraccionarias, pero implementaremos todo lo necesario en el marco de la escritura del algoritmo de optimización, en MQL5.

El método del código de adición se usa para representar números negativos en el sistema numérico binario. Permite visualizar un número negativo invirtiendo todos los bits del este y sumando uno al resultado obtenido. Sin embargo, aplicaremos un pequeño truco y evitaremos operaciones adicionales para trabajar con números negativos, para ello simplemente nos desharemos de ellos. Supongamos que uno de los parámetros a optimizar tiene límites:

min = -156.675 y max = 456.6789

entonces la distancia entre "max" y "min" será igual a:

distance = max - min = 456.6789 - (-156.675) = 613.3539

Por tanto, el número deseado en el problema de optimización siempre será positivo y se situará a la derecha de 0,0 en la recta numérica y tendrá un valor máximo igual a 613,3539. Ahora la tarea consiste en ofrecer la codificación de un número real, para ello dividiremos este número en partes enteras y fraccionarias. La parte entera usando el código de Gray se representará como sigue: los paréntesis denotan el método de representación:

613 (decimal) = 1 1 0 1 0 1 0 1 1 1 (binary Gray)

Entonces la parte fraccionaria tendrá este aspecto:

3539 (decimal) = 1 0 1 1 0 0 1 1 1 0 1 0 (binary Gray)

Podemos almacenar las partes enteras y fraccionarias en la misma cadena, recordando el número de dígitos usados para ambas partes, lo cual nos permitirá realizar fácilmente la conversión inversa. Como resultado, un número real tendrá este aspecto (el signo ":" separa de forma convencional las partes enteras de las fraccionarias):

613.3539 (decimal) =  1 1 0 1 0 1 0 1 1 1  :  1 0 1 1 0 0 1 1 1 0 1 0 (binary Gray)

Así, podemos convertir cualquier número real dentro de 16 dígitos en la parte entera y 16 decimales en la parte fraccionaria para números de tipo double. Además, esto nos permitirá tener más de 16 dígitos significativos en total, incluso hasta 32 dígitos significativos o más (limitado por la longitud del registro numérico de tipo ulong, utilizado en las funciones para manejar las conversiones de números enteros decimales a código de Gray y viceversa).

Para garantizar que la parte fraccionaria sea exacta hasta el decimosexto dígito, tendremos que convertir el número "9 999 999 999 999 999" (el máximo número de parte fraccionaria posible):

9999999999999999 (decimal) = 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (binary Gray)

Entonces, la notación final de nuestro número 613.9999999999999999 (sí, sí, 16 decimales) quedaría así:

613.9999999999999999 (decimal) = 1 1 0 1 0 1 0 1 1 1  :  1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (binary Gray)

Como podemos ver, el usuario puede especificar cualquier precisión decimal dentro de la longitud del tipo ulong.

Vamos a analizar las funciones para trabajar con la conversión de enteros decimales a código de Gray y viceversa. Para codificar en el código de Gray y descodificar este, utilizaremos funciones adicionales para convertir a código binario normal.

La función "DecimalToGray" toma como parámetros el número decimal "decimalNumber" y una referencia al array "array" donde se almacenará el resultado de la conversión. Esta realiza la conversión de un número de notación decimal a código de Gray. Para ello, primero calcula el valor del código de Gray "grayCode" aplicando una operación XOR a nivel de bits entre "decimalNumber" y desplazándolo un bit a la derecha. A continuación, llama a la función "IntegerToBinary" para convertir el valor "grayCode" resultante en una representación binaria y almacenarlo en el array "array". Para un array, se utiliza el almacenamiento más económico de enteros con el tipo char.

La función "IntegerToBinary" toma como parámetros el número "number" y una referencia al array "array" donde se almacenará el resultado de la conversión. Esta realiza la conversión de un número de un sistema numérico decimal a un sistema numérico binario. En el ciclo, obtiene el resto de dividir "number" entre 2 y lo añade al array "array". A continuación, divide "number" por 2 e incrementa el contador "cnt". El ciclo continúa mientras "number" sea mayor que cero. Después del ciclo, el "array" se voltea para obtener el orden correcto de los bits.

La función "GrayToDecimal" toma como parámetros una referencia al array "grayCode", el índice inicial "startInd" y el índice final "endInd". Realiza la conversión de un número del código de Gray a la notación decimal. Primero llama a la función "BinaryToInteger" para convertir el array "grayCode" en una representación binaria y almacenarla en la variable "grayCodeS". A continuación, inicializa la variable "result" con el valor "grayCodeS". A continuación, ejecuta un ciclo en el que desplaza "grayCodeS" un bit a la derecha y aplica una operación XOR a nivel de bit con "result". El ciclo continuará mientras "grayCodeS" esté desplazado hacia la derecha y sea mayor que cero. Al final, la función retorna el valor "result".

La función "BinaryToInteger" toma como parámetros una referencia al array "binaryStr", el índice inicial "startInd" y el índice final "endInd". Realiza la conversión de un número del sistema numérico binario al sistema numérico decimal. La función inicializa la variable "result" con un cero. A continuación, ejecuta un ciclo en el que desplaza "result" un bit a la izquierda y añade el valor de "binaryStr[i]" (bit) a "result". El ciclo continúa de "startInd" a "endInd". Al final, la función retorna el valor "result".

Nótese que la transformación inversa del código de Gray usa los índices de posición inicial y final. Esto permite extraer solo cierto número de parámetros optimizados de la "cadena" en la que se guardan todos los parámetros optimizados. Conocemos la longitud total de la cadena, incluidas las partes enteras y fraccionarias, y, por tanto, podemos determinar la posición concreta de los números en la cadena total del cromosoma, incluido el lugar donde se unen las partes enteras y fraccionarias.

//——————————————————————————————————————————————————————————————————————————————
//Converting a decimal number to a Gray code
void DecimalToGray (ulong decimalNumber, char &array [])
{
  ulong grayCode = decimalNumber ^(decimalNumber >> 1);
  IntegerToBinary(grayCode, array);
}

//Converting a decimal number to a binary number
void IntegerToBinary (ulong number, char &array [])
{
  ArrayResize(array, 0);
  ulong temp;
  int cnt = 0;
  while (number > 0)
  {
    ArrayResize (array, cnt + 1);
    temp = number % 2;
    array [cnt] = (char)temp;
    number = number / 2;
    cnt++;
  }

  ArrayReverse (array, 0, WHOLE_ARRAY);
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Converting from Gray's code to a decimal number
ulong GrayToDecimal (const char &grayCode [], int startInd, int endInd)
{
  ulong grayCodeS = BinaryToInteger(grayCode, startInd, endInd);
  ulong result = grayCodeS;

  while ((grayCodeS >>= 1) > 0)
  {
    result ^= grayCodeS;
  }
  return result;
}

//Converting a binary string to a decimal number
ulong BinaryToInteger (const char &binaryStr [], const int startInd, const int endInd)
{
  ulong result = 0;
  if (startInd == endInd) return 0;

  for (int i = startInd; i <= endInd; i++)
  {
    result = (result << 1) + binaryStr [i];
  }
  return result;
}
//——————————————————————————————————————————————————————————————————————————————

4. Métodos de selección

En los algoritmos de optimización, la selección es el proceso de selección de las mejores soluciones de una población o conjunto de candidatos para crear la siguiente generación y desempeña un papel crucial en los métodos de optimización. No solo la capacidad de búsqueda del algoritmo, sino también su tasa de convergencia dependen de la elección de una determinada opción de selección. Todos los métodos de selección tienen ventajas y desventajas y pueden resultar más eficientes en algunos algoritmos y menos eficientes en otros. La aplicación de cada una de ellos dependerá de la estrategia de búsqueda específica.

Existen varios tipos principales de selección que se utilizan para seleccionar individuos parentales y formar una nueva generación. Veamos en detalle cada uno de estos tipos de selección:

• Selección uniforme (Uniform Selection): es un método de selección parental en el que cada individuo tiene las mismas posibilidades de ser seleccionado. En este método, cada individuo de la población tiene las mismas probabilidades de ser seleccionado para la reproducción. La ventaja de la selección uniforme es que ofrece las mismas posibilidades de selección a cada individuo. Sin embargo, este método no tiene en cuenta la adaptabilidad de los individuos, por lo cual puede resultar menos eficaz para encontrar una solución óptima, especialmente cuando algunos individuos tienen una adaptabilidad significativamente mayor que otros. La selección uniforme puede ser útil en algunos casos, como cuando tenemos que explorar distintas regiones del espacio de soluciones o cuando hay que mantener un alto grado de diversidad en una población.

• Selección por rango (Rank Selection): en este método, los individuos se clasifican según su aptitud y la probabilidad de seleccionar un individuo depende de su rango. Cuanto mayor sea el rango de un espécimen, más posibilidades tendrá de ser seleccionado. La selección basada en el rango puede ser totalmente proporcional, es decir, la probabilidad de seleccionar a un individuo puede ser proporcional a su rango (número ordinal), o parcialmente proporcional; en esta, la probabilidad de seleccionar a un individuo aumentará con el rango según una ley no lineal. La selección por rango presenta una serie de ventajas. En primer lugar, preserva la diversidad de la población, puesto que los individuos menos aptos también tendrán la oportunidad de ser seleccionados. En segundo lugar, evita el problema de la convergencia prematura, cuando la población converge demasiado rápido a un óptimo local. La selección por rango favorece la preservación de la diversidad y la exploración de un espacio de soluciones mayor. La selección basada en el rango resulta similar a la selección uniforme, pero pone más énfasis en seleccionar a los individuos mejor adaptados dejando la posibilidad de ser seleccionados a los menos adaptados.
  

• Selección por torneo (Tournament Selection): en este método, se selecciona aleatoriamente un pequeño subconjunto de individuos (denominado torneo) y, de este subconjunto, se elige al individuo con la mayor aptitud. El tamaño del torneo determinará cuántas personas participarán en cada torneo. La selección por torneo preserva la diversidad en una población porque incluso los individuos menos aptos pueden ser seleccionados por azar. La selección por torneo tiene varias ventajas. En primer lugar, permite la aleatoriedad en la elección de los progenitores, lo cual favorece la diversidad de la descendencia. En segundo lugar, permite seleccionar progenitores de cualquier región de la población, incluidos tanto los individuos más aptos como los menos aptos. La selección por torneo es uno de los principales métodos de selección parental en los algoritmos evolutivos y suele usarse en combinación con otros operadores, como el cruce y la mutación, para crear nuevos descendientes y continuar la evolución de una población.
  

• Selección por ruleta (Roulette Wheel Selection): en este método, cada individuo se presenta en una ruleta imaginaria en proporción a su aptitud. La ruleta "gira" y se selecciona al individuo al que señale el "puntero". Cuanto mayor sea la aptitud de un individuo, mayor será el sector de la ruleta que ocupe y mayor la probabilidad de ser elegido. La selección por ruleta permite seleccionar a los progenitores con probabilidades proporcionales a su aptitud. Los individuos más aptos tendrán más posibilidades de ser seleccionados, pero incluso los menos aptos tendrán una probabilidad de ser seleccionados distinta de cero. Esto preservará la diversidad genética en la población y nos permitirá explorar diferentes regiones del espacio de soluciones. Sin embargo, debemos señalar que la selección por ruleta puede tener un problema de convergencia prematura, sobre todo si la adaptabilidad de los individuos difiere mucho. Los individuos con una gran adaptabilidad tendrán muchas más posibilidades de ser seleccionados, lo cual puede llevar a una pérdida de diversidad genética, "atascando" la población con soluciones uniformes y provocando el estancamiento en óptimos locales.

Como medida adicional que puede utilizarse junto con cualquier método de selección, puede emplearse el método del "elitismo". Consiste en preservar los mejores individuos de la población actual y transmitirlos sin cambios a la generación siguiente. El uso del método de "elitismo" permite conservar a los mejores individuos de generación en generación, lo cual ayuda a mantener una adaptabilidad elevada y evita la pérdida de información útil. Esto ayuda a acelerar la convergencia del algoritmo y a mejorar la calidad de la solución encontrada.

Sin embargo, debemos considerar que el uso del "elitismo" puede conducir a una pérdida de diversidad genética, especialmente si el elitismo se establece a un nivel elevado. Por tanto, resulta importante elegir un valor apropiado de elitismo para mantener un equilibrio entre la preservación de los mejores individuos y la exploración del espacio de soluciones.

5. Tipos de método de cruce

El cruce (o crossing over) es una de las principales operaciones importantes de los algoritmos genéticos que imita el proceso de cruce en la evolución natural. Consiste en combinar la información genética de dos individuos parentales para crear descendencia y transmitir rasgos hereditarios a los hijos. El cruce tiene sentido no solo como transferencia de información, sino que también tiene un enorme impacto en las cualidades combinatorias del algoritmo.

El cruce funciona a nivel del genotipo y permite combinar los genes de los individuos parentales para crear descendencia nueva.

El principio general del método de cruce es el siguiente:

1. Selección parental: se seleccionan dos o más individuos de la población para que se crucen.
   
2. Determinación del punto de cruce: el punto de cruce determina el lugar en el que los cromosomas de los padres se separarán para crear la descendencia.
3. Creación de la descendencia: los cromosomas de los padres se separan en el punto de cruce, y partes de los cromosomas de ambos padres se combinan para crear un nuevo genotipo descendiente. El cruce da lugar a uno o más descendientes que pueden tener una combinación de genes de ambos progenitores.

Figura 1. Principio general del método de "cruce".

Vamos a enumerar los principales tipos de cruce binario:

• Cruce de un solo punto (Single-Point Crossover): dos cromosomas se separan en un punto aleatorio y se producen dos descendientes intercambiando segmentos de los cromosomas de los padres después de ese punto.
• Cruce multipunto (Multi-Point Crossover): similar al cruce de un solo punto, pero con múltiples puntos de ruptura entre los que se intercambian segmentos de cromosomas.
  
• Cruce uniforme: cada bit de la descendencia se selecciona independientemente de uno de los padres con igual probabilidad.
  
• Cruce cíclico (Cycle Crossover): define ciclos de elementos que se intercambiarán entre los padres, preservando la unicidad de los elementos.
• PMX (Partially Mapped Crossover): preserva el orden relativo y la posición de los elementos de los cromosomas padres, se usa en tareas en las que el orden resulta importante, por ejemplo, en el problema del viajante de comercio.
• OX (Order Crossover): crea un descendiente conservando el orden de los genes de un progenitor y heredando los genes ausentes del otro progenitor en el orden en que aparecen.
  

Asimismo, los cruces se aplican no solo para la representación binaria sino también para la representación real, es decir, los principales tipos de cruces reales incluyen:

• Cruce mixto (BLX-α): crea descendientes cuyos valores se seleccionan aleatoriamente dentro de un rango definido por los valores de los padres y un parámetro "α" que amplía ese rango.
• Cruzamiento de mezcla simétrica (SBX): usa diferentes distribuciones de probabilidad para generar descendientes cuyos valores se encuentren entre los de los padres, considerando el grado de diferencia entre los padres.
  
• Cruce con código real (real-coded crossover): aplica operaciones aritméticas a números reales, por ejemplo, mediante la media o la suma ponderada de los valores de los padres.
  
• Cruce diferencial (Differential Crossover): se utiliza, por ejemplo, en la evolución diferencial, donde se genera un nuevo vector sumando la diferencia ponderada entre dos individuos a un tercero.
  
• Cruce por interpolación (Interpolation Crossover): crea descendientes interpolando entre los valores de los padres, lo que puede implicar una interpolación lineal o no lineal.
  
• Cruce de distribución normal (Normal Distribution Crossover): los descendientes se generan utilizando una distribución normal en torno a los valores de los padres, lo que permite explorar el espacio de soluciones en torno a los puntos de los padres.
  

6. Tipos de método de "mutación"

El operador de mutación es una de las operaciones básicas de los algoritmos genéticos y se usa para realizar cambios aleatorios en la información genética de los individuos de una población. Ayuda a explorar nuevas soluciones y a evitar estancarse en óptimos locales.

En biología, una mutación resulta extremadamente rara y suele tener un efecto limitado en la descendencia. El número de individuos de cada especie en la naturaleza se cuenta por millones, por lo que el material genético de la población resulta muy diverso, a menos, claro está, que hablemos de especies en peligro de extinción (existe incluso una definición de "cuello de botella", es decir, el número mínimo de individuos por debajo del cual una especie desaparecerá). A diferencia de lo que sucede en la naturaleza viva, las mutaciones también son raras en la mayoría de las implementaciones de algoritmos genéticos, en torno al 1-2%. Esto es especialmente importante en los algoritmos genéticos, donde el tamaño de las poblaciones suele ser pequeño y la endogamia estrecha puede resultar problemática, mientras que los estancamientos evolutivos son más comunes que en la evolución biológica. En biología solemos hablar de poblaciones de millones de individuos, al tiempo que en los algoritmos genéticos (y en los algoritmos de optimización en general) solo tratamos con decenas o centenares de individuos y la mutación es la única forma de añadir nueva información al acervo genético de una población.

Por ello, si falta alguna información genética en una población, una mutación ofrecerá la oportunidad de introducir dicha información.

Así pues, la mutación desempeña varias funciones importantes:

1. Exploración de nuevas soluciones: Esto permite al algoritmo explorar nuevas soluciones potenciales al problema que puedan encontrarse fuera del espacio de soluciones explorado por el cruce. La mutación permite al algoritmo "saltar" por el espacio de soluciones y descubrir nuevas variantes.
2. Mantenimiento de la diversidad genética: Sin mutación, el algoritmo puede enfrentarse al problema de la convergencia a un óptimo local en el que todos los individuos tienen información genética similar. La mutación permite los cambios aleatorios, cosa que ayuda a evitar la convergencia prematura y a mantener la diversidad en la población.
3. Superación de los bloqueos evolutivos: Durante la evolución, los algoritmos genéticos a veces se atascan en puntos muertos evolutivos en los que el espacio de soluciones se agota y resulta imposible alcanzar una solución mejor. La mutación puede ayudar a superar estos bloqueos introduciendo cambios aleatorios que pueden abrir nuevas oportunidades y permitir que el algoritmo siga avanzando.

Una probabilidad de mutación demasiado alta puede provocar la degeneración del algoritmo en una búsqueda aleatoria; una probabilidad demasiado baja puede provocar problemas de convergencia y pérdida de diversidad.

Para los algoritmos con representación binaria, podemos distinguir los siguientes tipos de métodos de mutación:

• Mutación de un solo punto (single-point mutation): en este caso se invertirá el valor de un bit seleccionado al azar en una cadena binaria. Por ejemplo, si tenemos una cadena "101010", una sola mutación puntual puede cambiarla a "100010".
• Mutación multipunto (multi-point mutation): en este caso se seleccionan varias posiciones aleatorias en una cadena binaria y se invierten los valores en dichas posiciones. Por ejemplo, si tenemos una cadena "101010", una mutación multipunto puede cambiarla a "100000" o "001010".
  
• Mutación basada en la probabilidad (probability-based mutation) o mutación estocástica (stochastic mutation): en este caso, cada bit tiene una determinada probabilidad de cambiar al mutar.
  
• Inversión completa (complete inversion): en este caso, los bits de la cadena binaria están completamente invertidos. Por ejemplo, si tenemos una cadena "101010", la inversión la cambiará a "010101".
• Inversión de punto (point inversion): en este caso, se selecciona al azar un punto de ruptura en la secuencia genética, el cromosoma se divide en dos partes en este punto y las partes se intercambian.  

Figura 2. Mutación basada en probabilidades (probability-based mutation).

En los algoritmos de optimización con representación de datos reales se distinguen los siguientes tipos de mutaciones, sobre los que no vamos a detenernos:

• Operador de mutación aleatoria (Random Mutation Operator).
• Operador de mutación gaussiano (Gaussian Mutation Operator).
• Operador aritmético de desplazamiento de números reales, también conocido como "arithmetic real number creep operator".
• Operador geométrico de fluencia de números reales, también conocido como "geometrical real number creep operator".
• El operador de mutación de potencia (power).
• Operador de mutación no uniforme de Michalewicz (Michalewicz's non-uniform operator).
• Operador de mutación dinámico (dynamic).

En general, en todos los algoritmos de optimización, todas las operaciones de modificación de los componentes del espacio de búsqueda, si no hay intercambio de información entre los agentes (individuos), pueden denominarse mutación y, de hecho, suelen ser muy específicas según la estrategia de búsqueda concreta del algoritmo.

7. Conclusiones

Esta es la primera parte del artículo sobre el "Algoritmo Genético Binario". En ella hemos abarcado casi todos los métodos usados no solo en este algoritmo sino también en otros algoritmos de optimización de poblaciones, incluso si no utilizan los términos "selección", "cruce" y "mutación". Si estudiamos y comprendemos bien estos métodos, podremos abordar los problemas de optimización con más conocimiento de causa, y podremos tener nuevas ideas para aplicar y modificar algoritmos conocidos, así como para crear otros nuevos. También hemos estudiado distintas formas de representar la información en los algoritmos de optimización, así como sus ventajas e inconvenientes, lo cual puede dar lugar a nuevas ideas y enfoques novedosos.