Problema Da Caixa Preta Doc Final 44l2x
This document was ed by and they confirmed that they have the permission to share it. If you are author or own the copyright of this book, please report to us by using this report form. Report 3b7i
Overview 3e4r5l
& View Problema Da Caixa Preta Doc Final as PDF for free.
More details w3441
- Words: 3,833
- Pages: 41
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Problema da caixa preta
Disciplina: Computação evolucionaria Professor: Bruno Henrique Groenner Barbosa Aluno: Elson Claudio Correa Moraes
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas 1. Introdução 1.1 Algoritmos Genéticos Um algoritmo
genético (AG)
é
uma técnica de
busca
utilizada
na ciência
da
computação para achar soluções aproximadas em problemas de otimização e busca, fundamentado principalmente pelo americano John Henry Holland. Algoritmos genéticos são uma classe particular de algoritmos evolutivos que usam técnicas inspiradas
pela biologia
evolutiva como
hereditariedade, mutação, seleção
natural e recombinação. Algoritmos genéticos são implementados como uma simulação de computador em que uma população de representações abstratas de solução é selecionada em busca de soluções melhores. A evolução geralmente se inicia a partir de um conjunto de soluções criado aleatoriamente e é realizada por meio de gerações. A cada geração, a adaptação de cada solução na população é avaliada, alguns indivíduos são selecionados para a próxima geração, e recombinados ou mutados para formar uma nova população. A nova população então é utilizada como entrada para a próxima iteração do algoritmo.
1.2 O problema da caixa preta O problema consistem em encontrar a melhor configuração para um conjunto de 9 (a) botões que estão disponíveis em uma caixa, sendo que cada botão pode assumir 16 posições distintas(b) Para representar a posição de cada botão no algoritmo, cada posição do botão é representando com um conjunto de 4 bits (c) e cada individuo (cromossomo) é representado pela disposição destes 9 botões, portanto 36 bits.
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Representação para cada posição dos botões da caixa preta (c) 2. Codificação O trabalho pratico foi desenvolvido utilizando a ferramenta Matlab 8.0.0.783 (R2012b) 32 bits. O trabalho foi organizado em funções e um corpo principal para a chamada das funções chamado BlackBox.m. 2.1 Populações iniciais e avaliação dos indivíduos A população inicial foi gerada no próprio main(BlackBox.m) em seguida é chamada a função avalia.m para geração da avaliação de cada individuo de acordo com a função abaixo: sinalDeSaida = 9+(teta(2)*teta(5))-(teta(23)*teta(14))+... (teta(24)*teta(4))-(teta(21)*teta(10))+(teta(36)*teta(15))-... (teta(11)*teta(26))+(teta(16)*teta(17))+(teta(3)*teta(33))+... (teta(28)*teta(19))+(teta(12)*teta(34))-(teta(31)*teta(32))-... (teta(22)*teta(25))+(teta(35)*teta(27))-(teta(29)*teta(7))+... (teta(8)*teta(13))-(teta(6)*teta(9))+(teta(18)*teta(20))-... (teta(1)*teta(30))+(teta(23)*teta(4))+(teta(21)*teta(15))+... (teta(26)*teta(16))+(teta(31)*teta(12))+(teta(25)*teta(19))+... (teta(7)*teta(8))+(teta(9)*teta(18))+(teta(1)*teta(33));
Sendo teta a posição do bit dentro do indivíduo (36 bits) 2.2 Seleções dos indivíduos Os métodos de seleção dos indivíduos para cruzamento foram implementadas nas funções roleta.m e sel_torneio.m. a- Seleção por roleta viciada cada indivíduo da população é representado na roleta de forma proporcionalmente ao seu valor de aptidão. b- Seleção por torneio: Em cada sorteio, dois indivíduos são escolhidos aleatoriamente, e o melhor deles é selecionado para a próxima geração 2.3 Operadores genéticos Após a seleção dos individuos os mesmos vão cruzar entre si, gerando assim novos individuos. Foram adotados dois meios de cruzamento: Uniforme e ponto de corte,
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas respectivamente
implementados
pelas
funções
cruzamento_uniforme
e
cruzamento_corte.m. a- Cruzamento uniforme - Dois indivíduos (pais) são selecionados aleatoriamente e os indivíduos filhos são gerados com base em uma máscara de bit.
b- Ponto de Corte: São selecionados dois indivíduos (pais) que dão origem a dois novos indivíduos (filhos). Um ponto de corte é escolhido aleatoriamente nos pais e as partes separadas por esse ponto são trocadas.
2.4 Mutação A mutação é muito importante para prevenir a convergência para um maximo local. Na figura abaixo o objetivo da mutação é a de evitar que o algoritmo ita que o ponto C é uma Maximo global, realizando a mutação teremos maiores chances de encontrar o real maximo global (Ponto A).
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
A mutação é feia pelas funções mutação_escolha_bit.m e mutação_bit_bit.m. a) Escolha aleatória do bit: Em cada indivíduo, um bit é escolhido aleatoriamente e o seu valor é invertido. Esse operador é aplicado em todos os indivíduos da população e a mutação ocorre de acordo com a taxa de mutação definida. b) Mutação bit a bit: A mutação ocorre bit a bit segundo uma probabilidade (taxa de mutação). A mutação bit a bit é aplicada em todos os indivíduos da população.
2.5 Elitismo O elitismo ocorre na função comelitismo.m e tem como objetivo preservar os melhores indivíduos da geração, de forma que o melhor indivíduo de uma geração sempre é ado para a geração seguinte.
2.6 Apresentação dos Resultados A apresentação dos resultados obtidos pelo Algoritmo Genético é feita no script principal
BlackBox.m. A cada N* execuções são apresentados o número de
sucessos, o maior valor de fitness, o menor valor de fitness, a média, o desvio padrão,
e
o
boxplot
dos
valores
de
fitness.
É
apresentado
também
o
histograma dos melhores indivíduos. *Valor de N a ser definido no programa 3 Testes e analise dos resultados 3.1 Primeiro teste: Para o primeiro teste, o algoritmo foi executado com a seguinte configuração de parâmetros e foi utilizado o cruzamento com um ponto de corte e o cruzamento uniforme:
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas a) Sem elitismo. b) Seleção por roleta. c) Mutação bit a bit. d) Probabilidade de cruzamento: 0,8. e) Probabilidade de mutação: 0,025. f) Número de indivíduos da população: 30. g) Número de gerações: 50. Utilizando ponto de corte temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 23 Menor Fitness (Pior caso): 18 Valor médio de Fitness: 21,14 Desvio-padrão dos valores de Fitness: 1.37
Fig.1 Box-Plot utilizando ponto de corte
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.2 Histograma utilizando ponto de corte
Utilizando cruzamento uniforme temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 23 Menor Fitness (Pior caso): 15 Valor médio de Fitness: 20,34 Desvio-padrão dos valores de Fitness: 2.48
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.3 Box-Plot utilizando cruzamento uniforme
Fig.4 Histograma utilizando cruzamento uniforme
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas 3.2. Segundo Teste: Avaliação do Efeito do Tipo de Seleção. Para o segundo teste foi utilizado a seguinte configuração de parâmetros, variando-se apenas o tipo de seleção: a) Sem elitismo. b) Cruzamento Uniforme. c) Mutação bit a bit. d) Probabilidade de cruzamento: 0,8. e) Probabilidade de mutação: 0,025. f) Número de indivíduos da população: 30. g) Número de gerações: 50. Utilizando seleção por roleta temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 26 Menor Fitness (Pior caso): 16 Valor médio de Fitness: 23,70 Desvio-padrão dos valores de Fitness: 2,48
Fig.5 Box-Plot utilizando seleção roleta
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.6 Histograma utilizando seleção roleta
Utilizando seleção por torneio temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 16 Menor Fitness (Pior caso): 11 Valor médio de Fitness: 11,30 Desvio-padrão dos valores de Fitness: 1,01
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.7 Box-Plot utilizando seleção torneio
Fig.8 Histograma utilizando seleção torneio
3.3. Terceiro Teste: Avaliação do Efeito do Tipo de Mutação Para avaliar o efeito do tipo de mutação, o algoritmo foi executado utilizando a configuração abaixo: a) Sem elitismo.
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas b) Cruzamento Uniforme. c) Seleção por Roleta. d) Probabilidade de cruzamento: 0,8. e) Probabilidade de mutação: 0,025. f) Número de indivíduos da população: 30. g) Número de gerações: 50.
Utilizando mutação bit a bit temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 21 Menor Fitness (Pior caso): 16 Valor médio de Fitness: 19.16 Desvio-padrão dos valores de Fitness: 1.16
Fig.9 Box-Plot utilizando mutação bit a bit
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.10 Histograma utilizando mutação bit a bit
Utilizando mutação aleatória de bit temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 23 Menor Fitness (Pior caso): 16 Valor médio de Fitness: 21.20 Desvio-padrão dos valores de Fitness: 2,02
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.11 Box-Plot utilizando mutação aleatória de bit
Fig.12 Histograma utilizando mutação aleatória de bit
3.4. Quarto Teste: Avaliação do Efeito da Probabilidade de Cruzamento Foram realizados três testes, variando o valor dessa probabilidade e mantendo fixos todos os outros parâmetros. Foram utilizados os valores de parâmetros a seguir e os valores utilizados para a taxa de cruzamento foram 0,2, 0,5 e 0,8:
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas a) Sem elitismo. b) Cruzamento Uniforme c) Seleção por Roleta d) Mutação por escolha aleatória do bit e) Probabilidade de mutação: 0,025. f) Número de indivíduos da população: 30. g) Número de gerações: 50.
Utilizando a taxa de cruzamento igual a 0,8 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 24 Menor Fitness (Pior caso): 15 Valor médio de Fitness: 21,08 Desvio-padrão dos valores de Fitness: 2.73
Fig.13 Box-Plot utilizando taxa de cruzamento 0,8
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.14 Histograma utilizando taxa de cruzamento 0,8 Utilizando a taxa de cruzamento igual a 0,5 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 25 Menor Fitness (Pior caso): 15 Valor médio de Fitness: 20.17 Desvio-padrão dos valores de Fitness: 1.9125
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.15 Box-Plot utilizando taxa de cruzamento 0,5
Fig.16 Histograma utilizando taxa de cruzamento 0,5
Utilizando a taxa de cruzamento igual a 0,2 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 21
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas Menor Fitness (Pior caso): 15 Valor médio de Fitness: 18,90 Desvio-padrão dos valores de Fitness: 1,85
Fig.17 Box-Plot utilizando taxa de cruzamento 0,2
Fig.18 Histograma utilizando taxa de cruzamento 0,2
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas 3.5. Quinto Teste: Avaliação do Efeito da Probabilidade de Mutação Para analisar o efeito da probabilidade de mutação foi fixado os parâmetros variandose apenas as taxas de mutações. Foram realizados quatro testes, os valores para a taxa de mutação foram: 0,05, 0,1, 0,25 e 0,75, respectivamente. Foi assumido os seguintes parâmetros: a) Sem elitismo. b) Cruzamento uniforme c) Seleção por Roleta d) Mutação por escolha aleatória do bit e) Probabilidade de cruzamento: 0.8 f) Número de indivíduos da população: 30. g) Número de gerações: 50.
Utilizando a taxa de mutação igual a 0,05 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 21 Menor Fitness (Pior caso): 16 Valor médio de Fitness: 18,48 Desvio-padrão dos valores de Fitness: 1,21
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.19 Box-Plot utilizando taxa de mutação 0,05
Fig.20 Histograma utilizando taxa de mutação 0,05
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas Utilizando a taxa de mutação igual a 0,1 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 21 Menor Fitness (Pior caso): 15 Valor médio de Fitness: 19,16 Desvio-padrão dos valores de Fitness: 1,43
Fig.21 Box-Plot utilizando taxa de mutação 0,1
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.22 Histograma utilizando taxa de mutação 0,1
Utilizando a taxa de mutação igual a 0,25 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 23 Menor Fitness (Pior caso): 17 Valor médio de Fitness: 20,72 Desvio-padrão dos valores de Fitness: 1,81
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.23 Box-Plot utilizando taxa de mutação 0,25
Fig.24 Histograma utilizando taxa de mutação 0,25
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas Utilizando a taxa de mutação igual a 0,75 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 23 Menor Fitness (Pior caso): 17 Valor médio de Fitness: 21,34 Desvio-padrão dos valores de Fitness: 1.86
Fig.25 Box-Plot utilizando taxa de mutação 0,75
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.26 Histograma utilizando taxa de mutação 0,75 3.6. Sexto Teste: Avaliação do Efeito do Elitismo Para avaliar os efeitos causados pelo processo de elitismo, foi utilizada a configuração abaixo e o algoritmo foi testado com e sem a aplicação do elitismo. a) Cruzamento Uniforme b) Seleção por Roleta c) Mutação por escolha aleatória do bit d) Probabilidade de cruzamento: 0.8 e) Probabilidade de mutação: 0.75 f) Número de indivíduos da população: 30. g) Número de gerações: 50. Sem a utilização de elitismo: Número de Sucessos: 0 Maior Fitness (Melhor caso): 21 Menor Fitness (Pior caso): 16 Valor médio de Fitness: 19,58 Desvio-padrão dos valores de Fitness: 1.18
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.27 Box-Plot sem elitismo
Fig.28 Histograma sem elitismo Utilizando elitismo temos: Número de Sucessos: 12 Maior Fitness (Melhor caso): 27 Menor Fitness (Pior caso): 16
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas Valor médio de Fitness: 23,78 Desvio-padrão dos valores de Fitness: 3,39
Fig.29 Box-Plot com elitismo
Fig.30 Histograma com elitismo
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas 3.7 Avaliação final Após a realização dos testes acima vemos que a melhor parametrização do algoritmo é: a) Cruzamento Uniforme b) Seleção por Roleta c) Mutação por escolha aleatória do bit d) Probabilidade de cruzamento: 0.8 e) Probabilidade de mutação: 0.05 f) Com elitismo Concluímos que ao aumentar o numero de indivíduos aumentamos a chances de obter um individuo ótimo, alem disso a chance de se obter um individuo ótimo sob exponencialmente ao se aumentar o numero de gerações e indivíduos conforme mostrado na tabela 5 e na figura 31.
Fig.31 Histograma com 800 gerações e 240 indivíduos
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
TESTE
TESTE 1 TESTE 2 TESTE 3
TESTE 4
TESTE 5 TESTE 6
N ELISTISMO SELEÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO SIM
ROLETA ROLETA ROLETA TORNEIO ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA
CRUZAMENTO PONTO DE CORTE UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME
MUTAÇÃO
TC
TM
N° IND
N° GERAÇÃO
BIT A BIT BIT A BIT BIT A BIT BIT A BIT BIT A BIT ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO
0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,5 0,2 0,8 0,8 0,8 0,8 0,8 0,8
0,025 0,025 0,025 0,025 0,025 0,025 0,025 0,025 0,025 0,05 0,1 0,25 0,75 0,75 0,75
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
Tabela 2: Parâmetros utilizados
TESTE TESTE 1 TESTE 2 TESTE 3
TESTE 4
TESTE 5 TESTE 6
N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
N° DE SUCESSO 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12
MAIOR FITNESS 23 23 26 16 21 23 24 22 21 21 21 23 23 21 27
MENOR FITNESS 18 15 16 11 16 16 15 16 15 16 15 17 17 16 16
Tabela 3: Resultados
FITNESS MÉDIO DESVIO PADRÃO 21,14 1,37 20,34 2,48 23,7 2,58 11,3 1,01 19,16 1,16 21,2 2,02 21,08 2,73 19,5 1,47 18,9 1,85 18,48 1,21 19,16 1,43 20,72 1,81 21,34 1,86 19,58 1,18 23,78 3,39
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
TESTE ELISTISMO TESTE 1 SIM TESTE 2 SIM TESTE 3 SIM TESTE 4 SIM TESTE 5 SIM TESTE 6 SIM TESTE 7 SIM TESTE 8 SIM TESTE 9 SIM TESTE 10 SIM
SELEÇÃO ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA
CRUZAMENTO UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME
MUTAÇÃO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO
TC 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8
TM 0,75 0,75 0,75 0,75 0,75 0,75 0,75 0,75 0,75 0,75
N° IND 60 120 240 30 30 30 30 60 120 240
N° GERAÇÃO 50 50 50 100 200 400 800 200 400 800
Tabela 4: Parâmetros com variações n° de indivíduos e n° de gerações
TESTE TESTE 1 TESTE 2 TESTE 3 TESTE 4 TESTE 5 TESTE 6 TESTE 7 TESTE 8 TESTE 9 TESTE 10
N° DE SUCESSO 0 12 16 0 0 0 0 0 357 769
MAIOR FITNESS 24 27 27 26 23 25 23 26 27 27
MENOR FITNESS 16 16 18 16 16 17 16 17 18 17
FITNESS MÉDIO DESVIO PADRÃO 21,46 2,177 24,5 2,28 23,76 2,83 24,8 2,45 22,5 1,54 24,87 0,71 22,87 0,79 25,46 1,52 26,63 1,29 26,83 0,99
Tabela 5: Resultados com variações n° de indivíduos e n° de gerações
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.32 Dados função anova1
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.33 Box-Plot com a função anova1
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.34 Box-Plot com a função anova1
pop_size num_ger numero de loops N valor medio fitness 60 75 125 25,89 120 75 125 26,73 120 250 125 26,8 600 250 125 27 Menor fitness Maior fitness Numero de sucesso 23 27 37 25 27 93 25 27 102 27 27 125
desvio padrao fitness 0,9 0,4604 0,4154 0
Tabela 6: Dados utilizados na função anova1
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas 3.8 Código fonte do programa Main – BlackBox.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== clear all close all clc % ===================================================================== % Configuracoes iniciais pcross = 0.8; % porcentagem de cruzamento taxaMutacao = 0.05; % porcentagem de mutação popsize = 60; % numero de individuos N = 125; % Rodar N vezes; num_ger= 75;% numero de gerações nbits=4; % numero de bits em cada cromossomo tam_ind=36; tipo_selecao = 0; % 0 - roleta; 1 - torneio elitismo=1;% 0 sem elitismo 1 com elitismo tipo_mutacao = 0; % 0 - escolha aleatoria de bit; 1 - bit a bit tipo_cruzamento = 1; % 0 - um ponto de corte; 1 - uniforme
for rodar = 1:N pop=round(rand(popsize,tam_ind)); % random da população de 1s e 0s for i=1:popsize vetorAvaliacao(i) = avalia(pop(i,1:tam_ind)); % somatorio das avaliações
end
for k=1:num_ger for i=1:popsize vetorAvaliacao(i) = avalia(pop(i,1:tam_ind)); % somatorio das avaliações
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
end if tipo_selecao == 0 % roleta selecionados = roleta(vetorAvaliacao,popsize); else % torneio selecionados = sel_torneio(vetorAvaliacao); end
% Cruzamento
if tipo_cruzamento == 0 % um ponto de corte filhos = cruzamento_corte(pop,selecionados,pcross);
end if tipo_cruzamento == 1% uniforme mascara = round(rand(popsize/2,tam_ind)); filhos = cruzamento_uniforme(pop,selecionados,tam_ind,popsize,mascara,pcross); end if tipo_mutacao == 0 %0 - escolha aleatoria mutacao_escolha_bit(filhos,taxaMutacao,popsize); else % 1 - bit a bit mutacao_bit_bit (filhos,taxaMutacao,popsize,tam_ind); end if elitismo == 1 filhos = comelistismo(popsize,pop,filhos,vetorAvaliacao); end
Melhor_Ind(rodar) = max(vetorAvaliacao); pop = filhos;
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
end end Valor_medio_fitness=mean(Melhor_Ind) desvio_pad_fitness=std(Melhor_Ind) ll=sort(Melhor_Ind); Menor_Fitness=(ll(1)) Maior_Fitness=(ll(N)) pp=0; for hh=1:N if Melhor_Ind(hh)==27 pp=pp+1; else pp=pp; end end Num_Sucesso=PP % % % % % %
Criar Estatisticas Melhor Avaliação no Teste Pior Avaliacao no Teste Media Avaliacao no Teste Desvio Padrão da Avaliacao Box-Plot
% Num_Sucesso=pp % boxplot(Melhor_Ind) % hist(Melhor_Ind)
% Funcao ANOVA %teste0=Melhor_Ind1'; %teste1=Melhor_Ind2'; %teste2=Melhor_Ind3'; %teste3=Melhor_Ind4';
%zz=[teste0 teste1 teste2 teste3]; % [p,table,st]=anova1(zz); % [c,m,nms]=multcompare(st); Função Avalia.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas % ALUNO:Elson Claudio Correa Moraes %=================================================================== % função avaliar individuo function sinalDeSaida = avalia( teta )
sinalDeSaida = 9+(teta(2)*teta(5))-(teta(23)*teta(14))+... (teta(24)*teta(4))-(teta(21)*teta(10))+(teta(36)*teta(15))-... (teta(11)*teta(26))+(teta(16)*teta(17))+(teta(3)*teta(33))+... (teta(28)*teta(19))+(teta(12)*teta(34))-(teta(31)*teta(32))-... (teta(22)*teta(25))+(teta(35)*teta(27))-(teta(29)*teta(7))+... (teta(8)*teta(13))-(teta(6)*teta(9))+(teta(18)*teta(20))-... (teta(1)*teta(30))+(teta(23)*teta(4))+(teta(21)*teta(15))+... (teta(26)*teta(16))+(teta(31)*teta(12))+(teta(25)*teta(19))+... (teta(7)*teta(8))+(teta(9)*teta(18))+(teta(1)*teta(33));
Função cruzamento_corte.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== %função cruzamento com 1 ponto de corte function filhos = cruzamento_corte(pop,selecionados,pcross) for i = 1:length(selecionados)/2
if rand
end
Função cruzamento_uniforme.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== %função cruzamento uniforme function filhos = cruzamento_uniforme(pop,selecionados,tam_ind,popsize,mascara,pcross)
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
%Cruzamento Uniforme
for i=1:popsize/2 % fazer so a metade tam_pop/2, use a mesma mascara para criar dois filhos
for j=1:tam_ind
if mascara(i,j)==0 && rand
else filhos(2*i,j) = pop(selecionados(2*i-1),j); filhos(2*i-1,j)= [pop(selecionados(2*i),j)];
end end end
end
Função roleta.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== %função roleta viciada function selecionados = roleta( vetorAvaliacao,popsize ) soma = sum(vetorAvaliacao); for k = 1:popsize s = rand*soma;
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas i = 1; aux = vetorAvaliacao(1); while aux<s i = i + 1; aux = aux + vetorAvaliacao(i); end selecionados(k) = i; end end
Função mutação_escolha_bit.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== %Função para para mutar individuo escolha aleatoria de bit function
filhos = mutacao_escolha_bit(filhos,taxaMutacao,popsize)
for i=1:popsize for j=ceil(rand*34 + 0.1) if rand
end
Função mutação_bit_bit.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %===================================================================
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas %Função para para mutar individuo bit a bit function
filhos = mutacao_bit_bit(filhos,taxaMutacao,popsize,tam_ind)
for i=1:popsize for j=1:tam_ind if rand
end
Função sel_torneio.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== % Funcao Torneio function selecionados = sel_torneio(vetorAvaliacao)
for i = 1:length(vetorAvaliacao) d=ceil(rand*29 + 0.1); if vetorAvaliacao(i)
end
Função comelitismo.m %===================================================================
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== % Funcao Torneio function selecionados = sel_torneio(vetorAvaliacao)
for i = 1:length(vetorAvaliacao) d=ceil(rand*29 + 0.1); if vetorAvaliacao(i)
end
Problema da caixa preta
Disciplina: Computação evolucionaria Professor: Bruno Henrique Groenner Barbosa Aluno: Elson Claudio Correa Moraes
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas 1. Introdução 1.1 Algoritmos Genéticos Um algoritmo
genético (AG)
é
uma técnica de
busca
utilizada
na ciência
da
computação para achar soluções aproximadas em problemas de otimização e busca, fundamentado principalmente pelo americano John Henry Holland. Algoritmos genéticos são uma classe particular de algoritmos evolutivos que usam técnicas inspiradas
pela biologia
evolutiva como
hereditariedade, mutação, seleção
natural e recombinação. Algoritmos genéticos são implementados como uma simulação de computador em que uma população de representações abstratas de solução é selecionada em busca de soluções melhores. A evolução geralmente se inicia a partir de um conjunto de soluções criado aleatoriamente e é realizada por meio de gerações. A cada geração, a adaptação de cada solução na população é avaliada, alguns indivíduos são selecionados para a próxima geração, e recombinados ou mutados para formar uma nova população. A nova população então é utilizada como entrada para a próxima iteração do algoritmo.
1.2 O problema da caixa preta O problema consistem em encontrar a melhor configuração para um conjunto de 9 (a) botões que estão disponíveis em uma caixa, sendo que cada botão pode assumir 16 posições distintas(b) Para representar a posição de cada botão no algoritmo, cada posição do botão é representando com um conjunto de 4 bits (c) e cada individuo (cromossomo) é representado pela disposição destes 9 botões, portanto 36 bits.
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Representação para cada posição dos botões da caixa preta (c) 2. Codificação O trabalho pratico foi desenvolvido utilizando a ferramenta Matlab 8.0.0.783 (R2012b) 32 bits. O trabalho foi organizado em funções e um corpo principal para a chamada das funções chamado BlackBox.m. 2.1 Populações iniciais e avaliação dos indivíduos A população inicial foi gerada no próprio main(BlackBox.m) em seguida é chamada a função avalia.m para geração da avaliação de cada individuo de acordo com a função abaixo: sinalDeSaida = 9+(teta(2)*teta(5))-(teta(23)*teta(14))+... (teta(24)*teta(4))-(teta(21)*teta(10))+(teta(36)*teta(15))-... (teta(11)*teta(26))+(teta(16)*teta(17))+(teta(3)*teta(33))+... (teta(28)*teta(19))+(teta(12)*teta(34))-(teta(31)*teta(32))-... (teta(22)*teta(25))+(teta(35)*teta(27))-(teta(29)*teta(7))+... (teta(8)*teta(13))-(teta(6)*teta(9))+(teta(18)*teta(20))-... (teta(1)*teta(30))+(teta(23)*teta(4))+(teta(21)*teta(15))+... (teta(26)*teta(16))+(teta(31)*teta(12))+(teta(25)*teta(19))+... (teta(7)*teta(8))+(teta(9)*teta(18))+(teta(1)*teta(33));
Sendo teta a posição do bit dentro do indivíduo (36 bits) 2.2 Seleções dos indivíduos Os métodos de seleção dos indivíduos para cruzamento foram implementadas nas funções roleta.m e sel_torneio.m. a- Seleção por roleta viciada cada indivíduo da população é representado na roleta de forma proporcionalmente ao seu valor de aptidão. b- Seleção por torneio: Em cada sorteio, dois indivíduos são escolhidos aleatoriamente, e o melhor deles é selecionado para a próxima geração 2.3 Operadores genéticos Após a seleção dos individuos os mesmos vão cruzar entre si, gerando assim novos individuos. Foram adotados dois meios de cruzamento: Uniforme e ponto de corte,
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas respectivamente
implementados
pelas
funções
cruzamento_uniforme
e
cruzamento_corte.m. a- Cruzamento uniforme - Dois indivíduos (pais) são selecionados aleatoriamente e os indivíduos filhos são gerados com base em uma máscara de bit.
b- Ponto de Corte: São selecionados dois indivíduos (pais) que dão origem a dois novos indivíduos (filhos). Um ponto de corte é escolhido aleatoriamente nos pais e as partes separadas por esse ponto são trocadas.
2.4 Mutação A mutação é muito importante para prevenir a convergência para um maximo local. Na figura abaixo o objetivo da mutação é a de evitar que o algoritmo ita que o ponto C é uma Maximo global, realizando a mutação teremos maiores chances de encontrar o real maximo global (Ponto A).
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
A mutação é feia pelas funções mutação_escolha_bit.m e mutação_bit_bit.m. a) Escolha aleatória do bit: Em cada indivíduo, um bit é escolhido aleatoriamente e o seu valor é invertido. Esse operador é aplicado em todos os indivíduos da população e a mutação ocorre de acordo com a taxa de mutação definida. b) Mutação bit a bit: A mutação ocorre bit a bit segundo uma probabilidade (taxa de mutação). A mutação bit a bit é aplicada em todos os indivíduos da população.
2.5 Elitismo O elitismo ocorre na função comelitismo.m e tem como objetivo preservar os melhores indivíduos da geração, de forma que o melhor indivíduo de uma geração sempre é ado para a geração seguinte.
2.6 Apresentação dos Resultados A apresentação dos resultados obtidos pelo Algoritmo Genético é feita no script principal
BlackBox.m. A cada N* execuções são apresentados o número de
sucessos, o maior valor de fitness, o menor valor de fitness, a média, o desvio padrão,
e
o
boxplot
dos
valores
de
fitness.
É
apresentado
também
o
histograma dos melhores indivíduos. *Valor de N a ser definido no programa 3 Testes e analise dos resultados 3.1 Primeiro teste: Para o primeiro teste, o algoritmo foi executado com a seguinte configuração de parâmetros e foi utilizado o cruzamento com um ponto de corte e o cruzamento uniforme:
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas a) Sem elitismo. b) Seleção por roleta. c) Mutação bit a bit. d) Probabilidade de cruzamento: 0,8. e) Probabilidade de mutação: 0,025. f) Número de indivíduos da população: 30. g) Número de gerações: 50. Utilizando ponto de corte temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 23 Menor Fitness (Pior caso): 18 Valor médio de Fitness: 21,14 Desvio-padrão dos valores de Fitness: 1.37
Fig.1 Box-Plot utilizando ponto de corte
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.2 Histograma utilizando ponto de corte
Utilizando cruzamento uniforme temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 23 Menor Fitness (Pior caso): 15 Valor médio de Fitness: 20,34 Desvio-padrão dos valores de Fitness: 2.48
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.3 Box-Plot utilizando cruzamento uniforme
Fig.4 Histograma utilizando cruzamento uniforme
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas 3.2. Segundo Teste: Avaliação do Efeito do Tipo de Seleção. Para o segundo teste foi utilizado a seguinte configuração de parâmetros, variando-se apenas o tipo de seleção: a) Sem elitismo. b) Cruzamento Uniforme. c) Mutação bit a bit. d) Probabilidade de cruzamento: 0,8. e) Probabilidade de mutação: 0,025. f) Número de indivíduos da população: 30. g) Número de gerações: 50. Utilizando seleção por roleta temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 26 Menor Fitness (Pior caso): 16 Valor médio de Fitness: 23,70 Desvio-padrão dos valores de Fitness: 2,48
Fig.5 Box-Plot utilizando seleção roleta
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.6 Histograma utilizando seleção roleta
Utilizando seleção por torneio temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 16 Menor Fitness (Pior caso): 11 Valor médio de Fitness: 11,30 Desvio-padrão dos valores de Fitness: 1,01
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.7 Box-Plot utilizando seleção torneio
Fig.8 Histograma utilizando seleção torneio
3.3. Terceiro Teste: Avaliação do Efeito do Tipo de Mutação Para avaliar o efeito do tipo de mutação, o algoritmo foi executado utilizando a configuração abaixo: a) Sem elitismo.
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas b) Cruzamento Uniforme. c) Seleção por Roleta. d) Probabilidade de cruzamento: 0,8. e) Probabilidade de mutação: 0,025. f) Número de indivíduos da população: 30. g) Número de gerações: 50.
Utilizando mutação bit a bit temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 21 Menor Fitness (Pior caso): 16 Valor médio de Fitness: 19.16 Desvio-padrão dos valores de Fitness: 1.16
Fig.9 Box-Plot utilizando mutação bit a bit
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.10 Histograma utilizando mutação bit a bit
Utilizando mutação aleatória de bit temos: Número de Sucessos: 0 Maior Fitness (Melhor caso): 23 Menor Fitness (Pior caso): 16 Valor médio de Fitness: 21.20 Desvio-padrão dos valores de Fitness: 2,02
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.11 Box-Plot utilizando mutação aleatória de bit
Fig.12 Histograma utilizando mutação aleatória de bit
3.4. Quarto Teste: Avaliação do Efeito da Probabilidade de Cruzamento Foram realizados três testes, variando o valor dessa probabilidade e mantendo fixos todos os outros parâmetros. Foram utilizados os valores de parâmetros a seguir e os valores utilizados para a taxa de cruzamento foram 0,2, 0,5 e 0,8:
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas a) Sem elitismo. b) Cruzamento Uniforme c) Seleção por Roleta d) Mutação por escolha aleatória do bit e) Probabilidade de mutação: 0,025. f) Número de indivíduos da população: 30. g) Número de gerações: 50.
Utilizando a taxa de cruzamento igual a 0,8 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 24 Menor Fitness (Pior caso): 15 Valor médio de Fitness: 21,08 Desvio-padrão dos valores de Fitness: 2.73
Fig.13 Box-Plot utilizando taxa de cruzamento 0,8
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.14 Histograma utilizando taxa de cruzamento 0,8 Utilizando a taxa de cruzamento igual a 0,5 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 25 Menor Fitness (Pior caso): 15 Valor médio de Fitness: 20.17 Desvio-padrão dos valores de Fitness: 1.9125
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.15 Box-Plot utilizando taxa de cruzamento 0,5
Fig.16 Histograma utilizando taxa de cruzamento 0,5
Utilizando a taxa de cruzamento igual a 0,2 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 21
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas Menor Fitness (Pior caso): 15 Valor médio de Fitness: 18,90 Desvio-padrão dos valores de Fitness: 1,85
Fig.17 Box-Plot utilizando taxa de cruzamento 0,2
Fig.18 Histograma utilizando taxa de cruzamento 0,2
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas 3.5. Quinto Teste: Avaliação do Efeito da Probabilidade de Mutação Para analisar o efeito da probabilidade de mutação foi fixado os parâmetros variandose apenas as taxas de mutações. Foram realizados quatro testes, os valores para a taxa de mutação foram: 0,05, 0,1, 0,25 e 0,75, respectivamente. Foi assumido os seguintes parâmetros: a) Sem elitismo. b) Cruzamento uniforme c) Seleção por Roleta d) Mutação por escolha aleatória do bit e) Probabilidade de cruzamento: 0.8 f) Número de indivíduos da população: 30. g) Número de gerações: 50.
Utilizando a taxa de mutação igual a 0,05 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 21 Menor Fitness (Pior caso): 16 Valor médio de Fitness: 18,48 Desvio-padrão dos valores de Fitness: 1,21
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.19 Box-Plot utilizando taxa de mutação 0,05
Fig.20 Histograma utilizando taxa de mutação 0,05
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas Utilizando a taxa de mutação igual a 0,1 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 21 Menor Fitness (Pior caso): 15 Valor médio de Fitness: 19,16 Desvio-padrão dos valores de Fitness: 1,43
Fig.21 Box-Plot utilizando taxa de mutação 0,1
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.22 Histograma utilizando taxa de mutação 0,1
Utilizando a taxa de mutação igual a 0,25 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 23 Menor Fitness (Pior caso): 17 Valor médio de Fitness: 20,72 Desvio-padrão dos valores de Fitness: 1,81
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.23 Box-Plot utilizando taxa de mutação 0,25
Fig.24 Histograma utilizando taxa de mutação 0,25
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas Utilizando a taxa de mutação igual a 0,75 o resultado foi: Número de Sucessos: 0 Maior Fitness (Melhor caso): 23 Menor Fitness (Pior caso): 17 Valor médio de Fitness: 21,34 Desvio-padrão dos valores de Fitness: 1.86
Fig.25 Box-Plot utilizando taxa de mutação 0,75
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.26 Histograma utilizando taxa de mutação 0,75 3.6. Sexto Teste: Avaliação do Efeito do Elitismo Para avaliar os efeitos causados pelo processo de elitismo, foi utilizada a configuração abaixo e o algoritmo foi testado com e sem a aplicação do elitismo. a) Cruzamento Uniforme b) Seleção por Roleta c) Mutação por escolha aleatória do bit d) Probabilidade de cruzamento: 0.8 e) Probabilidade de mutação: 0.75 f) Número de indivíduos da população: 30. g) Número de gerações: 50. Sem a utilização de elitismo: Número de Sucessos: 0 Maior Fitness (Melhor caso): 21 Menor Fitness (Pior caso): 16 Valor médio de Fitness: 19,58 Desvio-padrão dos valores de Fitness: 1.18
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.27 Box-Plot sem elitismo
Fig.28 Histograma sem elitismo Utilizando elitismo temos: Número de Sucessos: 12 Maior Fitness (Melhor caso): 27 Menor Fitness (Pior caso): 16
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas Valor médio de Fitness: 23,78 Desvio-padrão dos valores de Fitness: 3,39
Fig.29 Box-Plot com elitismo
Fig.30 Histograma com elitismo
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas 3.7 Avaliação final Após a realização dos testes acima vemos que a melhor parametrização do algoritmo é: a) Cruzamento Uniforme b) Seleção por Roleta c) Mutação por escolha aleatória do bit d) Probabilidade de cruzamento: 0.8 e) Probabilidade de mutação: 0.05 f) Com elitismo Concluímos que ao aumentar o numero de indivíduos aumentamos a chances de obter um individuo ótimo, alem disso a chance de se obter um individuo ótimo sob exponencialmente ao se aumentar o numero de gerações e indivíduos conforme mostrado na tabela 5 e na figura 31.
Fig.31 Histograma com 800 gerações e 240 indivíduos
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
TESTE
TESTE 1 TESTE 2 TESTE 3
TESTE 4
TESTE 5 TESTE 6
N ELISTISMO SELEÇÃO 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO NÃO SIM
ROLETA ROLETA ROLETA TORNEIO ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA
CRUZAMENTO PONTO DE CORTE UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME
MUTAÇÃO
TC
TM
N° IND
N° GERAÇÃO
BIT A BIT BIT A BIT BIT A BIT BIT A BIT BIT A BIT ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO
0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,5 0,2 0,8 0,8 0,8 0,8 0,8 0,8
0,025 0,025 0,025 0,025 0,025 0,025 0,025 0,025 0,025 0,05 0,1 0,25 0,75 0,75 0,75
30 30 30 30 30 30 30 30 30 30 30 30 30 30 30
50 50 50 50 50 50 50 50 50 50 50 50 50 50 50
Tabela 2: Parâmetros utilizados
TESTE TESTE 1 TESTE 2 TESTE 3
TESTE 4
TESTE 5 TESTE 6
N 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
N° DE SUCESSO 0 0 0 0 0 0 0 0 0 0 0 0 0 0 12
MAIOR FITNESS 23 23 26 16 21 23 24 22 21 21 21 23 23 21 27
MENOR FITNESS 18 15 16 11 16 16 15 16 15 16 15 17 17 16 16
Tabela 3: Resultados
FITNESS MÉDIO DESVIO PADRÃO 21,14 1,37 20,34 2,48 23,7 2,58 11,3 1,01 19,16 1,16 21,2 2,02 21,08 2,73 19,5 1,47 18,9 1,85 18,48 1,21 19,16 1,43 20,72 1,81 21,34 1,86 19,58 1,18 23,78 3,39
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
TESTE ELISTISMO TESTE 1 SIM TESTE 2 SIM TESTE 3 SIM TESTE 4 SIM TESTE 5 SIM TESTE 6 SIM TESTE 7 SIM TESTE 8 SIM TESTE 9 SIM TESTE 10 SIM
SELEÇÃO ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA ROLETA
CRUZAMENTO UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME UNIFORME
MUTAÇÃO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO ALEARTÓRIO
TC 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8 0,8
TM 0,75 0,75 0,75 0,75 0,75 0,75 0,75 0,75 0,75 0,75
N° IND 60 120 240 30 30 30 30 60 120 240
N° GERAÇÃO 50 50 50 100 200 400 800 200 400 800
Tabela 4: Parâmetros com variações n° de indivíduos e n° de gerações
TESTE TESTE 1 TESTE 2 TESTE 3 TESTE 4 TESTE 5 TESTE 6 TESTE 7 TESTE 8 TESTE 9 TESTE 10
N° DE SUCESSO 0 12 16 0 0 0 0 0 357 769
MAIOR FITNESS 24 27 27 26 23 25 23 26 27 27
MENOR FITNESS 16 16 18 16 16 17 16 17 18 17
FITNESS MÉDIO DESVIO PADRÃO 21,46 2,177 24,5 2,28 23,76 2,83 24,8 2,45 22,5 1,54 24,87 0,71 22,87 0,79 25,46 1,52 26,63 1,29 26,83 0,99
Tabela 5: Resultados com variações n° de indivíduos e n° de gerações
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.32 Dados função anova1
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.33 Box-Plot com a função anova1
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
Fig.34 Box-Plot com a função anova1
pop_size num_ger numero de loops N valor medio fitness 60 75 125 25,89 120 75 125 26,73 120 250 125 26,8 600 250 125 27 Menor fitness Maior fitness Numero de sucesso 23 27 37 25 27 93 25 27 102 27 27 125
desvio padrao fitness 0,9 0,4604 0,4154 0
Tabela 6: Dados utilizados na função anova1
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas 3.8 Código fonte do programa Main – BlackBox.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== clear all close all clc % ===================================================================== % Configuracoes iniciais pcross = 0.8; % porcentagem de cruzamento taxaMutacao = 0.05; % porcentagem de mutação popsize = 60; % numero de individuos N = 125; % Rodar N vezes; num_ger= 75;% numero de gerações nbits=4; % numero de bits em cada cromossomo tam_ind=36; tipo_selecao = 0; % 0 - roleta; 1 - torneio elitismo=1;% 0 sem elitismo 1 com elitismo tipo_mutacao = 0; % 0 - escolha aleatoria de bit; 1 - bit a bit tipo_cruzamento = 1; % 0 - um ponto de corte; 1 - uniforme
for rodar = 1:N pop=round(rand(popsize,tam_ind)); % random da população de 1s e 0s for i=1:popsize vetorAvaliacao(i) = avalia(pop(i,1:tam_ind)); % somatorio das avaliações
end
for k=1:num_ger for i=1:popsize vetorAvaliacao(i) = avalia(pop(i,1:tam_ind)); % somatorio das avaliações
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
end if tipo_selecao == 0 % roleta selecionados = roleta(vetorAvaliacao,popsize); else % torneio selecionados = sel_torneio(vetorAvaliacao); end
% Cruzamento
if tipo_cruzamento == 0 % um ponto de corte filhos = cruzamento_corte(pop,selecionados,pcross);
end if tipo_cruzamento == 1% uniforme mascara = round(rand(popsize/2,tam_ind)); filhos = cruzamento_uniforme(pop,selecionados,tam_ind,popsize,mascara,pcross); end if tipo_mutacao == 0 %0 - escolha aleatoria mutacao_escolha_bit(filhos,taxaMutacao,popsize); else % 1 - bit a bit mutacao_bit_bit (filhos,taxaMutacao,popsize,tam_ind); end if elitismo == 1 filhos = comelistismo(popsize,pop,filhos,vetorAvaliacao); end
Melhor_Ind(rodar) = max(vetorAvaliacao); pop = filhos;
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
end end Valor_medio_fitness=mean(Melhor_Ind) desvio_pad_fitness=std(Melhor_Ind) ll=sort(Melhor_Ind); Menor_Fitness=(ll(1)) Maior_Fitness=(ll(N)) pp=0; for hh=1:N if Melhor_Ind(hh)==27 pp=pp+1; else pp=pp; end end Num_Sucesso=PP % % % % % %
Criar Estatisticas Melhor Avaliação no Teste Pior Avaliacao no Teste Media Avaliacao no Teste Desvio Padrão da Avaliacao Box-Plot
% Num_Sucesso=pp % boxplot(Melhor_Ind) % hist(Melhor_Ind)
% Funcao ANOVA %teste0=Melhor_Ind1'; %teste1=Melhor_Ind2'; %teste2=Melhor_Ind3'; %teste3=Melhor_Ind4';
%zz=[teste0 teste1 teste2 teste3]; % [p,table,st]=anova1(zz); % [c,m,nms]=multcompare(st); Função Avalia.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas % ALUNO:Elson Claudio Correa Moraes %=================================================================== % função avaliar individuo function sinalDeSaida = avalia( teta )
sinalDeSaida = 9+(teta(2)*teta(5))-(teta(23)*teta(14))+... (teta(24)*teta(4))-(teta(21)*teta(10))+(teta(36)*teta(15))-... (teta(11)*teta(26))+(teta(16)*teta(17))+(teta(3)*teta(33))+... (teta(28)*teta(19))+(teta(12)*teta(34))-(teta(31)*teta(32))-... (teta(22)*teta(25))+(teta(35)*teta(27))-(teta(29)*teta(7))+... (teta(8)*teta(13))-(teta(6)*teta(9))+(teta(18)*teta(20))-... (teta(1)*teta(30))+(teta(23)*teta(4))+(teta(21)*teta(15))+... (teta(26)*teta(16))+(teta(31)*teta(12))+(teta(25)*teta(19))+... (teta(7)*teta(8))+(teta(9)*teta(18))+(teta(1)*teta(33));
Função cruzamento_corte.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== %função cruzamento com 1 ponto de corte function filhos = cruzamento_corte(pop,selecionados,pcross) for i = 1:length(selecionados)/2
if rand
end
Função cruzamento_uniforme.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== %função cruzamento uniforme function filhos = cruzamento_uniforme(pop,selecionados,tam_ind,popsize,mascara,pcross)
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas
%Cruzamento Uniforme
for i=1:popsize/2 % fazer so a metade tam_pop/2, use a mesma mascara para criar dois filhos
for j=1:tam_ind
if mascara(i,j)==0 && rand
else filhos(2*i,j) = pop(selecionados(2*i-1),j); filhos(2*i-1,j)= [pop(selecionados(2*i),j)];
end end end
end
Função roleta.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== %função roleta viciada function selecionados = roleta( vetorAvaliacao,popsize ) soma = sum(vetorAvaliacao); for k = 1:popsize s = rand*soma;
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas i = 1; aux = vetorAvaliacao(1); while aux<s i = i + 1; aux = aux + vetorAvaliacao(i); end selecionados(k) = i; end end
Função mutação_escolha_bit.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== %Função para para mutar individuo escolha aleatoria de bit function
filhos = mutacao_escolha_bit(filhos,taxaMutacao,popsize)
for i=1:popsize for j=ceil(rand*34 + 0.1) if rand
end
Função mutação_bit_bit.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %===================================================================
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas %Função para para mutar individuo bit a bit function
filhos = mutacao_bit_bit(filhos,taxaMutacao,popsize,tam_ind)
for i=1:popsize for j=1:tam_ind if rand
end
Função sel_torneio.m %=================================================================== % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== % Funcao Torneio function selecionados = sel_torneio(vetorAvaliacao)
for i = 1:length(vetorAvaliacao) d=ceil(rand*29 + 0.1); if vetorAvaliacao(i)
end
Função comelitismo.m %===================================================================
UNIVERSIDADE FEDERAL DE LAVRAS DEPARTAMENTO DE ENGENHARIA Programa de pós-graduação em engenharia de sistemas % DISCIPLINA DE COMPUTAÇÃO EVOLUCIONÁRIA - TRABALHO DA CAIXA PRETA % PROFESSOR:Bruno Henrique Groenner Barbosa % ALUNO:Elson Claudio Correa Moraes %=================================================================== % Funcao Torneio function selecionados = sel_torneio(vetorAvaliacao)
for i = 1:length(vetorAvaliacao) d=ceil(rand*29 + 0.1); if vetorAvaliacao(i)
end
Related Documents 3m3m1z
Problema Da Caixa Preta Doc Final 44l2x
December 2020 0
Teste Caixa Preta g3y2s
August 2021 0
Nos Caminhos Da Jurema Preta 6v2a15
April 2020 45
Manual Da Caixa Al4 315e3j
July 2022 0
381921885 A Caixa Preta De Darwin Desafio Da Bioquimica A Teoria Da Evolucao Michael Behe Pdf 3u2h6h
June 2020 3
Problema Certificado Digital E Caixa I 565p4h
November 2019 15More Documents from "Dimas Leme" 3l6y43
Problema Da Caixa Preta Doc Final 44l2x
December 2020 0
Sejarah Nutrisi Tanaman 59683y
November 2020 0
Vehicosta S.a 2 1s251n
May 2021 0
Mengenal Pekerjaan Mep 5j2w6p
May 2020 40
Tabel Gas Ideal 1d35g
October 2020 0