Algoritimos geneticos

Prévia do material em texto

FACULDADE SUL-AMERICANA: FASAM 
CURSO DE SISTEMAS DE INFORMAÇÃO 
Bruno Holanda de Sousa 
 
 
 
 
 
 
 
 
 
 
RESUMO SOBRE ALGORITIMOS GENETICOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
Goiânia 
2016 
Bruno Holanda de Sousa 
 
 
 
RESUMO SOBRE ALGORITIMOS GENETICOS 
 
 
 
 
 
 
 
 
 
 
 
 
 
Trabalho apresentado à disciplina de 
Sistemas Inteligentes como parte 
integrante da nota de N2 do 5º Período. 
Curso de Sistemas de Informação da 
Faculdade Sul-Americana. Professor : 
Francisco Citó. 
 
 
 
 
 
 
Goiânia 
2016 
 
1. Introdução 
Algoritmos genéticos são métodos que tem como objetivo escolher com 
base na seleção natural do melhor, baseando – se na teoria de Charles Darwin, 
"Quanto melhor um indivíduo se adaptar ao seu meio ambiente, maior será sua 
chance de sobreviver e gerar descendentes" 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
2. Desenvolvimento 
Algoritmos genéticos são métodos que tem como objetivo escolher com base 
na seleção natural do melhor até o momento. Eles utilizam busca paralela ou 
estruturada, que são aleatórias, visando a direção por reforço. 
Algoritmos genéticos estão sempre trabalhando na sua otimização buscando a 
melhor maneira de chegar ao seu “destino”, trabalhando sempre com a melhor 
solução encontrada e sempre a modificando para que fique cada vez melhor. 
A maioria das técnicas de busca e otimização, apresentam os seguintes fatores: 
 - Um espaço de busca, onde estão todas as possíveis soluções do problema, 
 - Trabalham com uma codificação do conjunto de parâmetros e não com os 
próprios parâmetros. 
- Trabalham com uma população e não com um único ponto. 
- Utilizam informações de custo ou recompensa e não derivadas ou outro 
conhecimento auxiliar. 
- Utilizam regras de transição probabilísticas e não determinísticas. 
Algoritmos genéticos tem grande eficiência para busca de soluções ótimas ou 
aproximadamente ótimas. 
Algoritmos genéticos baseiam – se na teoria de Charles Darwin, "Quanto melhor um 
indivíduo se adaptar ao seu meio ambiente, maior será sua chance de sobreviver e 
gerar descendentes": este é o conceito básico da evolução genética biológica. A área 
biológica mais proximamente ligada aos Algoritmos Genéticos é a Genética 
Populacional. 
O funcionamento básico desses algoritmos: 
 No ponto 0, é gerada uma população aleatória de indivíduos, onde essa 
população pode ser uma possível solução do problema. 
 Em seguida e gerada uma reprodução desses indivíduos, aumentando a sua 
população para que seja feita novas combinações. 
 No processo evolutivo a população e avaliada e para cada indivíduo e dada 
uma nota, refletindo na sua habilidade de adaptação, uma porcentagem dos mais 
adaptados são mantidos enquanto os menos adaptados são descartados. 
 O processo e refeito iterativamente até que seja alcançado uma população que 
satisfaça a solução do problema. 
 O funcionamento básico dos algoritmos genéticos, tendem em que depois de 
muitas gerações, criem – se camadas em que estejam populações mais aptas. 
Também e utilizado um método chamado de Roleta, onde indivíduos de uma 
determinada camada são selecionada para fazer parte de uma nova geração. Neste 
modo, cada indivíduo e representado pelo seu índice de aptidão, onde os com valores 
maiores de aptidão são atribuídos um valor maior, e os com menores valores de 
aptidão são atribuídos valores menores em uma roleta. 
 
 Para que se consiga gerar camadas de populações que estejam com uma alta 
probabilidade de sucesso, são utilizados operadores que são chamados de Crossover 
e Mutação. São utilizados para que a nova geração seja realmente nova, mais que 
mantenha as características de adaptações adquiridas. 
Operadores Genéticos 
O básico dos operadores é transformar gerações de indivíduos, onde os 
mesmos possam chegar a um resultado satisfatório, mais que mantenha as 
características de adaptações adquiridas. 
 O operador de mutação e faz pequenas alterações nas populações para que a 
probabilidade de que tenha populações igual seja zerada. O operador de mutação e 
utilizado em pequena escala, pois é um operador genético secundário. 
 
