Algoritmos naturais

Use o algoritmo de colônia de abelhas para solucionar problemas impossíveis

James McCaffrey

Baixar o código de exemplo

Os algoritmos de colônia de abelhas (ou SBC, Simulated Bee Colony) modelam o comportamento das abelhas melíferas e podem ser usados para encontrar soluções para problemas combinatórios difíceis ou impossíveis. Neste artigo, eu explico o que exatamente são os algoritmos SBC, descrevo os tipos de problemas que podem ser solucionados usando esses algoritmos e apresento um exemplo completo que usa um algoritmo SBC para resolver o Problema do Caixeiro Viajante.

Uma boa maneira de você entender os algoritmos SBC e perceber onde quero chegar com este artigo é examinar o programa de demonstração mostrado em execução na Figura 1. O programa de demonstração usa um algoritmo SBC para analisar um conjunto de 20 cidades (nomeadas de A até T) e localizar o menor caminho que percorre todas as cidades de uma única vez. Os dados da cidade foram artificialmente construídos, de forma que o melhor caminho comece na cidade A e continue até a cidade T, em ordem, além de o melhor caminho ter um comprimento de 19,0 unidades.

Figura 1 Demonstração de colônia de abelhas

Em segundo plano, o algoritmo SBC cria uma instância de colmeia com 100 abelhas, e cada uma delas possui uma solução em potencial aleatória. Inicialmente, a melhor das soluções aleatórias tem um comprimento de caminho de 95,0 unidades. O algoritmo SBC insere um loop de processamento, indicado pela barra de progresso com base em texto, que simula o comportamento de abelhas melíferas comuns à procura de alimento. No final do loop de processamento do SBC, a melhor solução encontrada possui 16 dentre 20 posições de cidades corretas, e o comprimento do caminho é de 26,5 — próxima, mas nem tanto, da solução ideal.

Os algoritmos SBC frequentemente são chamados de meta-heurísticos, pois fornecem uma estrutura geral e um conjunto de diretrizes para a criação de uma solução de problema, em vez de fornecer uma prescrição de solução altamente detalhada. Este artigo apresenta um exemplo de uso de SBC para resolver um problema específico. Depois de compreender como um SBC pode ser usado para resolver um problema, você poderá adaptar o algoritmo SBC apresentado aqui para resolver os seus próprios problemas. Conforme demonstrado neste artigo, os algoritmos SBC são mais adequados para a resolução de problemas combinatórios complexos que não têm soluções determinísticas práticas.

Este artigo pressupõe que você tenha habilidades de programação de nível intermediário. O exemplo apresentado neste artigo foi codificado usando C#, mas todos os códigos foram escritos, de forma que ele pode ser facilmente refatorado para outras linguagens de programação. Espero que este artigo seja bastante interessante para você e que a capacidade de usar algoritmos SBC seja uma adição útil ao seu conjunto de habilidades pessoais.

Sobre as abelhas

Abelhas melíferas comuns, como as Apis mellifera, assumem diferentes funções dentro de suas colônias ao longo do tempo. Uma colmeia típica pode ter de 5.000 a 20.000 abelhas. As abelhas adultas (de 20 a 40 dias de idade) geralmente se tornam operárias. As abelhas operárias normalmente se enquadram em uma destas três funções: ativas, protetoras e inativas.

As abelhas operárias ativas viajam até fontes de alimentos, examinam as fontes de alimentos da vizinhança, coletam alimentos e retornam para a colmeia.

As abelhas protetoras investigam a área ao redor da colmeia, em geral, uma região de até 130 quilômetros quadrados, procurando por novas fontes de alimentos atraentes. Aproximadamente 10% das abelhas operárias de uma colmeia são responsáveis pela proteção.

A todo o momento, algumas abelhas operárias ficam inativas. Essas operárias inativas aguardam próximas à entrada da colmeia. Quando as operárias ativas e as protetoras retornam à colmeia, dependendo da qualidade da fonte de alimento que acabaram de visitar, elas podem fazer uma dança agitada para as abelhas inativas que estavam aguardando. Existem fortes evidências de que essa dança transmite informações às abelhas inativas sobre o local e a qualidade da fonte de alimento. As operárias inativas recebem essas informações sobre a fonte de alimento a partir da dança e podem se tornar operárias ativas.

Em geral, uma abelha operária ativa continua coletando alimentos de uma fonte específica até que a fonte se esgote e, nesse momento, a abelha se torna uma operária inativa.

O Problema do Caixeiro Viajante

O Problema do Caixeiro Viajante (ou TSP, Traveling Salesman Problem) é um dos problemas mais estudados em pesquisas de ciências da computação. Existem muitas variações do TSP, mas, informalmente, o problema é encontrar o menor caminho que passe apenas uma única vez por todas as cidades de um determinado conjunto de cidades.

Se verificar a Figura 1, você verá que o programa de demonstração de SBC utiliza um conjunto de 20 cidades arbitrariamente denominadas de A a T. Um caminho válido consiste em um conjunto ordenado das 20 cidades, no qual cada cidade ocorre apenas uma vez. Portanto, há um total de 20 cidades, que é igual a 2.432.902.008.176.640.000 caminhos possíveis.

Em segundo plano, existe um valor de distância associado a cada par de cidades. Para simplificar, se cidade c1 < cidade c2, a distância entre c1 e c2 é apenas 1,0 vez a distância ordinal entre as cidades. Se c1 > c2, a distância será 1,5 vez a distância ordinal entre c1 e c2. Portanto, a distância de A até B é de 1,0 unidade arbitrária, a distância de B até A é de 1,5 unidade, a distância de A até C é de 2,0 unidades, e assim por diante. Dessa maneira, o melhor caminho que passa por todas as cidades apenas uma única vez é A -> B-> C -> ... -> T, e o melhor, ou menor, comprimento de caminho é (20-1) * 1,0 = 19,0.

Na maioria dos cenários do TSP, as distâncias entre as cidades não seriam artificialmente computadas. Em vez disso, as distâncias provavelmente seriam armazenadas em algum tipo de estrutura de dados de pesquisa. Algumas variações do TSP pressupõem que cada uma das cidades esteja conectada a todas as outras cidades, e outros problemas assumem que as cidades não estão totalmente conectadas. Além disso, algumas variações do TSP pressupõem que a distância de qualquer cidade c1 para a cidade c2 seja igual à distância da cidade c2 para a c1, e outras variações não fazem essas pressuposições bidirecionais.

