Meta-heurísticas e algoritmos de inteligência de enxame

Este é um excerto da minha dissertação. Para a consultares, segue o link.

Dadas as restrições encontradas em funções de custo não-convexas, diversas meta-heurísticas[1] foram propostas para a resolução do PDE, tais como algoritmos genéticos (GA), Simulated annealing (SA), Taboo search (TS), Evolutionary programming (EP), Evolutionary strategies (ES), Particle swarm optimization (PSO), Bacteria foraging optimization (BFO), Ant colony optimization (ACO), Redes neuronais (NN), Artificial bee colony (ABC) e híbridos [28]. A partir dos algoritmos básicos, foram propostas melhorias e híbridos, tais como o Improved Taboo Search (ITS) [22], Fast Evolutionary Programming (FEP) e Improved Evolutionary Programming (IEP) [29], Improved Particle Swarm Optimization (IPSO) [28] e híbridos como o PSO com EP [30] e Fast Evolutionary Programming with Swarm Direction [7]. Muitas destas meta-heurísticas têm em comum o facto de se basearem em inteligência de enxames, um ramo da inteligência artificial fundamentado no comportamento animal.

Origem do estudo da Inteligência de Enxames

Em 1989, G. Beni e J. Wang cunharam a expressão Swarm Intelligence, no seu trabalho em Robotic Swarm [31]. O estudo do reino animal aprofundou-se no estudo comportamental e possibilitou o melhor entendimento de como cooperam indivíduos dentro de um grupo e quais os mecanismos usados para controlar o enxame e condicionar o indivíduo, tais como a estigmergia. Por enxame, pode entender-se manada, alcateia, bando, colónia, entre outras designações conforme o animal e, a partir daqui, qualquer referência a um grupo de agentes passa a ser feita por enxame, e.g., um enxame de pássaros. Os 5 princípios da inteligência de enxame segundo [32], são:

  • Proximidade – A população deve ser capaz de executar tarefas simples.
  • Qualidade – A população deve ser capaz de responder a mudanças no ambiente.
  • Diversidade – A população não deve focar-se excessivamente.
  • Estabilidade – A população não deve alterar o seu comportamento a cada alteração no ambiente.
  • Adaptabilidade – A população deve ser capaz de alterar o seu comportamento quando valha o esforço computacional.

Comportamento de enxame

Um animal, quando agrupado com mais membros da sua espécie, poderá exibir um comportamento diferente de quando isolado. Um bando de pássaros em vôo tem um comportamento de enxame, isto é, os pássaros seus constituintes agem em prol do grupo, em vez de si mesmos, não respeitando um comando centralizado. Este comportamento pode ser observado em diversos animais, desde os insectos (formigas, gafanhotos, térmitas, abelhas, etc), até aos mamíferos (morcegos, gnus, ovelhas, humanos, etc). Assim, uma definição generalista dirá que este comportamento se dá sempre que um grupo de indivíduos se agrupa e age socialmente, tentando atingir um objectivo e que os indivíduos num enxame possuem sensibilidade local, efectuando acções simples e desconhecendo o estado global do enxame, bem como o seu objectivo comum. Este objectivo comum é quase tão diverso quanto o número de espécies que se comportam em enxame. As abelhas actuam conjuntamente na busca de alimento, na protecção da sua colmeia e seu desenvolvimento; as andorinhas voam em formação para assim reduzirem o atrito aerodinâmico, algo que também pode ser observado em pilotos de aviões caça e ciclistas; manadas de gnus juntam-se em números avolumados para protecção contra predadores, acasalamento e até calor.

