Algoritmi naturali

Algoritmi SBC per risolvere problemi impossibili

James McCaffrey

Scarica il codice di esempio

Gli algoritmi SBC (Simulated Bee Colony) modellano il comportamento delle api e possono essere utilizzati per cercare soluzioni a problemi combinatori complessi o impossibili. In questo articolo verrà illustrato il concetto di algoritmo SBC e verranno descritti i tipi di problemi che è possibile risolvere con questi algoritmi. Verrà inoltre presentato un esempio completo in cui viene utilizzato un algoritmo SBC per risolvere il Problema del commesso viaggiatore.

Per avere un'idea degli algoritmi SBC ed entrare nell'ottica di questo articolo, è opportuno esaminare il programma demo illustrato in esecuzione nella Figura 1. Il programma utilizza un algoritmo SBC per analizzare un gruppo di 20 città (con etichette dalla A alla T) e cercare il percorso più breve per visitare ogni città una volta. I dati della città vengono costruiti in modo artificiale, in modo tale che il percorso migliore inizi alla città A e continui fino alla città T, in ordine, con una lunghezza di 19,0 unità.

Figura 1 Demo - Simulazione di una colonia di api

"Dietro le quinte", l'algoritmo SBC crea un'istanza di un alveare di 100 api simulate, ognuna delle quali presenta una potenziale soluzione casuale. Inizialmente, la migliore soluzione potenziale presenta un percorso con lunghezza pari a 95,0 unità. L'algoritmo SBC inserisce un ciclo di elaborazione, mostrato dall'indicatore di stato basata su testo, che simula il comportamento delle comuni api da miele bottinatrici. Al termine del ciclo di elaborazione SBC, la soluzione migliore presenterà 16 posizioni di città corrette su 20 con una lunghezza di percorso pari a 26,5 (molto vicina alla soluzione ottimale).

Gli algoritmi SBC vengono spesso definiti metaeuristici, in quanto forniscono una struttura generale e un insieme di linee guida per creare la soluzione a un problema, anziché fornire una prescrizione di soluzione estremamente dettagliata. In questo articolo viene illustrato un esempio di utilizzo di un algoritmo SBC per risolvere un problema specifico. Una volta compreso il modo in cui un algoritmo di questo tipo consente di risolvere un problema, è possibile personalizzare quello indicato in questo articolo per risolvere altri problemi. Gli algoritmi SBC sono ideali per risolvere complessi problemi combinatori che non prevedono soluzioni pratiche deterministiche.

In questo articolo si presuppone che gli utenti dispongano di competenze di programmazione di livello intermedio. L'esempio in questo articolo viene codificato tramite C#, ma è disponibile il codice completo per consentirne il refactoring ad altri linguaggi di programmazione. Gli utenti troveranno sicuramente interessante questo articolo e grazie alla possibilità di utilizzare algoritmi SBC potranno arricchire le competenze finora acquisite.

Sulle api

Nel tempo le api comuni, quali l'Apis mellifera, ricoprono diversi ruoli all'interno della propria colonia. Un tipico alveare può contenere da 5.000 a 20.000 api. Le api mature (dai 20 ai 40 giorni) divengono in genere api bottinatrici, che a loro volta possono ricoprire tre ruoli: attive, esploratrici e inattive.

Le api bottinatrici attive volano a una fonte di cibo, esaminano le fonti vicine, raccolgono il cibo e tornano all'alveare.

Le api esploratrici controllano l'area circostante l'alveare (fino a un massimo di circa 130 chilometri quadrati) in cerca di nuove fonti di cibo. Circa il 10% delle api bottinatrici in un alveare sono api esploratrici.

In un determinato momento, alcune api bottinatrici diventano inattive e rimangono in attesa in prossimità dell'entrata dell'alveare. Quando le api bottinatrici attive ed esploratrici tornano all'alveare, a seconda della qualità della fonte individuata, eseguono una danza per le api inattive in attesa. È stato dimostrato che con questo tipo di danza le api segnalano alle compagne la posizione e la qualità del bottino. A questo punto le api ricevono le informazioni sulla fonte di cibo e possono diventare attive.

In generale, un'ape bottinatrice attiva continua a raccogliere cibo da una fonte finché non si esaurisce e quindi diviene inattiva.

Il Problema del commesso viaggiatore

Il Problema del commesso viaggiatore è uno dei problemi esaminati più di frequente nella ricerca informatica. Esistono vari tipi di problemi del commesso viaggiatore, ma a livello generale il problema consiste nell'individuare il percorso più breve per visitare ogni città in un gruppo una sola volta.

Osservando la Figura 1 si noterà che il programma demo utilizza un gruppo di 20 città etichettate in modo arbitrario da A a T. Un percorso valido è costituito da un gruppo ordinato di etichette delle 20 città, in cui ogni città viene indicata una sola volta. Esiste dunque un totale di 20! = 2.432.902.008.176.640.000 possibili percorsi.

"Dietro le quinte" è presente un valore di distanza associato a ogni coppia di città. Per semplificare, se la città c1 è minore della città c2, la distanza tra c1 e c2 rappresenta un valore di distanza di 1,0 unità rispetto alla distanza ordinale tra le etichette delle città. Se c1 è maggiore di c2, la distanza tra c1 e c2 è di 1,5 unità rispetto alla distanza ordinale. La distanza da A a B è pertanto pari a 1,0 unità arbitrarie, la distanza da B ad A è di 1,5 unità, la distanza da A a C è di 2,0 unità e così via. Il percorso migliore per visitare ogni città una sola volta risulterà quindi A -> B-> C -> ... -> T e la lunghezza migliore (più breve) risulterà (20-1) * 1,0 = 19,0.