Exceto em situações triviais, uma abordagem de força bruta para encontrar o menor caminho não é viável. Por exemplo, com 20 cidades, mesmo que você pudesse avaliar 1 milhão de caminhos por segundo, examinar todos os 20 caminhos possíveis exigiria mais de 77.000 anos. Esse tipo de problema de otimização combinatório extremamente difícil é o tipo de problema que os algoritmos SBC são indicados para tratar.

O problema fictício do TSP é implementado em uma classe chamada CitiesData, mostrado na Figura 2. O código-fonte completo do programa de demonstração de SBC está disponível em code.msdn.microsoft.com/mag201104BeeColony.

Figura 2 A definição da classe CitiesData

class CitiesData {
  public char[] cities;

  public CitiesData(int numberCities) {
    this.cities = new char[numberCities];
    this.cities[0] = 'A';
    for (int i = 1; i < this.cities.Length; ++i)
      this.cities[i] = (char)(this.cities[i - 1] + 1);
  }

  public double Distance(char firstCity, char secondCity) {
    if (firstCity < secondCity)
      return 1.0 * ((int)secondCity - (int)firstCity);
    else
      return 1.5 * ((int)firstCity - (int)secondCity);
  }

  public double ShortestPathLength() {
    return 1.0 * (this.cities.Length - 1);
  }

  public long NumberOfPossiblePaths() {
    long n = this.cities.Length;
    long answer = 1;
    for (int i = 1; i <= n; ++i)
      checked { answer *= i; }
    return answer;
  }

  public override string ToString() {
    string s = "";
    s += "Cities: ";
    for (int i = 0; i < this.cities.Length; ++i)
      s += this.cities[i] + " ";
    return s;
  }
}

A definição de algumas classes ou estruturas de dados que representam o seu problema específico será diferente da apresentada aqui. Entretanto, como um princípio básico geral, os problemas mais indicados para resolução com um algoritmo SBC geralmente podem ser representados como uma matriz não numérica ou uma matriz denteada e não numérica de matrizes.

O construtor CitiesData aceita um valor para o número de cidades e atribui à primeira cidade um rótulo de A, à segunda cidade, um rótulo de B, e assim por diante.

O método Distance é definido de forma unidirecional, conforme descrito anteriormente, e ele pressupõe que todas as cidades estão conectadas entre si.

O método ShortestPathLength retorna o comprimento de caminho ideal de acordo com a definição de Distance. Na maioria dos casos de SBC, você não terá as informações necessárias para implementar um método que retorne a solução ideal.

O método NumberOfPossiblePaths apenas computa n!, onde n é o número de cidades. Em alguns cenários de TSP, o número de caminhos possíveis é n-1! (se a cidade inicial não importar) e, em alguns cenários, o número de caminhos possíveis é n/2! (se a direção do caminho não importar).

O método ToString utiliza a concatenação de cadeia de caracteres, em vez da classe StringBuilder mais eficiente, para montar uma cadeia de caracteres com dados descritivos. A concatenação de cadeia de caracteres é utilizada a fim de simplificar a refatoração para outras linguagens de programação.

Neste artigo, para manter o código relativamente curto e limpo, eu utilizo atalhos que não devem ser usados no código de produção, como a remoção da maioria das verificações de erros. Por exemplo, o método NumberOfPossiblePaths não lida com estouros numéricos se o resultado for maior que long.MaxValue.

Estrutura do programa de SBC

O algoritmo SBC mostrado na Figura 1 é implementado como um aplicativo de console em C#. A estrutura geral do programa está listada na Figura 3. Observe que a estrutura do programa de SBC é relativamente simples e utiliza apenas o namespace System simples. Existem três classes: a classe Program, que hospeda um único método Main; a classe Hive, que hospeda toda a lógica do algoritmo SBC; e a classe CitiesData, apresentada na seção anterior deste artigo. A classe Hive é genericamente chamada de Hive, em vez de ter um nome mais específico com o TravelingSalesmanHive, embora as implementações do algoritmo SBC sejam altamente dependentes do problema específico que são designadas a resolver.

Figura 3 Estrutura geral do programa

using System;
namespace SimulatedBeeColony {
  class Program {
    static void Main(string[] args) {
      Console.WriteLine("\nBegin Simulated Bee Colony algorithm demo\n");
      . . . 
      Console.WriteLine("End Simulated Bee Colony demo");
    } 
  } 

  class Hive {
    public class Bee {
      . . . 
    }

    // Hive data fields here

    public override string ToString() { . . . }
    
    public Hive(int totalNumberBees, int numberInactive,
      int numberActive, int numberScout, int maxNumberVisits,
      int maxNumberCycles, CitiesData citiesData) {
      . . .      
    } 

    public char[] GenerateRandomMemoryMatrix() { . . . }
    
    public char[] GenerateNeighborMemoryMatrix(char[] memoryMatrix) { . . . }
    
    public double MeasureOfQuality(char[] memoryMatrix) { . . . }
    
    public void Solve() { . . . }

    private void ProcessActiveBee(int i) { . . . }

    private void ProcessScoutBee(int i) { . . . }

    private void ProcessInactiveBee(int i) { . . . }

    private void DoWaggleDance(int i) { . . . }
  } 

  class CitiesData {
    . . .
  }

} // ns

O método Main é bastante simples. Após exibir uma mensagem inicial, é criada uma instância do objeto CitiesData:

Console.WriteLine(
  "Loading cities data for SBC Traveling Salesman Problem analysis");
CitiesData citiesData = new CitiesData(20);
Console.WriteLine(citiesData.ToString());
Console.WriteLine("Number of cities = " + citiesData.cities.Length);
Console.WriteLine("Number of possible paths = " + 
  citiesData.NumberOfPossiblePaths().ToString("#,###"));
Console.WriteLine("Best possible solution (shortest path) length = " + 
  citiesData.ShortestPathLength().ToString("F4"));

Em muitos cenários de SBC, os dados de seu problema residirão em um armazenamento externo, como um arquivo de texto ou bancos de dados SQL, e você irá carregar esses dados por meio de algum construtor de carga ou método de carregamento, juntamente com as linhas de myProblemData.Load(dataFile).

Em seguida, o construtor Hive é preparado e chamado:

int totalNumberBees = 100;
int numberInactive = 20;
int numberActive = 50;
int numberScout = 30;
int maxNumberVisits = 100; 
int maxNumberCycles = 3460;
       
Hive hive = new TravelingSalesmanHive(totalNumberBees,
  numberInactive, numberActive, numberScout, maxNumberVisits,
  maxNumberCycles, citiesData);

