Discover MakerZone

MATLAB and Simulink resources for Arduino, LEGO, and Raspberry Pi

Learn more

Discover what MATLAB® can do for your career.

Opportunities for recent engineering grads.

Apply Today

Thread Subject:
Problem with Genetic Algorithm

Subject: Problem with Genetic Algorithm

From: Michael Solis Chacon

Date: 19 Mar, 2009 04:47:01

Message: 1 of 6

Hello everybody,

I'm in an university's project, and i have to program a real genetic algorithm (i.e. I haven't used binary representation). I finished the code, but it doesn't work well.

Does any have a suggestion?

Thanks in advance

You can use the algoritm this

X=[10;20;30;40;]
Y=[0.48;0.42;0.4;0.39;]
cotas= [0,1;0,1] % The bounds for the algorithm

[xMin,valMin,valMed,xPob,no_iter,conv] = AlgGen('prueba', cotas,0.0001, 3000,X,Y)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%%This file is called prueba.m

function [y] = prueba(a,p,s,X)
% p = parametros
% a = el tama�o del paso
% s = la direcc�n mas baja del gradiente
% X = son los datos
dim=size(p,2);
Npar=size(p,1);
Nx=length(X);

p1=repmat(p(:,1)+a*s(1),[1 length(X)]);

p2=repmat(p(:,2)+a*s(2),[1 length(X)]);

Xv=repmat(reshape(X,1,Nx),[Npar 1]);

y=reshape(p1 + (.49-p1).*exp(-(p2) .* (Xv-8)),length(X),Npar);


end

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

%% File named GA.m

function [xMin,valMin,valMed,xPob,no_iter,conv] = AlgGen(fun, cotas,epsilon, max_iter,X,Y)

%% Algoritmo Genetico


%cotas (dim x 2) tiene en la primera columna la cota inferior y en la segunda la cota superior

%% Inicializacion
warning off
dim = size(cotas,2);
Sfun=strcat('S',fun);
s = zeros(dim,1);% vector para la direccion del gradiente
conv = false;

%% Criterio de Parada


%% Variables Algoritmos Genetico
no_iter = 1;
nPob = 50; %Cantidad de poblaci�n
tasamut = 0.1; %Porcentaje de mutacion
tasa_selec = 0.5; %Porcentaje de seleccion
tasa_cruz = 0.5; % Pctj de la poblacion que se cruza
h = [0.1, 0.01]; %Paso para mutar; SE DEBE CAMBIAR SEGUN EL PROBLEMA

%% Numero de sobrevientes, parejas y mutantes

Nvivos = floor(tasa_selec*nPob); % No de miembros que sobreviven
Nmutantes = ceil((nPob-1)*dim*tasamut); % Numero de mutaciones
%Nparejas = floor((nPob-Nvivos)/2); % Numero de emparejamientos
Nparejas = floor((nPob)/2); % Numero de emparejamientos

%% Poblaci�n Inicial

cotaInf=cotas(:,1)';
cotaSup=cotas(:,2)';

xPob=rand(nPob,1)*(cotaSup-cotaInf).*rand(nPob,dim) + ones(nPob,1)*cotaInf;
valSSE=SSE(0,xPob,s,X,Y,fun);

% [valSSE,valSSE_ix] = sort(valSSE); %Best of current pop
% xPob = xPob(valSSE_ix,:);
% MatrizPob=[xPob valSSE]; %Matriz Poblacion

[valMin(no_iter,1) ixmin] = min(valSSE);
xMin(no_iter,:)=xPob(ixmin,:);
valMed(no_iter,1) = mean(valSSE);

while(~conv && no_iter < max_iter)
    
    % Solo quedan la cantidad $Nvivos de individuos y se debe selecionar
    % parejas para rellenar hasta $nPob
    
    clf
    scatter(xPob(:,1),xPob(:,2))
    hold
    scatter(xMin(end,1),xMin(end,2),'MarkerFaceColor','g')
    
    xPob = GeneraHijos(valSSE,xPob,Nparejas,xMin(no_iter,:),tasa_cruz,dim);
        
    %% Mutacion
       
    mfil=sort(ceil(rand(Nmutantes,1)*(nPob-1))+1);
    mcol=ceil(rand(Nmutantes,1)*dim);
    
    % Generar un h para mutar dependiendo del rango. 10%
    for k=1:Nmutantes
        % xPob(mfil(k),mcol(k)) = rand*(cotaSup(mcol(k))-cotaInf(mcol(k)))+ cotaInf(mcol(k));
        xPob(mfil(k),mcol(k)) = xPob(mfil(k),mcol(k)) + h(mcol(k))*rand;
    end
 
    %% Evaluaci�n de la nueva poblaci�n generada y mutada
    
    valSSE=SSE(0,xPob,s,X,Y,fun);
        
    [valMin(no_iter + 1,1) ixmin] = min(valSSE);
    
    xMin(no_iter+1,:)= xPob(ixmin,:);
    
         if valMin(no_iter+1,1) < valMin(no_iter,1)
             valMin(no_iter+1,1)=valMin(no_iter,1);
             xMin(no_iter+1,:)=xMin(no_iter,:);
         end
    
    valMed(no_iter + 1,1) = mean(valSSE);
    
    if no_iter>max_iter || abs(valMin(no_iter))<epsilon
        break
    end
    
    disp([no_iter valMin(no_iter)])
    
    % update iteration count
    no_iter = no_iter + 1;
    
end


function hijos = GeneraHijos(valSSE,xPob,Nparejas,xMin,tasa_cruz,dim)

% Se calcula la probabilidad de selecion dependiendo de su valor en $valSSE
% 1 - Primero se normaliza la funcion SSE = SSE - SSE(Nvivos+1)
% 2 - Luego se calcula la probalidad SSE/sum(SSE,1->Nvivos)

nPob=length(valSSE);
% [valSSE ix]=sort(valSSE);
%
% xPob = xPob(ix,:);

C = max(valSSE)-valSSE(1:end-1);
probSel = C/sum(C);

distSel=[0; cumsum(probSel)]; %distribucion de las probalidades


%% Seleccion para cruzar
pick1 = rand(Nparejas,1);
pick2 = rand(Nparejas,1);

% Incializan los hijos
hijo1 = [];
hijo2 = [];

% ma and pa contiene los indices de los padres
ic=1;
while ic<=Nparejas
    for id=2:nPob % Arreglar con un while
        if pick1(ic)<=distSel(id) && pick1(ic)>distSel(id-1)
            ma(ic,1)=id-1;
        end
        if pick2(ic)<=distSel(id) && pick2(ic)>distSel(id-1)
            pa(ic,1)=id-1;
        end
    end
    ic=ic+1;
end

xPob(pa(1),:) = xMin; % El mejor siempre se selecciona

%% Cruzamiento

%beta es un aleatorio
beta = repmat(rand(Nparejas,1),1,dim);
% beta = rand(Nparejas,dim); % Posible implementacion

ix= rand(Nparejas,1)<= tasa_cruz;

beta = beta .* repmat(ix,1,dim);

hijo1 = xPob(ma,:) + beta .* ( xPob(pa,:)- xPob(ma,:));
hijo2 = xPob(pa,:) + beta .* ( xPob(ma,:)- xPob(pa,:));

hijos = [hijo1 ; hijo2];

% hijo = beta .* xPob(ma,:) + (1-beta) .* xPob(pa,:);
% hijo = beta .* (xPob(ma,:) - xPob(pa,:)) + xPob(ma,:);
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Subject: Problem with Genetic Algorithm

From: Darren Rowland

Date: 19 Mar, 2009 05:00:18

Message: 2 of 6

Michael,
It is highly unlikely that anyone will investigate problems with your code, there is just too much of it. You have not even mentioned what errors you are experiencing.

There are some genetic algorithm implementations on the File Exchange which you should consult. They may give you some idea of how to improve your code.
Darren

Subject: Problem with Genetic Algorithm

From: Michael Solis Chacon

Date: 19 Mar, 2009 05:23:01

Message: 3 of 6

Thanks for your response and sorry for that.

Basically the variable valMin decrease in the first iteration but later it stays constant all the time. In fact, analyzing a little more this variable seems that increase instead of decrease.

I already checked some files in the central files site, but i can't figure out what its wrong with the code.

Very thanks again

Michael

Subject: Problem with Genetic Algorithm

From: Steven Lord

Date: 19 Mar, 2009 13:43:57

Message: 4 of 6


"Michael Solis Chacon" <basu123ra@yahoo.com> wrote in message
news:gpskrl$5mb$1@fred.mathworks.com...
> Thanks for your response and sorry for that.
>
> Basically the variable valMin decrease in the first iteration but later it
> stays constant all the time. In fact, analyzing a little more this
> variable seems that increase instead of decrease.
>
> I already checked some files in the central files site, but i can't figure
> out what its wrong with the code.
>
> Very thanks again
>
> Michael

Sounds like you have some debugging to do. But debugging is a useful skill,
and so the practice will do you good.

Start off with a problem that you've worked out using some other method for
which your code is giving a different answer than you expect. Then set a
breakpoint in your code, run the example, and step through each line of
code, checking what your code is computing against the other method. When
you find a discrepancy, figure out why you're receiving different results.
This may require running through your code several times, but that's okay.
Eventually, one of two things will happen:

1) Your code runs all the way through and gives the same result as you
expect. This is evidence in support of your code being correct -- now try
another example and make sure your code behaves as you expect on that one.

