gamominsc.m

this is for demo in matlab

                count_wtcp = count_wtcp + 1;
            else
                count_better(k) = count_better(k) + 1;
                count_btcp = count_btcp + 1;
                count_wtcp = count_wtcp + 1;
            end
        end

        if count_btcp == num_fitness            % the currently checked element in Pareto Set is totaly dominated
            to_be_removed = [to_be_removed h];
        elseif count_wtcp == num_fitness
            flag_worst = 1;
        end
        
        if Popul_Fit(i,:) == Pareto_Fit(h,:)     % The Function sets are identical
            if Popul_Set(i,:) == Pareto_Set(h,:)
            else                                % The Genes are identical
                Equal_min = 1;
                to_be_removed = to_be_removed(1:(length(to_be_removed)-1));
            end
        end
        
    end
    
    if sum(count_better) >= num_fitness*num_pareto & Equal_min == 0
        % Current Popul_Fit is better than all from Pareto_Fit
        NPareto_Set = [Pareto_Set; NPareto_Set];
        NPareto_Fit = [Pareto_Fit; NPareto_Fit];
        Pareto_Set = Popul_Set(i,:);
		Pareto_Fit = Popul_Fit(i,:);
        num_pareto = 1;
        
    elseif ( max(count_better) >= 1 & flag_worst == 0) | Equal_min
        % Current_Popul_Fit is better than some and worst than others from Pareto_Fit
        num_to_rem = length(to_be_removed);
        
        if num_to_rem ~= 0      % removing the dominated Genes from Pareto_Set
            for v = num_to_rem:-1:1
		        NPareto_Set = [NPareto_Set; Pareto_Set( to_be_removed(v),: )];
		        NPareto_Fit = [NPareto_Fit; Pareto_Fit( to_be_removed(v),: )];
                Pareto_Set( to_be_removed(v),: ) = [];
                Pareto_Fit( to_be_removed(v),: ) = [];
                num_pareto = num_pareto - 1;
            end
        end
        
        Pareto_Fit = [Pareto_Fit; Popul_Fit(i,:)];
        Pareto_Set = [Pareto_Set; Popul_Set(i,:)];
        num_pareto = num_pareto + 1;
    else
        NPareto_Set = [NPareto_Set; Popul_Set(i,:)];
        NPareto_Fit = [NPareto_Fit; Popul_Fit(i,:)];
    end

end

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  NonDominated Sorting Selection  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Genetic Algorithm
%			Non-Dominated Sorting Selection
%
%	[PARENTS, GENES_ALL] = GAParetoOpt (Pareto_Set, Pareto_Fit, ...
%							Non_Pareto_Set, Non_Pareto_Fit, populSize)
%
%   result:
%       PARENTS    - choosen parent chromosomes
% 				     matrix with couples [Parent1 Parent2]
%		GENES_ALL  - List of all Genes
%
%   arguments:
%		Pareto_Set 	   - Pareto Optimal Set
%		Pareto_Fit 	   - Pareto Otpimal Fitness Values
%		Non_Pareto_Set - The other genes
%		Non_Pareto_Fit - Fitness value of Non_Pareto_Set
%       populSize 	   - Population Size
%
%   Andrey Popov                  		www.automatics.hit.bg
%   [e-mail]          		Last update: 27.06.2003
function [SelParents, Pareto_Set_total] = GANDominSort (Pareto_Set, Pareto_Fit, Non_Pareto_Set, Non_Pareto_Fit, populSize)

[numPareto, x] = size(Pareto_Fit);
Fitness = ones(numPareto, 1);	% assigning rank to the Pareto optimal solutions
Pareto_Set_total = Pareto_Set;

i = 2;
[numNonPareto, x] = size(Non_Pareto_Set);

while ( numNonPareto>0 )
	[Pareto_Set_, Pareto_Fit_, Non_Pareto_Set, Non_Pareto_Fit]  = ...
				sortPareto( Non_Pareto_Set, Non_Pareto_Fit, [], [] );
	
	[numPareto, x] = size(Pareto_Fit_);
	Fitness = [Fitness; ones(numPareto,1)*i];
	Pareto_Set_total = [Pareto_Set_total; Pareto_Set_];
	
	[numNonPareto, x] = size(Non_Pareto_Set);

	i = i + 1;
