![]()
I Parte 1: Introducción a los algoritmos genéticos
1 Introducción
1.1 Introducción a los algoritmos genéticos
1.2 Primeros pasos mediante un problema sencillo
1.3 Definición del problema y generación de la población inicial
1.4 Función objetivo y operadores genéticos
1.5 Operadores genéticos
1.6 Últimos pasos: Algoritmo genético como caja negra
1.7 ¿Cómo conseguir resultados consistentes?
1.8 Convergencia del algoritmo
1.9 Exploración versus explotación en algoritmos genéticos
1.10 Código completo y lecciones aprendidas
1.11 Para seguir aprendiendo
2 El problema del viajero
2.1 Introducción al problema del viajero
2.2 Definición del problema y generación de la población inicial
2.3 Función objetivo y operadores genéticos
2.4 Selección del algoritmo genético
2.5 Últimos pasos
2.6 Comprobar la convergencia del algoritmo en problemas complejos
2.7 Ajuste de los hiperparámetros: Probabilidades de cruce y mutación
2.8 Acelerando la convergencia del algoritmo: El tamaño del torneo
2.9 Acelerando la convergencia del algoritmo: Aplicar elitismo
2.10 Complejidad del problema: P vs NP
2.11 Código completo y lecciones aprendidas
2.12 Para seguir aprendiendo
3 Algoritmos genéticos y benchmarking
3.1 Introducción a las funciones de benchmark
3.2 Aprendiendo a usar las funciones de benchmark: Formulación del problema
3.3 Definición del problema y generación de la población inicial
3.4 Función objetivo y operadores genéticos
3.5 Código completo
3.6 Evaluación de algunas funciones de benchmark
3.7 Ajuste de los hiperparámetros de los operadores genéticos
3.8 Lecciones aprendidas
3.9 Para seguir aprendiendo
4 Algoritmos genéticos con múltiples objetivos
4.1 Introducción a los problemas con múltiples objetivos
4.2 Introducción a la Pareto dominancia
4.3 Selección del algoritmo genético
4.4 El problema de la suma de subconjuntos con múltiples objetivos
4.5 Funciones de benchmark con múltiples objetivos
4.6 Lecciones aprendidas
4.7 Para seguir aprendiendo
![]()
1.1 Introducción a los algoritmos genéticos
Los algoritmos genéticos son técnicas de optimización metaheurísticas, también llamadas estocásticas o probabilísticas (Holland et al., 1992) (Goldberg, 2006). Aunque fueron propuestos en la década de los 60s por Jonh Holland (Holland, 1962) (Holland, 1965) (Holland et al., 1992), no ha sido posible su aplicación en problemas de ingeniería reales hasta hace un par de décadas, debido principalmente a que son computacionalmente intensivos y que, por lo tanto, necesitan una capacidad computacional elevada para llevar a cabo multitud de operaciones en poco tiempo. La idea principal de un algoritmo genético es realizar una búsqueda guiada a partir de un conjunto inicial de posibles soluciones, denominado población inicial, el cual va evolucionando a mejor en cada iteración del algoritmo (Lones, 2011). Dichas iteraciones se conocen como generaciones y, normalmente, la última generación incluye la mejor o las mejores soluciones a nuestro problema de optimización. Cada posible solución a nuestro problema se conoce como individuo, y cada individuo codifica las variables independientes del problema de optimización. Estas variables representan los genes de la cadena cromosómica que representa a un individuo. Los algoritmos genéticos están basados en la Teoría Evolucionista de Charles Darwin (Darwin, 1859). Dicha teoría, explicado de forma muy simple, indica que los individuos que mejor se adaptan al medio son aquellos que tienen más probabilidades de dejar descendencia, y cuyos genes pasarán a las siguientes generaciones. La teoría de Darwin también describe que aquellas modificaciones genéticas que hacen que los individuos se adapten mejor al medio, tienen mayor probabilidad de perdurar en el tiempo. Estas ideas son las que utilizan los algoritmos genéticos para realizar una búsqueda estocástica guiada de forma eficiente. En los problemas de optimización numéricos, los individuos son potenciales soluciones al problema y la adaptación al medio se mide mediante la función que queremos optimizar, también llamada función objetivo, fitness function o función de evaluación1. Un individuo se adaptará bien al medio si produce un desempeño o fitness2 alto, en caso de que se quiera maximizar la función objetivo, o si produce un desempeño bajo en caso de que estemos ante un problema de minimización. Ambos problemas son siempre duales3, por lo que pasar de un problema de maximización a un problema de minimización es tan sencillo como multiplicar por –1 el resultado de la función objetivo.
En cada iteración del algoritmo, nuevos individuos (descendientes o, en inglés, offsprings) son creados mediante operaciones genéticas, dando lugar a nuevas poblaciones. Dichas operaciones genéticas, que se pueden resumir en tres bloques -selección, cruce y mutación- son el motor de búsqueda de un algoritmo genético. Cada vez que se crea un nuevo conjunto de individuos, se crea una nueva generación, y dicho proceso termina con la generación final, la cual debe incluir los mejores individuos encontrados a lo largo de las generaciones. Así, la Figura 1.1 representa el funcionamiento general de un algoritmo genético. Como se puede observar, se parte de una población inicial aleatoria y, a través de las operaciones genéticas, se van obteniendo...