Nella maggior parte degli scenari di problemi del commesso viaggiatore, le distanze tra le città non verrebbero calcolate in modo artificiale, ma verrebbero probabilmente archiviate in una struttura di dati di ricerca. Alcune variazioni di questo problema presuppongono che ogni città sia connessa a un'altra, altre che le città non siano del tutto interconnesse. Inoltre alcune variazioni presuppongono che la distanza da una città c1 a una città c2 coincida con la distanza dalla città c2 alla città c1, altre non ammettono questo presupposto bidirezionale.

Se non in situazioni estreme, non è possibile applicare un approccio drastico per individuare il percorso più breve. Ad esempio, con 20 città, anche se si potesse valutare 1 milione di percorsi al secondo, sarebbero necessari 77.000 anni per esaminare tutti i 20! possibili percorsi. Questo tipo di problema di ottimizzazione delle combinazioni, estremamente complesso, può essere gestito in modo ideale con gli algoritmi SBC.

Il problema fittizio viene implementato in una classe denominata CitiesData, come illustrato nella Figura 2. Il codice sorgente completo per il programma demo SBC è disponibile all'indirizzo code.msdn.microsoft.com/mag201104BeeColony.

Figura 2 Definizione della 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;
  }
}

La definizione di una classe o di una struttura di dati che rappresenta un problema specifico sarà diversa da quella illustrata in questo esempi, ma per estensione i problemi risolvibili con un algoritmo SBC possono essere rappresentati con un array non numerico, una matrice non numerica o una matrice di matrici non numerica.

Il costruttore CitiesData accetta un valore per il numero di città e assegna alla prima città l'etichetta A, alla seconda città l'etichetta B e così via.

Il metodo Distance viene definito in modo unidirezionale, come già descritto, e presuppone che qualsiasi città possa essere raggiunta da un'altra città.

Il metodo ShortestPathLength restituisce la lunghezza di percorso ottimale per la definizione Distance fornita. Nella maggior parte dei casi SBC l'utente non disporrà delle informazioni necessarie per implementare un metodo che restituisce la soluzione ottimale.

Il metodo NumberOfPossiblePaths elabora n!, in cui n rappresenta il numero di città. In alcuni scenari di problemi del commesso viaggiatore il numero di percorsi possibili è n-1! (se la città iniziale non è determinate) e in altri il numero di percorsi possibili è n/2! (se la direzione del percorso non è determinante).

Il metodo ToString utilizza la concatenazione di stringhe anziché la classe StringBuilder (più efficace) per assemblare una stringa con dati descrittivi). La concatenazione di stringhe consente di semplificare il refactoring ad altri linguaggi di programmazione.

In questo articolo, per mantenere il codice relativamente breve e pulito, utilizzerò scorciatoie da evitare nel codice di produzione, ad esempio la rimozione della maggior parte dei controlli di errori. Il metodo NumberOfPossiblePaths non prevede un overflow numerico se il risultato è maggiore del valore di long.MaxValue.

Struttura del programma SBC

L'algoritmo SBC illustrato nella Figura 1 viene implementato come applicazione di console C#. La struttura generale del programma è indicata nella Figura 3. La struttura del programma SBC è relativamente semplice e utilizza solo lo spazio dei nomi System di base. Sono disponibili tre classi: la classe Program, che ospita un solo metodo Main, la classe Hive, che ospita l'intera logica dell'algoritmo SBC, e la classe CitiesData illustrata nella sezione precedente dell'articolo. Alla classe Hive non viene in genere assegnato un nome più specifico come TravelingSalesmanHive, anche se le implementazioni dell'algoritmo SBC sono strettamente dipendenti dal problema specifico che dovranno risolvere.

Figura 3 Struttura generale del programma

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

Il metodo Main è piuttosto semplice. Dopo aver visualizzato un messaggio iniziale, verrà creata un'istanza dell'oggetto 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"));

In molti scenari SBC i dati del problema si trovano in un archivio esterno, ad esempio un file di testo o un database SQL, e verranno caricati tramite un apposito costruttore o un metodo di caricamento nelle righe di myProblemData.Load(dataFile).

Successivamente viene preparato e chiamato il costruttore Hive:

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);

Come illustrato in dettaglio nelle sezioni seguenti di questo articolo, un algoritmo SBC utilizza tre tipi di oggetti Bee: attivi, esploratori e inattivi. Sebbene i conteggi di ogni tipo di oggetto Bee possano essere hardcoded, nella maggior parte degli scenari è opportuno passare questi conteggi come parametri al costruttore Hive, in modo da consentire l'ottimizzazione delle prestazioni dell'algoritmo.

Il valore della variabile totalNumberBees può essere derivato da altre tre variabili, ma la variabile extra migliora la leggibilità del codice in questo punto. Il numero totale di oggetti Bee dipenderà dal problema specifico. Un numero maggiore di oggetti è sicuramente consigliabile, ma determina rallentamenti nell'esecuzione del programma. In termini di rapporti, alcune ricerche indicano come percentuali ideali di oggetti Bee attivi, esploratori e inattivi rispettivamente il 75%, il 10% e il 15% circa. 

