Multiobjective Genetic Algorithm Generalised Assignment Problem - multiple pareto front not foun

I'm trying to solve a GAP problem of assigning students to supervisors using multi-obj GA toolbox. I have created both the students and supervisor's preference tables. The chromosome is chosen to be of length no_of_students to ensure each student is allocated a supervisor where each gene in the chromosome is an integer representing the supervisor assigned to a student. However, a supervisor is allowed to supervise multiple students. Ideally, each student should be assigned a supervisor from his list of preference and similarly for the supervisor. The GA should try to find the best combination of supervisor allocation that measures the compromise between the students and supervisors satisfaction i.e. obj functions f1 and f2 measured on each matrix. I expect to get a pareto set of solutions after running the code but GA returns just one pareto solution.

Can anyone help to explain why this might be?

The codes are available here: https://drive.google.com/open?id=0ByrZwrz8Bo8Ga19sZjc3elBGMkU

Answer 1

[Alan Weiss]

The gamultiobj solver does not support integer variables. The ga solver does not calculate a Pareto front, it just finds a minimum.

If you try to find a Pareto front manually by choosing different cost functions for different ga runs, then you should be able to get a Pareto front, assuming that there is more than one integer-feasible point and that the costs are chosen appropriately. You might need to help ga by giving a variety of integer-feasible initial points in a custom initial population.

Or you could just use a more appropriate solver. I suggest that you use intlinprog with a variety of cost functions similar to what I just described for ga. If you can formulate your problem as an MILP, you will find that intlinprog is faster and more reliable than ga.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Abiodun Ogunmolu]

Thanks for your response Alan. What I mean is I expect gamultiobj to return a set of solutions that minimises the supplied fitness function and not one solution. From the returned set of solutions I should then be able to calculate the value of the two fitness functions for each solution in the set.

Do you know why it may be that only one solution gets returned?

Thanks.

[Alan Weiss]

I am sorry, I cannot understand what you are doing. gamultiobj does not support integer variables, period. So your problem formulation, which I believe requires integer variables, cannot be done in gamultiobj, unless you have a custom population type, which you did not mention. That's why I thought you were using ga to perform the minimization.

If, indeed, you are using ga, then you should not be surprised that it returns just one answer, because that is what ga does.

If I misunderstand entirely, then please be more explicit about what you are doing, including showing your calls to ga or gamultiobj or whatever it is you are doing, and maybe show relevant portions of your fitness function and constraints.

Alan Weiss

MATLAB mathematical toolbox documentation

[Abiodun Ogunmolu]

Apologies for not making it clear. I understand gamultiobj doesn't support integers so I round the solution generated by gamultiobj to the nearest integer (is that acceptable?) and then proceed to carry out some calculations. The fitness function is:

if true
function [f1, f2] = fitnessFun(Z)
  % fitness function that returns the cost with respect to the student's
  % satisfaction and supervisor's satisfaction 

    global  noStu  SupM % noStu = total number of students
                        % SupM=cost matrix for supervisors
    Z=round(Z);         % since GA generates decimal values, it is rounded up 
                        % or down to obtain integers

    temp_f2=zeros(1,noStu);
    PEN_B=10e7; % penalty for assigning supervisor outside a 
                % student's preference list                  

        for i=1:noStu

            svi=Z(i); % extract the supervisor assigned to student i

            supPrefList = getSupPrefList(SupM, svi); % obtain the preference 
                                                     % list of a supervisor
            if ismember(i,supPrefList)
               svj=SupM(i,svi); 
               temp_f2(i)= svj;
            else
                temp_f2(i)= PEN_B;
            end                        
        end
        f1=sum(Z(:)); % the first obj function is the sum of the chromosome
                      % we are trying to obtain a lower sum (minimise)

        f2=1/sum(temp_f2(:)); % the second obj function is the sum of the 
                              % elements of the supervisor's matrix cost

    end

end

and here is the call to gamultiobj:

if true
lb=ones(1,noStu); % lower bound on design variables value
ub=noSup*ones(1,noStu); % upper bound on design variables value
Generations_Data = 200;
PopulationSize_Data=800;
c_rate = 0.7;                               % crossover rate
nvars=noStu;
options = gaoptimset;
options = gaoptimset(options,'PopulationSize', PopulationSize_Data);
options = gaoptimset(options,'Generations', Generations_Data);
options = gaoptimset(options,'CrossoverFcn', {  @crossoverintermediate c_rate });
options = gaoptimset(options,'Display', 'off');
options = gaoptimset(options,'PlotFcns',{@gaplotpareto});
[x,fval,exitflag,output,population,score] = ...
gamultiobj(@fitnessFun,nvars,[],[],[],[],lb,ub,@constraintFunc,options);
end

And the constraint:

if true
  function [C_ineq, Ceq] = constraintFunc(Z)
  % There's no equality constraint.
  % This checks to ensure that aeach solution generated satisfies the
  % lower and upper bounds of the constraint
  global lc uc

    Z=round(Z);    
    freq=hist(Z,unique(Z));
    h=find(freq>uc | freq<lc);
    if isempty(h)
        val = -3;
    else
        val = 4;
    end
    C_ineq=val;
    Ceq=[];
end  
end