Algoritmos de otimização populacional: busca por difusão estocástica (Stochastic Diffusion Search, SDS)

Conteúdo:

1. Introdução
2. Descrição do algoritmo
3. Resultados dos testes

1. Introdução

O algoritmo de busca por difusão estocástica (Stochastic Diffusion Search, SDS) foi proposto em 1989 por J. Bishop e desde então tem sido ativamente desenvolvido pelo seu autor e por S. Nasuto. Uma característica distintiva deste algoritmo é sua profundo raciocínio matemático em comparação com outros algoritmos populacionais. Inicialmente, o SDS foi desenvolvido para otimização discreta, mas somente em 2011 foi proposta sua modificação para otimização contínua global.

Fatos interessantes:

1. A busca por difusão estocástica (SDS) foi a primeira metaheurística de inteligências de enxame que pertence à família de algoritmos naturais de pesquisa e otimização. Outros exemplos desses algoritmos incluem a otimização por colônias de formigas, otimização por enxame de partículas e algoritmos genéticos.

2. Ao contrário da otimização por colônias de formigas, baseada em comunicação estigmergética, o SDS utiliza uma comunicação direta entre agentes, semelhante ao mecanismo de chamada em tandem usado pelas formigas da espécie Leptothorax acervorum.

O algoritmo SDS é baseado na avaliação parcial e econômica de uma hipótese (solução candidata para o problema de pesquisa) pelos agentes. Aqui, os agentes trocam informações sobre as hipóteses através de comunicação direta face a face. Por meio do mecanismo de difusão, soluções de alta qualidade podem ser identificadas a partir de agrupamentos de agentes com a mesma hipótese.

Para uma melhor compreensão do funcionamento do algoritmo SDS, pode-se utilizar uma analogia simples, o jogo do restaurante.

No jogo do restaurante, os participantes agem como agentes, e os restaurantes representam as hipóteses. Cada agente escolhe um restaurante onde deseja comer, com base em suas preferências e nas informações que recebe de outros agentes. Em seguida, os agentes trocam informações sobre suas escolhas e preferências. Como resultado desse processo, são formados agrupamentos de agentes que escolhem o mesmo restaurante e podem ser identificados como decisões potencialmente boas.

O algoritmo SDS tem várias vantagens. Primeiramente, permite que os agentes façam avaliações parciais e econômicas de hipóteses, o que reduz a complexidade computacional do algoritmo. Em segundo lugar, utiliza comunicação direta e pessoal entre agentes, o que permite a difusão eficaz da informação. Em terceiro lugar, o SDS tem uma base matemática, o que o torna mais confiável e previsível.

No entanto, o algoritmo SDS também tem suas limitações. Primeiramente, pode ser eficaz apenas em certos tipos de tarefas onde o conceito de hipótese é aplicável. Em segundo lugar, pode sofrer do problema da convergência prematura, quando os agentes convergem para uma hipótese muito rapidamente, sem explorar outras possibilidades. Em terceiro lugar, o algoritmo requer ajuste de parâmetros, o que pode ser um processo complexo e demorado. As limitações foram apontadas por alguns autores, vamos verificar se isso procede.

No geral, o SDS é um algoritmo interessante e eficaz para resolver problemas de otimização. Ele combina as vantagens dos algoritmos populacionais com uma fundamentação matemática, tornando-o atraente para pesquisa e aplicação em diversas áreas.

2. Descrição do algoritmo

Vamos considerar mais detalhadamente o algoritmo SDS.

A busca por difusão estocástica (SDS) é um algoritmo populacional baseado em duas ideias estratégicas de busca:

1. Avaliação parcial das soluções.
2. Difusão de soluções promissoras por toda a população.

Há dois jogos canônicos que descrevem em termos simples como o SDS funciona.
1. O jogo do restaurante
2. O jogo da caça ao ouro.

Jogo do restaurante

Imaginemos um grupo de delegados está em uma conferência prolongada em uma cidade desconhecida. Todas as noites, eles enfrentam o problema de escolher um restaurante para jantar. A cidade tem uma grande variedade de estabelecimentos que oferecem diversos pratos. O objetivo do grupo é encontrar o melhor restaurante, onde cada delegado possa desfrutar de um jantar agradável. No entanto, realizar uma busca exaustiva por todas as possíveis combinações de restaurantes e pratos levaria tempo demais. Para resolver esse problema, os delegados recorrem ao uso da busca por difusão estocástica.

