gamominsc.m

this is for demo in matlab

% GAMOminSC
%
% Genetic Algorithm MultiObjective Optimization
%		  Conventional CrossOver
%
% [ResultGenes, ResultFit, RecordGenes, RecordFit] = GAminSC ( Function, Bounds, Options, Mask )
%
%   Output:
%       ResultGenes - the result of the minimization
%       ResultFit   - result fitness value
%       RecordGenes - the best individual taken with step, defined in Options
%       RecordFit   - Fitness function values
%
%   Input:
%       Function    - Name of the file which evaluates the fitness function
%                     Function should return value between ( -Inf; +Inf )
%                     Small value means better gen
%                     Input of function is column vector
%       Bounds      - matrix with the upper and lower boundary of the variables
%                     N x 3 matrix  ->  [min max VT]
%                        min - minimal value of the variable
%                        max - maximal value of the variable
%                        VT  - variable type
%							   VT = -1 - integer variable
%							   VT = 0  - float varaible
%       Options     - Options structure - use GAopt to create, load and save the
%                     structure to file. If Options is not set default options are used
%					  		Select - type of selection
%								1 - Non-Dominated Sorting Selection
%								2 - Pareto Optimal Selection
%       Mask        - boolean mask used for the crossover
%                     [NULL] - random mask is used
%
%
%   Andrey Popov                            [e-mail]      
%   www.automatics.hit.bg                   Last update: 11.10.2005
function [Result_Genes, Result_Fitness, RecordGenes, RecordFitness] = GAMOminSC(Function, bounds_orig, options, mask)

alg_ver = '1.0'; 

if (nargin < 2)
    error('   Too few input arguments. See help "GAMOminDR" for details');
end

%================= Check the input arguments ==================%
if nargin < 4 | isempty(mask) == 1
    mask = [];
end
if bounds_orig(:,1) < bounds_orig(:,2)
else
    error('   Lower bound is greater than the Upper bound\n Bounds = [min max VarType]');
end
    
%==================== Define the options ======================%
def_opt = GAopt(-5);			% default options
if nargin < 3
    % no options set -> default options will be used
    options = def_opt;
else
    % update only fields which are not set
    options = CombineOpt(options,def_opt);
end
   
Comment     = options.Comment;
Num_cicles  = options.MaxIter;
populSize  = options.PopulSize;
mutatGenes  = ceil( populSize*options.MutatRate );
% Maximal number of non-dominated chromosomes
maxPareto   = max ( ceil( populSize*options.BestRate ), 3);	
newGenes    = ceil( populSize*options.NewRate );
TolX        = options.TolX;
rec_Iter    = options.RecIter;
par_Select  = options.pSelect;
par_Recomb  = options.pRecomb;
type_Select = 1; % options.Select;
if ( rec_Iter == 0 )  rec_Iter = Inf;  % no record
end
visual_iter = ceil(Num_cicles/5);

val = lower( options.Visual );
if ( strcmp(val,'none') )      visualize = -1; % no visualization at all
elseif ( strcmp(val,'no') )    visualize =  0; % no temporary results
elseif ( strcmp(val,'all') )   visualize =  2; % all temporary results
else                           visualize =  1; % some temporary results
end
val = lower( options.Graphics );
if ( strcmp(val,'on') )       	graph = 1;   % graphics on
elseif ( strcmp(val,'final') )  graph = 0;   % graphics only when done
else         					graph = -1;  % graphics off
end

clear def_opt val;

%============== Transform Bounds to extended form ===============%
Bounds = TransfGenesSC(bounds_orig, TolX);
[ng, mg] = size(Bounds);
ng_ = ng+1;

%---------- Update Mask
Mask = [];
if ~isempty(mask)
    start_pos = 0;
    original  = 1;
    for i = 1:ng
        if Bounds(i,2) == 1
            Mask = [Mask mask(original)*ones(1,(i-start_pos))];
            start_pos = i;
            original = original + 1;
        end
    end
end
    
