Algoritmos de otimização populacional: simulação de têmpera isotrópica (Simulated Isotropic Annealing, SIA). Parte II
102
0
Conteúdo:
1. Introdução
2. Descrição do algoritmo
3. Resultados dos testes
1. Introdução
Na primeira parte do artigo, analisamos a versão canônica do algoritmo de têmpera simulada, ou Simulated Annealing (SA). O algoritmo é baseado em três conceitos principais: aplicação da aleatoriedade, toma de decisões piores e redução gradual da probabilidade de toma de decisões piores. A aplicação da aleatoriedade nos permite explorar diferentes áreas do espaço de busca e evitar ficar preso em ótimos locais. A toma de decisões piores com uma certa probabilidade permite que o algoritmo temporariamente "escape" de ótimos locais e busque melhores soluções em outras partes do espaço de busca, o que possibilita inicialmente explorar o espaço de busca de forma mais ampla e depois se concentrar em melhorar a solução.
A ideia central do SA é uma analogia com o processo de têmpera do metal. O metal previamente aquecido é gradualmente resfriado, mudando sua estrutura. Analogamente, o algoritmo de têmpera simulada começa com uma alta temperatura (alta probabilidade de tomar uma decisão pior) e gradualmente diminui a temperatura (reduz a probabilidade de tomar uma decisão pior), o que supostamente ajuda o algoritmo a convergir para a solução ótima.
O algoritmo começa com uma solução inicial, que pode ser aleatória ou baseada em iterações anteriores. Em seguida, são aplicadas operações de alteração do estado da solução, que podem ser aleatórias ou controladas, para obter um novo estado, mesmo que seja pior que o atual. A probabilidade de tomar uma decisão pior é determinada por uma função de "resfriamento", que ao longo do tempo reduz a probabilidade de tomar uma decisão pior.
Para descrever o processo de têmpera simulada, são usadas algumas fórmulas simples. A fórmula para calcular a mudança de energia permite determinar a diferença nos valores da função de adaptação em duas iterações consecutivas. A fórmula para calcular a probabilidade de tomar uma decisão pior determina a probabilidade de adotar o novo estado levando em conta a diferença de energia e a temperatura atual.
Os parâmetros importantes que precisam ser ajustados ao usar o algoritmo de têmpera simulada são a temperatura inicial e o coeficiente de resfriamento. A configuração desses parâmetros pode ter um impacto significativo no desempenho e na qualidade da solução e é um dos pontos fracos do algoritmo, há certa dificuldade na escolha dos parâmetros por seu impacto não evidente na eficácia. Além disso, ambos os parâmetros influenciam mutuamente: o aumento da temperatura pode ser praticamente substituído pela redução do coeficiente de resfriamento.
Na primeira parte do artigo, identificamos os principais problemas do algoritmo:
- Configuração dos parâmetros: parâmetros do SA, como temperatura inicial e coeficiente de resfriamento, podem influenciar significativamente seu desempenho. A configuração desses parâmetros pode ser uma tarefa complexa, e requer experimentação para alcançar os valores ideais.
- Problema de ficar preso em extremos locais: para superar esse problema, podem-se utilizar várias estratégias, como a escolha da distribuição mais adequada da variável aleatória ao gerar novas soluções em combinação com as ferramentas de estratégia do algoritmo, bem como a consideração de possíveis soluções para aumentar as capacidades combinatórias.
- Melhoria da velocidade de convergência: para acelerar a convergência, podem-se aplicar modificações na função de resfriamento, que permitam reduzir a temperatura do sistema mais rapidamente (ou com outra forma da função de resfriamento). Também é possível revisar no algoritmo os métodos de escolha do próximo estado, que levam em conta informações dos estados anteriormente percorridos.
- Melhoria da eficiência do SA com um grande número de variáveis: essa é uma das questões mais desafiadoras para a esmagadora maioria dos algoritmos, pois com o aumento do número de variáveis a complexidade do espaço de busca cresce muito mais rapidamente do que se pode lidar com metodologias especiais nas estratégias de busca.
Um dos principais problemas em espaços multidimensionais é a explosão combinatória das possíveis combinações de variáveis. Com o aumento do número de variáveis, cresce exponencialmente a quantidade de possíveis estados do sistema que precisam ser investigados. Isso leva a algoritmos de otimização a enfrentarem o problema da complexidade espacial.
A complexidade espacial significa que o volume do espaço de busca cresce exponencialmente com o aumento do número de variáveis. Por exemplo, se temos 10 variáveis, cada uma podendo assumir 10 valores, o número total de combinações possíveis será de 10^10, que equivale a 10 bilhões, e isso considerando que temos apenas 10 mil tentativas (número de execuções da função de adaptação). Encontrar a solução ótima entre esse número de combinações se torna uma tarefa extremamente difícil. Vale destacar que em nossos testes realizamos a otimização dos parâmetros das funções com um passo 0, o que significa condições inimaginavelmente complexas para os algoritmos, e aqueles que conseguem lidar satisfatoriamente com esses testes extremamente difíceis, irão quase que garantidamente trabalhar melhor em tarefas reais menos complexas (ceteris paribus).
2. Descrição do algoritmo
O algoritmo de simulação de têmpera é tão simples que é verdadeiramente difícil imaginar como ele pode ser ainda mais aprimorado. É como transformar um copo de água em um vinho encantador, como um ato de magia. E realmente, o que pode ser aprimorado, se a geração de novos valores é uniformemente distribuída, e a ideia de tomar uma decisão pior contraria totalmente a lógica usual de construção de algoritmos de otimização.
Para uma comparação visual dos resultados subsequentes dos experimentos com o resultado de referência inicial do algoritmo original de simulação de têmpera (SA), apresentamos aqui a impressão dos resultados do artigo anterior:
=============================
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
Então, vamos lá. Tentaremos melhorar os resultados substituindo a distribuição uniforme de variáveis aleatórias pela normal ao gerar novos estados do sistema.
Usaremos a classe do algoritmo de simulação de têmpera como base para o novo algoritmo SIA, por isso não descreveremos os métodos e funcionalidades dessa classe, pois tudo já foi apresentado na primeira parte do artigo.
Para gerar um número aleatório com distribuição normal, podemos usar o método da função inversa. Suponhamos que queremos gerar um número "x" com distribuição normal, mu (valor médio) e sigma (desvio padrão). Então, podemos usar a seguinte fórmula:
x = z0 * sigma + mu
onde:- z0 é calculado pela fórmula:
z0 = sqrt(-2 * log(u1)) * cos(2 * Pi * u2)
onde:-
u1* - número aleatório no intervalo (0,0;1,0] (aqui o mínimo não está no intervalo)
-
u2** - número aleatório no intervalo [0,0;1,0]
- * e ** - dois números aleatórios independentes com distribuição uniforme
No artigo anterior, adicionamos ao SA o parâmetro coeficiente de difusão, que limita a área de geração de números aleatórios. É nessa área que devemos gerar números aleatórios.
Escreveremos um método da classe C_AO_SIA, imitando a difusão - "Diffusion". O método gera um número aleatório com distribuição normal até dois desvios padrão. Os valores que excedem esses limites são "dobrados" para dentro sem perder a forma da distribuição (abordaremos isso em mais detalhes em um dos próximos artigos).
Conhecendo o valor do desvio padrão (sigma), podemos traduzir esse intervalo de valores em nosso intervalo desejado que simula a difusão.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_SIA::Diffusion (const double value, const double rMin, const double rMax, const double step) { double logN = 0.0; double u1 = RNDfromCI (0.0, 1.0); double u2 = RNDfromCI (0.0, 1.0); logN = u1 <= 0.0 ? 0.000000000000001 : u1; double z0 = sqrt (-2 * log (logN))* cos (2 * M_PI * u2); double sigma = 2.0;//Sigma > 8.583864105157389 ? 8.583864105157389 : Sigma; if (z0 >= sigma) z0 = RNDfromCI (0.0, sigma); if (z0 <= -sigma) z0 = RNDfromCI (-sigma, 0.0); double dist = d * (rMax - rMin); if (z0 >= 0.0) return Scale (z0, 0.0, sigma, value, value + dist, false); else return Scale (z0, -sigma, 0.0, value - dist, value, false); } //——————————————————————————————————————————————————————————————————————————————
No método "Moving", usaremos o método "Diffusion" da seguinte forma:
for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { a [i].c [c] = Diffusion (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); a [i].c [c] = SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } }Após realizar os testes com as alterações feitas (substituímos a distribuição uniforme pela normal), obtivemos os seguintes resultados:
=============================
5 Rastrigin's; Func runs 10000 result: 60.999013617749895
Score: 0.75581
25 Rastrigin's; Func runs 10000 result: 47.993562806349246
Score: 0.59467
500 Rastrigin's; Func runs 10000 result: 40.00575378955945
Score: 0.49569
=============================
5 Forest's; Func runs 10000 result: 0.41673083215719087
Score: 0.23572
25 Forest's; Func runs 10000 result: 0.16700842421505407
Score: 0.09447
500 Forest's; Func runs 10000 result: 0.049538421252065555
Score: 0.02802
=============================
5 Megacity's; Func runs 10000 result: 2.7600000000000002
Score: 0.23000
25 Megacity's; Func runs 10000 result: 0.9039999999999999
Score: 0.07533
500 Megacity's; Func runs 10000 result: 0.28
Score: 0.02333
=============================
All score: 2.53305
Quando alteramos a distribuição de variáveis aleatórias no algoritmo de simulação de têmpera, assim como em qualquer outro algoritmo, isso certamente influenciará seu funcionamento e resultados. Na fórmula original do algoritmo, é utilizada a distribuição uniforme para gerar passos aleatórios na exploração do espaço de soluções. Essa distribuição garante probabilidades iguais para todos os possíveis passos.
Quando substituímos a distribuição uniforme pela distribuição normal, as propriedades probabilísticas do algoritmo mudaram. A distribuição normal tem um pico ao redor do valor médio e diminui à medida que se afasta do médio. Isso significa que os passos aleatórios gerados usando a distribuição normal estarão concentrados em torno do valor médio, tornando improváveis os passos que estão muito distantes do médio. No nosso caso, o "valor médio" é o valor inicial da coordenada que queremos melhorar.
Essa mudança na distribuição, obviamente, leva a passos menos variados na exploração do espaço de soluções. Parece que o algoritmo se torna mais local e menos capaz de explorar regiões mais distantes ou menos prováveis do espaço de soluções.
Os testes apresentados acima mostram que, neste caso, o uso da distribuição normal levou a uma pequena, mas estatisticamente significativa, piora nos resultados finais em comparação com a variável aleatória uniformemente distribuída (como refletido na primeira parte do artigo). Esses resultados foram obtidos usando dois desvios padrão, e o aumento do valor de sigma (desvio padrão) leva a uma piora estatisticamente significativa nos resultados.
Assim, concluímos que alterar a forma da distribuição para uma mais pontiaguda, neste caso específico, piora os resultados.
Agora que percebemos que "afunilar" a forma da distribuição no algoritmo original não é útil, vamos considerar outra abordagem. Suponhamos que, no algoritmo original, as moléculas no metal, ou melhor, os cristais inteiros dentro da zona de difusão, não têm a capacidade de trocar energia para distribuí-la uniformemente por todo o volume do metal. Nesse caso, podemos propor a seguinte ideia: permitir que os cristais troquem moléculas no processo de troca de energia.
Esse processo de troca de moléculas entre cristais com diferentes energias permitirá a transferência de coordenadas entre os agentes. Assim, as moléculas se tornarão transportadoras de energia, capazes de suavizar a distribuição de energia por todo o volume do metal. Como resultado dessa interação entre a rede cristalina e as moléculas, a energia será distribuída mais uniformemente, permitindo alcançar uma configuração mais estável e ótima do sistema. Ou seja, tentaremos aumentar a isotropia na estrutura do metal.
A isotropia é a propriedade de um objeto ou sistema de manter as mesmas características ou propriedades em todas as direções. Em termos mais simples, um objeto ou sistema é isotrópico se parecer e se comportar da mesma maneira em qualquer direção. Assim, a isotropia implica a ausência de direção ou orientação preferencial, e o objeto ou sistema é considerado igual ou homogêneo em todas as direções.
Para realizar um alinhamento simulado das propriedades no metal em todas as direções (aumento da isotropia), precisaremos fazer alterações no método "Moving".
A lógica do código é a seguinte: ocorre uma iteração por cada elemento da população "popSize" e cada coordenada "coords":
- gera-se um número inteiro aleatório "r" no intervalo de 0 a "popSize" usando a função RNDfromCI, escolhendo aleatoriamente um agente na população
- verifica-se a condição: se o valor da função de adaptação do agente selecionado for maior que o valor da adaptabilidade do agente alterado, a coordenada do melhor é copiada, caso contrário, a coordenada do agente não muda
- o número aleatório "rnd" no intervalo [-0,1;0,1] é gerado usando a função RNDfromCI
- o valor da coordenada é atualizado adicionando a ele o produto de "rnd", (rangeMax[c] - rangeMin[c]) e "d", ou seja, adicionamos um incremento aleatório na faixa de difusão
- a coordenada obtida é verificada com a função SeInDiSp para garantir que esteja dentro do intervalo permitido e com o passo requerido
int r = 0; double rnd = 0.0; for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { r = (int)RNDfromCI (0, popSize); if (r >= popSize) r = popSize - 1; if (a [r].fPrev > a [i].fPrev) { a [i].c [c] = a [r].cPrev [c]; } else { a [i].c [c] = a [i].cPrev [c]; } rnd = RNDfromCI (-0.1, 0.1); a [i].c [c] = a [i].c [c] + rnd * (rangeMax [c] - rangeMin [c]) * d; a [i].c [c] = SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } }
Resultados da têmpera com os mesmos parâmetros com distribuição uniforme e com adição de isotropia:
C_AO_SIA:50:1000.0:0.1:0.1
=============================
5 Rastrigin's; Func runs 10000 result: 80.52391137534615
Score: 0.99774
25 Rastrigin's; Func runs 10000 result: 77.70887543197314
Score: 0.96286
500 Rastrigin's; Func runs 10000 result: 57.43358792423487
Score: 0.71163
=============================
5 Forest's; Func runs 10000 result: 1.5720970326889474
Score: 0.88926
25 Forest's; Func runs 10000 result: 1.0118351454323513
Score: 0.57234
500 Forest's; Func runs 10000 result: 0.3391169587652742
Score: 0.19182
=============================
5 Megacity's; Func runs 10000 result: 6.76
Score: 0.56333
25 Megacity's; Func runs 10000 result: 5.263999999999999
Score: 0.43867
500 Megacity's; Func runs 10000 result: 1.4908
Score: 0.12423
=============================
All score: 5.45188
O aumento da isotropia, processo em que ocorre a troca de moléculas entre cristais com diferentes energias, melhorou significativamente os resultados de desempenho do algoritmo, reivindicando uma posição de liderança.
Conclusões que podem ser tiradas, motivadas pelo processo descrito:
- Transmissão de coordenadas entre agentes: a troca de moléculas entre cristais com diferentes energias permite a transmissão de informações de coordenadas entre os agentes no algoritmo. Isso contribui para uma busca mais eficiente e rápida da solução ótima, pois as informações sobre boas soluções são transmitidas a outros agentes.
- Suavização da distribuição energética: o processo de troca de moléculas entre cristais com diferentes energias permite suavizar a distribuição energética por todo o volume do metal. Isso significa que a energia será mais uniformemente distribuída, ajudando a evitar mínimos locais e a alcançar uma configuração mais estável e otimizada do sistema.
Agora, após a melhoria significativa dos resultados com o aumento da isotropia, tentemos novamente adicionar a distribuição normal (primeiro realizamos a operação de aumento da isotropia e aos valores obtidos adicionamos o incremento com distribuição normal).
Resultados da têmpera com adição de aumento de isotropia + distribuição normal:
C_AO_SIA:50:1000.0:0.1:0.05
=============================
5 Rastrigin's; Func runs 10000 result: 78.39172420614801
Score: 0.97132
25 Rastrigin's; Func runs 10000 result: 66.41980717898778
Score: 0.82298
500 Rastrigin's; Func runs 10000 result: 47.62039509425823
Score: 0.59004
=============================
5 Forest's; Func runs 10000 result: 1.243327107341557
Score: 0.70329
25 Forest's; Func runs 10000 result: 0.7588262864735575
Score: 0.42923
500 Forest's; Func runs 10000 result: 0.13750740782669305
Score: 0.07778
=============================
5 Megacity's; Func runs 10000 result: 6.8
Score: 0.56667
25 Megacity's; Func runs 10000 result: 2.776
Score: 0.23133
500 Megacity's; Func runs 10000 result: 0.46959999999999996
Score: 0.03913
=============================
All score: 4.43177
Os resultados pioraram significativamente.
A hipótese de que, se a simples geração de incrementos com distribuição normal no algoritmo de simulação de têmpera não trouxe melhorias, então, talvez, após aplicar o aumento da isotropia, o incremento com distribuição normal daria o efeito esperado? As expectativas não se confirmaram. Isso pode ser explicado pelo fato de que, após aplicar o aumento da isotropia, a distribuição uniforme ainda proporciona uma exploração mais equilibrada do espaço de soluções, permitindo que o algoritmo explore diferentes áreas sem grandes distorções nas preferências. A tentativa de refinar as coordenadas existentes com a distribuição normal não teve sucesso, o que limita uma exploração mais ampla das áreas pelo algoritmo.
Realizaremos um último experimento para finalmente tirar conclusões a favor da distribuição uniforme de incrementos de variáveis aleatórias após aplicar o aumento da isotropia. Tentaremos explorar de forma ainda mais precisa as proximidades das coordenadas conhecidas, usando para isso a distribuição quadrática. Se uma variável aleatória com distribuição uniforme é elevada ao quadrado, a distribuição resultante será chamada de distribuição quadrática ou distribuição da variável aleatória ao quadrado.
Resultados do algoritmo de simulação de têmpera com os mesmos parâmetros e adição de aumento de isotropia + distribuição quadrática acentuada:
C_AO_SIA:50:1000.0:0.1:0.2
=============================
5 Rastrigin's; Func runs 10000 result: 70.23675927985173
Score: 0.87027
25 Rastrigin's; Func runs 10000 result: 56.86176837508631
Score: 0.70455
500 Rastrigin's; Func runs 10000 result: 43.100825665204596
Score: 0.53404
=============================
5 Forest's; Func runs 10000 result: 0.9361317757226002
Score: 0.52952
25 Forest's; Func runs 10000 result: 0.25320813586138297
Score: 0.14323
500 Forest's; Func runs 10000 result: 0.0570263375476293
Score: 0.03226
=============================
5 Megacity's; Func runs 10000 result: 4.2
Score: 0.35000
25 Megacity's; Func runs 10000 result: 1.296
Score: 0.10800
500 Megacity's; Func runs 10000 result: 0.2976
Score: 0.02480
=============================
All score: 3.29667
Agora, vamos eliminar outro problema do algoritmo de simulação de têmpera, que é a dificuldade na escolha das configurações e da combinação da temperatura e do coeficiente de redução da temperatura, já que esses dois parâmetros se influenciam mutuamente. Para vincular os dois parâmetros, combinamos a função de redução de temperatura e a função de decisão probabilística do pior caso. Aplicaremos a função de arco cosseno hiperbólico:
(1 - delta) * (acosh (-(x^3 - 3))) / 1,765
onde:
- delta - diferença normalizada no intervalo [0,0;1,0] dos valores da função de adaptação nas duas últimas iterações
- x - passos normalizados das épocas do algoritmo
Figura 1. Gráfico da dependência da toma de uma pior solução em relação à diferença de energias e ao número da época atual (y - diferença de energias, x - épocas).
3. Resultados dos testes
Impressão do funcionamento da versão final do algoritmo de simulação de têmpera isotrópico (SIA) na bancada de testes:
C_AO_SIA:100:0.01:0.1
=============================
5 Rastrigin's; Func runs 10000 result: 80.49732910930824
Score: 0.99741
25 Rastrigin's; Func runs 10000 result: 78.48411039606445
Score: 0.97246
500 Rastrigin's; Func runs 10000 result: 56.26829697982381
Score: 0.69720
=============================
5 Forest's; Func runs 10000 result: 1.6491133508905373
Score: 0.93282
25 Forest's; Func runs 10000 result: 1.3608802086313785
Score: 0.76978
500 Forest's; Func runs 10000 result: 0.31584037846210056
Score: 0.17866
=============================
5 Megacity's; Func runs 10000 result: 8.6
Score: 0.71667
25 Megacity's; Func runs 10000 result: 6.152
Score: 0.51267
500 Megacity's; Func runs 10000 result: 1.0544
Score: 0.08787
=============================
All score: 5.86552
Resultados impressionantes e, ao mesmo tempo, como você notou, agora há um parâmetro a menos.
A visualização do funcionamento do algoritmo mostra uma clara separação em clusters distintos de agentes, abrangendo todos os extremos locais significativos. A imagem lembra a cristalização real de um metal em solidificação. Chama a atenção a excelente convergência em todos os testes, incluindo, o que é muito importante, aqueles com muitas variáveis.
SIA na função de teste Rastrigin.
SIA na função de teste Forest.
SIA na função de teste Megacity.
O novo algoritmo de simulação de têmpera isotrópico (SIA, 2023) conquistou o segundo lugar na tabela de classificação, tirando a liderança do SDSm em dois dos testes mais difíceis (Forest aguda e Megacity discreta com 1000 variáveis).
| № | 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 | 0,84982 | 2,84247 | 1,00000 | 1,00000 | 0,79920 | 2,79920 | 100,000 |
| 2 | SIA | simulated isotropic annealing | 0,99236 | 0,93642 | 0,69858 | 2,62736 | 0,88760 | 0,64655 | 1,00000 | 2,53416 | 0,58695 | 0,74342 | 1,00000 | 2,33038 | 89,524 |
| 3 | SSG | saplings sowing and growing | 1,00000 | 0,92761 | 0,51630 | 2,44391 | 0,72120 | 0,65201 | 0,71181 | 2,08502 | 0,54782 | 0,61841 | 0,79538 | 1,96161 | 77,027 |
| 4 | DE | differential evolution | 0,98295 | 0,89236 | 0,51375 | 2,38906 | 1,00000 | 0,84602 | 0,55672 | 2,40274 | 0,90000 | 0,52237 | 0,09615 | 1,51852 | 74,777 |
| 5 | HS | harmony search | 0,99676 | 0,88385 | 0,44686 | 2,32747 | 0,99148 | 0,68242 | 0,31893 | 1,99283 | 0,71739 | 0,71842 | 0,33037 | 1,76618 | 71,983 |
| 6 | IWO | invasive weed optimization | 0,95828 | 0,62227 | 0,27647 | 1,85703 | 0,70170 | 0,31972 | 0,22616 | 1,24758 | 0,57391 | 0,30527 | 0,26478 | 1,14395 | 49,045 |
| 7 | ACOm | ant colony optimization M | 0,34611 | 0,16683 | 0,15808 | 0,67103 | 0,86147 | 0,68980 | 0,55067 | 2,10194 | 0,71739 | 0,63947 | 0,04459 | 1,40145 | 48,119 |
| 8 | MEC | mind evolutionary computation | 0,99270 | 0,47345 | 0,21148 | 1,67763 | 0,60244 | 0,28046 | 0,18122 | 1,06412 | 0,66957 | 0,30000 | 0,20815 | 1,17772 | 44,937 |
| 9 | SDOm | spiral dynamics optimization M | 0,69840 | 0,52988 | 0,33168 | 1,55996 | 0,59818 | 0,38766 | 0,31953 | 1,30537 | 0,35653 | 0,15262 | 0,20653 | 0,71568 | 40,713 |
| 10 | NMm | Nelder-Mead method M | 0,88433 | 0,48306 | 0,45945 | 1,82685 | 0,46155 | 0,24379 | 0,18613 | 0,89148 | 0,46088 | 0,25658 | 0,13435 | 0,85180 | 40,577 |
| 11 | COAm | cuckoo optimization algorithm M | 0,92400 | 0,43407 | 0,24120 | 1,59927 | 0,57881 | 0,23477 | 0,11764 | 0,93121 | 0,52174 | 0,24079 | 0,13587 | 0,89840 | 38,814 |
| 12 | FAm | firefly algorithm M | 0,59825 | 0,31520 | 0,15893 | 1,07239 | 0,50637 | 0,29178 | 0,35441 | 1,15256 | 0,24783 | 0,20526 | 0,28044 | 0,73352 | 32,943 |
| 13 | ABC | artificial bee colony | 0,78170 | 0,30347 | 0,19313 | 1,27829 | 0,53379 | 0,14799 | 0,09498 | 0,77676 | 0,40435 | 0,19474 | 0,11076 | 0,70985 | 30,528 |
| 14 | BA | bat algorithm | 0,40526 | 0,59145 | 0,78330 | 1,78002 | 0,20664 | 0,12056 | 0,18499 | 0,51219 | 0,21305 | 0,07632 | 0,13816 | 0,42754 | 29,964 |
| 15 | CSS | charged system search | 0,56605 | 0,68683 | 1,00000 | 2,25289 | 0,13961 | 0,01853 | 0,11590 | 0,27404 | 0,07392 | 0,00000 | 0,02769 | 0,10161 | 28,825 |
| 16 | GSA | gravitational search algorithm | 0,70167 | 0,41944 | 0,00000 | 1,12111 | 0,31390 | 0,25120 | 0,23635 | 0,80145 | 0,42609 | 0,25525 | 0,00000 | 0,68134 | 28,518 |
| 17 | BFO | bacterial foraging optimization | 0,67203 | 0,28721 | 0,10957 | 1,06881 | 0,39364 | 0,18364 | 0,14700 | 0,72428 | 0,37392 | 0,24211 | 0,15058 | 0,76660 | 27,966 |
| 18 | EM | electroMagnetism-like algorithm | 0,12235 | 0,42928 | 0,92752 | 1,47915 | 0,00000 | 0,02413 | 0,24828 | 0,27240 | 0,00000 | 0,00527 | 0,08689 | 0,09216 | 19,030 |
| 19 | SFL | shuffled frog-leaping | 0,40072 | 0,22021 | 0,24624 | 0,86717 | 0,19981 | 0,02861 | 0,01888 | 0,24729 | 0,19565 | 0,04474 | 0,05280 | 0,29320 | 13,588 |
| 20 | SA | simulated annealing | 0,36938 | 0,21640 | 0,10018 | 0,68595 | 0,20341 | 0,07832 | 0,07964 | 0,36137 | 0,16956 | 0,08422 | 0,08307 | 0,33685 | 13,295 |
| 21 | MA | monkey algorithm | 0,33192 | 0,31029 | 0,13582 | 0,77804 | 0,09927 | 0,05443 | 0,06358 | 0,21729 | 0,15652 | 0,03553 | 0,08527 | 0,27731 | 11,903 |
| 22 | FSS | fish school search | 0,46812 | 0,23502 | 0,10483 | 0,80798 | 0,12730 | 0,03458 | 0,04638 | 0,20827 | 0,12175 | 0,03947 | 0,06588 | 0,22710 | 11,537 |
| 23 | IWDm | intelligent water drops M | 0,26459 | 0,13013 | 0,07500 | 0,46972 | 0,28358 | 0,05445 | 0,04345 | 0,38148 | 0,22609 | 0,05659 | 0,04039 | 0,32307 | 10,675 |
| 24 | PSO | particle swarm optimisation | 0,20449 | 0,07607 | 0,06641 | 0,34696 | 0,18734 | 0,07233 | 0,15473 | 0,41440 | 0,16956 | 0,04737 | 0,01556 | 0,23250 | 8,423 |
| 25 | RND | random | 0,16826 | 0,09038 | 0,07438 | 0,33302 | 0,13381 | 0,03318 | 0,03356 | 0,20055 | 0,12175 | 0,03290 | 0,03915 | 0,19380 | 5,097 |
| 26 | 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,02034 | 0,31301 | 1,000 |
Considerações finais
Com base nos experimentos realizados e na análise dos resultados, podemos fazer as seguintes conclusões:
- O novo algoritmo de simulação de têmpera isotrópico (SIA) demonstra resultados impressionantes na otimização de funções com muitas variáveis. Isso indica a eficácia do algoritmo na busca de soluções ótimas em espaços de alta dimensionalidade.
- O algoritmo mostra resultados especialmente bons em funções com características agudas e discretas. Isso pode ser atribuído ao fato de que o SIA permite explorar uniformemente o espaço de soluções e encontrar pontos ótimos, mesmo em áreas complexas e irregulares.
- Em geral, o novo algoritmo SIA é uma ferramenta poderosa de otimização. Graças à combinação bem-sucedida de estratégias de busca, o algoritmo possui propriedades qualitativamente novas e demonstra alta eficiência na busca de soluções ótimas.
No novo algoritmo SIA, além do tamanho da população, há apenas dois parâmetros, a temperatura e o coeficiente de difusão, em vez de três como era no SA. Além disso, agora o parâmetro de temperatura é muito simples de entender e é expresso em partes de uma temperatura abstrata, sendo por padrão igual a 0.01.
Com base nos estudos realizados e na análise dos resultados, podemos recomendar com total confiança o algoritmo SIA para uso no treinamento de redes neurais, em tarefas de trading com muitos parâmetros e em problemas complexos de combinatória.
Figura 2. Graduação de cores dos algoritmos nos testes correspondentes.
Figura 3. Histograma dos resultados dos testes dos algoritmos (na escala de 0 a 100, quanto maior, melhor,
no arquivo há um script para calcular a tabela de classificação de acordo com a metodologia descrita neste artigo).
Prós e contras do algoritmo de simulação de têmpera isotrópico (SIA):
- Número mínimo de parâmetros externos.
- Alta eficiência na resolução de diversas tarefas.
- Baixa carga nos recursos computacionais.
- Facilidade na implementação do algoritmo.
- Resistência a travamentos.
- Altos resultados tanto em funções suaves quanto em complexas e discretas.
- Alta convergência.
- Não foram observadas.
O artigo inclui um arquivo com as versões atualizadas e atuais dos códigos dos algoritmos descritos nos 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 conduzidos.
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/13870
Ciência de Dados e Aprendizado de Máquina (Parte 16): Uma nova perspectiva sobre árvores de decisão
EA de grid-hedge modificado em MQL5 (Parte I): Criando um EA de hedge simples
Desenvolvendo um sistema de Replay (Parte 50): Complicando as coisas (II)
Paradigmas de programação (Parte 1): Abordagem procedural para desenvolvimento de Expert Advisors com base na dinâmica de preços
- Aplicativos de negociação gratuitos
- 8 000+ sinais para cópia
- Notícias econômicas para análise dos mercados financeiros
Você concorda com a política do site e com os termos de uso