Algoritmo de Evolução do Casco da Tartaruga (Turtle Shell Evolution Algorithm, TSEA)

Conteúdo:

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

1. Introdução

A tartaruga é uma das mais antigas e surpreendentes criações da natureza. Ela carrega em si um casco — símbolo de resistência, proteção e sobrevivência. Este majestoso escudo, formado ao longo da vida da tartaruga, encarna não apenas sua proteção física, mas também simboliza desenvolvimento contínuo e superação de obstáculos.

Os desenhos no casco são testemunhos da singularidade de seu caminho evolutivo, simbolizando a harmonia entre o tempo e o próprio ser. O crescimento do casco da tartaruga ocorre a partir de um ponto central, chamado de umbigo. Novas camadas de material são adicionadas ao casco já existente, resultando na formação de diferentes padrões. Cada segmento do padrão representa um ano ou uma estação de crescimento da tartaruga. Camada após camada, ano após ano, o casco amadurece junto com a tartaruga. Ele adquire novos padrões, formando clusters únicos, que refletem sua experiência de vida e crescimento.

O casco da tartaruga é composto por duas partes principais: a parte superior, chamada carapaça, e a parte inferior, chamada plastrão. O crescimento do casco nas tartarugas ocorre mediante um processo chamado metamorfose. Os padrões no casco da tartaruga são o resultado de uma complexa interação de vários fatores, incluindo genética, ambiente e o processo de crescimento do próprio casco.

O casco da tartaruga é composto de tecido biológico e substâncias carbonatadas, como cálcio e magnésio. A estrutura carbonatada do casco lhe confere resistência e protege os órgãos internos da tartaruga. Nas tartarugas jovens, o casco é composto de placas cartilaginosas macias, que com o tempo se tornam ossos duros. O casco cresce devido ao depósito regular de novas camadas de tecido ósseo sob a pele da tartaruga. Este processo permite que o casco aumente de tamanho à medida que a tartaruga cresce e, com o tempo, pode levar ao surgimento de novos padrões ou à mudança dos já existentes.

Os padrões no casco da tartaruga não são aleatórios. Eles são formados como resultado de certos processos biológicos e podem ser classificados em diferentes grupos ou "clusters" com base em sua forma, cor e disposição. Por exemplo, algumas tartarugas têm padrões em forma de estrela, enquanto outras têm padrões que lembram a pele de leopardo. À medida que o casco da tartaruga cresce, os padrões nele podem mudar e evoluir. Isso pode levar à mudança do cluster ao qual o padrão pertence. Por exemplo, um padrão que inicialmente foi classificado como "estrelado" pode se tornar mais complexo com o tempo.

É importante destacar que os padrões no casco de cada tartaruga são únicos e ajudam-na a se adaptar ao ambiente, desempenhando funções importantes, como camuflagem ou atração de parceiros para reprodução.

Os padrões no casco da tartaruga me inspiraram a criar um algoritmo de otimização original, e a evolução do casco tornou-se uma metáfora para o processo de fusão e clusterização de dados, resultando na criação de uma nova ferramenta, capaz de se adaptar e evoluir com base na experiência e no conhecimento.

2. Implementação do algoritmo

A ideia por trás do algoritmo de evolução do casco da tartaruga é emular o crescimento do casco por meio da formação gradual de novas áreas queratinizadas da pele, que representam as soluções para o problema de otimização. Neste modelo, as melhores soluções tornam-se mais rígidas e estão mais próximas da superfície externa do casco, enquanto as soluções menos bem-sucedidas permanecem macias e ficam localizadas no interior do casco.

O casco, neste contexto, é dividido em clusters, que formam o padrão na superfície, e suas camadas são modeladas por meio de uma divisão vertical em clusters. O processo de emulação do crescimento do casco no algoritmo inclui movimento tanto para cima (externo) quanto para baixo (interno), além da expansão lateral. Uma característica única deste algoritmo de otimização é a preservação de soluções menos bem-sucedidas, o que se manifesta no crescimento interno do casco. A camada interna do casco é a única que se expande em ambas as direções, enquanto as demais camadas crescem apenas para fora, sendo que as piores soluções são substituídas por novas. Cada cluster vertical (camada) tem uma capacidade limitada para soluções; se o número máximo não for atingido, novas soluções são simplesmente adicionadas. Caso contrário, uma solução é substituída de acordo com o princípio descrito.

A Figura 1 ilustra a clusterização das soluções com base em sua qualidade e na distância entre elas. Para melhor compreensão, foi utilizado um exemplo hipotético em um espaço unidimensional de soluções. Este esquema permite visualizar como os clusters se formam em função da qualidade e da proximidade das soluções entre si.

Figura 1. Clusterização por qualidade das soluções e pela distância entre elas no algoritmo TSEA.

Agora, vamos escrever o pseudocódigo do algoritmo TSEA:

1.  Gerar indivíduos aleatórios na população.
2.  Calcular a FF.
3.  Clusterização inicial da população na vertical.
4.  Clusterização inicial da população K-Means na horizontal.
5.  Colocar a população no casco.
6.  Gerar uma nova população com base nos dados no casco:
     6.1. Com probabilidade de 0,8:
          Selecionar um cluster na vertical.
          Escolher, com probabilidade de 0,5, o melhor agente na célula, ou qualquer outro agente aleatório na célula.
          Com probabilidade de 0,6 para cada coordenada, usar o agente escolhido na célula ou usar a melhor solução global.
          Gerar uma nova coordenada para o agente usando uma distribuição de potência.
     6.2 Ou:
          Selecionar um cluster na vertical.
          Selecionar dois clusters na vertical e, a partir deles, escolher um agente de cada cluster aleatoriamente.
          Criar uma nova coordenada como o valor médio das coordenadas dos agentes selecionados.
