Los algoritmos genéticos son una herramienta basada en el proceso de selección natural para obtener soluciones a problemas de optimización y búsqueda.
La idea principal en estos algoritmos es imitar el proceso de selección natural, como la herencia, la mutación, el cruzamiento, la selección, etc. De esta manera, los individuos serán las posibles soluciones al problema que se trata. Además, estos algoritmos no requieren de gran cantidad de datos para su desarrollo.
Figura 1: A partir de una población inicial, imitamos el proceso de selección natural; herencia, mutación, cruzamiento, selección, etc. Los individuos resultantes serán las posibles soluciones.
¿Cómo procede este algoritmo?
Partimos de un conjunto inicial de soluciones, que serán la población inicial. Las que consideremos mejores soluciones, evaluadas según la llamada función fitness, serán seleccionadas para transmitir la información a la siguiente generación de formas distintas, de manera que esta nueva generación, heredará la información de la generación precedente. Las generaciones se suceden de forma que cada vez obtendrán mejores individuos, es decir, mejores soluciones al problema.
Una forma esquemática del algoritmo:
- Generación de la población inicial de soluciones.
- Evaluación de la población generada
- Selección de los mejores individuos
- Construcción de una nueva generación
- Repetición de los pasos 2, 3 y 4 hasta llegar a la condición de finalización
Las soluciones que encontraremos serán rápidas y eficientes. La población inicial del algoritmo no puede ser ni muy grande ni muy pequeña. Por norma general, lo inicializamos de forma aleatoria, así permitimos todo tipo de diversidad en nuestra población y garantizamos soluciones óptimas. En general, todas las generaciones tendrán el mismo número de individuos.
Función fitness: ¿qué es y qué mide?
La función fitness nos ayudará a evaluar a todos los individuos. Con ella, podremos asignar un valor a cada individuo de la generación de forma que, si una solución obtiene un valor más elevado que otra, representará que es una mejor solución, o una solución más cercana a la solución óptima que se busca. Así pues, podremos saber qué individuos son mejores dentro de una generación. Necesitamos una función fitness adecuada a cada problema.
¿Cómo generamos los sucesores de la siguiente generación?
Antes de generar los sucesores de la siguiente generación debemos seleccionar los individuos que utilizaremos como padres y, a veces, seleccionaremos qué hijos pasarán a la siguiente generación. A veces simplemente, haremos un clon de padre a hijo, para asegurar que preservamos la genética original.
Es importante que la selección favorezca a los mejores según su valoración respecto la función fitness, y que permita la diversidad. Usualmente también tiene una componente aleatoria.
Cada individuo tendrá una probabilidad de ser seleccionado, proporcional a su valoración, respecto de las valoraciones del total de la población. Los mejores individuos, tendrán una probabilidad más alta y, por lo tanto, serán seleccionados más frecuentemente.
Métodos que existen para transmitir la información a la siguiente generación:
- Mutación
- Cruce
- Clonación
- Etc.
¿Qué aplicaciones tienen los algoritmos genéticos?
Hay una gran cantidad de problemas que pueden ser resueltos mediante los algoritmos genéticos. Algunos de estos problemas son:
Caso 1: Optimización de rutas. Aplicado en la optimización de rutas, permite encontrar la ruta más corta o más rápida entre ciudades o zonas en muy poco tiempo. También resulta muy útil en Smart cities, para tratar de reducir las emisiones de CO2.
Caso 2: Optimización de tareas. Cuando se trata de realizar tareas en el tiempo más breve posible, optimizarlas es fundamental. Con los algoritmos genéticos, además el cálculo se hace rápido y eficaz.
Caso 3: Gestión automatizada de equipamiento industrial. Es posible hacer un cálculo en tiempo real para optimizar un proceso automatizado de equipamiento industrial.
Caso 4: Aprendizaje de comportamiento de robots. El aprendizaje de robots es posible respecto a una función de coste. Con estos algoritmos el aprendizaje se realiza de un modo más rápido y eficaz.
Caso 5: Sistemas del sector financiero. Una aplicación interesante en finanzas es que estos algoritmos permiten descubrir reglas de inversión que indican cuándo entrar y salir de un mercado para obtener los máximos beneficios. Por otro lado, en métodos de Splitwise, se puede optimizar el método de compartir gastos entre distintos usuarios.
Caso 6: Encontrar errores en programas. Permite detectar errores en los programas de los desarrolladores, lo que ayuda a ahorrar tiempo y dinero en su implementación.
En resumen, los algoritmos genéticos son una herramienta muy útil si queremos obtener resultados rápidos en problemas de optimización y búsqueda. Y aunque no siempre se garantiza encontrar la solución exacta al problema, la aproximación es suficientemente buena.