Exemplo de mutação 
Antes filho1 (0010101010010010101100) 
Antes filho2(0011111011100000111111) 
Depois filho1 (0010001010010010111100) 
Depois filho2 (0011111011000000111111 
 O Operador crossover fica responsável pela recombinação de características 
durante a reprodução das camadas, e considerado um operador genético 
predominante. 
Exemplo de Crossover 
Pai1 (0010101011|100000111111) 
Pai2(0011111010|010010101100) 
Filho1 (0010101011|010010101100) 
Filho2 (0011111010|100000111111) 
 
Parâmetros genéticos 
Tamanho da população 
O tamanho afeta o desempenho e a eficiência dos algoritmos genéticos, pois 
com a população pequena o desempenho pode cair, sendo que o mesmo não terá 
uma grande cobertura no espaço de busca, já com uma grande população fornece 
uma grande cobertura, só que para trabalhar com uma grande população requer um 
maior recurso computacional e de tempo. 
Taxa de cruzamento 
Quanto mais taxa de cruzamento, maior o número de camadas. Mas se o a 
velocidade de cruzamento for muita rápida, pode perder camadas com uma alta taxa 
de aptidão e a maior parte da população será substituída, causando assim uma perda 
de desempenho. 
Taxa de mutação 
Uma baixa taxa de mutação previne que uma dada posição fique parada em 
um valor, possibilitando que se chegue em qualquer ponto do espaço de busca, com 
a taxa muito alta, a busca se torna essencialmente aleatória. 
Intervalo de geração 
Controla a quantidade de população que será trocada durante a próxima 
geração, com um alto valor, a maior parte da população será substituída, mas com 
valores muito altos pode ocorrer perda de estruturas de alta aptidão, com um valor 
baixo, o algoritmo se torna muito lento. 
Exemplo de como funciona a geração das camadas. 
 
Exemplo de gerações na pratica 
Iniciando... Aptidão da solução: 9 
Geração 1 | Aptidão: 1 | Melhor: óÁá7ãxIãK 
Geração 2 | Aptidão: 1 | Melhor: óÁá7ãxIãK 
Geração 3 | Aptidão: 1 | Melhor: óÁá7ãxIãK 
Geração 4 | Aptidão: 2 | Melhor: OÁá7VqUj5 
Geração 5 | Aptidão: 2 | Melhor: OÁá7VqUj5 
Geração 6 | Aptidão: 2 | Melhor: OÁá7VqUj5 
Geração 7 | Aptidão: 2 | Melhor: OÁá7VqUj5 
Geração 8 | Aptidão: 3 | Melhor: uÔr M2ZDo 
Geração 9 | Aptidão: 3 | Melhor: uÔr M2ZDo 
Geração 10 | Aptidão: 3 | Melhor: uÔr M2ZDo 
Geração 11 | Aptidão: 3 | Melhor: uÔr M2ZDo 
Geração 12 | Aptidão: 3 | Melhor: uÔr M2ZDo 
Geração 13 | Aptidão: 3 | Melhor: uÔr M2ZDo 
Geração 14 | Aptidão: 3 | Melhor: uÔr M2ZDo 
Geração 15 | Aptidão: 3 | Melhor: uÔr M2ZDo 
Geração 16 | Aptidão: 3 | Melhor: uÔr M2ZDo 
Geração 17 | Aptidão: 3 | Melhor: uÔr M2ZDo 
Geração 18 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 19 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 20 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 21 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 22 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 23 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 24 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 25 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 26 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 27 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 28 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 29 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 30 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 31 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 32 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 33 | Aptidão: 4 | Melhor: OwáuM2ZÉoGeração 34 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 35 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 36 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 37 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 38 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 39 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 40 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 41 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 42 | Aptidão: 4 | Melhor: OwáuM2ZÉo 
Geração 43 | Aptidão: 5 | Melhor: uwá M2cdo 
Geração 44 | Aptidão: 5 | Melhor: uwá M2cdo 
Geração 45 | Aptidão: 5 | Melhor: uwá M2cdo 
Geração 46 | Aptidão: 5 | Melhor: uwá M2cdo 
Geração 47 | Aptidão: 5 | Melhor: uwá M2cdo 
Geração 48 | Aptidão: 5 | Melhor: uwá M2cdo 
Geração 49 | Aptidão: 5 | Melhor: uwá M2cdo 
Geração 50 | Aptidão: 5 | Melhor: uwá M2cdo 
Geração 51 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 52 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 53 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 54 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 55 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 56 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 57 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 58 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 59 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 60 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 61 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 62 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 63 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 64 | Aptidão: 6 | Melhor: O5á MuiÉo 
Geração 65 | Aptidão: 7 | Melhor: Olá MujÉo 
Geração 66 | Aptidão: 7 | Melhor: Olá MujÉo 
Geração 67 | Aptidão: 7 | Melhor: Olá MujÉo 
Geração 68 | Aptidão: 7 | Melhor: Olá MujÉo 
Geração 69 | Aptidão: 7 | Melhor: Olá MujÉo 
Geração 70 | Aptidão: 7 | Melhor: Olá MujÉo 
Geração 71 | Aptidão: 7 | Melhor: Olá MujÉo 
Geração 72 | Aptidão: 7 | Melhor: Olá MujÉo 
Geração 73 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 74 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 75 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 76 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 77 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 78 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 79 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 80 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 81 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 82 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 83 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 84 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 85 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 86 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 87 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 88 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 89 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 90 | Aptidão: 8 | Melhor: Olá MunÉo 
Geração 91 | Aptidão: 9 | Melhor: Olá Mundo 
Encontrado resultado na geração 91 | Olá Mundo (Aptidão: 9) 
 
O código java esta em anexo no email. 
 
 
 
3. Conclusão 
Concluímos que algoritmos genéticos são baseado na teria de Charles Darwin, 
onde são selecionados os melhores de cada geração, garantindo assim uma 
próxima geração melhor. Dado um problema utilizamos essas camada geradas 
para que se obtenha a melhor resposta com base nesse estudo, e que também 
pode ser aplicado em diversas áreas. 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
4. Referencias 
http://www.icmc.usp.br/~andre/research/genetic/ 
http://www.leca.ufrn.br/~estefane/metaheuristicas/ag.pdf Introdução aos algoritmos 
genéticos, capitulo 03 
Linden, Ricardo Algoritmos genéticos, 2 ed ,Rio de Janeiro, 2008,p.43,p74,p75,p90 
https://pt.wikipedia.org/wiki/Algoritmo_gen%C3%A9tico 
ftp://ftp.dca.fee.unicamp.br/pub/docs/vonzuben/ia707_01/topico6_01.pdf 
http://www.paulocollares.com.br/2013/05/algoritimo-genetico-classico-em-java-hello-
world/