Genetic Algorithms

Evolution

  • Another biological model "inspiring" computation

  • Idea: Nature fits populations to environments

    • "Natural Selection" causes fittest elements of population to be preserved

    • Genes act as a "memory" of good features

    • Combining the genes of two individuals gives a combination of their features — big search space

Genetic Algorithm

  • Specify "genes" representing features to be learned

  • Construct a random "population" of n "genomes"

  • Repeatedly

    • Remove genomes scoring lower on training set

    • Repopulate to size n by combining pairs from remainder of population

    • Optional: randomly "mutate" elements of population by changing genes

Removal Of Less-Fit Instances

  • Could just sort by score and remove lowest scorers

  • Problem: "genetic diversity" — all the high scorers tend to look alike

  • Better diversity through "tournament selection": take pairs of instances and remove the one with the lower score

Repopulation

  • Typically select pairs randomly

  • Methods for combining p1, p2:

    • "Crossover" selects some (random?) number of genes at start of p1, then fills in with genes from end of p2 — preserves positionally-related structures

    • "Shuffling" selects each gene randomly from p1 or p2 — mixes well

Loss Of Diversity

  • Big problem: After a while, population can start to look all alike; then combining doesn't do anything

  • Increase the population: Easy mode, but slows things down

  • Adjust amount of depopulation: Remove too many = loss of diversity. Remove too few = slow convergence

  • Adjust mutation rate: For largeish populations mutation is rarely necessary. Adjust rate for fastest convergence

  • Use similarity for depopulation: Cluster similar instances and remove the worst ones in each cluster

  • Choose a better genome: Feature engineering can reduce the search space size

Fancy GAs

  • "Predator / Prey" and other ecosystem approaches

  • "Biome" for covering different parts of the search space with different populations

Evaluation Of GA Approach

  • Advantages

    • Simple to do, understand
    • Requires little understanding of problem
  • Disadvantages

    • Evolution can be slow
    • Tuning still matters

Local Search As a Special Case

  • Note that if your population size n=1, this looks a lot like local search, for which

    • No memory / recombination, so much faster and cheaper but more sensitive to local conditions

    • Typically requires state-space engineering to work well

    • Doesn't accomodate continuous features well

    • Really scary faster

  • Interesting to compare the two approaches on real problems

Last modified: Friday, 15 November 2019, 11:39 PM