Results 1 to 9 of 9
  1. #1
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default Q about Genetic programming

    I have an assignment for uni, that goes as follows:
    You have a given communications network (a list of servers, and connections between them), your task is to disable it. A network is disabeled when there is no pair of connected servers. Disable the network by removing the least amount of servers.
    Now, I've made all of the backbone work on this, defined all the data structures, and came up with a naive algorithm that doesn't guarrantee a solution that is close to optimum (just remove the server with the most connections). Our teacher gave us a tip to look up genetic programming, as that is a neat way to get a solution that is pretty close to optimum. So, I looked up a few tutorials on the matter, and got to coding. The problem is, my algorithm hits a sort of threshold that it just can't stump over and keeps looping indefinately. I've implemented all the necessary operators (crossover, mutation, roulette selection for "breeding" etc.), so I'm kinda stumped. The encoding I used is an array of booleans, each representing one server (true = server working, false = server destroyed), and my fitness function is defined as num. of connections/num. of active servers, so once I hit 0, I found a solution. From what I understand of genetic programming, the purpouse of mutation is avoiding getting stuck in some local optimum, but that's exactely what's happenning. So before I paste any code up, I'd like to ask if anyone here has any experience with this matter (I'm looking at you JosAH! :D) who'd be willing to read a few lines of code.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  2. #2
    Fubarable's Avatar
    Fubarable is offline Moderator
    Join Date
    Jun 2008
    Posts
    19,316
    Blog Entries
    1
    Rep Power
    26

    Default

    Wow, I'll of course be no help to you, knowing nothing about genetic algorithms (other than what's in Wikipedia), but I'd be very interested in what transpires because this sounds extremely cool. Good luck!
    Last edited by Fubarable; 05-12-2010 at 02:38 AM.

  3. #3
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    how many servers?
    how large is your pool size?
    what are the ratios for crossover/mutation?

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

    Default

    Quote Originally Posted by m00nchile View Post
    I have an assignment for uni, that goes as follows:
    You have a given communications network (a list of servers, and connections between them), your task is to disable it. A network is disabeled when there is no pair of connected servers. Disable the network by removing the least amount of servers.
    I'm still a bit sleepy (it's early in the morning overhere and I didn't have my shots of espresso yet ;-) but I do know that I don't like genetic programming for a reason you described yourself: you can get stuck in a local optimum and there is no way out. It can be solved by applying a bit of simulated annealing but I don't like that either; it's like stirring the current solution up and trying again and hope for the best.

    I'll have a look at a bit of theory first and if I find some time I'll try to construct a solution finding algorithm from it; no promises made though ;-)

    kind regards,

    Jos

  5. #5
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Quote Originally Posted by iluxa View Post
    how many servers?
    how large is your pool size?
    what are the ratios for crossover/mutation?
    I haven't written up an exact way to define a pool size yet, but I'm trying various settings, from 20-100, dependent on the server count (256 to > 1000). My crosover rate is 80%, mutation rate is 1%, and I do use elitism (a few of the best chromosomes are directly copied to the next generation).

    Quote Originally Posted by JosAH View Post
    I'll have a look at a bit of theory first and if I find some time I'll try to construct a solution finding algorithm from it; no promises made though ;-)
    Cool, thanks. Just a word of warning, the solution this algorithm is supposed to find is not a disconnected graph, but a graph that has no edges at all.
    And thanks to everyone who took a bit of time too have a look at my problem!
    Last edited by m00nchile; 05-12-2010 at 10:38 AM.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  6. #6
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    in my experience with genetic programming, thats what i would try

    - use larger pools. with mutation rate of 1% and pool size of 20, you're having no mutations at all 80% of the time. the smaller the pool, the more the chance all hypothesises (how do you spell that anywayz...) will be close together and all together fall into a local minimum.

    I'd use pool size of ~1,000 - 10,000

    - use higher mutation rate. I'd use at least 10%, but perhaps as high as 20%.

    - how exactly did you implement crossover?

  7. #7
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Well, my mutation rate came from a tutorial about genetic programming, so I'll try a greater value. Also know, that the mutation rate gets checked on every bit, not just once on the whole chromosome. Now, greater pool sizes are not that feasible due to the slowness of the algorithm. Crossover was implemented as follows:
    Java Code:
    select 2 parents from the pool, better fitness chromosomes have better chance of being selected.
    Example:
    crossover point (randomly generated): 3
    parent1: [1,1,0,1,0,0,1,1,1]
    parent2: [0,1,1,0,0,1,1,0,1]
    
    child1 : [1,1,0,0,0,1,1,0,1]
    child2 : [0,1,1,1,0,0,1,1,1]
    I've been to a few sites about his problem, and most suggested single point crossover as a good method.
    Ever seen a dog chase its tail? Now that's an infinite loop.

  8. #8
    iluxa is offline Senior Member
    Join Date
    Mar 2010
    Posts
    266
    Rep Power
    5

    Default

    Mutation-wise, I guess if that's your probability for every bit, it's high enough.

    so try larger pool size + possible two-point crossover?

  9. #9
    m00nchile is offline Senior Member
    Join Date
    Feb 2010
    Location
    Ljubljana, Slovenia
    Posts
    470
    Rep Power
    5

    Default

    Yeah, I'll have to try something different, and mainly go back to the drawing board and make up a good fitness function, and maybe even do a bit of work on my starting conditions, as potential solutions that have most of the servers as active just pollute the gene pool.
    Ever seen a dog chase its tail? Now that's an infinite loop.

Similar Threads

  1. genetic algorithm
    By rpsaranya in forum New To Java
    Replies: 1
    Last Post: 03-05-2010, 07:30 AM
  2. GUI Programming Help
    By sirwiggles in forum New To Java
    Replies: 4
    Last Post: 04-28-2009, 04:53 AM
  3. genetic algorithms
    By nurfadhillah in forum Advanced Java
    Replies: 1
    Last Post: 10-19-2008, 04:13 PM
  4. New to Programming . . .Need Help
    By DSutta22 in forum New To Java
    Replies: 2
    Last Post: 09-10-2008, 05:19 AM
  5. programming
    By abcdefg in forum New To Java
    Replies: 9
    Last Post: 03-10-2008, 10:34 AM

Posting Permissions

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