Upload
davidalves
View
216
Download
0
Embed Size (px)
Citation preview
7/23/2019 Apresentao AG sobre optimizao
1/62
Tpicos Especiais em Otimizao
Ivo Chaves da Silva Junior
Juiz de Fora, 22 de Maio de 2014
Algoritmos Genticos
7/23/2019 Apresentao AG sobre optimizao
2/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
In troduo
2
Algoritmo Gentico
John H. Holland
(Pesquisador da Universidade de Michigan)
Dcada de 60 - Props um processo de otimizao,
denominado:
7/23/2019 Apresentao AG sobre optimizao
3/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
Motivao
3
Na evoluo das espcies, s os indivduos mais aptos ao meio
ambiente sobrevivem e a estes so dadas a oportunidade de se
reproduzir e deixar suas caractersticas em seus descendentes
TEORIA DA EVOLUO DAS ESPCIES
1859Charles Darwin
7/23/2019 Apresentao AG sobre optimizao
4/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
A lgoritm os Evo luc ionrios
4
DEFINIO:
Algoritmos que modelam computacionalmente os processos naturais daevoluo de modo a construir uma ferramenta para resoluo deproblemas nas mais diversas reas do conhecimento.
SIMULAO DA EVOLUO DAS ESPCIES
Seleo dos indivduos
Reproduo entre indivduos
Nova gerao de indivduos
Nascimento dos indivduos
7/23/2019 Apresentao AG sobre optimizao
5/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
5
Pseudo-Cdigo
Inicializa_Populao P(0)
Enquanto no term inar faaAvalie_Populao
Selecione_Pais
Recombinao
MutaoNova Populao
Fim enquanto
A lgoritm os Evo luc ionrios
7/23/2019 Apresentao AG sobre optimizao
6/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
A lgoritm os Evo luc ionrios
6
Coisas bizarras da computao evolutiva :
Pais morrerem imediatamente aps o nascimento dos filhos
Mutaes genticas podem ser frequentes
Indivduos podem ser eternos
Entre outras........
Um algoritmo evolucionrio INSPIRADO na natureza e nouma cpia fiel da mesma
No h distino de machos e fmeas
7/23/2019 Apresentao AG sobre optimizao
7/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
A lgoritm os Evo luc ionrios
7
Tcnicas de Busca
Baseadas em ClculoAleatrias-Guiadas Enumerativas
Algoritmos Evolucionrios Resfriamento Simulado
Estratgias Evolucionrias Algoritmos Genticos Programao Gentica
Paralelos Seqenciais
7/23/2019 Apresentao AG sobre optimizao
8/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
8
Indivduo Uma soluo
Populao Conjunto de SoluesGerao Passo do Processo de Soluo
Cromossomos Sequncias de Caracteres
Gene Cada um dos Caracteres
Fentipo Decodificao da Soluo
Gentipo Codificao da Soluo
TERMINOLOGIA
Conceitos Bsicos
A lgo r itmos Genticos
7/23/2019 Apresentao AG sobre optimizao
9/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
9
Algoritmos genticos (GA) so um ramo dos algoritmos evolucionrios
So algoritmos de busca baseados nos mecanismos de seleonatural e gentica.
Os algoritmos genticos so tcnicas heursticas de otimizao global
Heurstica significa encontrar ou descobrir, porm sem garantir a
otimalidade da soluo encontrada.
Melhor soluo para o problema em anlise
Conceitos Bsicos
A lgo r itmos Genticos
7/23/2019 Apresentao AG sobre optimizao
10/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
MaximizaoMtodos clssicos
10
Conceitos Bsicos
A lgo r itmos Genticos
Mximo Global
Mximo Local
Ponto Inicial
Ponto Inicial
GAs trabalham com vrias solues ao mesmo tempo, logo, no ficampresos a timos locais devido a condio inicial . Situao que ocorre com
mtodos de otimizao clssica (baseados em derivadas).
7/23/2019 Apresentao AG sobre optimizao
11/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
11
No porque se encontrou um indivduo que instantaneamente omelhor de um grupo que o processo de busca finaliza a procura deoutros indivduos ainda melhores.
Conceitos Bsicos
A lgo r itmos Genticos
Bactrias ambiente livre de antibitico Bactrias ambiente com antibitico
EXEMPLO REAL : AMBIENTE VARIVEL
Melhor Bactria Melhor Bactria
7/23/2019 Apresentao AG sobre optimizao
12/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
12
Conceitos Bsicos
A lgo r itmos Genticos
Como os AGs tm o mesmo comportamento que a evoluo das espcies:
COMPETIO ENTRE OS INDIVDUOS NATURAL
A competio entre os indivduos que determina as solues obtidas
7/23/2019 Apresentao AG sobre optimizao
13/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
13
Conceitos Bsicos
A lgo r itmos Genticos
COMPETIO!!!???
QUAL O CRITRIO A SER AVALIADO??
7/23/2019 Apresentao AG sobre optimizao
14/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
14
De dois indivduos no to bons (de acordo com um critrio pr-definido)podem nascer indivduos com excelentes caractersticas, sendo a situaocontrria verdadeira.
Conceitos Bsicos
A lgo r itmos Genticos
EXEMPLO: BELEZA O CRITRIO !!! COMO SER O NOVO INDIVDUO?
7/23/2019 Apresentao AG sobre optimizao
15/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
15
Conceitos Bsicos
A lgo r itmos Genticos
CARACTERSTICAS DOS AGs
GAs so tcnicas probabilsticas, e no tcnicas determinsticas.
Iniciando um GA com a mesma populao inicial e o mesmo conjuntode parmetros podemos encontrar solues diferentes a cada vez queexecutamos o programa.
GAs so em geral programas extremamente simples que necessitamsomente de:
Informaes relativas adequabilidade do ponto como soluo doproblema em questo
No necessitam de derivadas ou qualquer outra informaoadicional.
Extremamente aplicveis a problemas do mundo real que em geral
incluem descontinuidades severas.
7/23/2019 Apresentao AG sobre optimizao
16/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
16
Conceitos Bsicos
A lgo r itmos Genticos
GAs trabalham com uma grande populao de solues, sendo umaheurstica de busca.
Um GA diferencia-se dos esquemas enumerativos pelo fato de noprocurar em todos os pontos possveis, mas sim em um subconjuntodestes pontos
GAs diferenciam-se de esquemas aleatrios por serem uma busca que
utiliza informao pertinente ao problema e no trabalham comcaminhadas aleatrias (random walks) pelo espao de solues.
CARACTERSTICAS DOS AGs
7/23/2019 Apresentao AG sobre optimizao
17/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
17
Conceitos Bsicos
A lgo r itmos Genticos
POR QUE USAR ALGORITMOS GENTICOS??
GA uma tcnica de busca com as seguintes caractersticas positivas:
Otimizao Global
No so totalmente aleatrios
No afetada por descontinuidades na funo ou em suasderivadas
Capaz de lidar com funes discretas e contnuas
Boa tcnica para atacar problemas com espaos de buscaintratveis, que no podem ser resolvidos por tcnicas tradicionais.
7/23/2019 Apresentao AG sobre optimizao
18/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
18
A lgor itmos Genticos
REPRESENTAO DE UM INDIVDUO - MODELAGEM
A representao cromossomial fundamental para o algoritmo gentico.
Ela consiste em uma maneira de traduzir a informao do problema emuma maneira vivel de ser tratada pelo computador.
Quanto mais adequada ao problema, maior a qualidade dos resultadosobtidos.
7/23/2019 Apresentao AG sobre optimizao
19/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
19
A lgor itmos Genticos
REPRESENTAO DE UM INDIVDUO - MODELAGEM
7/23/2019 Apresentao AG sobre optimizao
20/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
20
A lgor itmos Genticos
Varivel X2Varivel X1
8 35
0 0 1 0 0 0 1 0 0 0 1 1
Codificao(Gentipo)
Decodificao(Fentipo)
Indivduo
CromossomoGene
02 Cromossomos12 Genes
EXEMPLO DE UM INDIVDUO
7/23/2019 Apresentao AG sobre optimizao
21/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
21
A lgor itmos Genticos
REPRESENTAO DE UM INDIVDUO - MODELAGEM
Representamos nmeros (inteiros ou reais), strings, etc. usando a
representao binria.
Para representar nmeros reais como nmeros binrios, temos primeiroque saber duas coisas:
A faixa de operao de cada uma das variveis;
A preciso desejada.
Sabendo isto, convertemos bits para nmeros usando a seguinte frmula:
real= infi+r
i
supi inf
i
2
k
1
7/23/2019 Apresentao AG sobre optimizao
22/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
22
A lgor itmos Genticos
000011 110011
x1 x2
r1 = 000011 = 3
r2 = 110011 = 51
x1 = -2 + 3*(2-(-2))/(26-1) = -1,8
x2 = 0 + 51 *(1-0)/(26-1) = 0,8
real= infi+r
i supi infi
2k 1
Exemplo deinterpretao
de nmeros reais
X1-> [-2 2]X2-> [0 1]
7/23/2019 Apresentao AG sobre optimizao
23/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
23
A lgor itmos Genticos
A funo aptido a maneira utilizada pelos GAs para determinar aqualidade de um indivduo como soluo do problema em questo.
uma nota dada ao indivduo na resoluo do problema.
O valor da funo de aptido usada para a escolha dos indivduos pelo
mdulo de seleo de pais, sendo a forma de diferenciar entre as boas eas ms solues para um problema.
Dada a generalidade dos GAs, a funo de avaliao, em muitos casos, anica ligao verdadeira do algoritmo com o problema real.
AVALIAO DO INDIVDUO FUNO APTIDO
7/23/2019 Apresentao AG sobre optimizao
24/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
24
A lgor itmos Genticos
AVALIAO DO INDIVDUO FUNO APTIDO
fapt=1
FOB+Cmin
fapt= FOB
Problema de Maximizao:
Problema de Minimizao:
7/23/2019 Apresentao AG sobre optimizao
25/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
25
A lgor itmos Genticos
OBSERVAES IMPORTANTES SOBRE FUNO APTIDO
NENHUM INDIVDUO DEVE TER AVALIAO NULA;
A FUNO APTIDO DEVE EMBUTIR TODAS AS RESTRIES ECARACTERSTICAS DO PROBLEMA EM ANLISE;
A FUNO APTIDO DEVE SER CAPAZ DE DIFERENCIAR TODAS ASSOLUES ENTRE SI.
7/23/2019 Apresentao AG sobre optimizao
26/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
26
A lgor itmos Genticos
SELEO DOS MELHORES INDIVDUOS
O mtodo de seleo de pais deve simular o mecanismo de seleonatural: Pais mais capazes geram mais filhos; Pais menos aptos tambm podem gerar descendentes.
Temos que privilegiar os indivduos com funo de avaliao alta,sem desprezar completamente aqueles indivduos com funo de
avaliao extremamente baixa;
At indivduos com pssima avaliao podem ter caractersticas genticasque sejam favorveis criao de um indivduo timo;
7/23/2019 Apresentao AG sobre optimizao
27/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
27
A lgor itmos Genticos
SELEO DOS MELHORES INDIVDUOS
Mtodo simples e muito adotado: MTODO DA ROLETA.
Criamos uma roleta (virtual) na qual cada cromossomo recebe umpedao proporcional sua avaliao (a soma dos pedaos no podesuperar 100%).
Rodamos a roleta
Selecionado ser o indivduo sobre o qual ela parar.
7/23/2019 Apresentao AG sobre optimizao
28/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
28
A lgor itmos Genticos
SELEO DOS MELHORES INDIVDUOS
Exemplo Roleta
Indivduo
1
2
3
Funo Aptido
100
130
50
Total 280
Pedao Roleta
35,70%
46,40%
17,90%
100%
7/23/2019 Apresentao AG sobre optimizao
29/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
29
A lgor itmos Genticos
CRUZAMENTO E MUTAO
Vamos comear com o operador de cruzamento mais simples, chamado
de operador de CRUZAMENTO DE UM PONTO.
Depois de selecionados dois pais pelo mdulo de seleo de pais, umponto de corte selecionado.
Um ponto de corte constitui em uma posio entre dois genes de umcromossomo.
Cada indivduo de n genes contem n-1 pontos de corte.
7/23/2019 Apresentao AG sobre optimizao
30/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
30
A lgor itmos Genticos
CRUZAMENTO E MUTAO
gen
Pontos de Corte: 1 2 3 4
Depois de sorteado o ponto de corte, ns separamos os pais emduas partes: uma esquerda do ponto de corte e outra direita.
7/23/2019 Apresentao AG sobre optimizao
31/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
31
A lgor itmos Genticos
Pai 1
Pai 2
Selecionamos um
ponto de corte
Pai 1
Pai 2
cruzamento
Filho 1
Filho 2
mutao
Filho 1
Filho 2
Gen alteradopela mutao
CRUZAMENTO E MUTAO
7/23/2019 Apresentao AG sobre optimizao
32/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
32
A lgor itmos Genticos
Por simplicidade, populao no pode crescer. Populao de tamanho Constante;
Pais so, obrigatoriamente, substitudos conforme os filhos vo nascendo;
A cada cruzamento estaremos criando dois filhos;
Estes vo sendo armazenados at que o nmero de filhos gerado seja igual aotamanho da populao original;
A probabilidade de ocorrncia de mutao deve ser baixa. Se for alta, o AG sermuito parecido com uma tcnica chamada RANDOM WALK.
CRUZAMENTO E MUTAO
7/23/2019 Apresentao AG sobre optimizao
33/62
Ivo Chaves da Silva Junior
TAMANHO DA POPULAO
GRANDE Aumento do tempo computacional
Pequena Convergncia prematura / rpida
A lgor itmos Genticos
ANLISE DOS PARMETROS GENTICOS
7/23/2019 Apresentao AG sobre optimizao
34/62
Ivo Chaves da Silva Junior
PROBABILIDADE DE SELEO/REPRODUO
ALTA
BAIXA
A lgor itmos Genticos
Perda de qualidade gentica
Pouca diversidade gentica
ANLISE DOS PARMETROS GENTICOS
7/23/2019 Apresentao AG sobre optimizao
35/62
Ivo Chaves da Silva Junior
PROBABILIDADE DE MUTAO
ALTA
BAIXA
A lgor itmos Genticos
Processo muito aleatrio
Estagnao do processo (restrito a timos locais)
ANLISE DOS PARMETROS GENTICOS
7/23/2019 Apresentao AG sobre optimizao
36/62
Ivo Chaves da Silva Junior
FIM DO PROCESSO GENTICO
A lgor itmos Genticos
NMERO MXIMO DE GERAES
TEMPO DE EXECUO
ANLISE DO VALOR MDIO DA POPULAO
ESTAGNAO DE UMA SOLUO POR UM DETERMINDO PERODO
ANLISE DOS PARMETROS GENTICOS
7/23/2019 Apresentao AG sobre optimizao
37/62
Ivo Chaves da Silva Junior
Intervalos Tpicos dos Parmetros Genticos
TamanhoPopulao
Probabilidade deCruzamento
Probabilidade deMutao
Tp Pc Pm
30
100
90%
60%
1%
0,1%
TamanhoPopulao
A lgor itmos Genticos
CONVERGNCIA PELO NMERO MXIMO DE GERAES
7/23/2019 Apresentao AG sobre optimizao
38/62
Ivo Chaves da Silva JuniorIvo Chaves da Silva Junior
38
A lgor itmos Genticos
Seleo: escolhemos os
indivduos que participarodo processo reprodutrio
Avaliao :Aplicamos a funo deavaliao a cada um dosindivduos desta gerao
Operadores genticos:Aplicamos os
operadores de recombinao e mutaoaos indivduos escolhidos para pais
Satisfizemos o critriode parada ?
No
Fim
Sim
Mdulo de populao :definimos a nova populao a partir
da gerao existente e dos filhosgerados
Filhos geradossobrevivem eso copiados
sobre seus pais
Toda a antigagerao de pais
Filho 1 :
Filho 2 :
7/23/2019 Apresentao AG sobre optimizao
39/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
7/23/2019 Apresentao AG sobre optimizao
40/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
7/23/2019 Apresentao AG sobre optimizao
41/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Exemplo Ilustrativo Mecanismo Gentico
Maximizao da funo
7/23/2019 Apresentao AG sobre optimizao
42/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Gerao 1Mximo Global
Indivduo
7/23/2019 Apresentao AG sobre optimizao
43/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Gerao 10
Indivduo de baixa aptido
7/23/2019 Apresentao AG sobre optimizao
44/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Gerao 50
98% dos indivduos no ponto de mximo global.Gerao de excelente qualidade
7/23/2019 Apresentao AG sobre optimizao
45/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Grfico de Convergncia Mdia da Populao
N de Geraes
FOB
Melhor soluo
Mdia da Populao
7/23/2019 Apresentao AG sobre optimizao
46/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ou tros Operadores Genticos
REPRODUO/CROSSOVER
7/23/2019 Apresentao AG sobre optimizao
47/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ou tros Operadores Genticos
Genitor -1 Genitor -2
Descendente -1
Descendente - 2
(sorteio)
7/23/2019 Apresentao AG sobre optimizao
48/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ou tros Operadores Genticos
O Cruzamento realizado gene a gene.
7/23/2019 Apresentao AG sobre optimizao
49/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ou tros Operadores Genticos
0
1
2
7/23/2019 Apresentao AG sobre optimizao
50/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ou tros Operadores Genticos
POPULAO
7/23/2019 Apresentao AG sobre optimizao
51/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ou tros Operadores Genticos
0 10 20 30 40 50 600
2000
4000
6000
8000
10000
12000
Generation
Maximum/AverageFitness
0 10 20 30 40 50 600
2000
4000
6000
8000
10000
12000
Generation
Maximum/AverageFitness
Sem Elitismo Com Elitismo
O melhor indivduo da gerao anterior deve estar presente na prxima gerao;
7/23/2019 Apresentao AG sobre optimizao
52/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ou tros Operadores Genticos
Visa reproduzir, em termos, o comportamento real de nascimento e
morte;
No steady state geram-se os novos indivduos um a um e faz-se atroca destes pelos piores indivduos da populao;
Com o steady state o conceito de gerao fica quase inexistente;
Convergncia por mdia da populao ou tempo de execuo.
7/23/2019 Apresentao AG sobre optimizao
53/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ou tros Operadores Genticos
SELEO
7/23/2019 Apresentao AG sobre optimizao
54/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ou tros Operadores Genticos
Selecionamos uma srie de K indivduos da populao;
Fazemos com que eles entrem em competio direta pelo direito de serpai, usando como arma a sua avaliao;
7/23/2019 Apresentao AG sobre optimizao
55/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Observaes
MUTAO
Importante para a diversidade gentica;
Heurstica exploratria;
Estratgias de taxas de mutao que variem ao longo do processo;
Estratgias de mutao dirigidas (situao de estagnao);
7/23/2019 Apresentao AG sobre optimizao
56/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Observaes
REPRODUO/CROSSOVER
Importante para evitar a busca aleatria da soluo (randow walk);
Codificao binria crossover uniforme o indicado (maior combinao);
Estratgia: Sorteio da forma como um determinado genitor ir se reproduzir;
h d il i
7/23/2019 Apresentao AG sobre optimizao
57/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Observaes
PARMETROS GENTICOS
Estimar os valores dos parmetros genticos (desafio);
Estratgia Determinstica
Estratgia Adapativa
I Ch d Sil J i
7/23/2019 Apresentao AG sobre optimizao
58/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ap licao
Aplicaes: ALGORITMO GENTICO ITA - AERODESIGN
I Ch d Sil J i
http://localhost/Users/ivosilvajunior/Desktop/AG_2014/Algor%C3%ADtmos%20Gen%C3%A9ticos%20aplicados%20no%20projeto%20conceitual%20de%20aeronaves%20n%C3%A3o%20tripuladas%20-%20Ney%20T11.mp47/23/2019 Apresentao AG sobre optimizao
59/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ap licao
I Ch d Sil J i
7/23/2019 Apresentao AG sobre optimizao
60/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ap licao
I Ch d Sil J i
7/23/2019 Apresentao AG sobre optimizao
61/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Ap licao
Ivo Chaves da Silva Junior
7/23/2019 Apresentao AG sobre optimizao
62/62
Ivo Chaves da Silva Junior
A lgor itmos Genticos
Bibl iograf ia