Algoritmos de otimização populacional: simulação de têmpera (Simulated Annealing, SA). Parte I

Conteúdo:

1. Introdução
2. Descrição do Algoritmo
3. Resultados dos Testes

1. Introdução

O algoritmo de otimização por simulação de têmpera surgiu em 1983, graças aos estudos de Scott Kirkpatrick, George Gelatt e Mario Vecchi. Eles exploraram como líquidos e sólidos se comportam sob altas temperaturas, notando que os metais, ao se liquefazerem, permitem que as partículas se espalhem aleatoriamente. Sob condições ideais de alta temperatura inicial e um resfriamento prolongado, o material atinge um estado de energia mínima. Caso contrário, ele permanece num estado metaestável, com energia mais alta, fenômeno conhecido como têmpera, que envolve o resfriamento rápido do material, resultando em uma estrutura atômica anisotrópica e variável dentro do cristal.

Diante dessa observação, surgiu a ideia de aplicar esse processo gradual de resfriamento para desenvolver um algoritmo que conseguisse identificar soluções ótimas em problemas complexos. Assim, além de inspirar novos métodos em otimização física, o algoritmo começou a ser utilizado para solucionar desafios de otimização combinatória.

A inspiração por trás do algoritmo de simulação de têmpera vem de um paralelo matemático com o processo de têmpera de metais. Durante a têmpera, para uma distribuição homogênea de energia interna, o metal é aquecido até altas temperaturas e depois resfriado de maneira controlada.Isso permite que as moléculas metálicas se reorganizem em uma configuração mais estável, reduzindo tensões internas e corrigindo defeitos nos cristais. Além disso, o termo "têmpera" relaciona-se à energia livre termodinâmica do material, que varia de acordo com seu estado físico.

No contexto do algoritmo de otimização de simulação de têmpera, adota-se um procedimento similar. O algoritmo realiza etapas análogas ao aquecimento e ao resfriamento do metal, iniciando com uma solução inicial que pode ser aleatória ou baseada em dados de iterações anteriores. Seguidamente, o algoritmo executa modificações no estado dessa solução, através de mudanças que podem ser aleatórias ou planejadas, para alcançar uma nova configuração, mesmo que esta seja inicialmente menos favorável. A decisão de aceitar estados piores é controlada por uma função de "resfriamento", que diminui gradualmente a probabilidade de aceitar soluções inferiores, possibilitando assim que o algoritmo explore além dos ótimos locais e encontre soluções superiores em outras regiões do espaço de busca.

O SA se baseia em três conceitos fundamentais:

• Aplicação de aleatoriedade: O algoritmo utiliza operações aleatórias para alterar o estado da solução e escolher o próximo estado. Isso permite explorar diferentes áreas do espaço de busca e evitar ficar preso em ótimos locais.

• Toma de piores decisões: O SA é um dos poucos algoritmos que prefere piores decisões com certa probabilidade a melhores decisões.

• Redução gradual da probabilidade de tomar piores decisões: O algoritmo utiliza um processo de "resfriamento", que com o tempo reduz a probabilidade de aceitar piores decisões. Isso permite explorar o espaço de busca mais amplamente no início e, em seguida, focar em melhorar a solução, equilibrando a exploração e o aproveitamento do espaço de busca.

O algoritmo de otimização de simulação de têmpera é um dos métodos aplicados em metaheurística, que descreve uma classe de algoritmos para resolver problemas complexos de otimização. Eles são baseados em métodos heurísticos que permitem buscar soluções aproximadas no espaço de busca, sem a necessidade de uma iteração completa de todas as possibilidades. A aleatoriedade é um dos elementos-chave das metaheurísticas, que permite descobrir novas e promissoras regiões de soluções. O algoritmo pertence ao grupo de algoritmos chamados "métodos de otimização estocástica".

O algoritmo SA tem desvantagens, sobre as quais falaremos mais adiante. O SA deu a base para o desenvolvimento de outros algoritmos, como "Simulação de têmpera adaptativa, ASA" e "Normalização quântica, QN" (também chamada de "Têmpera quântica, QA").

2. Descrição do Algoritmo

A versão inicial do algoritmo de simulação de têmpera apresentada pelos autores é extremamente simples de entender, embora não seja fácil entender como o algoritmo opera sem auxílio visual dos gráficos que mostram as variações de temperatura e o gráfico de probabilidade de decisão do pior caso.

