Pages

Showing posts with label framework. Show all posts
Showing posts with label framework. Show all posts

Slides for Scientific Computing Meeting: Benchy and GeoMapper Visualization

Sunday, April 7, 2013



Hi all,

Yesterday it happened the XXVI local meeting of the Python Users Group at Pernambuco (PUG-PE).  In the occasion I had the opportunity to present two talks about scientific computing with python.


The first one was the lightweight framework for benchmark analysis on Python Scripts called Benchy, which I developed for about one week to help me on checking performance of several algorithms that I developed in Python.  I covered the framework at my last post which can be found here.


Here are the slides for the presentation:




The second talk was about a new type of visualization that I developed for social network analysis in order to check the degree of connections between the users at the socialnetwork using their geolocation data to present in a map.

The result was beautiful plots using this new type of visualization.  Amazing!

The slides are available here:



I hope you enjoy the slides, any further information feel free to comment!

Regards,

Marcel Caraciolo

Performing runtime benchmarks with Python Monitoring Tool Benchy

Friday, March 22, 2013


Hi all,

I've been working on in the last weeks at a little project that I developed called benchy.  The goal of benchy is answer some trivial questions about which code is faster ?  Or which algorithm consumes more memory ?  I know that there are several tools suitable for this task, but I would like to create some performance reports  by myself using Python.   

Why did I create it ?  Since the beginning of the year I decided to rewrite all the code at Crab, a python framework for building recommender systems.  And one of the main components that required some refactoring was the pairwise metrics such as cosine, pearson, euclidean, etc.  I needed to unit test the performance of several versions of code for those functions. But doing this manually ? It's boring. That's why benchy came for!


What benchy can do ?

Benchy is a lightweight Python library for running performance benchmarks over alternative versions of code.  How can we use it ?

Let's see the cosine function, a popular pairwise function for comparing the similarity between two vectors and matrices in recommender systems.




Let's define the benchmarks to test:



With all benchmarks created, we could test a simple benchmark by calling the method run:


The dict associated to the key memory represents the memory performance results. It gives you the number of calls repeat to the statement, the average consumption usage in units . In addition, the key 'runtime' indicates the runtime performance in timing results. It presents the number of calls repeat following the average time to execute it timing in units.

Do you want see a more presentable output ? It is possible calling the method to_rst with the results as parameter:


Benchmark setup
import numpy
X = numpy.random.uniform(1,5,(1000,))

import scipy.spatial.distance as ssd
X = X.reshape(-1,1)
def cosine_distances(X, Y):
    return 1. - ssd.cdist(X, Y, 'cosine')
Benchmark statement
cosine_distances(X, X)
namerepeattimingloopsunits
scipy.spatial 0.8.0318.3610ms


Now let's check which one is faster and which one consumes less memory. Let's create a BenchmarkSuite. It is referred as a container for benchmarks.:

Finally, let's run all the benchmarks together with the BenchmarkRunner. This class can load all the benchmarks from the suite and run each individual analysis and print out interesting reports:



Next, we will plot the relative timings. It is important to measure how faster the other benchmarks are compared to reference one. By calling the method plot_relative:




As you can see the graph aboe the scipy.spatial.distance function is 2129x slower and the sklearn approach is 19x. The best one is the numpy approach. Let's see the absolute timings. Just call the method plot_absolute:



You may notice besides the bar representing the timings, the line plot representing the memory consumption for each statement. The one who consumes the less memory is the nltk.cluster approach!

Finally, benchy also provides a full repport for all benchmarks by calling the method to_rst:




Performance Benchmarks

These historical benchmark graphs were produced with benchy.
Produced on a machine with
  • Intel Core i5 950 processor
  • Mac Os 10.6
  • Python 2.6.5 64-bit
  • NumPy 1.6.1

scipy.spatial 0.8.0

Benchmark setup
import numpy
X = numpy.random.uniform(1,5,(1000,))

import scipy.spatial.distance as ssd
X = X.reshape(-1,1)
def cosine_distances(X, Y):
    return 1. - ssd.cdist(X, Y, 'cosine')
Benchmark statement
cosine_distances(X, X)
namerepeattimingloopsunits
scipy.spatial 0.8.0319.1910ms

sklearn 0.13.1

