Algoritmos de otimização populacionais: objetos de busca multissociais artificiais (artificial Multi-Social search Objects, MSO)

Conteúdo:

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

1. Introdução

No artigo anterior, discutimos a evolução dos grupos sociais, onde eles se moviam livremente no espaço de busca. No entanto, neste artigo, propomos modificar esse conceito e supor que os grupos se movem entre setores, pulando de um para outro. Todos os grupos têm seus centros, que são atualizados em cada iteração do algoritmo. Além disso, introduzimos o conceito de memória tanto para o grupo como um todo quanto para cada partícula individual nele. Usando essas mudanças, nosso algoritmo agora permite que os grupos se movam de setor em setor, baseando-se nas informações das melhores soluções.

Essa nova modificação abre novas possibilidades para a investigação da evolução dos grupos sociais. A transição para setores permite que os grupos troquem informações e experiências dentro de cada setor, o que pode levar a uma busca e adaptação mais eficazes. A introdução da memória permite que os grupos armazenem informações sobre movimentos anteriores e as utilizem para tomar decisões sobre movimentos futuros.

Neste artigo, realizaremos uma série de experimentos para investigar como esses novos conceitos afetam as qualidades de busca do algoritmo. Analisaremos a interação entre os grupos, sua capacidade de cooperação e coordenação, bem como sua capacidade de aprendizado e adaptação. Nossos resultados podem lançar luz sobre a evolução dos sistemas sociais e ajudar a entender melhor como os grupos se formam, evoluem e se adaptam a ambientes em mudança.

Concluiremos discutindo as possibilidades de melhorias adicionais no algoritmo modificado e sua aplicação em várias áreas. As modificações introduzidas neste trabalho permitem explorar o espaço de soluções de forma mais eficiente e encontrar valores ótimos. Isso pode ser útil para pesquisadores e praticantes que trabalham nas áreas de otimização e busca de soluções.

2. Descrição do algoritmo

O objetivo final do algoritmo, que integra os princípios dos grupos sociais, é criar um sistema eficiente de coordenação e cooperação entre os participantes do grupo. Aqui estão os princípios gerais que podem ser integrados em tal algoritmo:

• Algoritmo de movimentação: permite que o grupo se mova entre diferentes setores ou áreas. Isso permitirá que o grupo explore diversos recursos e experiências, bem como troque não apenas informações sobre coordenadas individuais, mas metadados na forma de setores com outros grupos.

• Divisão de papéis e especialização: fornece aos participantes do grupo a oportunidade de escolher e se especializar em determinadas áreas. Isso permitirá que o grupo use seus recursos e habilidades de forma eficiente para alcançar objetivos comuns. Especialmente, isso pode ser útil na resolução de problemas com espaços multidimensionais, onde estão presentes superfícies de funções com diferentes propriedades (tanto suaves quanto discretas).
  

• Cooperação e interação: permitem que os participantes do grupo cooperem e interajam entre si. Isso pode incluir troca de informações, discussão de ideias, bem como interpolação e extrapolação em áreas desconhecidas.
  

• Conflito e resolução de conflitos: mecanismos de resolução de conflitos dentro do grupo. Isso pode incluir estabelecimento de regras e procedimentos, mediação e diálogo para resolver discordâncias e disputas. Por exemplo, para evitar a competição de partículas pelos mesmos locais e permitir que economizem iterações preciosas do algoritmo.
  

• Liderança e organização: a possibilidade de haver líderes no grupo, que asseguram organização, coordenação e tomada de decisões. Os líderes devem ser capazes de motivar e conduzir o grupo para atingir seus objetivos.

• Troca de conhecimentos e experiências: permite que o grupo troque ativamente conhecimentos e experiências entre os participantes. Isso ajudará o grupo a aprender com o exemplo dos outros, adaptar-se a novas situações e tomar decisões mais informadas. A possibilidade de construir conexões lógicas complexas entre coordenadas, e não apenas utilizar a exploração estocástica do espaço.
  

• Consideração da memória do grupo: permite que o grupo mantenha informações sobre movimentos anteriores, papéis, especializações, cooperação e resolução de conflitos. Isso permitirá que o grupo use a experiência acumulada para tomar decisões mais fundamentadas sobre futuros movimentos e interações.

A integração desses princípios gerais no algoritmo permitirá criar um sistema social mais eficiente, capaz de cooperação, coordenação, troca de informações e adaptação ao ambiente em mudança.

Para melhor compreensão no contexto do algoritmo, explicaremos o significado de setor. Setor - é uma parte da área de definição do parâmetro a ser otimizado (eixos de coordenadas do espaço multidimensional). A divisão dos eixos em setores é a mesma para todos os grupos, dois grupos G0 e G1 podem estar localizados em setores de coordenadas correspondentes, por exemplo, assim:

G0 (X) |---V---|-------|-------|-------|-------|

G0 (Y) |-------|---V---|-------|-------|-------|

G0 (Z) |-------|-------|-------|-------|---V---|

-----------------------------------------------------

G1 (X) |-------|-------|---V---|-------|-------|

G1 (Y) |---V---|-------|-------|-------|-------|

G1 (Z) |-------|-------|-------|---V---|-------|

