Hey! I was just wondering who here has previously or is currently implementing a GP system. I was wondering because I currently am and am currious how other people did theirs and how general case they wrote it. I am trying to be very very general and allow all of the classes to be inherited by other new classes to implement *any* kind of GP you could dream up. Basically I have everything set up like this: CGroupNode Inherited by: CGroup, CHeadNode This class doesn't actually provide any functionallity. it just allows for someone to have a list of objects and not worry about if they are groups or programs (CHeadNode). CGroup This class provides the structure of the GP. It contains a list of programs and groups that are under it and that are in it. It also contains a pointer to a CMutator and a CVM, which are used by the group and its children. CNode This class is just a single node... it can be a function, an input, a constant, a loop, or a call to another program. the randomization of init pop is implemented in here CMutator This class is used by the CGroup objects to mutate their programs. It randomly selects programs for mutation, crossover or whatever other CGeneticOperator you come up with. CVM This is the class that contains the virtual machine, or the environment/problem that is to be solved or executed in. Create a new class with this as a base class to implement whatever functionallity you want. All functions must accept no arguments and can't return any arguments. All data is passed through the stack. At the beggening of your function, read however many values off of the stack as you need and then push the result if there is one back onto the stack at the end of the function CGeneticOperator This class is a base class for CGeneticMutate and CGeneticCross. derive classes from this one if you would like to create your own genetic operators or would like to alter the functionallity of the provided cross and mutate operations. well I think that is about it. You don't need to provide as much detail as I did, but just some general, how you system works, would be nice Thanks! EDIT: why did I have the code tag in there? screwed with the page width... my bad Dwiel [edited by - Tazzel3d on November 23, 2003 5:45:06 PM]

Hi;

I have never worked with GP before. But I think you should consider implementing this with templates, rather than class heirarchy.

Peace Out!

I would love to hear more about what you mean ''by templates''. I considered using templates for the groups, but then realized that if I used templates, I wouldn''t be able to put it into a so/dll. I was really hoping to put each of the classes into different libraries. That way, I could have a single program that given the libraries for each component of the system, would execute the GP. In this way, I only need to compile the parts I alter each time instead of recompiling the whole thing... well... I guess that I won''t have to recompile the whole thing even if I have it all in one because the headers won''t change... only the cpp... still... It seems that this way, everything is modularized better.

I would however like a little more detail on what you mean by useing templates. Thanks!

Dwiel

You are absolutely right about the DLL thing. Templates and DLL''s aren''t friends.

This is the AI and not programming forum so I won''t go into much detail about this. But looking at the STL, you''ll find that algorithms in general are implemented as templates.
Class heirarchies are useful when you know at design time what the output and input are, but the operations vary.
Templates, on the other hand, are useful when you know at design time the exact operations but not the form of input and output (Which is the reason why algorithms are implemented as templates)
This of course is an over-simplification.

Smart use of templates can assure you of type safety and eliminate a lot of infrastucture coding for you (like the stack for keeping track of input and output)

If you find your code starting to fill up with explicit type casts, then this is a good indication that you should consider templates.

I hope this was useful, and I''m sorry that again I deviated from your original subject, GP.

Peace Out!

Actually I am thankful that you have mentioned that maybe my stack hack was not such a good idea. This is exactly the kind of constructive critisism I was looking for . How would you suggest that I implement my virtual machine if I am to use templates? Are you saying that my functions that currently push and pop data off of the stack should accept arguments, but should be template member functions so that they can accept nearly any value? This sounds great, but I think that if I implement the functions this way, I am going to have truoble keeping track of the functons, and specifically, keeping a vector of pointers to them to pass out to the programs to use for calling... I would like to steer clear from a massive switch block Is there a way that I can have the best of both worlds? What they must do:

Accept any # of variables.
be stored in a large list of every function available
created in a new class that inherits this one
be fairly easy to use (rather not be passing around void **)
be reasonably quick (no huge switch statement)

If there is a way templates can fit all of these, that would be wonderful! I tried for some time to get them to, but couldn''t seem to get it to work. The perq where they must be able to accept any # of variables really jumbles things up...

Thanks!

Dwiel

Please keep in mind that everything I say in this post or future posts is based on no experience in GP. I have worked with simple genetic algorithms and I hope the specifics of GP won''t make my judgement too irrelevant.
This post might prove to be long so please bear with me.

First let me qualify my preference for templates in this specific case with a GA algorithm (This way we''ll know whether I''m addressing the real problem). The solutions provided are in this example are arrays of numbers (a travelling salesperson problem?)

class CSolution // comparable to your CGroup class
{};
class CMutator
{
virtual void mutate(CSolution* );// Has no idea what your solution looks like (a bit array, tree...etc)
};