2) You realize that the answer you expected was incorrect and you change
your expectation. Go back to the beginning and check if your code now
agrees with your expectation.

As you get more experienced, you'll come up with your own tricks and
techniques, like setting a breakpoint halfway through your code and using
bisection to locate the source of the discrepancy more quickly, or using
conditional breakpoints, or using things like "DBSTOP IF INFNAN".

You might find this page from the documentation, that describes some of the
diagnostic tools available, to be useful.

http://www.mathworks.com/access/helpdesk/help/techdoc/matlab_env/brqxeeu-147.html

--
Steve Lord
slord@mathworks.com

Subject: Problem with Genetic Algorithm

From: Richard Crozier

Date: 19 Mar, 2009 14:53:01

Message: 5 of 6

If you just need a real valued GA (i.e. the object of the exercise isn't just to show you can develop a GA) I suggest using the free toolbox from the following link:

http://www.shef.ac.uk/acse/research/ecrg/gat.html

It is free and has real-valued representation. It was developed by the evolutionary computing team at the University of Sheffield in the UK. It has worked well for me.

Richard

Subject: Problem with Genetic Algorithm

From: Michael Solis Chacon

Date: 20 Mar, 2009 04:34:01

Message: 6 of 6

Thanks for yours advices

I checked my code and now it maximize (before the idea was to minimize a function, but it's just use the "-f" function), and test the code with the Jong's function

y=0
for i=1:n
  y= y + 100?(x(i+1)-x(i)^2)^2+(1-x(i))^2
  end
%-2.048<=x(i)<=2.048.
%global minimum:
% f(x)=0; x(i)=1, i=1:n.

and works pretty well, look at the results

Value function
http://www.freeimagehosting.net/image.php?294b90d951.jpg

Parametres
http://www.freeimagehosting.net/image.php?be5b2e805c.jpg

Again, very thank you.

Tags for this Thread

What are tags?

A tag is like a keyword or category label associated with each thread. Tags make it easier for you to find threads of interest.

Anyone can tag a thread. Tags are public and visible to everyone.

Contact us