7.   Calcular a FF.
8.   Clusterização da população na vertical.
9.   Determinar a afiliação dos agentes aos clusters do casco com K-NN (método dos N vizinhos mais próximos).
10. A cada 50 épocas, realizar uma clusterização do casco na vertical.
11. Colocar a população no casco.
12. Repetir a partir do passo 6.

A escolha do cluster vertical será realizada de acordo com uma lei quadrática (ver Fig. 2), que atribui uma maior probabilidade ao último cluster da lista (o melhor) em comparação com o cluster 0 (o pior).

Figura 2. Lei de probabilidade de seleção de clusters na vertical (por qualidade), onde 3 é o número de clusters.

Assim, a lógica para a criação de novas áreas do casco (agentes - soluções do problema de otimização) é a seguinte:

1. Seleção de uma camada do casco (cluster vertical). A probabilidade de escolher a camada superior, mais rígida, é maior do que a das camadas inferiores, menos rígidas.
2. Seleção das áreas do casco a partir dos clusters horizontais na camada escolhida.
3. "Fusão" das áreas selecionadas.

A probabilidade de "fusão" (endurecimento) é maior para as camadas superiores do que para as inferiores.

Agora que temos o pseudocódigo e a lei de escolha dos agentes na população-mãe, podemos dizer que a tarefa está 99% completa. Claro, estou brincando, ainda será necessário escrever o código.

O agente de otimização do algoritmo TSEA será descrito como uma estrutura "S_TSEA_Agent", e precisaremos de rótulos para os clusters na vertical e na horizontal.

1. A estrutura contém os seguintes campos:

• c[] - array para armazenar as coordenadas do agente
• f - variável para armazenar a avaliação (fitness) do agente
• label - rótulo de afiliação ao cluster
• labelClustV - clusterização vertical
• minDist - distância mínima até o centróide mais próximo

2. Init - este é o método da estrutura "S_TSEA_Agent", que inicializa os campos da estrutura. Ele aceita um argumento inteiro "coords", que é utilizado para redimensionar o array c usando a função ArrayResize.
3. f = -DBL_MAX - define o valor inicial da variável f como o menor valor possível para um número do tipo double.
4. label = -1 e labelClustV = -1 - inicializam os rótulos de afiliação ao cluster com o valor -1.
5. minDist = DBL_MAX - define o valor inicial da variável "minDist" como o maior valor possível para um número do tipo double.

Este código representa a estrutura básica de dados para os agentes no algoritmo de otimização TSEA e inicializa seus campos ao criar um novo agente. Isso permite que os agentes armazenem informações sobre seu estado atual e as atualizem conforme o algoritmo é executado.

//——————————————————————————————————————————————————————————————————————————————
struct S_TSEA_Agent
{
    double c     [];     //coordinates
    double f;            //fitness
    int    label;        //cluster membership label
    int    labelClustV;  //clusters vertically
    double minDist;      //minimum distance to the nearest centroid

    void Init (int coords)
    {
      ArrayResize (c,     coords);
      f           = -DBL_MAX;
      label       = -1;
      labelClustV = -1;
      minDist     = DBL_MAX;
    }
};
//——————————————————————————————————————————————————————————————————————————————

Precisaremos descrever o casco da tartaruga, que será representado por uma matriz bidimensional, onde os clusters de fitness estão dispostos verticalmente, e os clusters de posição estão dispostos horizontalmente. Cada célula da matriz bidimensional contém de 0 até o valor máximo definido nos parâmetros externos do algoritmo.

O cluster horizontal será descrito pela estrutura "S_TSEA_horizontal", que contém os seguintes campos:

• indBest - índice do melhor agente na célula.
  
• agent[] - um array de estruturas S_TSEA_Agent, utilizado para armazenar os agentes.

O cluster vertical pode ser descrito pela estrutura "S_TSEA_horizontal", contendo os campos:

• cell[] - um array de estruturas "S_TSEA_horizontal".
  

Dessa forma, o código nos dá a possibilidade de descrever o casco da tartaruga em duas direções de uma matriz bidimensional, onde cada célula pode armazenar os agentes de otimização. Essencialmente, o casco é uma população parental estruturada de maneira especial, que será conveniente acessar ao criar os agentes filhos.

//——————————————————————————————————————————————————————————————————————————————
struct S_TSEA_horizontal
{
    int indBest;
    S_TSEA_Agent agent [];
};

struct S_TSEA_vertical
{
    S_TSEA_horizontal cell [];
};

//——————————————————————————————————————————————————————————————————————————————

Para realizar a clusterização, conforme o pseudocódigo fornecido, o algoritmo TSEA usa dois métodos de clusterização: K-Means e K-NN. K-Means foi discutido no artigo sobre o algoritmo BSO, e aqui vamos apenas relembrar como a estrutura do cluster é apresentada:

• centroid[] - array para armazenar as coordenadas do centróide da célula.
• f - variável para armazenar a avaliação (fitness) do centróide.
• count - número de agentes no cluster.
• agentList[] - lista de agentes no cluster.
• Init - método da estrutura "S_Cluster", que inicializa os campos da estrutura.
  