Benchmark setup
import numpy
X = numpy.random.uniform(1,5,(1000,))

from sklearn.metrics.pairwise import cosine_similarity as cosine_distances
Benchmark statement
cosine_distances(X, X)
namerepeattimingloopsunits
sklearn 0.13.130.18121000ms

nltk.cluster

Benchmark setup
import numpy
X = numpy.random.uniform(1,5,(1000,))

from nltk import cluster
def cosine_distances(X, Y):
    return 1. - cluster.util.cosine_distance(X, Y)
Benchmark statement
cosine_distances(X, X)
namerepeattimingloopsunits
nltk.cluster30.010241e+04ms

numpy

Benchmark setup
import numpy
X = numpy.random.uniform(1,5,(1000,))

import numpy, math
def cosine_distances(X, Y):
    return 1. -  numpy.dot(X, Y) / (math.sqrt(numpy.dot(X, X)) *
                                     math.sqrt(numpy.dot(Y, Y)))
Benchmark statement
cosine_distances(X, X)
namerepeattimingloopsunits
numpy30.0093391e+05ms

Final Results

namerepeattimingloopsunitstimeBaselines
scipy.spatial 0.8.0319.1910ms2055
sklearn 0.13.130.18121000ms19.41
nltk.cluster30.010241e+04ms1.097
numpy30.0093391e+05ms1

Final code!

I might say this micro-project is still a prototype, however  I tried to build it to be easily extensible. I have several ideas to extend it, but feel free to fork it and send suggestions and bug fixes.  This project was inspired by the open-source project vbench, a framework for performance benchmarks over your source repository's history. I recommend!

For me, benchy will assist me to test several pairwise alternative functions in Crab. :)  Soon I will publish the performance results that we got with the pairwise functions that we built for Crab :)

I hope you enjoyed,

Regards,

Marcel Caraciolo

Crab - Python Framework for Building Recommender Engines Video at Scipy 2011 Conference

Thursday, July 28, 2011

Hi all,

My lecture at Scipy Conference 2011 is already available on-line in video, so you can watch me now presenting about our work at Muricoca Labs called "Crab - A Python Framework for Building Recommender Engines"  .  It is a work that I am developing with some machine learning developers as an alternative for python developers that want to work with recommender engines writing Python code.

Further information , it may be found here at the official home project. About my experience at Scipy, you can find at this post.

Here the link for the video,






Cheers,

Marcel Caraciolo

Scipy Conference 2011 and my participation!

Tuesday, July 19, 2011

Hi all,

Last week I was at the Scipy 2011 Conference at Austin, Tx. My first international conference as also my first lecture international! The Scipy Conference is an annual meeting for scientific computing developers and researchers that use python scientific packages in their research or work.  It was a great opportunity for meeting new python developers, know more about what's happening in scientific python nowadays and to learn about Scipy, Numpy and Matplotlib, considered the standard libraries for developers who wants start to develop in the scientific world.




At the first day of the conference, I had the opportunity to learn more about Numpy, a widely used library for numerical computations in Python as also learn more about the Scikit-learn framework, a great open-source toolkit for machine learning developers written in Python, Numpy and Scipy.  

You can access both tutorials available here at the Scipy Conference Tutorials WebPage.  Numpy is an amazing library, and what I learned I started already applied at the library I am currently working on called Crab for building recommender systems.   The Scikit-learn is also an interesting framework written in Scipy, Numpy and Matplotlib with several machine learning techniques and has as one main features the easy-to-use interface with lots of examples and tutorials for starters and beginners in machine learning.  It works so smoothly that I decided to use it as dependency of the Crab framework.

The second day started with more advanced tutorials, specially on Global Arrays with Numpy for  High performance computation. A quite powerful effort in this feature and I believe that soon will be added to the Numpy core. 

The another tutorial was about an introduction to Traits, Matplotlib and Chaco - great tools for creating nice user interfaces and plotting charts. One of the best parts of this tutorial was easily to create nice interfaces and animated plottings with a few lines of code.  Take a look of what you can do here or even see a real-time animated plotting with Matplotlib.








Traits and Chaco are part of the EPD package developed by the company Enthought, whose one of the co-founders is one of the main developers and founders of Numpy! Yeah :D Those frameworks allow easily create nice interfaces only using models concepts. If you want to learn more, please check out the tutorials as the official website about how to download, install and use it.