Como poderá ver mais detalhadamente nas próximas seções deste artigo, um algoritmo SBC usa três tipos de abelhas: ativas, inativas e protetoras. Embora a contagem de cada um desses tipos de abelhas possa ser inserida, na maioria dos cenários, é melhor transmitir essas contagens como parâmetros para o construtor Hive, de forma que o algoritmo possa ser ajustado em relação ao desempenho mais facilmente.

O valor da variável totalNumberBees pode ser derivado de outras três variáveis, mas a variável extra melhora a legibilidade do código aqui. O número total de abelhas dependerá de seu problema específico. Mais abelhas é melhor, mas torna a execução do programa mais lenta. Em termos de proporção, existem algumas pesquisas que sugerem que as melhores porcentagens de abelhas ativas, inativas e protetoras devem ser de aproximadamente 75%, 10% e 15%, respectivamente. 

O valor 100 utilizado para a variável maxNumberVisits será explicado brevemente; ele está relacionado ao número de soluções aproximadas relativas a uma determinada solução.

A variável maxNumberCycles é usada para controlar quantas vezes a rotina Solve será iterada; isso é necessário porque em cenários de algoritmo SBC, você normalmente não sabe quando atingiu uma solução ideal — se você conhece a solução ideal, você realmente não tem um problema para resolver. Nesse caso, o valor de maxNumberCycles foi limitado a apenas 3.460, de forma que o algoritmo SBC não produza um resultado perfeito. O ponto aqui é que, embora os algoritmos SBC possam gerar um resultado ideal, você normalmente não tem como saber isso e, portanto, acaba correndo o risco de aceitar um “bom” resultado.

Quando o construtor é executado, ele cria um conjunto de abelhas, cada uma delas com uma solução aleatória. O objeto Hive monitora o melhor (menor) caminho geral encontrado por qualquer uma das abelhas da colmeia e o melhor comprimento de caminho associado à solução.

Após chamar o construtor Hive, o método Main conclui usando o método ToString para exibir os valores iniciais de Hive gerados aleatoriamente, chamando o método Solve com um parâmetro que indica que uma barra de progresso com base em texto deve ser impressa e, em seguida, exibindo o melhor caminho e o comprimento associado ao caminho encontrado:

...
  Console.WriteLine("\nInitial random hive");
  Console.WriteLine(hive);

  bool doProgressBar = true;
  hive.Solve(doProgressBar);

  Console.WriteLine("\nFinal hive");
  Console.WriteLine(hive);
  Console.WriteLine("End Simulated Bee Colony demo");
}

A classe Bee

Conforme mostrado na Figura 3, a classe Hive contém uma definição da classe Bee aninhada. Os detalhes da definição de Bee estão listados na Figura 4.

Figura 4 Definição da classe Bee

public class Bee {
  public int status;
  public char[] memoryMatrix;
  public double measureOfQuality; 
  public int numberOfVisits;

  public Bee(int status, char[] memoryMatrix, 
    double measureOfQuality, int numberOfVisits) {
    this.status = status;
    this.memoryMatrix = new char[memoryMatrix.Length];
    Array.Copy(memoryMatrix, this.memoryMatrix, memoryMatrix.Length);
    this.measureOfQuality = measureOfQuality;
    this.numberOfVisits = numberOfVisits;
  }

  public override string ToString() {
    string s = "";
    s += "Status = " + this.status + "\n";
    s += " Memory = " + "\n";
    for (int i = 0; i < this.memoryMatrix.Length-1; ++i)
      s += this.memoryMatrix[i] + "->";
    s += this.memoryMatrix[this.memoryMatrix.Length-1] + "\n";
    s += " Quality = " + this.measureOfQuality.ToString("F4");
    s += " Number visits = " + this.numberOfVisits;
    return s;
  }
}

A classe Bee possui três campos de dados comuns a todas as implementações de SBC e um campo de dados específico do problema. O campo específico do problema é chamado memoryMatrix. Todas as implementações de SBC devem ter alguma maneira de representar uma solução. No caso do TSP deste artigo, uma solução pode ser representada por uma matriz do tipo char. Deixe-me enfatizar que o objeto que representa uma solução é altamente dependente do problema e todo problema deve ser analisado separadamente a fim de produzir uma representação significativa da solução.

O campo chamado Status possui um valor int que indica o tipo do objeto Bee: 0 para inativa, 1 para ativa e 2 para protetora. Se estiver escrevendo o código em uma linguagem que oferece suporte a tipos de enumeração, talvez você queira refatorar o campo Status como uma enumeração.

O campo measureOfQuality possui um valor do tipo double que representa a qualidade de memoryMatrix do objeto Bee. No caso do TSP, uma medida natural da qualidade da solução é o comprimento do caminho representado pelo objeto memoryMatrix. Observe que, nessa situação, caminhos mais curtos são melhores e, por isso, valores menores no campo measureOfQuality representam soluções melhores do que valores mais altos. Todas as implementações de SBC devem ter alguma maneira de computar a medida de qualidade da solução. Em muitas situações, essa medida é melhor representada por um valor do tipo double.

O terceiro campo de dados comum na classe Bee é chamado de numberOfVisits. Esse campo possui um valor int que representa o número de vezes que o objeto Bee visitou uma fonte de alimento/solução de problema específica, sem encontrar uma solução aproximada melhor. Esse campo é usado para simular uma abelha visitando uma fonte de alimento até que a fonte se esgote. Para uma abelha ativa, quando o valor do campo numberOfVisits excede um valor limite, a abelha simulada terá praticamente esgotado a fonte de alimento e passará para o status de inativa (e uma abelha inativa passará para o status de ativa).

O construtor Bee aceita valores para os quatro campos de dados: Status, memoryMatrix, measureOfQuality e numberOfVisits. Observe que o construtor Bee deve aceitar um valor para measureOfQuality, pois Bee não pode computar isso diretamente de seu campo memoryMatrix. A determinação da medida de qualidade depende das informações armazenadas no objeto CitiesData específico do problema.

A definição da classe Bee contém um método ToString, que expõe os valores dos quatro campos de dados. O método Bee.ToString não é absolutamente necessário, mas pode ser bastante útil durante o desenvolvimento de SBC para ajudar a descobrir bugs usando instruções WriteLine.

Os campos de dados de Hive

O código da classe Hive é apresentado na Figura 5. Existem 14 campos de dados de Hive, e compreender a finalidade de cada um deles é a chave para entender como implementar um algoritmo SBC específico.

Figura 5 Os 14 campos de dados de Hive

static Random random = null;

public CitiesData citiesData;

public int totalNumberBees; 
public int numberInactive; 
public int numberActive;
public int numberScout;

public int maxNumberCycles;
public int maxNumberVisits; 

public double probPersuasion = 0.90;
public double probMistake = 0.01; 