Cada delegado atua como um agente que faz uma suposição sobre a escolha do melhor restaurante na cidade. Todas as noites, os delegados testam suas hipóteses, visitando restaurantes e escolhendo aleatoriamente um dos pratos do menu do restaurante. Na manhã seguinte, durante o café da manhã, cada delegado que ficou insatisfeito com o jantar da noite anterior pede a um colega para compartilhar suas impressões sobre o jantar. Se as impressões do colega forem positivas, o delegado também escolhe esse restaurante. Caso contrário, ele escolhe aleatoriamente outro estabelecimento da lista de restaurantes disponíveis na cidade.

Dessa forma, graças a essa estratégia, rapidamente se forma um número significativo de delegados reunidos em torno do melhor restaurante da cidade.

Esse processo do jogo do restaurante tem várias características interessantes. Na ausência total de controle e gerência externos, o grupo de delegados se comunica para resolver um problema que não pode ser resolvido rapidamente de forma individual. Se a qualidade do serviço ou do menu do restaurante atual diminui significativamente ou se ele fecha, os delegados se movem eficientemente para o próximo melhor estabelecimento. A principal exigência é a comparabilidade dos restaurantes, menus e pratos individuais. Cada agente decide independentemente se sua experiência foi boa.

Os delegados passam muitas noites em um restaurante de alta qualidade antes que todos os pratos em todos os estabelecimentos da cidade sejam avaliados.
Críticos apontam que os delegados provavelmente têm preferências diferentes em alimentos, portanto, um delegado pode encontrar um restaurante onde goste de todos os pratos, mas isso pode não satisfazer os outros membros do grupo. Se apenas um ou uma pequena parte dos delegados permanecer constantemente nesse restaurante, os demais continuam agindo como de costume, e, eventualmente, a maioria ainda se reúne no melhor restaurante. No entanto, no pior caso, todos os agentes podem acabar comendo sozinhos, mesmo se houver um único restaurante excepcional que satisfaria a maioria dos delegados. Este restaurante nunca será encontrado, uma vez que todos os delegados estão satisfeitos com suas escolhas atuais e não procurarão novos estabelecimentos.

Em nossa implementação, foram feitas pequenas alterações na lógica da estratégia de busca, permitindo que os delegados continuem a busca por restaurantes mesmo quando não há um único delegado com uma experiência melhor, assim, a busca por restaurantes não cessa, ao contrário da versão canônica, na qual é importante a própria mudança de opinião atual sobre o restaurante em relação à anterior, se a opinião não mudar para melhor para a maioria dos delegados, eles continuarão indo ao mesmo restaurante, o que significa ficar preso em um extremo local.

Jogo da caça ao ouro

Um grupo de amigos, consistindo em mineiros experientes, descobre sobre a possibilidade de encontrar ouro nas colinas de uma cadeia montanhosa. No entanto, eles não têm informações sobre onde exatamente o lugar mais rico em ouro está localizado. Em seus mapas, a cadeia montanhosa é dividida em várias colinas separadas, cada uma contendo um conjunto de veios que requerem mineração. A probabilidade de descobrir ouro ao longo do tempo é proporcional à sua riqueza.

Para maximizar sua riqueza coletiva, os mineiros devem identificar a colina com os veios mais ricos em ouro, para que o máximo número de mineiros possa minerar lá. No entanto, essa informação não está disponível antecipadamente. Para resolver este problema, os mineiros decidem usar uma simples busca estocástica por difusão.

O processo de mineração começa com cada mineiro sendo aleatoriamente designado a uma colina para minerar (sua hipótese de colina). Todos os dias, a cada mineiro é aleatoriamente escolhido um veio em sua colina para ele explorar.

Ao final de cada dia, a probabilidade de um mineiro estar satisfeito é proporcional à quantidade de ouro que ele encontrou (valor da função de adaptação).
À noite, após o término do trabalho, os mineiros se reúnem. Um mineiro insatisfeito aleatoriamente escolhe outro mineiro para conversar. Se o mineiro escolhido estiver satisfeito, ele "com prazer" informa ao seu colega o nome da colina que ele está explorando. Assim, ambos os mineiros mantêm a hipótese da colina. Se, por outro lado, o mineiro escolhido estiver insatisfeito, ele não diz nada, e o mineiro inicial é forçado a escolher uma nova hipótese, isto é, a determinação aleatória da colina que ele explorará no dia seguinte.