//——————————————————————————————————————————————————————————————————————————————
struct S_Cluster
{
    double centroid [];  //cluster centroid
    double f;            //centroid fitness
    int    count;        //number of points in the cluster

    void Init (int coords)
    {
      ArrayResize (centroid, coords);
      f     = -DBL_MAX;
      count = 0;
      ArrayResize (ideasList, 0, 100);
    }
};
//——————————————————————————————————————————————————————————————————————————————

Para determinar a afiliação de um agente filho ao respectivo cluster, usaremos o método K-NN (método dos k-vizinhos mais próximos).

Na classe "C_TSEA_clusters", além do método K-Means, os seguintes métodos estão incluídos:

1. O método "VectorDistance":

• Esse método calcula a distância euclidiana entre dois vetores "v1" e "v2", representados por arrays de números do tipo "double".
• Ele usa a fórmula da distância euclidiana: .
• O valor da distância calculada é retornado.

2. A estrutura "DistanceIndex":

• Essa estrutura representa um par de valores: a distância "distance" e o índice "index".
• É usada para armazenar as distâncias de um ponto até outros pontos e seus índices.

3. O método "BubbleSort":

• Este método ordena um array de objetos do tipo "DistanceIndex" usando o método de ordenação por bolha, em ordem crescente das distâncias.
• É usada uma variável temporária "temp" para trocar os elementos do array.

4. O método "KNN" implementa o algoritmo dos k-vizinhos mais próximos para classificar um ponto "point":

• Ele calcula as distâncias do ponto "point" até todos os pontos no array "data", ordena essas distâncias e determina a afiliação do ponto a um dos "n_clusters" clusters com base nos k-vizinhos mais próximos.
• É utilizado um array "votes" para contar os votos de cada cluster.
• O índice do cluster com o maior número de votos é retornado.

//——————————————————————————————————————————————————————————————————————————————
class C_TSEA_clusters
{
  public:

  double VectorDistance (double &v1 [], double &v2 [])
  {
    double distance = 0.0;
    for (int i = 0; i < ArraySize (v1); i++)
    {
      distance += (v1 [i] - v2 [i]) * (v1 [i] - v2 [i]);
    }
    return MathSqrt (distance);
  }

  struct DistanceIndex
  {
      double distance;
      int index;
  };

  void BubbleSort (DistanceIndex &arr [], int start, int end)
  {
    for (int i = start; i < end; i++)
    {
      for (int j = start; j < end - i; j++)
      {
        if (arr [j].distance > arr [j + 1].distance)
        {
          DistanceIndex temp = arr [j];
          arr [j] = arr [j + 1];
          arr [j + 1] = temp;
        }
      }
    }
  }

  int KNN (S_TSEA_Agent &data [], S_TSEA_Agent &point, int k_neighbors, int n_clusters)
  {
    int n = ArraySize (data);
    DistanceIndex distances_indices [];

    // Вычисление расстояний от точки до всех других точек
    for (int i = 0; i < n; i++)
    {
      DistanceIndex dist;
      dist.distance = VectorDistance (point.c, data [i].c);
      dist.index = i;
      ArrayResize (distances_indices, n);
      distances_indices [i] = dist;
    }

    // Сортировка расстояний
    BubbleSort (distances_indices, 0, n - 1);

    // Определение кластера для точки
    int votes [];
    ArrayResize (votes, n_clusters);
    ArrayInitialize (votes, 0);

    for (int j = 0; j < k_neighbors; j++)
    {
      int label = data [distances_indices [j].index].label;

      if (label != -1 && label < n_clusters)
      {
        votes [label]++;
      }
    }

    int max_votes = 0;
    int max_votes_cluster = -1;

    for (int j = 0; j < n_clusters; j++)
    {
      if (votes [j] > max_votes)
      {
        max_votes = votes [j];
        max_votes_cluster = j;
      }
    }

    return max_votes_cluster;
  }
};
//——————————————————————————————————————————————————————————————————————————————

Agora passamos diretamente à descrição da classe "C_AO_TSEA", que deriva da classe base "C_AO" e implementa o algoritmo "Turtle Shell Evolution Algorithm" (TSEA). Campos e métodos da classe:

1. C_AO_TSEA - o construtor inicializa os campos da classe. Ele define o nome do algoritmo, sua descrição e um link para o artigo sobre o algoritmo. Além disso, define os parâmetros do algoritmo, como: tamanho da população, número de clusters verticais e horizontais, número de vizinhos mais próximos e o número máximo de agentes por célula.

2. SetParams - o método define os parâmetros do algoritmo com base nos valores do array "params".

3. Init - o método inicializa o algoritmo. Ele recebe os intervalos mínimos e máximos de busca, o passo de busca e o número de épocas.

4. Os métodos "Moving" e "Revision" são os principais métodos do algoritmo TSEA, que implementam sua lógica central.

5. Os campos "vClusters", "hClusters", "neighbNumb" e "maxAgentsInCell" são parâmetros do algoritmo definidos no construtor e podem ser alterados usando o método "SetParams".

6. Os arrays "agent", "cell" e "clusters" são estruturas de dados utilizadas pelo algoritmo. Eles contêm informações sobre os agentes, as células e os clusters, respectivamente.

7. O objeto "km" da classe "C_TSEA_clusters" é usado para realizar operações de clusterização.