Another keynote interesting was about the Ipython, the incremented shell for scientific Python developers. What amazed me was when he showed the matplotlib embedded at the shell instead of opening a new window! The work around the Ipython has been fantastic, with several features for python developers! I extremely recommend!




The rest of the conference was dedicated to keynotes and talks about currently works on data science, core technologies and data mining with Python, Scipy , Numpy and related libraries.  I had the opportunity of giving the lecture - Crab - A Python Framework for Building Recommender Systems written by me, Bruno Melo and Ricardo Caspirro, actually the main contributors for this work.  The idea is to provide for python developers a recommender toolkit so they can easily create, test and deploy recommender engines with simple interfaces written with the scientific python packages such as Numpy, Scipy and Matplotlib.




You can check out my slides at the Scipy Conference here.


The project is currently being developed by the non-profitable organization called Muriçoca, that we decided  to create to manage and develop the Crab Framework. 


One of the best keynotes was the presentation of Hilary Manson, the Data Scientist at bit.ly.  She gave a funny lecture about her work and the current challenges with handling with large data sets and lots of URL-shortening happening at the backend of Bit.ly. It is quite amazing the amount of data and what you can do and extract useful information from all this data.

At least, I decided also to give a lighting talk about Mining the Scipy Lectures. A simple lecture to show what you can do with the data from the Scipy Conference Schedule and play with it. I used some NLP techniques and clustered based on the most frequent topics to check how was distributed the lectures at Scipy based on the keywords from their titles.  To visualize I used the Graph Visualization tool Ubigraph to show in 3D the clusters generated (by the way I used the K-means algorithm to cluster). 




The slides are also available here and the source code here.

3D Lectures Clusters


Soon I will release the PDF with the article submitted as also the video with both keynotes that I presented.  It was an amazing conference at Austin, making new friends and lots of new partners! :D I expect to be there next year, absolutely!  One of my goals this year also is to prepare a scientific computing course using Python, wait for more information soon here at the blog (it will include matplotlib, scipy and numpy)!

Cheers,

Marcel Caraciolo

Keynote about Recommender Systems at CIN- UFPE

Tuesday, June 21, 2011

Hi all,

I'dl like to share my presentation about recommender systems that I lectured at the Federal University of Pernambuco (UFPE) .  It was an introduction for who wants to know more about this machine learning research field as also my contributions to this area.




One of them is the development of the framework for building recommender engines written in Python called Crab.  Soon I will release more information and a paper that I wrote about the framework to submit to Scipy 2011 Conference.

Stay tuned!

Regards,

Marcel Caraciolo

Python and Machine Learning: Introductory Keynote in Portuguese

Monday, May 30, 2011


Dear readers,

I am sharing my last keynote at I Information Technology and Knowledge Management Symposium at IFPE (located at Recife, Pernambuco- Brazil) about Python and Machine Learning. It is a introductory keynote for students of that institution about machine learning and how Python is applied and useful for scientists, researchers and developers for building intelligent systems.

It is in portuguese.  The link for the slides.





Thanks for the the staff organization team for the opportunity.

Best regards,

Marcel Caraciolo

Crab: A Python Framework for Building Recommendation Engines

Sunday, May 8, 2011

Hi all,

In this weekend I presented a lecture at the XII Python User Group Pernambuco Meeting about the framework I've been working on at these last months. The framework is called Crab and it is a Python library for building recommendation engines. Its main goal is to be an alternative for machine learning researchers and developers for use standard-of-the-art implemented recommendation algorithms, evaluate and extend it by building new techniques using the basic core provided by the framework.   

Me presenting the Crab : A Python framework for building recommendation engines

The framework has started in 2010, as a support toolkit for my master degree thesis about recommendation engines. I've implemented the Collaborative Filtering techniques as also the evaluation metrics used in recommendations (Precision, Recall, F1-Score, RMSE, etc). But since last month (April,2011) I decided to give the framework a shot to become more visible and bring more contributors for the project. The project became part of a Non-profitable organization called Muriçoca Labs, a team of  developers and researchers interested in Machine Learning and Artificial Intelligence. We also decided to    migrate all the core of the project using the scientific libraries Numpy, Scipy and Matplotlib, since the speed and the legibility of the code were the main advantages of these toolkits.   

