4 ms·

Unfortunately, it's not even that! Simulated annealing needs a cooling heuristic, which makes the algorithm smarter as it gets closer to the optimum. What this

Unfortunately, it's not even that! Simulated annealing needs a cooling heuristic, which makes the algorithm smarter as it gets closer to the optimum. What this is is some combination of hill climbing and random state space search. Not sure if it has a name. Want evidence? Look at the iteration counts. With SA, you'd see the differences between the successive pictures be roughly constant or even decrease (I can't prove it, but I've implemented it, and you usually end up choosing a cooling heuristic that roughly matches the human intuition for "closeness"). As it is, the algorithm that's implemented finds it exponentially harder to get close to optimum. You start off with a gap of 100 iterations between optima, and you end up at 300,000. Which is exactly why I think this is even more amazing -- it's just about the dumbest algorithm you can think of, and it still manages to vectorize an arbitrary raster image. If an actual GA or SA version were built, it could have some real potential. (See my comment below.)

deleted 18y ago
[deleted]
globalrev 18y ago
I just did this because I got inspired. What does it count as, genetic programming? It uses naive mutation and crossover(don't know if they qualfiy as real crossover and mutation) and a simple fitness function. It is fairly pointless since all it does is find a list with ones but it does so in just around 400 generations while random guessing takes forever. from __future__ import division import matplotlib.mlab as M import matplotlib.pyplot as plt import random as R def crossover(a, b): new = [] for x,y in zip(a,b): if R.random() > 0.5: new.append(x) else: new.append(y) return new def mutate(xs): xs[int(R.uniform(0, len(xs)))] = int(R.uniform(1, 10)) return xs def fitness(xs, goal): summa = 0 for x,y in zip(xs, goal): summa += abs(x-y) return summa, xs, True if summa == 0 else False def nFittest(xs, goal, n=2): fittest = sorted(fitness(x, goal) for x in xs)[:n] if fittest[0][2] : return fittest[0] elif fittest[1][2]: return fittest[1] else: return fittest def init(fields, n): return [[int(R.uniform(1,10)) for x in xrange(fields)] for y in xrange(n)] def newGen(a,b,n): next = [crossover(a,b) for x in xrange(n)] mutated = [] for x in next: if R.random() > 0.9: mutated.append(mutate(x)) else: mutated.append(x) return mutated def run(printing=True): n = 0 first = init(15, 10) while n < 1000000: n += 1 next = nFittest(first, [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], 2) if type(next) == tuple: break first = newGen(next[0][1],next[1][1], 10) if printing: print "Nbr of generations: ", n print next return n, next def plot(): trials = [run(False)[0] for x in range(100)] print "Done trials" averages = [sum(trials[:x]) / len(trials[:x])\ for x in xrange(1,len(trials)+1)] print "Done averages" plt.plot([x for x in xrange(len(averages))], averages, 'ro') plt.axis([1, 100, 0, 1000]) plt.show() def test(): goal = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] c=0 while 1: c += 1 x = [int(R.uniform(1,10)) for y in range(15)] if sum(x) == 15: break if c % 10000 == 0: print c print x
- randomwalker 18y ago
  Dude, pastebin? :-) Yeah, I guess this is GA alright. Your crossover is not right -- it should "cross over" at one point, not flip flop at each location :-) [Edit] And there's a lot of in-breeding going on! You want to keep 10-20 sequences from each generation, not just 2.
  - yters 18y ago
    Crossing over at one point is not as effective as an even crossover, since it is actually equivalent to an even crossover with one static and one dynamic point. Thus, building blocks in the middle are more likely to be disrupted than building blocks on the ends. That being said, his approach is also a viable GA operator. It is called a uniform crossover. But really, to qualify as a GA, his solution only needs some kind of variation, mutation, and selection.
- yters 18y ago
  Good GA, but for genetic programming, you need to come up with a program representation and then evolve something in that space that spits out a solution. V. simple in lisp, given the code/data are the same thing. You could try the same thing with python's string eval, but it'll be trickier to define the lexemes and what qualifies as a feasible program. Here's Koza's material from his Stanford class: http://www.genetic-programming.com/coursemainpage.html http://www.genetic-programming.com/coursemainpage.html