Sobre o comportamento de enxames, estigmergia é um termo usado para o explicar. Vem do grego, com a junção das palavras gregas στίγμα (estigma, sinal) e ἔργον (projecto, acção). É um termo cunhado pelo biólogo francês, Pierre-Paul Grassé, em 1959 para caracterizar o comportamento de térmitas. Basicamente, estigmergia é o comportamento que leva um agente a reagir à acção de outro ou de si próprio. Trata-se de um condicionalismo que estimula certa resposta a certa acção, reforçando a acção inicial e permitindo assim uma acção complexa realizada por agentes simples, sem inteligência. O exemplo habitualmente dado para a estigmergia é o das formigas representadas na figura 3‑2. Sozinhas, as formigas são agentes simples, sem inteligência, mas em enxame demonstram a inteligência de perceber qual o caminho mais curto entre o formigueiro e a comida. As formigas libertam químicos, feromonas, no seu rasto, que qualquer formiga no seu encalço sentirá e decidirá se segue o caminho das feromonas ou se diverge e cria um caminho próprio. A probabilidade de as formigas seguirem o caminho já trilhado é maior.

Figura 3‑2 – Estigmergia em formigas

Na figura 3‑2, duas formigas partem em busca de alimento, tendo a formiga debaixo demorado menos tempo até regressar ao formigueiro por o seu caminho ser mais curto. Este caminho foi percorrido duas vezes (ida e volta), logo terá maior intensidade de feromonas que o caminho de cima. Esta maior intensidade levará uma maior quantidade de formigas a escolherem o caminho debaixo, enquanto a intensidade do de cima tenderá a desaparecer, pois as feromonas evaporam.

Particle Swarm Optimization

Em 1995 foi apresentado um artigo da autoria de J. Kennedy e R. Eberhart, no qual foi introduzido um método de optimização para funções não lineares, denominado Particle Swarm Optimization (PSO) [33].

O PSO é baseado no comportamento de um bando de pássaros em busca de alimento. O bando aumenta a probabilidade de encontrar alimento quando coopera na sua procura, interagindo entre si com a informação que cada pássaro retira do meio ambiente. Cada pássaro poderá decidir entre tomar um rumo egoísta, em que valoriza o seu próprio conhecimento e segue para a melhor posição que já encontrou até ao momento ou decidir tomar um rumo social, em que segue a direcção do melhor pássaro do bando (considera-se como melhor pássaro aquele que mais perto se encontra da posição da comida). Esta é a base biológica em que se fundamenta a formulação matemática do PSO, tal como foi inicialmente enunciada em [33].

Na implementação do algoritmo em problemas de optimização, o meio ambiente representa o espaço de busca e cada pássaro é considerado uma partícula, que representa uma possível solução para o problema considerado. Cada partícula interage com todas as outras na busca por uma solução melhor através de três parâmetros, nomeadamente a sua inércia e comportamentos cognitivo e de sociabilização. O comportamento cognitivo dá um peso ao melhor valor de fitness de cada partícula obtida até ao momento e o de sociabilização dá um peso à partícula que alcançou o melhor valor de fitness do enxame até ao momento. A inércia estabelece limites à velocidade de cada partícula [34]. Cada pássaro tem a capacidade de avaliar a sua posição, devolvendo um valor de fitness para a sua posição. Este fitness permite que as partículas sejam comparadas entre si e determinem para onde se devem dirigir. Em suma, cada partícula é definida pela sua posição, pela sua velocidade e pelo seu valor de fitness. A inércia é calculada por (42), a velocidade de cada partícula por (43) e a nova posição de cada partícula por (44) [22].

Em (42), ω é a inércia, ωmáx a inércia máxima e ωmin a inércia mínima, sendo estes dois últimos definidos a priori. Em (43), vi é a velocidade de cada partícula i, c1 é o coeficiente cognitivo, c2 é o coeficiente social, xbest representa o melhor valor atingido por cada partícula até ao momento e gbest o melhor valor atingido pelo enxame até ao momento. Em (44), xi(t+1) é a nova posição e xi(t) é a posição actual. A equação (43) é ilustrada na figura 3‑3, onde está representado esquematicamente o processo que define a nova posição de cada partícula i.

Figura 3‑3 – Velocidade imposta a uma dada partícula.