8. Os campos privados "minFval", "stepF", "epochs" e "epochsNow" são variáveis internas. Elas não são destinadas ao acesso externo à classe.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_TSEA : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_TSEA () { }
  C_AO_TSEA ()
  {
    ao_name = "TSEA";
    ao_desc = "Turtle Shell Evolution Algorithm";
    ao_link = "https://www.mql5.com/ru/articles/14789";

    popSize         = 100; //population size

    vClusters       = 3;   //number of vertical clusters
    hClusters       = 10;  //number of horizontal clusters
    neighbNumb      = 5;   //number of nearest neighbors
    maxAgentsInCell = 3;   //max agents in cell

    ArrayResize (params, 5);

    params [0].name = "popSize";          params [0].val  = popSize;

    params [1].name = "vClusters";        params [1].val  = vClusters;
    params [2].name = "hClusters";        params [2].val  = hClusters;
    params [3].name = "neighbNumb";       params [3].val  = neighbNumb;
    params [4].name = "maxAgentsInCell";  params [4].val  = maxAgentsInCell;
  }

  void SetParams ()
  {
    popSize         = (int)params [0].val;

    vClusters       = (int)params [1].val;
    hClusters       = (int)params [2].val;
    neighbNumb      = (int)params [3].val;
    maxAgentsInCell = (int)params [4].val;
  }

  bool Init (const double &rangeMinP  [], //minimum search range
             const double &rangeMaxP  [], //maximum search range
             const double &rangeStepP [], //step search
             const int     epochsP = 0);  //number of epochs

  void Moving    ();
  void Revision  ();
  void Injection (const int popPos, const int coordPos, const double value);

  //----------------------------------------------------------------------------
  int    vClusters;      //number of vertical clusters
  int    hClusters;      //number of horizontal clusters
  int    neighbNumb;     //number of nearest neighbors
  int    maxAgentsInCell;

  S_TSEA_Agent    agent   [];
  S_TSEA_vertical cell    [];

  S_Cluster      clusters [];
  C_TSEA_clusters km;

  private: //-------------------------------------------------------------------
  double minFval;
  double stepF;

  int    epochs;
  int    epochsNow;
};
//——————————————————————————————————————————————————————————————————————————————

O método "Init" da classe "C_AO_TSEA" inicializa o algoritmo TSEA. Descrição detalhada de seu funcionamento:

1. StandardInit (rangeMinP, rangeMaxP, rangeStepP) - o método é chamado para a inicialização padrão do algoritmo. Ele recebe os intervalos mínimos e máximos de busca e o passo de busca. Se a inicialização falhar, o método retorna "false".

2. ArrayResize(agent, popSize) - redimensiona o array "agent" para o tamanho da população "popSize". Em seguida, para cada agente, é chamado o método "Init(coords)", que inicializa o agente.

3. ArrayResize(clusters, hClusters) - redimensiona o array "clusters" para o número de clusters horizontais "hClusters". Depois, para cada cluster, o método "Init(coords)" é chamado para inicializar o cluster.

4. ArrayResize(cell, vClusters) - redimensiona o array "cell" para o número de clusters verticais "vClusters". Depois, para cada célula, o array "cell[i].cell" e o array de agentes em cada célula são inicializados.

5. "minFval = DBL_MAX", "stepF = 0.0", "epochs = epochsP", "epochsNow = 0". Essa é a inicialização das variáveis internas do algoritmo.

6. No final, o método retorna "true", indicando que a inicialização foi bem-sucedida.

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_TSEA::Init (const double &rangeMinP  [], //minimum search range
                      const double &rangeMaxP  [], //maximum search range
                      const double &rangeStepP [], //step search
                      const int     epochsP = 0)   //number of epochs
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false;

  //----------------------------------------------------------------------------
  ArrayResize (agent, popSize);
  for (int i = 0; i < popSize; i++) agent [i].Init (coords);

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

  ArrayResize (cell, vClusters);

  for (int i = 0; i < vClusters; i++)
  {
    ArrayResize (cell [i].cell, hClusters);

    for (int c = 0; c < hClusters; c++) ArrayResize (cell [i].cell [c].agent, 0, maxAgentsInCell);
  }

  minFval   = DBL_MAX;
  stepF     = 0.0;
  epochs    = epochsP;
  epochsNow = 0;

  return true;
}
//——————————————————————————————————————————————————————————————————————————————

O método "Moving" da classe "C_AO_TSEA" implementa a lógica central de movimentação dos agentes no algoritmo TSEA. Breve descrição dos principais passos:

1. Inicialização da população:

• Se for a primeira iteração (revision == false), os indivíduos são gerados aleatoriamente na população.
• Caso contrário, a população é atualizada com base nas soluções existentes.

2. Atualização da população:

• Para cada cluster (vClusters x hClusters), encontra-se a melhor solução.
• Novas soluções são formadas da seguinte maneira:
• Com uma probabilidade de 0,5, a melhor solução de um cluster aleatório é copiada com algum deslocamento.
• Com uma probabilidade de 0,2, uma nova solução é formada como a média de duas soluções aleatórias de clusters diferentes.
• As novas coordenadas das soluções são geradas usando uma distribuição de potência para manter a proximidade com as melhores soluções.

3. Atualização dos agentes (indivíduos) na população.

