Introduction to Genetic Algorithms

Bethesda AI Meetup, Sep 2019

Craig Mandsager | @genolve | genolve.com | github

Sections

  • The Inspiration from Nature
  • Genetic Algorithms
  • Grammatical Evolution on Genolve.com
  • Why Genolve is Moving to Deep Neural Nets

The Inspiration from Nature

  • Evolution is nature's search algorithm
  • Nature is searching for the fittest individual for a given environment

"Owing to this struggle for life, any variation, however slight and from whatever cause proceeding, if it be in any degree profitable to an individual of any species, in its infinitely complex relations to other organic beings and to external nature, will tend to the preservation of that individual, and will generally be inherited by its offspring "
- Charles Darwin
It was Herbert Spencer who coined the term "survival of the fittest"

Crossing Over


In meiosis I chromosomes duplicate exchanging genetic information
[photo Simplified Biology]

New Gamete Cells


Mutations can occur during meiosis or during gene expression
[photo By Rdbickel]





CENTRAL DOGMA

  • DNA ⇒
  • RNA ⇒
  • Proteins ⇒
  • Phenoype

[photo Bozeman Science]

Genetic Algorithms

Genetic Algorithms solve optimization and search problems by representing a solution space as a chromosome and using simulated evolution to find the 'fittest' individual a.k.a. the solution to the problem.

The Algorithm

Randomly initialize population
 { Evaluate fitness
   Select parents
   Crossover & mutate
 } Repeat ↺


Input: PopSize, Pcross, Pmutate, SelectAlg
Output:  BestScore
Population = InitializePopulation(PopSize)
EvaluatePopulation(Population)
BestScore = Generations = 0
While (!StopCondition(BestScore,Generations,...))
    Parents  = SelectParents(Population, SelectAlg)
    Children = none
    For (parent1,parent2 in   Parents)
        child1,child2 =   Crossover(parent1, parent2, Pcross)
        Children += Mutate(child1, Pmutate)
        Children += Mutate(child2, Pmutate)
    End
    EvaluatePopulation(Children)
    BestScore = GetBestSolution(Children)
    Population = Replace(Population, Children)
    Generations += 1
End
Return (BestScore)
[from Clever Algorithms]

Roulette Wheel Selection

[image Tutorials Point]

Tournament Selection

Chromosome Representation

  • Bit-string representations of integers (Gray coding)
  • Each parameter represented as an integer or float
  • Bit-string for T/F
  • Permutation
  • Integers as indexes to other data structures
The chromosome must cover the solution space

Crossover

Single-point crossover or multi-point by Pcross
Mutation randomly changes genes by Pmutate
[image By R0oland]

Demo: Knapsack Problem

Fill a Halloweeen shopping bag w/ scary items
[image Wikimedia]

Halloween Decorations $20 Budget

Item Scariness Cost Scare/$
Ghost 11.00 $5.00 2.2
Bat 13.00 $7.00 1.9
Skull 10.00 $5.00 2.0
Jackolantern 20.00 $10.00 2.0
Witch mask 5.00 $3.00 1.7
Goblin mask 10.00 $3.00 3.3
Trump mask 15.00 $3.00 5.0

Chromosome Representation?

  • Hint: What is the solution space?
  • Bit-string is sufficient
  • Bit 0 - buy the Ghost
  • Bit 1 - buy the Bat
  • 1011001
  • Will crossover work?

next: fitness function?

Fitness Function


Gene.prototype.calcFitness = function() {
  var selectedItems = items.filter(getItem); 
  this.fitness = selectedItems.reduce(sumPoints, 0);
  this.totalCost = selectedItems.reduce(sumCost, 0);
  //set penalty if totalCost > costlimit 
  if (this.totalCost > costlimit) {
    this.fitness -= Math.pow(costlimit - this.totalCost,2);
    this.fitness = Math.min(this.fitness,population.bestFitnessSoFar-1);
    if(this.fitness<0)
      this.fitness=0;
  }
}

The best solution is 51 scare points

Further Reading

Goldberg's classic text is still a valuable resource for the Genetic Algorithm [Goldberg1989], and Holland's text is interesting for those looking to learn about the research into adaptive systems that became the Genetic Algorithm [Holland1975]. Additionally, the seminal work by Koza should be considered for those interested in Genetic Programming [Koza1992], and Schwefel's seminal work should be considered for those with an interest in Evolution Strategies [Schwefel1981]. For an in-depth review of the history of research into the use of simulated evolutionary processed for problem solving, see Fogel [Fogel1998] For a rounded and modern review of the field of Evolutionary Computation, Bäck, Fogel, and Michalewicz's two volumes of "Evolutionary Computation" are an excellent resource covering the major techniques, theory, and application specific concerns [Baeck2000] [Baeck2000a]. For some additional modern books on the unified field of Evolutionary Computation and Evolutionary Algorithms, see De Jong [Jong2006], a recent edition of Fogel [Fogel1995], and Eiben and Smith [Eiben2003].

[from Clever Algorithms]

Grammatical Evolution on Genolve.com

Generate + Evolve

Genolve

What Does Genolve Do?

Basic concepts
Make a blog graphic
(try clicking the 'geometric' button then click a design on the right)

English Grammar

Time flies like an arrow

