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.

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!

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

Quote:

---

Originally Posted by m00nchile

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

Quote:

---

Originally Posted by iluxa

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

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!

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?

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:

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.

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?

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.