• Advertisement

Archived

This topic is now archived and is closed to further replies.

GA in a more literal sense

This topic is 5541 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I am writing a GA for a class that I am not sure will keep its current chromasome. Is there any way in C++ to automatically generate a chromosome from a class? e.g.: [cpp] class Crud { unsigned int a; unsigned char b; public: std::vector<bool> GenerateChromasome(); }; ... std::vector<bool> Crud::GenerateChromasome() { unsigned int i; unsigned int temp_a = a; unsigned char temp_b = b; std::vector<bool> chroma; for(i = 0; i < sizeof(unsigned int); ++i) { chroma.push(temp_a%2); temp_a/=2; } for(i = 0; i < sizeof(unsigned char); ++i) { chroma.push(temp_b%2) temp_b/=2; } } [/cpp] But I want the chromasome function generated. Is this possible through templates or inheritance? I don''t see a way apart from running scripts on my code. :-/ Thanks a lot for your help. -flang

Share this post


Link to post
Share on other sites
Advertisement
What exactly do you mean? Is your problem that it changes every time it''s called? (I guessed that from your "not sure will keep its current chromosome" line.) If so, just move the chroma object into the class and check that it''s empty before filling it - that way it''ll only be generated once for each instance of the class. Better still, initialise it in the constructor.

If you really want to evolve the code within the GenerateChromasome function you''d need to use some sort of scripting, although to be honest I can''t see an application where you''d need that.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

Share this post


Link to post
Share on other sites
I''m not sure I understand what you mean. Could you clarify?

You code seems a bit odd too. You''re looping from 0 to the size of a char, which is 1. Always will be 1. You run this loop 4 times.. Why not just say (i = 0; i < 4) and fill in the code?

I''m quite curious about what you''re trying though.


Cheers,
Will

Share this post


Link to post
Share on other sites
I suspect that what you mean is (and please correct me if I''m wrong)...

That during the course of running your GA you want to vary either a) the length of the chromosome; b) the encoding alphabet of the chromosome; or c) both.

This would constitute a dynamic encoding scheme for your objective function. Perhaps you could provide more details about your optimisation/search problem so that we could better assist you in determining the appropriate methodology for a dynamic encoding.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Well spotted mistake in the sizeof... :-(

What I meant was that I would like to have a way of easily programming Chromasomes. Since the process of breeding is pretty simple on the top level, it seems to me that the breeding should be something quite easy to program. Or rather, should be made easy. So instead of what I initially put, it would be ''nice'' to have something akin to:

class something
{
private:
std::string name;
unsigned int id;

private genes:
unsigned int mass;
unsigned int volume;
unsigned int colour;
};

where ''genes'' is a bit like QT''s ''slot'' and ''signal'' so it has code generated for encoding and decoding chromasomes, as well as crossing.

Would this be:
a.) a good idea
b.) airly straight forward
c.) already done?

Thanks a bunch..
-flang

Share this post


Link to post
Share on other sites
Here''s one way:


  
//------------------------------------------------------------------------

// When creating your genes, inherit from this base class to make sure

// the interface is acceptable.

// Also make sure the default constructor for a gene creates a ''random'' gene.

//------------------------------------------------------------------------

class GeneBase
{
public:

virtual void Mutate()=0;

virtual bool operator==(const GeneBase &rhs) const = 0;

virtual ~GeneBase(){}
};

template<class Gene>
std::vector<Gene> CreateRandomChromosome(const int length)
{

std::vector<Gene> chromosome;

for (int gene=0; gene<length; ++gene)
{
chromosome.push_back(Gene());
}

return chromosome
}





ai-junkie.com

Share this post


Link to post
Share on other sites
I already have something resembling that... Which is reassuring since it means I am on the right track.

Timkin: I am not really searching anything, but trying out a dynamic breeding system for my own personal pokemon/tomagotchi game.

And a learning experience (read: I don''t intend to polish it or make it ''good'' -unless I show it to friends and they go spastic and think its the coolest thing ever and demand I polish it up and distrobute it.)

Share this post


