Skip to the content ForoHackers
Log inJoin

Evolutionary computation: start here

Evolutionary computation
#2859 · · Quote · Report

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

You are not logged in, so this goes up anonymously: no account, no name and no address is stored with it, and it may carry no link and no image. Log in or join to post under your name. Our web server's logs keep the address and time of every request for up to 14 days; to keep yours out of them, use Tor. To reach the staff in confidence, use the drop. Sign as a returning source (a key kept only in this browser)

Sending takes a few seconds here: your browser first works out a proof of work against spam.

Reply