end
	
Fitness = i - Fitness; 
% renumbering (Pareto optimal solutions receive heightest rank)

SelParents = [];

M = ceil(populSize/2);
Scale = sum(Fitness);
[Num_Par,x] = size(Fitness);

while M > 0
	% random number with uniform distribution
	rh = rand*Scale; 
	H = Roulette( rh, Fitness, Num_Par );
	K = H;
	while (K == H)
		rk = rand*Scale;
		K = Roulette( rk, Fitness, Num_Par );
	end

	M = M - 1;
	SelParents = [SelParents; H, K];
end %while

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  Pareto Optimal Selection  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	Genetic Algorithm
%			Pareto Optimality Selection
%
%	[PARENTS, GENES_ALL] = GAParetoOpt (Pareto_Set, Pareto_Fit, ...
%							Non_Pareto_Set, Non_Pareto_Fit, populSize)
%
%   result:
%       PARENTS    - choosen parent chromosomes
% 				     matrix with couples [Parent1 Parent2]
%		GENES_ALL  - List of all Genes
%
%   arguments:
%		Pareto_Set 	   - Pareto Optimal Set
%		Pareto_Fit 	   - Pareto Otpimal Fitness Values
%		Non_Pareto_Set - The other genes
%		Non_Pareto_Fit - Fitness value of Non_Pareto_Set
%       populSize 	   - Population Size
%
%   Andrey Popov                  		www.automatics.hit.bg
%   [e-mail]          		Last update: 27.06.2003
function [SelParents, Pareto_Set_total] = GAParetoOpt (Pareto_Set, Pareto_Fit, Non_Pareto_Set, Non_Pareto_Fit, populSize)

[numPareto, x] = size(Pareto_Set);
	
if (numPareto <= 2)		% only one member in Pareto set
	[Pareto_Set2, Pareto_Fit2, Non_Pareto_Set, Non_Pareto_Fit]  = ...
				sortPareto( Non_Pareto_Set, Non_Pareto_Fit, [], [] );
	Pareto_Fit_total = [Pareto_Fit; Pareto_Fit2];
	Pareto_Set_total = [Pareto_Set; Pareto_Set2];
else
	Pareto_Fit_total = Pareto_Fit;
	Pareto_Set_total = Pareto_Set;
end

%XXXXXXXXXXX Selection
SelParents  = GAMOSelect ( Pareto_Fit_total, populSize, numPareto );

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  Pareto Optimal Selection  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% GAMOSelect
%
% MultiObjective Select
%
% PARENTS =  GAMOSelect ( Pareto_Fit, Num_Ind, Num_Pareto )
%
%   result:
%       PARENTS 	- choosen parent chromosomes
%				  		matrix with couples [Parent1 Parent2]
%
%   arguments:
%		Pareto_Fit 	- Fitness Values of all Parents 
%       populSize   - number of couples (respectively number of children)
%		Num_Pareto  - number of individuals in Pareto Set
%
%   Andrey Popov                     [e-mail]      
%   www.automatics.hit.bg            Last update: 22.06.2003
function [result] = GAMOSelect ( Pareto_Fit, populSize, numPareto )

[np,mp] = size( Pareto_Fit );

if ( np > numPareto )
	numA = numPareto;			% number of individuals in 1st Pareto Set
	numB = np - numPareto;		% number of individuals in 2nd Pareto Set
	D = numPareto;				% distance between 1st and 2nd sets
else
	numA = numPareto;
	numB = numPareto;	
	D = 0;
end

result=[];
M =  ceil(populSize/2);

while M > 0
	% random number with uniform distribution
	H = ceil(rand*numA);
	K = H;
	while (K == H)
		K = D + ceil(rand*numB);
	end

	M = M - 1;
	result = [result; H, K];