Più avanti verrà spiegato il valore 100 utilizzato per la variabile maxNumberVisits e relativo al numero di soluzioni vicine in rapporto a una determinata soluzione.

La variabile maxNumberCycles consente di controllare la frequenza di reiterazione della routine Solve. Si tratta di un valore necessario, in quanto negli scenari di algoritmi SBC non è in genere possibile stabilire il momento in cui è stata raggiunta una soluzione ottimale (in caso contrario, il problema non sussisterebbe). In questo caso il valore di maxNumberCycles è stato limitato a 3.460, in modo che l'algoritmo SBC non produca un risultato perfetto. Sebbene però gli algoritmi SBC possano produrre un risultato ottimale, non è in genere possibile prevedere l'esito ed è quindi necessario accettare la possibilità di un risultato "buono".

In fase di esecuzione, il costruttore crea una raccolta di oggetti Bee, ognuno con una soluzione casuale. L'oggetto Hive tiene traccia del percorso generale migliore (più breve) rilevato in tutti gli oggetti Bee e la lunghezza del percorso associato alla soluzione migliore.

Per concludere, dopo aver chiamato il costruttore Hive, il metodo Main utilizza il metodo ToString per visualizzare i valori Hive iniziali generati in modo casuale, chiama il metodo Solve con un parametro indicante la necessità di stampare un indicatore dello stato basato su testo e quindi visualizza il percorso migliore e la relativa lunghezza individuata:

...
  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");
}

Classe Bee

Come illustrato nella Figura 3, la classe Hive contiene una definizione della classe Bee nidificata. Nella Figura 4 sono elencati i dettagli della definizione della classe Bee.

Figura 4 Definizione della 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;
  }
}

La classe Bee presenta tre campi di dati comuni a tutte le implementazioni SBC e un campo di dati specifico del problema. Questo campo è denominato memoryMatrix. Ogni implementazione SBC deve corrispondere a un modo per rappresentare una soluzione. Nel caso del Programma del commesso viaggiatore di questo articolo, una soluzione può essere rappresentata da un array di tipo char. È opportuno sottolineare che l'oggetto che rappresenta una soluzione è strettamente dipendente dal problema e ogni problema deve essere analizzato separatamente per produrre una rappresentazione significativa di soluzione.

Il campo denominato Status contiene un valore int che indica il tipo dell'oggetto Bee: 0 per inattivo, 1 per attivo e 2 per esploratore. In caso di codifica in un linguaggio che supporta tipi di enumerazione, è opportuno eseguire il refactoring del campo status come enumerazione.

Il campo measureOfQuality contiene un valore doppio che rappresenta la validità dell'elemento memoryMatrix dell'oggetto Bee. Nel caso del Problema del commesso viaggiatore, una misura naturale della qualità della soluzione è costituita dalla lunghezza del percorso rappresentata dall'oggetto memoryMatrix. In questa situazione sono preferibili lunghezze di percorso più brevi e pertanto valori inferiori del campo measureOfQuality rappresentano soluzioni migliori. Ogni implementazione SBC deve corrispondere a un modo per calcolare una misura della qualità della soluzione. In molti casi la rappresentazione ideale di questa misura è costituita da una valore di tipo double.

Il terzo campo di dati comune nella classe Bee è denominato numberOfVisits. Questo campo contiene un valore int che rappresenta il numero di volte in cui l'oggetto Bee ha visitato una particolare fonte di cibo/soluzione per il problema, senza individuare una migliore soluzione vicina. Questo campo consente di simulare un oggetto Bee che esplora una fonte di cibo finché non la esaurisce. Per un oggetto Bee attivo, se il valore del campo numberOfVisits supera un valore soglia, l'oggetto Bee simulato avrà virtualmente esaurito la riserva di cibo e passerà allo stato inattivo (e un oggetto Bee inattivo passerà allo stato attivo).

Il costruttore Bee accetta valori per i quattro campi di dati (status, memoryMatrix, measureOfQuality e numberOfVisits). È importante sottolineare che il costruttore Bee deve accettare un valore per measureOfQuality, poiché una classe Bee non può calcolarlo direttamente dal campo memoryMatrix. La capacità di determinare la misura della qualità dipende dalle informazioni archiviate nell'oggetto CitiesData specifico del problema.

La definizione della classe Bee contiene un metodo ToString, che espone i valori dei quattro campi di dati. Il metodo Bee.ToString non è assolutamente necessario, ma può risultare utile in fase di sviluppo SBC per individuare eventuali bug mediante istruzioni WriteLine.

Campi di dati Hive

Nella Figura 5 è illustrato il codice della classe Hive. Esistono 14 campi di dati Hive e comprendere lo scopo di ogni campo significa comprendere come implementare un algoritmo SBC specifico.

Figura 5 I 14 campi di dati 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;

Per semplicità e ai fini di un'esecuzione semplificata del debug con istruzioni WriteLine, tutti i 14 campi di dati sono definiti con ambito pubblico. È possibile restringere i campi all'ambito privato e creare proprietà per questi i campi a cui è necessario accedere all'esterno della definizione della classe.

Il primo campo è denominato in modo casuale ed è di tipo Random. Gli algoritmi SBC sono probabilistici e l'oggetto Random viene utilizzato per generare numeri pseudocasuali per vari scopi. Verrà creata un'istanza dell'oggetto nel costruttore Hive.