public Bee[] bees;
public char[] bestMemoryMatrix;
public double bestMeasureOfQuality;
public int[] indexesOfInactiveBees;

Para simplificar e facilitar a depuração com instruções WriteLine, todos os 14 campos de dados são definidos com escopo público. Você talvez queira restringir os campos para um escopo particular e criar propriedades para os campos que devem ser acessados fora da definição de classe.

O primeiro campo é chamado de random e é do tipo Random. Os algoritmos SBC são probabilísticos e o objeto random é usado para gerar números pseudoaleatórios para diversas finalidades. O objeto random será instanciado no construtor Hive.

O segundo campo de dados é um objeto do tipo CitiesData. A implementação de SBC precisa saber detalhes do problema que está sendo resolvido. Na maioria dos casos, assim como neste aqui, os dados do problema são representados como um objeto. Lembre-se que CitiesData possui uma lista dos nomes das cidades e um método que retorna a distância entre duas cidades quaisquer.

Do terceiro ao sexto campo de dados são variáveis int que possuem o número total de abelhas, o número de abelhas inativas, o número de abelhas ativas e o número de abelhas protetoras. Conforme mencionado anteriormente, como cada abelha representa uma solução em potencial, quanto mais abelhas na colmeia, melhor. Entretanto, grandes números de abelhas diminuem o desempenho do programa.

O sétimo campo de dados, maxNumberCycles, é um valor limite usado para restringir o tempo de execução do método Solve. Um ciclo representa o processamento de cada abelha da colmeia.

O oitavo campo de dados, maxNumberVisits, é um valor limite usado para impedir que uma abelha permaneça muito tempo em uma solução específica. Em cada iteração do loop de processamento principal do método Solve, se uma abelha não encontrar uma fonte de alimento próxima de melhor qualidade, o contador numberOfVisits da abelha será incrementado. Se o contador numberOfVisits de um objeto Bee exceder o valor limite de maxNumberVisits, a abelha passará para o estado inativa.

O nono campo de dados, probPersuasion, é um valor limite probabilístico usado para determinar se uma abelha inativa que observa a dança agitada de uma abelha que retornou para a colmeia com uma solução melhor será persuadida a atualizar sua memória com a solução melhor.

O valor de probPersuasion é inserido no código como 0,90, o que significa que uma abelha inativa será persuadida a aceitar uma solução melhor aproximadamente 90% das vezes. O valor 0,90 para probPersuasion baseia-se em descobertas de pesquisas, mas você talvez queira experimentar outros valores. Valores maiores produzirão um algoritmo SBC que converge para uma solução mais rapidamente, com o risco de uma maior probabilidade de chegar a uma solução não ideal.

O décimo campo de dados, probMistake, é um valor limite probabilístico usado para determinar se uma abelha ativa cometerá um erro — ou seja, se ela rejeitará incorretamente uma solução aproximada que é melhor do que a solução atual ou se ela aceitará incorretamente uma solução aproximada que é pior do que a solução atual. O valor de probMistake é inserido no código como 0,01, o que significa que uma abelha ativa cometerá um erro na avaliação de uma solução aproximada cerca de 1% das vezes.

O décimo primeiro campo de dados, bees, é uma matriz de objetos Bee. Lembre-se de que cada abelha tem um status (ativa, inativa, protetora), uma solução (memoryMatrix), uma medida de qualidade da solução (measureOfQuality) e um contador do número de vezes que uma fonte de alimento virtual específica foi visitada sem que uma fonte próxima melhor fosse encontrada (numberOfVisits). Como Bee é definido como uma classe, cada entrada na matriz bees é uma referência a um objeto Bee.

O décimo segundo campo de dados, bestMemoryMatrix, é uma matriz do tipo char e representa a melhor solução na matriz bees. Lembre-se de que, como os algoritmos de colônias de abelhas são implementações específicas de um meta-heurístico, a representação da solução de um problema irá variar de acordo com o problema. Uma abordagem de design alternativa para embutir no código uma definição de tipo de solução é parametrizar esse campo de dados como um tipo genérico. Quando utilizo um algoritmo SBC, eu geralmente estou tentando resolver um problema específico e, por isso, prefiro recodificar cada nova implementação de SBC desde o início.

O décimo terceiro campo de dados, bestMeasureOfQuality, é a medida de qualidade que corresponde à solução bestMemoryMatrix.

O último campo de dados de Hive, indexesOfInactiveBees, é uma matriz de int. Essa matriz possui os índices das abelhas na colmeia que estão atualmente inativas. Lembre-se de que as abelhas ativas podem passar para o estado inativa e vice-versa. Uma implementação do algoritmo SBC deve determinar com frequência as abelhas que estão inativas no momento em que uma abelha ativa realiza uma dança agitada virtual, e o armazenamento dos índices de abelhas inativas melhora o desempenho em comparação à alternativa de iterar toda a matriz bees e verificar o campo de dados Status de cada abelha.

Uma representação visual de um possível objeto Hive é apresentada na Figura 6. A colmeia apresentada possui 10 abelhas: 5 ativas, 2 protetoras e 3 inativas. As abelhas atualmente inativas estão nos índices 2, 7 e 4 da matriz bees. O objeto CitiesData possui 5 cidades. A melhor solução atual é:

A->B->E->C->D

Essa solução tem um comprimento de caminho, em unidades de distância, de:

1,0 + (3 * 1,0) + (2 * 1,5) + 1,0 = 8,0

Observe que o campo citiesData é uma referência a um objeto CitiesData definido fora do objeto Hive.

Figura 6 A representação de Hive

O construtor Hive

O código do construtor Hive é apresentado na Figura 7. O construtor Hive aceita sete parâmetros de entrada. Seis dos parâmetros são escalares e o outro é um objeto (citiesData). O parâmetro totalNumberBees é redundante no sentido de que pode ser determinado a partir de numberInactive, numberActive e numberScout, mas acredito que a melhoria na legibilidade vale o código extra.

Figura 7 Construtor Hive

