Graph Partitioning using a Simulated Bee Colony Algorithm

Graph Partitioning using a Simulated Bee Colony
Algorithm
James D. McCaffrey
15 de maio de 2013

1

Introdu¸ c˜ ao

realizar solu¸c˜oes ´otimas para alguns problemas de alta complexidade.

O contexto desse artigo ´e a an´alise de uma heur´ıstica de particionamento de 1.1.1 Exemplos grafos, geralmente utilizada para diminuir a carga de trabalho em processa- Bee System, Bee Hive, Virtual Bee Almentos de grafos de grande porte, ou gorithm, Bee Swarm Optimization, Bee para diferentes processos entre subgra- Colony Optimization, Bees Algorithm. fos. Nesse artigo, a proposta do autor n˜ ao foi uma melhora na performace Colˆ onia Artificial de Abelhas mas sim uma maior qualidade na separa¸c˜ ao dos subgrafos.
Proposto em 2005 por Dervis KaA primeira heur´ıstica de particio- raboga o algoritmo Artificial Bee Conamento de grafo foi criada em 1970 lony (ABC), ´e um algoritmo de otipor Kernighan e Lin, um algoritmo sim- miza¸c˜ao baseado em popula¸c˜ao, como ples que divide o grafo em duas parti¸c˜oes. por exemplo uma popula¸c˜ao de abelhas
Utiliza m´etodo guloso e tem complexi- que se dividem em dois conjuntos; um dade (n log n). executa o trabalho em si e o outro conPor ser um problema NP completo h´a junto supervisiona o seu trabalho e dele varias heur´ısticas para a resolu¸c˜ao do recebe informa¸c˜oes e com base nessa problema como fora bruta, recursivi- informa¸c˜ao que toma as decis˜oes. dade, spectral analysis, Simulate Annealing, artificial colony bee(ABC) e
Referˆ
encias por algoritmos gen´eticos.
[1] James D. McCaffrey: Graph
Partitioning using a Simulated
Bee Colony Algorithm, Microsoft.,
Algoritmos baseados em comportamento
(2010),
561-578. naturais s˜ ao amplamente estudados, pois de alguma forma a natureza consegue

1.1

Meta-Heur´ısticas

1