Uma das principais ideias do algoritmo é dar às equipes a oportunidade de trocar conhecimentos sobre setores bem-sucedidos, mantendo ao mesmo tempo alguma dose de aleatoriedade na liberdade de escolha dos setores.

Agora passamos à descrição do primeiro conceito do nosso algoritmo. Primeiro, consideremos o algoritmo com movimentação aleatória dos grupos entre setores, sem considerar a memória das melhores soluções.

O pseudocódigo do algoritmo é o seguinte:

1. Selecionar setores para os grupos aleatoriamente
2. Criar pontos uniformemente pelos setores
3. Calcular a função de adaptabilidade
4. Atualizar a solução global (melhor partícula da população)
5. Obter o valor da melhor partícula no grupo na iteração atual
6. Atualizar a memória das melhores soluções nos setores para cada grupo
7. Atualizar a memória das melhores soluções nos setores para cada partícula
8. Atualizar a melhor solução por grupo
9. Para o grupo, perguntar para cada coordenada separadamente a outro grupo se sua solução é melhor:
9. a) se sim: adotar seu setor
9. b) se não: com probabilidade escolher outro setor
10. Criar partículas com base nas probabilidades:
10. a) se sim: uniformemente pelo setor
10. b) se não: refinar a solução do grupo
11. Repetir a partir do ponto 4.

Podemos representar a arquitetura interna do grupo e a distribuição das coordenadas pelos setores da seguinte forma:

Group  [groups]|
                        |-----------------------------------------
                        |fB
                        |-----------------------------------------
                        |fBLast
                        |-----------------------------------------
                        |cB              [coords]
                        |-----------------------------------------
                        |cLast         [coords]
                        |-----------------------------------------
                        |centre       [coords]
                        |-----------------------------------------
                        |secInd       [coords]
                        |-----------------------------------------
                        |secIndLast [coords]
                        |-----------------------------------------
                        |p                [groupSize]|
                        |                                    |-------------------
                        |                                    |c   [coords]
                        |                                    |f   

m [coords]|
                 |--------------
                 |min [sectNumb]
                 |max [sectNumb]

Passamos à descrição do código.

Para a demarcação do espaço de busca por setores, precisamos definir os limites dos setores. Para isso, escreveremos a estrutura "S_Min_Max".  Vamos analisá-la por partes:

A estrutura "S_Min_Max" possui dois campos de dados: "min" e "max", onde "min" representa o limite do setor à esquerda e "max" representa o limite do setor à direita. O tamanho de ambos os arrays é igual ao número de setores, que é definido pelo parâmetro "sectNumb".

Também está definida na estrutura a função "Init", que inicializa os arrays "min" e "max". Ela aceita um parâmetro "sectNumb", que indica a quantidade de setores. Dentro da função "Init", o tamanho dos arrays "min" e "max" é ajustado conforme o parâmetro "sectNumb". Assim, esta estrutura oferece uma forma de armazenar os limites dos setores e inicializá-los por meio da função "Init".

//——————————————————————————————————————————————————————————————————————————————
struct S_Min_Max
{
  void Init (int sectNumb)
  {
    ArrayResize (min, sectNumb);
    ArrayResize (max, sectNumb);
  }
  double min []; //sector border on the left, size - number of sectors
  double max []; //sector border on the right, size - number of sectors
};
//——————————————————————————————————————————————————————————————————————————————

Para descrever uma partícula - membro do grupo, escreveremos a estrutura "S_Particle", que contém dois campos: "c" e "f".

• "c" é um array para armazenar as coordenadas da partícula. O tamanho do array é determinado pelo parâmetro "coords" passado para a função "Init".
• "f" é o valor da função de adaptabilidade da partícula, inicializado com o valor "-DBL_MAX" na função "Init".

Dessa forma, esta estrutura fornece um contêiner para armazenar as coordenadas da partícula e o valor associado da função.

//——————————————————————————————————————————————————————————————————————————————
struct S_Particle
{
  void Init (int coords, int sectNumb)
  {
    ArrayResize (c, coords);

    f = -DBL_MAX;
  }

  double c  [];
  double f;
};
//——————————————————————————————————————————————————————————————————————————————

Reuniremos o grupo de partículas em uma estrutura de dados "S_Group". A estrutura "S_Group" contém vários campos de dados:

• "p" representa um array de estruturas "S_Particle", que serve para armazenar as partículas do grupo. O tamanho do array "p" é determinado pelo parâmetro "groupSize", passado para a função "Init". Dentro do loop "for", cada partícula é inicializada utilizando a função "Init" da estrutura "S_Particle".
• "secInd" e "secIndLast" são arrays que armazenam os índices dos setores em cada coordenada. O tamanho dos arrays "secInd" e "secIndLast" é determinado pelo parâmetro "coords".
• "cB" e "cBLast" são arrays que armazenam as melhores coordenadas no grupo e as melhores coordenadas anteriores, respectivamente. O tamanho dos arrays "cB" e "cBLast" também é determinado pelo parâmetro "coords".
• "fB" e "fBLast" são variáveis que armazenam o melhor resultado e o resultado anterior no grupo, respectivamente.
• "centre" é um array que armazena o centro. O tamanho do array "centre" também é determinado pelo parâmetro "coords" e serve para determinar as melhores coordenadas por setor para todo o grupo.
  