Os coeficientes c1 e c2 são parâmetros positivos e constantes. Na implementação original do PSO, apenas um parâmetro, c, era aplicado, sendo então chamado de factor de aprendizagem (learning factor) ou constante de aceleração (acceleration constant) e geralmente igual a dois, i.e., c1=c2=2. Para controlar o comportamento do enxame, versões recentes do PSO têm vindo a ajustar estes parâmetros no intervalo [0,4]. Ajustando estes parâmetros, os seguintes comportamentos são obtidos [31]:

  • Valores elevados de c1 e c2 habilitam o enxame a obter novas partículas em regiões distantes, o que garante uma melhor busca global, mas por outro lado poderão levar o enxame a divergir.
  • Valores reduzidos de c1 e c2 limitam o movimento do enxame, podendo assim restringir a busca global a uma busca mais local. Esta opção poderá ser vantajosa quando se pretende uma busca localizada, mais refinada, com poucas variações à volta dos melhores valores obtidos.
  • Se o coeficiente cognitivo for maior que o de sociabilização, o enxame favorecerá as melhores experiências locais de cada partícula.
  • Se o coeficiente de sociabilização for maior que o cognitivo, o enxame favorecerá a melhor experiência global do enxame.

Na figura 3‑4 está representada a evolução das partículas do enxame em função do número de iterações para a função De Jong (função 1, [35]) para duas dimensões, 100 partículas, c1=c2=2, ωmáx=0,9 e ωmin=0,3. A função De Jong tem o seu valor mínimo no ponto f(x1, x2)=(0, 0), verificando-se claramente a tendência do deslocamento das partículas para as proximidades desse valor com o evoluir do número de iterações.

Figura 3-4 – Evolução do enxame do PSO na busca pela melhor solução.

Apesar da sua simplicidade, o PSO é um algoritmo rápido a correr completamente e eficaz, sendo utilizado nos mais variados problemas. No anexo 1 pode ser encontrado um possível pseudo-código para a implementação do algoritmo [22], [31] e [36].

Bee Colony Optimization

O Bee Colony Optimization (BCO) é caracterizado por reproduzir o comportamento das abelhas na busca por pólen nas flores. A simulação de colónia de abelhas pode ser encontrada em [34], em que é denominada de Artifical Bee Colony.

As abelhas batedoras (scouts) partem da colmeia em busca de flores, com a maior quantidade de pólen. No regresso à colmeia, as abelhas comunicarão com as restantes abelhas de modo a cativá-las para as acompanhar. Esta comunicação indica qualidade da flor, distância relativamente à colmeia e direcção relativamente ao sol e é conseguida através de uma dança executada pela abelha. A direcção (parecida com uma trajectória em forma de oito) em que a abelha dança informa qual a posição da flor relativamente ao sol; a distância da flor relativamente à colmeia é codificada na dança pelo comprimento que a abelha percorre; a qualidade da flor é transmitida pela frequência com que a abelha treme, e.g., quanto maior a frequência, mais excitada a abelha se demonstra estar sobre a qualidade da flor. Uma representação esquemática da dança está ilustrada na figura 3‑5.

Figura 3‑5 – Representação da dança da abelha para comunicar.

Na implementação do BCO, são criados três diferentes tipos de abelhas: batedoras (scouts), seguidoras (followers) e escudeiras (onlookers). Na primeira fase, as scouts partem da colmeia em busca de flores num percurso aleatório. De seguida, regressam à colmeia e apresentam a sua melhor flor encontrada às followers. Estas acompanharão com maior probabilidade a scout com melhor fitness. Se nenhuma melhoria no valor de fitness for encontrada pela scout num determinado intervalo de iterações, esta abandona a flor e passa a onlooker, que irá procurar outra flor de forma aleatória [31], [34]. A equação (45) demonstra como é calculada a probabilidade de cada flor encontrada pelas scouts ser explorada pelas followers. Na equação (46) está representada a forma como as followers circulam à volta da posição encontrada pela scout.

