Algoritmos Culturais
1
Sumário
•
•
•
•
•
•
•
•
Introdução
Objetivo
Níveis do Algoritmo Cultural (AC)
Componentes
Pseudo Código AG X AC
Modelagem do AC
Exemplo
Referências
2
Introdução
“A evolução cultural habilita as sociedades a
evoluir ou a se adaptar ao seu ambiente em
taxas que excedem as da evolução biológica
baseada somente na herança genética”.
(Reynolds, 1998, p: 1).
3
Introdução
Modelos e conceitos da Biologia inspiraram a
resolução de problemas computacionais
(Algoritmos Genéticos ).
Novas metáforas interligam outras áreas do
conhecimento à Ciência da Computação.
4
Introdução
Algoritmos Culturais (AC):
• Melhora a taxa de aprendizado de um
Algoritmo Evolutivo, adicionando
mecanismo de pressão cultural para
pressão evolutiva –BELIEFSPACE
5
Introdução
• Sistema de dupla herança:
– genética e
– cultural
• pode adaptar-se melhor e responder com mais
eficiência em problemas.
6
Objetivo
•Filosofia de Algoritmos Culturais:
 aquisição de conhecimento pela
evolução da população e
uso do conhecimento para guiar a
busca.
• Empregados em problemas numéricos
para aumentar a eficiência da busca.
7
Níveis do AC
 Processo de evolução cultural baseado em uma
perspectiva micro e macro evolucionária.
 Nível micro evolucionário:
 população de indivíduos:
 características comportamentais modificadas
e trocadas entre indivíduos.
 Nível macro evolucionário:
 experiências individuais:
 colecionadas no espaço de crença.
8
Componentes do AC
• população,
• espaço de crença e
• protocolo de
comunicação
Espaço de
Crença
Herança
Promoção:
Função de
Influência
Votação:
Função de
Aceitação
Protocolo de
Comunicação
Herança
Reprodução,
Evolução
População
Função de
Avaliação
9
Componentes do AC
Espaço de
Crença
Componente população é
modelado por Algoritmo
Genético, Programação
Genética ou sistemas de
Multi-Agentes entre
outros.
Herança
Promoção:
Função de
Influência
Votação:
Função de
Aceitação
Protocolo de
Comunicação
Herança
Reprodução,
Evolução
População
Função de
Avaliação
10
Componentes do AC
Espaço de
Crença
O Espaço de Crença
representa a influência que
está sendo adquirida pela
população durante o
processo de evolução.
Herança
Promoção:
Função de
Influência
Votação:
Função de
Aceitação
Protocolo de
Comunicação
Herança
Reprodução,
Evolução
População
Função de
Avaliação
11
Componentes do AC
Espaço de
Crença
O protocolo de
comunicação é usado para
determinar a interação
entre a população e o
espaço de crença.
Herança
Promoção:
Função de
Influência
Votação:
Função de
Aceitação
Protocolo de
Comunicação
Herança
Reprodução,
Evolução
População
Função de
Avaliação
12
Algoritmo Genético
Procedimento básico do Algoritmos Genéticos:
Início
t=0
inicializar população P(t)
avaliar população P(t)
;primeira geração
;população inicial aleatória
;calcula f(i) para cada
indivíduo
enquanto (não condição_fim) faça
tt+1
;próxima geração
selecionar P(t) de P(t-1)
altera P(t)
;crossover e mutação
avaliar população P(t)
;calcula f(i) para cada
indivíduo
fim enquanto
fim
13
Algoritmo Cultural
Procedimento básico do Algoritmos Culturais:
Início
t=0
inicializar população P(t)
Inicializar Espaço de Crença EP(t)
avaliar população P(t)
enquanto (não condição_fim) faça
Comunicação (P(t), EP(t));
Atualização EP(t);
Comunicação (EP(t), P(t));
tt+1
selecionar P(t) de P(t-1)
altera P(t)
avaliar P(t)
fim enquanto
fim
;primeira geração
;população inicial aleatória
;calcula f(i) para cada indivíduo
;votação
;uso de operadores culturais
;promoção
;próxima geração
;crossover e mutação
;calcula f(i) para cada indivíduo
14
Componentes do Algoritmo Cultural
 Representação da População
 Representação do Espaço de Crença
 Operadores Culturais
 Protocolo de Comunicação
15
População
 População do Algoritmo Cultural é modelada
por Algoritmo Genético, Programação
Genética, etc.
16
Espaço de Crença
 Espaço de Crença é composto por padrões
que representam as características dos
melhores indivíduos da população.
 Espaço de Crença é representado por
intervalos de números inteiros:
(lim_inf, lim_sup)
17
Operadores Culturais
• Generalização
Caso existam genes na vizinhança de algum
intervalo que compõe o Espaço de Crença,
expande-se este intervalo de modo que
passe a acomodar estes genes.
• Especialização
Caso os genes pertencentes a algum
intervalo que compõe o Espaço de Crença
estejam concentrados em algum ponto
deste intervalo, contrai-se este intervalo.
18
Operadores Culturais
• Fusão
Este é um caso particular de generalização
onde existem genes na vizinhança de dois
intervalos bastante próximos e por isso
ambos os intervalos acabam se fundindo.
• Fissão
Este é um caso particular de
especialização na qual os genes
pertencentes a determinado intervalo
estão concentrados em mais de um ponto
no interior deste intervalo.
19
Ajuste do Espeço de Crença com
Operadores
Todo
espaço de
busca
Espaço de Crença
20
Ajuste do Espaço de Crença com
Operadores
Especialização
   
   
   