bd 18y ago
Ah yes, you are right. I also didn't realize it's not even genetic programming as DNA seems to be just polygon data, not polygon-drawing programs. BTW your comment was eponysterical :) http://mssv.net/wiki.cgi?Eponysterical http://mssv.net/wiki.cgi?Eponysterical
- randomwalker 18y ago
  Ha ha. Although part of the reason I picked that username is that a lot of my work involves statistics/probability, so it's not entirely a coincidence that I should be posting about this.
deleted 18y ago
[deleted]
yters 18y ago
Since it has a neighborhood function, i.e. doesn't select from the global population, I'd say it's a form of tabu search.

deleted 18y ago

[deleted]

globalrev 18y ago

I just did this because I got inspired. What does it count as, genetic programming? It uses naive mutation and crossover(don't know if they qualfiy as real crossover and mutation) and a simple fitness function. It is fairly pointless since all it does is find a list with ones but it does so in just around 400 generations while random guessing takes forever. from __future__ import division import matplotlib.mlab as M import matplotlib.pyplot as plt import random as R def crossover(a, b): new = [] for x,y in zip(a,b): if R.random() > 0.5: new.append(x) else: new.append(y) return new def mutate(xs): xs[int(R.uniform(0, len(xs)))] = int(R.uniform(1, 10)) return xs def fitness(xs, goal): summa = 0 for x,y in zip(xs, goal): summa += abs(x-y) return summa, xs, True if summa == 0 else False def nFittest(xs, goal, n=2): fittest = sorted(fitness(x, goal) for x in xs)[:n] if fittest[0][2] : return fittest[0] elif fittest[1][2]: return fittest[1] else: return fittest def init(fields, n): return [[int(R.uniform(1,10)) for x in xrange(fields)] for y in xrange(n)] def newGen(a,b,n): next = [crossover(a,b) for x in xrange(n)] mutated = [] for x in next: if R.random() > 0.9: mutated.append(mutate(x)) else: mutated.append(x) return mutated def run(printing=True): n = 0 first = init(15, 10) while n < 1000000: n += 1 next = nFittest(first, [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1], 2) if type(next) == tuple: break first = newGen(next[0][1],next[1][1], 10) if printing: print "Nbr of generations: ", n print next return n, next def plot(): trials = [run(False)[0] for x in range(100)] print "Done trials" averages = [sum(trials[:x]) / len(trials[:x])\ for x in xrange(1,len(trials)+1)] print "Done averages" plt.plot([x for x in xrange(len(averages))], averages, 'ro') plt.axis([1, 100, 0, 1000]) plt.show() def test(): goal = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1] c=0 while 1: c += 1 x = [int(R.uniform(1,10)) for y in range(15)] if sum(x) == 15: break if c % 10000 == 0: print c print x

randomwalker 18y ago
Dude, pastebin? :-) Yeah, I guess this is GA alright. Your crossover is not right -- it should "cross over" at one point, not flip flop at each location :-) [Edit] And there's a lot of in-breeding going on! You want to keep 10-20 sequences from each generation, not just 2.
- yters 18y ago
  Crossing over at one point is not as effective as an even crossover, since it is actually equivalent to an even crossover with one static and one dynamic point. Thus, building blocks in the middle are more likely to be disrupted than building blocks on the ends. That being said, his approach is also a viable GA operator. It is called a uniform crossover. But really, to qualify as a GA, his solution only needs some kind of variation, mutation, and selection.
yters 18y ago
Good GA, but for genetic programming, you need to come up with a program representation and then evolve something in that space that spits out a solution. V. simple in lisp, given the code/data are the same thing. You could try the same thing with python's string eval, but it'll be trickier to define the lexemes and what qualifies as a feasible program. Here's Koza's material from his Stanford class: http://www.genetic-programming.com/coursemainpage.html http://www.genetic-programming.com/coursemainpage.html

bd 18y ago

Ah yes, you are right. I also didn't realize it's not even genetic programming as DNA seems to be just polygon data, not polygon-drawing programs. BTW your comment was eponysterical :) http://mssv.net/wiki.cgi?Eponysterical http://mssv.net/wiki.cgi?Eponysterical

randomwalker 18y ago
Ha ha. Although part of the reason I picked that username is that a lot of my work involves statistics/probability, so it's not entirely a coincidence that I should be posting about this.

deleted 18y ago

[deleted]

yters 18y ago

Since it has a neighborhood function, i.e. doesn't select from the global population, I'd say it's a form of tabu search.