4 ms·

Of course, being a new old thing, it's not complete without referencing it by it's actual name ... Genetic Programming. http://www.genetic-programming.com/john

by opless 8y ago

Of course, being a new old thing, it's not complete without referencing it by it's actual name ... Genetic Programming. http://www.genetic-programming.com/johnkoza.html http://www.genetic-programming.com/johnkoza.html

seanmcdirmid 8y ago
Well, genetic programming is a subset of program synthesis, not a same set. I’m not sure how the use of an SMT solver could be considered a genetic programming method.
- opless 8y ago
  Ah, I read the first link in the comments first, which really does imply they're using GP methods. https://homes.cs.washington.edu/~bornholt/post/synthesis-explained.html https://homes.cs.washington.edu/~bornholt/post/synthesis-exp... However they're using a SMT solver as part of the fitness function of the program. You know - it needs the correct output, but you need to prevent overfitting, and if you have a formal proof of the program generated you can expend greater effort into reducing its complexity and optimising. Again, it's an old new thing and possibly going to start getting hyped like neural networks have been of late.
  - seanmcdirmid 8y ago
    I’m sure the term program synthesis precedes the term genetic programming. Neither of these are new things. This (https://www.sri.com/sites/default/files/uploads/publications/pdf/1426.pdf https://www.sri.com/sites/default/files/uploads/publications...) is from 1971, for example. The earliest reference I can find to genetic programming is in the early 90s. There are plenty of program synthesis techniques (maybe not this one) that do not use fitness functions and get the program straight from a solver. If they have anything written up, I’m sure the related work section would make the context more clear. As for the accusation of band wagoning, it seems to come straight from the community that has been doing synthesis for years, not the ones that do GP.
  - ychen306 8y ago
    Ah, I read the first link in the comments first, which really does imply they're using GP methods. No, it doesn't.
    - opless 8y ago
      And the evidence to back up your assertion, is where? Here's mine... (excuse my lack of formatting.) The synthesis step of stochastic superoptimisation finds the next candidate program P’ by drawing an MCMC sample based on the previous candidate program P. It proposes P’ by randomly applying one of a few mutations to P: * changing the opcode of a randomly selected instruction * changing a random operand of a randomly selected instruction * inserting a new random instruction * swapping two randomly selected instructions * deleting an existing randomly selected instruction The MCMC sampler uses the cost function, which measures how “close” to the target program P’ is and how fast P’ is, to decide whether to accept the candidate P’. A candidate is more likely to be accepted if it is close to the target or very fast. But even programs that are slow or distant from the target have some probability of being accepted, ensuring we explore novel programs
      - TheOtherHobbes 8y ago
        That looks very GP-ish, but - as with all GP - the usefulness of the outputs depends on the sophistication of the cost function. What does "close" mean here? I don't see that explained. If you're trying to match outputs, then this is just old-fashioned GP with a minor twist - i.e. including speed in the fitness function, which has the potential to find some novel local maxima, which produce outputs that are close to the target AND very fast. If you're trying to match instruction sequences - then I don't see the point at all. GP often fails because it runs out of steam before producing a definitively correct solution. It's easy to design cost/fitness functions that get close but not close enough, and slightly harder to design functions that solve a non-trivial problem some of the time. It's incredibly hard to design functions that find an answer reliably without getting lost in the problem space.
        opless 8y ago

by opless 8y ago

seanmcdirmid 8y ago

Well, genetic programming is a subset of program synthesis, not a same set. I’m not sure how the use of an SMT solver could be considered a genetic programming method.

opless 8y ago
Ah, I read the first link in the comments first, which really does imply they're using GP methods. https://homes.cs.washington.edu/~bornholt/post/synthesis-explained.html https://homes.cs.washington.edu/~bornholt/post/synthesis-exp... However they're using a SMT solver as part of the fitness function of the program. You know - it needs the correct output, but you need to prevent overfitting, and if you have a formal proof of the program generated you can expend greater effort into reducing its complexity and optimising. Again, it's an old new thing and possibly going to start getting hyped like neural networks have been of late.
- seanmcdirmid 8y ago
  I’m sure the term program synthesis precedes the term genetic programming. Neither of these are new things. This (https://www.sri.com/sites/default/files/uploads/publications/pdf/1426.pdf https://www.sri.com/sites/default/files/uploads/publications...) is from 1971, for example. The earliest reference I can find to genetic programming is in the early 90s. There are plenty of program synthesis techniques (maybe not this one) that do not use fitness functions and get the program straight from a solver. If they have anything written up, I’m sure the related work section would make the context more clear. As for the accusation of band wagoning, it seems to come straight from the community that has been doing synthesis for years, not the ones that do GP.
- ychen306 8y ago
  Ah, I read the first link in the comments first, which really does imply they're using GP methods. No, it doesn't.
  - opless 8y ago
    And the evidence to back up your assertion, is where? Here's mine... (excuse my lack of formatting.) The synthesis step of stochastic superoptimisation finds the next candidate program P’ by drawing an MCMC sample based on the previous candidate program P. It proposes P’ by randomly applying one of a few mutations to P: * changing the opcode of a randomly selected instruction * changing a random operand of a randomly selected instruction * inserting a new random instruction * swapping two randomly selected instructions * deleting an existing randomly selected instruction The MCMC sampler uses the cost function, which measures how “close” to the target program P’ is and how fast P’ is, to decide whether to accept the candidate P’. A candidate is more likely to be accepted if it is close to the target or very fast. But even programs that are slow or distant from the target have some probability of being accepted, ensuring we explore novel programs
    - TheOtherHobbes 8y ago
      That looks very GP-ish, but - as with all GP - the usefulness of the outputs depends on the sophistication of the cost function. What does "close" mean here? I don't see that explained. If you're trying to match outputs, then this is just old-fashioned GP with a minor twist - i.e. including speed in the fitness function, which has the potential to find some novel local maxima, which produce outputs that are close to the target AND very fast. If you're trying to match instruction sequences - then I don't see the point at all. GP often fails because it runs out of steam before producing a definitively correct solution. It's easy to design cost/fitness functions that get close but not close enough, and slightly harder to design functions that solve a non-trivial problem some of the time. It's incredibly hard to design functions that find an answer reliably without getting lost in the problem space.
      - opless 8y ago