public Hive(int totalNumberBees, int numberInactive,
  int numberActive, int numberScout, int maxNumberVisits,
  int maxNumberCycles, CitiesData citiesData) {

  random = new Random(0);
      
  this.totalNumberBees = totalNumberBees;
  this.numberInactive = numberInactive;
  this.numberActive = numberActive;
  this.numberScout = numberScout;
  this.maxNumberVisits = maxNumberVisits;
  this.maxNumberCycles = maxNumberCycles;

  this.citiesData = citiesData;

  this.bees = new Bee[totalNumberBees];
  this.bestMemoryMatrix = GenerateRandomMemoryMatrix();
  this.bestMeasureOfQuality = 
    MeasureOfQuality(this.bestMemoryMatrix);

  this.indexesOfInactiveBees = new int[numberInactive]; 

  for (int i = 0; i < totalNumberBees; ++i) {
    int currStatus; 
    if (i < numberInactive) {
      currStatus = 0; // inactive
      indexesOfInactiveBees[i] = i; 
    }
    else if (i < numberInactive + numberScout)
      currStatus = 2; // scout
    else
      currStatus = 1; // active
    
    char[] randomMemoryMatrix = GenerateRandomMemoryMatrix();
    double mq = MeasureOfQuality(randomMemoryMatrix);
    int numberOfVisits = 0;

    bees[i] = new Bee(currStatus, 
      randomMemoryMatrix, mq, numberOfVisits); 
        
    if (bees[i].measureOfQuality < bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix, 
        bees[i].memoryMatrix.Length);
      this.bestMeasureOfQuality = bees[i].measureOfQuality;
    }
  } 
}

O objeto aleatório de escopo de classe é instanciado com um valor de semente de 0. O fornecimento de um valor de semente permite que você reproduza os resultados. Em seguida, os seis valores de parâmetro de entrada dos campos de dados escalares são copiados para os campos de dados de Hive. O objeto Hive possui um total de 14 campos de dados; os valores limite de probPersuasion e probMistake são inseridos no código.

O construtor Hive obtém o parâmetro citiesData de entrada e atribui o campo citiesData ao parâmetro como uma referência. Uma alternativa a essa abordagem por referência é fazer uma nova cópia dos dados do problema, dessa maneira:

int n = citiesData.cities.Length;
this.citiesData = new CitiesData(n);

Essa abordagem utiliza mais memória, mas evita potenciais erros de efeito colateral. A abordagem alternativa pode ser usada se você estiver refatorando o código apresentado aqui para uma linguagem de programação que não oferece suporte a ponteiros ou referências.

Nesse ponto do construtor Hive, todas as entradas na matriz bees serão nulas. Em seguida, o construtor inicializa a melhor solução globalmente (ou seja, a melhor solução dentre todas as abelhas na colmeia) e a qualidade de solução correspondente:

this.bestMemoryMatrix = GenerateRandomMemoryMatrix();
this.bestMeasureOfQuality = 
  MeasureOfQuality(this.bestMemoryMatrix);

O método auxiliar GenerateRandomMemoryMatrix gera uma solução aleatória. O método auxiliar MeasureOfQuality aceita a solução gerada aleatoriamente e computa sua qualidade. Eu vou discutir o código desses dois métodos auxiliares posteriormente neste artigo.

Após inicializar a melhor solução global e sua qualidade correspondente, o construtor Hive aloca a matriz bees indexesOfInactiveBees usando o valor do campo numberInactive. Nesse ponto, todos os valores nessa matriz de índices serão igual a 0.

A próxima parte do código do construtor faz a iteração em cada objeto Bee da matriz bees e cria uma instância deles usando o construtor Bee. A lógica nesse loop pressupõe que as primeiras células numberInactive na matriz bees são abelhas inativas, as próximas células numberScout são abelhas protetoras e as células restantes são abelhas ativas.

Por exemplo, se houver cinco abelhas ativas, duas inativas e três protetoras, o construtor inicializará uma matriz bees de tamanho 10 e criará instâncias das células 0 e 1 como abelhas inativas, das células 2 a 4 como abelhas protetoras e das células 5 a 9 como abelhas ativas. Além disso, a matriz indexesOfInactiveBees terá o tamanho 2 e, inicialmente, possuirá os valores 0 e 1.

Após o status da abelha atual ser determinado com base na variável de índice de loop, uma solução gerada aleatoriamente será criada e sua qualidade correspondente será computada, o contador de número de visitas será explicitamente definido como 0 e o construtor Bee será chamado:

char[] randomMemoryMatrix = GenerateRandomMemoryMatrix();
double mq = MeasureOfQuality(randomMemoryMatrix);
int numberOfVisits = 0;
bees[i] = new Bee(currStatus, randomMemoryMatrix, 
  mq, numberOfVisits);

Depois de cada abelha ser instanciada, a qualidade da solução gerada aleatoriamente da abelha é verificada para definir se é melhor do que a melhor solução global. Em caso afirmativo, a solução da abelha atual e sua qualidade correspondente são copiadas nos campos bestMemoryMatrix e bestMeasureOfQuality. Observe que na verificação da qualidade de uma solução global melhor, um valor menor é melhor do que um valor maior, pois o valor de qualidade refere-se a comprimentos de caminhos e o TSP deseja minimizar o comprimento do caminho.

Em vez de copiar explicitamente a memória de uma abelha na matriz bestMemoryMatrix, uma abordagem alternativa é fazer a atribuição por referência. Essa abordagem melhora o desempenho às custas de um aumento na complexidade.

Três métodos de SBC essenciais

Toda implementação de algoritmos SBC deve ter três métodos específicos do problema: um método para gerar uma solução aleatória, um método para gerar uma solução aproximada relativa a uma determinada solução e um método para computar a qualidade de uma solução específica. Nesse exemplo de TSP, cada método é implementado de uma maneira personalizada e totalmente dependente do problema.

Uma alternativa de design é definir interfaces e implementá-las. A programação por meio de interfaces tem várias vantagens e desvantagens em comparação à abordagem utilizada sem interface, mas, na minha opinião, é principalmente uma questão de preferência pessoal. O método para gerar uma solução aleatória, GenerateRandomMemoryMatrix, está mostrado a seguir:

public char[] GenerateRandomMemoryMatrix() {
  char[] result = new char[this.citiesData.cities.Length];
  Array.Copy(this.citiesData.cities, result,
    this.citiesData.cities.Length);      
  for (int i = 0; i < result.Length; i++) {
    int r = random.Next(i, result.Length);
    char temp = result[r];
    result[r] = result[i];
    result[i] = temp;
  }
  return result;
}

Como uma solução para o problema TSP é uma matriz de char, na qual cada char representa uma cidade, o método GenerateRandomMemoryMatrix retorna uma matriz char. O tamanho da matriz de resultado local é alocado com base no objeto CitiesData do Hive, e as IDs das cidades armazenadas na referência do Hive ao objeto CitiesData são copiadas na matriz de resultado. A ordem dos valores na matriz de resultados é tornada aleatória usando o objeto random do escopo da classe e o algoritmo de ordem aleatória Fisher-Yates (às vezes, chamado de Knuth).