A função "Init" inicializa todos os arrays e variáveis na estrutura "S_Group". Ela aceita três parâmetros: "coords" - número de coordenadas, "groupSize" - tamanho do grupo, "sectNumb" - número de setores.

Dessa forma, esta estrutura fornece um contêiner para armazenar informações sobre o grupo de partículas. As partículas seguem as regras do grupo e não interagem com partículas de outros grupos, a interação ocorre através da transferência indireta de informações via setores no nível dos grupos.

//——————————————————————————————————————————————————————————————————————————————
struct S_Group
{
  void Init (int coords, int groupSize, int sectNumb)
  {
    ArrayResize     (p,             groupSize);
    ArrayResize     (secInd,        coords);
    ArrayResize     (cB,            coords);
    ArrayResize     (cBLast,        coords);
    ArrayResize     (secIndLast,    coords);
    ArrayResize     (centre,        coords);
    for (int i = 0; i < groupSize; i++)  p [i].Init (coords, sectNumb);

    fB     = -DBL_MAX;
    fBLast = -DBL_MAX;
  }

  S_Particle p          [];
  int        secInd     []; //sector index on the coordinate, size is the number of coordinates
  int        secIndLast []; //previous index of the sector on the coordinate, the size is the number of coordinates

  double     cB         []; //the best coord's in the group
  double     cBLast     []; //the previous best coord's in the group
  double     fB;            //the best result in the group
  double     fBLast;        //the previous best result in the group
  double     centre [];
};
//——————————————————————————————————————————————————————————————————————————————

Descreveremos o agente de otimização com a estrutura "S_Agent", através da qual ocorrerá a transferência de informações das partículas dos grupos para o cálculo da função de adaptabilidade. A estrutura "S_Agent" contém dois campos:

• "c" - array que armazena as coordenadas do agente.
• "f" - armazena a função de adaptabilidade do agente.

A função "Init" inicializa o array "c" e a variável "f" na estrutura "S_Agent". Ela aceita um parâmetro "coords", que determina o tamanho do array "c".

//——————————————————————————————————————————————————————————————————————————————
struct S_Agent
{
  void Init (const int coords)
  {
    ArrayResize (c, coords);
    f = -DBL_MAX;
  }

  double c []; //coordinates
  double f;    //fitness
};
//——————————————————————————————————————————————————————————————————————————————

Descreveremos o algoritmo multi-social com a classe "C_AO_MSO". A classe contém vários campos de dados e métodos:

• "cB" - array que armazena as melhores coordenadas.
• "fB" - variável que armazena a fitness das melhores coordenadas.
• "a" - array de estruturas "S_Agent", que armazena os agentes.
• "rangeMax", "rangeMin" e "rangeStep" - arrays que armazenam os intervalos máximo e mínimo de busca e o passo, respectivamente.

A classe também contém vários métodos:

• "Init" inicializa todos os membros de dados da classe. Ele aceita parâmetros: número de coordenadas "coordinatesNumberP", tamanho da população "populationSizeP", número de grupos "groupsP", número de setores "sectorsNumberP" por coordenada, probabilidade de setor aleatório "probRNSsectorP", probabilidade de distribuição uniforme "probUniformSectorP" para partícula, probabilidade de refinamento do resultado do grupo "probClgroupP" e grau "powerP" para a função de lei de potência da distribuição.
• "Moving" e "Revision" são métodos para executar as operações principais com os grupos e partículas dos grupos.

No geral, a classe "C_AO_MSO" representa a implementação de um algoritmo de otimização usando busca múltipla com distribuição ótima de agentes. Ela contém dados e métodos para gerenciar agentes, grupos, setores e executar operações de busca e refinamento de resultados.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_MSO
{
  //----------------------------------------------------------------------------
  public: double cB [];         //best coordinates
  public: double fB;            //FF of the best coordinates
  public: S_Agent a [];         //agents

  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    groupsP,             //number of groups
                     const int    sectorsNumberP,      //sectors number
                     const double probRNSsectorP,      //probability random sector
                     const double probUniformSectorP,  //probability uniform distribution
                     const double probClgroupP,        //probability of clarifying the group's result
                     const double powerP);             //power

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

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

  private: int    sectNumb;              //sectors number
  private: double sectorSpace [];        //sector space

  private: S_Group    gr [];             //groups
  private: S_Min_Max  min_max_Sector []; //sector boundary by coordinates

  private: int    groups;                //number of groups
  private: int    sectorsNumber;         //sectors number
  private: double probRNSsector;         //probability random sector
  private: double probUniformSector;     //probability uniform distribution
  private: double probClgroup;           //probability of clarifying the group's result
  private: double power;                 //power

  private: bool   revision;

  private: double SeInDiSp  (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI (double min, double max);
  private: double Scale     (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers);
  private: double PowerDistribution (const double In, const double outMin, const double outMax, const double power);
};
//——————————————————————————————————————————————————————————————————————————————

O método "Init" inicializa o objeto da classe "C_AO_MSO" com os parâmetros fornecidos. Vamos analisar este código em partes:

