Genetic Algorithm Data Structure Dillema

[otacon]

Hey guys, first off I'm fairly new here, and this isn't exactly a coding question, more so a opinion from you guys that might have some experience with this. Also even tho the issue is pretty basic, I put it in the advanced forums because I figured people here might have exp with GA's.

Here is my problem. I'm implementing a fairly abstract genetic algorithm framework, which will be expendable to quite a big range of problems, including np-hard problems...and finding solutions to some of them with evolutionary systems will be very efficiency sensitive.

I would really like to hear your suggestions about the data structure (or combination) that you think would prove most efficient.

At first I assumed keeping my population member (or genes) in an array is a no-go because for every change i make - for example a mutation..or crossover etc..i want to i insert the new gene into the population at a correct location (based on its fitness value)...which made me decide to go with a linked-list (since its just a relinking of 2 nodes to add a new one..which seemed very efficient).

However as I implemented more of the system, I realized that, for example, in order to perform a crossover between 2 population members...i can't just choose two members and get them in O(1) like i could with an array...but have to traverse through my linked list, every time..which if done twice in every crossover becomes very not efficient.

I guess I'm asking for what you think might be the more efficient way of implement this, since I don't have much experience with GA's...and probably won't find a big difference until I'm committed to one alternative.

EDIT: by the way, I do use the GA terminology fairly loosely..and if some of my reasoning makes no sense to you, or is confusing I will gladly explain what i mean. Just looking for some brainstorm:) or someone pointing out i'm wrong :D

[Armadillo]

Hi Otacon,

My answer does not come from the GA course at uni but from what i learned programming Java webapps:
Optimalisation is what you do last, and only if it proves necessary.

You state that your program is designed for efficiency. However i would still go with the rule of thumb of designing your objects to be most comprehensible. Then, get a software tool for profiling (i cannot remember right now what i use last time i used one) and find the bottlenecks.
They are likely to be where you least expect them.

Good luck!

[otacon]

Then, get a software tool for profiling (i cannot remember right now what i use last time i used one) and find the bottlenecks.
They are likely to be where you least expect them.

Good luck!

To be embarrassingly honest, I didn't know software like that was around. Sounds like a great idea to use one though. I'll definitely look into that!

[JosAH]

However as I implemented more of the system, I realized that, for example, in order to perform a crossover between 2 population members...i can't just choose two members and get them in O(1) like i could with an array...but have to traverse through my linked list, every time..which if done twice in every crossover becomes very not efficient.

In general the crossover operation in GAs can't be O(1); think of a TSP solving algorithm using GA: crossing over two routes can even take O(n) steps. Don't bother in this stage of your GA development, leave the efficiency to particular instances of your system.

kind regards,

Jos

[paul pasciak]

This may help to set your mind at ease.

A linked-list is considered to be the best
data structure to use when you are developing
an application where you have no complete
specifications, or proof that an alternate
data structure should be used.

(Unfortunately, I cannot recall where I
had read this)

Anecdotally, a project I am currently working
on superfically dictates, upon studying the
problem, that a data tree structure is needed.
It has turned out that a bare-bones, single
linked-list is completely effective.

Although my algorithm crawls along the
linked-list in a FIFO manner, with each
iteration being o(n), it is easy to deliniate
the past and future data, where the code can
be tweaked, and how auxilerary linked-list
will be implemented.

Right now, I like the certainty of how I
see the project developing. I do not want
to tangle with hypothetical nightmares that
might give me nlog(n) performance.

[Jodokus]

What is wrong with Strings? All kinds of manipulationmethods and if needed access to Stringbuffer, easy displayable, pleasing the eye (esp. ACTG contrasted with 01100111).
(Yes I know this is an old thread, I was searching on "genetic".)
Edit: I made a mistake. The datastructure spoken of here is at populationlevel, not gene or chromosomelevel. The last time I've been reading about (and implementing) GA's and (as a biologist) think it is remarkable how far of biology they often are (but sometimes effective though). I hoped to trigger some discussion on coding, decoupling of genotype/fenotype, (ab)use of fitnessfunctions, but started it incorrectly. Maybe in time start my own thread.