Il secondo campo di dati è un oggetto di tipo CitiesData. L'implementazione SBC deve conoscere i dettagli del problema in fase di risoluzione. Nella maggior parte dei casi, come in questo, i dati del problema sono rappresentati come un oggetto. Tenere presente che CitiesData contiene un elenco di etichette di città e un metodo che restituisce la distanza tra due città qualsiasi.

I campi di dati dal terzo al sesto sono variabili int che contengono il numero totale di oggetti Bee, il numero di oggetti Bee inattivi, attivi ed esploratori. Come già menzionato, poiché ogni oggetto Bee rappresenta una potenziale soluzione, è opportuno avere un numero maggiore di oggetti Bee possibile nel costruttore Hive. Un numero elevato di oggetti Bee comporta tuttavia una riduzione nelle prestazioni del programma.

Il settimo campo di dati, maxNumberCycles, è un valore soglia utilizzato per limitare la durata di esecuzione del metodo Solve. Un ciclo rappresenta l'elaborazione di ogni oggetto Bee nel costruttore.

L'ottavo campo di dati, maxNumberVisits, è un valore soglia che impedisce a un oggetto Bee di rimanere troppo a lungo su una specifica soluzione. In ogni iterazione del ciclo di elaborazione principale nel metodo Solve, se un oggetto Bee non trova una fonte di cibo vicina di qualità migliore, viene incrementato il contatore numberOfVisits dell'oggetto. Se il contatore numberOfVisits in un oggetto Bee supera il valore soglia di maxNumberVisits, l'oggetto passa a uno stato inattivo.

Il nono campo di dati, probPersuasion, è un valore di soglia probabilistico che consente di determinare se un oggetto Bee inattivo che osserva la danza di un oggetto Bee tornato nel costruttore Hive con una soluzione migliore verrà convinto ad aggiornare la propria memoria con la soluzione.

Il valore di probPersuasion è hardcoded pari a 0,90, ovvero un oggetto Bee inattivo verrà convinto ad accettare una soluzione migliore il 90% delle volte. Il valore di 0,90 per probPersuasion si basa su alcune ricerche svolte, ma è possibile sperimentare altri valori. Valori superiori produrranno un algoritmo SBC che convergerà più rapidamente in una soluzione, con il rischio di convergere con molta probabilità in una soluzione non ottimale.

Il decimo campo di dati, probMistake, è un valore di soglia probabilistico che consente di determinare se un oggetto Bee attivo commetterà un errore, ovvero rifiuterà una soluzione vicina di qualità superiore rispetto alla soluzione corrente dell'oggetto Bee oppure accetterà una soluzione vicina di qualità inferiore rispetto alla soluzione corrente. Il valore di probMistake è hardcoded pari a 0,01, ovvero un oggetto attivo commetterà un errore di valutazione di una soluzione vicina l'1% delle volte.

L'undicesimo campo di dati, bees, è un array di oggetti Bee. Tenere presente che ogni oggetto Bee dispone di uno stato (attivo, inattivo, esplorazione), una soluzione (memoryMatrix), una misura della qualità della soluzione (measureOfQuality) e un contatore del numero di visite a una specifica fonte di cibo virtuale senza individuarne una migliore vicina (numberOfVisits). Poiché un oggetto Bee è definito come una classe, ogni voce nell'array è un riferimento a un oggetto Bee.

Il dodicesimo campo di dati, bestMemoryMatrix, è un array di oggetti char e rappresenta la soluzione migliore nell'array di oggetti Bee. Tenere presente che, poiché gli algoritmi di colonie di api simulate sono implementazioni specifiche metaueristiche, la rappresentazione della soluzioni di un problema varierà a seconda del problema. Un approccio di progettazione alternativo all'impostazione di una definizione del tipo di soluzione come hardcoded consiste nell'impostare parametri per questo campo di dati per renderlo di tipo generico. Un algoritmo SBC viene in genere utilizzato per tentare di risolvere un problema specifico ed è pertanto consigliabile ricodificare dall'inizio ogni nuova implementazione SBC.

Il tredicesimo campo di dati, bestMeasureOfQuality, rappresenta la misura della qualità che corrisponde alla soluzione bestMemoryMatrix.

L'ultimo campo di dati Hive, indexesOfInactiveBees, è un array di int contenente gli indici degli oggetti Bee nel costruttore Hive attualmente inattivi. Tenere presente che gli oggetti Bee attivi possono passare allo stato inattivo e viceversa. L'implementazione di un algoritmo SBC deve determinare con una certa frequenza quali oggetti Bee sono inattivi quando un oggetto Bee esegue una danza virtuale. L'archiviazione degli indici di oggetti Bee inattivi determina miglioramenti nelle prestazioni rispetto all'alternativa di iterazione nell'intero array di oggetti Bee e controllo del campo dei dati status di ogni oggetto Bee.

Nella Figura 6 è illustrata una rappresentazione virtuale di un potenziale oggetto Hive. L'oggetto Hive contiene 10 oggetti Bee: cinque attivi, due esploratori e tre inattivi. Gli oggetti Bee attualmente inattivi sono negli indici 2, 7 e 4 nell'array. L'oggetto CitiesData presenta cinque città. La soluzione migliore corrente è:

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

Di seguito è indicata la lunghezza del percorso della soluzione in unità di distanza:

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