The project started last month and had its first sprint where the team is focused on rewriting all the code of the old crab to this new release as also make it a independent project member of the Scikit repository - Sub-projects of Scipy Framework and a sub-module of the Scikit-Learn  (a popular python framework for machine learning algorithms). 

We are quite excited and working harder! By the way the Crab framework is already in production providing the recommendations of the brazilian social network AtePassar.  We are with lot of ideas and features such as content based filtering algorithms, recommendations as services providing REST APIs and Databases Models Support.

If you are interested in the project and want to know how to join us or use our projects, please let me know and add a comment below and I will be glad to help you!  The project is at the beginning, but we are working harder to see it in action as a possible alternative for Python developers that want to work with this hot topic in the data mining and web services: Recommender Systems.

Below I provide the slides that I presented about the project at the lecture.






Meet the Muriçoca Labs here  and the link for the Crab framework here.

Regards,

Marcel Caraciolo

My lecture about Recommender Systems at IX Pernambuco Python User Group Meeting and my contributions.

Tuesday, December 7, 2010

Hi all,

It has been while since my last post, but my master thesis is taking a lot of time available. Soon I will come back with posts and content related to what I am working now.

But the main reason of this post is to publish my lectures that were recorded at the IX Pernambuco Python User Group Meeting (PUG-PE) last month in November.  I had the opportunity to talk more about what I am studying, which is related to the topics of recommender systems and a lighting talk about lighting talks!

But since this blog concerns about artificial intelligence,  I will focus on the recommender systems. In this lecture I've introduced the main concepts behind recommender systems, how it works, the advantages and drawbacks of each classing filtering algorithm.  Both examples presented were used in my lecture at PythonBrasil (a main meeting that joins all Python Users of Brazil).  The result of this project will be explained in the future in two posts. But let me explain my main contributions in this field.

One is my work currently at the startup Orygens, where I am developing a novel recommender system applied on social networks. The idea is to recommend users and content to the users of a brazilian social network called AtePassar.

Main Profile of AtePassar



The other contribution is the development of a framework written purely in Python called Crab.  It was originally idealized by me to be a simple easy-to-use recommendation engine framework in order to  be applied on any domains. Besides it will be used to test new approaches, since it will be easy to plug-in new recommender algorithms and test them with the evaluation tools available.  This project is open-source is completely available at my account on GitHub.com.

The main page of the Crab Project


Today we have four collaborators and we are planning to keep going forward with some demos and a distributed computing framework totally integrated with Crab.  More information I will provide soon here at my blog with some demonstrations.


My video about Recommender Systems.  The video is in portuguese.








Wait for news!  Please any further information, contact me!

Marcel Caraciolo

Know how many retweets (RT) and the user that you most retweet at Twitter! -Text Mining

Saturday, November 21, 2009


Hi all,

While playing with some collective intelligence techniques under the Twitter, i and some friends developed a simple application with the original idea of my friend Bruno Melo and some suggestions of my friend Ricardo Caspirro to count the number of retweets that you do on twitter and the users that you most retweet. We decided to give it the name of BabaOvo (A portuguese word that means that you are a pamper or flatter) . The idea is to know how many retweets i've done in all my statuses profile and whose the users i retweeted (RT) most.

The code is so simple and we've done it all in Python! Soon i'll release a official version and the source code so you can you it on your own.

I've made a test with my twitter username 'marcelcaraciolo' , and i've discovered some really interesting insights: ' I like the user lucianans (hehhe she's my date)' , 'The users cinlug, larryolj and the user tarantulae are related to python development and open-source: what i like a lot' . 'marcelobarros, telmo_mota, croozeus are associated with mobile topics: great guys to follow if you want to know about mobile area' and at least 'reciferock, davidsonFellipe and macmagazine: all personal interests: rock music, blogs and the apple world' !

It's amazing what you can find about you only using this simple technique of text mining ! Data mining is a powerful area and natural language processing is incredible if you know how to handle it. I am playing with it and soon i'll publish here some results of a project that i am doing with recommendations and Twitter networking!

For now, take a look on the pie chart that i plot after running the babaOvo application. I've put only the top-10 users! The chart was drawn with the Matplotlib Python framework!



BabaOvo Pie Chart : Frequency Retweets