NP : Determiner + Pre-modifiers + NOUN + Postmodifiers/Complement

[image Wikipedia]

Grammars are Everywhere

  • Extensible Markup Language (XML)
  • XSD (XML Schema Definition) is basically a grammar
  • BeerXML is a thing
  • HTML
  • SVG
  • Programming languages

Context Free Grammars

Backus Normal Form (BNF)


 <postal-address> ::= <name-part> <street-address> <zip-part>
      <name-part> ::= <personal-part> <last-name> <opt-suffix-part> <EOL> 
                    | <personal-part> <name-part>
  <personal-part> ::= <letter> "." | <first-name>
 <street-address> ::= <house-num> <street-name> <opt-apt-num> <EOL>
       <zip-part> ::= <town-name> "," <state-code> <ZIP-code> <EOL>
<opt-suffix-part> ::= "Sr." | "Jr." | <roman-numeral> | ""
    <opt-apt-num> ::= <apt-num> | ""
     <first-name> ::= <word>
           <word> ::= <letter><word> | <letter>
         <letter> ::= "a"|"b"|"c"|"d"|"e"|"f"|"g"|"h"|"i"|"j"|"k"|"l"|"m"|"n"|"o"|"p"|"q"|"r"|"s"|"t"|"u"|"v"|"w"|"x"|"y"|"z"
Start Symbol • Production Rule • Choice • Terminal
[from Wikipedia]

Programming Grammar

To solve the Sante Fe Ant Trail


<prog> ::= <code>
<code> ::= <line> | <code> <line>
<line> ::= <condition>'\n' | <op>'\n'
<condition> ::= 'if(food_ahead()==1) {' <opcode> '} else {' <opcode> '}'
<op> ::=  'left();' | 'right();' | 'move();'
<opcode> ::= <op> | <opcode> <op>
left(); move(); if(food_ahead()==1) { right(); } else { move(); move(); right(); move(); }
[from GEVA]

The Genolve Grammar

Weighted Extended Backus Normal Form (EBNF) of over 2000 lines models the full SVG specification.

  • ^nn - weight rule by nn percent
  • ?nn - optionally include 0 or 1 times
  • *nn - repeat 0 or more times
  • +nn - repeat 1 or more times

Timecount_list    : Timecount_val ( '; '  Timecount_val )*5;
Timecount_val     : float_datatype (Metric)?20;
Metric            : 's'^80 |'min'^10 | 'h'^5 | 'ms'^5;

Demo: Evolve Radial Gradients

Scalable Vector Graphics (SVG)

Radial Gradient


<radialGradient id='grad1' cx='60%' cy='80%' r='90%'    
        spreadMethod='pad' gradientUnits='objectBoundingBox'>
        <stop offset='0' stop-color='hsl(34, 58%, 57%)'   />
        <stop offset='0.7' stop-color='hsl(214, 58%, 70%)'    />
        </radialGradient>

Radial Gradient Grammar

Radial Gradient in Tracery notation


  gradient : "<radialGradient id='grad1' cx='#digit#0%' cy='#digit#0%' r='#digit#0%' spreadMethod='#spread#' gradientUnits='objectBoundingBox'>
<stop offset='0' stop-color='#svgColor#' />
<stop offset='0.#largeDigit#' stop-color='#svgColor#' />
</radialGradient>"
largeDigit : ["5","6","7","8","9"],
     digit : ["1","2","3","4","5","6","7","8","9","0"],
 r255Start : ["1","2","3","4","5","6","7","8","9","10","11","12","13","14","15","16","17","18","19","20","21","22","23","24","25"],
      r255 : "#r255Start##digit#",
    spread : ["repeat","pad","reflect"],
  svgColor : "hsl(#r255#, #largeDigit##digit#%, #largeDigit##digit#%)",
[If you make something in Tracery load it on Genolve!]

Create Phenotype from Chromosome

  • The gene controls how we traverse the grammar
  • gene: 92,45,2,45,86,23,45,56
  • "spread":["repeat","pad","reflect"]
  • 92 (mod) 3 ⇒ 2 ⇒ "reflect"
  • demo Pmutate:1,Pcross:0

Further Reading

Michael O'Neill, University College Dublin, and Conor Ryan, University of Limerick, have a wealth of books and papers.

Genolve.com Moving to Deep Neural Nets

Problem 1 - Evolution on Paths

  • Shapes:rect,circle,ellipse,path,polygon,polyline,line
  • Paths are a cornerstone of SVG
  • Random path modifications sometimes work
  • But more often don't work

Google's SketchRNN, an RNN trained on thousands of human sketches, can generate new sketches from a 'latent vector', the essence of a sketch.


[image Google]

Problem 2 - Poor Fitness Function

Avoid using humans as your fitness function!

  • slow
  • lose interest
  • lack an artistic eye

A GAN Discriminator as a Fitness Function


[image KDnuggets] //

Problem 3 - No Global Learning

Each shape, no matter now similar, must travel its own evolutionary path.

Neural Nets can Aid Global Learning

Learn a 'latent chromosome'

Chromosome style transfer

Other ideas?

Grammatical evolution gives you a parse tree for free

Possible parallels with NLP

Thank You!

Enquiries welcome

Use these backgrounds for your own slides!
Watch Twitter

Craig Mandsager | @genolve | genolve.com | github