%=================== Display Start Message ======================%
if ( visualize >= 0 )
    disp(' ');
    clk = clock;
    disp([' GENETIC ALGORITHM for MATLAB, ver ',alg_ver]);
    disp([' MultiObjective Minimization of function "',Function,'"']);
    V = sprintf(' ->Iter:%d Popul:%d<-',Num_cicles, populSize); disp(V);
    clk = sprintf(' Started at %d:%d:%d  %d.%d.%d',clk(4),clk(5),floor(clk(6)),clk(3),clk(2),clk(1));
    disp(clk);
end
if (graph > 0)
    FigHandle = figure; 
else
    FigHandle = 0;
end

%%%%%%%%%%%%%%%%% Generate initial population %%%%%%%%%%%%%%%%%%%%
Popul_Genes = GARandSC(Bounds, populSize);   

iteration = 0;

RecordFitness 		 = [];%NaN*ones(Num_cicles,1); 	% record - every 'rec_Iter' iterations a new "best" fitness value is added
RecordGenes    		 = [];%NaN*ones(Num_cicles,ng); 	% record - every 'rec_Iter' iterations a new "best" gen is added

Pareto_Set 			 = [];
Pareto_Fit 			 = [];
Non_Pareto_Set		 = [];
Non_Pareto_Fit		 = [];
top_Pareto 	  		 = Inf;
top_Pareto_old 		 = Inf;
TD				 	 = 0; % flag: 1 is there have been a total
						  %	dominating individual in current population

%%%%%%%%%%%%%%%%%%%%%%%%%%% Start the cicle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
while iteration < Num_cicles
    iteration = iteration + 1; 
	
	Fitness_Value 		 = [];
    %+++++++++++ Evaluating the genes
    for i = 1:populSize
        ff = feval(Function, Popul_Genes(i,:));
        Fitness_Value = [ Fitness_Value; ff ];
    end
    
    %+++++++++++ finding the individuals in Pareto set
	[Pareto_Set, Pareto_Fit, Non_Pareto_Set, Non_Pareto_Fit]  = ...
					sortPareto( Popul_Genes, Fitness_Value, Pareto_Set, Pareto_Fit );

    %+++++++++++ Make a record
 	RecordFitness = [ RecordFitness; Pareto_Fit(1,:) ];
	RecordGenes   = [ RecordGenes; Pareto_Set(1,:) ];

    %+++++++++++ Printing some results
	if (iteration == 1)
		old_Pareto_best		 = Inf*ones(size(Pareto_Fit(1,:)));
	else
		old_Pareto_best = VisualMO ( visualize, graph, iteration, visual_iter, Pareto_Set, Pareto_Fit, old_Pareto_best, FigHandle);
	end

	%XXXXXXXXXXX Selection
	if ( type_Select == 2)
		[SelParents, Pareto_Set_total] = GAParetoOpt (Pareto_Set, Pareto_Fit, Non_Pareto_Set, Non_Pareto_Fit, populSize);
	else
		[SelParents, Pareto_Set_total] = GANDominSort (Pareto_Set, Pareto_Fit, Non_Pareto_Set, Non_Pareto_Fit, populSize);
	end		

	%XXXXXXXXXXX CrossOver
	Cross_Genes = GACrossSC ( SelParents, Pareto_Set_total, populSize-newGenes, Mask );

	%XXXXXXXXXXX Mutation
    GMut = GAMutatSC ( Cross_Genes, Bounds, mutatGenes );

	%XXXXXXXXXXX New
	GNew = GARandSC( Bounds, newGenes );
	
	%XXXXXXXXXXX Reducing number of Pareto optimal solutions
	[Pareto_Set, Pareto_Fit] = ReducePareto(Pareto_Set, Pareto_Fit, maxPareto); 

	Popul_Genes = [GNew; GMut];
    
end % while
%%%%%%%%%%%%%%%%%%%%%%%%%%% End the cicle %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
Result_Fitness = Pareto_Fit;
Result_Genes   = Pareto_Set;
RecordFitness  = RecordFitness(1:rec_Iter:Num_cicles, :);
RecordGenes    = RecordGenes(1:rec_Iter:Num_cicles, :);

fprintf('\n');
if ( visualize >= 0 )
    fprintf (' Fitness Values:\n');
	disp(Result_Fitness);
    fprintf ('\n Genes Values:\n');
    disp(Result_Genes);
    fprintf ('\n');
	if (graph >= 0)
		if (graph == 0) 		FigHandle = figure;
		end
 		PlotResultsMO( iteration, FigHandle, Pareto_Fit);
	end