That's all!

Marcel Caraciolo

Introdução à Inteligência de Enxame - Otimização por Enxame de Partículas (PSO)

Wednesday, April 8, 2009





Olá pessoal,

Neste novo tutorial abordarei um novo ramo na área de inteligência artificial, e de certo modo, com grande motivação. Não que os outros artigos não tenham sido motivantes, mas é justificado pelo fato que este tutorial é baseado na área de conhecimento que preparei minha tese de conclusão de curso de graduação: Multi-Ring: Uma nova topologia para o algoritmo de otimização por enxame de partículas (PSO).

Mas antes de entrarmos em detalhes sobre o que é PSO ou enxame de partículas, é necessário entendermos o conceito de inteligência de enxame (swarm intelligence).




Enxame de formigas colaborando para criar uma ponte viva.



O que é Inteligência de enxame ?

Swarm Intelligence (Inteligência de enxame) é o termo utilizado para designar sistemas de inteligência artificial onde o comportamento coletivo dos indivíduos em uma população causa simples soluções coerentes ou padrões a surgir.

O termo "enxame" (ou população) é utilizado de forma genérica para se referir a qualquer coleção estruturada de agentes capazes de interagir. O exemplo clássico de um enxame é um enxame de abelhas. Entretanto, de maneira similar podemos considerar também que outros sistemas, como por exemplo uma colônia de formigas, podem ser vistas como um enxame, onde os agentes são as formigas; uma revoada de pássaros que é um enxame, onde os agentes são os pássaros e até um engarrafamento, onde os agentes são os carros. A noção de enxame sugere um aspecto de movimento coletivo no espaço, todavia, como em um enxame de pássaros, estamos interessados em todos os tipos de comportamentos coletivos, não somente espacial.
Logo, podemos dizer que as interações coletivas de todos os agentes dentro do sistema muitas vezes leva a algum tipo de comportamento ou inteligência coletiva. Este tipo de inteligência artificial inclui qualquer tentativa de projetar algoritmos ou dispositivos distribuídos de solução de problemas sem ter um controle centralizado, inspirado no comportamento coletivo de agentes sociais e outras sociedades animais.
A inteligência coletiva é uma propriedade de sistemas compostos por agentes não (ou pouco) inteligentes com capacidade individual limitada, capazes de apresentar comportamentos coletivos inteligentes. Tais comportamentos seguem as seguintes propriedades:


  • Proximidade: Os agentes devem ser capazes de interagir .
  • Qualidade: Os agentes devem ser capazes de avaliar seus comportamentos.
  • Diversidade: Permite ao sistema reagir a situações inesperadas.
  • Estabilidade: Nem todas as variações ambientais devem afetar o comportamento de um agente.
  • Adaptabilidade: Capacidade de se adequar a variações ambientais.

Exemplos de sistemas de inteligência de enxame

Otimização por Colônia de Formigas (ANT Colony Optimization - ACO)

O comportamento da colônia de formigas tem sido um dos mais populares modelos de comportamento de enxame. Formigas por si só podem parecer agir de forma aleatória e sem qualquer efeito discernível, mas quando a interação entre as formigas são tomadas em conjunto, emerge uma inteligência coletiva e de comportamento que tem a capacidade de resolver uma série de problemas. A idéia por trás deste algoritmo é a busca de um melhor caminho em um conjunto de rotas baseado no comportamento das formigas procurando um caminho entre o seu formigueiro (colônia) e o local do alimento. Uma técnica probabilística muito poderosa para resolver problemas computacionais de otimização.

O algoritmo de otimização por colônia de formigas já foi aplicada na solução de diversos problemas de otimização combinatória nos últimos anos, como roteamento de otimização de redes de comunicação, programação de fábricas e roteamento de veículos. Não entraremos em detalhe agora sobre o ACO (Ant Colony Optimization) já que não é o foco deste artigo, mas fiquem à vontade para descobrir mais sobre o algoritmo e sua implementação. Em outras oportunidades poderemos detalhar mais este algoritmo. Mais informações sobre o mesmo podem ser encontradas neste link.
Este artigo irá tratar de outro algoritmo popular na área de inteligência de enxame , o algoritmo de otimização por enxame de partículas (PSO).


