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

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