end
return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  COMBINEOPT - combines options from Default and User Set  %%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% CombineOpt
% 
% Combines User Options with Default Options
%
%	result_Options = CombineOpt (User_options, Default_options)
%
%   Andrey Popov                            [e-mail]      
%   www.automatics.hit.bg                   Last update: 28.06.2003
function result = CombineOpt(options,def_opt)

result = def_opt;
% Empty options structure
result.Comment = 'Combination of User defined and Default options';
REAL_STRUCT = struct(  ...
        'Comment',[], ...
        'MaxIter', [], ...
        'PopulSize', [], ...
        'MutatRate', [], ...
        'BestRate', [], ...
        'NewRate', [], ...
        'TolX', [], ...
		'pSelect', [], ...
		'pRecomb', [], ...
		'Select', [], ...
        'RecIter', [], ...
        'Visual', [], ...
        'Graphics',[]);
    
Names = fieldnames(REAL_STRUCT);
[m,n] = size(Names);
names = lower(Names);
    
opt_names = lower(fieldnames(options));
try    
    for i = 1:m
        k = strmatch(opt_names(i), names);
        if ( k )
            % Identical fields names
            Real_Field_Name = Names{k};
            Value = getfield(options, Real_Field_Name);
            if exist('Value')
                % the parameter is set in options
                if (strcmp(opt_names(i),'visual') | strcmp(opt_names(i),'graphics') | strcmp(opt_names(i),'select'))
                    value = lower(Value);
                    result = setfield(result, Real_Field_Name, value);
                else
                    result = setfield(result, Real_Field_Name, Value);
                end
            end
        end
    end
catch
    V = sprintf('Options structure is not correct.\nSee: help GAopt for detail about option settings');
    disp(V);
end
return;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  TRANSFORMGENS - transforms genes to extended form  %%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%	TransfGenesSC
%
%	Transforms Bounds matrix and if necessary the genes	
%
%	Bounds = TransformGenesBC(bounds_original, TolX)
%
%   Andrey Popov                            [e-mail]      
%   www.automatics.hit.bg                   Last update: 28.06.2003
function Bounds = TransfGenesSC(bounds_orig, TolX)

[n, m] = size(bounds_orig);
Bounds = [];

dB = bounds_orig(:,2) - bounds_orig(:,1);

%-> float variables
if ( m < 3 )       % if tolerance not set
    bounds_orig(:,3) = TolX;
end
Bounds = [];

for ( i = 1:n )
	if ( bounds_orig(i,3) == -1 )						% integer representation
		Bounds = [Bounds; [dB(i) bounds_orig(i,1:2) 1]];
	else
		Bounds = [Bounds; [dB(i) bounds_orig(i,1:2) 0]];
	end
end

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  GARAND - generates initial random population  %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% GARandSC
%
% Generates Random strings when Standard CrossOver is Used
%
% FPopul =  GARandSC ( Bounds, Num_Ind )
%
%   result:
%       FPopul 	- population of random individuals
%
%   parameters:
%       Bounds 	- extendet matrix of the boundaries
%					[ Distance Lower_Bound Upper_Bound Var_Type]
%					Distance = Upper_Bound - Lower_Bound
%  				    VarType: 1 - integer;  0 - float
%       Num_Ind - number of randomly created individuals
%
%   Andrey Popov                     [e-mail]      
%   www.automatics.hit.bg            Last update: 22.06.2003
function [result] = GARandSC(Bounds, num)

if nargin < 2
    error('Wrong number of input parameters');
end

[nb, mb] = size(Bounds);

result = zeros(num, nb);

result(:,1:nb) = ( ones(num,1)*Bounds(:,1)' ).*rand(num,nb) + ( ones(num,1)*Bounds(:,2)' );

for ( i = 1:nb )
	if ( Bounds(i,4) == 1 )				% the gen is integer
		result(:,i) = round( result(:,i) );  				
	end