Il campo citiesData è un riferimento a un oggetto CitiesData definito all'esterno dell'oggetto Hive.

Figura 6 Rappresentazione dell'oggetto Hive

Costruttore Hive

Nella Figura 7 è illustrato il codice del costruttore Hive. Il costruttore accetta sette parametri di input, sei dei quali sono scalari e uno è un oggetto (citiesData). Il parametro totalNumberBees è ridondante nel senso che può essere determinato da numberInactive, numberActive e numberScout, ma a mio parere il miglioramento del livello di leggibilità giustifica l'aggiunta di codice.

Figura 7 - Costruttore 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;
    }
  } 
}

Viene creata un'istanza dell'oggetto Random con ambito di classe con un valore di inizializzazione pari a 0. La capacità di fornire un valore di inizializzazione consente di riprodurre risultati. Successivamente sei valori di parametri di input per i campi dei dati scalari verranno copiati nei campi di dati Hive. L'oggetto Hive presenta un totale di 14 campi di dati; i valori soglia probPersuasion e probMistake sono hardcoded.

Il costruttore Hive utilizza il parametro citiesData di input e assegna il campo citiesData al parametro come riferimento. Un'alternativa a questo approccio per riferimento consiste nell'effettuare una nuova copia dei dati del problema, nel modo seguente:

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

In questo approccio viene utilizzata una quantità superiore di memoria, ma si evitano potenziali effetti collaterali indesiderati. L'approccio alternativo può essere utilizzato in caso di refactoring del codice illustrato in questo articolo in un linguaggio di programmazione che non supporta puntatori o riferimenti.

A questo punto nel costruttore Hive tutte le voci dell'array di oggetti Bee saranno vuote. Il costruttore inizializza quindi la migliore soluzione a livello globale (ovvero la migliore soluzione tra tutti gli oggetti Bee nell'oggetto Hive) e la relativa qualità della soluzione:

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

Il metodo di supporto GenerateRandomMemoryMatrix genera una soluzione casuale. Il metodo di supporto MeasureOfQuality accetta la soluzione generata in modo casuale e ne elabora la qualità. Più avanti in questo articolo parlerò del codice di questi due metodi di supporto.

Dopo aver inizializzato la migliore soluzione a livello globale e la relativa qualità, il costruttore Hive allocherà l'array di oggetti Bee indexesOfInactiveBees utilizzando il valore del campo numberInactive. A questo punto tutti i valori in questo array saranno pari a 0.

La parte successiva del codice del costruttore viene iterata in oggetto Bee dell'array e viene creata un'istanza mediante il costruttore Bee. La logica in questo ciclo presuppone che le prime celle numberInactive nell'array di oggetti Bee siano oggetti inattivi, le successive celle numberScout siano oggetti Bee esploratori e le celle rimanenti siano oggetti Bee attivi.

Se ad esempio sono presenti cinque oggetti Bee attivi, due inattivi e tre esploratori, il costruttore inizializza un array di oggetti Bee con dimensione 10 e crea istanze delle celle 0 e 1 come oggetti inattivi, delle celle 2-4 come oggetti esploratori e delle celle 5-9 come oggetti attivi. L'array indexesOfInactiveBees avrà inoltre una dimensione pari a 2 e conterrà inizialmente i valori 0 e 1.

Dopo aver determinato lo stato dell'oggetto Bee attuale in base alla variabile dell'indice del ciclo, verrà creata una soluzione generata in modo casuale e verrà calcolata la relativa qualità, il contatore del numero di visite verrà impostato su 0 in modo esplicito e verrà chiamato il costruttore Bee:

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

Una volta creata un'istanza di ogni oggetto Bee, verrà controllata la qualità della soluzione generata in modo casuale per stabilire se sia di livello superiore rispetto alla migliore soluzione globale. In caso affermativo, la soluzione corrente e la relativa qualità verranno copiate nei campi bestMemoryMatrix e bestMeasureOfQuality. Nel controllo della qualità di una soluzione migliore globale, un valore inferiore è preferibile a un valore superiore, in quanto il valore della qualità corrisponde a una lunghezza di percorso e il Problema del commesso viaggiatore richiede una riduzione di questa lunghezza.

Anziché copiare in modo esplicito la memoria di un oggetto Bee nell'array bestMemoryMatrix, un approccio alternativo consiste nell'assegnazione per riferimento, ottimizzando le prestazioni a scapito di un aumento del livello di complessità.

Tre metodi SBC essenziali

Ogni implementazione dell'algoritmo SBC deve disporre di tre metodi specifici del problema: un metodo per generare una soluzione casuale, un metodo per generare una soluzione vicina in rapporto a una determinata soluzione e un metodo per elaborare la qualità di una specifica soluzione. In questo esempio di Problema del commesso viaggiatore ogni metodo viene implementato in modo personalizzato e completamente dipendente dal problema.

Un'alternativa di progettazione consiste nel definire e nell'implementare interfacce. La programmazione tramite interfacce presenta diversi vantaggi e svantaggi rispetto a un approccio senza interfacce, ma a mio parere si tratta essenzialmente di una preferenza personale. Di seguito è illustrato il metodo per generare una soluzione casuale, GenerateRandomMemoryMatrix:

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;
}

