Exemplo de Algoritmo Genético: Balança de dois pratos (com sistema de "idade")

Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original

%Víttor Paulo (R)
%Segunda avaliação de Matemática Aplicada - Algoritmos Genéticos
%Limpeza de variáveis e prompt antes da execução do programa
clear;
clc;
%Importação dos dados (de um arquivo texto, presente na mesma pasta do programa)
Populacao=load('BD balanca.txt');
%______________________________________________________________________________________________________________________________________
%Montagem aleatória da população inicial a partir do banco de dados
N_pop=0; %Variável que comportará o número de indivíduos na população
Repete=1; %Contadores de repetição
Contador=0;
Igualdade=0;
Contador2=1;
[linhas,colunas]=size(Populacao); %Obtenção das dimensões da matriz
N_pop=round(linhas/3); %A população receberá aproximadamente um terço do total de indivíduos do banco de dados (pode ser alterado) (*)
marcador=zeros(N_pop,1); %Vetor para "marcar" indivíduos já escolhidos para a população inicial (não haver escolha repetida)
Pop_def=zeros(N_pop,colunas); %Matriz da população "definitiva"
while Repete==1
 seletor=round(rand*1000); %Seletor de indivíduos para compor a população inicial; escolha aleatória (0<x<1000) (*)
 if (seletor<=linhas)&&(seletor>0) %Se o número do seletor corresponder ao número de algum indivíduo do banco (0<x<=linhas)...
 for Contador=1:length(marcador) %Verificando se o indivíduo sorteado já não foi escolhido, percorrendo o vetor "marcador"
 if seletor==marcador(Contador) 
 Igualdade=Igualdade+1; %Se houver correspondência, a igualdade é detectada
 end
 end
 if Igualdade==0 %Se o indivíduo ainda não foi escolhido...
 marcador(Contador2)=seletor; %O indivíduo é "marcado"
 Pop_def(Contador2,1:colunas)=Populacao(seletor,1:colunas); %A população "definitiva" receberá o respectivo indivíduo
 Contador2=Contador2+1; %Variação do contador (próxima linha/casa a ser preenchida)
 end
 end
 Igualdade=0; %Reiniciando o contador de igualdade
 if Contador2>N_pop %Quando o contador extrapolar o limite de casas/linhas, parar a repetição
 Repete=0;
 end
end
%______________________________________________________________________________________________________________________________________
%Evolução da população (padrão utilizado para parada: Número de balanças em equilíbrio>95%, ou 400 gerações) (*)
%Análise da população de balanças (em equilíbrio ou pendendo para um lado)
%Total de 4 atributos: pesos e comprimento de cada braço
%Atributos adicionais: classificação da balança (em equilíbrio ou pendendo para um lado);
% "idade" da balança (descarte AUTOMÁTICO após 10 "gerações") (*)
Contador=0; %Reiniciando os contadores
Contador2=0;
num_equil=0; %Variável para o número de balanças em equilíbrio
Vetor_categ=sym(zeros(N_pop,1)); %Vetor auxiliar (categorias)
Vetor_idade=zeros(N_pop,1); %Vetor auxiliar ("idade")
eixo_x=[]; %Variáveis para plotagem do gráfico (número de balanças equilibradas em cada geração)
eixo_y=[]; %Valor absoluto
eixo_y2=[]; %Valor em porcentagem
num_equil=0; %Variável que receberá a quantidade de balanças equilibradas em cada geração
%Cálculos para o instante inicial (população inicial)
for Contador=1:N_pop %Atribuição das "letras"
 torque_esq=Pop_def(Contador,1)*Pop_def(Contador,2); %Cálculo do torque no lado esquerdo
 torque_dir=Pop_def(Contador,3)*Pop_def(Contador,4); %Cálculo do torque no lado direito
 if abs(torque_esq-torque_dir)<=0.001 %Se a diferença não for perceptível
 Vetor_categ(Contador)=sym('B'); %Equilíbrio
 else if torque_esq<torque_dir
 Vetor_categ(Contador)=sym('R'); %Pende para a direita
 else
 Vetor_categ(Contador)=sym('L'); %Pende para a esquerda
 end
 end
end
for Contador=1:N_pop %Contagem de balanças em equilíbrio
 if Vetor_categ(Contador)=='B'
 num_equil=num_equil+1;
 end
end
 