À primeira vista, pode parecer que o método GenerateRandomMemoryMatrix conceitualmente pertence ao objeto Bee. Entretanto, como a geração de uma solução aleatória depende, em parte, de dados específicos do problema (neste caso, CitiesData), colocar o método de geração de solução aleatória na definição geral de Hive é um design melhor.

O método para gerar uma solução aproximada, GenerateNeighborMemoryMatrix, é apresentado na Figura 8.

Figura 8 Gerando uma solução aproximada

public char[] GenerateNeighborMemoryMatrix(char[] memoryMatrix) {
  char[] result = new char[memoryMatrix.Length];
  Array.Copy(memoryMatrix, result, memoryMatrix.Length);

  int ranIndex = random.Next(0, result.Length);
  int adjIndex;
  if (ranIndex == result.Length - 1)
    adjIndex = 0;
  else
    adjIndex = ranIndex + 1;

  char tmp = result[ranIndex];
  result[ranIndex] = result[adjIndex];
  result[adjIndex] = tmp;  return result;
}

Um conceito importante nos algoritmos SBC é a ideia de que cada fonte de alimento virtual que representa uma solução possui algum tipo de aproximação. Sem o conceito de aproximação, toda a ideia de um algoritmo com base no comportamento das abelhas entre em colapso. No caso do TSP, em que uma solução pode ser retratada como uma matriz de IDs de cidades representando um caminho entre cidades, uma solução aproximada natural relativa a uma solução atual é uma permutação da solução atual, na qual duas cidades adjacentes foram trocadas.

Por exemplo, se uma solução atual do TSP for A, B, C, D, E, uma solução aproximada razoável será A, C, B, D, E. Isso não é tão óbvio se uma permutação em que duas cidades arbitrárias são trocadas (em oposição às duas cidades adjacentes) representar uma solução aproximada razoável. No exemplo anterior, A, D, C, B, E é uma solução aproximada razoável? Decidir sobre a definição de uma solução aproximada para um algoritmo SBC depende do problema e, normalmente, envolve critérios subjetivos.

O conceito de solução aproximada também serve para ilustrar, em parte, por que problemas combinatórios não numéricos são especialmente indicados para a solução por algoritmos SBC. Se um problema for inerentemente numérico, a ideia de uma aproximação é frequentemente difícil de ser definida de maneira satisfatória. Se um problema for inerentemente combinatório, a ideia de uma aproximação normalmente pode ser bem definida por algum formulário de permutação ou combinação matemática.

O método GenerateNeighborMemoryMatrix aceita uma representação atual de memoryMatrix da abelha de uma solução como um parâmetro de entrada e a copia em uma matriz de resultado. O método seleciona um único índice aleatório na matriz de resultado atual usando o objeto random do escopo da classe. Se o índice aleatório apontar para a última célula, a primeira e a última ID das cidades serão trocadas; caso contrário, se o índice aleatório apontar para qualquer célula que não seja a última, as IDs apontadas pelo índice aleatório e o próximo índice serão trocados.

O conceito de solução aproximada está relacionado ao valor de maxNumberVisits. Existem algumas pesquisas que indicam que um bom valor para maxNumberVisits deve ser cerca de cinco vezes o número de soluções aproximadas possível para uma determinada solução. Por exemplo, para três cidades (A, B, C), se uma solução aproximada for definida como trocando qualquer par de cidades adjacentes, existirão três possíveis soluções aproximadas (trocar A e B, trocar B e C, trocar A e C). Portanto, para 20 cidades, um valor razoável para maxNumberVisits seria 20 * 5 = 100.

O método para avaliar a qualidade da solução de uma abelha, MeasureOfQuality, é:

public double MeasureOfQuality(char[] memoryMatrix) {
  double answer = 0.0;
  for (int i = 0; i < memoryMatrix.Length - 1; ++i) {
    char c1 = memoryMatrix[i];
    char c2 = memoryMatrix[i + 1];
    double d = this.citiesData.Distance(c1, c2);
    answer += d;
  }
  return answer;
}

Para resolver um problema usando um algoritmo SBC, uma característica essencial do problema é que qualquer solução deve poder ser avaliada a fim de gerar uma medida de qualidade da solução. Em termos conceituais, um problema de otimização combinatório do mundo real quase sempre possui alguma medida de qualidade inerente e de senso comum. Entretanto, em termos práticos, a computação da medida de qualidade de uma solução pode ser difícil e demorada.

Neste exemplo, o método MeasureOfQuality apenas faz a iteração em cada par de IDs de cidades consecutivas na solução representado pelo parâmetro memoryMatrix, determina a distância entre cada par usando o método Distance do objeto CitiesData e acumula a distância total. Lembre-se de que os dados das cidades foram artificialmente construídos, de forma que a distância entre duas cidades quaisquer pudesse ser computada de maneira rápida e fácil usando a distância ordinal entre duas IDs de cidades. Mas, em um problema real, a distância entre duas cidades provavelmente teria de ser pesquisada em algum tipo de estrutura de dados. Em implementações de SBC, o método MeasureOfQuality geralmente é a rotina que domina o tempo de execução do programa. Dessa maneira, normalmente vale a pena se certificar de que esse método seja otimizado em relação ao desempenho — bem como que seja viável, tendo em vista os recursos de memória do sistema host.

O método Solve

O método Solve hospeda toda a lógica que simula o comportamento das abelhas operárias a fim de resolver um problema. O método Solve é moderadamente complexo e utiliza três métodos auxiliares: ProcessActiveBee, ProcessScoutBee e ProcessInactiveBee. Os métodos ProcessActiveBee e ProcessScoutBee, por sua vez, utilizam o método auxiliar DoWaggleDance. O método Solve é apresentado na Figura 9.

Figura 9 O método Solve

public void Solve(bool doProgressBar) {
  bool pb = doProgressBar;
  int numberOfSymbolsToPrint = 10; 
  int increment = this.maxNumberCycles / numberOfSymbolsToPrint;
  if (pb) Console.WriteLine("\nEntering SBC Traveling Salesman Problem algorithm main processing loop\n");
  if (pb) Console.WriteLine("Progress: |==========|");
  if (pb) Console.Write("           ");
  int cycle = 0;
      
  while (cycle < this.maxNumberCycles) {
    for (int i = 0; i < totalNumberBees; ++i) {
      if (this.bees[i].status == 1)
        ProcessActiveBee(i);
      else if (this.bees[i].status == 2)
        ProcessScoutBee(i);
      else if (this.bees[i].status == 0)
        ProcessInactiveBee(i);
    } 
    ++cycle;

    if (pb && cycle % increment == 0)
      Console.Write("^");
  } 

  if (pb) Console.WriteLine("");
}