Vamos entender isso passo a passo. O algoritmo começa com uma temperatura inicial elevada (um parâmetro externo), que simula o aquecimento de um material em metalurgia. Neste estado, a alta temperatura indica uma energia molecular elevada, permitindo transições de um estado energético para outro, seja para um estado de maior ou menor energia. Este processo é análogo ao movimento de alta energia observado em metais, onde o sistema pode, probabilisticamente, fazer escolhas subótimas.

Imagine um esquiador descendo de um pico montanhoso até uma planície que ele presume ser a base da montanha. Para confirmar se sua avaliação está correta, ele pode precisar piorar temporariamente sua posição, subindo até um ponto mais alto, o que facilitaria uma descida mais rápida posteriormente. Essa estratégia de aceitar soluções piores temporariamente é decisivo para escapar de armadilhas locais. Nesse contexto, foi desenvolvido o algoritmo de simulação de têmpera quântico, que incorpora efeitos quânticos como estar em dois lugares ao mesmo tempo, possibilitando o salto sobre "muros" através de tunelamento, apesar de tentar mitigar alguns problemas introduzidos pelo recozimento quântico, especialmente a seleção da intensidade da transição quântica.

Para representar esse processo, são utilizadas várias equações simples. A fórmula para calcular a energia é:

E = f (x)

Ou seja, E representa o valor da função de adaptação para o estado atual do agente.

A fórmula para cálculo da mudança de energia é:

ΔE = E_new - E_old

onde:

• ΔE - mudança de energia ao transitar do estado atual para um novo estado (diferença dos valores da função de adaptação em duas iterações consecutivas)
  
• E_new - valor de energia para o novo estado
• E_old - valor de energia para o estado anterior

Fórmula para cálculo da probabilidade de aceitação de uma pior decisão:

P = exp(-ΔE / T)

onde:

• P - probabilidade de aceitação de uma pior decisão
• T - temperatura atual

No gráfico apresentado abaixo, que ilustra a relação da probabilidade P com o aumento de ΔE, percebe-se que um ΔE maior resulta em uma probabilidade menor. Isso indica que, com a diminuição da temperatura, as transições para estados de energia mais alta se tornam menos prováveis muito mais rapidamente do que transições com menores variações energéticas. Assim, o algoritmo passa a "arriscar" menos ao tentar escapar de uma "armadilha", optando por melhorias incrementais na solução. A relação entre as probabilidades é detalhada na Figura 1, onde é usada uma redução linear da temperatura para simplificação, embora na prática o algoritmo utilize uma variação de temperatura não linear.

Figura 1. Gráfico das probabilidades de decisão dependendo da mudança de energia para o pior com redução linear da temperatura.

A fórmula para atualizar a temperatura é:

Tnew = α * Tprev

onde:

• α - coeficiente de resfriamento, geralmente α está no intervalo de 0.8 a 0.99
• Tnew - nova temperatura
• Tprev - temperatura anterior
  

O gráfico da mudança de temperatura a cada iteração com coeficientes α = 0.99, 0.8, 0.5 e 0.1 com uma temperatura inicial de T = 500 é mostrado na Figura 2. A temperatura diminui gradualmente, o que corresponde ao resfriamento do material. A redução da temperatura a cada iteração leva à redução da probabilidade de aceitar piores decisões, o que corresponde à diminuição da capacidade das moléculas de mudarem seu estado energético à medida que a temperatura diminui.

Figura 2. Gráfico da mudança de temperatura com coeficientes α = 0.99, 0.8, 0.5 e 0.1.

Fórmula para geração de um novo estado do sistema:

x_new = GenerateNeighbor (x)

onde:

• x_new - novo estado, gerado com base no estado atual x
  
• GenerateNeighbor (x) - função que gera um novo estado através de alterações aleatórias com distribuição uniforme no estado atual
  

Agora, conhecendo todas as bases teóricas do algoritmo de simulação de têmpera, não teremos dificuldades em escrever o código. O movimento das moléculas, que alteram seu estado energético e que são os agentes, pode ser representado na forma de uma estrutura, S_Agent, que contém informações sobre o agente na tarefa de otimização. Descrição dos campos e métodos da estrutura:

• Init (int coords): método que inicializa o agente e aloca memória para os arrays "c" e "cPrev" de tamanho "coords". Ele também define os valores iniciais de "f" e "fPrev" como "-DBL_MAX" (negativo infinito).
• c []: array "c" representa as coordenadas do agente no espaço de otimização.
  
• cPrev []: array "cPrev" representa as coordenadas anteriores do agente.
  
• f: representa o valor da função de adaptação para as coordenadas atuais do agente.
  
• fPrev: representa o valor anterior da função de adaptação do agente.
  

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

  double c     []; //coordinates
  double cPrev []; //previous coordinates
  double f;        //fitness
  double fPrev;    //previous fitness
};
//————————————————————————————————————————

Descreveremos a classe do algoritmo SA e a chamaremos de C_AO_SA. Ela será muito simples, pois não contém nada incomum que não tenhamos usado anteriormente, exceto por variáveis térmicas específicas e constantes.

Campos e métodos da classe:

• cB []: array das melhores coordenadas encontradas pelo algoritmo de otimização até o momento da iteração atual.
  
• fB: valor da função de adaptação para as melhores coordenadas.
  
• a []: array que representa os agentes, é usado para armazenar informações sobre cada agente na tarefa de otimização, cada elemento do array é uma instância da estrutura S_Agent.
• rangeMax []: array de valores máximos do intervalo de busca para cada coordenada e é usado para definir o limite superior de busca para cada coordenada do agente.
• rangeMin []: array de valores mínimos do intervalo de busca para cada coordenada e é usado para definir o limite inferior de busca para cada coordenada do agente.
• rangeStep []: array que representa os passos de busca para cada coordenada.
• Init (const int coordsP, const int popSizeP, const double tP, const double aP, const double dP): método que inicializa o algoritmo de otimização, recebe parâmetros: número de coordenadas "coordsP", tamanho da população "popSizeP", temperatura inicial "tP", coeficiente de redução de temperatura "aP" e coeficiente de difusão "dP", o método realiza a inicialização dos campos da classe e dos agentes.
• Moving (): método que executa o movimento dos agentes no processo de otimização e é usado pelo algoritmo para determinar novas coordenadas dos agentes.
• Revision (): método que realiza a revisão e atualização das melhores coordenadas e função de adaptação com base nos valores atuais dos agentes.
• SeInDiSp (double In, double InMin, double InMax, double Step): método privado usado para normalizar o valor "In" no intervalo de "InMin" a "InMax" com o passo "Step".
• RNDfromCI (double min, double max): método privado usado para gerar um número aleatório no intervalo especificado de "min" a "max".

É importante destacar que, na formulação original do SA, o coeficiente de difusão dP não é contemplado. Os criadores pretendiam que cada nova atualização do estado do sistema resultasse em uma realocação aleatória das posições dos agentes, oscilando entre os valores "min" e "max" de cada coordenada. Isso simularia o movimento errático das moléculas dentro de um metal durante o processo de têmpera. No entanto, através de meus experimentos, observei uma melhora nos resultados quando o movimento das moléculas é confinado a uma faixa mais restrita, uma fração do intervalo total. O propósito deste parâmetro do coeficiente de difusão é justamente esse: delimitar a extensão na qual as moléculas podem se misturar.

Para obter resultados equivalentes ao SA original, basta definir este parâmetro como 1 (padrão 0.2).

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

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

  public: void Init (const int    coordsP,      //coordinates number
                     const int    popSizeP,     //population size
                     const double tP,           //temperature
                     const double aP,           //temperature reduction coefficient
                     const double dP);          //diffusion coefficient


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

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

  private: double T;
  private: double α;
  private: double d;

  private: bool   revision;

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

A função "Init" servirá como método de inicialização, realizando a inicialização de todos os campos da classe e alocando os tamanhos necessários para os arrays utilizados no algoritmo de otimização.

//————————————————————————————————————————
void C_AO_SA::Init (const int    coordsP,      //coordinates number
                    const int    popSizeP,     //population size
                    const double tP,           //temperature
                    const double aP,           //temperature reduction coefficient
                    const double dP)           //diffusion coefficient
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords     = coordsP;
  popSize    = popSizeP;
  T          = tP;
  α          = aP;
  d          = dP;

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

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

Para mover os agentes no espaço de busca, escreveremos o método "Moving". 
Na primeira iteração, quando o algoritmo é iniciado, a variável-flag "revision" é igual a "false", sendo necessário inicializar os agentes da população com valores iniciais dentro do intervalo [min;max] com uma distribuição uniforme. Os valores das coordenadas dos agentes são normalizados pela função SeInDiS, para manter o passo de movimento requerido. Em seguida, a flag "revision" é definida como "true", para indicar que na próxima iteração será necessário aplicar os operadores do algoritmo de simulação de têmpera.

Na segunda e subsequentes iterações, se fosse o SA original, continuaríamos a fazer o que foi feito na primeira iteração, ou seja, continuaríamos a gerar números aleatórios no intervalo especificado com uma distribuição uniforme. Na nossa versão ligeiramente modificada, procederemos de forma semelhante, mas ajustando o intervalo de valores, limitando assim a área de interação difusiva das moléculas no metal, movendo-se a partir do local onde a molécula estava na iteração anterior. Os valores das coordenadas dos agentes são normalizados pela função SeInDiS, para manter o passo de movimento requerido.

//————————————————————————————————————————
void C_AO_SA::Moving ()
{
  //----------------------------------------------------------------------------
  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  double rnd = 0.0;

  for (int i = 0; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      rnd = RNDfromCI (-0.1, 0.1);
      a [i].c [c] = a [i].cPrev [c] + rnd * (rangeMax [c] - rangeMin [c]) * d;
      a [i].c [c] = SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//————————————————————————————————————————

Se no método "Moving" realizamos a geração de novos estados do sistema, ou seja, movimentamos moléculas no metal fundido, então no método "Revision" realizaremos o cálculo do "balanço térmico" e a probabilidade de transição das moléculas para um novo estado.

No início do método, verificamos os valores de todas as funções de adaptação dos agentes, e se encontrarmos valores melhores que o global, então o atualizamos.

Em seguida, no ciclo "for" realizamos as seguintes ações para cada agente na população:

• o valor "ΔE" é calculado como o valor absoluto da diferença entre "a[i].f" e "a[i].fPrev", ou seja, a diferença entre os valores da função de adaptação na iteração atual e na anterior.

Se o valor "a[i].f" for maior que o valor "a[i].fPrev" (ou seja, a aptidão atual é melhor que a anterior), então o seguinte bloco de código é executado:

• o valor "a[i].fPrev" é substituído pelo valor "a[i].f"
• os valores do array "a[i].cPrev" são copiados do array "a[i].c"

Caso contrário, o seguinte bloco de código é executado (o valor atual da função de adaptação é pior que o anterior):

• o valor da probabilidade "P" é calculado como a exponencial da relação negativa de "ΔE" por "T"
• um número aleatório é gerado no intervalo [0.0;1.0] para "rnd", modelando a probabilidade de transição para um novo estado que é pior que o anterior

Se o valor de "rnd" for menor que o valor de "P" (ou seja, a probabilidade é cumprida), então:

• o valor "a[i].fPrev" é substituído pelo valor "a[i].f"
• os valores do array "a[i].cPrev" são copiados do array "a[i].c"

O valor da temperatura "T" é multiplicado pelo coeficiente térmico "α", resultando na redução da temperatura a cada nova iteração.

//————————————————————————————————————————
void C_AO_SA::Revision ()
{
  //----------------------------------------------------------------------------
  int ind = -1;

  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB) ind = i;
  }

  if (ind != -1)
  {
    fB = a [ind].f;
    ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY);
  }

  //----------------------------------------------------------------------------
  double rnd  = 0.0;
  double ΔE;
  double P;

  for (int i = 0; i < popSize; i++)
  {
    ΔE = fabs (a [i].f - a [i].fPrev);

    if (a [i].f > a [i].fPrev)
    {
      a [i].fPrev = a [i].f;
      ArrayCopy (a [i].cPrev, a [i].c, 0, 0, WHOLE_ARRAY);
    }
    else
    {
      P = exp (-ΔE / T);
      rnd = RNDfromCI (0, 1.0);

      if (rnd < P)
      {
        a [i].fPrev = a [i].f;
        ArrayCopy (a [i].cPrev, a [i].c, 0, 0, WHOLE_ARRAY);
      }

    }
  }

  T = α * T;
}
//————————————————————————————————————————

3. Resultados dos Testes

Resultados do funcionamento do algoritmo original em um ambiente de teste com a geração de números aleatórios em todo o intervalo permitido de valores:

C_AO_SA:50:1000.0:0.1:0.2
=============================
5 Rastrigin's; Func runs 10000 result: 61.3646399742684
Score: 0.76034
25 Rastrigin's; Func runs 10000 result: 47.454223750487884
Score: 0.58798
500 Rastrigin's; Func runs 10000 result: 39.06494648961887
Score: 0.48404
=============================
5 Forest's; Func runs 10000 result: 0.4708272303190655
Score: 0.26632
25 Forest's; Func runs 10000 result: 0.17553657864203864
Score: 0.09929
500 Forest's; Func runs 10000 result: 0.0538869772164491
Score: 0.03048
=============================
5 Megacity's; Func runs 10000 result: 2.6
Score: 0.21667
25 Megacity's; Func runs 10000 result: 1.0
Score: 0.08333
500 Megacity's; Func runs 10000 result: 0.3044
Score: 0.02537
=============================
All score: 2.55383

E esta é um print do algoritmo em execução em uma bancada de teste com o coeficiente de difusão adicionado:

C_AO_SA:50:1000.0:0.1:0.2
=============================
5 Rastrigin's; Func runs 10000 result: 65.78409729002105
Score: 0.81510
25 Rastrigin's; Func runs 10000 result: 52.25447043222567
Score: 0.64746
500 Rastrigin's; Func runs 10000 result: 40.40159931988021
Score: 0.50060
=============================
5 Forest's; Func runs 10000 result: 0.5814827554067439
Score: 0.32892
25 Forest's; Func runs 10000 result: 0.23156336186841173
Score: 0.13098
500 Forest's; Func runs 10000 result: 0.06760002887601002
Score: 0.03824
=============================
5 Megacity's; Func runs 10000 result: 2.92
Score: 0.24333
25 Megacity's; Func runs 10000 result: 1.256
Score: 0.10467
500 Megacity's; Func runs 10000 result: 0.33840000000000003
Score: 0.02820
=============================
All score: 2.83750

Pelos resultados desses dois testes, podemos ver que o desempenho do algoritmo melhorou significativamente com a aplicação do coeficiente de difusão. O algoritmo original precisou de melhorias para se posicionar em nossa tabela. É surpreendente que um método de otimização tão conhecido e popular apresente resultados tão fracos, especialmente considerando sua ampla aplicação, inclusive no treinamento de redes neurais.

A visualização da operação do SA não revelou quaisquer características distintas notáveis no comportamento dos agentes no espaço de busca, com os pontos se comportando de maneira caótica sem formar estruturas, similar ao movimento browniano térmico. Além disso, vemos que ficamos presos em extremos locais e a convergência deixa a desejar, embora não haja falta de diversidade na população, ou seja, a população não se esgota ao final das iterações.

  SA na função de teste Rastrigin.

  SA na função de teste Forest.

   SA na função de teste Megacity.

O algoritmo de simulação de têmpera simulado ficou na parte inferior da tabela. A tabela comparativa mostra que o algoritmo não apresenta características distintas em testes individuais, todos os resultados estão abaixo da média. Na tabela, há algoritmos como o CSS, que mostram resultados excelentes em testes individuais, embora também estejam na parte inferior da tabela, infelizmente, o algoritmo SA não está entre eles.

№	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	SDSm	stochastic diffusion search M	0,99809	1,00000	0,69149	2,68958	0,99265	1,00000	1,00000	2,99265	1,00000	1,00000	1,00000	3,00000	100,000
2	SSG	saplings sowing and growing	1,00000	0,92761	0,51630	2,44391	0,72120	0,65201	0,83760	2,21081	0,54782	0,61841	0,99522	2,16146	77,683
3	DE	differential evolution	0,98295	0,89236	0,51375	2,38906	1,00000	0,84602	0,65510	2,50112	0,90000	0,52237	0,12031	1,54268	73,099
4	HS	harmony search	0,99676	0,88385	0,44686	2,32747	0,99148	0,68242	0,37529	2,04919	0,71739	0,71842	0,41338	1,84919	70,623
5	IWO	invasive weed optimization	0,95828	0,62227	0,27647	1,85703	0,70170	0,31972	0,26613	1,28755	0,57391	0,30527	0,33130	1,21048	48,250
6	ACOm	ant colony optimization M	0,34611	0,16683	0,15808	0,67103	0,86147	0,68980	0,64798	2,19925	0,71739	0,63947	0,05579	1,41265	47,387
7	MEC	mind evolutionary computation	0,99270	0,47345	0,21148	1,67763	0,60244	0,28046	0,21324	1,09615	0,66957	0,30000	0,26045	1,23002	44,049
8	SDOm	spiral dynamics optimization M	0,69840	0,52988	0,33168	1,55996	0,59818	0,38766	0,37600	1,36183	0,35653	0,15262	0,25842	0,76758	40,289
9	NMm	Nelder-Mead method M	0,88433	0,48306	0,45945	1,82685	0,46155	0,24379	0,21903	0,92437	0,46088	0,25658	0,16810	0,88555	39,660
10	COAm	cuckoo optimization algorithm M	0,92400	0,43407	0,24120	1,59927	0,57881	0,23477	0,13842	0,95200	0,52174	0,24079	0,17001	0,93254	37,830
11	FAm	firefly algorithm M	0,59825	0,31520	0,15893	1,07239	0,50637	0,29178	0,41704	1,21519	0,24783	0,20526	0,35090	0,80398	33,139
12	ABC	artificial bee colony	0,78170	0,30347	0,19313	1,27829	0,53379	0,14799	0,11177	0,79355	0,40435	0,19474	0,13859	0,73768	29,766
13	BA	bat algorithm	0,40526	0,59145	0,78330	1,78002	0,20664	0,12056	0,21769	0,54488	0,21305	0,07632	0,17288	0,46225	29,499
14	CSS	charged system search	0,56605	0,68683	1,00000	2,25289	0,13961	0,01853	0,13638	0,29452	0,07392	0,00000	0,03465	0,10856	27,930
15	GSA	gravitational search algorithm	0,70167	0,41944	0,00000	1,12111	0,31390	0,25120	0,27812	0,84322	0,42609	0,25525	0,00000	0,68134	27,807
16	BFO	bacterial foraging optimization	0,67203	0,28721	0,10957	1,06881	0,39364	0,18364	0,17298	0,75026	0,37392	0,24211	0,18841	0,80444	27,542
17	EM	electroMagnetism-like algorithm	0,12235	0,42928	0,92752	1,47915	0,00000	0,02413	0,29215	0,31628	0,00000	0,00527	0,10872	0,11399	19,002
18	SFL	shuffled frog-leaping	0,40072	0,22021	0,24624	0,86717	0,19981	0,02861	0,02221	0,25063	0,19565	0,04474	0,06607	0,30646	13,200
19	SA	simulated annealing	0,36938	0,21640	0,10018	0,68595	0,20341	0,07832	0,09372	0,37545	0,16956	0,08422	0,10394	0,35772	13,138
20	MA	monkey algorithm	0,33192	0,31029	0,13582	0,77804	0,09927	0,05443	0,07482	0,22852	0,15652	0,03553	0,10669	0,29874	11,777
21	FSS	fish school search	0,46812	0,23502	0,10483	0,80798	0,12730	0,03458	0,05458	0,21647	0,12175	0,03947	0,08244	0,24366	11,332
22	IWDm	intelligent water drops M	0,26459	0,13013	0,07500	0,46972	0,28358	0,05445	0,05112	0,38916	0,22609	0,05659	0,05054	0,33322	10,423
23	PSO	particle swarm optimisation	0,20449	0,07607	0,06641	0,34696	0,18734	0,07233	0,18207	0,44175	0,16956	0,04737	0,01947	0,23641	8,426
24	RND	random	0,16826	0,09038	0,07438	0,33302	0,13381	0,03318	0,03949	0,20648	0,12175	0,03290	0,04898	0,20363	5,054
25	GWO	grey wolf optimizer	0,00000	0,00000	0,02093	0,02093	0,06514	0,00000	0,00000	0,06514	0,23478	0,05789	0,02545	0,31812	1,000

Considerações finais

O algoritmo de simulação de têmpera possui várias fraquezas que podem limitar sua eficácia na resolução de algumas tarefas de otimização. Alguns desses pontos fracos são:

• Dependência da solução inicial: assim como muitos outros métodos de otimização, o algoritmo de simulação de têmpera pode depender da solução inicial, que é escolhida aleatoriamente. Se a solução inicial for ruim, o algoritmo pode ficar preso em um ótimo local e não conseguir encontrar o ótimo global.
  
  É importante notar que o algoritmo requer ajustes de parâmetros como a "temperatura" inicial, e o passo de mudança de temperatura, que influenciam a probabilidade de aceitar uma solução pior. Esses parâmetros afetam o desempenho e a qualidade das soluções, portanto, a escolha e ajuste dos parâmetros são aspectos importantes na aplicação do algoritmo de simulação de têmpera a uma tarefa específica de otimização. Ajustar esses parâmetros pode ser uma tarefa complexa, e um ajuste inadequado pode levar a resultados ruins. As configurações padrão foram escolhidas por mim para obter os melhores resultados no conjunto de testes de funções.
  
  
