djyoti
11-02-2005, 03:38 AM
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.
Let
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 ?
Let
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 ?