Visão Geral, Ferramentas e Aplicações dos Algoritmos Genéticos

1 /Algoritmos Genéticos 38

Algoritmos GenéticosAlgoritmos GenéticosConceitos, Aplicações e FerramentaConceitos, Aplicações e Ferramentas

Daniel Seabra

Norton Guimarães

Rodrigo Francisco

2 /Algoritmos Genéticos 38

Agenda

• A teoria da Evolução

• Introdução

• Aplicações de AG

• Ferramentas

3 /Algoritmos Genéticos 38

A teoria da Evolução Natural

4 /Algoritmos Genéticos 38

A teoria

● Em 1885, Charles Darwin escreveu o livro “A Origem das Espécies”;

População de indivíduos com diferentes propriedades e habilidades;

Limite do número de indivíduos numa população; A natureza cria novos indivíduos com propriedades

similares; Os mais hábeis são selecionados para reprodução;

5 /Algoritmos Genéticos 38

Paródia

Filme: Idiocracia

6 /Algoritmos Genéticos 38

O que são O que são Algoritmos Genéticos?Algoritmos Genéticos?

“Uma técnica de busca baseada numa metáfora do processo biológico de evolução natural” (Linder, 2008).

7 /Algoritmos Genéticos 38

História

8 /Algoritmos Genéticos 38

História

9 /Algoritmos Genéticos 38

Analogia das Terminologias

Linguagem Natural Algoritmos GenéticosCromossomo Indivíduo, string,

cromossomo, árvoreGene CaracterísticaAlelo ValorLocus PosiçãoGenótipo EstruturaFenótipo Conjunto de parâmetros

 Tabela 1: Analogia do Algoritmo Genético com a Linguagem Natural (Linder, 2008)

10 /Algoritmos Genéticos 38

Características

11 /Algoritmos Genéticos 38

Esquema dos AGsEsquema dos AGs

12 /Algoritmos Genéticos 38

Representação do Problema

13 /Algoritmos Genéticos 38

Overview do Processo

14 /Algoritmos Genéticos 38

Geração da População Inicial

Cada indivíduo deverá apresentar um conjunto de genes e um conjunto de características observáveis;

A geração é de forma aleatória;

15 /Algoritmos Genéticos 38

Função de Avaliação

Conhecida como função fitness; Projetada para cada problema; Uma função matemática modelada para

o problema; Entra indivíduo e sai resultado.

16 /Algoritmos Genéticos 38

Operadores GenéticosOperadores Genéticos

17 /Algoritmos Genéticos 38

Seleção da População

18 /Algoritmos Genéticos 38

Seleção Proporcional/Truncamento

Baseados no valor relativo da sua aptidão.

19 /Algoritmos Genéticos 38

Seleção Baseado em Ordem

Uso do rank do indivíduo baseado sua aptidão.

20 /Algoritmos Genéticos 38

Método da Roleta Viciada

Busca linear através de uma roleta virtual.

21 /Algoritmos Genéticos 38

Seleção por Torneio

04 indivíduos são aleatoriamente selecionados.

02 são eliminados e, 02 são ganhadores

para gerar a próxima geração..

A

B

C

A

D

D

22 /Algoritmos Genéticos 38

Operação de Crossover

23 /Algoritmos Genéticos 38

Um ponto de corte

Cortar pais em uma posição aleatória e recombinar as partes geradas

24 /Algoritmos Genéticos 38

Dois pontos de corte

Cortar pais em duas posições aleatórias e recombinar as partes geradas.

25 /Algoritmos Genéticos 38

Uniforme

Gerar uma máscara de bits aleatórios e combinar os bits dos pais de acordo com a máscara gerada.

26 /Algoritmos Genéticos 38

Operação de Mutação

27 /Algoritmos Genéticos 38

Radom Resetting

Consiste de troca dos valores de um gene dada uma pequena probabilidade.

28 /Algoritmos Genéticos 38

Creep Mutation

Esta forma acrescenta ou subtrai ao valor do gene um pequeno número aleatório (Eiben, 2008)

29 /Algoritmos Genéticos 38

Aplicações em AG

30 /Algoritmos Genéticos 38

Aplicações em AG

31 /Algoritmos Genéticos 38

Algumas Ferramentas

32 /Algoritmos Genéticos 38

Conclusão

34 /Algoritmos Genéticos 38

Referências

Deepa, S. N. S. S. N. (2008). Introduction to Genetic Algorithms. New York: Springer.

Eiben, A., & Smith, J. E. (2008). Introduction to Evolutionary Computing. New York: Springer.

Ellingsen, K.-E., & Penaloza, M. (2003). A genetic algorithm approach for finding a good course schedule. In Proceedings of the Midwest instruction and Computing Symposium. Duluth, USA.

Filitto, D. (2008). Algoritmos genéticos: Uma visão explanatória. Saber Acadêmico, São Paulo, Brazil.

35 /Algoritmos Genéticos 38

Referências

Linder, R. (2008). Algoritmos Genéticos (3nd ed). Rio de Janeiro: Ciência Moderna.

Melanie, M. (1996). An Introduction to genetic algorithms. London: MIT Press.

Raghavjee, R., & Pillay, N. (2010). An informed genetic algorithm for the high school timetabling problem. In Proceedings of the 2010 Annual Research Conference of the South African Institute of Computer Scientists and Information Technologists (SAICSIT '10). New York, USA, 408-412. doi: 10.1145/1899503.1899555.

36 /Algoritmos Genéticos 38

Referências

Teles, R. M. (2011). Um estudo de técnicas da inteligência artificial aplicadas na distribuição de recursos em áreas geográficas. Unpublished master’s thesis, Universidade Federal de Goiás, Goiás, Brazil.

Turabieh, S. A. H. (2008). Generating university course timetable using genetic algorithms and local search. In Proceeding of the International Conference on Convergence and Hybrid Information Technology. Busan, South Korea (pp. 254 – 260)

Wang, Z., Liu, J.-l., & Yu, X. (2009). Self-fertilization based genetic algorithm for university timetabling problem. In Proceedings of the first ACM/SIGEVO Summit on Genetic and Evolutionary Computation (GEC ’09), New York, USA (pp. 1001–1004).

37 /Algoritmos Genéticos 38