Poiché una soluzione al Problema del commesso viaggiatore è un array di oggetti char in cui ogni oggetto rappresenta un'etichetta di città, il metodo GenerateRandomMemoryMatrix restituisce un array di oggetti char. La dimensione dell'array di risultati in locale viene allocata in base all'oggetto CitiesData dell'oggetto Hive e gli ID di città archiviati nel riferimento dell'oggetto Hive all'oggetto CitiesData vengono copiati nell'array dei risultati. I valori nell'array dei risultati vengono quindi disposti in ordine casuale mediante l'oggetto Random con ambito di classe e l'algoritmo di shuffle Fisher-Yates per la riproduzione con sequenza casuale (noto anche come Knuth shuffle).

Di primo acchito potrebbe sembrare che il metodo GenerateRandomMemoryMatrix appartenga concettualmente a un oggetto Bee. Tuttavia, poiché la generazione di una soluzione casuale dipende in parte da dati specifici del problema (in questo caso, CitiesData), il posizionamento del metodo di generazione della soluzione casuale nella definizione Hive generica rappresenta una progettazione migliore.

Nella Figura 8 è illustrato il metodo per generare una soluzione vicina, GenerateNeighborMemoryMatrix.

Figura 8 Generazione di una soluzione vicina

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;
}

Un concetto chiave negli algoritmi SBC consiste nell'idea che ogni fonte di cibo virtuale che rappresenta una soluzione abbia una soluzione vicina. Senza questo concetto, l'idea di un algoritmo basato sul comportamento delle api non ha più senso. Nel caso del Problema del commesso viaggiatore, in cui una soluzione può essere rappresentata come un array di ID di città che rappresentano un percorso da città a città, una soluzione vicina naturale relativa a una soluzione corrente è una permutazione della soluzione corrente in cui sono state scambiate due città adiacenti.

Se ad esempio una soluzione del Problema del commesso viaggiatore corrente è A,B,C,D,E, una ragionevole soluzione vicina è A,C,B,D,E. Il risultato non è così ovvio se una permutazione in cui vengono scambiate due città arbitrarie (rispetto a due città adiacenti) rappresenta una ragionevole soluzione vicina. Nell'esempio precedente, A,D,C,B,E è una ragionevole soluzione vicina? La decisione della definizione di una soluzione vicina per un algoritmo SBC è strettamente dipendente dal problema e riguarda in genere criteri soggettivi.

Il concetto di soluzione vicina consente inoltre di illustrare in parte il motivo per cui i problemi di combinazioni non numerici risultano particolarmente idonei per una soluzione per gli algoritmi SBC. Se un problema è implicitamente numerico, l'idea di una soluzione vicina è spesso difficile da definire in modo soddisfacente. Se è un problema è implicitamente combinatorio, l'idea di una soluzione vicina può essere tranquillamente definita da una forma di combinazione o permutazione matematica.

Il metodo GenerateNeighborMemoryMatrix accetta la rappresentazione memoryMatrix corrente di un oggetto Bee di una soluzione come parametro di input e lo copia in un array di risultati. Il metodo seleziona un indice casuale nell'array di risultati corrente mediante l'oggetto Random con ambito di classe. Se l'indice punta all'ultima cella, vengono scambiati il primo e l'ultimo ID di città. In caso contrario, se punta a qualsiasi cella diversa dall'ultima, vengono scambiati gli ID a cui puntano l'indice e l'indice successivo.

Il concetto di soluzione vicina fa riferimento al valore maxNumberVisits. Alcune ricerche indicano che un buon valore per maxNumberVisits è di circa cinque volte il numero di soluzioni vicine possibili per una determinata soluzione. Ad esempio, per tre città (A,B,C), se una soluzione vicina viene definita come lo scambio di qualsiasi coppia di città adiacenti, esistono tre soluzioni vicine possibili (scambio di A e B, scambio di B e C, scambio di A e C). Per 20 città un valore maxNumberVisits ragionevole è pertanto 20 * 5 = 100.

Il metodo per valutare la qualità della soluzione di un oggetto Bee, 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;
}

Per risolvere un problema con un algoritmo SBC, una caratteristica essenziale del problema consiste nel fatto che qualsiasi soluzione deve poter essere valutata per produrre una misura della qualità. A livello teorico, un problema di ottimizzazione combinatoriale realistico presenta quasi sempre una misura inerente e ragionevole della qualità. A livello pratico, tuttavia, il calcolo di questa misura può risultare complesso e dispendioso in termini di tempo.

In questo esempio, il metodo MeasureOfQuality viene iterato per ogni coppia di ID di città consecutive nella soluzione rappresentata dal parametro memoryMatrix, determina la distanza tra ogni coppia mediante il metodo Distance dell'oggetto CitiesData e accumula la distanza totale. Tenere presente che i dati delle città sono stati creati in modo artificiale per consentire il calcolo della distanza tra due città qualsiasi in modo rapido e semplice, utilizzando la distanza ordinale tra due ID di città. In un problema realistico, tuttavia, la distanza tra due città deve essere cercata con molta probabilità in una sorta di struttura di dati. Nelle implementazioni SBC, il metodo MeasureOfQuality rappresenta spesso la routine che regola la durata di esecuzione del programma. Pertanto, può essere utile verificare che il metodo sia ottimizzato per le prestazioni e fattibile, grazie alle risorse di memoria del sistema host.

Metodo Solve