A maior parte do trabalho real é delegada aos métodos auxiliares ProcessActiveBee, ProcessScoutBee e ProcessInactiveBee. Um parâmetro de entrada booliano é transferido para Solve para indicar se uma barra de progresso com base em texto rudimentar deve ser impressa. Isso é útil ao desenvolver um algoritmo SBC a fim de monitorar a velocidade da implementação e ajudar a revelar afunilamentos no desempenho. Essa abordagem pressupõe que o método Solve faz parte de um aplicativo de console.

O valor do parâmetro booliano é transferido para uma variável booliana local chamada pb, apenas para ter uma variável de nome curto com a qual trabalhar. O valor de numberOfSymbolsToPrint é definido como 10, de forma que cada incremento na barra de status represente 10% do progresso total, o qual é determinado pelo valor de maxNumberCycles (a variável de incremento é usada para determinar quantos ciclos representam 10% do progresso).

Depois da variável de controle de loop, cycle, ser inicializada como 0, um while é usado para processar cada abelha na colmeia. Um loop for também poderia ser facilmente utilizado. Em cada ciclo, a matriz bees é iterada usando um loop for e cada objeto Bee é processado pelo método auxiliar apropriado. Após cada abelha ser processada, se o parâmetro booliano doProgressBar for igual a true, o código usará o operador de módulo % para verificar se é o momento de imprimir uma atualização na barra de progresso usando um caractere ^.

O método ProcessActiveBee

O método ProcessActiveBee é o coração de um algoritmo SBC, além de ser o método mais complexo em termos de tamanho de código e ramificação. O método ProcessActiveBee é apresentado na Figura 10.

Figura 10 O método ProcessActiveBee

private void ProcessActiveBee(int i) {
  char[] neighbor = GenerateNeighborMemoryMatrix(bees[i].memoryMatrix);
  double neighborQuality = MeasureOfQuality(neighbor); 
  double prob = random.NextDouble();
  bool memoryWasUpdated = false;
  bool numberOfVisitsOverLimit = false; 

  if (neighborQuality < bees[i].measureOfQuality) { // better
    if (prob < probMistake) { // mistake
      ++bees[i].numberOfVisits;
      if (bees[i].numberOfVisits > maxNumberVisits)
        numberOfVisitsOverLimit = true;
    }
    else { // No mistake
      Array.Copy(neighbor, bees[i].memoryMatrix, neighbor.Length);
      bees[i].measureOfQuality = neighborQuality;
      bees[i].numberOfVisits = 0; 
      memoryWasUpdated = true; 
    }
  }
  else { // Did not find better neighbor
    if (prob < probMistake) { // Mistake
      Array.Copy(neighbor, bees[i].memoryMatrix, neighbor.Length);
      bees[i].measureOfQuality = neighborQuality;
      bees[i].numberOfVisits = 0;
      memoryWasUpdated = true; 
    }
    else { // No mistake
      ++bees[i].numberOfVisits;
      if (bees[i].numberOfVisits > maxNumberVisits)
        numberOfVisitsOverLimit = true;
    }
  }

  if (numberOfVisitsOverLimit == true) {
    bees[i].status = 0; 
    bees[i].numberOfVisits = 0;
    int x = random.Next(numberInactive); 
    bees[indexesOfInactiveBees[x]].status = 1; 
    indexesOfInactiveBees[x] = i; 
  }
  else if (memoryWasUpdated == true) {
    if (bees[i].measureOfQuality < this.bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix,
        bees[i].memoryMatrix.Length); 
      this.bestMeasureOfQuality = bees[i].measureOfQuality
    }
    DoWaggleDance(i);
  }
  else {
    return;
  }
}

O método ProcessActiveBee aceita um parâmetro de entrada único, i, que é o índice de abelhas na matriz bees. A abelha ativa primeiro obtém uma solução aproximada relativa à sua solução atual armazenada em memoryMatrix e, em seguida, determina a qualidade da aproximação:

char[] neighbor =
  GenerateNeighborMemoryMatrix(bees[i].memoryMatrix); 
double neighborQuality = MeasureOfQuality(neighbor);

Em seguida, o algoritmo configura três variáveis locais que serão utilizadas posteriormente:

double prob = random.NextDouble();)
bool memoryWasUpdated = false; 
bool numberOfVisitsOverLimit = false;

A variável prob possui um valor entre 0,0 e 1,0 e será comparada com o valor do campo probMistake a fim de determinar se a abelha cometeu um erro ao avaliar a solução aproximada — ou seja, se ela rejeitou uma solução aproximada melhor ou aceitou uma solução aproximada pior.

O valor booliano de memoryWasUpdated será usado para determinar se a abelha ativa deve (valor igual a true) ou não (valor igual a false) realizar uma dança agitada para as abelhas inativas. O valor booliano de numberOfVisitsOverLimit será comparado com o campo maxNumberVisits para determinar se a abelha esgotou uma fonte de alimento específica sem encontrar uma solução aproximada melhor e, em caso afirmativo, se deve passar do status ativa para o status inativa.

Se a abelha atual encontrar uma solução aproximada melhor, o algoritmo determinará se ela cometeu um erro e rejeitou a solução aproximada melhor ou se ela aceitou a solução aproximada melhor. De maneira semelhante, se a abelha atual não encontrar uma solução aproximada melhor, o algoritmo determinará se ela cometeu um erro e aceitou a pior solução aproximada ou se ela não cometeu nenhum erro e rejeitou a solução aproximada.

Observe que existem dois tipos diferentes de erros possíveis, mas ambos têm a mesma probabilidade: probMistake = 0,01. Existem algumas pesquisas que sugerem que o uso de duas probabilidades diferentes para os dois tipos de erros diferentes não melhora a eficácia dos algoritmos SBC, mas você talvez queira experimentar dois valores limite diferentes.

Depois de a abelha ativa aceitar ou rejeitar a solução aproximada, o algoritmo verifica se o contador de número de visitas excedeu o limite maxNumberVisits. Em caso afirmativo, o status da abelha atual é convertido para inativa, uma abelha inativa selecionada aleatoriamente passa para o status ativa e a matriz indexesOfInactiveBees é atualizada. EM seguida, o algoritmo verifica se a memória da abelha foi atualizada. Se sim, a nova solução é verificada para saber se ela é uma nova solução global melhor e, em seguida, um método auxiliar particular, DoWaggleDance, é chamado para simular o retorno da abelha para a colmeia e a transferência das informações sobre a nova fonte de alimento para as abelhas inativas.

O método DoWaggleDance