Esse método implementa a ideia central da evolução do casco da tartaruga, onde as melhores soluções tornam-se mais "rígidas" e ficam mais próximas da superfície externa, enquanto as soluções menos bem-sucedidas permanecem "macias" e localizadas no interior. A clusterização das soluções e a preservação das opções menos bem-sucedidas garantem a flexibilidade e a adaptabilidade do algoritmo.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_TSEA::Moving ()
{
  epochsNow++;

  //----------------------------------------------------------------------------
  //1. Сгенерировать случайные особи в популяцию
  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = u.SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);

        agent [i].c [c] = a [i].c [c];
      }
    }

    return;
  }

  //----------------------------------------------------------------------------
  int    vPos = 0;
  int    hPos = 0;
  int    pos  = 0;
  int    size = 0;
  double val  = 0.0;
  double rnd  = 0.0;
  double min  = 0.0;
  double max  = 0.0;

  for (int v = 0; v < vClusters; v++)
  {
    for (int h = 0; h < hClusters; h++)
    {
      size = ArraySize (cell [v].cell [h].agent);

      if (size > 0)
      {
        max = -DBL_MAX;
        pos = -1;

        for (int c = 0; c < size; c++)
        {
          if (cell [v].cell [h].agent [c].f > max)
          {
            max = cell [v].cell [h].agent [c].f;
            pos = c;
            cell [v].cell [h].indBest = c;
          }
        }
      }
    }
  }

  for (int i = 0; i < popSize; i++)
  {
    if (u.RNDprobab () < 0.8)
    {
      while (true)
      {
        rnd = u.RNDprobab ();
        rnd = (-rnd * rnd + 1.0) * vClusters;

        vPos = (int)rnd;
        if (vPos > vClusters - 1) vPos = vClusters - 1;

        hPos = u.RNDminusOne (hClusters);

        size = ArraySize (cell [vPos].cell [hPos].agent);

        if (size > 0) break;
      }

      pos = u.RNDminusOne (size);

      if (u.RNDprobab () < 0.5) pos = cell [vPos].cell [hPos].indBest;

      for (int c = 0; c < coords; c++)
      {
        if (u.RNDprobab () < 0.6) val = cell [vPos].cell [hPos].agent [pos].c [c];
        else                      val = cB [c];

        double dist = (rangeMax [c] - rangeMin [c]) * 0.1;
        min = val - dist; if (min < rangeMin [c]) min = rangeMin [c];
        max = val + dist; if (max > rangeMax [c]) max = rangeMax [c];

        val = u.PowerDistribution (val, min, max, 30);

        a [i].c [c] = u.SeInDiSp  (val, rangeMin [c], rangeMax [c], rangeStep [c]);

        agent [i].c [c] = a [i].c [c];
      }
    }
    else
    {
      int size2 = 0;
      int hPos2 = 0;
      int pos2  = 0;

      while (true)
      {
        rnd = u.RNDprobab ();
        rnd = (-rnd * rnd + 1.0) * vClusters;

        vPos = (int)rnd;
        if (vPos > vClusters - 1) vPos = vClusters - 1;

        hPos = u.RNDminusOne (hClusters);
        size = ArraySize (cell [vPos].cell [hPos].agent);

        hPos2 = u.RNDminusOne (hClusters);
        size2 = ArraySize (cell [vPos].cell [hPos2].agent);

        if (size > 0 && size2 > 0) break;
      }

      pos  = u.RNDminusOne (size);
      pos2 = u.RNDminusOne (size2);

      for (int c = 0; c < coords; c++)
      {
        val = (cell [vPos].cell [hPos ].agent [pos ].c [c] +
               cell [vPos].cell [hPos2].agent [pos2].c [c]) * 0.5;

        a [i].c [c] = u.SeInDiSp  (val, rangeMin [c], rangeMax [c], rangeStep [c]);

        agent [i].c [c] = a [i].c [c];
      }
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método "Revision" da classe "C_AO_TSEA" implementa a etapa de redistribuição das áreas do casco da tartaruga no algoritmo TSEA.

Ele é responsável pelo processo de revisão (atualização) da população de agentes e pela atualização da melhor solução global.

Principais etapas dessa parte do algoritmo:

1. Cálculo da adequação "fitness" de cada agente e determinação da melhor solução "fB".
2. Classificação dos agentes nos clusters verticais "labelClustV" com base na sua adequação.
3. Se for a primeira iteração (revision == false), a clusterização dos agentes é inicializada usando o algoritmo K-Means.
4. Se não for a primeira iteração, o seguinte é executado:

Todos os agentes são reunidos em um único array "data".
Para cada agente na população, seu cluster horizontal "label" é determinado usando o algoritmo K-Nearest Neighbors.
A cada 50 épocas, ocorre a atualização da estrutura "cell", onde os agentes são armazenados, divididos por clusters.

5. Colocação de cada agente na célula correspondente. Se a célula já estiver preenchida, o agente substitui o agente na célula com a menor adequação (ou a maior, se a célula estiver no nível inferior).

A ideia principal dessa etapa é manter a estrutura do casco, onde as melhores soluções estão mais próximas da superfície externa, enquanto as menos bem-sucedidas permanecem no interior. A clusterização dos agentes e a atualização dinâmica da estrutura do casco garantem a flexibilidade e a adaptabilidade do algoritmo.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_TSEA::Revision ()
{
  //получить приспособленность--------------------------------------------------
  int pos = -1;

  for (int i = 0; i < popSize; i++)
  {
    agent [i].f = a [i].f;

    if (a [i].f > fB)
    {
      fB = a [i].f;
      pos = i;
    }

    if (a [i].f < minFval) minFval = a [i].f;
  }

  if (pos != -1) ArrayCopy (cB, a [pos].c, 0, 0, WHOLE_ARRAY);

  stepF = (fB - minFval) / vClusters;

  //Разметка по вертикали дочерней популяции------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    if (agent [i].f == fB) agent [i].labelClustV = vClusters - 1;
    else
    {
      agent [i].labelClustV = int((agent [i].f - minFval) / stepF);
      if (agent [i].labelClustV > vClusters - 1) agent [i].labelClustV = vClusters - 1;
    }
  }

  //----------------------------------------------------------------------------
  if (!revision)
  {
    km.KMeansPlusPlusInit (agent, popSize, clusters);
    km.KMeans             (agent, popSize, clusters);

    revision = true;
  }
  //----------------------------------------------------------------------------
  else
  {
    static S_TSEA_Agent data [];
    ArrayResize (data, 0, 1000);
    int size = 0;

    for (int v = 0; v < vClusters; v++)
    {
      for (int h = 0; h < hClusters; h++)
      {
        for (int c = 0; c < ArraySize (cell [v].cell [h].agent); c++)
        {
          size++;
          ArrayResize (data, size);

          data [size - 1] = cell [v].cell [h].agent [c];
        }
      }
    }

    for (int i = 0; i < popSize; i++)
    {
      agent [i].label = km.KNN (data, agent [i], neighbNumb, hClusters);
    }
    
    if (epochsNow % 50 == 0)
    {
      for (int v = 0; v < vClusters; v++)
      {
        for (int h = 0; h < hClusters; h++)
        {
          ArrayResize (cell [v].cell [h].agent, 0);
        }
      }

      for (int i = 0; i < ArraySize (data); i++)
      {
        if (data [i].f == fB) data [i].labelClustV = vClusters - 1;
        else
        {
          data [i].labelClustV = int((data [i].f - minFval) / stepF);
          if (data [i].labelClustV > vClusters - 1) data [i].labelClustV = vClusters - 1;
        }

        int v = data [i].labelClustV;
        int h = data [i].label;

        int size = ArraySize (cell [v].cell [h].agent) + 1;
        ArrayResize (cell [v].cell [h].agent, size);

        cell [v].cell [h].agent [size - 1] = data [i];
      }
    }
  }

  //Поместить популяцию в панцирь----------------------------------------
  for (int i = 0; i < popSize; i++)
  {
    int v = agent [i].labelClustV;
    int h = agent [i].label;

    int size = ArraySize (cell [v].cell [h].agent);
    int pos    = 0;
    int posMin = 0;
    int posMax = 0;

    if (size >= maxAgentsInCell)
    {
      double minF =  DBL_MAX;
      double maxF = -DBL_MAX;

      for (int c = 0; c < maxAgentsInCell; c++)
      {
        if (cell [v].cell [h].agent [c].f < minF)
        {
          minF = cell [v].cell [h].agent [c].f;
          posMin = c;
        }
        if (cell [v].cell [h].agent [c].f > maxF)
        {
          maxF = cell [v].cell [h].agent [c].f;
          posMax = c;
        }
      }

      if (v == 0)
      {
        if (agent [i].f < minF)
        {
          pos = posMin;
        }
        else
        {
          pos = posMax;
        }
      }
      else  pos = posMin;
    }
    else
    {
      ArrayResize (cell [v].cell [h].agent, size + 1);
      pos = size;
    }

    cell [v].cell [h].agent [pos] = agent [i];
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Resultados dos testes

Exibição dos resultados do algoritmo de evolução do casco da tartaruga TSEA no print:

TSEA|Turtle Shell Evolution Algorithm|100.0|3.0|10.0|5.0|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.811921100517765
25 Hilly's; Func runs: 10000; result: 0.5537631430428238
500 Hilly's; Func runs: 10000; result: 0.2813575513298344
=============================
5 Forest's; Func runs: 10000; result: 0.9564485273109922
25 Forest's; Func runs: 10000; result: 0.481362270824773
500 Forest's; Func runs: 10000; result: 0.181400891410298
=============================
5 Megacity's; Func runs: 10000; result: 0.6676923076923076
25 Megacity's; Func runs: 10000; result: 0.3633846153846153
500 Megacity's; Func runs: 10000; result: 0.11670769230769343
=============================
All score: 4.41404 (49.04%)

O resultado geral em todas as funções de teste é de 4.41404, o que corresponde a 49,04% da solução teoricamente ótima.

A visualização do funcionamento do ambiente de teste demonstra uma boa convergência do algoritmo. Em todas as funções de teste, há uma dispersão das trajetórias no gráfico de convergência, mas, com o aumento dos graus de liberdade, essa dispersão diminui. O uso de clusterização no algoritmo, assim como a manutenção de uma quantidade constante de agentes em cada célula, permite que o algoritmo explore eficientemente as áreas relevantes da função de fitness.

  TSEA na função de teste Hilly.

  TSEA na função de teste Forest.

  TSEA na função de teste Megacity.

Após os testes nas funções de teste, o algoritmo ocupa uma posição respeitável em 6º lugar na parte superior da tabela de classificação final.

№	AO	Description	Hilly			Hilly final	Forest			Forest final	Megacity (discrete)			Megacity final	Final result	% of MAX
			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	BGA	binary genetic algorithm	0,99992	0,99484	0,50483	2,49959	1,00000	0,99975	0,32054	2,32029	0,90667	0,96400	0,23035	2,10102	6,921	76,90
2	(P+O)ES	(P+O) evolution strategies	0,99934	0,91895	0,56297	2,48127	1,00000	0,93522	0,39179	2,32701	0,83167	0,64433	0,21155	1,68755	6,496	72,18
3	SDSm	stochastic diffusion search M	0,93066	0,85445	0,39476	2,17988	0,99983	0,89244	0,19619	2,08846	0,72333	0,61100	0,10670	1,44103	5,709	63,44
4	ESG	evolution of social groups	0,99906	0,79654	0,35056	2,14616	1,00000	0,82863	0,13102	1,95965	0,82333	0,55300	0,04725	1,42358	5,529	61,44
5	SIA	simulated isotropic annealing	0,95784	0,84264	0,41465	2,21513	0,98239	0,79586	0,20507	1,98332	0,68667	0,49300	0,09053	1,27020	5,469	60,76
6	TSEA	turtle shell evolution algorithm	0,96798	0,64480	0,29672	1,90949	0,99449	0,61981	0,22708	1,84139	0,69077	0,42646	0,13598	1,25322	5,004	55,60
7	DE	differential evolution	0,95044	0,61674	0,30308	1,87026	0,95317	0,78896	0,16652	1,90865	0,78667	0,36033	0,02953	1,17653	4,955	55,06
8	BSA	bird swarm algorithm	0,90857	0,73661	0,25767	1,90285	0,90437	0,81619	0,16401	1,88457	0,61692	0,54154	0,10951	1,26797	5,055	56,17
9	HS	harmony search	0,86509	0,68782	0,32527	1,87818	0,99999	0,68002	0,09590	1,77592	0,62000	0,42267	0,05458	1,09725	4,751	52,79
10	SSG	saplings sowing and growing	0,77839	0,64925	0,39543	1,82308	0,85973	0,62467	0,17429	1,65869	0,64667	0,44133	0,10598	1,19398	4,676	51,95
11	(PO)ES	(PO) evolution strategies	0,79025	0,62647	0,42935	1,84606	0,87616	0,60943	0,19591	1,68151	0,59000	0,37933	0,11322	1,08255	4,610	51,22
12	BSO	brain storm optimization	0,91301	0,56222	0,30047	1,77570	0,97162	0,57162	0,23449	1,77772	0,60462	0,27138	0,12011	0,99611	4,550	50,55
13	WOAm	wale optimization algorithm M	0,84521	0,56298	0,26263	1,67081	0,93100	0,52278	0,16365	1,61743	0,66308	0,41138	0,11357	1,18803	4,476	49,74
14	ACOm	ant colony optimization M	0,88190	0,66127	0,30377	1,84693	0,85873	0,58680	0,15051	1,59604	0,59667	0,37333	0,02472	0,99472	4,438	49,31
15	BFO-GA	bacterial foraging optimization - ga	0,89150	0,55111	0,31529	1,75790	0,96982	0,39612	0,06305	1,42899	0,72667	0,27500	0,03525	1,03692	4,224	46,93
16	MEC	mind evolutionary computation	0,69533	0,53376	0,32661	1,55569	0,72464	0,33036	0,07198	1,12698	0,52500	0,22000	0,04198	0,78698	3,470	38,55
17	IWO	invasive weed optimization	0,72679	0,52256	0,33123	1,58058	0,70756	0,33955	0,07484	1,12196	0,42333	0,23067	0,04617	0,70017	3,403	37,81
18	Micro-AIS	micro artificial immune system	0,79547	0,51922	0,30861	1,62330	0,72956	0,36879	0,09398	1,19233	0,37667	0,15867	0,02802	0,56335	3,379	37,54
19	COAm	cuckoo optimization algorithm M	0,75820	0,48652	0,31369	1,55841	0,74054	0,28051	0,05599	1,07704	0,50500	0,17467	0,03380	0,71347	3,349	37,21
20	SDOm	spiral dynamics optimization M	0,74601	0,44623	0,29687	1,48912	0,70204	0,34678	0,10944	1,15826	0,42833	0,16767	0,03663	0,63263	3,280	36,44
21	NMm	Nelder-Mead method M	0,73807	0,50598	0,31342	1,55747	0,63674	0,28302	0,08221	1,00197	0,44667	0,18667	0,04028	0,67362	3,233	35,92
22	FAm	firefly algorithm M	0,58634	0,47228	0,32276	1,38138	0,68467	0,37439	0,10908	1,16814	0,28667	0,16467	0,04722	0,49855	3,048	33,87
23	GSA	gravitational search algorithm	0,64757	0,49197	0,30062	1,44016	0,53962	0,36353	0,09945	1,00260	0,32667	0,12200	0,01917	0,46783	2,911	32,34
24	BFO	bacterial foraging optimization	0,61171	0,43270	0,31318	1,35759	0,54410	0,21511	0,05676	0,81597	0,42167	0,13800	0,03195	0,59162	2,765	30,72
25	ABC	artificial bee colony	0,63377	0,42402	0,30892	1,36671	0,55103	0,21874	0,05623	0,82600	0,34000	0,14200	0,03102	0,51302	2,706	30,06
26	BA	bat algorithm	0,59761	0,45911	0,35242	1,40915	0,40321	0,19313	0,07175	0,66810	0,21000	0,10100	0,03517	0,34617	2,423	26,93
27	SA	simulated annealing	0,55787	0,42177	0,31549	1,29513	0,34998	0,15259	0,05023	0,55280	0,31167	0,10033	0,02883	0,44083	2,289	25,43
28	IWDm	intelligent water drops M	0,54501	0,37897	0,30124	1,22522	0,46104	0,14704	0,04369	0,65177	0,25833	0,09700	0,02308	0,37842	2,255	25,06
29	PSO	particle swarm optimisation	0,59726	0,36923	0,29928	1,26577	0,37237	0,16324	0,07010	0,60572	0,25667	0,08000	0,02157	0,35823	2,230	24,77
30	Boids	boids algorithm	0,43340	0,30581	0,25425	0,99346	0,35718	0,20160	0,15708	0,71586	0,27846	0,14277	0,09834	0,51957	2,229	24,77
31	MA	monkey algorithm	0,59107	0,42681	0,31816	1,33604	0,31138	0,14069	0,06612	0,51819	0,22833	0,08567	0,02790	0,34190	2,196	24,40
32	SFL	shuffled frog-leaping	0,53925	0,35816	0,29809	1,19551	0,37141	0,11427	0,04051	0,52618	0,27167	0,08667	0,02402	0,38235	2,104	23,38
33	FSS	fish school search	0,55669	0,39992	0,31172	1,26833	0,31009	0,11889	0,04569	0,47467	0,21167	0,07633	0,02488	0,31288	2,056	22,84
34	RND	random	0,52033	0,36068	0,30133	1,18234	0,31335	0,11787	0,04354	0,47476	0,25333	0,07933	0,02382	0,35648	2,014	22,37
35	GWO	grey wolf optimizer	0,59169	0,36561	0,29595	1,25326	0,24499	0,09047	0,03612	0,37158	0,27667	0,08567	0,02170	0,38403	2,009	22,32
36	CSS	charged system search	0,44252	0,35454	0,35201	1,14907	0,24140	0,11345	0,06814	0,42299	0,18333	0,06300	0,02322	0,26955	1,842	20,46
37	EM	electroMagnetism-like algorithm	0,46250	0,34594	0,32285	1,13129	0,21245	0,09783	0,10057	0,41085	0,15667	0,06033	0,02712	0,24412	1,786	19,85

Considerações finais

A ideia de um algoritmo de otimização baseado no crescimento do casco da tartaruga mostrou-se bastante interessante, demonstrando que até mesmo animais lentos podem servir de inspiração para soluções "técnicas", nas quais a natureza é uma fonte inesgotável. Com base nos testes realizados com o algoritmo TSEA (Turtle Shell Evolution Algorithm), suas características especiais podem ser destacadas.

A preservação de soluções menos bem-sucedidas é uma característica única do algoritmo. Isso se manifesta no fato de que as opções menos promissoras são mantidas na camada interna do casco. Essa abordagem permite manter a diversidade na população e evitar a convergência precoce para ótimos locais. É importante lembrar que um mínimo local, aparentemente uma solução ruim, pode estar próximo de um ótimo global, portanto, continuar explorando suas proximidades faz sentido. Embora o algoritmo possa explorar essas áreas de forma menos intensa em comparação com áreas mais promissoras, elas ainda permanecem no foco.

A divisão das soluções em clusters verticais, que imitam as camadas do casco, e horizontais, que imitam os padrões característicos na superfície, permite destacar de forma eficaz as áreas do espaço de soluções e explorá-las separadamente. Ao mesmo tempo, o padrão no casco permanece dinâmico e pode mudar e se adaptar à superfície da função de fitness.

O uso da divisão do casco em camadas permite a formação de novas soluções dentro de cada camada. As camadas rígidas superiores não interagem com as camadas macias inferiores, e vice-versa. Isso lembra o processo de crescimento do casco de uma tartaruga viva, mas com a diferença de que uma área rígida da camada inferior pode se mover para as camadas superiores, graças à re-clusterização periódica. Isso pode ser comparado com o processo de renovação do casco, onde um casco antigo é descartado e um novo, mais forte e aprimorado, é formado.

O algoritmo demonstra um bom desempenho em problemas com diferentes dimensões (escalabilidade), o que atesta sua flexibilidade.

Em geral, o TSEA representa uma abordagem interessante, combinando mecanismos de algoritmos evolutivos e de clusterização. No entanto, acredito que o potencial do algoritmo está longe de ser totalmente explorado. Até o momento, foram utilizados apenas alguns métodos de criação de novas soluções, de um vasto repertório discutido em artigos anteriores. O algoritmo continua no meu foco de atenção e está aberto para melhorias futuras. Talvez ele sirva de base para o surgimento de novas modificações, da mesma forma que ocorreu com o PSO e outros algoritmos conhecidos.

Figura 3. Graduação de cores dos algoritmos nos respectivos testes. Os resultados iguais ou superiores a 0,99 estão destacados em branco.

Figura 4. Histograma dos resultados de teste dos algoritmos (em uma escala de 0 a 100, onde quanto maior, melhor,

com 100 sendo o resultado teórico máximo possível; o script para calcular a tabela de classificação está no arquivo).

Prós e contras do algoritmo de evolução do casco da tartaruga (TSEA):

Prós:

1. Boa convergência em diferentes tipos de funções
2. Poucos parâmetros externos
   

Contras:

1. Alta variabilidade de resultados em funções de baixa dimensionalidade
   
2. Alta demanda por recursos computacionais

Um arquivo com as versões mais recentes dos códigos dos algoritmos está anexado ao artigo. O autor do artigo não se responsabiliza pela precisão absoluta na descrição dos algoritmos canônicos, pois muitas modificações foram feitas para melhorar as capacidades de busca. As conclusões e julgamentos apresentados nos artigos são baseados nos resultados dos experimentos realizados.

github: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5

CodeBase: https://www.mql5.com/ru/code/49355