Il metodo Solve ospita la logica che simula il comportamento delle api bottinatrici per risolvere un problema. Si tratta di un metodo mediamente complesso che utilizza tre metodi di supporto: ProcessActiveBee, ProcessScoutBee e ProcessInactiveBee. I metodi ProcessActiveBee e ProcessScoutBee utilizzano a turno un metodo di supporto DoWaggleDance. Il metodo Solve è illustrato nella Figura 9.

Figura 9 Metodo 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("");
}

Gran parte del lavoro effettivo è affidato ai metodi di supporto ProcessActiveBee, ProcessScoutBee e ProcessInactiveBee. Al metodo Solve viene passato un parametro di input Boolean per indicare se stampare un indicatore di stato rudimentale basato su testo. Questa situazione risulta utile in caso di sviluppo di un algoritmo SBC per monitorare la velocità dell'implementazione e individuare colli di bottiglia nelle prestazioni. Questo approccio presuppone che il metodo Solve sia parte di un'applicazione di console.

Il valore del parametro Boolean viene trasferito in una variabile Boolean locale denominata pb per poter utilizzare un nome di variabile breve. numberOfSymbolsToPrint viene impostato su 10, in modo che ogni incremento nell'indicatore di stato rappresenterà il 10% dello stato totale, determinato dal valore maxNumberCycles (viene utilizzata la variabile di incremento per determinare il numero di cicli che rappresentano il 10% dello stato).

Una volta inizializzata la variabile di controllo del ciclo (cycle) su 0, viene utilizzato un ciclo while loop per calcolare ogni oggetto Bee nell'oggetto Hive. È possibile utilizzare anche un ciclo for loop. In ogni ciclo, l'array di oggetti Bee viene iterato mediante un ciclo for loop e ogni oggetto Bee viene calcolato dal metodo di supporto appropriato. Una volta elaborato ogni oggetto Bee, se il parametro Boolean doProgressBar è true, il codice utilizza l'operatore modulus, %, per verificare se sia giunto il momento di stampare un aggiornamento all'indicatore di stato mediante un carattere ^.

Metodo ProcessActiveBee

Il metodo ProcessActiveBee è il fulcro di un algoritmo SBC ed è il metodo più complesso in termini di dimensioni e diramazione del codice. Il metodo ProcessActiveBee è illustrato nella Figura 10.

Figura 10 Metodo 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;
  }
}

Il metodo ProcessActiveBee accetta un parametro di input, i, che corrisponde all'indice dell'oggetto Bee nell'array. L'oggetto Bee attivo ottiene in primo luogo una soluzione vicina relativa alla soluzione corrente archiviata in memoryMatrix e quindi determina la qualità della soluzione vicina:

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

L'algoritmo configura quindi tre variabili locali che verranno utilizzate in un secondo momento:

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

La variabile prob presenta un valore compreso tra 0,0 e 1,0 che verrà confrontato rispetto al valore del campo probMistake per determinare se l'oggetto Bee commetterà un errore di valutazione della soluzione vicina (ovvero rifiuterà una soluzione vicina di qualità superiore oppure accetterà una soluzione vicina di qualità inferiore).

Il valore Boolean memoryWasUpdated verrà utilizzato per determinare se l'oggetto Bee attivo debba eseguire una danza virtuale per gli oggetti Bee inattivi (true) o meno (false). Il valore Boolean numberOfVisitsOverLimit verrà confrontato con il campo maxNumberVisits per determinare se l'oggetto Bee abbia esaurito una particolare fonte di cibo virtuale senza trovare una soluzione vicina migliore e, in questo caso, debba passare dallo stato attivo allo stato inattivo.

Se l'oggetto Bee corrente trova una soluzione vicina migliore, l'algoritmo determina se l'oggetto Bee commette un errore e rifiuta la soluzione vicina migliore oppure se la accetta. In modo analogo, se l'oggetto Bee corrente non ha trovato una soluzione vicina migliore, l'algoritmo determina se l'oggetto Bee commette un errore e accetta la soluzione vicina di qualità inferiore oppure non commette un errore e rifiuta la soluzione vicina.

Possono essere commessi dunque solo due tipi di errore, ma entrambi con la stessa probabilità, ovvero probMistake = 0,01. Alcune ricerche indicano che l'utilizzo di due probabilità diverse per i due tipi diversi di errori non aumentano il livello di efficacia degli algoritmi SBC, ma consentono di sperimentare due diversi valori soglia.

Dopo che l'oggetto Bee attivo corrente avrà accettato o rifiutato la soluzione vicina, l'algoritmo controllerà se il contatore del numero di visite avrà superato la soglia maxNumberVisits. In caso affermativo, lo stato dell'oggetto Bee corrente passa a inattivo, un oggetto Bee inattivo selezionato in modo casuale passa allo stato attivo e l'array indexesOfInactiveBees viene aggiornato. L'algoritmo controlla quindi se la memoria dell'oggetto Bee è stata aggiornata. In caso affermativo, viene controllata la nuova soluzione per stabilire se sia una nuova soluzione migliore globale e quindi viene chiamato un metodo di supporto privato, DoWaggleDance, per simulare l'ape che torna all'alveare e veicola le informazioni sulla nuova fonte di cibo alle api inattive.

Metodo DoWaggleDance

Il metodo di supporto DoWaggleDance simula un'ape attiva o esploratrice che torna all'alveare ed esegue una danza per veicolare alle api inattive le informazioni sulla posizione e sulla qualità di una fonte di cibo. Di seguito è indicato il metodo 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;
      } 
    } 
  } 
}