end %while

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  Roulette Wheel Selection  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Roulette Wheel
%
% Calculates which parent is taken
%
%	ParentNum = Roulette( randN, Fitness, Num_Par )
%
%   result:
%       ParentNum - choosen parent chromosome
%
%   arguments:
%		randN	- random number between 0 and sum of all Fitness functions
%		Fitness - vector with fitness functions of the parents
%		Num_Par - Number of possible Parents
%
% 
%   Andrey Popov                     [e-mail]      
%   www.automatics.hit.bg            Last update: 27.06.2003
function ParentNum = Roulette( randN, fitness, Num_Par )

W = 0; 
for i = 1:Num_Par
	if ( W >= randN )
		break;
	end
	W = W + fitness(i);
end
ParentNum = i;
return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  Recombination - Standart CrossOver  %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% GACrossSC
%
% CrossOver Operation - Standard Crossover
%
% FPopul =  GACrossSC ( SelPar, IPopul, Num, Mask )
%
%   result:
%       FPopul  - Offspring (population after CrossOver)
%
%   parameters:
%		SelPar  - matrix with selected parents [Parent1 Parent2]
%       IPopul  - Population with parent individuals ( P x N matrix ) 
%           	 	P - number of parents
%           	 	N - number of elements in chromosome
%       Num     - number in 'children' in next generation
%       Mask    - 1xN boolean vector - mask showing which elements are changed in gen
%               	if MASK is empty or missing than random mask is used
%
%   Andrey Popov							www.automatics.hit.bg
%   [e-mail]                    Last update: 22.06.2003
function [result] = GACrossSC ( SelParents, InitPopul, Num, Mask )

	if (nargin < 3)
 	   error('Wrong number of input parameters in GACrossSC');
	end

	[ m,N ] = size(InitPopul);
	if (m==1)
		error('Only 1 gen in GENS matrix');
	end
	result=[];

	if ( nargin == 3 & ~isempty(Mask) ) | ( N == 2 )
		% Used Defined crossover Mask is used
		if (N == 2)
			Mask = [1 0];
		else
			[ u,n ] = size(Mask);   
			if (n ~= N)
		        error(' GENS and MASK matrix are not with the same dimension');
		    end
		end
		MaskType = 0;	
	    Mask_ = Mask < 0.5;
	else
		MaskType = 1;
	end
		
	i = 1;
	while Num > 0
		H = SelParents(i,1);
		K = SelParents(i,2);
	
		if ( MaskType == 1 )	% random mask is used
	        Mask = rand(1,N) < 0.5;
	        Mask_ = Mask < 0.5;
		end
		
		Q = Mask.*InitPopul(H,:);
	 	W = Mask_.*InitPopul(K,:); 
	    result = [result; Q + W];
	    Num = Num - 1;
		
	    if ( Num==0 ) 
			break;
	    end
	
	    Q = Mask.*InitPopul(K,:);
	    W = Mask_.*InitPopul(H,:); 
	
	    result = [result; Q + W];
	    Num = Num - 1;
		i = i + 1;
	end %while

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  VISUALIZATION  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% ReducePareto
%
% Reducing the number of Pareto Optimal Solutions
%
% [New_P_Set, New_P_Fit] = ReducePareto(Pareto_Set, Pareto_Fit, Max_Number)
%
%   Output:
%       New_P_Set  - reduced Pareto Set
%       New_P_Fit  - reduced Pareto Fitness
%
%   Input:
%		Pareto_Set - Pareto Set to be reduced
%       Pareto_Fit - Pareto Fitness
%		Max_Number - Number of solutions to remain
%
%
%   Andrey Popov                            [e-mail]      
%   www.automatics.hit.bg                   Last update: 28.06.2003
function [Pareto_Set, Pareto_Fit] = ReducePareto(Pareto_Set, Pareto_Fit, Max_Number);

[num_Pareto, num_Fit] = size (Pareto_Fit);

