Python, PSO e Google Elevation

05fev11

Depois que comecei a participar do CIRG, Computational Intelligence Research Group, assisti várias palestras onde a técnica do PSO e sua variações eram utilizadas.Para quem não conhece o PSO (Particle Swarm Optimization) é uma técnica de computação inteligente criado pelos pesquisadores Kennedy e Eberhart em 1995. Sua descoberta foi feita a partir dos estudos do comportamento dos pássaros em um bando em vôo. Enfim, não vou me ater muito a explicar o PSO porque esse não é o foco mas para quem não conhece, recomedo a leitura do artigo que o propôs.

Num desses momentos de loucura eu tive a seguinte ideia:

“Se eu usasse o PSO e a API do Google Elevation para tentar encontrar o Everest?”

Dai para frente foi só implementar o PSO com a ajuda do @serginhfr e ver o que ia acontecer. Alguns detalhes sobre a implementação:

  • O espaço de busca era a Terra ou seja duas dimensões. Latitude: -90° a 90° e Longitude -180° a 180°.
  • Se por acaso a particula saisse do espaço de busca, seria como se ela tivesse dadouma volta na terra. Ex.: Logitude: -200° se tornaria 20°.
  • Foi usado a topologia de comunicação global (Gbest).
  • A função de fitness da particula é calculada fazendo uma requisição a API do Elevation passando o local em que a partícula se encontra no espaço de busca.
import simplejson
from urllib import urlopen
ELEVATION = "http://maps.google.com/maps/api/elevation/json?locations=%f,%f&sensor=false"

class Particle(object):
...
def _fitness(self,position):
   site = ELEVATION %(position.latitude,position.longitude)
   dicionario = simplejson.load(urlopen(site))
   if dicionario['status'] == 'OK':
      fit = dicionario['results'][0]['elevation']
   else:
      raise Exception # Criar uma exception digna.
   return fit

O retorno da requisição a o Elevation é um arquivo json – poderia ser um xml – como esse aqui . É utilizado o metodo load do modulo simplejson para transformar as informações contidas no json em um Dicionário (dict) que é um tipo padrão de Python.

  • A forma de atualizar a velocidade foi a seguinte:
from random import random
class Particle(object):
   ...
   def update_velocity(self,i,gbest):
       w = (0.9-(0.5*(i/self.iteracoes)))
       self.velocity.x = w * self.velocity.x + random()*2.05*(self.pbest.longitude - self.position.longitude) + random()*2.05*(gbest.position.longitude -self.position.longitude)
       self.velocity.y = w * self.velocity.y + random()*2.05*(self.pbest.latitude - self.position.latitude) + random()*2.05*(gbest.position.latitude -self.position.latitude)

Resultados!
Adianto logo que o mais próximo que ele chegou do Everest, foi um ponto na China. Basicamente a melhor partícula sempre se encontra na Antártida. O que me leva a crer que essa minha implementação foi baseada no comportamento dos pinguins  😀

A minha explicação:

  • Realmente a Antártida possui pontos elevados, o 6º ponto mais alto é o Vinson Massif na Antártica com 4.892 m.
  • O formato de topologia de comunicação GBest tem maior probabilidade de deixar o exame presas em pontos de minimo, como o Visson Massif.

Por enquanto ainda não achei o Everest mas quando fizer novos testes mudando o formato de comunicação espero ter melhores resultados.

Visão dos 8 pontos mais altos do mundo

Anúncios


One Response to “Python, PSO e Google Elevation”


  1. 1 Tweets that mention Python, PSO e Google Elevation « Blog do Rodrigo Lira -- Topsy.com

Deixe um comentário

Preencha os seus dados abaixo ou clique em um ícone para log in:

Logotipo do WordPress.com

Você está comentando utilizando sua conta WordPress.com. Sair / Alterar )

Imagem do Twitter

Você está comentando utilizando sua conta Twitter. Sair / Alterar )

Foto do Facebook

Você está comentando utilizando sua conta Facebook. Sair / Alterar )

Foto do Google+

Você está comentando utilizando sua conta Google+. Sair / Alterar )

Conectando a %s


%d blogueiros gostam disto: