Algoritmos de otimização populacional: Busca em sistema carregado (Charged System Search, CSS)

Conteúdo:

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

1. Introdução

Na física, o espaço ao redor de uma carga elétrica possui uma propriedade conhecida como campo elétrico. Este campo exerce uma força sobre outros objetos carregados eletricamente. O campo elétrico ao redor de uma carga pontual é determinado pela lei de Coulomb. Coulomb confirmou que a força elétrica entre duas pequenas esferas carregadas é inversamente proporcional ao quadrado da distância entre as partículas, direcionada ao longo da linha que as conecta, e proporcional ao produto das cargas de ambas as partículas. Além disso, a magnitude do campo elétrico em um ponto dentro de uma esfera carregada pode ser obtida usando a lei de Gauss, segundo a qual é proporcional à distância entre as partículas. Com esses princípios, o CSS define uma série de soluções possíveis, que são chamadas de partículas carregadas. Cada partícula é tratada como uma esfera carregada (diferente do algoritmo eletromagnético (EM), onde a partícula é um ponto unidimensional) e pode exercer efeitos elétricos sobre outros agentes (partículas carregadas).

Por outro lado, a segunda lei de Newton explica que a aceleração de um objeto é diretamente proporcional à força total que atua sobre esse objeto. Assim, a força elétrica resultante que atua sobre uma partícula leva à sua aceleração. De acordo com a mecânica newtoniana, a posição de uma partícula, considerada como uma massa pontual de tamanho infinitesimal, é completamente conhecida a qualquer momento se sua posição, velocidade e aceleração no espaço forem conhecidas no momento anterior. O CSS utiliza leis de movimento da mecânica newtoniana para determinar a posição das partículas. A aplicação dessas leis na teoria deve garantir um bom equilíbrio entre a pesquisa e a utilização prática do algoritmo.

O algoritmo de busca em sistema carregado (Charged System Search, CSS) foi inicialmente apresentado por A. Kaveh e S. Talatahari em 2010.

A otimização é uma parte importante e integral da solução de problemas de modelagem matemática e aprendizado de máquina. Os algoritmos metaheurísticos são uma classe eficiente e popular de métodos de otimização. Uma metaheurística pode ser entendida como um algoritmo que realiza uma busca estocástica por soluções aproximadamente ótimas de um problema, até que uma condição específica seja atendida ou um número definido de iterações seja alcançado.

Na literatura científica, considera-se que as metaheurísticas combinam os principais métodos heurísticos em esquemas algorítmicos de nível superior, permitindo uma exploração mais eficiente dos espaços de busca e a tomada de decisões. Isso geralmente requer menos trabalho do que desenvolver novas heurísticas especializadas. O desafio é adaptar esquemas metaheurísticos gerais para resolver problemas difíceis de otimização. Além disso, a implementação eficaz da metaheurística pode garantir a obtenção de uma solução quase ideal em um tempo aceitável. As diversas abordagens para entender as metaheurísticas permitem formular algumas propriedades fundamentais que as caracterizam. Nos últimos anos, o uso de métodos metaheurísticos aumentou, e esforços foram feitos para aumentar a potência dos algoritmos e reduzir o tempo de otimização.

2. Descrição do algoritmo

O algoritmo de busca em sistema carregado (CSS) opera com partículas carregadas na forma de esfera, o tamanho mínimo da esfera é determinado por um parâmetro externo (representa uma parte da máxima distância euclidiana possível em todas as coordenadas do espaço de busca), quando as partículas se aproximam a uma distância menor que o raio da esfera, as forças de repulsão atuam sobre as partículas, enquanto a direção das forças entre as partículas é influenciada pela diferença de suas cargas. O algoritmo leva em conta os valores das coordenadas na iteração anterior, o que modela a velocidade das partículas. A aceleração, um componente do movimento das partículas, é influenciada pelas cargas e suas distâncias relativas.

Considerando o exposto, vamos descrever os passos do pseudocódigo do algoritmo:

1. Inicializamos as partículas com uma posição aleatória inicial no espaço de busca, bem como uma posição aleatória no espaço para a iteração anterior (assumimos que a iteração anterior ocorreu).

2. Calculamos o valor da função de adequação (adaptação).

3. Calculamos a próxima posição das partículas usando fórmulas.

4. Determinamos os melhores e piores valores de adaptação entre todas as partículas.

5. Repetimos os passos de nº2 até que a condição de parada seja atendida.

Vamos analisar as fórmulas para calcular o movimento mútuo das partículas. A principal característica de uma partícula carregada é sua carga:

q = (φp - φw) / (φb - φw)

onde:

• q - carga atual da partícula
• φp - valor da função de adaptação da partícula
• φb - melhor valor de adaptação entre todas as partículas
• φw - pior valor de adaptação entre todas as partículas

Para determinar a distância entre as partículas, usaremos a fórmula:

r(i,j) = (|Xi - Xj|) / (|(Xi - Xj) * 0.5 - Xb|)

onde:

• || - distância euclidiana
• r(i,j) - distância entre as partículas i e j
• Xi e Xj - coordenadas correspondentes das partículas i e j
• Xb - coordenada correspondente à melhor posição encontrada em todas as iterações.

Aparentemente, a ideia dos autores era considerar a posição das partículas em relação às melhores coordenadas globais. Talvez essa tenha sido uma boa ideia, mas meus experimentos deram motivos para acreditar que a melhor solução para este algoritmo seria aplicar apenas o cálculo do numerador na fórmula.

Assim como no algoritmo eletromagnético EM, as forças de interação podem ser tanto atrativas quanto repulsivas. Indicaremos o sinal da direção com a variável c. Para levar em conta a direção das forças, usaremos a seguinte expressão condicional:

c = -1, se φi < φj, caso contrário c = 1

onde:

• c - sinal da direção das forças de interação
• φi e φj - valores de adaptação das partículas i e j

O sinal da direção da força pode ser interpretado de modo que a partícula com menor valor de adaptação repele, enquanto a partícula com maior valor atrai.

Como acordamos, ao contrário do algoritmo EM, a partícula é representada por uma esfera cujo raio é maior que 0 (parâmetro externo do algoritmo). Assim, a força que atua sobre uma partícula colinear à coordenada correspondente (em nosso algoritmo, a força total que atua sobre uma partícula é um conjunto de vetores) pode ser expressa pela fórmula:

F = qi * Q * c * (Xj - Xi)

onde:

• F - força exercida sobre a partícula
• qi - partícula para a qual a força está sendo calculada
• Q - componente que leva em conta a posição mútua das duas partículas consideradas, dependendo da penetração de suas esferas umas nas outras, fórmula para Q:

Q = ((qj * r(i,j) * b1) / a^3) + (qj * b2) / r(i,j)^2

onde:

• qj - carga da partícula que atua sobre a partícula considerada
• b1 e b2 para "ligar/desligar" o respectivo termo da expressão, onde b1 = 0 e b2 = 1 se r >= ao raio da partícula, e b1 = 1 e b2 = 0 se menor.

E, finalmente, a nova coordenada de movimento das partículas pode ser calculada pela fórmula:

Xn = X + λ1 * U * V + λ2 * U * coordinatesNumber * (F / qi)

onde:

• Xn - nova coordenada
• λ1 - coeficiente de peso (parâmetro externo), determina o grau de influência do segundo termo, a velocidade
• λ2 - coeficiente de peso (parâmetro externo), determina o grau de influência do terceiro termo, a aceleração
• U - número aleatório no intervalo [0;1]
• V - diferença entre a coordenada na iteração atual e na anterior
• coordinatesNumber - número de coordenadas, este "coeficiente" não está na fórmula original, foi introduzido por mim devido ao fato de que com o aumento da dimensionalidade do espaço de busca, torna-se necessário aumentar o coeficiente λ2 (portanto introduzido para evitar o efeito de "congelamento" das partículas)

Os valores relativos de λ1 e λ2 determinam o equilíbrio entre a diversificação e a intensificação da busca. Aumentar os valores do parâmetro λ1 fortalece a influência da posição anterior da partícula, aumentando as propriedades exploratórias do algoritmo. Valores grandes de λ2 resultam em uma forte influência das forças atrativas e podem causar uma convergência prematura do algoritmo. Por outro lado, valores menores dessa grandeza desaceleram a taxa de convergência do algoritmo, proporcionando uma pesquisa mais ampla da área de busca.

Vamos proceder à análise do código do algoritmo CSS. O agente de busca do algoritmo é uma partícula, que é convenientemente representada pela estrutura S_Particle.

A estrutura da partícula inclui os seguintes campos:

• -c: array de coordenadas da partícula. Este array contém as coordenadas atuais da partícula no espaço.
• -cPrev: array de coordenadas anteriores da partícula. Este array contém as coordenadas anteriores da partícula no espaço.
• -cNew: array de novas coordenadas da partícula. Este array contém as novas coordenadas da partícula, que serão usadas na próxima iteração do algoritmo.
• -q: carga da partícula. Este valor representa a carga atribuída à partícula. A carga pode assumir apenas valores positivos diferentes de zero.
• -f: valor da função de adequação da partícula.

A presença de um array de novas coordenadas na estrutura da partícula e seu carregamento simplificaram o algoritmo devido às suas características, embora esses valores pudessem ser, e logicamente à primeira vista, mantidos como variáveis para uso comum por todas as partículas. 

//——————————————————————————————————————————————————————————————————————————————
struct S_Particle
{
  double c     [];  //coordinates
  double cPrev [];  //coordinates
  double cNew  [];  //coordinates
  double q;         //particle charge
  double f;         //fitness
};
//——————————————————————————————————————————————————————————————————————————————

Vamos declarar a classe C_AO_CSS, que inclui:

Propriedades da classe:

• - p: array de partículas
• - rangeMax: array com os valores máximos de alcance para cada coordenada
• - rangeMin: array com os valores mínimos de alcance para cada coordenada
• - rangeStep: array com os tamanhos dos passos de busca para cada coordenada
• - cB: array com as melhores coordenadas encontradas
• - fB: valor da função de adaptação para as melhores coordenadas
• - fW: valor da função de adaptação para as piores coordenadas

Métodos da classe:

• - Init: inicializa os parâmetros do algoritmo (número de coordenadas, número de partículas, tamanho do raio, coeficientes de velocidade e aceleração)
• - Moving: realiza o movimento das partículas
• - Revision: atualiza as melhores coordenadas

Propriedades privadas da classe:

• - coordinatesNumber: número de coordenadas
• - particlesNumber: número de partículas
• - radius: tamanho do raio
• - speedCo: coeficiente de velocidade
• - accelCo: coeficiente de aceleração
• - F: vetor de forças
• - revision: flag que indica a necessidade de revisão

Métodos privados da classe:

• - SeInDiSp: calcula um novo valor de coordenada dentro de um alcance definido com um passo específico
• - RNDfromCI: gera um número aleatório dentro de um intervalo especificado

//——————————————————————————————————————————————————————————————————————————————
class C_AO_CSS
{
  //----------------------------------------------------------------------------
  public: S_Particle p     []; //particles
  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search
  public: double cB        []; //best coordinates
  public: double fB;           //FF of the best coordinates
  public: double fW;           //FF of the worst coordinates

  public: void Init (const int    coordinatesNumberP, //coordinates number
                     const int    particlesNumberP,   //particles number
                     const double radiusSizeP,        //radius size
                     const double speedCoP,           //speed coefficient
                     const double accelCoP);          //acceleration coefficient

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

  //----------------------------------------------------------------------------
  private: int    coordinatesNumber; //coordinates number
  private: int    particlesNumber;   //particles number
  private: double radius;            //radius size
  private: double speedCo;           //speed coefficient
  private: double accelCo;           //acceleration coefficient
  private: double F       [];        //force vector
  private: bool   revision;

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

O método C_AO_CSS inicializa os parâmetros do objeto da classe. Ele aceita como argumentos os valores do número de coordenadas, número de partículas, tamanho do raio, coeficiente de velocidade e coeficiente de aceleração.

Dentro do método, o gerador de números aleatórios é reiniciado, e os valores iniciais para as variáveis fB e revision são definindos. Em seguida, os valores dos argumentos são atribuídos às variáveis correspondentes do objeto.
Depois, os tamanhos dos arrays rangeMax, rangeMin, rangeStep, F, p e cB são ajustados de acordo com o número de coordenadas e partículas.
Então, em um laço, os tamanhos dos arrays para cada partícula são ajustados e o valor inicial da variável f é definido para cada partícula.
No final do método, o tamanho do array cB é ajustado de acordo com o número de coordenadas.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_CSS::Init (const int    coordinatesNumberP, //coordinates number
                     const int    particlesNumberP,   //particles number
                     const double radiusSizeP,        //radius size
                     const double speedCoP,           //speed coefficient
                     const double accelCoP)           //acceleration coefficient
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coordinatesNumber = coordinatesNumberP;
  particlesNumber   = particlesNumberP;
  radius            = radiusSizeP;
  speedCo           = speedCoP;
  accelCo           = accelCoP;

  ArrayResize (rangeMax,  coordinatesNumber);
  ArrayResize (rangeMin,  coordinatesNumber);
  ArrayResize (rangeStep, coordinatesNumber);
  ArrayResize (F,         coordinatesNumber);

  ArrayResize (p,  particlesNumber);

  for (int i = 0; i < particlesNumber; i++)
  {
    ArrayResize (p [i].c,     coordinatesNumber);
    ArrayResize (p [i].cPrev, coordinatesNumber);
    ArrayResize (p [i].cNew,  coordinatesNumber);
    p [i].f  = -DBL_MAX;
  }

  ArrayResize (cB, coordinatesNumber);
}
//——————————————————————————————————————————————————————————————————————————————

A lógica principal do movimento das partículas (agentes de busca) é implementada no método Moving().

Na primeira iteração, é necessário realizar a inicialização dos valores iniciais das coordenadas das partículas com um número aleatório no intervalo de rangeMin a rangeMax, e o valor de adaptação das partículas é definido como `-DBL_MAX`.

O parâmetro externo do algoritmo RadiusSize_P define o tamanho das partículas em partes da distância euclidiana máxima possível por todas as coordenadas, que é a raiz quadrada da soma dos quadrados das diferenças entre o valor máximo e mínimo permitido para cada coordenada.
No final do código, a variável `revision` é definida como `true`.

//----------------------------------------------------------------------------
if (!revision)
{
  fB = -DBL_MAX;

  for (int obj = 0; obj < particlesNumber; obj++)
  {
    for (int c = 0; c < coordinatesNumber; c++)
    {
      p [obj].c     [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
      p [obj].cPrev [c] = RNDfromCI (rangeMin [c], rangeMax [c]);

      p [obj].c     [c] = SeInDiSp (p [obj].c     [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      p [obj].cPrev [c] = SeInDiSp (p [obj].cPrev [c], rangeMin [c], rangeMax [c], rangeStep [c]);

      p [obj].f         = -DBL_MAX;
    }
  }

  double r = 0.0;
  double t = 0.0;

  for (int c = 0; c < coordinatesNumber; c++)
  {
    t = rangeMax [c] - rangeMin [c];
    r += t * t;
  }

  radius *= sqrt (r);
  revision = true;
}

A parte restante do código do método Moving() é executada na segunda e subsequentes iterações e é responsável pelo movimento das partículas no espaço de busca.

Primeiro, a diferença entre os valores das funções de adaptação fB e fW (para as melhores coordenadas encontradas em todas as iterações e as piores coordenadas entre as partículas na iteração atual) é calculada e armazenada na variável difference. Se a difference for igual a 0.0, então ela é definida como 1.0.

Em seguida, é executado um laço onde é calculado o novo valor para cada partícula. Para cada partícula i, calcula-se um novo valor de carga q.

Depois, são declaradas e inicializadas as variáveis summ1, summ2, q, e, c, b1, b2, X, Q, U, V, t1, t2 para uso nas fórmulas descritas acima.

Em um laço para cada partícula, é realizado o cálculo da força total F, que atua por parte de todas as outras partículas na população. Para cada partícula i, ocorre um laço onde as somas summ1 e summ2 são calculadas. Em seguida, calcula-se a distância r entre as partículas i e j. Se r for igual a 0.0, é atribuído o valor 0.01 para evitar a divisão por zero. Depois, os valores de b1 e b2 são calculados dependendo do valor de r e do radius. Em seguida, calcula-se o valor da direção da força c, dependendo dos valores de adaptação das duas partículas consideradas. A seguir, calcula-se o valor de Q. Então, para cada coordenada k, o valor da força F[k] é calculado.

Tendo os valores do vetor de forças que atuam sobre a partícula, podemos calcular os valores das novas coordenadas para o seu movimento. Depois, ocorre um laço em que os valores das coordenadas anteriores e atuais da partícula i são atualizados.

No código, as partes das fórmulas originais são mantidas como elementos comentados para mostrar como era nos autores do CSS.

double difference = fB - fW;
if (difference == 0.0) difference = 1.0;

for (int i = 0; i < particlesNumber; i++)
{
  p [i].q = ((p [i].f - fW) / difference) + 0.1;
}

double summ1 = 0.0;
double summ2 = 0.0;
double q     = 0.1;
double e     = 0.001;
double c     = 0.0;
double b1    = 0.0;
double b2    = 0.0;
double X     = 0.0;
double Q     = 0.0;
double U     = 0.0;
double V     = 0.0;
double t1    = 0.0;
double t2    = 0.0;

for (int i = 0; i < particlesNumber && !IsStopped (); i++)
{
  ArrayInitialize (F, 0.0);

for (int j = 0; j < particlesNumber && !IsStopped (); j++)
{
  if (i == j) continue;

  summ1 = 0.0;
  summ2 = 0.0;

  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    t1 = p [i].c [k] - p [j].c [k];
    summ1 += t1 * t1;

    //t2 = t1 * 0.5 - cB [k];
    //summ2 += t2 * t2;
  }

  //r = sqrt (summ1) / (sqrt (summ2) + e);
  r = sqrt (summ1);
        
  if (r == 0.0) r = 0.01;

  if (r >= radius)
  {
    b1 = 0.0;
    b2 = 1.0;
  }
  else
  {
    b1 = 1.0;
    b2 = 0.0;
  }

  c = p [i].f < p [j].f ? -1.0 : 1.0;

  q = p [j].q;

  Q = ((q * r * b1 / (radius * radius * radius)) + (q * b2 / (r * r))) * c;

  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    F [k] += /*p [i].q */ Q * (p [j].c [k] - p [i].c [k]);
  }
}

  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    V = p [i].c [k] - p [i].cPrev [k];
    U = RNDfromCI (0.0, 1.0);

    X = p [i].c [k] + speedCo * U * V + accelCo * U * coordinatesNumber * (F [k] / p [i].q);
        
    p [i].cNew [k] = SeInDiSp (X, rangeMin [k], rangeMax [k], rangeStep [k]);
  }
}

for (int i = 0; i < particlesNumber && !IsStopped (); i++)
{
  for (int k = 0; k < coordinatesNumber && !IsStopped (); k++)
  {
    p [i].cPrev [k] = p [i].c [k];
    p [i].c [k] = p [i].cNew [k];
  }
}

E, finalmente, segue o método Revision().
No início do método, a variável fW é atribuída ao valor máximo do tipo double (DBL_MAX), para que possamos posteriormente determinar a pior partícula com o menor valor de função de adaptação.
Então, ocorre um laço percorrendo todas as partículas do sistema. Para cada partícula, são executadas as seguintes ações:
- Se o valor de f da partícula atual for maior que o valor de fB (melhor função de adaptação entre todas as partículas), o valor de fB é atualizado com o valor de f da partícula atual, e o array cB (melhor posição) é copiado da posição da partícula atual.
- Se o valor de f da partícula atual for menor que o valor de fW (menor função de adaptação entre todas as partículas), então o valor de fW é atualizado com o valor de f da partícula atual.

Assim, este código encontra as melhores e piores funções de adaptação entre todas as partículas e atualiza os valores correspondentes.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_CSS::Revision ()
{
  fW  = DBL_MAX;

  for (int i = 0; i < particlesNumber; i++)
  {
    if (p [i].f > fB)
    {
      fB = p [i].f;
      ArrayCopy (cB, p [i].c, 0, 0, WHOLE_ARRAY);
    }

    if (p [i].f < fW)
    {
      fW = p [i].f;
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

3. Resultados dos testes

Saída obtida usando o CSS em uma bancada de teste:

C_AO_CSS:50;0.1;0.7;0.01
=============================
5 Rastrigin's; Func runs 10000 result: 70.43726076935499
Score: 0.87276
25 Rastrigin's; Func runs 10000 result: 68.88569793414477
Score: 0.85353
500 Rastrigin's; Func runs 10000 result: 66.01225385184436
Score: 0.81793
=============================
5 Forest's; Func runs 10000 result: 0.4891262437640296
Score: 0.27667
25 Forest's; Func runs 10000 result: 0.1494549763925046
Score: 0.08454
500 Forest's; Func runs 10000 result: 0.07829232143185726
Score: 0.04429
=============================
5 Megacity's; Func runs 10000 result: 2.04
Score: 0.17000
25 Megacity's; Func runs 10000 result: 0.744
Score: 0.06200
500 Megacity's; Func runs 10000 result: 0.26880000000000004
Score: 0.02240
=============================
All score: 3.20412

A impressão dos resultados do trabalho do algoritmo indica um baixo desempenho geral, chamando a atenção para o fato de que, na função Rastrigin para 10, 50 e 1000 variáveis, os resultados da função de adaptação não diferem muito, vamos tentar entender o que isso significa.

A visualização da função de teste Rastrigin mostra claramente uma divisão distinta da população de partículas em significativos extremos locais, indicando um bom trabalho nas áreas locais, mas tal comportamento não é observado nas funções Forest e Megacity, onde a população se comporta como uma nuvem amorfa. Os longos trechos horizontais no gráfico de convergência indicam uma tendência do algoritmo a ficar preso em extremos locais, embora essa enorme desvantagem do algoritmo seja um pouco compensada pela excelente escalabilidade na função suave Rastrigin.

  CSS na função de teste Rastrigin.

  CSS na função de teste Forest.

  CSS na função de teste Megacity.

O teste do algoritmo CSS identificou um novo líder para a otimização de funções suaves, com o líder anterior na função Rastrigin sendo também um algoritmo inspirado na natureza inanimada, a busca eletromagnética (EM). Desta vez, o novo recorde supera o anterior por quase 10%. Infelizmente, na função Forest, com um extremo global agudo, e na função discreta Megacity, o algoritmo apresenta alguns dos piores resultados. Graças ao impressionante resultado na Rastrigin com 1000 variáveis, o algoritmo conseguiu alcançar o 13º lugar entre 20 pelo total de indicadores. No número de 10000 lançamentos estipulado pelo regulamento de teste, o algoritmo CSS não conseguiu se aproximar do extremo global mais do que 90% (veja os resultados da bancada de teste mencionada acima).   

№	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,58904	2,58641	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,51630	2,46944	0,72740	0,69680	1,00000	2,42421	0,69612	0,65918	1,00000	2,35531	87,506
3	HS	harmony search	0,99676	0,90817	0,44686	2,35179	1,00000	0,72930	0,44806	2,17736	0,91159	0,76578	0,41537	2,09274	79,501
4	ACOm	ant colony optimization M	0,34611	0,17142	0,15808	0,67562	0,86888	0,73719	0,77362	2,37968	0,91159	0,68163	0,05606	1,64929	55,026
5	IWO	invasive weed optimization	0,95828	0,63939	0,27647	1,87415	0,70773	0,34168	0,31773	1,36714	0,72927	0,32539	0,33289	1,38756	54,060
6	MEC	mind evolutionary computation	0,99270	0,48648	0,21148	1,69066	0,60762	0,29973	0,25459	1,16194	0,85083	0,31978	0,26170	1,43231	49,669
7	COAm	cuckoo optimization algorithm M	0,92400	0,44601	0,24120	1,61121	0,58378	0,25090	0,16526	0,99994	0,66298	0,25666	0,17083	1,09047	42,223
8	FAm	firefly algorithm M	0,59825	0,32387	0,15893	1,08106	0,51073	0,31182	0,49790	1,32045	0,31491	0,21880	0,35258	0,88629	36,941
9	ABC	artificial bee colony	0,78170	0,31182	0,19313	1,28664	0,53837	0,15816	0,13344	0,82998	0,51381	0,20758	0,13926	0,86064	32,977
10	BA	bat algorithm	0,40526	0,60773	0,78330	1,79629	0,20841	0,12884	0,25989	0,59714	0,27073	0,08135	0,17371	0,52579	32,236
11	GSA	gravitational search algorithm	0,70167	0,43098	0,00000	1,13265	0,31660	0,26845	0,33204	0,91710	0,54144	0,27208	0,00000	0,81352	31,522
12	BFO	bacterial foraging optimization	0,67203	0,29511	0,10957	1,07671	0,39702	0,19626	0,20652	0,79980	0,47514	0,25807	0,18932	0,92253	30,702
13	CSS	charged system search	0,56605	0,70573	1,00000	2,27178	0,14081	0,01980	0,16282	0,32343	0,09393	0,00000	0,03481	0,12874	29,743
14	EM	electroMagnetism-like algorithm	0,12235	0,44109	0,92752	1,49096	0,00000	0,02578	0,34880	0,37458	0,00000	0,00562	0,10924	0,11486	20,252
15	SFL	shuffled frog-leaping	0,40072	0,22627	0,24624	0,87323	0,20153	0,03057	0,02652	0,25862	0,24862	0,04769	0,06639	0,36270	14,050
16	MA	monkey algorithm	0,33192	0,31883	0,13582	0,78658	0,10012	0,05817	0,08932	0,24762	0,19889	0,03787	0,10720	0,34396	12,564
17	FSS	fish school search	0,46812	0,24149	0,10483	0,81445	0,12840	0,03696	0,06516	0,23052	0,15471	0,04208	0,08283	0,27961	11,880
18	PSO	particle swarm optimization	0,20449	0,07816	0,06641	0,34906	0,18895	0,07730	0,21738	0,48363	0,21547	0,05049	0,01957	0,28553	9,246
19	RND	random	0,16826	0,09287	0,07438	0,33551	0,13496	0,03546	0,04715	0,21757	0,15471	0,03507	0,04922	0,23900	5,083
20	GWO	grey wolf optimizer	0,00000	0,00000	0,02093	0,02093	0,06570	0,00000	0,00000	0,06570	0,29834	0,06170	0,02557	0,38561	1,000

Considerações finais

Tive que realizar muitos experimentos e alterações no código para fazer as partículas se moverem pelo campo sem "colarem" e "congelarem", os autores do algoritmo não levaram em conta a influência do número de parâmetros otimizados na qualidade da otimização (com o aumento da dimensão do problema, a convergência piorava desproporcionalmente rápido), a adição do número de coordenadas na fórmula permitiu fortalecer a influência da aceleração e melhorar as características do CSS (sem essas mudanças, o algoritmo mostrava resultados muito ruins). As leis de movimento das partículas incorporadas são muito caprichosas para quaisquer mudanças em propósitos de pesquisa, dificultando assim tentativas de melhorar os indicadores deste interessante algoritmo de otimização.

O algoritmo de busca por sistema de cargas é um método eficaz de otimização de funções suaves, que usa um enxame de partículas carregadas interligadas por forças de Coulomb. Deve-se considerar, ao usar este interessante algoritmo, sua baixa adequação para tarefas com um campo de busca discreto, mas para funções suaves com muitas variáveis, é o melhor algoritmo de otimização dentre os anteriormente considerados. O CSS pode ser usado em todas as áreas de otimização com um grande número de variáveis, não necessitando nem de informações sobre o gradiente nem de continuidade do espaço de busca.

Para visualizar melhor as vantagens e desvantagens de cada algoritmo em comparação entre si, a tabela acima pode ser apresentada usando uma escala de cores na Figura 1. A gradação de cores na tabela possibilita uma representação mais clara da aplicabilidade de cada algoritmo, dependendo da tarefa de otimização específica. Assim, podemos ver que ainda não foi encontrado um algoritmo absolutamente universal para a melhor solução de todos os problemas no momento (talvez, em pesquisas futuras, possamos encontrar tal algoritmo).

Por exemplo, se considerarmos o algoritmo na primeira linha do ranking, o SDS, ele não é o melhor em tarefas de teste individuais (funções suaves com muitas variáveis são medianas para ele na tabela). Se tomarmos o algoritmo ACOm, seus resultados individuais estão muito abaixo da média na tabela (surpreendentemente ruim em resolver funções suaves), mas lida muito bem com Forest e a discreta Megacity (foi originalmente projetado para resolver problemas discretos, como o problema do caixeiro-viajante), embora sua escalabilidade deixe muito a desejar.

O último algoritmo apresentado, o CSS, é um exemplo claro de que vemos seu ponto mais forte na função Rastrigin com 1000 variáveis (pode ser uma boa escolha para treinar redes neurais com muitos parâmetros), ou seja, o melhor resultado entre todos os algoritmos de otimização considerados anteriormente, embora nos resultados totais ele não pareça o melhor na tabela, por isso, é muito importante a escolha correta do algoritmo dependendo das especificidades da tarefa.

Testes em larga escala de algoritmos de otimização com as mais variadas estratégias de busca revelaram um fato inesperado, isto é, a estratégia pode acabar sendo pior do que simplesmente aplicar uma busca aleatória com seleção do melhor resultado, RND ocupa o penúltimo lugar em vez do último esperado, GWO ficou pior que a busca aleatória, exceto na discreta Megacity com 10 parâmetros.

Figura 1. Gradação de cores dos algoritmos nos testes correspondentes.

Histograma dos resultados dos testes dos algoritmos na figura 2 (na escala de 0 a 100, quanto maior, melhor, no arquivo o script para calcular a tabela de classificação de acordo com o método nesta artigo):

Figura 2. Histograma dos resultados finais dos testes dos algoritmos.

Prós e contras do algoritmo de busca por sistema de cargas (CSS):

Prós:
1. Alta escalabilidade em funções suaves.
2. Pequena quantidade de parâmetros externos.

Contras:
1. Resultados não tão altos em funções discretas.
2. Baixa convergência.
3. Tendência a ficar preso em extremos locais.

Cada artigo tem um arquivo anexo com versões atualizadas dos códigos dos algoritmos descritos em artigos anteriores. O autor do artigo não assume responsabilidade pela precisão absoluta na descrição dos algoritmos canônicos, muitos dos quais foram modificados para melhorar as capacidades de busca. As conclusões e opiniões apresentadas nos artigos são baseadas nos resultados dos experimentos realizados.