Saltar al contenido ForoHackers

Evolutionary computation: start here

Computación evolutiva
#353 · Ophuscado · · 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

Inicia sesión o únete para responder.