prop_eq=num_equil/N_pop; %Obtenção da proporção
Pop_real=[Pop_def Vetor_idade]; %População com idade
num_ger=0; %Variável que contém o número da geração; inicia-se com zero (população inicial)
eixo_x=[eixo_x num_ger]; %Atribuição de valores para as variáveis do gráfico
eixo_y=[eixo_y num_equil];
eixo_y2=[eixo_y2 prop_eq];
disp('População original:'); %Mostrar no prompt a população inicial na forma de matriz (*)
disp(Pop_real);
%______________________________________________________________________________________________________________________________________
%Primeira geração em diante
while (prop_eq<=0.95)&&(num_ger<400) %Repetir até atingir uma das condições de parada
 
 
 %"Envelhecimento" da população e eliminação automática (*)
 Pop_real(1:N_pop,5)=Pop_real(1:N_pop,5)+1;
 for Contador=1:N_pop %Organização da matriz em ordem crescente de idade
 for Contador2=(Contador+1):N_pop
 if Pop_real(Contador,5)>Pop_real(Contador2,5)
 vetor_armaz= Pop_real(Contador,1:5); %Vetor auxiliar para evitar a perda de dados
 Pop_real(Contador,1:5)=Pop_real(Contador2,1:5);
 Pop_real(Contador2,1:5)=vetor_armaz;
 end
 end
 end
 Vetor_idade=Pop_real(1:N_pop,5); %Atualização do vetor idade
 Ponto_corte=max(find(Vetor_idade<10)); %Encontro do último indivíduo a não ultrapassar 10 gerações (novo limite da pop.)
 Pop_real=Pop_real(1:Ponto_corte,1:5); %Eliminação (corte da matriz)
 
 %Cálculo do fitness (aptidão)
 torque_esq=Pop_real(1:Ponto_corte,1).*Pop_real(1:Ponto_corte,2); %Cálculo do torque em cada lado (peso*comprimento do braço)
 torque_dir=Pop_real(1:Ponto_corte,3).*Pop_real(1:Ponto_corte,4);
 fitness=zeros(Ponto_corte,1); %Vetor para os valores do fitness de cada indivíduo
 for Contador=1:Ponto_corte %O fitness será dado pela proporção entre o menor e o maior torque;
 %E também em relação à proporção entre os braços da balança ((Tmin/Tmax)*(Lmin/Lmax))
 if torque_dir(Contador)>torque_esq(Contador) %Detecção do maior torque e montagem da proporção
 fitness(Contador)=torque_esq(Contador)/torque_dir(Contador);
 else
 fitness(Contador)=torque_dir(Contador)/torque_esq(Contador);
 end
 if Pop_real(Contador,2)>Pop_real(Contador,4) %Detecção do maior braço e montagem da segunda proporção
 fitness(Contador)=fitness(Contador)*Pop_real(Contador,4)/Pop_real(Contador,2);
 else
 fitness(Contador)=fitness(Contador)*Pop_real(Contador,2)/Pop_real(Contador,4);
 end
 end
 matriz_cruza=[Pop_real fitness]; %Matriz composta dos indivíduos e respectivos fitness 
 for Contador=1:Ponto_corte %Organização da matriz em ordem decrescente de fitness
 for Contador2=(Contador+1):Ponto_corte
 if matriz_cruza(Contador,6)<matriz_cruza(Contador2,6)
 vetor_armaz= matriz_cruza(Contador,1:6); %Vetor para auxiliar a troca (não haver perda de dados)
 matriz_cruza(Contador,1:6)=matriz_cruza(Contador2,1:6);
 matriz_cruza(Contador2,1:6)=vetor_armaz;
 end
 end
 end
 
 %Eliminação dos menos aptos
 selec_neg=round(0.2*Ponto_corte); %Os 20% menos aptos (aproximadamente) serão eliminados (*)
 matriz_selec=matriz_cruza(1:(Ponto_corte-selec_neg),1:6); %Indivíduos selecionados (corte da matriz)
 fitness=matriz_selec(1:length(matriz_selec),6); %Atualização do vetor fitness
 [num_selec,Aux]=size(matriz_selec); %Obtenção do número de indivíduos restantes
 Deficit=N_pop-num_selec; %Obtenção da quantidade de indivíduos que precisam ser gerados
 
 %Geração de novos indivíduos
 Contador3=0; %Variável contador de repetição
 chance_crossover=0.7; %Probabilidade de
