42. Paso a paso de un algoritmo genético básico
El contenido de este segundo material se centra en la programación paso a paso de un algoritmo genético, abordando no solo su estructura conceptual, sino también la forma en que se implementa en la práctica. A diferencia del anterior, donde se describía el modelo general, aquí se profundiza en la construcción del algoritmo desde una perspectiva más operativa, destacando cada uno de los elementos necesarios para que el proceso evolutivo funcione correctamente.
El punto de partida consiste en la definición de los parámetros del algoritmo genético, los cuales determinan su comportamiento y rendimiento. Entre estos parámetros se encuentran el tamaño de la población, la longitud de los individuos —que depende del número de variables y de la precisión de representación—, y las probabilidades de cruza y mutación, conocidas como PcPcPc y PmPmPm. Se hace una analogía con la naturaleza para justificar estos valores: la cruza ocurre con alta frecuencia en los procesos biológicos, por lo que su probabilidad suele establecerse entre un 60% y un 100%, mientras que la mutación es un fenómeno menos frecuente, por lo que se fija con valores pequeños cercanos a cero, generalmente no mayores al 10% relativo a la longitud del cromosoma. Además, se deben definir los rangos de las variables de decisión, los cuales provienen directamente del problema que se desea resolver.
Un aspecto importante que se introduce en este material es la necesidad de monitorear el desempeño del algoritmo. Para ello se definen variables que permiten conservar, en cada generación, la mejor solución encontrada hasta el momento. Esto incluye tanto el valor de la función objetivo como el cromosoma que representa dicha solución. Esta estrategia, conocida como elitismo implícito o seguimiento del mejor individuo, permite no perder las mejores soluciones a lo largo del proceso evolutivo.
El proceso de implementación comienza con la creación de la población inicial, la cual se genera de forma aleatoria. Esta población se construye como una matriz donde cada fila representa un individuo y cada columna un bit del cromosoma. Los valores se asignan comparando números aleatorios con un umbral de 0.5, de modo que se obtienen cadenas binarias de ceros y unos. Se menciona también que, si se dispone de conocimiento previo del problema, es posible introducir soluciones iniciales no aleatorias para acelerar la convergencia del algoritmo.
Una vez generada la población inicial, se procede a la decodificación de los cromosomas, es decir, a transformar cada cadena binaria en valores reales dentro del rango de las variables del problema. Con estos valores se evalúa la función objetivo, lo que permite medir el desempeño de cada individuo. Este paso marca la transición entre la representación genotípica y la fenotípica, fundamental en los algoritmos genéticos.
A partir de aquí se entra en el ciclo evolutivo, que constituye el núcleo del algoritmo. El primer paso dentro de este ciclo es transformar los valores de la función objetivo en valores de aptitud o fitness. Esta transformación asegura que los individuos con mejor desempeño tengan mayor probabilidad de ser seleccionados. Dependiendo de si el problema es de maximización o minimización, la relación entre función objetivo y aptitud se ajusta para que siempre los mejores individuos posean los valores de aptitud más altos. Se destaca además que, aunque la función objetivo puede tomar valores negativos o positivos, los valores de aptitud siempre deben ser positivos para que el mecanismo de selección funcione correctamente.
Posteriormente se aplica el método de selección por ruleta, también conocido como selección proporcional. Este método asigna probabilidades de selección a cada individuo en función de su aptitud, de manera que los más aptos tienen mayor probabilidad de reproducirse, aunque los menos aptos aún conservan cierta posibilidad de ser elegidos, lo cual mantiene la diversidad en la población.
Con los individuos seleccionados, se procede a aplicar el operador de cruza, que en este caso es de un solo punto, siguiendo la propuesta clásica de John Holland. Se genera un número aleatorio y, si este es menor o igual a la probabilidad de cruza, los individuos seleccionados se combinan intercambiando segmentos de sus cromosomas; en caso contrario, pasan sin cambios a la siguiente etapa. Después de la cruza se aplica el operador de mutación, que consiste en invertir bits individuales (de 0 a 1 o de 1 a 0) con una probabilidad muy baja, introduciendo así variabilidad genética en la población.
El resultado de la aplicación de estos operadores es una nueva población, la cual se vuelve a decodificar y evaluar, repitiendo el mismo proceso que con la población inicial. Esta nueva generación reemplaza completamente a la anterior, actualizando tanto los valores de la función objetivo como los cromosomas. En cada iteración se registra la mejor solución encontrada y se continúa con el ciclo evolutivo.
Finalmente, el proceso se repite hasta cumplir el criterio de parada, que en este caso es un número máximo de generaciones previamente definido. Al concluir, el algoritmo habrá explorado el espacio de soluciones y, gracias al proceso evolutivo, habrá encontrado una solución cercana al óptimo del problema.
Creación de la Población Inicial
- Se inicia con la generación de una población aleatoria binaria, donde los individuos se crean asignando valores aleatorios entre 0 y 1. Un valor menor a 0.5 se convierte en 0, mientras que un valor mayor se convierte en 1.
- Cada individuo se define en el dominio del problema mediante la conversión de binario a decimal y el mapeo en el rango de las variables de decisión.
Evaluación y Selección
- Una vez definidas las variables de decisión, se evalúa la función a optimizar para obtener un valor objetivo, que se convierte en un valor de aptitud. Este valor indica la calidad de la solución, siendo más alto en individuos mejores.
- La aptitud se utiliza para aplicar la selección, donde un valor mayor implica una mayor probabilidad de ser seleccionado, similar a una ranura de ruleta más grande.
Cruzamiento y Mutación
- Después de seleccionar a los mejores individuos, se procede al cruzamiento utilizando un operador de cruzamiento en un punto, que es una característica del algoritmo genético básico.
- Finalmente, se realiza una mutación aleatoria en la población resultante, lo que introduce variabilidad y ayuda a explorar nuevas soluciones.
Aplicaciones de los Algoritmos Genéticos
- Los algoritmos genéticos no se limitan a problemas de optimización paramétrica; son robustos y pueden aplicarse a una amplia variedad de problemas en diferentes dominios, lo que se explorará en módulos posteriores del curso.
Este enfoque sistemático permite a los algoritmos genéticos abordar problemas complejos, imitando procesos de evolución natural y optimizando soluciones de manera efectiva.
relatedInteligencia Artificial