Relatório Lab 2

Prévia do material em texto

Universidade Federal de Minas Gerais
ELE 083 -Computação Evolucionária
Laboratório II
Gabriel Jerônimo Tavares
Gabriel David de Souza Lucas
Maio
2018
Problema
O problema apresentado consiste no seguinte enunciado: “Projete um Algoritmo Genético que evolui uma população de strings até convergir para a seguinte string:
METHINKS*IT*IS*LIKE*A*WEASEL
 Assumindo que apenas o caracter de espaço (representado por *), letras maísculas e dígitos são permitidos. ”
Qual a probabilidade de uma string gerada aleatoriamente ser exatamente igual a string alvo?
	
Letras = 26
Números = 10
Caractere ‘*’ = 1
Total = 37
Tamanho da string = 28
A probabilidade para isso acontecer é de 1/(37^28) = 1,2312655436389010226379928311857e-44
Explique como o algoritmo genético consegue superar essa probabilidade incrivelmente pequena. 
Mesmo com uma probabilidade baixa, o algoritmo genético consegue superar através das seleções ocorridas e do tempo. A medida que as seleções pegam alguns bons indivíduos da população e os cruzamentos e mutações gerem novos indivíduos com uma avaliação melhor, a população vai convergindo para o alvo ao longo do tempo.
Calcule o número médio de gerações para convergência. 
Teste 1 => 4261 gerações
Teste 2 => 3929 gerações
Teste 3 => 3819 gerações
Teste 4 => 3859 gerações
Teste 5 => 5865 gerações
Número médio de gerações = 4346,6
Faça experimentos com o parâmetro probabilidade de mutação. O que acontece com o desempenho do algoritmo? 
Probabilidade de mutação = 80%
Gerações = 3801
Probabilidade de mutação = 50%
Gerações = 10000
Não convergiu para a string alvo.
Probabilidade de mutação = 90%
Gerações = 4582
	Para valores da probabilidade de mutação acima de 50%, o algoritmo genético convergiu para string alvo, todavia o número de gerações necessários para essa convergência não foi influenciado proporcionalmente. Para valores menores que 50%, o algoritmo não conseguiu convergir.
Faça experimentos com o parâmetro probabilidade de cruzamento. O que acontece com o desempenho do algoritmo? 
O cruzamento é influenciado no algoritmo pelo número de indivíduos selecionados para participar do torneio. Para a convergência, esse valor foi de no máximo 1% da população.
Indivíduos selecionados = 2%
Indivíduos selecionados = 1%
Indivíduos selecionados = 0,5%
Quando a porcentagem dos indivíduos selecionados para o torneio é muito grande, os melhores indivíduos da população sempre são selecionados para fazer o cruzamento. Dessa forma, os filhos gerados são muito parecidos ou até idênticos, assim a variância dentro da população diminui muito rapidamente, fazendo com que o algoritmo venha convergir para um mínimo local e não o ótimo global.
Implementação do algoritmo genético
Representação
A matriz população foi representada pela tabela ASCII. Como cada caractere representa um número dessa tabela, foi colocado em um vetor todos os possíveis caracteres utilizados: “ABCDEFGHIJKLMNOPQRSTUV0123456789*” e convertido para números inteiros. A partir desse vetor, para cada posição da string de um indivíduo, foi gerado um número aleatório que estava relacionado a posição desse vetor de caracteres. Dessa forma foi possível gerar uma matriz de população de maneira aleatória.
Seleção dos pais
Para a seleção dos pais, foi utilizado a seleção por torneio, onde foram selecionados alguns indivíduos aleatoriamente e escolhido os dois melhores para serem os pais. Assim, para essa avaliação, foi feito uma função Fitness que compara cada posição da string alvo “METHINKS*IT*IS*LIKE*A*WEASEL”, já convertida para números da tabela ASCII, com uma possível solução, indivíduo. Se essa comparação apresentasse uma desigualdade, era somado a uma variável soma o valor 1, se apresentasse uma igualdade, era somado a mesma variável o valor 0. Ao final, essa função retornava o valor da variável soma. Dessa forma, conseguiu-se avaliar cada indivíduo da população, onde o melhor indivíduo apresentava um valor de 0 para variável soma, que significava que a string solução era igual a string alvo, e o pior indivíduo apresentava um valor de 28, que significava que a string solução não tinha nenhum caractere, nas mesmas posições, igual a string alvo.
Para a escolha da quantidade de indivíduos para participar do torneio, utilizou-se um valor de 1% da população. Como a população utilizada foi de 800, o número de indivíduos selecionados foi “8”.
Cruzamento
Para o cruzamento dos pais, foi utilizado o Crossover Uniforme. Nesse processo, para cada posição de um filho foi jogado uma moeda. Se caísse cara, era escolhido o gene do pai 1, se caísse coroa, era escolhido o gene do pai 2. Ou seja, foi gerado um número aleatório entre 0 e 1 e se fosse menor que 0,5, o filho receberia caractere do pai 1, caso contrário, o filho receberia o caractere do pai 2. Com isso, foi gerado dois filhos.
Mutação
Para realizar as mutações, foi escolhido a Mutação Scramble. Para esse procedimento, foi gerado aleatoriamente duas posições do vetor a ser mutado, dois números entre 1 e 28, e todos os as posições entre essas duas foram permutadas. 
Por exemplo:
Além disso, a probabilidade para a mutação ocorrer foi de 80%.
Evolução da população 
Por fim, para avaliar a evolução da população foi feito outro torneio. Depois de ter sido obtido os dois filhos, a população ficou maior, então foi feito esse processo novamente para eliminar dois indivíduos. Foi escolhido aleatoriamente 8 indivíduos da população e eliminado os dois piores desses selecionados. Com isso se encerra uma geração e se inicia outra.
O fim do algoritmo ocorreu quando foi encontrada uma solução ótima (fitness = 0), ou quando o número de gerações atingiu 10000.