Em (45), Pi é a probabilidade de cada flor ser escolhida pelas followers, fit(xi) é o valor de fitness da posição xi e SN é o número de alimentos, i.e., número de scouts. Em (46), vij é a posição da follower na vizinhança da flor encontrada pela scout, xij é a posição da flor encontrada pela scout, φij é um valor aleatório no intervalo [-1, 1] e xkj é a posição de outra scout, com a qual é feita a comparação.

Na figura 3‑6 está representada a evolução das partículas (abelhas) do enxame em função do número de iterações para a função De Jong para duas dimensões, 100 partículas.

Figura 3-6 – Evolução do enxame do BCO na busca pela melhor solução.

Na figura 3‑6 pode ver-se que o BCO e o PSO convergem de forma diferente. Enquanto que no PSO as partículas vão convergindo para o mínimo global quando este é encontrado, no BCO esta convergência não acontece. Na 1ª iteração já o algoritmo encontrou a proximidade do óptimo em (0,0), mas as partículas continuam a procurar o espaço de busca inteiro (como se pode ver na 40ª iteração, em que há partículas nos extremos) de forma aparentemente aleatória, embora estejam limitadas pela posição das restantes abelhas. Tal característica resulta num algoritmo com uma elevada capacidade de busca e facilidade em não ficar preso em mínimos locais. No reverso da medalha, esta característica também atrasa o algoritmo, tendo o BCO uma velocidade de convergência baixa. No anexo 2 pode ser encontrado um possível pseudo-código para a implementação do algoritmo [34].

Cockroach Swarm Optimization

O Cockroach Swarm Optimization (CSO) é inspirado no comportamento social das baratas. Diversos algoritmos foram criados com base no comportamento das baratas, por exemplo o Cockroach Swarm Optimization e o Roach Infestation Optimization (RIO) que podem ser analisados em [37] e [38], respectivamente.

Um estudo do comportamento das baratas em [39], conclui que “a decisão colectiva emerge das interacções entre indivíduos iguais, que inicialmente possuem pouca informação sobre o seu ambiente”. As baratas exibem um comportamento de perseguição (chase swarming), pelo qual as baratas deixam um trilho de matéria fecal no seu caminho, para que outras baratas possam seguir. Para este comportamento também contribui a emissão de feromonas para o ar. Outro comportamento, dispersão (dispersing), permite às baratas dispersarem-se repentinamente na presença de perigo ou quando há falta de recursos no local. Por último, os seus enxames apresentam um comportamento de implacabilidade (ruthless), i.e., quando há falta de alimento, as baratas eliminar-se-ão mutuamente [37], [40]. A formulação matemática do CSO pretende simular os comportamentos dos enxames de baratas, através das três características já apontadas. Um enxame de baratas é inicializado de forma aleatória e as suas partículas são avaliadas, sendo o melhor indivíduo, i.e., o melhor valor de fitness associado a uma dada posição, no seu campo visual. Caso exista uma melhor barata no seu campo visual, ela irá para lá segundo (47), formando um cluster. Se a barata for a melhor no seu campo visual ou cluster, então irá para a posição da melhor barata de todo o enxame segundo (48), sendo seguida pelas restantes baratas que fazem parte do seu cluster.

Em (47), x'(i) é a nova posição da barata i, x(i) é a posição actual, rand é um valor aleatório uniformemente distribuído e P(i) a posição associada ao melhor valor de fitness do cluster. Pg é a posição associada ao melhor valor de fitness do enxame em (48). Na figura 3‑7 está representada a evolução da posição de uma barata tal como em (47).

Figura 3-7 – Comportamento de uma partícula no CSO.

Na figura 3‑8 está representada a evolução das baratas do enxame em função do número de iterações para a função De Jong para duas dimensões, 10 partículas.

Figura 3-8 – Evolução do algoritmo CSO na busca pela melhor solução.

Verifica-se o chase swarming característico do CSO, bem como o deslocamento das baratas para as proximidades do valor mínimo da função com o evoluir do número de iterações. No CSO, as baratas criam aglomerados (clusters), com vários clusters de baratas a convergir para a melhor posição encontrada até ao momento pelo enxame, tal como está representado na figura 3‑8 com o círculo. Um possível pseudo-código é apresentado no anexo 3 [37].

