Saltar al contenido ForoHackers

Evolutionary computation: start here

Computación evolutiva
#2859 · · Citar · Denunciar

Evolutionary computation solves problems by evolving a population of candidate solutions: keep the better ones, recombine and mutate them, repeat. It needs only a way to score a candidate, not a gradient, so it works on awkward search spaces such as schedules, designs, rule sets and programs. It is a flexible search method, rarely the fastest one when a problem has structure to exploit.

Key concepts

  • Representation: how a candidate is encoded, as a bit string, a vector of numbers, a permutation or a tree.
  • Fitness: the score that decides who reproduces; shaping it is most of the craft.
  • Variation operators: crossover mixes two parents, mutation makes small random changes.
  • Selection: tournament, rank or fitness-proportional rules set how strongly the best are favoured.
  • Diversity: a population that converges too early gets stuck at a local optimum; niching and restarts help.

Vocabulary

  • Genotype and phenotype: the encoded candidate, and the solution it decodes to.
  • Genetic algorithm: evolution of fixed-length encodings, often bit strings.
  • Genetic programming: evolution of programs or expressions represented as trees.
  • Local optimum: a solution better than all its neighbours but not the best overall.

What to study, in order

  1. Optimisation basics: objective functions, local and global optima, hill climbing.
  2. Write a genetic algorithm for a small problem, such as a travelling-salesman route, in plain code.
  3. Vary population size, mutation rate and selection pressure, and plot convergence over many runs.
  4. Implement a simple evolution strategy for continuous parameters.
  5. Compare your evolutionary search against random search and a problem-specific method, and decide when it earns its cost.

Related tags

#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