Il parametro di input i è l'indice dell'oggetto Bee corrente che esegue la danza virtuale. La misura della qualità della soluzione dell'oggetto Bee corrente viene confrontata rispetto alla misura della qualità di ogni oggetto Bee inattivo. Se la soluzione dell'oggetto Bee corrente è migliore e l'oggetto Bee inattivo corrente viene convinto (con probabilità probPersuasion = 0,90), la memoria dell'oggetto Bee corrente viene copiata nella memoria dell'oggetto Bee inattivo.

Sussistono varie opportunità per inserire il controllo degli errori nel codice presentato in questo articolo. All'interno del ciclo for loop in DoWaggleDance è ad esempio possibile controllare lo stato dell'oggetto Bee inattivo corrente con:

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

In alternativa, è possibile verificare il contatore del numero di visite dell'oggetto Bee inattivo con:

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

ProcessScoutBee e ProcessInactiveBee

Il metodo di supporto ProcessScoutBee utilizzato dal metodo Solve simula l'azione di un'ape esploratrice che cerca in modo casuale fonti di cibo invitanti. Il metodo ProcessScoutBee è illustrato nella Figura 11.

Figura 11 Metodo 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);
  }
}

Il parametro di input i rappresenta l'indice di un oggetto Bee esploratore nell'array di oggetti Bee. Un oggetto Bee esploratore genera una soluzione casuale, controlla se si tratta di una soluzione migliore rispetto a quella corrente nella memoria e, in caso affermativo, la copia nella memoria. Tenere presente che sono preferibili valori di qualità inferiori. Se l'oggetto Bee esploratore ha rilevato una nuova soluzione, l'algoritmo controlla se la nuova soluzione è una soluzione migliore a livello globale.

A differenza degli oggetti Bee attivi, in questa implementazione SBC gli oggetti Bee esploratori non commettono errori di valutazione della qualità di una fonte di cibo. Non è in corso alcuna ricerca sugli effetti degli errori degli oggetti Bee esploratori.

Di seguito è indicato il metodo ProcessInactiveBee:

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

In questa implementazione SBC gli oggetti Bee inattivi sono effettivamente ciò che l'aggettivo suggerisce (inattivi) e pertanto il metodo ProcessInactiveBee rappresenta semplicemente un segnaposto in caso si desideri implementare logica dipendente dai problemi per un oggetto Bee inattivo. Una possibile modifica consisterebbe nel mutare in modo casuale la memoria di un oggetto Bee inattivo con un tipo di probabilità minimo.

Conclusioni

Il processo generale di implementazione di un algoritmo SBC ha inizio con l'identificazione del problema. I problemi di ottimizzazione combinatori complessi e non numerici senza soluzioni deterministiche pratiche costituiscono spesso candidati ideali per una soluzione SBC. Il problema di riferimento deve avere un modo per rappresentare una soluzione (spesso come array o matrice) e ogni soluzione deve presentare una sorta di soluzione vicina e una misura della qualità della soluzione.

Considerare ad esempio il problema di dividere un grafico in due parti per fare in modo che il numero di connessioni in ogni parte sia elevato al massimo e il numero di connessioni tra le due parti sia ridotto al minimo. Questo problema di partizione del grafico è combinatorio e non esiste un algoritmo rapido in grado di rilevare la soluzione ottimale (sebbene siano disponibili algoritmi deterministici in grado di rilevare soluzioni quasi ottimali). Esistono vari problemi NP-completo e NP-difficile che è possibile risolvere con un algoritmo SBC.

Gli algoritmi SBC si basano sul comportamento dei sistemi naturali. Esistono altri algoritmi di questo tipo, tra cui algoritmi genetici basati sulla selezione e sull'evoluzione naturale, algoritmi ACO (Ant Colony Optimization) basati sul comportamento delle formiche e algoritmi SA (Simulated Annealing) basati sulle proprietà fisiche del raffreddamento dei metalli.

Gli algoritmi basati su sistemi naturali sono spesso semplici da implementare in relazione ad approcci deterministici, ma richiedono in genere la specifica di valori tendenzialmente sensibili riguardo all'effetto sulla velocità di convergenza e sull'accuratezza della soluzione. Nel caso di un algoritmo SBC, alcuni parametri sensibili che devono essere ottimizzati per ogni problema includono il numero di ogni tipo di oggetti Bee, il numero massimo di visite prima di esaurire una fonte di cibo virtuale, la soglia di probabilità di convincimento degli oggetti Bee inattivi e la probabilità di errore degli oggetti Bee attivi.

Sebbene gli algoritmi SBC non siano applicabili a ogni problema, in alcuni scenari possono rappresentare strumenti estremamente efficaci. 

Dott. James McCaffrey* lavora in Volt Information Sciences, Inc., dove gestisce la formazione tecnica degli ingegneri software di Microsoft, presso il campus di Redmond, Washington. Si è occupato di diversi prodotti Microsoft, inclusi Internet Explorer e MSN Search. McCaffrey è autore di ".NET Test Automation Recipes" (Apress, 2006) ed è possibile contattarlo all'indirizzo jammc@microsoft.com.*

Un ringraziamento ai seguenti esperti tecnici per la revisione dell'articolo: Dan Liebling e Anne Loomis Thompson di Microsoft Research