Otimização por enxame de partículas (Particle Swarm Optimization - PSO)

O algoritmo de otimização por enxame de partículas, por outro lado, é um tipo de inteligência de enxame inspirado no comportamento de bandos de pássaros. A busca por alimentos e a interação entre aves ao longo do vôo são modeladas como um mecanismo de otimização. No caso, a área sobrevoada é equivalente ao espaço de busca e encontrar o local com comida corresponde a encontrar a solução ótima. O algoritmo é modelado por pássaros (doravante chamados de partículas) que fazem uso de sua experiência e da experiência do próprio bando para encontrar a melhor região do espaço de busca.




Aves voando "alinhadas" em busca de alimento



Há anos vem sendo estudado o comportamento social de alguns grupos de animais como a organização de abelhas, formigas e pássaros na busca de alimentos ou novos locais para estabelecer sua nova moradia. Este último grupo, em especial despertou um grande interesse de alguns pesquisadores, na década de 80, onde se destaca dentre eles o biológo Frank Heppner. Após diversas observações sobre o comportamento de bando de pássaros em revoada, Heppner decidiu modelar aquela inteligência coletiva para usá-la em métodos de busca para solução de problemas. Os estudos de Heppner consideravam que o comportamento de várias espécies de pássaros, em bando ao longo do vôo, fazia o uso de alguma lógica e de alguma forma de comunicação. Após vários estudos e observações, Heppner descreveu o raciocínio por trás daquele comportamento, qualificando-o como comportamento social.

James Kennedy e Russel Eberhart, inspirados no comportamento social dos pássaros estudados por Heppner, desenvolveram uma técnica de otimização que veio a ser conhecida como enxame de partículas. Essa denominação se deu, pois se notou que o modelo escrito por Heppner demonstrava características de um enxame inteligente, onde seus membros que apresentavam tal comportamento foram generalizados para o termo partículas.



Não só o nome do algoritmo, como os demais aspectos do modelo estudado por Heppner ganharam uma nova conotação. Fazendo uma analogia, o termo partícula foi adotado para simbolizar os pássaros e representar as possíveis soluções do problema a ser resolvido. A área sobrevoada pelos pássaros é equivalente ao espaço de busca e encontrar o local com comida, ou o ninho, corresponde a encontrar a solução ótima.



Para que o bando de pássaros sempre se aproxime do objetivo, ao invés de se perder ou nunca alcançar o alvo focado, utiliza-se o indicador denominado fitness, função que irá avaliar o desempenho das partículas. Para alcançar o alvo focado, sejam os alimentos ou os ninhos, os pássaros fazem uso de suas experiências e da experiência do próprio brando.



O termo indicador da experiência ou conhecimento individual de cada partícula, isto é, seu histórico de vida, é o pbest. Em uma abordagem mais simples, o responsável por representar o conhecimento do enxame como um todo é o gbest. A Tabela 1 apresenta de forma resumida as nomenclaturas descritas acima:






O algoritmo de técnica de otimização por enxame de partículas é um algoritmo que possui uma população de partículas, onde cada partícula representa uma possível solução para o problema de otimização. Cada partícula do exame pode ser representada por um objeto que possui associado a ele um vetor posição, isto é, a posição da partícula no espaço de busca, e um vetor velocidade, responsável por guiar as mudanças da posição das partículas durante a execução do processo.



A idéia é que as partículas voem pelo espaço de busca (mudanças de posição) tendo suas velocidades atualizadas dinamicamente de acordo com o histórico das experiências individuais e coletiva de todo o enxame. Logo, a evolução do algoritmo do PSO está associada à trajetória percorrida pelo enxame e ao tempo gasto para encontrar a melhor solução do problema.



O algoritmo básico de otimização por enxame de partículas pode ser descrito brevemente utilizando os seguintes passos: dada uma população inicial de partículas, atualiza-se o vetor posição a partir do vetor velocidade de cada partícula até que se atinja o critério de parada pré-definido. A figura abaixo ilustra essa lógica:

Fluxograma-Algoritmo PSO

