Results 1 to 6 of 6
  1. #1
    otacon's Avatar
    otacon is offline Member
    Join Date
    Dec 2010
    Posts
    24
    Rep Power
    0

    Default Genetic Algorithm Data Structure Dillema

    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
    Last edited by otacon; 12-16-2010 at 08:18 PM. Reason: clarification
    --Otacon
    Somebody set up us the bomb.

  2. #2
    Armadillo is offline Member
    Join Date
    Jul 2010
    Posts
    15
    Rep Power
    0

    Default

    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!

  3. #3
    otacon's Avatar
    otacon is offline Member
    Join Date
    Dec 2010
    Posts
    24
    Rep Power
    0

    Default

    Quote Originally Posted by Armadillo View Post

    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!
    --Otacon
    Somebody set up us the bomb.

  4. #4
    JosAH's Avatar
    JosAH is offline Moderator
    Join Date
    Sep 2008
    Location
    Voorschoten, the Netherlands
    Posts
    13,526
    Blog Entries
    7
    Rep Power
    20

    Default

    Quote Originally Posted by otacon View Post
    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
    cenosillicaphobia: the fear for an empty beer glass

  5. #5
    paul pasciak is offline Senior Member
    Join Date
    Jul 2008
    Posts
    125
    Rep Power
    0

    Default

    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.

  6. #6
    Jodokus's Avatar
    Jodokus is offline Senior Member
    Join Date
    Jan 2011
    Location
    Amsterdam, the Netherlands
    Posts
    230
    Rep Power
    4

    Default

    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.
    Last edited by Jodokus; 05-08-2011 at 08:13 AM.

Similar Threads

  1. genetic algorithm
    By rpsaranya in forum New To Java
    Replies: 1
    Last Post: 03-05-2010, 07:30 AM
  2. Which data structure to choose ?
    By lumpy in forum New To Java
    Replies: 2
    Last Post: 02-20-2010, 04:43 AM
  3. data structure and data base??
    By ahmed13 in forum Advanced Java
    Replies: 8
    Last Post: 03-27-2009, 05:48 AM
  4. data file structure
    By Nicholas Jordan in forum Advanced Java
    Replies: 2
    Last Post: 01-07-2009, 04:16 AM
  5. Queue data structure
    By Java Tip in forum java.lang
    Replies: 0
    Last Post: 04-14-2008, 08:35 PM

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •