Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

DE_GS_CUDA_NEW

Desenvolvendo um algoritmo de Evolução Diferencial híbrido com Golden Search em CUDA
by

Guilherme Nogueira

on 4 May 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of DE_GS_CUDA_NEW

DE + GS + CUDA
Implementando um algoritmo de evolução diferencial híbrido usando Golden Search em CUDA
DE
DE - Relembrando
DE (Differential Evolution) é uma heurística de otimização baseada em um população que evolui em busca da solução do problema.
DE - Pontos Fortes
- Fácil implementação
- Algoritmo pequeno
- Simples de usar
- Rápida convergência
- Robusto
DE - Pontos Fracos
- Explora uma quantidade exagerada de pontos
- Superfícies multimodais tendem a desacelerar demais o processo de convergência
Idéia Básica:
Uma população aleatória de tamanho Tpop é criada
segundo uma distribuição normal sobre o espaço de
decisão D.
Minimizar uma função f da seguinte forma:
Observação:
DE/BEST/1 X'
X'filho = Xbest + F*(Xr - Xs)
DE/CUR-TO-BEST/1
X'filho = Xi + F*(Xbest - Xi) + F*(Xs - Xt)
DE/BEST/2
X'filho = Xbest + F*(Xs - Xt) + F*(Xu - Xv)
DE/RAND/2
X'filho = Xr + F*(Xs - Xt) + F*(Xu - Xv)
A equação (1) define um esquema de busca denominado (DE/rand/1) Outras variações foram proposta posteriormente, a saber:
Em seguida efetua-se uma operação de crossover sobre o individuo mutado X'filho:
Cada gene de X'filho é trocado com o gene de Xi com uma dada probabilidade CR,
gerando Xfilho.
Se Xfilho for melhor que Xi, os dois são trocados.
GS
CUDA
DE+GS
DE+GS+CUDA
Golden Search (GS) é um algoritmo simples de busca local.
Ele busca o mínimo da função realizando partições no espaço de busca.
No contexto corrente, o Goden Search é usado para estimar o melhor valor ótimo de F.
A cada geração, para cada indivíduo Xi da população,
três individuos Xr, Xs e Xt são (pseudo-)aleatoriamente
escolhidos.
Um indivíduo-filho temporário é criado da seguinte maneira:

X'filho = Xt + F*(Xr - Xs) (1)

Onde F é um número real que controla o módulo
do vetor de exploração (Xr - Xs), determinando
a distância da busca em relação a Xt.
Esse operador é chamado de mutação.
O GS é capaz de achar em poucas iterações o mínimo de função monomodais.
Certamente a função g que define F não tem essa característica.
Tirronen et al argumentam que para pontos próximos, g é provavelmente unimodal
e o GS irá convergir para o valor ótimo de F.
Avaliação Experimental
Resultados
Sem Ruído
DE
1.8183e-05 (3.5153e-05)
DE+GS
1.8506e-05 (3.6752e-05)
Com Ruído
DE
0.002536 0.004537
DE+GS
0.002536 0.004536
Sem Ruído
DE
3.0331e-08 1.1510e-07
DE+GS
4.0234e-08 1.6323e-07

Com Ruído
DE
0.002536 0.004537
DE+GS
0.002536 0.004536
Resultados
Sem Ruído
DE
0.4257 1.6297
DE+GS
0.1301 0.6243

Com Ruído
DE
0.3527 1.8414
DE+GS
0.1121 0.8941
Resultados
Resultados
Sem Ruído
DE
0.01992 0.04595
DE+GS
0.008587 0.02248

Com Ruído
DE
-0.5160 0.9280
DE+GS
-0.5154 0.9300
Foram escolhidas 4 funções de benchmark para avaliar o desempenho
do algoritmo proposto. Para cada função rodamos 30 vezes cada algoritmo
e mais 30 vezes para a mesma função com um ruído gaussiano aleatório.
CUDA (Compute Unified Device
Architecture) é uma arquitetura de
computação paralela desevolvida
pela NVIDIA para rodar em GPU's
usando o poder do processamento
paralelo das placas de vídeo.
Conclusão
Full transcript