O enxame é inicializado com os valores dos vetores de velocidade e posição gerados aleatoriamente. A primeira iteração do algoritmo inicia com a atribuição de valores aos parâmetros da equação de velocidade. Definem-se então os valores referentes ao enxame, constantes e o critério de parada. Tendo já definido os valores para posição das partículas e suas respectivas velocidades, aplica-se o cálculo do fitness a cada partícula desta população. Conforme explicado anteriormente, o fitness avalia o desempenho da partícula. Com as partículas do enxame avaliadas, extraem-se os pbest e o gbest, isto é, a melhor posição encontrada pela partícula e pelo enxame. Depois as velocidades e as posições de cada partícula do enxame são atualizadas. Diante das novas posições, caso o critério de parada tenha sido atingido, a solução do problema encontrada é apresentada. Caso contrário, aplica-se novamente o fitness a este enxame, atualizam-se os valores de pbest e gbest, caso seja apresentada uma solução melhor, seguido da velocidade e posição de cada partícula do enxame. O laço prossegue até o critério de parada ter sido atingido.



Existem duas variantes bastante utilizadas na literatura para a escolha do critério de parada do algoritmo PSO. Uma é pelo número de iterações, ou seja, quando o algoritmo chega ao fim por que atingiu a última iteração. A outra é pela função de avaliação (Fitness), ou seja, quando o algoritmo chegou ao fim por que alcançou um valor pré-definido para a função.

Outro componente importante que influencia no desempenho do algoritimo PSO é a estrutura ou topologia da comunicação das partículas. Ela rege como as partículas do enxame trocam informações e se comunicam. Logo, a escolha da topologia influencia na avaliação da velocidade das partículas. A depender de como as partículas se comunicam entre si e do problema a ser tratado, a busca pela solução ótima pode priorizar tanto a velocidade de convergência, a qualidade da solução ou ambas. As principais topologias utilizadas como mecanismos de comunicação entre as partículas são: a topologia global e a topologia local. A figura abaixo apresenta a estrutura de tais topologias.


a) Topologia local b) Topologia Global



Na topologia local, conforme ilustrado na figura a), o enxame está organizado em formato de anel e cada partícula deste possui dois vizinhos. Logo, a partícula troca informações apenas com seus vizinhos diretos. Embora a troca de informação entre as partículas seja mais lenta, esta estrutura provê uma melhor qualidade de soluções para problemas multimodais em comparação ao mesmo provido pela topologia global, visto a seguir.

Na topologia global, conforme ilustrado na figura b) acima, o enxame está organizado em formato estrela e todas as partículas estão conectadas entre si. Esta topologia utiliza o mecanismo de vizinhança global, também denominado de gbest para a troca de informação. Ao contrário da topologia anteriormente descrita, esta topologia permite uma convergência mais acelerada, visto que a informação da melhor posição é disseminada rapidamente entre todas as partículas do enxame,porém não garante a qualidade da solução obtida. Nestes casos o algoritmo pode atingir um mínimo local, devido a sua convergência precoce.



Depois dessa breve introdução sobre o algoritmo PSO, vamos agora vê-lo em execução. Iremos utilizar o PSO implementado em Python para solucionar um problema matemático de otimização: a minimização da função esfera (sphere). O objetivo é encontrar a solução ótima, que para esta função seria o seu mínimo global localizado pelo ponto (x,y) através das coordenadas (0,0).
Gráfico em Três dimensões da função esfera


Como podemos observar acima no gráfico plotado da função sphere, que o mínimo desta função encontra-se na região mais baixa (vértice inferior) da função esfera, e é a solução desejada a ser obtida pelo algoritmo de otimização por enxame de partículas.

Para este problema, padronizamos as fronteiras do espaço de busca, a região de inicialização das posições das partículas e o número de dimensões. Utilizamos também uma variação do PSO, com o fator de enxugamento (constriction factor - CONSTRICTED) no cálculo do vetor velocidade, o qual tem obtido um grande desempenho para solução de problemas multi-modais difíceis. A topologia utilizada para a solução deste problema foi a topologia global (todas as partículas conectadas entre si), o qual é bastante utilizada na literatura.

Todo o enxame é inicializado aleatoriamente na sub-região do espaço de busca disponível longe da solução ótima em todas as dimensões de acordo com a função a ser minimizada, neste caso, longe da posição (0,0).

Ao iniciar a execução do PSO, podemos observar o estado das partículas distribuídas aleatoriamente na região do espaço de busca com um alto valor de fitness ( O objetivo é minimizar a função, ou seja foca na redução do fitness). Vejam o histograma/gráfico abaixo:

