Algoritmos de otimização populacionais: Algoritmo do macaco (MA)
Conteúdo
1. Introdução
2. Descrição do algoritmo
3. Resultado dos testes
1. Introdução
O algoritmo do macaco (Monkey Algorithm, MA) é uma metaheurística de pesquisa algorítmica. Este artigo explicará os componentes essenciais do algoritmo, dando ênfase às soluções para o processo de ascensão (movimento para cima), o processo de salto local e o processo de salto global. Este algoritmo foi proposto por R. Zhao e W. Tang em 2007. O modelo algorítmico reproduz o comportamento dos macacos durante os seus movimentos e saltos por montanhas na busca por comida. O algoritmo supõe que os macacos assumem que quanto mais alto é o topo da montanha, mais comida esta possuirá.
O terreno que os macacos exploram representa a paisagem da função de adaptação, portanto, a solução para o problema corresponde à montanha mais elevada (aqui consideramos o problema de maximização global). A partir da sua posição atual, cada macaco se move para cima até atingir o cume da montanha. O processo de ascensão tem como objetivo a melhoria contínua do valor da função objetivo. Depois, o macaco realiza uma série de saltos locais em uma direção aleatória, na tentativa de encontrar uma montanha mais alta, e o movimento ascendente é retomado. Após uma quantidade determinada de ascensões e saltos locais, o macaco presume ter explorado adequadamente a paisagem circundante à sua posição de origem.
Para explorar uma nova região do espaço de busca, o macaco executa um salto global longo. As ações mencionadas são repetidas um número pré-definido de vezes conforme os parâmetros do algoritmo. A solução é proclamada como sendo o pico mais alto encontrado por uma população específica de macacos. No entanto, o MA gasta um tempo computacional substancial procurando soluções locais ideais durante o processo de escalada. O processo de salto global pode acelerar a taxa de convergência do algoritmo. O objetivo deste processo é incentivar os macacos a descobrirem novas oportunidades de pesquisa para evitar que fiquem presos na pesquisa local. O algoritmo tem vantagens como estrutura simples, fiabilidade relativamente alta e eficiente na busca de soluções ótimas locais.
O MA é um novo tipo de algoritmo evolutivo capaz de resolver vários problemas complexos de otimização caracterizados por não-linearidade, não-diferenciabilidade e alta dimensionalidade. A distinção em relação a outros algoritmos é que o tempo gasto pelo MA é principalmente dedicado à utilização do processo de ganho de altura para encontrar soluções locais ideais. Na seção seguinte, descreveremos os componentes fundamentais do algoritmo, as soluções propostas, a inicialização, o processo de ganho de altura, o processo de observação e o salto.
2. Descrição do algoritmo
Para facilitar a compreensão do algoritmo do macaco, é mais simples começar com o pseudocódigo.
O pseudocódigo do MA é:
1. Distribuição aleatória dos macacos no espaço de busca.
2. Medições de altitude na posição atual dos macacos.
3. Realização de saltos locais por um número fixo de vezes.
4. Caso o novo pico encontrado seja mais elevado que o obtido no passo 3, realização de saltos locais a partir desse ponto.
5. Se o limite para o número de saltos locais for alcançado e nenhum novo pico for identificado, realizar um salto global.
6. Após o passo 5, retomar ao passo 3.
7. Repetir a partir do passo 2 até que se atinja o critério de parada estabelecido.
Agora, vamos analisar cada item do pseudocódigo de forma mais detalhada.
1. No início do processo de otimização, o espaço de busca é desconhecido pelos macacos. Os animais são distribuídos aleatoriamente no território inexplorado, uma vez que a probabilidade de encontrar alimento é igual em todos os lugares.
2. O processo de medição da altura onde os macacos estão localizados corresponde à aplicação da função de adaptação (ou função fitness).
3. Ao realizar saltos locais, há um limite definido para o seu número, conforme especificado nos parâmetros do algoritmo. Isso implica que o macaco tenta melhorar sua posição atual ao fazer pequenos saltos locais na área de busca por alimentos. Se uma nova fonte de alimento encontrada for melhor, avançamos para a etapa 4.
4. Uma vez que a nova fonte de alimento foi identificada, o contador de saltos locais é reiniciado. Agora, a busca por uma nova fonte de alimento será feita a partir desta posição.
5. Saltos locais podem não ser suficientes para localizar uma nova fonte de alimento de maneira mais eficaz. Quando isso acontece, o macaco conclui que a atual região de busca foi totalmente explorada, sendo necessário buscar um novo local, porém mais distante. Surge então a questão: em que direção dar o próximo salto? A proposta do algoritmo é utilizar o centro de coordenadas de todos os macacos, garantindo uma espécie de comunicação entre eles no bando: os macacos podem emitir sons altos e, graças a sua audição espacial aguçada, são capazes de determinar a posição exata dos demais. Conhecendo a posição de seus congêneres (que não estarão em lugares onde não há comida), é possível estimar um novo ponto ideal para a localização de alimento, e é nessa direção que o salto deve ser dado.
No algoritmo original proposto pelos autores, o macaco executa um salto global ao longo de uma linha que passa pelo centro de coordenadas de todos os macacos e pela posição atual do animal. A direção do salto pode ser tanto em direção ao centro de coordenadas quanto no sentido oposto. No entanto, realizar um salto na direção oposta ao centro contradiz a lógica de buscar alimentos com base nas coordenadas aproximadas de todos os macacos, algo que meus experimentos com o algoritmo confirmaram - na verdade, há uma probabilidade de 50% de se afastar do ótimo global.
A experiência mostrou que é mais proveitoso ultrapassar o centro de coordenadas com o salto do que não saltar o suficiente ou saltar na direção oposta. Não ocorre uma concentração de todos os macacos em um único ponto, mesmo que essa lógica possa sugerir isso à primeira vista. De fato, ao esgotar o limite de saltos locais, os macacos saltam além do centro, provocando assim uma rotação na posição de todos os macacos na população. Se imaginarmos os macacos seguindo este algoritmo, veremos um grupo de animais saltando periodicamente através do centro geométrico do bando, enquanto o bando como um todo se desloca coletivamente em direção a uma fonte de alimento mais rica. Este "efeito de deslocamento do bando" é claramente visível na animação do algoritmo (o algoritmo original não possui este efeito e apresenta resultados inferiores).
6. Depois de realizar um salto global, o macaco começa a precisar a posição da fonte de alimento no novo local. O processo continua até que o critério de parada seja atingido.
A ideia principal do algoritmo pode ser facilmente representada em um único diagrama. O movimento do macaco é indicado por círculos numerados na Figura 1. Cada número corresponde a uma nova posição do macaco. Pequenos círculos amarelos representam tentativas fracassadas de saltos locais. O número 6 indica a posição na qual o limite de saltos locais foi atingido e nenhuma posição melhor foi encontrada. Círculos sem números simbolizam as posições dos outros membros do bando. O centro geométrico das coordenadas do bando é representado por um pequeno círculo com as coordenadas (x,y).
Figura 1. Diagrama do movimento do macaco no bando.
Passamos agora para a análise do código do MA.
Um macaco em um bando pode ser convenientemente representado pela estrutura S_Monkey. A estrutura contém o array c [] com as coordenadas atuais, o array cB [] com as melhores coordenadas do alimento (é a partir da posição com essas coordenadas que os saltos locais acontecem), h e hB representam o valor da altura do ponto atual e o valor do ponto mais alto, respectivamente. lCNT é o contador de saltos locais, que limita a quantidade de tentativas para melhorar a localização.
//—————————————————————————————————————————————————————————————————————————————— struct S_Monkey { double c []; //coordinates double cB []; //best coordinates double h; //height of the mountain double hB; //best height of the mountain int lCNT; //local search counter }; //——————————————————————————————————————————————————————————————————————————————
A classe do algoritmo do macaco, C_AO_MA, não possui características particulares que a diferenciam dos algoritmos que foram analisados anteriormente. Um bando de macacos é representado na classe como um array de estruturas m []. As declarações de métodos e membros na classe são compactas em termos de volume de código, uma vez que o algoritmo é conciso e não inclui a necessidade de classificação, como em muitos outros algoritmos de otimização. Necessitaremos de arrays para definir o máximo, o mínimo e o passo dos parâmetros que estão sendo otimizados, e também variáveis constantes para transferir os parâmetros externos do algoritmo para eles. Vamos agora proceder à descrição dos métodos onde a lógica principal do MA está contida.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_MA { //---------------------------------------------------------------------------- public: S_Monkey m []; //monkeys public: double rangeMax []; //maximum search range public: double rangeMin []; //minimum search range public: double rangeStep []; //step search public: double cB []; //best coordinates public: double hB; //best height of the mountain public: void Init (const int coordNumberP, //coordinates number const int monkeysNumberP, //monkeys number const double bCoefficientP, //local search coefficient const double vCoefficientP, //jump coefficient const int jumpsNumberP); //jumps number public: void Moving (); public: void Revision (); //---------------------------------------------------------------------------- private: int coordNumber; //coordinates number private: int monkeysNumber; //monkeys number private: double b []; //local search coefficient private: double v []; //jump coefficient private: double bCoefficient; //local search coefficient private: double vCoefficient; //jump coefficient private: double jumpsNumber; //jumps number private: double cc []; //coordinate center private: bool revision; private: double SeInDiSp (double In, double InMin, double InMax, double Step); private: double RNDfromCI (double min, double max); private: double Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool revers); }; //——————————————————————————————————————————————————————————————————————————————
O método público Init () é destinado à inicialização do algoritmo. Aqui, definimos os tamanhos dos arrays. Inicializaremos o índice de qualidade do melhor território encontrado por um macaco com o menor número possível em double, e faremos o mesmo com as variáveis correspondentes no array de estruturas do MA.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_MA::Init (const int coordNumberP, //coordinates number const int monkeysNumberP, //monkeys number const double bCoefficientP, //local search coefficient const double vCoefficientP, //jump coefficient const int jumpsNumberP) //jumps number { MathSrand ((int)GetMicrosecondCount ()); // reset of the generator hB = -DBL_MAX; revision = false; coordNumber = coordNumberP; monkeysNumber = monkeysNumberP; bCoefficient = bCoefficientP; vCoefficient = vCoefficientP; jumpsNumber = jumpsNumberP; ArrayResize (rangeMax, coordNumber); ArrayResize (rangeMin, coordNumber); ArrayResize (rangeStep, coordNumber); ArrayResize (b, coordNumber); ArrayResize (v, coordNumber); ArrayResize (cc, coordNumber); ArrayResize (m, monkeysNumber); for (int i = 0; i < monkeysNumber; i++) { ArrayResize (m [i].c, coordNumber); ArrayResize (m [i].cB, coordNumber); m [i].h = -DBL_MAX; m [i].hB = -DBL_MAX; m [i].lCNT = 0; } ArrayResize (cB, coordNumber); } //——————————————————————————————————————————————————————————————————————————————
O primeiro método que é compulsório executar em cada iteração é o método público Moving(), que executa a lógica dos saltos dos macacos. Na primeira iteração, quando o sinalizador revision é falso, é necessário inicializar os agentes com valores aleatórios dentro do intervalo de coordenadas do espaço a ser explorado, o que corresponde a posicionar os macacos aleatoriamente no território habitado pelo grupo. Para diminuir a repetição de operações, tais como os cálculos das contagens de saltos globais e locais, armazenaremos os valores das quantidades correspondentes às coordenadas (cada coordenada pode ter sua própria dimensão) nos arrays v [] e b []. O contador de saltos locais de cada macaco será redefinido para zero.
//---------------------------------------------------------------------------- if (!revision) { hB = -DBL_MAX; for (int monk = 0; monk < monkeysNumber; monk++) { for (int c = 0; c < coordNumber; c++) { m [monk].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]); m [monk].c [c] = SeInDiSp (m [monk].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); m [monk].h = -DBL_MAX; m [monk].hB = -DBL_MAX; m [monk].lCNT = 0; } } for (int c = 0; c < coordNumber; c++) { v [c] = (rangeMax [c] - rangeMin [c]) * vCoefficient; b [c] = (rangeMax [c] - rangeMin [c]) * bCoefficient; } revision = true; }
Para calcular o centro das coordenadas de todos os macacos, utilizamos o array cc [], cuja dimensão corresponde ao número de coordenadas. O cálculo consiste em somar as coordenadas dos macacos e dividir o somatório pelo tamanho da população. Desta forma, o centro das coordenadas representa a média aritmética das coordenadas.
//calculate the coordinate center of the monkeys---------------------------- for (int c = 0; c < coordNumber; c++) { cc [c] = 0.0; for (int monk = 0; monk < monkeysNumber; monk++) { cc [c] += m [monk].cB [c]; } cc [c] /= monkeysNumber; }
Seguindo o pseudocódigo, se o limite de saltos locais não tiver sido alcançado, o macaco irá saltar a partir de sua localização atual para todas as direções com igual probabilidade. O raio do círculo de saltos locais é determinado pelo coeficiente de saltos locais, que é recalculado de acordo com a dimensão do array de coordenadas b [].
//local jump-------------------------------------------------------------- if (m [monk].lCNT < jumpsNumber) //local jump { for (int c = 0; c < coordNumber; c++) { m [monk].c [c] = RNDfromCI (m [monk].cB [c] - b [c], m [monk].cB [c] + b [c]); m [monk].c [c] = SeInDiSp (m [monk].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } }
Passamos agora para uma parte crucial da lógica do MA - a performance do algoritmo depende, em grande medida, da implementação dos saltos globais. Diferentes autores abordam este aspecto de várias maneiras, sugerindo uma gama de soluções. Os saltos locais, conforme evidenciado por estudos, têm pouco impacto na convergência do algoritmo; são os saltos globais que determinam a habilidade do algoritmo de "escapar" dos extremos locais. Meus experimentos com saltos globais revelaram apenas uma abordagem eficaz especificamente para este algoritmo que melhora os resultados.
Anteriormente, discutimos a conveniência de saltar em direção ao centro das coordenadas, sendo preferível que o ponto final esteja além do centro, em vez de entre o centro e as coordenadas atuais. Esta estratégia envolve a aplicação da fórmula de voo de Lévy, a qual descrevemos em detalhes no artigo dedicado ao algoritmo de busca do cuco (COA).
Figura 2. Gráficos da função voo de Lévy dependendo do expoente.
As coordenadas do macaco são calculadas usando a seguinte fórmula:
m [monk].c [c] = cc [c] + v [c] * pow (r2, -2.0);
Onde:
cc [c] — coordenada do centro de coordenadas,
v [c] — coeficiente do raio do salto convertido para a dimensionalidade do espaço de busca,
r2 — número no intervalo de 1 a 20.
Ao aplicar o voo de Lévy nesta operação, alcançamos uma maior probabilidade de um macaco aterrar nas proximidades do centro de coordenadas ao saltar, e uma menor probabilidade de terminar muito além do centro. Assim, estabelecemos um equilíbrio entre a reconhecimento e a exploração na busca, descobrindo novas fontes de alimento. Se a coordenada resultante ultrapassar o limite inferior do intervalo permitido, a coordenada será deslocada para uma distância correspondente ao limite superior do intervalo, e o mesmo será feito ao ultrapassar o limite superior. Ao terminar os cálculos de coordenadas, verificamos se o valor obtido cumpre com os limites e a etapa de reconhecimento.
//global jump------------------------------------------------------------- for (int c = 0; c < coordNumber; c++) { r1 = RNDfromCI (0.0, 1.0); r1 = r1 > 0.5 ? 1.0 : -1.0; r2 = RNDfromCI (1.0, 20.0); m [monk].c [c] = cc [c] + v [c] * pow (r2, -2.0); if (m [monk].c [c] < rangeMin [c]) m [monk].c [c] = rangeMax [c] - (rangeMin [c] - m [monk].c [c]); if (m [monk].c [c] > rangeMax [c]) m [monk].c [c] = rangeMin [c] + (m [monk].c [c] - rangeMax [c]); m [monk].c [c] = SeInDiSp (m [monk].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); }
Após a realização de saltos locais/globais, incrementamos o contador de saltos em uma unidade.
m [monk].lCNT++;
O segundo método público é invocado em cada iteração após o cálculo da função de adaptação, método Revision(). Este método atualiza a solução global se uma melhor for encontrada. A lógica de processamento dos resultados após os saltos locais e globais difere entre si: em um salto local, é necessário verificar se a posição atual foi melhorada e atualizá-la (nos saltos das próximas iterações são feitos a partir deste novo local), enquanto com os saltos globais não há verificação de melhoria - de qualquer forma, os novos saltos serão realizados a partir deste local.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_MA::Revision () { for (int monk = 0; monk < monkeysNumber; monk++) { if (m [monk].h > hB) { hB = m [monk].h; ArrayCopy (cB, m [monk].c, 0, 0, WHOLE_ARRAY); } if (m [monk].lCNT <= jumpsNumber) //local jump { if (m [monk].h > m [monk].hB) { m [monk].hB = m [monk].h; ArrayCopy (m [monk].cB, m [monk].c, 0, 0, WHOLE_ARRAY); m [monk].lCNT = 0; } } else //global jump { m [monk].hB = m [monk].h; ArrayCopy (m [monk].cB, m [monk].c, 0, 0, WHOLE_ARRAY); m [monk].lCNT = 0; } } } //——————————————————————————————————————————————————————————————————————————————
Ao concluir a descrição do código, é possível observar a similaridade das abordagens deste algoritmo com um conjunto de algoritmos de inteligência de enxame, como o enxame de partículas (PSO) e outros, que seguem uma lógica de estratégia de busca semelhante.
3. Resultado dos testes
Saída do resultado do algoritmo do macaco na bancada de teste:
2023.02.22 19:36:21.841 Test_AO_MA (EURUSD,M1) C_AO_MA:50;0.01;0.9;50
2023.02.22 19:36:21.841 Test_AO_MA (EURUSD,M1) =============================
2023.02.22 19:36:26.877 Test_AO_MA (EURUSD,M1) 5 Rastrigin's; Func runs 10000 result: 64.89788419898215
2023.02.22 19:36:26.878 Test_AO_MA (EURUSD,M1) Score: 0.80412
2023.02.22 19:36:36.734 Test_AO_MA (EURUSD,M1) 25 Rastrigin's; Func runs 10000 result: 55.57339368461394
2023.02.22 19:36:36.734 Test_AO_MA (EURUSD,M1) Score: 0.68859
2023.02.22 19:37:34.865 Test_AO_MA (EURUSD,M1) 500 Rastrigin's; Func runs 10000 result: 41.41612351844293
2023.02.22 19:37:34.865 Test_AO_MA (EURUSD,M1) Score: 0.51317
2023.02.22 19:37:34.865 Test_AO_MA (EURUSD,M1) =============================
2023.02.22 19:37:39.165 Test_AO_MA (EURUSD,M1) 5 Forest's; Func runs 10000 result: 0.4307085210424681
2023.02.22 19:37:39.165 Test_AO_MA (EURUSD,M1) Score: 0.24363
2023.02.22 19:37:49.599 Test_AO_MA (EURUSD,M1) 25 Forest's; Func runs 10000 result: 0.19875891413613866
2023.02.22 19:37:49.599 Test_AO_MA (EURUSD,M1) Score: 0.11243
2023.02.22 19:38:47.793 Test_AO_MA (EURUSD,M1) 500 Forest's; Func runs 10000 result: 0.06286212143582881
2023.02.22 19:38:47.793 Test_AO_MA (EURUSD,M1) Score: 0.03556
2023.02.22 19:38:47.793 Test_AO_MA (EURUSD,M1) =============================
2023.02.22 19:38:53.947 Test_AO_MA (EURUSD,M1) 5 Megacity's; Func runs 10000 result: 2.8
2023.02.22 19:38:53.947 Test_AO_MA (EURUSD,M1) Score: 0.23333
2023.02.22 19:39:03.336 Test_AO_MA (EURUSD,M1) 25 Megacity's; Func runs 10000 result: 0.96
2023.02.22 19:39:03.336 Test_AO_MA (EURUSD,M1) Score: 0.08000
2023.02.22 19:40:02.068 Test_AO_MA (EURUSD,M1) 500 Megacity's; Func runs 10000 result: 0.34120000000000006
2023.02.22 19:40:02.068 Test_AO_MA (EURUSD,M1) Score: 0.02843
Ao observar a visualização do desempenho do algoritmo nas funções de teste, é importante destacar a ausência de padrões em seu comportamento, o que é bastante semelhante ao algoritmo RND. Há uma ligeira concentração de agentes em extremos locais, que evidencia as tentativas do algoritmo em refinar a solução, mas não há engarrafamentos óbvios.
MA na função de teste Rastrigin.
MA na função de teste Forest.
MA na função de teste Megacity.
Agora, vamos à análise dos resultados dos testes. Com base na pontuação acumulada, o algoritmo MA se posiciona na parte inferior da tabela, entre GSA e FSS. Vale ressaltar uma circunstância: como o teste de algoritmos é construído com base no princípio da análise comparativa, na qual as pontuações dos resultados são valores relativos entre o melhor e o pior desempenho, a presença de um algoritmo com excelentes resultados em um teste e falhas em outros às vezes causa uma alteração nos indicadores dos demais participantes do teste.
No entanto, os resultados do MA foram tais que não exigiram um recálculo de qualquer um dos resultados dos outros participantes do teste na tabela. O MA não tem um único resultado de teste que seja o pior, embora haja algoritmos na tabela com resultados relativos nulos, mas que possuem uma classificação mais alta (exemplo: GSA). Portanto, podemos fazer algumas conclusões: embora o algoritmo se comporte de maneira bastante discreta, sua capacidade de busca não é tão expressiva quanto gostaríamos. Contudo, o algoritmo demonstra resultados estáveis, o que é uma qualidade positiva para algoritmos de otimização.
AO | Description | Rastrigin | Rastrigin final | Forest | Forest final | Megacity (discrete) | Megacity final | Final result | ||||||
10 params (5 F) | 50 params (25 F) | 1000 params (500 F) | 10 params (5 F) | 50 params (25 F) | 1000 params (500 F) | 10 params (5 F) | 50 params (25 F) | 1000 params (500 F) | ||||||
HS | busca de harmonia | 1,00000 | 1,00000 | 0,57048 | 2,57048 | 1,00000 | 0,98931 | 0,57917 | 2,56848 | 1,00000 | 1,00000 | 1,00000 | 3,00000 | 100,000 |
ACOm | otimização de colônia de formigas M | 0,34724 | 0,18876 | 0,20182 | 0,73782 | 0,85966 | 1,00000 | 1,00000 | 2,85966 | 1,00000 | 0,88484 | 0,13497 | 2,01981 | 68,094 |
IWO | otimização invasiva de ervas daninhas | 0,96140 | 0,70405 | 0,35295 | 2,01840 | 0,68718 | 0,46349 | 0,41071 | 1,56138 | 0,75912 | 0,39732 | 0,80145 | 1,95789 | 67,087 |
COAm | algoritmo de otimização de cuco M | 0,92701 | 0,49111 | 0,30792 | 1,72604 | 0,55451 | 0,34034 | 0,21362 | 1,10847 | 0,67153 | 0,30326 | 0,41127 | 1,38606 | 50,422 |
FAm | algoritmo de vaga-lumes M | 0,60020 | 0,35662 | 0,20290 | 1,15972 | 0,47632 | 0,42299 | 0,64360 | 1,54291 | 0,21167 | 0,25143 | 0,84884 | 1,31194 | 47,816 |
BA | algoritmo do morcego | 0,40658 | 0,66918 | 1,00000 | 2,07576 | 0,15275 | 0,17477 | 0,33595 | 0,66347 | 0,15329 | 0,06334 | 0,41821 | 0,63484 | 39,711 |
ABC | colônia artificial de abelhas | 0,78424 | 0,34335 | 0,24656 | 1,37415 | 0,50591 | 0,21455 | 0,17249 | 0,89295 | 0,47444 | 0,23609 | 0,33526 | 1,04579 | 38,937 |
BFO | otimização de forrageamento bacteriano | 0,67422 | 0,32496 | 0,13988 | 1,13906 | 0,35462 | 0,26623 | 0,26695 | 0,88780 | 0,42336 | 0,30519 | 0,45578 | 1,18433 | 37,651 |
GSA | algoritmo de busca gravitacional | 0,70396 | 0,47456 | 0,00000 | 1,17852 | 0,26854 | 0,36416 | 0,42921 | 1,06191 | 0,51095 | 0,32436 | 0,00000 | 0,83531 | 35,937 |
MA | algoritmo do macaco | 0,33300 | 0,35107 | 0,17340 | 0,85747 | 0,03684 | 0,07891 | 0,11546 | 0,23121 | 0,05838 | 0,00383 | 0,25809 | 0,32030 | 14,848 |
FSS | busca por cardume de peixes | 0,46965 | 0,26591 | 0,13383 | 0,86939 | 0,06711 | 0,05013 | 0,08423 | 0,20147 | 0,00000 | 0,00959 | 0,19942 | 0,20901 | 13,215 |
PSO | otimização de enxame de partículas | 0,20515 | 0,08606 | 0,08448 | 0,37569 | 0,13192 | 0,10486 | 0,28099 | 0,51777 | 0,08028 | 0,21100 | 0,04711 | 0,33839 | 10,208 |
RND | aleatório | 0,16881 | 0,10226 | 0,09495 | 0,36602 | 0,07413 | 0,04810 | 0,06094 | 0,18317 | 0,00000 | 0,00000 | 0,11850 | 0,11850 | 5,469 |
GWO | otimizador lobo-cinzento | 0,00000 | 0,00000 | 0,02672 | 0,02672 | 0,00000 | 0,00000 | 0,00000 | 0,00000 | 0,18977 | 0,03645 | 0,06156 | 0,28778 | 1,000 |
Conclusões
O MA clássico consiste primordialmente no uso do processo de ganho de altura para identificar soluções ótimas locais. O passo ou incremento no ganho de altura desempenha um papel crucial na precisão da aproximação da solução local. Quanto menor for esse passo durante os saltos locais, maior será a precisão da solução, mas mais iterações serão necessárias para encontrar o ótimo global. Para minimizar o tempo de computação através da redução do número de iterações, muitos pesquisadores sugerem o uso de outros métodos de otimização, como ABC, COA, IWO nos estágios iniciais da otimização, recorrendo ao MA apenas posteriormente para refinar a solução global. Discordo desse enfoque, acredito que é mais apropriado utilizar de imediato os algoritmos mencionados em substituição ao MA, embora o potencial de desenvolvimento do MA esteja presente e sirva como estímulo para futuras pesquisas e estudos.
O MA é um algoritmo populacional que tem suas origens na natureza. Como muitos outros algoritmos metaheurísticos, este algoritmo pertence à categoria de evolutivos e é capaz de solucionar uma série de problemas de otimização, que incluem não linearidade, não diferenciabilidade, alta dimensionalidade do espaço de busca e alta taxa de convergência. Outra vantagem do MA é que ele é controlado por um pequeno número de parâmetros, o que o torna relativamente fácil de implementar. Apesar da estabilidade dos resultados, a baixa velocidade de convergência impede que o MA seja recomendado para a resolução de problemas com alta complexidade computacional, uma vez que exige um número significativo de iterações. Existem muitos outros algoritmos capazes de realizar a mesma tarefa em menos tempo (ou seja, com um menor número de iterações).
Gostaria de acrescentar em conclusão que, apesar de inúmeros experimentos realizados, a versão clássica do algoritmo não conseguiu subir acima da terceira posição mais baixa na tabela de classificação, ficou presa em extremos locais e performou muito mal em funções discretas. Por isso, não havia um desejo particular de escrever um artigo sobre isso. No entanto, empreendi tentativas de melhorá-lo, uma das quais mostrou algumas melhorias nas taxas de convergência e aumentou a estabilidade dos resultados através do uso de viés de probabilidade nos saltos globais, além de revisar o princípio dos próprios saltos globais. Muitos pesquisadores do MA apontam para a necessidade de modernizar o algoritmo, razão pela qual existem muitas modificações do mesmo. Não era meu objetivo considerar todas as variações do MA, já que o algoritmo em si não é excepcional, é mais uma variação do tema do enxame de partículas (PSO). O resultado dos experimentos foi a versão final do algoritmo apresentada neste artigo, sem a marcação adicional 'm' (modificado).
O histograma que apresenta os resultados do teste de algoritmo está na Figura 3.
Figura 3. Histograma dos resultados finais dos testes dos algoritmos.
Prós e contras do algoritmo do macaco (MA):
1. Simplicidade de implementação.
2. Boa escalabilidade, apesar da baixa taxa de convergência.
3. Bom desempenho em funções discretas.
4. Poucos parâmetros externos.
Contras:
1. Baixa taxa de convergência.
2. Grande número de iterações de busca.
3. Baixa eficiência geral.
Para cada artigo, eu anexo um arquivo que contém versões atualizadas dos códigos dos algoritmos para todos os artigos anteriores. O artigo é a experiência acumulada do autor e opinião pessoal, as conclusões e julgamentos são baseados em experimentos.
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/12212
- 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