• Outra fraqueza do algoritmo de simulação de têmpera é a possibilidade de ficar preso em extremos locais. Isso ocorre quando o algoritmo encontra uma solução ótima que é um extremo local, mas não é um extremo global. Neste caso, o algoritmo não será capaz de avançar além e parará no ótimo local. Isso é muito evidente na imagem acima.
  
  
• Baixa velocidade de convergência: O SA pode ser lento na convergência para a solução ótima, especialmente para tarefas complexas de otimização. Isso se deve ao fato de que o algoritmo usa aleatoriedade e pode aceitar soluções piores, o que pode desacelerar o processo de otimização.
  
  
• Necessidade de um grande número de iterações: Para alcançar a solução ótima, o algoritmo de simulação de têmpera simulado pode requerer um grande número de iterações. Isso pode ser um problema para tarefas onde o tempo de execução é um fator crítico.
  
  
• Ineficácia na resolução de tarefas com um grande número de variáveis: O SA pode ser ineficaz na resolução de tarefas com um grande número de variáveis, pois o espaço de busca pode ser muito grande. Nesse caso, outros métodos de otimização, como algoritmos genéticos ou métodos de otimização baseados em gradiente, podem ser mais eficientes. Com um pequeno número de variáveis (1-2), o algoritmo funciona bem, assim como qualquer algoritmo, até mesmo uma simples busca aleatória RND.

Existem várias melhorias que podem ser aplicadas ao algoritmo de simulação de têmpera simulado para aumentar sua performance e eficiência:

1. Modificação da função de resfriamento: a função de resfriamento é um parâmetro importante do algoritmo, que regula a velocidade de resfriamento e a temperatura do sistema.

2. Uso de métodos mais eficazes para seleção do próximo estado: o SA utiliza a seleção aleatória do próximo estado. No entanto, existem métodos mais eficientes de seleção, como técnicas de mutação e cruzamento.

3. Uso de parâmetros adaptativos: parâmetros do algoritmo, como a temperatura inicial e o coeficiente de resfriamento, podem ser adaptativamente ajustados dependendo das características da tarefa de otimização.

4. Combinação de algoritmos: o SA pode ser combinado com outros algoritmos de otimização, como algoritmos genéticos ou métodos de descida de gradiente, para melhorar a performance e eficiência da otimização.

A aplicação de diferentes distribuições aleatórias na geração de novos estados do sistema, em vez de uniforme, não ajudou a melhorar os resultados. No entanto, existe uma maneira de transformar radicalmente este popular algoritmo de tal forma que ele possa competir com os líderes da tabela por posições de destaque. Como isso é possível? Estou pronto para compartilhar esse método na segunda parte do artigo e contar sobre todas as etapas de modificação. Mas, como sabemos, não existe uma maneira universal de melhorar qualquer algoritmo de otimização, e isso depende exclusivamente da estratégia de busca no próprio algoritmo. Portanto, a melhoria só se aplicará ao velho e bom, mas praticamente inútil, algoritmo de simulação de têmpera simulado.

Figura 3. Gradiente de cores dos algoritmos de acordo com os testes correspondentes.

Figura 4. Histograma dos resultados dos testes dos algoritmos (na escala de 0 a 100, quanto maior, melhor,

no arquivo um script para calcular a tabela de classificação conforme o método neste artigo).

Prós e contras do algoritmo de simulação de têmpera (SA):

Prós:

1. Poucos parâmetros externos.
2. Alta velocidade de operação.
3. Implementação muito simples.
   

Contras:

1. Ajustes não óbvios (não está claro como e o que a temperatura afeta).
   
2. Escala muito pobre.
3. Alta variabilidade dos resultados.
4. Tendência a ficar preso em extremos locais.
5. Má convergência.

O artigo é acompanhado por um arquivo com versões atualizadas dos códigos dos algoritmos descritos em artigos anteriores. 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 opiniões apresentadas nos artigos são baseadas nos resultados dos experimentos realizados.