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

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 .

[Geoff Hayes]

Reshdev - do you have the Global Optimization Toolbox? If you do, you can use the genetic algorithm functionality from that rather than re-creating the selection, crossover, and mutation operations.

As for your attached file, you indicate that it will generate an initial population. I think that you need some way to output all those members (of the population) from that file so that you can evaluate each separately using your fitness function. Which should be developed next, before moving to the roulette wheel selection which is dependent upon the fitness function to score each member of the population.

[reshdev]

Geoff Hayes, Thank you for your suggestion.

Actually, i am first time working on genetic algorithm.So, please suggest me to way to implement it further. After initial population creation, i am unable to decide how to advance.

[Geoff Hayes]

Reshdev - what does each member of your population represent? How many variables in your optimization problem are you trying to minimize? What is your fitness function? I know that you have described the latter in your question, but it is difficult to understand the pseudo-code.

I think that you should concentrate on getting the fitness function defined next. Use this as the function signature

 function [score] = fitnessFunc(inputVar)

where inputVar is a vector (?) of input variables, and score is a scalar output that indicates the fitness of the input data. Since we are minimizing (is this correct?) then the smaller the score, the more fit the member (of the population) that has these input variables.

Once you have defined the fitness function, and a way to manage your population (i.e. will you use a cell array to hold each member of the population?) then you can move on to the selection operator.

But, you didn't answer my initial question. Do you have the Global Optimization Toolbox?

[reshdev]

i am trying to explain it by example, consider 'input online2([9 1 3; 8 2 4], 5)', this shows that i am sending f= 9 units of data from source node(c0) 1 to termination node(r0) 3 and f=8 units from source node 2 to termination 4. The 5 in end shows, i want population size=5.

r=5 means total nodes in network are 5.

Now, let us come to output. Each member of population represents two matrix's of size 5*5 each combined to each other row wise.

So, actual size if you can see becomes 5*10. So, first 5 columns(or you can say, first 5*5 matrix) of each member is output matrix for input [9 1 3] and column 6 to 10(i.e. next 5*5 matrix), shows output for second input [8 2 4]

Also, Matrix X, for example, for 'output member 1' is obtained by

Matrix X = output from run1 (:,1:5)+output from run1 (:, 6:10)

matrix X will be different for each member.

Note- rows of each member show source nodes and columns shows destination nodes.

yes, i have Global optimization toolbox.

Thank You

[Geoff Hayes]

How do you measure the fitness of a single member of the population? What problem are you trying to minimize?

If each member of the population is a 5x10 matrix, then how do you apply a function to this to say whether this is a "better" 5x10 matrix over another member of the population?

[reshdev]

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]

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

Answer 1

[Geoff Hayes]

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.

[reshdev]

Thank you Geoff, helped a lot to move further.

Can you please explain by giving example that how r gonna select the parent. will it choose the member that has slightly higher commulative probability than r?. and also, why we are sorting the probForMember in ascending order?

Thank You

[Geoff Hayes]

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]

Thank You again Geoff, i have been able to select parents. I am posting another question for crossover of parents.. Please have a look.