function [ MinValue,bestx,cg] = SGA(PopulationSize,NIterations,lInf,lSup,dim,fobj)
%% 搜索组算法
%% SGA Parameters
AlfaMin=0.01; % minimum value that alpha may assume in Eq.(6): see section 3.4
AlfaInitial=2; % initial value of alpha: Eq.(6)
GlobalIterationsRatio = 0.3; % percentage of itmax dedicated to global phase selection scheme: see section 3.5
NPerturbed = 5; % number of mutated individuals of the search group: see Eq.(5) in section 3.3
PlotFamily = false; % define if plot the value of families
SearchGroupSize=10; %SearchGroupSize >NPerturbed;
if SearchGroupSize==0
disp('Error - Search group is empty -> Redefine SearchGroupSize');
return
end
global OFEs OFELim Plot
Plot=0;OFEs=0;
DisplayParams.PlotFamily = PlotFamily;
% Create a v vector with size of the family
w=(0:1/(SearchGroupSize):1).^2*(PopulationSize - SearchGroupSize);
v = zeros(1,SearchGroupSize);
for i=1:(SearchGroupSize - 1)
v(SearchGroupSize+1-i)=round(w(i+1)-w(i));
end
nRemainder = PopulationSize - SearchGroupSize - sum(v);
v(1) = nRemainder;
% Evaluate the number of global iterations
NIterationsGlobal = floor(GlobalIterationsRatio*NIterations);
% get the problem data;
if length(lInf)==1
lInf= lInf * ones( 1,dim ); % Lower bounds
lSup= lSup * ones( 1,dim ); % Upper bounds
end
% Ellitism: number of individuals that are kept due to their fitness value
elite = 1;
% Percentage of local phase search
NIterationsLocal = NIterations - NIterationsGlobal;
% percentage of alpha_min used to generate new members
SmallValue = 0.0025;
AlfaCorrectionMatrix = [1 -4/(NIterationsGlobal);0.25 -1/(4*NIterationsGlobal);0 0];
% Number of individuals used in each tournament of the algorithm
TournamentSize = 4;
Alfa = (AlfaInitial+AlfaMin)*(lSup-lInf);
if length(lSup) ~= length(lInf)
disp('Simple bounds/limits are improper');
else
%% Generates the initial population
x = zeros(PopulationSize,dim);
for i = 1:PopulationSize
x(i,:) = lInf + (lSup - lInf).*rand(1,dim);
end
%% Evaluates the fitness value of all the individuals
fertility = zeros(PopulationSize,1);
for i = 1:PopulationSize
fertility(i,1) = fobj(x(i,:));
end
Database = [fertility x];
Database = sortrows(Database,1);
%% Selection of the first Search group
Indices = transpose(1:1:SearchGroupSize);
TournamentIndices = Tournament(PopulationSize,SearchGroupSize-elite,TournamentSize);
IterationData= zeros(NIterations,dim+1);
TournamentIndices = sort(TournamentIndices);
Indices(elite+1:SearchGroupSize) = TournamentIndices(:,1);
FamilyLeader = zeros(SearchGroupSize,dim+1);
for i = 1:SearchGroupSize
Local = Indices(i);
FamilyLeader(i,:) = Database(Local,:);
end
%% Iterative process of the SGA:
%%GLOBAL PHASE
for k = 1:NIterationsGlobal
%% Mutation Eq.(5) of section 3.3
% Using tournament, select the individuals to be mutated
PerturbedIndices = ReverseTournament(TournamentSize,NPerturbed,SearchGroupSize);
% Mutation:
for t = 1:NPerturbed
FamilyLeader(PerturbedIndices(t,1),2:dim+1) = mean(FamilyLeader(:,2:dim+1)) + t*std(FamilyLeader(:,2:dim+1)).*(rand(1,dim)-0.5);
FamilyLeader(PerturbedIndices(t,1),2:dim+1) = max(FamilyLeader(PerturbedIndices(t,1),2:dim+1),lInf);
FamilyLeader(PerturbedIndices(t,1),2:dim+1) = min(FamilyLeader(PerturbedIndices(t,1),2:dim+1),lSup);
FamilyLeader(PerturbedIndices(t,1),1) = fobj(FamilyLeader(PerturbedIndices(t,1),2:dim+1));
end
%% Construction of the Search Group and Generation of the families
[FamilyLeader, FamilyGroup]= FamilyGeneration(FamilyLeader,SearchGroupSize,lSup,lInf,Alfa,fobj,v,PlotFamily);
FamilyLeader = sortrows(FamilyLeader,1);
IterationData(k,:) = FamilyLeader(1,:);
%% Update the value of alpha
AlfaCorrection = max(AlfaCorrectionMatrix(:,1)+AlfaCorrectionMatrix(:,2)*k);
Alfa = (AlfaInitial*AlfaCorrection+AlfaMin)*(lSup-lInf);
if OFEs>OFELim
break
end
end
%% LOCAL PHASE
for k = 1:NIterationsLocal
PerturbedIndices = ReverseTournament(TournamentSize,NPerturbed,SearchGroupSize);
for t = 1:NPerturbed
FamilyLeader(PerturbedIndices(t,1),2:dim+1) = mean(FamilyLeader(:,2:dim+1)) + t*std(FamilyLeader(:,2:dim+1)).*(rand(1,dim)-0.5);
FamilyLeader(PerturbedIndices(t,1),2:dim+1) = max(FamilyLeader(PerturbedIndices(t,1),2:dim+1),lInf);
FamilyLeader(PerturbedIndices(t,1),2:dim+1) = min(FamilyLeader(PerturbedIndices(t,1),2:dim+1),lSup);
FamilyLeader(PerturbedIndices(t,1),1) = fobj(FamilyLeader(PerturbedIndices(t,1),2:dim+1));
end
[ Database, FamilyGroup ] = LocalFamilyGeneration(FamilyLeader,PopulationSize,SearchGroupSize,lSup,lInf,Alfa,fobj,v,PlotFamily);
Alfa = (((NIterationsLocal-k)/(NIterationsLocal))*AlfaMin+SmallValue*AlfaMin)*(lSup-lInf);
Database = sortrows(Database,1);
IterationData(NIterationsGlobal+k,:) = Database(1,:);
FamilyLeader = zeros(SearchGroupSize,dim+1);
Indices = transpose(1:1:SearchGroupSize);
TournamentIndices = Tournament(PopulationSize,(SearchGroupSize-elite),TournamentSize);
TournamentIndices = sort(TournamentIndices);
Indices(elite+1:SearchGroupSize) = TournamentIndices(:,1);
for i = 1:SearchGroupSize
Local = Indices(i);
FamilyLeader(i,:) = Database(Local,:);
end
if OFEs>OFELim
break
end
end
% Saves the best design found
Solution(1,:) = IterationData(NIterations,2:dim+1);
bestx=Solution(1,:) ;
% Evaluates the objective function of the best design
MinValue = fobj(Solution);
cg = IterationData(:,1);
%% FINISH the iterative process of SGA
end
end
function [ PerturbedIndices ] = Tournament( PopulationSize,FamilyLeader,TournamentSize )
%% Tournament code
PerturbedIndices = zeros(FamilyLeader,1);
c = zeros(TournamentSize,1);
SearchGroupIndices= transpose(2:1:PopulationSize);
for i=1:FamilyLeader
for j = 1:TournamentSize
c(j)=PopulationSize - ceil((PopulationSize-i)*rand(1));
end
e = SearchGroupIndices(min(c));
SearchGroupIndices(min(c))=0;
SearchGroupIndices=sortrows(SearchGroupIndices);
PerturbedIndices(i,1) = e;
end
end
function [ FamilyLeader, FamilyGroup] = FamilyGeneration( FamilyLeader,SearchGroupSize,lSup,lInf,Alfa,Fobj,v,PlotFamily )
%This function generates a family with size defined in v for each member of the search group and
%chooses the best fit member as its leader for the next iteration.
Dim = length(lSup);
FamilyGroup(1).Min = FamilyLeader(1,2:Dim+1);
FamilyGroup(1).Max = FamilyLeader(1,2:Dim+1);
k = 1;
for i = 1:SearchGroupSize
FamilySize = v(1,i);
Family = zeros(FamilySize+1,Dim+1);
xTemp = zeros(FamilySize,Dim);
Family(1,:) = FamilyLeader(i,:);
xTemp(1:FamilySize,:)= repmat(FamilyLeader(i,2:Dim+1),FamilySize,1)+repmat(Alfa,FamilySize,1).*(rand(FamilySize,Dim)-0.5);
xTemp=max(xTemp,repmat(lInf,FamilySize,1));
xTemp=min(xTemp,repmat(lSup,FamilySize,1));
Family(2:(FamilySize+1),2:(Dim+1)) = xTemp(1:FamilySize,:);
for j = 1:FamilySize
Family(1+j,1) = Fobj(xTemp(j,:));
end
for j=1:FamilySize
if Family(1+j,1) < FamilyLeader(i,1)
FamilyLeader(i,:) = Family(1+j,:);
if PlotFamily
k = j;
end
end
end
if PlotFamily
Family(1+k,:) = Family(1,:);
Family(1,:) = FamilyLeader(i,:);
FamilyGroup(i).Family = Family(2:FamilySize,:);
FamilyGroup(i).Leader = FamilyLeader(i,:);
FamilyGroup(1).Min = min(min(Family(:,2:Dim+1)