class CNumArraySol: public CSolution
{};

class CNumArrayMutor: public CMutator
{
virtual void mutate(CSolution* unknownForm)
{
CNumArraySol* solution = (CNumArraySol*)unknownForm;
//Do something with the values here
};
};
In this example you needed information that was hidden by the inheritance. You had to make an explicit typecast and a mess.

alternatively:
template
class CMutator
{
virtual void mutate(solution* )=0;
};

class CNumArraySol: public CSolution
{};

class CNumArrayMutor: public CMutator
{
virtual void mutate(CNumArraySol* knownForm)
{
//No need for typecasts.
//your class already knows what to expect
};
};
In the above example The objects already know all they need to know about what''s being passed around. There''s nothing to prevent you from inheriting any of the above classes. This keeps things tidier and more modularized.

You will find such cases creeping up all over the place. It can get messy and dangerous. The bigger your heirarchy, the more so.
This is where huge switch statements will force themselves on you.

As for GP, by using the above technique, your programs can have more knowledge about the problem they''re trying to resolve(Parameters...etc) and the kind of result they''re supposed to produce. They know how to address them directly without resolving to some uncontrollable stack(which might contain strings, numerics, structs..etc)

On another note:
I am getting the impression that you''re trying to evolve a program in C++ or a similar (strongly typed) language. Did you consider evolving a LISP program? If you have never worked with LISP check it out, I think you''ll find it much easier to manipulate than C (for this specific purpose). If you''re familiar with it, then you probably know where I''m coming from. Of course I''m only suggesting LISP as the language of the EVOLVED program, not the language you want to write your engine in.

P.S.I don''t know how to use code tags. The code might look rather messy. How does one do that anyway?

Peace Out!

Before I say anything< i''d like to thank you for the descussion... not too many others seem intrested in this.

:: NOTE :: skip to towards the end.. I had an epiphany while writing and completely changed my view-point left the ''old'' stuff in for completeness...

I am still having a hard time understanding you are accomplishing the problem. I have a better idea... One thing I thinkink that is happening in your example code is that each of the possible solutions will have their own instance of a mutator... This is really very un-necessary as there will be on the order of millions of programs beign executed/mutated at once and normally just one mutator... possibly 1 or 2 more... why have 1,000,000 of them? If this is not what you meant, sorry...

Also, I am not sure if you understood my Group class... My group class is basically a list of other groups (children groups) and programs. When a group is instructed to mutate itself, it passes a pointer to its structure to the mutator object that has been assigned to it. Basically, a group can contain any kind of structure... There are a ton of different ways that GPs can breed programms and a billion ways it decides which programs are more likely to breed with which other programs (hopfully that made sence...)

I guess I am just kind of confused at the thinking behind having the mutator class inherit from the group class...

... WAIT ...

EPIFINAY

OK, I think that I understand what you are doing and why it is a pretty good idea. The way that programs in a structure are contained, list, tree, graph, etc, will also have a method for mutating the structure that probobly wont be to applicable to other groups/structure types. If the group and the Mutator are one, then I reduced a part of my class heirchy... simplified it. I was thinking now that it might be nice to be able to have a single group have mutlipule different methods of mutation available for the user. But this is easy with your solution as it was with mine. All I will need to do is create a base class that would be the type of structure (tree, list, graph) and then derive new classes for each of the different mutation systems that could be incorperated.

Thanks for the help!

Also, while you kind of understand my system I was wondering if you think that if I make it a kind of ''plugable'' system, it will be more user friendly? Example... Each of the different types of classes and derived classes are available in DLL format. This way, you can mix and match all of the different types with-out ever recompiling...

It might just make it a lot more messy... not sure.. what do you think?

Dwiel

Here wwe have hit the wall of my ignorance of GP. The system I suggested was good for a general GA. Maybe GP is specific enough that indeed you could have everything you need in a few well interfaced classes.

But just to make sure you understand my code, I never suggested that mutator would inherit from group, but rather that it would specialize the mutator template.

A system that uses a very similar approach is MFC''s document/view architecture. Try to look at the headers produced by the wizard of a simple SDI that supports document view. MFC is very "pluggable" but not quite in the same way you have i mind.

The code I provided is actually wrong, as it does not include the template arguements(My failure to use the code tags apparently wiped them out)

Peace Out!

I did implement GP with this architecture :

template
class CGeneticAlgorithm
{
virtual void Randomize(T& t) = 0;
virtual void Reproduce(const T& father, const T& mother, T& son1, T& son2) = 0;
virtual void Mutate(T& t) = 0;
};

The user derivate this class and implement the few abstract methods. It has then access to methods to indicate the size of the population...