O método auxiliar DoWaggleDance simula uma abelha ativa ou protetora voltando para a colmeia e realizando uma dança agitada para as abelhas inativas a fim de transmitir informações sobre o local e a qualidade de uma fonte de alimento. Este é o método DoWaggleDance:

private void DoWaggleDance(int i) {
  for (int ii = 0; ii < numberInactive; ++ii) {
    int b = indexesOfInactiveBees[ii]; 
    if (bees[i].measureOfQuality < bees[b].measureOfQuality) {
      double p = random.NextDouble(); 
      if (this.probPersuasion > p) {
        Array.Copy(bees[i].memoryMatrix, bees[b].memoryMatrix,
          bees[i].memoryMatrix.Length);
        bees[b].measureOfQuality = bees[i].measureOfQuality;
      } 
    } 
  } 
}

O parâmetro de entrada i é o índice da abelha atual que está realizando a dança agitada virtual. A medida de qualidade da solução da abelha atual é comparada com a medida de qualidade de cada abelha inativa. Se a solução da abelha atual for melhor e a abelha inativa atual for convencida (com uma probabilidade de probPersuasion = 0,90), a memória da abelha atual será copiada para a memória da abelha inativa.

Observe que existem muitas oportunidades de inserir verificações de erros no código apresentado neste artigo. Por exemplo, no loop for em DoWaggleDance, você talvez queira verificar o status da abelha inativa atual com:

if (bees[b].status != 0) throw new Exception(. . .);

Ou você talvez queira verificar o contador de número de visitas da abelha inativa com:

if (bees[b].numberOfVisits != 0) throw new Exception(. . .);

ProcessScoutBee e ProcessInactiveBee

O método auxiliar ProcessScoutBee utilizado pelo método Solve simula a ação de uma abelha protetora procurando aleatoriamente por fontes de alimentos atraentes. O método ProcessScoutBee é apresentado na Figura 11.

Figura 11 O método ProcessScoutBee

private void ProcessScoutBee(int i) {
  char[] randomFoodSource = GenerateRandomMemoryMatrix();
  double randomFoodSourceQuality = 
    MeasureOfQuality(randomFoodSource);
  if (randomFoodSourceQuality < bees[i].measureOfQuality {
    Array.Copy(randomFoodSource, bees[i].memoryMatrix,
      randomFoodSource.Length);
    bees[i].measureOfQuality = randomFoodSourceQuality;
    if (bees[i].measureOfQuality < bestMeasureOfQuality) {
      Array.Copy(bees[i].memoryMatrix, this.bestMemoryMatrix,
        bees[i].memoryMatrix.Length);
      this.bestMeasureOfQuality = bees[i].measureOfQuality;
    } 
    DoWaggleDance(i);
  }
}

O parâmetro de entrada i representa o índice de uma abelha protetora na matriz bees. Uma abelha protetora gera uma solução aleatória, verifica se essa solução é melhor do que a solução atualmente na memória e, em caso afirmativo, copia a solução aleatória na memória. Lembre-se de que valores menores de qualidade são melhores. Se a abelha protetora tiver encontrado uma solução melhor, o algoritmo verificará se a nova solução é uma solução global melhor.

Observe que, de maneira diferente das abelhas ativas, nessa implementação de SBC, as abelhas protetoras nunca cometem erros ao avaliar a qualidade de uma fonte de alimento. Atualmente, não existem pesquisas sobre o efeito de erros de abelhas protetoras.

O método ProcessInactiveBee é:

`private void ProcessInactiveBee(int i) {
  return;
}
private void ProcessInactiveBee(int i) {
  return;
}

Nessa implementação de SBC, as abelhas inativas são exatamente isso: inativas. Por isso, o método ProcessInactiveBee é meramente um espaço reservado para o caso de você desejar implementar alguma lógica dependente do problema para uma abelha inativa. Uma possível modificação seria alterar aleatoriamente a memória de uma abelha inativa com alguma probabilidade muito pequena.

Conclusão

O processo geral de implementação de um algoritmo SBC começa com a identificação do problema. Problemas combinatórios complexos e não numéricos sem nenhuma solução determinística prática geralmente são bons candidatos para uma solução de SBC. O problema em questão deve ter uma maneira de representar uma solução (frequentemente, uma matriz) e cada solução deve ter algum tipo de solução aproximada e uma medida de qualidade de solução.

Por exemplo, considere o problema de dividir um gráfico em duas partes, de forma que o número de conexões dentro de cada parte seja maximizado e o número de conexões entre as duas partes seja minimizado. Esse problema de partição de gráfico é combinatório e não existe nenhum algoritmo rápido que encontre a solução ideal — embora existam algoritmos determinísticos bons em encontrar soluções próximas ao ideal. Existem muitos outros problemas NP-completo e NP-difícil que podem ser resolvidos usando um SBC.

Os algoritmos SBC baseiam-se no comportamento de sistemas naturais. Existem outros algoritmos desse tipo, incluindo algoritmos genéticos (ou GA, Genetic Algorithms) que se baseiam na evolução e seleção natural, algoritmos da otimização da colônia de formigas (ou ACO, Ant Colony Optimization) baseados no comportamento das formigas e algoritmos de recozimento simulado (ou SA, Simulated Annealing) que se baseiam nas propriedades físicas do resfriamento de metais.

Os algoritmos baseados em sistemas naturais geralmente são fáceis de implementar em relação a abordagens determinísticas. Entretanto, os algoritmos com base em sistemas naturais normalmente exigem a especificação de valores para diversos parâmetros que tendem a fazer diferenciações em relação a seus efeitos sobre a precisão e a velocidade de convergência da solução. No caso de um SBC, os parâmetros com diferenciação que devem ser adaptados para cada problema incluem a quantidade de cada tipo de abelha, o número máximo de visitas antes de uma fonte de alimento ser esgotada, o valor limite da probabilidade de persuasão de abelhas inativas e a probabilidade de cometer erros de abelhas ativas.

Embora os algoritmos SBC não sejam aplicáveis a todos os problemas, em alguns cenários, eles podem ser ferramentas extremamente poderosas. 

Dr. James McCaffrey trabalha para a Volt Information Sciences Inc., onde gerencia o treinamento técnico de engenheiros de software que trabalham no campus de Washington da Microsoft Redmond. Ele trabalhou em vários produtos da Microsoft, como Internet Explorer e MSN Search. O Dr. McCaffrey é autor de “.NET Test Automation Recipes” (Apress, 2006) e pode ser contatado pelo email jammc@microsoft.com.

Agradecemos aos seguintes especialistas técnicos pela revisão deste artigo: Dan Liebling e Anne Loomis Thompson, ambos da Microsoft Research