crossover (recombinar os atributos dos modelos) (*)
 chance_mutacao=0.005; %Probabilidade de "mutação" (erro de montagem) (*)
 
 while Contador3<Deficit %Repetir até gerar todos os indivíduos necessários
 modelo1=0; %Seleção do primeiro "pai"
 while modelo1==0
 indice=0;
 while indice==0 %Escolha aleatória dentro da população
 indice=round(rand*1000);
 if indice>num_selec %O índice escolhido não pode ultrapassar o tamanho da população
 indice=0; %Refazer a escolha
 end
 end
 modelo1=matriz_selec(indice,1:6); %O primeiro "pai" é escolhido
 if rand>modelo1(6) %Verificando se o fitness permitirá a reprodução
 modelo1=0; %Se não, refazer a escolha
 end
 dif=indice; %Armaz. do índice do primeiro modelo
 end
 modelo2=0; %Seleção do segundo "pai"
 while modelo2==0
 indice=0;
 while indice==0 %Escolha aleatória dentro da população
 indice=round(rand*1000);
 if (indice>num_selec)||(indice==dif) %O índice escolhido não pode ultrapassar o tamanho da população
 %Impedir que o segundo modelo coincida com o primeiro
 indice=0; %Refazer a escolha
 end
 end
 modelo2=matriz_selec(indice,1:6); %O segundo "pai" é escolhido
 if rand>modelo1(6) %Verificando se o fitness permitirá a reprodução
 modelo2=0; %Se não, refazer a escolha
 end
 end
 %Chance de mutação (para cada atributo)
 for mut=1:4 %Primeiro modelo
 if rand<=chance_mutacao
 modelo1(mut)=round(rand*5); %Valor aleatório entre 0 e 5
 end
 end
 for mut=1:4 %Segundo modelo
 if rand<=chance_mutacao %Se o valor aleatório for menor/igual à taxa de mutação
 modelo2(mut)=round(rand*5); %Valor aleatório entre 0 e 5
 end
 end
 
 %Chance de crossover entre os modelos (para cada atributo)
 for cross=1:4 %Contador
 if rand<=chance_crossover %Se o valor aleatório for menor/igual à taxa de crossover
 intermed=modelo1(cross); %Troca dos valores
 modelo1(cross)=modelo2(cross);
 modelo2(cross)=intermed;
 end
 end
 %Novos indivíduos (2 por "casal" de modelos)
 novo1=[modelo1(1:4) 0 0]; %Os zeros correspondem à idade do novo indivíduo e ao fitness (ainda não testado)
 novo2=[modelo2(1:4) 0 0];
 novo=[novo1;novo2]; %Juntando os dois em uma única matriz
 
 for Aux=1:2 %Calculando o fitness dos novos indivíduos
 torque_esq=novo(Aux,1)*novo(Aux,2); %Cálculo do torque em cada lado
 torque_dir=novo(Aux,3)*novo(Aux,4);
 if torque_dir>torque_esq %Em função do torque
 novo(Aux,6)=torque_esq/torque_dir;
 else
 novo(Aux,6)=torque_dir/torque_esq;
 end
 if novo(Aux,2)>novo(Aux,4) %Em função do comprimento dos braços
 novo(Aux,6)=novo(Aux,6)*novo(Aux,4)/novo(Aux,2);
 else
 novo(Aux,6)=novo(Aux,6)*novo(Aux,2)/novo(Aux,4);
 end
 end
 matriz_selec=[matriz_selec;novo];%Juntando os novos indivíduos à população
 fitness=[fitness;novo(1:2,6)]; %Atualização do vetor fitness
 Contador3=Contador3+2;
 end
 %Retomando a população e eliminando excesso de "filhotes" (o número de
 %novos indivíduos gerados pode ter ultrapassado o limite estabelecido)
 Pop_real=matriz_selec(1:N_pop,1:5); %Recuperando os atributos e a idade de cada indivíduo, respeitando o limite populacional
 num_equil=0; %Reiniciando o contador
 for Contador=1:N_pop %Atribuição das "letras"
 torque_esq=Pop_real(Contador,1)*Pop_real(Contador,2); %Cálculo do torque no lado esquerdo
 torque_dir=Pop_real(Contador,3)*Pop_real(Contador,4); %Cálculo do torque no lado direito
 if abs(torque_esq-torque_dir)==0 %Se a diferença não for perceptível
 Vetor_categ(Contador)=sym('B'); %Equilíbrio ("Balanced")
 else if torque_esq<torque_dir
 Vetor_categ(Contador)=sym('R'); %Pende para a direita ("Right")
 else
 Vetor_categ(Contador)=sym('L'); %Pende para a esquerda ("Left")
 end
 end
 
 end
 for Contador=1:N_pop %Contagem de balanças em equilíbrio
 if Vetor_categ(Contador)=='B'
 num_equil=num_equil+1;
 end
 end
 
 prop_eq=num_equil/N_pop; %Obtenção da proporção
 num_ger=num_ger+1; %Atualizando a geração
 
 eixo_x=[eixo_x num_ger]; %Atribuição de valores para as variáveis do gráfico
 eixo_y=[eixo_y num_equil];
 eixo_y2=[eixo_y2 prop_eq]; 
 
% disp('Geração atual:'); %Exibição do número da geração atual e da respectiva população no prompt
% disp(num_ger);
% disp('População atual:');
% disp(Pop_real);
end 
%Explicação das matrizes apresentadas no prompt
disp('Legenda da população:')
disp('Coluna 1: peso no lado esquerdo');
disp('Coluna 2: comprimento do braço esquerdo');
disp('Coluna 3: peso no lado direito');
disp('Coluna 4: comprimento do braço direito');
disp('Coluna 5: idade da balança');
%Orientação para visualização das variáveis
disp('Fitness da população: var. "fitness"');
disp('População atual: var. "Pop_real"');
disp('Porcentagem em eq.: var. "prop_eq"');
clf; %Limpa a janela do gráfico
%Plotagem dos gráficos quantidade x gerações (valores absolutos e porcentagem)
subplot(121),plot(eixo_x,eixo_y,'b'),title('Quantidade de balanças em equilíbrio, ao longo das gerações'),xlabel('Número da geração'),ylabel('Quantidade de balanças equilibradas'),grid;
subplot(122),plot(eixo_x,eixo_y2,'black'),title('Proporção de balanças em equilíbrio, ao longo das gerações'),xlabel('Número da geração'),ylabel('Proporção de balanças equilibradas'),grid;