What are some problems that genetic programming has solved successfully? [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 10 months ago.

I am currently experimenting with GP and I wanted some test problems that have already been solved with GP. This way, I would know that genetic programming would be able to provide a solution that works. Also, shorter and simpler test cases would be better since I'm planning on running the algorithm many times. Thank you.

Answer 1

Here's a list of the more common benchmark problems GP is tested on. These are very widely used and descriptions of each should be easy to find with Google. For a very thorough description of each, including suitable fitness functions and results you can compare against see Koza's first Genetic Programming book if you can (the field has come on a bit since then, so they're not leading results, but you're unlikely to find more thorough descriptions).

Boolean Functions

• Even Parity
• Odd Parity
• Multiplexer (3-bit, 6-bit, 11-bit)
• Majority

Symbolic Regression

• Quartic Polynomial
• too many other functions to mention

Path Finding

• Artificial ant (Santa Fe Trail)
• Lawnmower
• Tartarus problem
• Circuit design
• Travelling Salesman

Control

• Cart centering
• Pole balancing

Iterative/Recursion

• Sorting
• List reversion
• Fibonacci sequence
• Factorial

There's also a whole range of other problems that GP has been successfully tested on, here's a few more, although these are perhaps beyond what you're looking for at the moment:

• Game playing, including Ms. Pacman, Othello, Mario
• Classification problems (protein classification etc)
• Scheduling
• Financial trading
• Biped locomotion
• Antenna design

If you're just looking for a few problems to get started with, to see the algorithm working and producing solutions, then I'd suggest starting with a simple symbolic regression (where you're trying to find a mathematical formula), then try one of the simpler boolean problems such as Even-3-Parity or 6-bit Multiplexer. The good thing about these problems is that you can easily ramp up the difficulty by changing the formula you're trying to find or increasing the number of bits.

Answer 2

Here's an interesting paper on applying genetic algorithms to the Traveling Salesman problem. I'm sure that if you check around JStor or similar journal collections, though, you can find a genetic programming algorithm for most NP-complete problems. Here's a paper about a SAT solver, for example.