No início da função, ocorre a inicialização das variáveis e membros de dados da classe. O gerador de números aleatórios é reinicializado usando o tempo atual em microssegundos. Em seguida, a variável "fB" é definida para o valor mínimo possível do tipo double "-DBL_MAX", e a variável "revision" é definida como "false".

Em seguida, os parâmetros passados para a função são atribuídos aos campos correspondentes da classe.

Para distribuir as partículas da população entre os grupos, é criado um array "partInSwarms", que armazenará a quantidade de partículas em cada grupo. O tamanho do array é definido igual ao número de grupos. Em seguida, a variável "particles" calcula o número de partículas em cada grupo dividindo o tamanho total da população "popSize" pelo número de grupos "groups".

Se houver um resto "lost", ele é distribuído entre os grupos. O loop será executado até que o resto seja igual a 0.

Depois, ocorre a alteração dos tamanhos dos arrays e a inicialização dos objetos.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_MSO::Init (const int    coordinatesNumberP,  //coordinates number
                     const int    populationSizeP,     //population size
                     const int    groupsP,             //number of groups
                     const int    sectorsNumberP,      //sectors number
                     const double probRNSsectorP,      //probability random sector
                     const double probUniformSectorP,  //probability uniform distribution
                     const double probClgroupP,        //probability of clarifying the group's result
                     const double powerP)              //power
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords            = coordinatesNumberP;
  popSize           = populationSizeP;
  groups            = groupsP;
  sectNumb          = sectorsNumberP;
  probRNSsector     = probRNSsectorP;
  probUniformSector = probUniformSectorP;
  probUniformSector = probClgroupP;
  power             = powerP;

  //----------------------------------------------------------------------------
  int partInSwarms [];
  ArrayResize (partInSwarms, groups);

  int particles = popSize / groups;
  ArrayInitialize (partInSwarms, particles);

  int lost = popSize - particles * groups;

  if (lost > 0)
  {
    int pos = 0;

    while (true)
    {
      partInSwarms [pos]++;
      lost--;
      pos++;
      if (pos >= groups) pos = 0;
      if (lost == 0) break;
    }
  }

  //----------------------------------------------------------------------------
  ArrayResize (rangeMax,  coords);
  ArrayResize (rangeMin,  coords);
  ArrayResize (rangeStep, coords);
  ArrayResize (cB,        coords);

  ArrayResize (gr,        groups);
  for (int s = 0; s < groups; s++) gr [s].Init (coords, partInSwarms [s], sectNumb);

  ArrayResize (sectorSpace, coords);

  ArrayResize (a, popSize);
  for (int i = 0; i < popSize; i++) a [i].Init (coords);
}
//——————————————————————————————————————————————————————————————————————————————

O método "Moving" é responsável pelo movimento das partículas na primeira iteração e realiza a função de inicialização dos grupos e suas partículas na posição inicial.

No início da função, verifica-se o valor da variável "revision" para garantir a execução única, e se for "false".

A primeira parte do código é responsável pela divisão do espaço em setores e pela inicialização do array "min_max_Sector". Para cada coordenada "c", calcula-se o tamanho do setor "sectorSpace[c]" como a diferença entre "rangeMax[c]" e "rangeMin[c]", dividida pelo número de setores "sectNumb". Em seguida, para cada coordenada e para cada setor, inicializam-se os valores "min" e "max" no array "min_max_Sector".

Depois, ocorre a distribuição das partículas no espaço de busca. Para cada grupo "s", selecionam-se setores aleatórios para cada coordenada. Os valores dos índices dos setores são armazenados no array "secInd" para cada grupo. Em seguida, ocorre a distribuição aleatória das partículas do grupo dentro dos setores selecionados. Para cada partícula "p" e para cada coordenada "c", seleciona-se um valor aleatório "cd" dentro dos valores mínimo e máximo do setor, e esse valor é armazenado nas coordenadas das partículas.

O último bloco de código é responsável pelo envio das partículas aos agentes. Cria-se um contador "cnt", que será usado para iterar sobre os agentes. Em seguida, para cada grupo "s" e para cada partícula "p", os valores das coordenadas da partícula são copiados para o array "a[cnt].c", onde "cnt" é incrementado após cada cópia.