No contexto do SDS (sistemas dinâmicos auto-organizados), os agentes atuam como mineiros. Agentes ativos são os "mineiros felizes", enquanto agentes inativos são os "mineiros infelizes". A hipótese de cada agente representa a "hipótese da colina" do mineiro. Este processo é isomórfico ao SDS, permitindo que os mineiros se autoorganizem naturalmente e rapidamente se reúnam nas colinas da cadeia montanhosa com alta concentração de ouro.

A felicidade dos mineiros pode ser medida probabilisticamente ou representada por um valor lógico absoluto, considerando que cada mineiro ao final do dia está feliz ou infeliz. Se o ouro é modelado como um recurso limitado que diminui com o tempo, então a busca se torna suficientemente adaptativa, e os mineiros se movem para locais com a maior quantidade de ouro.

Embora o termo "feliz" seja subjetivo, assim como as preferências alimentares, neste caso, ele é usado em um sentido objetivo. Todos os mineiros usam o mesmo processo: a quantidade de ouro que encontram durante o dia determina a probabilidade de se declararem "felizes" no final do dia, quando se reúnem para potencialmente compartilhar informações sobre as colinas que estão minerando.

Não utilizaremos a divisão dos mineiros em "felizes" e "infelizes", o que permitirá, assim como no caso da concepção do jogo do restaurante, aumentar a atividade dos agentes na busca por novos locais inexplorados.

Para formalizar o algoritmo, usaremos o conceito de "candidato", que é equivalente ao delegado no jogo do restaurante e ao mineiro no jogo de caça ao ouro. O candidato representa um agente de busca. Para entender melhor do que se trata, o restaurante ou a colina pode ser imaginado/a como um espaço com duas coordenadas, embora na realidade, para resolver problemas multidimensionais, um número ilimitado de coordenadas possa ser aplicado. Na Figura 1, os candidatos são mostrados como C1, C2, C3, que armazenam os números dos restaurantes (espaços correspondentes no campo de busca). Durante a troca difusiva de informações sobre os restaurantes, os candidatos adotam números de restaurantes de participantes da conferência selecionados aleatoriamente, caso o valor da função de adaptação do interlocutor seja mais alto. O intervalo de cada parâmetro de otimização (coordenadas do espaço de busca) é dividido pelo número de restaurantes especificado nos parâmetros externos do algoritmo; por exemplo, se os parâmetros do algoritmo especificam 100 restaurantes, isso significa que o alcance de cada coordenada será dividido em 100 partes.

Cada restaurante oferece um menu de pratos, cada prato do menu é uma coordenada específica do espaço de busca dentro de um restaurante. O algoritmo implementa um esquema pelo qual o candidato prova apenas um prato escolhido aleatoriamente do restaurante.

Figura 1. Representação do princípio de troca difusiva de informações sobre restaurantes.

Vamos considerar os passos do algoritmo SDS em forma de pseudocódigo.

1. Inicialização dos candidatos (atribuição de restaurantes e pratos aleatórios).

2.0. Teste de hipótese e troca difusiva entre os candidatos.

2.1. Comparação da experiência atual do candidato com a sua anterior.

2.1.1. Se a experiência for melhor, atribuímos os endereços dos restaurantes como hipótese para a próxima iteração.

2.1.2. Se a experiência for pior, então pedimos a opinião de um candidato escolhido aleatoriamente.

2.1.2.1. Se a experiência do colega candidato for melhor, então pegamos os endereços dos restaurantes promissores (para o candidato atual).

2.1.2.2. Se a experiência do colega candidato for pior, então com uma certa probabilidade escolhemos o endereço de um restaurante selecionado aleatoriamente, ou mantemos o atual.

3.0. Selecionamos pratos, na lista formada de restaurantes, como hipótese para a próxima iteração.

A estrutura lógica do teste de hipótese é mostrada na Figura 2. A maior parte dessa estrutura executa a tarefa de escolha do restaurante, e após a conclusão da escolha do restaurante, um prato é selecionado aleatoriamente. A escolha do restaurante é a principal tarefa do algoritmo, porém a escolha do prato é completamente aleatória e independente das iterações anteriores.

Figura 2. Esquema lógico da verificação de hipóteses.