Histograma -Distribuição Fitness x Partículas- (Iteração: 0)

Distribuição das partículas no espaço de busca (Iteração: 0)

Podemos inferir que há uma dispersão na distribuição das partículas com altos valores de fitness, o que significa que as partículas são inicializadas aleatoriamente em regiões distantes da solução ótima.
A simulação do algoritmo PSO é executada por 10.000 iterações, o qual no fim da mesma, obtemos os seguintes resultados:


Simulação do PyPSO para a solução do problema Sphere




Podemos observar pela figura acima, que após 9000 iterações, o melhor fitness encontrado é o valor 4.46.. e-164 e a melhor posição com o valor 3.03...e-83, ou seja, aproximadamente 0.00. Isto prova que o algoritmo convergiu até a solução ótima, isto é, as partículas se moveram pelo espaço de busca em direção à região que contém a solução ótima, o mínimo global da função matemática o qual estamos tentando minimizar. Claro, que o algoritmo consegue convergir bem antes que 9000 iterações, mas a fim de ilustrar o desempenho do PSO, decidimos executar com 10.000 iterações.


Plotando o histograma de distribuição de fitness e o gráfico da posição das partículas no fim da execução do algoritmo PSO, podemos concluir que os fitness de cada partículas estão com valores na ordem de grandeza e -160, bem próximo ao valor 0.0, o que significa que as partículas convergiram para a solução ótima, pela trajetória no espaço de busca. Observer também o gráfico de distribuição das posições das partículas na iteração 10.000, o qual ilustra as partículas concentradas numa região ao redor do ponto ótimo localizado nas coordenadas (0,0). Embora este seja um estudo de caso, demonstramos o poder do algoritmo PSO que se mostra eficiente na solução de problemas de busca e otimização de alta dimensionalidade.


Histograma - Distribuição de Fitness das partículas (Iteração: 10000)


Distribuição das posições das partículas na região de busca (Iteração: 10000)



Segue abaixo, o código principal utilizado para este experimento:




#Pso Demo

from pypso import Pso
from pypso import Consts
from pypso import GlobalTopology

#This is the Sphere Function
def sphere(position):
n = len(position)
total = 0.0
for i in xrange(n):
total += (position[i] ** 2.0)
return total

#Parameters
dimensions = 30
swarm_size = 30
timeSteps = 10000

# PSO Instance

pso = Pso.PSO()
pso.setPsoType(Consts.psoType["CONSTRICTED"])
pso.setTimeSteps(timeSteps)
pso.setTopology(GlobalTopology.GlobalTopology(swarm_size,dimensions))

# The evaluator function (objective function)
pso.setFunction(sphere)
pso.initializeBounds(dimensions)
pso.definePositionBounds(0, dimensions, (-100.0, 100.0))
pso.defineInitialPositionBounds(0,dimensions, (50.0,100.0))
pso.defineVelocityBounds(0,dimensions,100.0)

#Do the swarm movement, with stats
#dump frequency of 10 timeSteps
#import psyco

#psyco.full()

pso.execute(freq_stats=20)



(Código PSODemo.py)

Na época da execução desta simulação, tomei a iniciativa de construir um framework (ainda em desenvolvimento - versão 0.1) denominado PyPsoBox -Python PSO Toolbox- para execução de testes e avaliação de desempenho de algoritmos de otimização por enxame de partículas (PSO) e suas variações. O framework está sendo construído em Python e com suporte apenas para plataformas Windows. Em breve, novas funcionalidades serão adicionadas ao projeto que é gratuito e open-source. Todos estes gráficos acima foram gerados através do framework, que tem suporte para plotagem de gráficos de análise de simulação. Em um próximo post, disponibilizarei um tutorial de como usar o framework para simulações.

O projeto está hospedado no Google Code Hosting e o código está acessível através deste link.

Quero agradecer especialmente ao colega Christian S. Perone, criador do projeto PyEvolve (Um Framework similar implementado em Python para algoritmos genéticos). O trabalho dele serviu-me como forte inspiração para o meu trabalho.

Quaisquer dúvidas, dicas, sugestões para este artigo, framework, fiquem à vontade.


Até a próxima,

Marcel P. Caraciolo