Link to post
Share on other sites
You could always consider making a structure for an individual chromosome, and then creating a doubly-linked list to store Chromosomes.

Write Add, Remove, Move, and Insert functions for the linked list, and you''re done.

Will

Share this post


Link to post
Share on other sites
quote:
Original post by flangazor

where ''genes'' is a bit like QT''s ''slot'' and ''signal'' so it has code generated for encoding and decoding chromasomes, as well as crossing.



Each of the genes should not contain information about how to encode or decode the chromosome, unless you want to dedicate a particular gene to that function.

Either, your chromosome class should contain methods for encoding or decoding the information within the class structure, or the chromosome class should look for a particular gene and encode/decode the information in the chromosome according to directions from this structure gene.

However, this latter approach really isn''t necessary for a GA, even one for the purpose you have described (artificial breeding). You can do everything just as well by hiding this information within the chromosome class.

Cheers,

Timkin

Share this post


Link to post
Share on other sites
Timkin,

quote:
Each of the genes should not contain information about how to encode or decode the chromosome, unless you want to dedicate a particular gene to that function.


Well, it would be nice to have encoding and decoding functions generated for me since it would be such a common task.

Failing that, I suppose I could use fup''s template.

Thanks, everyone, for your insight.

-flang

Share this post


Link to post
Share on other sites
quote:
Original post by flangazor
Well, it would be nice to have encoding and decoding functions generated for me since it would be such a common task.



I don''t see how you''re going to get automatically generated encoding and decoding functions?! You''re going to have to write them yourself... at least at some level of your class heirarchy!

Timkin

Share this post


Link to post
Share on other sites
QT: I can think of several expansions of that abbreviation... could you elaborate please?

Cheers,

Timkin

Share this post


Link to post
Share on other sites
QT, the windowing library.

http://doc.trolltech.com/3.0/

It has a signals and slots way of doing things:

http://doc.trolltech.com/3.0/signalsandslots.html

It does this by having a precompiler that generates code for functions that are designated for use as slots, or signals:


A minimal C++ class declaration might read:


class Foo
{
public:
Foo();
int value() const { return val; }
void setValue( int );
private:
int val;
};

A small Qt class might read:


class Foo : public QObject
{
Q_OBJECT
public:
Foo();
int value() const { return val; }
public slots:
void setValue( int );
signals:
void valueChanged( int );
private:
int val;
};


I was of the opinion that something in the same vein could be done for data members for use in Genetic Algorithms. Determine which values are part of a chromosome, and encode them using a generated function that was generated by the precompiler by looking at which data members are designated to be part of the chromosome.

Share this post


Link to post
Share on other sites
Aha! I think I understand you now.

You''re looking for some sort of automatic system that will take any given class, or part of a class, and create a chromosome to represent it, right? Or more specifically, create the functions and data that will represent it.

Basically, the problem you have is that while QT''s signals and slots are pretty standard across all classes, the representation you might want to use for GAs would change from situation to situation. You might have limits on what valid chromosomes are, you might want to choose normal binary or grey code, etc.

Probably the best way is to instead use some sort of template class which can take any basic type and encode it. You can use policy classes to specify the encoding methods etc. A generic encoding function could probably be written using sizeof() to make sure that you know how many bits you''re working with, although really you should use the constants in the numeric_limits class in the <limits> header.

Alternatively, have you looked at GALib? It is "free for any use, commercial or otherwise" and might suit your needs as a lot of the functionality you may need is already there.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

Share this post


Link to post
Share on other sites
Yeah. Finally I got someone on my page. ;-)

I am usually pretty good at asking questions.. sorry it took so long this time.

wrt GALib, I know if it, but I haven''t tried using it. I saw a link to it on ai-depot.com. I was hoping to work pretty much from scratch as a learning excersise.

After I make some progress, I will try GALib and compare my results with it''s results.

I will try your templating method. I read about using limits in Scott Meyer''s book, but have long since returned it to the library.

Cheers,
-flang

Share this post


Link to post
Share on other sites

  • Advertisement