Chegou a hora de examinar o código SDS (Stochastic Diffusion Search) e começar com o coração e a alma do algoritmo, isto é, o agente, também conhecido como candidato, que pode ser descrito pela estrutura S_Candidate. Ela contém os seguintes campos:

1. raddr: array que contém os endereços dos restaurantes. Cada elemento do array representa o endereço de um restaurante.
2. raddrPrev: array que contém os endereços anteriores dos restaurantes. Cada elemento do array representa o endereço anterior de um restaurante.
3. c: array que contém as coordenadas (pratos). Cada elemento do array representa a coordenada de um prato.
4. cPrev: array que contém as coordenadas anteriores (pratos). Cada elemento do array representa a coordenada anterior de um prato.
5. f: valor da função de adaptação (fitness) para o estado atual do agente.
6. fPrev: valor da função de adaptação (fitness) para o estado anterior do agente.

A estrutura S_Candidate tem um método Init, que inicializa todos os arrays com a dimensão coords (número de coordenadas - parâmetros otimizados) e define os valores iniciais de f e fPrev como -DBL_MAX, pois não há com o que ou com quem comparar a experiência do candidato na primeira iteração.

//——————————————————————————————————————————————————————————————————————————————
struct S_Candidate
{
  void Init (int coords)
  {
    ArrayResize (c,         coords);
    ArrayResize (cPrev,     coords);
    ArrayResize (raddr,     coords);
    ArrayResize (raddrPrev, coords);
    f        = -DBL_MAX;
    fPrev    = -DBL_MAX;
  }
  int    raddr     []; //restaurant address
  int    raddrPrev []; //previous restaurant address
  double c         []; //coordinates (dishes)
  double cPrev     []; //previous coordinates (dishes)
  double f;            //fitness
  double fPrev;        //previous fitness
};
//——————————————————————————————————————————————————————————————————————————————

Vamos declarar a classe do algoritmo SDS contendo o seguinte:

Campos da classe:
- cB: array contendo as melhores coordenadas
- fB: valor da função de adaptação para as melhores coordenadas
- cands: array de candidatos para a busca das coordenadas ótimas
- rangeMax: array contendo os valores máximos para cada coordenada
- rangeMin: array contendo os valores mínimos para cada coordenada
- rangeStep: array contendo os passos de busca para cada coordenada

Métodos da classe:
- Init: inicialização dos parâmetros do algoritmo, como número de coordenadas, tamanho da população, número de restaurantes e a probabilidade de escolha de um restaurante
- Moving: execução do passo do algoritmo, deslocamento dos candidatos para novas coordenadas
- Revision: execução do passo de revisão, atualização das melhores coordenadas e da função de adaptação
- SeInDiSp: método para calcular uma nova coordenada dentro de um intervalo dado com um passo especificado
- RNDfromCI: método para gerar um número aleatório dentro de um intervalo especificado

Outros campos da classe:
- coords: número de coordenadas
- populationSize: tamanho da população
- restNumb: número de restaurantes
- probabRest: probabilidade de escolha de um restaurante
- restSpace: espaço dos restaurantes
- revision: flag indicando a necessidade de realizar uma revisão

//——————————————————————————————————————————————————————————————————————————————
class C_AO_SDS
{
  //----------------------------------------------------------------------------
  public: double cB   [];       //best coordinates
  public: double fB;            //FF of the best coordinates
  public: S_Candidate cands []; //candidates

  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search



  public: void Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    restaurantsNumberP,   //restaurants number
                     const double probabRestP);         //probability restaurant choosing

  public: void Moving   ();
  public: void Revision ();

  //----------------------------------------------------------------------------
  private: int    coords;            //coordinates number
  private: int    populationSize;    //population size

  private: int    restNumb;          //restaurants number
  private: double probabRest;        //probability restaurant choosing
  private: double restSpace [];      //restaurants space

  private: bool   revision;

  private: double SeInDiSp  (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI (double min, double max);
};
//——————————————————————————————————————————————————————————————————————————————

O método de inicialização do algoritmo SDS começa com a definição dos valores iniciais para algumas variáveis e arrays.

Os parâmetros de entrada do método são:
- coordinatesNumberP: número de coordenadas (dimensão do espaço de busca)
- populationSizeP: tamanho da população (número de candidatos)
- restaurantsNumberP: número de restaurantes
- probabRestP: probabilidade de escolha de um restaurante

