Skip to the content ForoHackers
Log inJoin

Computación evolutiva: por dónde empezar

Evolutionary computation
#354 · Ophuscado · · Report

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

  1. Lo básico de la optimización: funciones objetivo, óptimos locales y globales, ascenso de colinas.
  2. Escribe un algoritmo genético para un problema pequeño, como una ruta del viajante, en código simple.
  3. 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.
  4. Implementa una estrategia evolutiva sencilla para parámetros continuos.
  5. 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

Log in or join to reply.