Assim, o método é responsável pelo posicionamento inicial aleatório das partículas no algoritmo de otimização, divide o espaço em setores, seleciona aleatoriamente setores para cada grupo e distribui as partículas dentro dos setores selecionados. Em seguida, as partículas são enviadas aos agentes para processamento adicional.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_MSO::Moving ()
{
  if (!revision)
  {
    //marking up sectors--------------------------------------------------------
    ArrayResize (min_max_Sector, coords);

    for (int c = 0; c < coords; c++)
    {
      sectorSpace [c] = (rangeMax [c] - rangeMin [c]) / sectNumb;
      min_max_Sector [c].Init (sectNumb);

      for (int sec = 0; sec < sectNumb; sec++)
      {
        min_max_Sector [c].min [sec] = rangeMin [c] + sectorSpace [c] * sec;
        min_max_Sector [c].max [sec] = min_max_Sector [c].min [sec] + sectorSpace [c];
      }
    }

    //--------------------------------------------------------------------------
    int    sect    = 0;   //sector
    double sectMin = 0.0; //sector's min
    double sectMax = 0.0; //sector's max
    int    ind     = 0;   //index
    double cd      = 0.0; //coordinate

    for (int s = 0; s < groups; s++)
    {
      //select random sectors for the group-------------------------------------
      for (int c = 0; c < coords; c++)
      {
        ind = (int)(RNDfromCI (0, sectNumb));
        if (ind >= sectNumb) ind = sectNumb - 1;

        gr [s].secInd     [c] = ind;
        gr [s].secIndLast [c] = ind;
      }

      //random distribute the particles of the group within the sectors---------
      for (int p = 0; p < ArraySize (gr [s].p); p++)
      {
        for (int c = 0; c < coords; c++)
        {
          sect               = gr [s].secInd [c];
          cd                 = RNDfromCI (min_max_Sector [c].min [sect], min_max_Sector [c].max [sect]);
          gr [s].p [p].c [c] = SeInDiSp (cd, rangeMin [c], rangeMax [c], rangeStep [c]);
        }
      }
    }

    //--------------------------------------------------------------------------
    //send particles to agents
    int cnt = 0;

    for (int s = 0; s < groups; s++)
    {
      for (int p = 0; p < ArraySize (gr [s].p); p++)
      {
        ArrayCopy (a [cnt].c, gr [s].p [p].c, 0, 0, WHOLE_ARRAY);
        cnt++;
      }
    }

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

As operações principais de movimentação dos grupos e suas partículas pelo espaço de busca são realizadas pelo método "Revision":

• Atualização da melhor solução global comparando os valores da função de adaptabilidade de cada partícula com o valor atual. Se o valor da função objetivo da partícula atual exceder o valor atual, ele se torna o novo melhor valor, e suas coordenadas são copiadas para a variável "cB".

• Transferência dos resultados dos agentes para as partículas e determinação da melhor partícula em cada grupo. O valor da função de adaptabilidade de cada partícula é definido igual ao valor da função objetivo do agente correspondente a essa partícula. Se o valor da função de adaptabilidade da partícula exceder o valor atual na melhor solução do grupo, ele se torna o novo melhor valor, e suas coordenadas são copiadas para a variável "cB" do grupo.

• Atualização da melhor solução para cada grupo. Se o novo melhor valor no grupo exceder o anterior, ele se torna o valor atual, e suas coordenadas são copiadas para as variáveis "cBLast" e "secIndLast" do grupo.

• Para cada coordenada de cada grupo, verifica-se se existe outro grupo com uma solução melhor. Se tal grupo existir, o setor e o centro do grupo atual são atualizados com os valores do setor e do centro do grupo com a melhor solução. Caso contrário, o setor e o centro permanecem inalterados.

• Criação de novas partículas com base em probabilidades. Para cada grupo e cada partícula no grupo, geram-se novos valores de coordenadas com base em probabilidades. A probabilidade de escolher uma distribuição uniforme ou uma distribuição utilizando a função "PowerDistribution" é determinada pelos parâmetros "probUniformSector" e "power".

• Transferência das partículas criadas para os agentes para uso na próxima iteração do algoritmo de otimização.

O método realiza a atualização das soluções em cada iteração, utilizando informações sobre as melhores soluções nos grupos e probabilidades para criar novas partículas.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_MSO::Revision ()
{
  //----------------------------------------------------------------------------
  //Update the best global solution
  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB)
    {
      fB = a [i].f;
      ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  //----------------------------------------------------------------------------
  //Transfer the results from the agents to the particles
  //and get the value of the best particle in the group at the current iteration
  int cnt = 0;
  for (int s = 0; s < groups; s++)
  {
    gr [s].fB = -DBL_MAX;

    for (int p = 0; p < ArraySize (gr [s].p); p++)
    {
      gr [s].p [p].f = a [cnt].f;

      if (a [cnt].f > gr [s].fB)
      {
        gr [s].fB = a [cnt].f;
        ArrayCopy (gr [s].cB, a [cnt].c, 0, 0, WHOLE_ARRAY);
      }

      cnt++;
    }
  }

  int sector = 0;

  //----------------------------------------------------------------------------
  //Update the best solution for the group
  for (int s = 0; s < groups; s++)
  {
    if (gr [s].fB > gr [s].fBLast)
    {
      gr [s].fBLast = gr [s].fB;
      ArrayCopy (gr [s].cBLast, gr [s].cB, 0, 0, WHOLE_ARRAY);
      ArrayCopy (gr [s].secIndLast, gr [s].secInd, 0, 0, WHOLE_ARRAY);
    }

    ArrayCopy (gr [s].centre, gr [s].cBLast);
  }


  //----------------------------------------------------------------------------
  int    sect    = 0;     //sector
  double sectMin = 0.0;   //sector's min
  double sectMax = 0.0;   //sector's max
  int    ind     = 0;     //index
  double cd      = 0.0;   //coordinate

  for (int s = 0; s < groups; s++)
  {
    for (int c = 0; c < coords; c++)
    {
      if (RNDfromCI (0.0, 1.0) < 0.6)
      {
        ind = (int)(RNDfromCI (0, groups));
        if (ind >= groups) ind = groups - 1;

        if (ind == s) ind++;
        if (ind > groups - 1) ind = 0;

        if (gr [ind].fBLast > gr [s].fBLast)
        {
          gr [s].secInd [c] = gr [ind].secIndLast [c];
          gr [s].centre [c] = gr [ind].cBLast [c];
        }
      }
      else
      {
        if (RNDfromCI (0.0, 1.0) < probRNSsector)
        {
          ind = (int)(RNDfromCI (0, sectNumb));
          if (ind >= sectNumb) ind = sectNumb - 1;

          gr [s].secInd [c] = ind;
          sect = gr [s].secInd [c];

          cd = RNDfromCI (min_max_Sector [c].min [sect], min_max_Sector [c].max [sect]);
          gr [s].centre [c] = SeInDiSp (cd, rangeMin [c], rangeMax [c], rangeStep [c]);
        }
        else gr [s].secInd [c] = gr [s].secIndLast [c];
      }
    }
  }

  //----------------------------------------------------------------------------
  for (int s = 0; s < groups; s++)
  {
    for (int p = 0; p < ArraySize (gr [s].p); p++)
    {
      for (int c = 0; c < coords; c++)
      {
        sect = gr [s].secInd [c];

        if (RNDfromCI (0.0, 1.0) < probUniformSector)
        {
          cd = RNDfromCI (min_max_Sector [c].min [sect], min_max_Sector [c].max [sect]);
        }
        else
        {
           cd = PowerDistribution (gr [s].centre [c], min_max_Sector [c].min [sect], min_max_Sector [c].max [sect], power);
        }

        gr [s].p [p].c [c] = SeInDiSp (cd, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }
  //----------------------------------------------------------------------------
  cnt = 0;

  for (int s = 0; s < groups; s++)
  {
    for (int p = 0; p < ArraySize (gr [s].p); p++)
    {
      ArrayCopy (a [cnt].c, gr [s].p [p].c, 0, 0, WHOLE_ARRAY);
      cnt++;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

A seguir, consideramos o mesmo algoritmo, mas com a adição de memória para o grupo e suas partículas, e algumas outras mudanças na lógica da estratégia de busca.

O pseudocódigo do algoritmo é alterado, considerando a existência de memória para os grupos e partículas:

• 1. Selecionar setores para os grupos aleatoriamente
• 2. Criar pontos uniformemente pelos setores
• 4. Calcular a função de adaptabilidade
• 5. Atualizar a solução global (melhor partícula da população)
• 6. Obter o valor da melhor partícula no grupo na iteração atual
• 7. Atualizar a memória das melhores soluções nos setores para cada grupo
• 8. Atualizar a memória das melhores soluções nos setores para cada partícula
• 9. Atualizar a melhor solução por grupo
• 10. Para o grupo, perguntar para cada coordenada separadamente a outro grupo se sua solução é melhor:
• 10. a) se sim: adotar seu setor
• 10. b) se não: com probabilidade escolher outro setor
• 11. Criar partículas com base nas probabilidades:
• 11. a) se sim: uniformemente pelo setor
• 11. b) se não: (probabilidade ? (refinar a solução do grupo) : (refinar sua própria solução))
• 12. Repetir a partir do ponto 4.

A adição de memória teoricamente permitirá que o grupo mantenha informações sobre movimentos anteriores e as utilize para tomar decisões sobre o futuro. Isso pode ajudar os grupos a se adaptarem melhor ao ambiente em mudança e a explorar o espaço de soluções de forma mais eficaz.

Faremos mudanças na arquitetura interna do grupo da seguinte forma:

Swarm [groups]|
                        |-----------------------------------------
                        |fB
                        |-----------------------------------------
                        |fBLast
                        |-----------------------------------------
                        |cB               [coords]
                        |-----------------------------------------
                        |cBLast        [coords]
                        |-----------------------------------------
                        |secInd        [coords]
                        |-----------------------------------------
                        |secIndLast [coords]
                        |-----------------------------------------
                        |sMemory    [coords]|
                        |                               |---------------
                        |                               |cB      [sectNumb]
                        |                               |fB      [sectNumb]
                        |-----------------------------------------
                        |p         [groupSize] |
                        |                              |-------------------
                        |                              |c       [coords]
                        |                              |f
                        |                              |pMemory [coords]|
                        |                                                            |--------
                        |                                                            |cB [sectNumb]
                        |                                                            |fB [sectNumb]

Adicionaremos a estrutura "S_Memory", que descreve a memória. Para grupos e partículas, a memória terá a mesma aparência e conterá dois arrays "cB" e "fB" para armazenar informações sobre as melhores coordenadas e a função de adaptabilidade para essas coordenadas.

//——————————————————————————————————————————————————————————————————————————————
struct S_Memory
{
  void Init (int sectNumb)
  {
    ArrayResize     (cB, sectNumb);
    ArrayResize     (fB, sectNumb);
    ArrayInitialize (fB, -DBL_MAX);
  }
  double cB []; //the best sector coordinate, size is the number of sectors
  double fB []; //FF is the best coordinate on a sector, size is the number of sectors
};
//——————————————————————————————————————————————————————————————————————————————

Portanto, nas estruturas de partículas e grupos, adicionaremos declarações de memória:

//——————————————————————————————————————————————————————————————————————————————
struct S_Particle
{
  <..............code is hidden.................>

  S_Memory pMemory []; //particle memory, size - the number of coordinates
};
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
struct S_Group
{
  <..............code is hidden.................>

  S_Memory sMemory []; //group memory, size - number of coordinates 
}; 
//——————————————————————————————————————————————————————————————————————————————

As mudanças também afetaram o método "Revision":

• Atualização das melhores coordenadas dos setores na memória do enxame. Para cada grupo e cada coordenada, todos os setores são iterados. Se o valor "fB" do grupo em um setor for maior que o valor "fB" na memória do setor, então "fB" e "cB" são atualizados na memória.

• Atualização das melhores posições na memória das partículas. Se o valor da função de adaptabilidade da partícula for maior que o valor na memória da partícula, então "fB" e "cB" são atualizados na memória.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_MSO::Revision ()
{
  //----------------------------------------------------------------------------
  //Update the best global solution
  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB)
    {
      fB = a [i].f;
      ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY);
    }
  }

  //----------------------------------------------------------------------------
  //Transfer the results from the agents to the particles
  //and get the value of the best particle in the group at the current iteration
  int cnt = 0;
  for (int s = 0; s < groups; s++)
  {
    gr [s].fB = -DBL_MAX;

    for (int p = 0; p < ArraySize (gr [s].p); p++)
    {
      gr [s].p [p].f = a [cnt].f;

      if (a [cnt].f > gr [s].fB)
      {
        gr [s].fB = a [cnt].f;
        ArrayCopy (gr [s].cB, a [cnt].c, 0, 0, WHOLE_ARRAY);
      }

      cnt++;
    }
  }

  //----------------------------------------------------------------------------
  //Update the best sector coordinates in the swarm's memory
  int sector = 0;
  for (int s = 0; s < groups; s++)
  {
    for (int c = 0; c < coords; c++)
    {
      sector = gr [s].secInd [c];

      if (gr [s].fB > gr [s].sMemory [c].fB [sector])
      {
        gr [s].sMemory [c].fB [sector] = gr [s].fB;
        gr [s].sMemory [c].cB [sector] = gr [s].cB [c];
      }
    }
  }

  //----------------------------------------------------------------------------
  //Update in the memory of the particles their best positions by sector
  sector  = 0;
  for (int s = 0; s < groups; s++)
  {
    for (int p = 0; p < ArraySize (gr [s].p); p++)
    {
      for (int c = 0; c < coords; c++)
      {
        sector = gr [s].secInd [c];

        if (gr [s].p [p].f > gr [s].p [p].pMemory [c].fB [sector])
        {
          gr [s].p [p].pMemory [c].fB [sector] = gr [s].p [p].f;
          gr [s].p [p].pMemory [c].cB [sector] = gr [s].p [p].c [c];
        }
      }
    }
  }

  //----------------------------------------------------------------------------
  //Update the best solution for the group
  for (int s = 0; s < groups; s++)
  {
    if (gr [s].fB > gr [s].fBLast)
    {
      gr [s].fBLast = gr [s].fB;
      ArrayCopy (gr [s].cBLast, gr [s].cB, 0, 0, WHOLE_ARRAY);
      ArrayCopy (gr [s].secIndLast, gr [s].secInd, 0, 0, WHOLE_ARRAY);
    }
  }

  //----------------------------------------------------------------------------
  int    sect    = 0;     //sector
  double sectMin = 0.0;   //sector's min
  double sectMax = 0.0;   //sector's max
  int    ind     = 0;     //index
  double cd      = 0.0;   //coordinate

  for (int s = 0; s < groups; s++)
  {
    for (int c = 0; c < coords; c++)
    {
      ind = (int)(RNDfromCI (0, groups));
      if (ind >= groups) ind = groups - 1;

      if (ind == s) ind++;
      if (ind > groups - 1) ind = 0;

      if (RNDfromCI (0.0, 1.0) < 0.6)
      {
        if (gr [ind].fBLast > gr [s].fBLast)                                       
        {
          gr [s].secInd [c] = gr [ind].secIndLast [c];
        }
      }
      else                                                                      
      {
        if (RNDfromCI (0.0, 1.0) < probRNSsector)
        {
          ind = (int)(RNDfromCI (0, sectNumb));
          if (ind >= sectNumb) ind = sectNumb - 1;

          gr [s].secInd [c] = ind;
          sect = gr [s].secInd [c];

          if (gr [s].sMemory [c].fB [sect] == -DBL_MAX)
          {
            cd = RNDfromCI (min_max_Sector [c].min [sect], min_max_Sector [c].max [sect]);
            gr [s].sMemory [c].cB [sect] = SeInDiSp (cd, rangeMin [c], rangeMax [c], rangeStep [c]);
          }
        }
        else gr [s].secInd [c] = gr [s].secIndLast [c];
      }
    }
  }

  //----------------------------------------------------------------------------
  for (int s = 0; s < groups; s++)
  {
    for (int p = 0; p < ArraySize (gr [s].p); p++)
    {
      for (int c = 0; c < coords; c++)
      {
        sect = gr [s].secInd [c];

        if (RNDfromCI (0.0, 1.0) < probUniformSector)
        {
          cd = RNDfromCI (min_max_Sector [c].min [sect], min_max_Sector [c].max [sect]);
        }
        else
        {
          if (RNDfromCI (0.0, 1.0) < probClgroup)
          {
            cd = PowerDistribution (gr [s].sMemory [c].cB [sect], min_max_Sector [c].min [sect], min_max_Sector [c].max [sect], power);
          }
          else
          {
            cd = PowerDistribution (gr [s].p [p].pMemory [c].cB [sect], min_max_Sector [c].min [sect], min_max_Sector [c].max [sect], power);
          }
        }

        gr [s].p [p].c [c] = SeInDiSp (cd, rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }
  }

  //----------------------------------------------------------------------------
  //send the particles to the agents
  cnt = 0;

  for (int s = 0; s < groups; s++)
  {
    for (int p = 0; p < ArraySize (gr [s].p); p++)
    {
      ArrayCopy (a [cnt].c, gr [s].p [p].c, 0, 0, WHOLE_ARRAY);
      cnt++;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Resultados dos testes

Analisados os resultados dos testes do algoritmo sem considerar a memória das partículas, pode-se notar que ele demonstra resultados bastante bons. O algoritmo ocupa uma posição entre os dez melhores na tabela de classificação. É importante notar que este algoritmo serve apenas como um exemplo de lógica, e se tivesse demonstrado resultados excepcionais, eu o incluiria na tabela. Ainda existem muitas oportunidades para a implementação e modificação deste algoritmo.

Embora os resultados não sejam extraordinários, o algoritmo mostrou boas habilidades de busca ao explorar diferentes áreas do espaço de busca.

C_AO_MSO|60|30|9|0.05|0.05|10.0
=============================
5 Hilly's; Func runs: 10000; result: 0.9313358190790157
25 Hilly's; Func runs: 10000; result: 0.6649184286250989
500 Hilly's; Func runs: 10000; result: 0.3282041522365852
=============================
5 Forest's; Func runs: 10000; result: 0.9522099605531393
25 Forest's; Func runs: 10000; result: 0.5542256622730999
500 Forest's; Func runs: 10000; result: 0.08984352753493675
=============================
5 Megacity's; Func runs: 10000; result: 0.7899999999999998
25 Megacity's; Func runs: 10000; result: 0.33533333333333326
500 Megacity's; Func runs: 10000; result: 0.042983333333333325
=============================
All score: 4.68905 (52.1%)

Os resultados seguintes referem-se à variante de grupos sociais com memória, onde a degradação dos resultados gerais do algoritmo é pequena. No entanto, este algoritmo ocupa uma posição respeitável na parte superior da tabela de classificação. Isso indica o potencial do algoritmo e sua capacidade de alcançar resultados satisfatórios. A ideia de considerar a troca de memória não apenas entre grupos, mas também entre suas partículas, é um passo lógico para melhorar o algoritmo. A introdução de tal interação adicional pode levar ao surgimento de novas ideias e estratégias. Como mencionado anteriormente no artigo, foram descritos vários cenários de interação entre grupos sociais, e incluí apenas alguns deles. Isso significa que há amplas oportunidades para modificar e melhorar o algoritmo.

C_AO_MSOm|60|30|9|0.1|0.9|0.1|10.0
=============================
5 Hilly's; Func runs: 10000; result: 0.9468984351872132
25 Hilly's; Func runs: 10000; result: 0.5865441453580522
500 Hilly's; Func runs: 10000; result: 0.3186653673403949
=============================
5 Forest's; Func runs: 10000; result: 0.9064162754293653
25 Forest's; Func runs: 10000; result: 0.43175851113448455
500 Forest's; Func runs: 10000; result: 0.06865408175918558
=============================
5 Megacity's; Func runs: 10000; result: 0.6783333333333333
25 Megacity's; Func runs: 10000; result: 0.213
500 Megacity's; Func runs: 10000; result: 0.03310000000000002
=============================
All score: 4.18337 (46.4%)

  MSO na função de teste Hilly.

  MSO na função de teste Forest.

  MSO na função de teste Megacity.

Considerações finais

Com base nas considerações e resultados anteriores, pode-se acrescentar o seguinte:

Nos experimentos, descobriu-se que o algoritmo com memória apresentou resultados um pouco abaixo em comparação com o algoritmo sem memória. No entanto, isso não significa que o algoritmo com memória seja menos promissor. Provavelmente, é necessário modificar a concepção de troca de memória entre grupos e partículas para melhorar seus resultados.

Além disso, vale ressaltar que a inclusão de outros princípios de interação entre grupos sociais pode aumentar significativamente a eficiência do algoritmo com memória. A introdução de mecanismos de cooperação, coordenação e aprendizado entre grupos pode levar a uma melhoria significativa dos indicadores e colocar o algoritmo em uma das posições de liderança na nossa tabela de classificação.

Em conclusão, a pesquisa propõe uma nova concepção da evolução de grupos sociais, baseada na movimentação entre setores e no uso de memória. Essas concepções abrem novas possibilidades para o estudo dos sistemas sociais e sua capacidade de cooperação, coordenação e adaptação. Espero que os resultados ajudem a entender melhor como os grupos sociais funcionam e evoluem em ambientes sociais complexos, e isso possibilitará a continuação de pesquisas futuras nesta área.