while (num_Pareto > Max_Number)
	D = zeros(num_Pareto, 1);	% vector with the neighbor distance
	M = zeros(num_Pareto, num_Pareto);	% matrix with distance to the other solutions
	for i = 1:num_Pareto
		for k = i:num_Pareto
			if k == i
				M(k,k) = Inf;
			else	% Euclidian distance
				M(k,i) = norm( Pareto_Fit(i,:) - Pareto_Fit(k,:) );
				M(i,k) = M(k,i);
			end
		end
	end
	for i = 1:num_Pareto
		[m1, ind1] = min(M(i,:));
		M(i,ind1) = Inf;
		[m2, ind2] = min(M(i,:));
		D(i) = ( m1 + m2 )/2;
	end
	[d, ind] = min(D);
	Pareto_Fit(ind, :) = [];
	Pareto_Set(ind, :) = [];
	num_Pareto = num_Pareto - 1;	
end

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  VISUALIZATION  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function old_Pareto_best = VisualMO( visualize, graph, iteration, visual_iter, ...
					Pareto_Set, Pareto_Fit, old_Pareto_best, FigHandle);

if ( visualize >= 0 )   % temporary result allowed?
	if ( visualize == 1 )		% some results
		if ( old_Pareto_best > Pareto_Fit(1,:) )  
			TD = 1;
			old_Pareto_best = Pareto_Fit(1,:);
		else	TD = 0;
		end
		if ( TD == 1 | (~rem(iteration, visual_iter) ) )
			DispResultsMO( iteration, Pareto_Fit, Pareto_Set, 0 );
			if ( graph > 0 )
				PlotResultsMO( iteration, FigHandle, Pareto_Fit );
			end                    
		end
	elseif ( visualize == 2 )	% all results
		DispResultsMO( iteration, Pareto_Fit, Pareto_Set, 1 );
		if ( graph > 0 )
			PlotResultsMO( iteration, FigHandle, Pareto_Fit );
		end
	else % no results, only dots sign action is taking place
		if ( rem(iteration, 20) == 0 )       fprintf('.');
			if (rem(iteration, 5000) == 0)   fprintf('\n');
			end
		end
	end
end % if visualize

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  Display Temporary Results  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function DispResultsMO( iteration, Pareto_Fit, Pareto_Set, Flag )
    V = sprintf('Iter:%%5.0f ##>Fit:');
	[n,m] = size(Pareto_Fit);
	for i = 1:m
        V = [V sprintf('   %%8.4g')];
    end
	[n,m] = size(Pareto_Set);
	V = [V sprintf('   ##>Genes:')];
	for i = 1:m
        V = [V sprintf('   %%5.6g')];
    end

	if (Flag == 0)
	   MSG = sprintf(V,iteration, Pareto_Fit(1,:), Pareto_Set(1,:));
   	else
		MSG = [];
		for i=1:n
			if (i==n)
				MSG = [MSG sprintf(V,iteration, Pareto_Fit(i,:), Pareto_Set(i,:))];
			else
				MSG = [MSG sprintf([V 13],iteration, Pareto_Fit(i,:), Pareto_Set(i,:))];
			end
		end
	end
    disp(MSG);
return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%  PlotResults - Visual reperesntation of some temporary results  %%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function PlotResultsMO ( iteration, FigHandle, Pareto_Fit)
	figure(FigHandle);
	[n,m] = size(Pareto_Fit);
	if (m==2)		% 2-D
		MSG = sprintf('Fitness Values\nIteration %d; Individs in Pareto set = %d',iteration,n);
		plot(Pareto_Fit(:,1),Pareto_Fit(:,2),'ro','MarkerSize', 5);grid;
		title(MSG);xlabel('Fintess 1');ylabel('Fitness 2');
	elseif (m==3)	% 3-D
		MSG = sprintf('Fitness Values\nIteration %d; Individs in Pareto set = %d',iteration,n);
		plot3(Pareto_Fit(:,1),Pareto_Fit(:,2),Pareto_Fit(:,3),'ro','MarkerSize', 5);grid;
		title(MSG);xlabel('Fintess 1');ylabel('Fitness 2');zlabel('Fitness 3');
	end
	drawnow;
return