Primeiramente, o gerador de números aleatórios é reiniciado usando a função MathSrand e passando o valor atual de microssegundos. Em seguida, as variáveis fB e revision são inicializadas com os valores iniciais -DBL_MAX e false, respectivamente.
Depois, os valores dos parâmetros de entrada coordinatesNumberP e populationSizeP são atribuídos às variáveis coords e populationSize.
As variáveis restNumb e probabRest são inicializadas com os valores de restaurantsNumberP e probabRestP.
Cria-se um array restSpace de tamanho coords usando a função ArrayResize.
Depois, cria-se um array cands de tamanho populationSize usando a função ArrayResize. Em um loop, cada elemento do array cands é inicializado chamando o método Init com o parâmetro coords.
Também são criados os arrays rangeMax, rangeMin, rangeStep, e cB de tamanho coords usando a função ArrayResize.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDS::Init (const int    coordinatesNumberP,   //coordinates number
                     const int    populationSizeP,      //population size
                     const int    restaurantsNumberP,   //restaurants number
                     const double probabRestP)          //probability restaurant choosing
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords         = coordinatesNumberP;
  populationSize = populationSizeP;

  restNumb   = restaurantsNumberP;
  probabRest = probabRestP;
  ArrayResize (restSpace, coords);

  ArrayResize (cands, populationSize);
  for (int i = 0; i < populationSize; i++) cands [i].Init (coords);

  ArrayResize (rangeMax,       coords);
  ArrayResize (rangeMin,       coords);
  ArrayResize (rangeStep,      coords);
  ArrayResize (cB,             coords);
}
//——————————————————————————————————————————————————————————————————————————————

O método Moving() será chamado em cada iteração, mas a lógica principal do método é executada apenas uma vez, controlada pela flag revision.

No início da função, a variável revision é verificada; se for false, é realizada a inicialização das variáveis e arrays.
Então, ocorre um laço pelas coordenadas do espaço.

Dentro desse laço, calcula-se o valor restSpace[i], que é o comprimento do intervalo para cada coordenada, comprimento esse que não só é definido como a diferença entre os valores máximo e mínimo do intervalo como também é dividido por restNumb.

Em seguida, declaram-se as variáveis min e max, que serão usadas para definir o intervalo de valores para o espaço de um restaurante específico.

Em seguida, inicializam-se as variáveis n e dish, que serão usadas para determinar valores aleatórios dentro do intervalo do restaurante selecionado.

Então, executa-se um laço iterando a população de tamanho populationSize, dentro do qual se executa um laço pelas coordenadas dos pontos do espaço. Dentro deste laço, gera-se um número aleatório n usando a função RNDfromCI(), que é utilizado para determinar o índice no array restSpace. Se o valor obtido de n for maior ou igual a restNumb, então ele é atribuído a restNumb - 1, para garantir uma distribuição uniforme da variável aleatória. Em seguida, calculam-se os valores de min e max, usando rangeMin, restSpace e n.

Gera-se um número aleatório para dish (prato) usando a função RNDfromCI(), que fica no intervalo de min a max (espaço do restaurante).

Então, o valor de dish é usado para calcular o valor de c[i] usando a função SeInDiSp(), que utiliza rangeMin, rangeMax, rangeStep para garantir o passo correto dos parâmetros otimizados.

Como resultado da execução deste algoritmo, cada ponto do espaço recebe valores aleatórios para cada coordenada de acordo com o espaço do restaurante, imitando a escolha aleatória de um prato.

