Saltar al contenido ForoHackers

Computación evolutiva: por dónde empezar

Computación evolutiva
#2860 · · Citar · Denunciar

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

No has iniciado sesión, así que esto se publica como anónimo: no se guarda con ello ninguna cuenta, nombre ni dirección, y no puede llevar enlaces ni imágenes. Inicia sesión o únete para publicar con tu nombre. Los registros de nuestro servidor web guardan la dirección y la hora de cada petición hasta 14 días; para que la tuya no quede en ellos, usa Tor. Para escribir al equipo de forma confidencial, usa el buzón. Firmar como fuente habitual (una clave guardada solo en este navegador)

Enviar tarda unos segundos aquí: tu navegador resuelve antes una prueba de trabajo contra el spam.

Responder