La computación evolutiva resuelve problemas haciendo evolucionar una población de soluciones candidatas: se conservan las mejores, se recombinan y se mutan, y se repite. Solo necesita una forma de puntuar un candidato, no un gradiente, así que sirve en espacios de búsqueda incómodos como horarios, diseños, conjuntos de reglas y programas. Es un método de búsqueda flexible, pocas veces el más rápido cuando el problema tiene estructura que aprovechar.
Conceptos clave
- Representación: cómo se codifica un candidato, como una cadena de bits, un vector de números, una permutación o un árbol.
- Aptitud: la puntuación que decide quién se reproduce; darle forma es la mayor parte del oficio.
- Operadores de variación: el cruce mezcla a dos padres, la mutación hace pequeños cambios al azar.
- Selección: las reglas de torneo, por rango o proporcionales a la aptitud fijan cuánto se favorece a los mejores.
- Diversidad: una población que converge demasiado pronto se atasca en un óptimo local; los nichos y los reinicios ayudan.
Vocabulario
- Genotipo y fenotipo: el candidato codificado, y la solución a la que se decodifica.
- Algoritmo genético: evolución de codificaciones de longitud fija, a menudo cadenas de bits.
- Programación genética: evolución de programas o expresiones representados como árboles.
- Óptimo local: una solución mejor que todas sus vecinas pero no la mejor de todas.
Qué estudiar, en orden
- Lo básico de la optimización: funciones objetivo, óptimos locales y globales, ascenso de colinas.
- Escribe un algoritmo genético para un problema pequeño, como una ruta del viajante, en código simple.
- Varía el tamaño de la población, la tasa de mutación y la presión de selección, y dibuja la convergencia en muchas ejecuciones.
- Implementa una estrategia evolutiva sencilla para parámetros continuos.
- Compara tu búsqueda evolutiva con la búsqueda aleatoria y con un método específico del problema, y decide cuándo compensa su coste.
Etiquetas relacionadas
#optimization #machine-learning #algorithms #complexity #simulation