A variável revision é definida como true, para que na próxima chamada da função Moving() a inicialização de variáveis e arrays não seja realizada.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDS::Moving ()
{
  if (!revision)
  {
    for (int i = 0; i < coords; i++)
    {
      restSpace [i] = (rangeMax [i] - rangeMin [i]) / restNumb;
    }

    double min = 0.0;
    double max = 0.0;

    int    n   = 0;
    double dish = 0.0;

    for (int i = 0; i < populationSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        n = (int)(RNDfromCI (0, restNumb));
        if (n >= restNumb) n = restNumb - 1;

        cands [i].raddr     [c] = n;
        cands [i].raddrPrev [c] = n;
        min = rangeMin [c] + restSpace [c] * n;
        max = min + restSpace [c];

        dish = RNDfromCI (min, max);

        cands [i].c [c] =  SeInDiSp (dish, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método Revision do algoritmo SDS realiza a lógica principal de escolha de restaurantes e pratos nos restaurantes. Isso não é típico para os algoritmos considerados anteriormente, nos quais a lógica principal de movimentação dos agentes estava localizada no método Moving, embora a ordem de acesso aos métodos do algoritmo permaneça a mesma e esteja de acordo com o conceito escolhido no primeiro artigo da série de artigos. O algoritmo consiste nas seguintes etapas:

1. Atualização do melhor valor encontrado da função de adaptação fB e do conjunto de coordenadas correspondente cB. Para cada candidato i na população, é feita uma comparação, se o valor de f (avaliação da função) for maior que o valor global atual fB, então fB é atualizado e o melhor conjunto global de coordenadas cB é copiado do candidato i.

2. Atualização dos valores de avaliação anteriores e dos conjuntos de restaurantes para cada candidato. Para cada candidato i na população, se o valor de f for maior que o valor anterior fPrev, então fPrev é atualizado, bem como os conjuntos de restaurantes c e raddr são copiados do candidato i para os valores anteriores correspondentes cPrev e raddrPrev.

3. Seleção de um novo conjunto de restaurantes para cada candidato. Para cada candidato i na população e cada coordenada c, um número aleatório n é escolhido no intervalo de 0 a populationSize. Se o valor de fPrev para o candidato n for maior que o valor de fPrev para o candidato i, então o conjunto de restaurantes raddr para o candidato i é atualizado com o valor de raddrPrev para o candidato n. Caso contrário, gera-se um número aleatório rnd no intervalo de 0.0 a 1.0. Se rnd for menor que a probabilidade probabRest, então escolhe-se um número aleatório n no intervalo de 0 a restNumb e o conjunto de restaurantes raddr para o candidato i é atualizado com o valor n. Caso contrário, o conjunto de restaurantes raddr para o candidato i permanece inalterado.

4. Geração de um novo conjunto de coordenadas para cada candidato. Para cada candidato i na população e para cada coordenada c, os valores mínimo e máximo min e max são determinados com base no intervalo rangeMin e restSpace para a respectiva coordenada. Então, gera-se um número aleatório no intervalo de min a max usando a função SeInDiSp, e o valor obtido é atribuído à coordenada correspondente c no conjunto c para o candidato i.

Assim, o método Revision do algoritmo SDS executa cada iteração pela população de candidatos, atualiza o melhor valor encontrado e o conjunto de restaurantes, além de selecionar novos conjuntos de restaurantes e gerar novos conjuntos de coordenadas para cada candidato.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SDS::Revision ()
{
  //----------------------------------------------------------------------------
  for (int i = 0; i < populationSize; i++)
  {
    if (cands [i].f > fB)
    {
      fB = cands [i].f;
      ArrayCopy (cB, cands [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  //----------------------------------------------------------------------------
  double min = 0.0;
  double max = 0.0;
  double rnd = 0.0;
  int    n   = 0;

  for (int i = 0; i < populationSize; i++)
  {
    if (cands [i].f > cands [i].fPrev)
    {
      cands [i].fPrev = cands [i].f;
      ArrayCopy (cands [i].cPrev, cands [i].c, 0, 0, WHOLE_ARRAY);
      ArrayCopy (cands [i].raddrPrev, cands [i].raddr, 0, 0, WHOLE_ARRAY);
    }
  }

  for (int i = 0; i < populationSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      n = (int)(RNDfromCI (0, populationSize));
      if (n >= populationSize) n = populationSize - 1;

      if (cands [n].fPrev > cands [i].fPrev)
      {
        cands [i].raddr [c] = cands [n].raddrPrev [c];
      }
      else
      {
        rnd = RNDfromCI (0.0, 1.0);

        if (rnd < probabRest)
        {
          n = (int)(RNDfromCI (0, restNumb));
          if (n >= restNumb) n = restNumb - 1;
          cands [i].raddr [c] = n;
        }
        else
        {
          cands [i].raddr [c] = cands [i].raddrPrev [c];
        }
      }

      min = rangeMin [c] + restSpace [c] * cands [i].raddr [c];
      max = min + restSpace [c];

      cands [i].c [c] = SeInDiSp (RNDfromCI (min, max), rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Resultados dos testes

Print dos resultados do algoritmo de busca difusiva estocástica no banco de testes:

C_AO_SDS:100;1000;0.1
=============================
5 Rastrigin's; Func runs 10000 result: 80.64253803557851
Score: 0.99921
25 Rastrigin's; Func runs 10000 result: 79.00996143538204
Score: 0.97898
500 Rastrigin's; Func runs 10000 result: 54.31544686388126
Score: 0.67300
=============================
5 Forest's; Func runs 10000 result: 1.677891584229713
Score: 0.94910
25 Forest's; Func runs 10000 result: 1.4089003503272384
Score: 0.79694
500 Forest's; Func runs 10000 result: 0.2437939668372883
Score: 0.13790
=============================
5 Megacity's; Func runs 10000 result: 8.6
Score: 0.71667
25 Megacity's; Func runs 10000 result: 6.448
Score: 0.53733
500 Megacity's; Func runs 10000 result: 0.9551999999999999
Score: 0.07960
=============================
All score: 5.86873

Logo após olharmos o print dos resultados do algoritmo, podemos notar os resultados incrivelmente altos em comparação com outros algoritmos. Uma comparação detalhada é apresentada abaixo na tabela.

Deve-se destacar especialmente o comportamento atípico do algoritmo ao visualizar o movimento do agente. Os agentes são distribuídos uniformemente e proporcionalmente à altura do pico da função de adaptação, demonstrando uma alta qualidade de agrupamento pelos extremos locais. Isso dá a impressão de que nenhum pico será ignorado pelo algoritmo. Também chama a atenção o crescimento quase sem etapas da convergência do algoritmo a cada iteração, o que indica uma pequena tendência a ficar preso em extremos locais. Mesmo na função Forest mais complexa com extremo global acentuado, não se observa convergência gradual.

  SDS na função de teste Rastrigin.

  SDS na função de teste Forest.

  SDS na função de testeMegacity.

Gostaria de salientar que não esperava resultados surpreendentes de um algoritmo tão simples baseado puramente em passeios aleatórios. O algoritmo SDS superou todos os algoritmos anteriormente considerados por uma grande margem, quase 13%, demonstrando os melhores resultados em muitos testes (4 primeiros lugares de 9 possíveis). A única disciplina, a função multivariável de Rastrigin, cujo líder deixou todos para trás, é o algoritmo de busca eletromagnética (EM).

Mesmo na função discreta extremamente complexa Megacity, o SDS mostra resultados excelentes, demonstrando quase nenhuma tendência a ficar preso, sendo o único que superou o SDS nos testes com 1000 variáveis em Forest e Megacity é o algoritmo mudas, semeadura e crescimento (Saplings Sowing and Growing up, SSG). 

№	AO	Description	Rastrigin			Rastrigin final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result
			10 p (5 F)	50 p (25 F)	1000 p (500 F)		10 p (5 F)	50 p (25 F)	1000 p (500 F)		10 p (5 F)	50 p (25 F)	1000 p (500 F)
1	SDS	stochastic diffusion search	0,99737	1,00000	0,63507	2,63244	0,96893	1,00000	0,95092	2,91985	1,00000	1,00000	0,72149	2,72149	100,000
2	SSG	saplings sowing and growing	1,00000	0,95313	0,55665	2,50978	0,72740	0,69680	1,00000	2,42421	0,69612	0,65726	1,00000	2,35338	87,489
3	HS	harmony search	0,99676	0,90817	0,48178	2,38670	1,00000	0,72930	0,44806	2,17736	0,91159	0,76446	0,41537	2,09142	79,474
4	ACOm	ant colony optimization M	0,34611	0,17142	0,17044	0,68797	0,86888	0,73719	0,77362	2,37968	0,91159	0,67983	0,05606	1,64749	54,863
5	IWO	invasive weed optimization	0,95828	0,63939	0,29807	1,89575	0,70773	0,34168	0,31773	1,36714	0,72927	0,32158	0,33289	1,38375	53,994
6	MEC	mind evolutionary computation	0,99270	0,48648	0,22800	1,70718	0,60762	0,29973	0,25459	1,16194	0,85083	0,31594	0,26170	1,42847	49,567
7	COAm	cuckoo optimization algorithm M	0,92400	0,44601	0,26004	1,63006	0,58378	0,25090	0,16526	0,99994	0,66298	0,25246	0,17083	1,08627	42,193
8	FAm	firefly algorithm M	0,59825	0,32387	0,17135	1,09348	0,51073	0,31182	0,49790	1,32045	0,31491	0,21438	0,35258	0,88188	36,860
9	ABC	artificial bee colony	0,78170	0,31182	0,20822	1,30174	0,53837	0,15816	0,13344	0,82998	0,51381	0,20311	0,13926	0,85617	32,954
10	BA	bat algorithm	0,40526	0,60773	0,84451	1,85750	0,20841	0,12884	0,25989	0,59714	0,27073	0,07616	0,17371	0,52060	32,794
11	GSA	gravitational search algorithm	0,70167	0,43098	0,00000	1,13265	0,31660	0,26845	0,33204	0,91710	0,54144	0,26797	0,00000	0,80941	31,322
12	BFO	bacterial foraging optimization	0,67203	0,29511	0,11813	1,08528	0,39702	0,19626	0,20652	0,79980	0,47514	0,25388	0,18932	0,91834	30,615
13	EM	electroMagnetism-like algorithm	0,12235	0,44109	1,00000	1,56344	0,00000	0,02578	0,34880	0,37458	0,00000	0,00000	0,10924	0,10924	21,024
14	SFL	shuffled frog-leaping	0,40072	0,22627	0,26548	0,89247	0,20153	0,03057	0,02652	0,25862	0,24862	0,04231	0,06639	0,35732	14,189
15	MA	monkey algorithm	0,33192	0,31883	0,14644	0,79719	0,10012	0,05817	0,08932	0,24762	0,19889	0,03243	0,10720	0,33853	12,603
16	FSS	fish school search	0,46812	0,24149	0,11302	0,82264	0,12840	0,03696	0,06516	0,23052	0,15471	0,03666	0,08283	0,27420	11,893
17	PSO	particle swarm optimisation	0,20449	0,07816	0,07160	0,35425	0,18895	0,07730	0,21738	0,48363	0,21547	0,04513	0,01957	0,28016	9,238
18	RND	random	0,16826	0,09287	0,08019	0,34132	0,13496	0,03546	0,04715	0,21757	0,15471	0,02962	0,04922	0,23354	5,108
19	GWO	grey wolf optimizer	0,00000	0,00000	0,02256	0,02256	0,06570	0,00000	0,00000	0,06570	0,29834	0,05640	0,02557	0,38031	1,000

Considerações finais

O algoritmo SDS é um método de otimização eficaz que utiliza amostras aleatórias para encontrar o ótimo global de uma função dada.
Este artigo apresentou os princípios básicos de funcionamento do algoritmo SDS. Ele se baseia na ideia de escolha aleatória de pontos em um espaço de busca dividido em segmentos. Os resultados dos testes mostraram que o SDS é capaz de encontrar ótimos globais em funções complexas com muitos extremos locais, demonstrando excelente convergência. Uma das vantagens do algoritmo SDS é que ele é simples e fácil de implementar. Não exige um grande número de cálculos e pode ser aplicado a diferentes tipos de problemas de otimização.

Para uma representação mais visual das vantagens e desvantagens dos diferentes algoritmos em comparação entre si, a tabela acima pode ser apresentada usando uma escala de cores na figura 3.

Figura 3. Graduação de cores dos algoritmos de acordo com os testes correspondentes.

O histograma a seguir mostra os resultados do teste do algoritmo apresentado na Figura 3 (na escala de 0 a 100, quanto maior, melhor; no arquivo há um script para calcular a tabela de classificação de acordo com a metodologia deste artigo):

Figura 4. Histograma dos resultados do teste final do algoritmo.

Prós e contras do algoritmo de busca por difusão estocástica (SDS):

Prós:
1. Mínimo de parâmetros externos.
2. Alta eficiência na resolução de uma variedade de tarefas.
3. Baixa carga nos recursos de computação.
4. Facilidade de implementação do algoritmo.
5. Resistência ao bloqueio.
6. Resultados elevados tanto em funções suaves quanto em funções discretas complexas.
7. Alta convergência.

Contras:
1. Não observados.

Em cada artigo, anexo um arquivo contendo versões atualizadas e atuais dos códigos dos algoritmos descritos nos artigos anteriores. No entanto, é importante notar que não assumo responsabilidade pela precisão absoluta na descrição dos algoritmos canônicos. Frequentemente, também adiciono minhas próprias ideias e melhorias, baseando-me na experiência acumulada e na opinião pessoal. As conclusões e opiniões apresentadas nos artigos são baseadas nos resultados dos experimentos conduzidos.