11. Evolutional programming

Evolutional programming

Randomly create program pieces and combine them until they meets the needs

Evolutional algorithms

Artificially make programs and parameters evolve

Preserve good ones under "selection pressure"

Genetic algorithms, etc.

Genetic algorithm

Simulate evolution on computer

Encode data values as "genes"

Create better solutions through generations

Genetic algorithm

code:GAalgorithm

Randomly generate N data

while(1){

Calculate evaluation function for each data

Stochastically perform the following operations

Select two data and perform crossover

Select one data and perform mutation

Select one data and keep it

Use the new data for next generation

}

Genetic manipulations

Crossover

Mutation

One-point crossover

http://gyazo.com/fc41eca4275cac628ded90bc347ad1f5.png

Two-point crossover

http://gyazo.com/88c894a29d5c22e1b59b711ffe42ad5b.png

Random crossover

http://gyazo.com/77ea3c2cbc95253934ff55e49b5fab5a.png

Ex. 8-Queens

Layout 8 queens without 'conflict'

12 solutions

http://gyazo.com/72040da65f9db0160756e01ca233abee.png

8-Queen Program example

code:8queen.rb

class Queens

def initialize(nqueens = 8)

@col = []

@qpos = []

@up = []

@down = []

@nqueens = nqueens

(0...@nqueens).each { |i|

(-@nqueens...@nqueens).each { |i|

}

end

def out(block)

if block then

block.call(@qpos)

else

end

end

def expand(n,block)

(0...@nqueens).each { |c|

if n+1 >= @nqueens then

out(block)

else

expand(n+1,block)

end

end

}

end

def run(&block)

while true do

expand(0,block)

end

end

end

if __FILE__ == $0 then

Queens.new.run

end

Solving 8-Queens problem by GA

code:8queenga.txt

queens = Queens.new

while true do

queens.evaluate

queens.dump

queens.calc

break if queens.solution

end

Representation of queens on a gene

http://gyazo.com/6db282eb3171606d0351cdecc04928db.png

Mutation

http://gyazo.com/cae1c0d0a907f0f01fa6f813d8f054ce.png

Crossover

http://gyazo.com/887cf5d84c267a4d7168ca38a24809e4.png

8-Queens program in GA

code:8queenGA.rb

# -*- coding: utf-8 -*-

#

# Solving 8-Queen by GA

#

class Queens

POPULATION = 1000

attr_reader :solution

def randomgene

(0...8).collect {

rand(8)

}

end

def initialize

@genes = []

POPULATION.times {

@genes << randomgene

}

File.delete("average.log") if File.exist?("average.log")

File.delete("best.log") if File.exist?("best.log")

end

def evaluateone(gene)

collisions = 0

v = {}

(0...8).each { |i|

}

v = {}

(0...8).each { |i|

}

v = {}

(0...8).each { |i|

}

if collisions == 0 then

@solution = gene

end

# 1.0 / (1.0 + collisions)

collisions

end

def evaluate

@val = []

@totalval = 0.0

totalcollisions = 0.0

best = 100.0

(0...POPULATION).each { |i|

totalcollisions += collisions

best = collisions if collisions < best

}

File.open("average.log","a"){ |f|

f.puts totalcollisions.to_f / POPULATION

}

File.open("best.log","a"){ |f|

f.puts best.to_f

}

end

def selectone

r = rand(10000) / 10000.0

v = 0.0

(0...POPULATION).each { |i|

end

}

end

def dump

(0..10).each { |i|

}

end

def calc

newgenes = []

while newgenes.length < POPULATION do

if rand(10000) < 6000 then # mutation

a = selectone

b = selectone

p1 = rand(8)

p2 = rand(8)

if p2 < p1 then

tmp = p2

p2 = p1

p1 = tmp

end

(p1..p2).each { |i|

}

newgenes << a

newgenes << b

elsif rand(10000) < 600 then # mutation

a = selectone

newgenes << a

else

newgenes << selectone

end

end

@genes = newgenes

end

end

queens = Queens.new

while true do

queens.evaluate

queens.dump

queens.calc

break if queens.solution

end

(0...8).each { |i|

s = (0...8).collect { '.' }

puts s.join(' ')

}

Demo: 8-queen calculation

Success example

http://gyazo.com/31fc922b2e4c91dc553b85e1fa8605e2.png

Failure example

Can't get out from local minimum

http://gyazo.com/ccda781e488ab681acb08e3121666f68.png

Variations of GA

Mutation rate, crossover rate

Strategies for keeping descendants

Keep good descendants

Keep best descendant (Elitest strategy)

Also keep bad descendants

Selection strategies

Evaluation functions

Crossover strategies

Genetic programming

Make programs to evolve

Physical rules can be found

John R. Koza

「Genetic Programming」(GP)

http://gyazo.com/8b6838e3edaa7f03197ce6970ce3ffb2.png

Genetic programming

https://www.youtube.com/watch?v=xIoytwJWJP8

Representing a program as a tree

Crossover example

http://gyazo.com/1dda0879c9119387954fd6f443f8c824.png

Genetic image processing

Give only the results

Generate the combination of image filters

Combine many standard filters

Genetic image processing

http://gyazo.com/657094f428bca4644b01c8b6abe2d4ff.png

Example

http://gyazo.com/fb0055f4430460914c787f97dbe88579.png

Example

http://gyazo.com/b308e19010915fb5e39e3e94a7634cc1.png

Applications of genetic algorithm

Applicable to any optimization problem

Applicable to any problem if evaluation function exists

Limitation of genetic algorithm

Not applicable if evaluation function is not known

e.g. Generating a hit song

Hit rate is not calculatabl

Evaluation is not always easy

Evaluation is function is not always obvious

Song evaluation

Layout evaluation

Difficult to find evaluation function for good layout

Interactive genetic algorithm

Add human evaluation in the main loop

Add restrictions to solution

Calculate evaluation by human

Human intervention example

http://gyazo.com/ed2e829e648f00311f8538290d078aff.png

c.f. Selective breeding

Artificial selection and mating

Interactive GA for creating beautiful face

http://gyazo.com/c684db9fa5f0b9178fd367a4ed99b5ac.png

Graph layout by genetic programming (Masui)

Evaluation function is important for stochastic layout methods

Generate an evaluation function from user preferences

Stochastic methods

Gradually generate good solution based on evaluation function

Generate next solutions from current solutions

Getting good solutions without solving the problem

Algorithms

Genetic algorithm (GA)

Simulated Annealing (SA)

Simulated Annealing

https://gyazo.com/c94e159fbb06cb60a1e1199ca06f6eed

Add random noises to current solution

Gradually reduce the "temperature" of the noise

Examples of stochastic methods

VLSI layout by GA and SA

http://gyazo.com/d552207ae20dbed910c518d59e48e1ea.png

Using GA for graph layout

Use an evaluation function that calculates the goodness

http://gyazo.com/8a28ce95b25c9fe78d8f583114577fc6.png

Problems of stochastic methods

Slow

Not always best solution is generated

Evaluation function is sometimes unclear

Constraints and evaluationi function is different

Example: put a point in an appropriate position

Need an evaluation function which can calculate the quality

https://gyazo.com/2894ed46ce8ecac8be0ae56a83b50470

http://gyazo.com/d03154eeb529d6cbddf7862010e7fc8a.png

http://gyazo.com/bf06f4b7382f172adc55fea9f02350ef.png

Example-based approach

Create an evaluation function from examples

Users tell their preferences to the system

System generates an evaluation function which fits the users' preferences

Methods

Give good layout examples and bad examples

Create an evaluation function from examples

Use the evaluation function for other layout tasks

Layouts given to the system

http://gyazo.com/c203269a8abf8cd58ea730b9c119fe4f.png

Generated evaluation function

code:result.lisp

(ADD (SUB (ADD (MUL (MUL (MUL (ADD (ADD (ADD SUM(diry) SUM(minangle)) (ADD 44.00 69.00)) (MUL 43.00 MIN(diry))) 5.00) (ADD (ABS MAX(minangle) MIN(dist)) (ADD (ABS 74.00 MIN(dirx)) (ABS 15.00 SUM(locx))))) SUM(minangle)) (MUL 12.00 (CMP (DIV 57.00 MIN(locx)) (CMP 94.00 MIN(intersec))))) (DIV (ABS (MUL (SUB SUM(locy) 27.00) (CMP 28.00 65.00)) 62.00) SUM(dirx))) (CMP (ABS (DIV 67.00 SUM(locy)) (CMP (ABS (ABS 73.00 (CMP 67.00 SUM(dist))) MIN(intersec)) (ABS MIN(dist) MIN(diry)))) MIN(diry)))</code>

Results

http://gyazo.com/bb72e5ebf630d30e1ddc8fff69b13a74.png

Art piece generated from GA

Repetitive human selection of good results

Biomorph (Richard Dawkins)

Galapagos (Karl Sims)

sbart (Unemi)

Biomorph

by Richard Dawkins

Famous for his book "Blind watchmaker", "Selfish genes"

Artificial evolution by users

Breed good descendants

Select a good child from ramdomly-generated children

Repeat selecting the best one from ramdomly generated descendants

Richard Dawkins

http://gyazo.com/34b3ba70545c4f303aaaed62d194a3ac.png

Evolution of Biomorph

https://gyazo.com/189863961ab4de620dab6d570ac8dfd9

http://gyazo.com/f16acd4cabf8e9bcd10b11fcfa92b1be.png

Result

http://images.digopaul.com/wp-content/uploads/related_images/2015/09/10/biomorph_3.jpg

Galapagos (Sims)

Presented at NTT ICC

Select one from 9 examples

http://gyazo.com/922ac4cc0136595f718209c81e6d4874.png

Results of the evolution

http://gyazo.com/3ffc4dfce6ee255512e690f4939d3306.png

http://gyazo.com/356252a15a0243c5915b83662c2047a0.png

http://gyazo.com/06cb5d773b1add3e24775950e0fa5ab3.png

Conclusions

Various evolutional algorithms exist

Useful for evolutional computing

Require trial and error

Interactive evolutional algorithm

Generating art by evolutional methods