Genetic Programming Online Learning

Question

Has anybody seen a GP implemented with online learning rather than the standard offline learning? I've done some stuff with genetic programs and I simply can't figure out what would be a good way to make the learning process online.

Please let me know if you have any ideas, seen any implementations, or have any references that I can look at.

Answer 1

Per the Wikipedia link, online learning "learns one instance at a time." The online/offline labels usually refer to how training data is feed to a supervised regression or classification algorithm. Since genetic programming is a heuristic search that uses an evaluation function to evaluate the fitness of its solutions, and not a training set with labels, those terms don't really apply.

If what you're asking is if the output of the GP algorithm (i.e. the best phenotype), can be used while it's still "searching" for better solutions, I see no reason why not, assuming it makes sense for your domain/application. Once the fitness of your GA/GP's population reaches a certain threshold, you can apply that solution to your application, and continue to run the GP, switching to a new solution when a better one becomes available.

One approach along this line is an algorithm called rtNEAT, which attempts to use a genetic algorithm to generate and update a neural network in real time.

Answer 2

I found a few examples by doing a Google scholar search for online Genetic Programming.

An On-Line Method to Evolve Behavior and to Control a Miniature Robot in Real Time with Genetic Programming

It actually looks like they found a way to make GP modify the machine code of the robot's control system during actual activities - pretty cool!

Those same authors went on to produce more related work, such as this improvement:

Evolution of a world model for a miniature robot using genetic programming

Hopefully their work will be enough to get you started - I don't have enough experience with genetic programming to be able to give you any specific advice.

Answer 3

It actually looks like they found a way to make GP modify the machine code of the robot's control system during actual activities - pretty cool!

Yes, the department at Uni Dortmund was heavily into linear GP :-)

Direct execution of GP programs vs. interpreted code has some advantages, though in these days you'd probably rather want to go with dynamic languages such as Java, C# or Obj-C that allow you to write classes/methods at runtime while still you can still benefit from some runtime rather than run on the raw CPU.

The online-learning approach doesn't seem like anything absolutely novel or different from 'classic GP' to me. From my understanding it's just a case of extending the set of training/fitness/test cases during runtime?

Cheers, Jay