end

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  GAMUTAT - mutation of randomly choosen genes  %%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% GAMutatSC
%
% Generates random Mutations when Standard CrossOver is Used
%
% FPopul = GAMutatSC ( IPopul, Bounds, Num_Mut )
%
%   result:
%       FPopul 	 - population after the mutation
%
%   parameters:
%       IPopul   - initial population
%       Bounds 	 - extendet matrix of the boundaries
%					  [ Distance Lower_Bound Upper_Bound Var_Type]
%						Distance = Upper_Bound - Lower_Bound
%						VarType: 1 - integer;  0 - float
%       Num_Mut  - total number of mutations for the population
%
%   Andrey Popov							www.automatics.hit.bg
%   [e-mail]                    Last update: 20.06.2003
function result = GAMutatSC(InitPopul, Bounds, num)

if nargin < 3
    error('Wrong number of input parameters. See "help GAMutatSC"');
end

result   = InitPopul;
[nb, mb] = size(Bounds);
[mg, ng] = size(InitPopul);
% mg - number of chromosomes
% ng - number of genes in a chromosome

if (nb ~=  ng)
    error('Number of bounds NOT equal to number of elements in the string');
end

while ( num > 0 )
	n = ceil(rand*ng);   % number of the gen to mutate
    m = ceil(rand*mg);   % number of the chromosome to mutate

	if ( Bounds(n,4) == 1 )	% integer
		R = round( Bounds(n,1)*rand ) + Bounds(n,2);
	else					% float
		R = Bounds(n,1)*rand + Bounds(n,2);
	end
   
    result(m,n) = R;
    
    num = num - 1;
end

return

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%  SortPareto - finding the Pareto optimal solutions  %%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% sortPareto
%
% Sorting Genes acording to Pareto's criteria
%
% [Pareto_Set, Pareto_Fit, NPareto_Set, NPareto_Fit]  = ...
%					sortPareto( Popul_Set, Popul_Fit, iPareto_Set, iParetoFit )
% 
%   result:
%       Pareto_Set   - result individuals in Pareto set
%       Pareto_Fit	 - Fitness functions of current Pareto Set
%       NPareto_Set  - individuals which are non in Pareto set
%		NPareto_Fit  - Fintess functions of non Pareto individuals
%
%   arguments:
%       Popul_Set    - initial Population
%       Popul_Fit    - Fitness Function of initial Population
%       iPatero_Set  - initial members of Pareto_Set
%       iPatero_Fit  - initial fitness functions of Pareto_Set members
%
%   Andrey Popov                            [e-mail]      
%   www.automatics.hit.bg                   Last update: 22.06.2003
function [Pareto_Set, Pareto_Fit, NPareto_Set, NPareto_Fit]  = ...
					sortPareto( Popul_Set, Popul_Fit, Pareto_Set, Pareto_Fit )

[num_individ, num_genes] = size(Popul_Set);
[num_indiv, num_fitness] = size(Popul_Fit);
[num_pareto, num_fit] 	 = size(Pareto_Fit);
% num_pareto  - number of strings in Pareto Set
% num_individ - number of strings in the set
% num_fitness - number of evaluated fitness functions

NPareto_Set = [];	% Non-Pareto set (dominated solutions)
NPareto_Fit = [];

start_num = 1;
if num_pareto == 0 % if no previous Pareto Set is available
    Pareto_Fit = Popul_Fit(1,:);
    Pareto_Set = Popul_Set(1,:);
    num_pareto = 1;
    start_num  = 2;
elseif  num_fitness ~= num_fit
    error('Number of fitness functions in Popul_Fit and Pareto_Set is different');
end

for i = start_num : num_individ
    
    count_better = zeros(1,num_fitness);
    to_be_removed = [];
    flag_worst = 0;
    Equal_min  = 0;      % there are few minimumums with equal fitness values but different Popul_Set
    
    for h = 1 : num_pareto
        count_btcp = 0; % better than current pareto
        count_wtcp = 0; % worst than current pareto
        
        for k = 1 : num_fitness
            if Popul_Fit(i,k) < Pareto_Fit(h,k)
                count_better(k) = count_better(k) + 1;
                count_btcp = count_btcp + 1;
            elseif Popul_Fit(i,k) > Pareto_Fit(h,k)