help for roulette-wheel selection matlab code for minimization problem?

20 Ansichten (letzte 30 Tage)
Hello,
I am trying to implement genetic algorithm.(Already able to generate initial population (matlab code attached))
can any one please help to write roulette-wheel selection matlab code for minimization problem --
Just to explain, Suppose my input to matlab program is online2([9 1 3; 8 2 4], 5)
fitness function= Min. C(1,1)*X(1,1)+C(1,2)*X(1,2)+C(1,3)*X(1,3)+C(1,4)*X(1,4)+C(1,5)*X(1,5)+
C(2,1)*X(2,1)+..............+C(2,5)*X(2,5)+C(3,1)*X(3,1)+........C(3,5)*X(3,5)+C(4,1)*X(4,1)+
.....+C(4,5)*X(4,5)+
C(5,1)*X(5,1)+.....+C(5,5)*X(5,5)
input matrix for C(i,j)= [1 2 3 4 5;2 3 4 5 6; 1 2 3 4 5; 3 4 6 7 8; 9 6 5 3 2]
Matrix X = output from run u (:,1:5)+output from run u (:,6:10)..... note r=5 is given as input within program
X wiil be 5*5 matrix .
  7 Kommentare
reshdev
reshdev am 26 Aug. 2014
Just add following code to existing program for calculating fitness of a single member of the population--
X = output(:,1:5)+output(:,6:10).
C= [1 2 3 4 5;2 3 4 5 6; 1 2 3 4 5; 3 4 6 7 8; 9 6 5 3 2]
for row=1:r
for col =1:r
Ff(row,col)= C(row,col)*X(row,col);
end
end
disp(Ff)
Fitness= sum(sum(Ff));
disp(Fitness)
Geoff Hayes
Geoff Hayes am 26 Aug. 2014
reshdev - you will need to separate your fitness function from the population initialization. Something like
function [score] = myFitnessFunction(inputData)
X = inputData(:,1:5)+inputData(:,6:10);
C= [1 2 3 4 5;2 3 4 5 6; 1 2 3 4 5; 3 4 6 7 8; 9 6 5 3 2];
r = size(X,1);
Ff = zeros(r,r);
for row=1:r
for col =1:r
Ff(row,col)= C(row,col)*X(row,col);
end
end
%disp(Ff)
score= sum(sum(Ff));
%disp(Fitness)
end

Melden Sie sich an, um zu kommentieren.

Akzeptierte Antwort

Geoff Hayes
Geoff Hayes am 26 Aug. 2014
reshdev - I took your code to initialize the population and to score each member, and put both in the myInitPop.m and myFitnessFunc.m. See attached. Now when you execute
pop = myInitPop([9 1 3; 8 2 4], 5);
the output variable, pop, will be a 5x2 cell array where each element corresponds to a member of the population. The first column will have the 5x10 matrix for each member, and the second column will be the score/fitness of each member according to myFitnessFunc.
Now roulette wheel selection, or fitness proportionate selection, is relatively easy (there may be better methods for parent selection) but try using the following pseudo-code to get you going. I'll define the function as
function [parents] = mySelectionRoulette(pop,numParents)
So the inputs to the roulette selection method will be the population, pop, which was generated in the population initialization phase (and will be the updated population on subsequent iterations of the algorithm), and the number of parents to select, numParents. So from this population, we wish to choose a certain number of parents, which corresponds to the output parameter parents.
According to the above link, you need to calculate the probability of each member of the population being selected as a parent, with the idea being that the fitter members will more likely be selected as parents.
This probability will be defined as
invFitnessSum = sum of the inverse of the fitness (score) for each member of population
probForMember(k,1) = (1/pop{k,2})/invFitnessSum
The first is easy to calculate. Just sum the inverse of each score value from the second column of the input vector pop. You will need an array for the second value which will have the probabilities for each member of the population. The array size will correspond to the number of members of the population. Note that we do (1/pop{k,2})/invFitnessSum because (presumably) we are using the GA to minimize the fitness function, so we want those members with a smaller score to have a higher probability of being selected.
You then want to sort the probForMember in ascending order (keeping in mind which probability corresponds to which member). You may in fact want to store this data within probForMember. You could initialize this matrix as
probForMember = zeros(n,2); % where n is the number of members in population
probForMember(:,2) = [1:n]'; % assign the member id to each each element
Then, to do the sort, just try
probForMember = sortrows(probForMember,1)
which will sort the first column in ascending order AND maintain the ids of the members with that probability.
According to the link, we now need the cumulative probability distribution. So use cumsum on the first column of probForMember.
Finally, for each parent that you need to select, generate a random number (see rand) which will correspond to the ball in the roulette wheel analogy, and wherever that ball drops, that is your parent to choose.
Try writing the above code. I think that you have all that is needed to get you started on this.
  3 Kommentare
Geoff Hayes
Geoff Hayes am 27 Aug. 2014
Reshdev - suppose that five members of a population have the following scores
scores = [1 2 3 4 5]';
As we are minimizing, then clearly the first member (index 1) is the fittest, and the last member is the weakest (index 5). We then compute the probabilities for each according to the above as observe
probs =
0.437956204379562 1
0.218978102189781 2
0.145985401459854 3
0.109489051094891 4
0.0875912408759124 5
where the first column corresponds to the probabilities, and the second column the member ids (or indices into the pop cell array).
We sort so that we can construct the cumulative distribution function for thee data. So sort in ascending order to get
probssorted =
0.0875912408759124 5
0.109489051094891 4
0.145985401459854 3
0.218978102189781 2
0.437956204379562 1
Now apply the cumulative summation function to the first column to get
memberCdf =
0.0875912408759124 5
0.197080291970803 4
0.343065693430657 3
0.562043795620438 2
1 1
Now look at the differences between each interval. For any random number generated between 0 and 0.0875912408759124, we select member 5 as a parent. For any random number generated between 0.0875912408759124 and 0.197080291970803, we select member 4. Etc. Note how the interval size increases as the fitness for the member increases, so that for the most fit member (index 1) its interval (slot on the roulette wheel) is the largest, from 0.562043795620438 to 1.
When you generate a random number (which will be between 0 and 1) to determine which parent to select, use the find function to return the index of the first CDF value that is greater than the random number. This index can then be used to get the member index from the second column. For example, if
r = 0.57; % using rand
idx = 5; % using find
memberIdx = memberCdf(idx,2);
reshdev
reshdev am 27 Aug. 2014
Thank You again Geoff, i have been able to select parents. I am posting another question for crossover of parents.. Please have a look.

Melden Sie sich an, um zu kommentieren.

Weitere Antworten (0)

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by