Sensing Cloud Optimization

O Sensing Cloud Optimization (SCO) é uma técnica heurística baseada em nuvens de partículas proposta em [7] e [39] não se baseando em qualquer comportamento biológico. Cada partícula da nuvem tem como função analizar o espaço de busca de modo a ajudar na definição do posicionamento da partícula central da nuvem, que é a única candidata a óptimo. A posição da partícula central é definida através de uma média pesada entre a posição da melhor partícula da nuvem e o vértice de regressão polinomial de segunda ordem. A dimensão da nuvem, definida dinamicamente, é obtida através de uma regressão polinomial de primeira ordem da distância entre a partícula central e as restantes. O SCO opera em dois estados complementares, em que o primeiro consiste na avaliação do fitness da nuvem de partículas e o segundo numa análise estatística com dois objectivos: o de direccionar a mesma nuvem e de definir a sua expansão. Uma das particularidades do SCO encontra-se no segundo objectivo, o qual capacita este algoritmo de controlar o seu próprio tamanho no espaço de busca. O controlo da expansão e contracção da nuvem serve para acelerar o tempo de convergência e evitar mínimos locais. A partícula central é inicialmente criada a partir de (49), na qual i representa o número de dimensões do problema, garantindo-se logo que a mesma se encontra dentro do espaço de busca.

A criação da nuvem é feita através de uma distribuição gaussiana com média definida pela posição da partícula central dispersa segundo um desvio padrão inicial. Após a criação da nuvem, todos as partículas são avaliadas, e com os seus valores de fitness, define-se uma regressão polinomial de segunda ordem para cada dimensão do espaço de busca. Estas regressões permitem ter uma ideia acerca da forma do espaço de busca sob a nuvem. No caso de as regressões serem convexas pode-se definir quais os seus valores mínimos tp(i)  e assim ter uma indicação para onde a partícula central se deverá mover. Assim a posição da partícula central resulta da soma ponderada entre o valor de tp(i) e o melhor de fitness encontrado pela nuvem, xb(i), como é demonstrado em (50) e representado na figura 3‑9. Os pesos da soma ponderada são obtidos através do coeficiente de correlação da regressão polinomial de segunda ordem, R2q(i).

Na figura 3‑9 está representada uma superfície de busca característica da expressão De Jong com duas dimensões cujo mínimo se encontra na posição (0,0). Está também representada uma nuvem de partículas com o respectivo ponto central (old queen) e as coordenadas do trend point, bem como a nova posição do ponto central.

Figura 3-9 – Contour plot da partícula Xq(1) [41].

Para uma melhor compreensão do funcionamento do algoritmo, na figura 3‑10 e figura 3‑11 estão representadas as nuvens de partículas segundo cada uma das dimensões, indicando em cada uma delas a regressão de segunda ordem com o respectivo tp(i) e o coeficiente de correlação. Analisando as figura 3‑11 e figura 3‑12 pode ver-se o tp(i) que resulta da regressão segundo cada variável. Se a posição da nova partícula central fosse definida apenas pelo valor de tp(i), a solução afastar-se-ia para um valor de fitness superior ao da iteração anterior, como se pode ver na figura 3‑9. Neste caso, o peso da posição da melhor partícula do enxame, conforme definido em (50), ajuda a que a nova partícula central caminhe para uma solução com menor valor de fitness. Isto ajuda também a uma maior estabilidade do algoritmo diminuindo as oscilações da solução.

Figura 3-10 – Regressão polinomial para a dimensão X(2) [41].

Particle Cloud Optimization

O Particle Cloud Optimization (PCO) é uma técnica híbrida entre o PSO e o SCO e é proposta como contribuição original nesta dissertação. O objectivo deste híbrido é o de aproveitar os pontos fortes do PSO e do SCO e assim atingir um algoritmo mais completo. Os pontos fortes em vista são a capacidade de busca, e velocidade de convergência, respectivamente do PSO e do SCO. Na figura 3‑16 estão representadas as evoluções do PSO e do SCO para a função De Jong com 2 dimensões, 30 partículas e 500 gerações.