Espaço de Crença
21
Ajuste do Espaço de Crença com
Operadores
Espaço de
crença
  
  
   
  
  
   
   
   
      
      
22
Ajuste do Espaço de Crença com
Operadores
Generalização
      
 
     
   
    

      
Espaço de Crença
23
Ajuste do Espaço de Crença com
Operadores
  
   
  
   
  
   
  
   
   
   
   
   
   
Espaço de Crença
24
Ajuste do Espaço de Crença com
Operadores
Fissão
   
   
   
   
   
   
  
   
  
   
  
   
   Espaço de Crença
Espaço de Crença
25
Ajuste do Espaço de Crença com
Operadores
Espaço de
Crença
Espaço de
Crença
  
      
      
     
    
   
   
    

   


    
      
     
  
26
Ajuste do Espaço de Crença com
Operadores
Fusão
  
      
      
     
    
   
   
    

   


    
      
     
  
Espaço de Crença
27
Protocolo de Comunicação
Processo de Votação e Promoção
Espaço de
Crença
Herança
Votação
Promoção
Herança
Reprodução,
Evolução
População
Função de
Avaliação
28
Protocolo de Comunicação
Processo de Votação e Promoção
melhores indivíduos
de uma geração do
AG influenciam o
espaço de crença
Espaço de
Crença
Herança
Votação
Promoção
Herança
Reprodução,
Evolução
População
Função de
Avaliação
29
Protocolo de Comunicação
Processo de Votação e Promoção
melhores indivíduos
de uma geração do
AG influenciam o
espaço de crença
(8 15) ( 2 10)
Espaço de
Crença
Espaço de Crença
Herança
Votação
Promoção
Herança
15
2
X Y
Cromossomo
Reprodução,
Evolução
População
Função de
Avaliação
30
Protocolo de Comunicação
Processo de Votação e Promoção
crenças atualizadas
influenciam um
componente da
população
(8 15) ( 2 10)
Espaço de Crença
Espaço de
Crença
Herança
Votação
Promoção
Herança
15
2
X Y
Cromossomo
Reprodução,
Evolução
População
Função de
Avaliação
31
Protocolo de Comunicação
Processo de Votação e Promoção
crenças atualizadas
influenciam um
componente da
população
(8 15) ( 2 10)
Espaço de Crença
Espaço de
Crença
Herança
Votação
Promoção
Herança
15
2
X Y
Cromossomo
Reprodução,
Evolução
População
Função de
Avaliação
10
7
X Y
Av = Av + Bonus
32
Exemplo
• Sistema de Otimização de Alternativas para
Desenvolvimento de Campos de Petróleo
Algoritmo de
Otimização
AG ou AG / AC
Operadores
Dimensão
do Grid de
Reservatório
Simulador de
Reservatórios
(IMEX)
Alternativa
Poços produtores
Plataforma
Poços
injetores
Avaliação
Dimensão
das Células
do Grid
Curva de
produção
Q (t )
bbs/t
T AB
t
VPL  V  D
Cálculo do
VPL
Preço do
Petróleo
33
Exemplo
• Modelagem do Cromossomo
Máscara de Ativação
0
1
0
1
0
1
1
0
Cromossomo
Verticais
X Y
X Y
Injetores
X Y
Horizontais
X Y
Produtores
XYZ
Dir Dist
XYZ
XYZ
XYZ
Dir Dist Dir Dist Dir Dist
Injetores
Produtores
34
Exemplo
• Modelagem do Espaço de Crença
Espaço de Crença
G(0) G(1) G(2) ................................................................... G(n)
Crença do Gene (2)
[3 12] [15 29] [1 29] [1 1]
x
y
z
[0 1]
[-27 23] [24 24] [23 24]
direção
distância
35
Exemplo
• Gráfico De desempenho do Algoritmo Otimizador
AG
15000 Avaliações
Avaliações
Score
1.70E+09
1.60E+09
1.50E+09
1.40E+09
1.30E+09
1.20E+09
1.10E+09
1.00E+09
9.00E+08
8.00E+08
15*108
8.2*108
1
10
19
28
37
46
55
64
73
82
91 100 109 118 127 136 145 154
Gerações
AG/AC
15000 Avaliações
Score
1.9000E+09
18*108
Avaliações
1.7000E+09
1.5000E+09
1.3000E+09
1.1000E+09
9.0000E+08
5.1*108
7.0000E+08
5.0000E+08
1
10
19
28
37
46
55
64
73
82
Gerações
91 100 109 118 127 136 145
36
Exemplo
• Gráfico de desempenho do AG x AG/AC
Score
2,00E+09
1,80E+09
Avaliações
1,60E+09
1,40E+09
1,20E+09
1,00E+09
8,00E+08
6,00E+08
4,00E+08
1
Teste 3
8
15 22 29 36 43 50 57 64 71 78 85 92 99 106 113 120 127 134 141 148 155
Teste 7
Gerações
37
Exemplo
AG – 15000 Avaliações
20 Injetores / 20 produtores
VPL = 1.57*109
AG/AC - 15000 Avaliações
15 Injetores / 16 produtores
VPL = 1.77*109
38
Referências
• Robert G. Reynolds: An Introduction to Cultural
Algorithms.
• Robert G. Reynolds, and ChanJin Chung: A Testbed
for Solving Optimization Problems Using Cultural
Algorithms.
• Robert G. Reynolds, and ChanJin Chung: A Selfadaptive Approach to Representation Shifts in
Cultural Algorithms.
39
Fim
40