1 Algoritmos Culturais. 2 Sumário Introdução Objetivo Níveis do Algoritmo Cultural (AC)...

1

Algoritmos Culturais

2

Sumário

• Introdução

• Objetivo

• Níveis do Algoritmo Cultural (AC)

• Componentes

• Pseudo Código AG X AC

• Modelagem do AC

• Exemplo

• Referências

3

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).

4

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.

5

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

6

Introdução

• Sistema de dupla herança:

– genética e

– cultural

• pode adaptar-se melhor e responder com mais eficiência em problemas.

7

•Filosofia de Algoritmos Culturais: aquisição de conhecimento pela evolução da população euso do conhecimento para guiar a busca.

• Empregados em problemas numéricos para aumentar a eficiência da busca.

Objetivo

8

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.

Níveis do AC

9

Componentes do AC

Herança

População

Votação: Função de Aceitação

Espaço de Crença

Herança

Promoção: Função de Influência

Protocolo de Comunicação

Reprodução, Evolução

Função de Avaliação

• população, • espaço de crença e• protocolo de comunicação

10

Componente população é modelado por Algoritmo Genético, Programação Genética ou sistemas de Multi-Agentes entre outros.

Herança

População

Votação: Função de Aceitação

Espaço de Crença

Herança

Promoção: Função de Influência

Protocolo de Comunicação

Reprodução, Evolução

Função de Avaliação

Componentes do AC

11

Herança

População

Votação: Função de Aceitação

Espaço de Crença

Herança

Promoção: Função de Influência

Protocolo de Comunicação

Reprodução, Evolução

Função de Avaliação

O Espaço de Crença representa a influência que está sendo adquirida pela população durante o processo de evolução.

Componentes do AC

12

Herança

População

Votação: Função de Aceitação

Espaço de Crença

Herança

Promoção: Função de Influência

Protocolo de Comunicação

Reprodução, Evolução

Função de Avaliação

O protocolo de comunicação é usado para determinar a interação entre a população e o espaço de crença.

Componentes do AC

13

Procedimento básico do Algoritmos Genéticos:

Iníciot=0 ;primeira geraçãoinicializar população P(t) ;população inicial aleatóriaavaliar população P(t) ;calcula f(i) para cada

indivíduoenquanto (não condição_fim) faça

tt+1 ;próxima geraçãoselecionar P(t) de P(t-1)altera P(t) ;crossover e mutaçãoavaliar população P(t) ;calcula f(i) para cada

indivíduofim enquantofim

Algoritmo Genético

14

Procedimento básico do Algoritmos Culturais:

Iníciot=0 ;primeira geraçãoinicializar população P(t) ;população inicial aleatóriaInicializar Espaço de Crença EP(t)avaliar população P(t) ;calcula f(i) para cada indivíduoenquanto (não condição_fim) faça

Comunicação (P(t), EP(t)); ;votaçãoAtualização EP(t); ;uso de operadores

culturaisComunicação (EP(t), P(t)); ;promoçãott+1 ;próxima geraçãoselecionar P(t) de P(t-1)altera P(t) ;crossover e mutaçãoavaliar P(t) ;calcula f(i) para cada indivíduo

fim enquantofim

Algoritmo Cultural

15

Componentes do Algoritmo Cultural

Representação da População

Representação do Espaço de Crença

Operadores Culturais

Protocolo de Comunicação

16

População

População do Algoritmo Cultural é modelada por Algoritmo Genético, Programação Genética, etc.

17

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)

18

• GeneralizaçãoCaso 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çãoCaso 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.

Operadores Culturais

19

• FusãoEste é 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ãoEste é 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.

Operadores Culturais

20

Ajuste do Espeço de Crença com Operadores

Todo espaço de

busca

Espaço de Crença

21

Ajuste do Espaço de Crença com Operadores

Especialização

Espaço de Crença

22

Ajuste do Espaço de Crença com Operadores

Espaço de crença

23

Ajuste do Espaço de Crença com Operadores

Generalização

Espaço de Crença

24

Ajuste do Espaço de Crença com Operadores

Espaço de Crença

25

Ajuste do Espaço de Crença com Operadores

Espaço de Crença

Fissão

Espaço de Crença

26

Ajuste do Espaço de Crença com Operadores

Espaço de Crença