Figura 3-16 – Evolução do PSO (vermelho) e do SCO (verde).

Como se pode ver, o PSO atinge um valor de fitness cerca de 1e60 vezes menor que o atingido pelo SCO. Outro ponto relevante acontece quando os algoritmos chegam às 5000 avaliações e o valor atingido pelo PSO alcança o atingido pelo SCO há cerca de 3000 avaliações. Ou seja, o PSO necessita de muito mais avaliações para obter o valor atingido pelo SCO, mas depois prossegue na sua busca, enquanto o SCO estagna.

O PCO será assim constituído por duas fases: SCO e depois PSO. Na primeira fase, comporta-se como SCO até atingir um patamar de estagnação a partir do qual iniciará o PSO. A fase PSO irá assim começar a sua busca a partir de uma posição já optimizada e poderá usar as avaliações restantes para obter um valor de fitness melhor que o do PSO.

A implementação do PCO é feita de forma modular, ligando o PSO (explicado em 3.5.4) ao SCO (explicado em 3.5.8). Os parâmetros do PCO são os mesmos que os indicados para o PSO e o SCO separadamente. O único parâmetro exclusivo do PCO tem a ver com o início da sua segunda fase, ou seja, o começo do PSO. Este parâmetro reflecte o critério de entrada do PSO, que se escolhe como sendo o número limite de iterações sem melhoria por parte do SCO.

Na figura 3‑17 estão representados a evolução dos valores de fitness para os algoritmos PSO, SCO e o modelo híbrido proposto (PCO), que resulta do PSO e SCO. A simulação é feita com 30 partículas em cada algoritmo e 3000 gerações.

Figura 3-17 – Representação do PCO face ao PSO e SCO.

Além de o PCO ser computacionalmente mais rápido que os algoritmos em que se baseia, demonstra também uma maior capacidade de busca atingindo um mínimo melhor que o do PSO e o do SCO.

O patamar de estagnação do PCO deve-se a dois factores. O primeiro tem a ver com o momento em que o PSO entra em funcionamento, ao fim de um determinado número de iterações sem melhoria no SCO. Este número de iterações sem melhoria poderá ser reduzido ou aumentado, mas ambos os extremos têm defeitos. Se o número for demasiado pequeno, então o PCO não recolhe os benefícios totais do SCO. Se o número for demasiado elevado, o PCO prolonga o seu patamar de estagnação, o que prejudica a sua velocidade de convergência e capacidade de busca. Neste caso da figura 3‑17, o número de iterações é 5, ou seja 150 avaliações. O segundo factor a considerar sobre o patamar de estagnação diz respeito à fase PSO do PCO. Dado que o PSO começa a sua busca a partir de uma posição com algum grau de optimização, os seus parâmetros não podem ser iguais aos que tem o PSO isolado. Pelo contrário, a velocidade inicial, , das partículas tem de ser reduzida, visto que não é vantajoso voltar a procurar no espaço de busca todo. Os coeficientes c1 e c2 têm também de ser afinados, bem como o ω, pela mesma razão que a da velocidade inicial. O desafio reside no elevado número de parâmetros que carecem de ser determinados. Um possível pseudo-código para o PCO está descrito no anexo 5.

Deixe uma Resposta

Preencha os seus detalhes abaixo ou clique num ícone para iniciar sessão:

Logótipo da WordPress.com

Está a comentar usando a sua conta WordPress.com Terminar Sessão /  Alterar )

Google photo

Está a comentar usando a sua conta Google Terminar Sessão /  Alterar )

Imagem do Twitter

Está a comentar usando a sua conta Twitter Terminar Sessão /  Alterar )

Facebook photo

Está a comentar usando a sua conta Facebook Terminar Sessão /  Alterar )

Connecting to %s