Genetic Algorithm

djyoti 101 Nov 02, 2005 at 10:38

The problem is to locate p- emergency service centres for a set of n- villages. Each village is represented by a point, whose location is given in terms of (x, y) coordinates. Maximum distance from each village to its nearest centre is 2 km. We should try to cover all villages by those service centres.


No of villages: n = 50. They are denoted by numerals 1,2,3,…, 50.

No of emergency service centres: p = 8

So, we have to choose 8 villages out of 50 where emergency service centres will be built.

Hence, possible combination of choosing 8 out of 50 = 50C8, which is a huge number.

We are trying to take an initial population of chromosomes, each of which has 8-positions, with numbers 1-50 and no repetition (randomly generated). Like:

1 5 9 18 20 8 49 41

2 4 9 32 45 5 8 27 etc.

Then, taking the villages 1,5,9,18,20 etc. (for 1st string) as the desired locations, we are determining how many villages are covered by circles with 2km radius and centre at the village positions. As we want to cover as many villages as possible, our objective function is to maximize the number of villages covered. Hence, fitness function is expressed by the same quantity.

Now, using GA operators: reproduction, crossover and mutation we wish to find the fitness function value for several generations.

At this point, my queries are:

  1. Are the fitness function and problem formulation proper or any modification required?

  2. What value should we take for probabilities of reproduction, crossover and mutation?

  3. What should be the parent generation size, i.e., how many chromosomes to begin with?

  4. Do you suggest any addition/alteration ?

2 Replies

Please log in or register to post a reply.

NomadRock 101 Nov 02, 2005 at 14:53

Maybe you should ask your teacher? We dont know what information your teacher was expecting you to reason out on your own.

GroundKeeper 101 Dec 27, 2005 at 12:37

If we answer we actually answer the problems. I would guess he wants empirical suggestions..