Espaço de Crença

27

Ajuste do Espaço de Crença com Operadores

Fusão

Espaço de Crença

28

Protocolo de Comunicação

Processo de Votação e Promoção

Herança

População

Votação

Espaço de Crença

Herança

Promoção

Reprodução, Evolução

Função de Avaliação

29

Protocolo de Comunicação

Processo de Votação e Promoção

Herança

População

Votação

Espaço de Crença

Herança

Promoção

Reprodução, Evolução

Função de Avaliação

melhores indivíduos de uma geração do AG influenciam o espaço de crença

30

Protocolo de Comunicação

Processo de Votação e Promoção

Herança

População

Votação

Espaço de Crença

Herança

Promoção

Reprodução, Evolução

Função de Avaliação

melhores indivíduos de uma geração do AG influenciam o espaço de crença

15 2

X YCromossomo

(8 15) ( 2 10)

Espaço de Crença

31

Protocolo de Comunicação

Processo de Votação e Promoção

Herança

População

Votação

Espaço de Crença

Herança

Promoção

Reprodução, Evolução

Função de Avaliação

crenças atualizadas influenciam um componente da

população

15 2

X YCromossomo

(8 15) ( 2 10)

Espaço de Crença

32

Protocolo de Comunicação

Processo de Votação e Promoção

Herança

População

Votação

Espaço de Crença

Herança

Promoção

Reprodução, Evolução

Função de Avaliação

crenças atualizadas influenciam um componente da

população

15 2

X YCromossomo

(8 15) ( 2 10)

Espaço de Crença

10 7

X YAv = Av + Bonus

33

Exemplo

• Sistema de Otimização de Alternativas para Desenvolvimento de Campos de Petróleo

Dimensão do Grid de Reservatório

Curva de produção

Algoritmo de Otimização

AG ou AG / AC Operadores

Simulador de Reservatórios

(IMEX)

Cálculo do

VPL

Alternativa

DVVPL

bbs/t

)(tQ

t

ABT

Poços produtores

Poços injetores

Plataforma

Preço do Petróleo

Avaliação

Dimensão das Células do Grid

34

Exemplo

• Modelagem do Cromossomo

X Y Z

Dir Dist X Y Z

Dir Dist X Y

Máscara de Ativação

Cromossomo

Verticais Horizontais

Injetores Produtores

X Y Z

Dir Dist

Injetores Produtores

0 0 1 1 0 0 1 1

X Y Z

Dir Dist X Y X Y X Y

35

Exemplo

• Modelagem do Espaço de Crença

[3 12] [15 29] [1 29] [1 1] [0 1] [-27 23] [24 24] [23 24]

G(0) G(1) G(2) ................................................................... G(n)

Espaço de Crença

Crença do Gene (2)

x y z direção distância

36

• Gráfico De desempenho do Algoritmo Otimizador

Exemplo

AG

15000 Avaliações

AG/AC

15000 Avaliações

Score

8.00E+089.00E+081.00E+091.10E+091.20E+091.30E+091.40E+091.50E+091.60E+091.70E+09

1 10 19 28 37 46 55 64 73 82 91 100 109 118 127 136 145 154

Gerações

Av

alia

çõ

es

Score

5.0000E+08

7.0000E+08

9.0000E+08

1.1000E+09

1.3000E+09

1.5000E+09

1.7000E+09

1.9000E+09

1 10 19 28 37 46 55 64 73 82 91 100 109 118 127 136 145

Gerações

Av

alia

çõ

es

8.2*108

15*108

18*108

5.1*108

37

Exemplo

• Gráfico de desempenho do AG x AG/AC

Score

4,00E+08

6,00E+08

8,00E+08

1,00E+09

1,20E+09

1,40E+09

1,60E+09

1,80E+09

2,00E+09

1 8 15 22 29 36 43 50 57 64 71 78 85 92 99 106 113 120 127 134 141 148 155

Gerações

Ava

liaçõ

es

Teste 3 Teste 7

38

AG – 15000 Avaliações AG/AC - 15000 Avaliações

20 Injetores / 20 produtoresVPL = 1.57*109

15 Injetores / 16 produtoresVPL = 1.77*109

Exemplo

39

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 Self-adaptive Approach to Representation Shifts in Cultural Algorithms.

40

Fim