4 ms·

A few years ago I wrote a genetic algorithm to solve a travelling salesman problem - it was a ton of fun - I need to port it to JS one day. Ive also thought ab

A few years ago I wrote a genetic algorithm to solve a travelling salesman problem - it was a ton of fun - I need to port it to JS one day. Ive also thought about making an algorithm that would breed JS programs to solve basic tasks - sort an array of input or find the longest consecutive group of numbers. Maybe one day I'll find the time.

lucio 12y ago
http://agentscript.org/models/tspga.html http://agentscript.org/models/tspga.html http://agentscript.org http://agentscript.org
- netcraft 12y ago
  very cool! thanks for the link!
jacques_chester 12y ago
> Ive also thought about making an algorithm that would breed JS programs to solve basic tasks When you do, a useful tip: in the literature, Genetic Algorithms are distinct from Genetic Programming. GAs evolve collections of parameters into a function or group of functions. GPs evolve actual executable programs. Mostly as interpreter trees, though some experiments have been done with evolving strings of machine code for real and virtual machines. So in your case, the place to start is Genetic Programming. ps. it's freakishly slow and the GP literature is really fixated on favouring one evolution step almost to the exclusion of others (I can't remember if it's the crossover step or mutation step).
- makeset 12y ago
  In a lot of GA applications the effects of mutation are negligible. Given a large and diverse population, crossover provides enough variation already. Mutation will only be necessary to escape if the entire population has converged to a poor local optimum, but that doesn't tend to happen often in practice, and even if it does, there's no guarantee that mutation will help; hence the lack of focus on mutation operators in general.
  - jacques_chester 12y ago
    Oh, maybe I mixed up GA and GP myself? In terms of favouring crossover vs mutation.
- netcraft 12y ago
  good information - if you have any links to share id love to see them.
  - jacques_chester 12y ago
    I got a lot of value from A Field Guide to Genetic Programming[1] and Introduction to Evolutionary Computing[2] when I was studying this stuff. I've heard good things about Essentials of Metaheuristics[3] and Clever Algorithms[4] too, I would like to read them some day. [1] http://www.gp-field-guide.org.uk/ http://www.gp-field-guide.org.uk/ [2] http://www.cs.vu.nl/~gusz/ecbook/ecbook.html http://www.cs.vu.nl/~gusz/ecbook/ecbook.html [3] http://cs.gmu.edu/~sean/book/metaheuristics/ http://cs.gmu.edu/~sean/book/metaheuristics/ [4] http://www.cleveralgorithms.com/ http://www.cleveralgorithms.com/

lucio 12y ago

http://agentscript.org/models/tspga.html http://agentscript.org/models/tspga.html http://agentscript.org http://agentscript.org

netcraft 12y ago
very cool! thanks for the link!

jacques_chester 12y ago

> Ive also thought about making an algorithm that would breed JS programs to solve basic tasks When you do, a useful tip: in the literature, Genetic Algorithms are distinct from Genetic Programming. GAs evolve collections of parameters into a function or group of functions. GPs evolve actual executable programs. Mostly as interpreter trees, though some experiments have been done with evolving strings of machine code for real and virtual machines. So in your case, the place to start is Genetic Programming. ps. it's freakishly slow and the GP literature is really fixated on favouring one evolution step almost to the exclusion of others (I can't remember if it's the crossover step or mutation step).

makeset 12y ago
In a lot of GA applications the effects of mutation are negligible. Given a large and diverse population, crossover provides enough variation already. Mutation will only be necessary to escape if the entire population has converged to a poor local optimum, but that doesn't tend to happen often in practice, and even if it does, there's no guarantee that mutation will help; hence the lack of focus on mutation operators in general.
- jacques_chester 12y ago
  Oh, maybe I mixed up GA and GP myself? In terms of favouring crossover vs mutation.
netcraft 12y ago
good information - if you have any links to share id love to see them.
- jacques_chester 12y ago
  I got a lot of value from A Field Guide to Genetic Programming[1] and Introduction to Evolutionary Computing[2] when I was studying this stuff. I've heard good things about Essentials of Metaheuristics[3] and Clever Algorithms[4] too, I would like to read them some day. [1] http://www.gp-field-guide.org.uk/ http://www.gp-field-guide.org.uk/ [2] http://www.cs.vu.nl/~gusz/ecbook/ecbook.html http://www.cs.vu.nl/~gusz/ecbook/ecbook.html [3] http://cs.gmu.edu/~sean/book/metaheuristics/ http://cs.gmu.edu/~sean/book/metaheuristics/ [4] http://www.cleveralgorithms.com/ http://www.cleveralgorithms.com/