Algoritmos de otimização de população: Resistência a ficar preso em extremos locais (Parte II)

Conteúdo

1. Algoritmos
2. Melhorando o agente para BGA
3. Conclusões

Como parte de nossa pesquisa, investigamos a robustez dos algoritmos de otimização de população e sua capacidade de superar armadilhas locais e alcançar máximos globais em uma variedade de funções de teste. No artigo anterior, analisamos algoritmos que mostraram resultados modestos no ranking. Agora é hora de prestar atenção aos melhores desempenhos.

Buscamos realizar uma análise aprofundada de cada um desses algoritmos, identificando suas vantagens e características únicas. Nosso objetivo é entender quais estratégias e abordagens tornam esses algoritmos bem-sucedidos em superar complexidades e alcançar metas de otimização global.

Esta fase da pesquisa nos permitirá não apenas compreender melhor a resiliência dos algoritmos de população em ficar presos em armadilhas locais, mas também identificar os fatores-chave que contribuem para seu sucesso diante de funções de teste diversas e complexas. Meus esforços visam aumentar a compreensão de como esses algoritmos podem ser otimizados e aprimorados, e identificar oportunidades para seu uso conjunto e hibridização para resolver efetivamente vários problemas de otimização no futuro.

1. Algoritmos

Vamos continuar estudando os algoritmos que ocupam as principais posições em nossa tabela de comparação. Eles definitivamente merecem uma consideração e atenção mais detalhadas. Vamos nos aprofundar em uma análise detalhada de suas características para descobrir todos os aspectos que os tornam tão valiosos e eficazes na resolução de problemas complexos de otimização.

Abaixo estão os relatórios de operação dos algoritmos, que devem ser lidos da seguinte forma:

• C_AO_FSS:50;0.01;0.8 - nome do algoritmo e parâmetros externos
  
• 5 Hilly's - nome da função de teste e seu número no teste
  
•  Execuções da função: 10000 - número de execuções
  
• resultado: 0.32457068874346456 - resultado obtido, onde 0.0 é o mínimo da função de teste e 1.0 é o máximo. Quanto maior o valor, melhor
  
• Pontuação total: 1.33084 - valor total dos pontos obtidos. Quanto maior o valor, melhor

Estratégias Evolutivas, (P+O)ES

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.45574011563217454
25 Hilly's; Execuções da função: 10000; resultado: 0.5979154724556998
500 Hilly's; Execuções da função: 10000; resultado: 0.3415203622112476
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.18929181937830403
25 Forest's; Execuções da função: 10000; resultado: 0.1837517532554242
500 Forest's; Execuções da função: 10000; resultado: 0.15411134176683486
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.10153846153846155
25 Megacity's; Execuções da função: 10000; resultado: 0.12030769230769231
500 Megacity's; Execuções da função: 10000; resultado: 0.08793846153846216
=============================
Pontuação total: 2.23212

Ao contrário de seu irmão mais novo (PO)ES, o (P+O)ES é altamente ativo no espaço de busca, especialmente na função Hilly suave, onde a população é dividida em vários grupos, cada um explorando diferentes áreas. No entanto, por algum motivo, sua eficiência diminui na função Forest suave, enquanto na função discreta seu desempenho é fraco (apenas a colina mais próxima é alcançada). Em geral, o algoritmo é muito interessante em funções diferenciáveis suaves, mas há uma tendência clara a ficar preso. Além disso, faltam capacidades que refinam o resultado.

Otimização do Lobo Cinzento (GWO)

C_AO_GWO:50;10
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.5385541648909985
25 Hilly's; Execuções da função: 10000; resultado: 0.33060651191769963
500 Hilly's; Execuções da função: 10000; resultado: 0.25796885816873344
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.33256641908450685
25 Forest's; Execuções da função: 10000; resultado: 0.2040563379483599
500 Forest's; Execuções da função: 10000; resultado: 0.15278428644972566
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.2784615384615384
25 Megacity's; Execuções da função: 10000; resultado: 0.1587692307692308
500 Megacity's; Execuções da função: 10000; resultado: 0.133153846153847
=============================
Pontuação total: 2.38692

Um grupo de lobos do algoritmo GWO avança pelas vastas extensões do mundo virtual, espalhando-se rapidamente em todas as direções em várias funções de teste. Essa propriedade pode ser usada de forma eficaz nas iterações iniciais, especialmente se o algoritmo for combinado com outro método que possa melhorar e complementar as soluções encontradas. As excelentes habilidades de pesquisa do grupo falam de seu potencial, mas, infelizmente, a precisão na identificação de áreas continua sendo seu ponto fraco. Curiosamente, o algoritmo mostrou resultados ainda melhores do que no teste convencional com a distribuição uniforme de agentes.

Algoritmo Shuffled Frog-Leaping (SFL)

C_AO_SFL:50;25;15;5;0.7
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.5009251084703008
25 Hilly's; Execuções da função: 10000; resultado: 0.3175649450809088
500 Hilly's; Execuções da função: 10000; resultado: 0.25514153268631673
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.4165336325557746
25 Forest's; Execuções da função: 10000; resultado: 0.21617658684174407
500 Forest's; Execuções da função: 10000; resultado: 0.15782134182434096
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.2892307692307692
25 Megacity's; Execuções da função: 10000; resultado: 0.14892307692307696
500 Megacity's; Execuções da função: 10000; resultado: 0.10636923076923148
=============================
Pontuação total: 2.40869

O algoritmo SFL demonstrou uma gama ainda mais ampla de capacidades de propagação em diferentes direções do espaço de busca, mesmo em uma função Megacity discreta, em comparação com o algoritmo anterior na lista. O SFL é capaz de alcançar até mesmo regiões de máximo global dentro de um número dado de iterações. No entanto, a precisão de refinar as soluções encontradas não é o ponto forte do SFL. Semelhante ao GWO, o algoritmo apresentou resultados superiores aos dos testes convencionais.

Algoritmo de Busca Aleatória (RND)

C_AO_RND:50
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.5024853724464499
25 Hilly's; Execuções da função: 10000; resultado: 0.3284469438564529
500 Hilly's; Execuções da função: 10000; resultado: 0.2600678718550755
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.3989291459162246
25 Forest's; Execuções da função: 10000; resultado: 0.22913381881119183
500 Forest's; Execuções da função: 10000; resultado: 0.16727444696703453
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.2753846153846154
25 Megacity's; Execuções da função: 10000; resultado: 0.14861538461538465
500 Megacity's; Execuções da função: 10000; resultado: 0.09890769230769311
=============================
Pontuação total: 2.40925

Este método de otimização mais simples superou muitos participantes respeitados e bem conhecidos nesta competição única. Como você deve se lembrar, a estratégia do algoritmo RND é 50% de probabilidade: selecionar a coordenada de um indivíduo aleatoriamente escolhido da população, ou gerar uma coordenada aleatória com uma distribuição uniforme. No entanto, isso permitiu que o algoritmo subisse para o meio da lista de participantes. Isso se tornou possível devido às suas amplas capacidades de exploração do espaço, embora não seja necessário falar sobre precisão neste caso.

Evolução de Grupos Sociais (ESG)

C_AO_ESG:200:100:0.1:2.0:10.0
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.3695915822772909
25 Hilly's; Execuções da função: 10000; resultado: 0.3396716009249312
500 Hilly's; Execuções da função: 10000; resultado: 0.2727013729189837
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.2956316169252261
25 Forest's; Execuções da função: 10000; resultado: 0.2875217303660672
500 Forest's; Execuções da função: 10000; resultado: 0.16124201361354124
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.30769230769230765
25 Megacity's; Execuções da função: 10000; resultado: 0.306153846153846
500 Megacity's; Execuções da função: 10000; resultado: 0.13183076923077003
=============================
Pontuação total: 2.47204

O algoritmo ESG demonstra boas capacidades em explorar o espaço de busca, dividindo-o em grupos característicos. No entanto, ele deixa de lado regiões distantes do espaço, o que pode levar a problemas ao explorar toda a escala do problema. Também há sinais de estagnação em extremos locais significativos, o que pode dificultar a obtenção de um ótimo global. Apesar disso, o algoritmo demonstra sucesso significativo ao lidar com a função Megacity discreta, destacando seu potencial em certas condições e tarefas.

Algoritmo Intelligent Water Drops (IWDm)

C_AO_IWDm:50;10;3.0
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.4883273901756646
25 Hilly's; Execuções da função: 10000; resultado: 0.34290016593207995
500 Hilly's; Execuções da função: 10000; resultado: 0.2581256124908963
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.5119191969436073
25 Forest's; Execuções da função: 10000; resultado: 0.2564038040639046
500 Forest's; Execuções da função: 10000; resultado: 0.1675925588605327
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.34153846153846157
25 Megacity's; Execuções da função: 10000; resultado: 0.15784615384615389
500 Megacity's; Execuções da função: 10000; resultado: 0.09889230769230851
=============================
Pontuação total: 2.62355

Como as correntes de um rio furioso, o algoritmo IWDm desliza rapidamente pelo espaço de busca, alcançando rapidamente a região do máximo global e demonstrando excelentes capacidades de busca. No entanto, vale notar que esse algoritmo não possui qualidades suficientemente esclarecedoras, o que pode dificultar a determinação precisa da solução ótima.

Na classificação convencional, esse algoritmo não está entre os melhores, mas neste teste específico teve um desempenho impressionante em comparação com outros algoritmos. O IWDm pode ser recomendado para uso nas etapas iniciais da otimização, para então passar para algoritmos mais precisos, enriquecendo e aprimorando o processo de otimização como um todo.

Algoritmo Particle Swarm (PSO)

C_AO_PSO:50;0.8;0.4;0.4
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.5548169875802522
25 Hilly's; Execuções da função: 10000; resultado: 0.3407594364160912
500 Hilly's; Execuções da função: 10000; resultado: 0.2525297014321252
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.4573903259815636
25 Forest's; Execuções da função: 10000; resultado: 0.27561812346057046
500 Forest's; Execuções da função: 10000; resultado: 0.19079124396445962
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.3092307692307693
25 Megacity's; Execuções da função: 10000; resultado: 0.14923076923076928
500 Megacity's; Execuções da função: 10000; resultado: 0.09553846153846236
=============================
Pontuação total: 2.62591

O algoritmo PSO surpreendeu com seus resultados inesperadamente fortes neste experimento, demonstrando uma velocidade ainda maior de movimento em território desconhecido em comparação com o algoritmo IWDm anterior. Esse sucesso repentino pode ser explicado pelo fato de que as partículas no PSO possuem uma velocidade inicial escolhida aleatoriamente na primeira iteração, o que permite que elas deixem rapidamente sua posição original. Os passos iniciais do algoritmo assemelham-se à dança das partículas através do espaço até encontrarem sua harmonia especial. Infelizmente, essa harmonia nem sempre leva a um ótimo global. A falta de qualidades esclarecedoras desacelera a obtenção de uma solução ideal.

Assim como o IWDm, o PSO pode ser recomendado para uso nas etapas iniciais da otimização, onde sua capacidade de explorar rapidamente o espaço de busca pode ser a chave para descobrir soluções promissoras.

Algoritmo Bat (BA)

C_AO_BA:50;0.0;1.0;0.0;1.5;0.0;1.0;0.3;0.3
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.5127608047854995
25 Hilly's; Execuções da função: 10000; resultado: 0.4239882910506281
500 Hilly's; Execuções da função: 10000; resultado: 0.3127353914885268
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.4355521825589907
25 Forest's; Execuções da função: 10000; resultado: 0.29303187383086005
500 Forest's; Execuções da função: 10000; resultado: 0.19433130092541523
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.28769230769230764
25 Megacity's; Execuções da função: 10000; resultado: 0.16030769230769232
500 Megacity's; Execuções da função: 10000; resultado: 0.10907692307692407
=============================
Pontuação total: 2.72948

Os morcegos no algoritmo BA possuem a incrível propriedade de encontrar rapidamente a região do máximo global, movendo-se instantaneamente nas primeiras iterações. No entanto, a equação dos pulsos sonoros neste método de busca faz com que os movimentos dos morcegos se desvaneçam rapidamente, apesar da necessidade óbvia de continuar a busca. O BA ocupa uma posição baixa nas classificações regulares, mas figura perto do topo da tabela neste desafio.

 Otimização de Ervas Invasivas (IWO)

C_AO_IWO:50;12;5;2;0.2;0.01
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.4570149872637351
25 Hilly's; Execuções da função: 10000; resultado: 0.4252105325836707
500 Hilly's; Execuções da função: 10000; resultado: 0.28299287471456525
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.43322917175445896
25 Forest's; Execuções da função: 10000; resultado: 0.33438950288190694
500 Forest's; Execuções da função: 10000; resultado: 0.18632383795879612
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.3061538461538461
25 Megacity's; Execuções da função: 10000; resultado: 0.24369230769230765
500 Megacity's; Execuções da função: 10000; resultado: 0.12887692307692397
=============================
Pontuação total: 2.79788

O algoritmo Invasive Weed também segue a taxa de propagação como uma função da iteração atual, assim como o Algoritmo de Morcego (BA). No entanto, neste caso, os agentes são capazes de explorar o espaço de maneira mais eficiente e completa, o que permite encontrar soluções ótimas rapidamente e com precisão, levando em consideração as características chave da função e a região do máximo global, em comparação com o BA. Mas, se a distância do ponto de partida ao objetivo for grande, então as ervas não chegam à área do máximo global. Isso é especialmente notável na função Megacity - os agentes ficam presos no extremo significativo mais próximo.

Colônia de Abelhas Artificiais (ABC)

C_AO_ABC:50;45;10;0.1;0.4
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.5969246550857782
25 Hilly's; Execuções da função: 10000; resultado: 0.3899058056869557
500 Hilly's; Execuções da função: 10000; resultado: 0.26574506946962373
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.536535405336652
25 Forest's; Execuções da função: 10000; resultado: 0.29048311417293887
500 Forest's; Execuções da função: 10000; resultado: 0.17322987568991322
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.3307692307692308
25 Megacity's; Execuções da função: 10000; resultado: 0.18492307692307694
500 Megacity's; Execuções da função: 10000; resultado: 0.11512307692307773
=============================
Pontuação total: 2.88364

O comportamento interessante do algoritmo ABC é sua capacidade de dividir uma população em enxames separados que exploram ativamente extremos locais. No entanto, é possível que o algoritmo não possua qualidades esclarecedoras suficientes, o que se reflete em sua posição na tabela de classificação padrão. No entanto, há potencial para melhorar e usar suas capacidades de busca em algoritmos híbridos. A capacidade do algoritmo de encontrar ótimos globais, bem como sua eficiência geral em vários problemas de otimização, pode ser significativamente melhorada com a integração com outros métodos de otimização.

Computação Evolutiva Mental (MEC)

C_AO_MEC:50;10;0.4
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.5566946043237988
25 Hilly's; Execuções da função: 10000; resultado: 0.430203412538813
500 Hilly's; Execuções da função: 10000; resultado: 0.2724348221662864
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.4548936450507163
25 Forest's; Execuções da função: 10000; resultado: 0.3156014530351309
500 Forest's; Execuções da função: 10000; resultado: 0.17625852850331755
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.3415384615384615
25 Megacity's; Execuções da função: 10000; resultado: 0.23107692307692304
500 Megacity's; Execuções da função: 10000; resultado: 0.1186615384615393
=============================
Pontuação total: 2.89736

O algoritmo MEC é incrível em sua velocidade, detectando instantaneamente quase todos os extremos locais significativos e identificando com sucesso a área do máximo global. Apesar do ligeiro atraso em relação ao teste convencional, o MEC continua a demonstrar alta estabilidade e eficiência na busca por soluções ótimas.

Algoritmo de Otimização de Cuco (COAm)

C_AO_COAm:100;40;0.6;0.6;0.63
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.600998666320958
25 Hilly's; Execuções da função: 10000; resultado: 0.42709404776275245
500 Hilly's; Execuções da função: 10000; resultado: 0.26571090745735276
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.5533129896276743
25 Forest's; Execuções da função: 10000; resultado: 0.30413063297063025
500 Forest's; Execuções da função: 10000; resultado: 0.1703031415266755
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.3261538461538461
25 Megacity's; Execuções da função: 10000; resultado: 0.2046153846153847
500 Megacity's; Execuções da função: 10000; resultado: 0.1112615384615393
=============================
Pontuação total: 2.96358

Nosso desempenho médio na tabela convencional do COAm mostra uma velocidade incrível de movimento no espaço de busca, saindo facilmente do mínimo global. No entanto, possui certas dificuldades em ficar preso em extremos locais significativos, impedindo-o de alcançar o máximo global.

Sistema Imunológico Artificial Micro (Micro-AIS)

C_AO_Micro_AIS:50:1:2:0.3
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.6193671060348247
25 Hilly's; Execuções da função: 10000; resultado: 0.4656896752001433
500 Hilly's; Execuções da função: 10000; resultado: 0.24995620778886124
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.7121901446084455
25 Forest's; Execuções da função: 10000; resultado: 0.4254191301238518
500 Forest's; Execuções da função: 10000; resultado: 0.211517515004865
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.2676923076923077
25 Megacity's; Execuções da função: 10000; resultado: 0.16461538461538466
500 Megacity's; Execuções da função: 10000; resultado: 0.10927692307692398
=============================
Pontuação total: 3.22572

O algoritmo Micro-AIS pode identificar uma nuvem muito uniforme criada pelos antígenos, o que dá ao processo uma certa ordem, lembrando mais harmonia do que caos. Apesar disso, suas propriedades esclarecedoras requerem alguma melhoria, embora o algoritmo tenha boas capacidades de busca. No entanto, ele também é suscetível a ficar preso em armadilhas locais.

Busca por Harmonia (HS)

C_AO_HS:50;0.9;0.1;0.2
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.602082991833691
25 Hilly's; Execuções da função: 10000; resultado: 0.5533985889779909
500 Hilly's; Execuções da função: 10000; resultado: 0.2820448101527182
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.6503798132320532
25 Forest's; Execuções da função: 10000; resultado: 0.5104503170911219
500 Forest's; Execuções da função: 10000; resultado: 0.19337757947865844
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.30769230769230765
25 Megacity's; Execuções da função: 10000; resultado: 0.29538461538461525
500 Megacity's; Execuções da função: 10000; resultado: 0.12826153846153937
=============================
Pontuação total: 3.52307

Neste problema específico, a HS demonstra habilidades impressionantes de busca e alta velocidade de movimentação através do espaço em busca de um máximo global. No entanto, ao encontrar o primeiro extremo local significativo, ela diminui a velocidade devido à sua dependência do número da época atual. No entanto, essa deficiência só aparece na função discreta Megacity, enquanto suas capacidades de busca permanecem impressionantes nas funções suaves Hilly e Forest. Na tabela de classificação, a Busca Harmônica ocupa as posições superiores, demonstrando sua eficiência também no teste atual.

Otimização por Dinâmica Espiral (SDOm)

C_AO_SDOm:100;0.5;4.0;10000.0
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.7132463872323508
25 Hilly's; Execuções da função: 10000; resultado: 0.43264564401427485
500 Hilly's; Execuções da função: 10000; resultado: 0.25506574720969816
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.804287574819851
25 Forest's; Execuções da função: 10000; resultado: 0.4249161540200845
500 Forest's; Execuções da função: 10000; resultado: 0.2193817986301354
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.4938461538461539
25 Megacity's; Execuções da função: 10000; resultado: 0.22030769230769232
500 Megacity's; Execuções da função: 10000; resultado: 0.11410769230769328
=============================
Pontuação total: 3.67780

O algoritmo SDOm aparece repentinamente no topo do ranking. Este algoritmo, baseado em oscilações harmônicas, se manifesta de uma maneira muito incomum e única dentro deste experimento, deixando um mistério que é difícil de desvendar. Uma esfera de pêndulo suspensa por um cordão pode de repente se soltar e entrar em voo livre. O comportamento do algoritmo possui muitos aspectos que o tornam especial, e é quase impossível prever as condições que levam a esse comportamento inesperado. É por isso que é difícil recomendá-lo para uma ampla gama de tarefas em sua forma atual. No entanto, em combinação com outros algoritmos (por exemplo, transferindo alguns agentes da população geral para o controle do SDOm) pode ajudar a identificar padrões cíclicos na tarefa.

Otimização por Forrageamento Bacteriano - Algoritmo Genético (BFO-GA)

C_AO_BFO_GA:50;0.01;0.8;50;10.0
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.8233662999080027
25 Hilly's; Execuções da função: 10000; resultado: 0.5031148772790799
500 Hilly's; Execuções da função: 10000; resultado: 0.27434497581097494
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.8611314745481611
25 Forest's; Execuções da função: 10000; resultado: 0.45038118646429437
500 Forest's; Execuções da função: 10000; resultado: 0.1806538222176609
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.3907692307692308
25 Megacity's; Execuções da função: 10000; resultado: 0.272
500 Megacity's; Execuções da função: 10000; resultado: 0.11061538461538559
=============================
Pontuação total: 3.86638

O algoritmo BFO_GA exibe uma capacidade impressionante de detectar rapidamente a região do máximo global - vários agentes já estão se aproximando das coordenadas alvo durante as iterações iniciais. No entanto, seus resultados são menos impressionantes na função discreta. Aparentemente, o número limitado de iterações dentro do teste não é suficiente para encontrar completamente o ótimo global. No entanto, é importante notar que nosso teste está definido dentro de um framework rigoroso, no qual avaliamos a capacidade do algoritmo de alcançar seus objetivos pretendidos.

Busca por Difusão Estocástica (SDSm)

C_AO_SDSm:100;100;0.05
=============================
5 Hilly's; Execuções da função: 10000; resultado: 0.6838494804548411
25 Hilly's; Execuções da função: 10000; resultado: 0.6796828568841194
500 Hilly's; Execuções da função: 10000; resultado: 0.32584905164208583
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.6703019775594297
25 Forest's; Execuções da função: 10000; resultado: 0.6398441335988195
500 Forest's; Execuções da função: 10000; resultado: 0.24899123954861618
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.5307692307692308
25 Megacity's; Execuções da função: 10000; resultado: 0.49446153846153845
500 Megacity's; Execuções da função: 10000; resultado: 0.14973846153846293
=============================
Pontuação total: 4.42349

Ao discutir o algoritmo SDSm, não é totalmente apropriado focar na velocidade com que os agentes se propagam pelo espaço de busca, uma vez que suas coordenadas são especificadas dentro de setores aleatoriamente selecionados do ambiente. Essencialmente, esses agentes são distribuídos instantaneamente por todo o campo de busca após a primeira iteração. Essa abordagem única produz resultados notáveis, demonstrando a eficiência da estratégia do algoritmo.

O que diferencia o SDSm é sua capacidade de aproveitar o poder da aleatoriedade, aumentando a probabilidade de que nenhum canto do espaço de busca fique inexplorado. Ao levar essa natureza estocástica em conta, o algoritmo pode cobrir de forma eficiente grandes áreas e revelar informações valiosas sobre a superfície da função, tornando-o uma ferramenta realmente poderosa para a resolução de problemas.

Algoritmo Genético Binário (BGA)

C_AO_BGA:50:50:1.0:3:0.001:0.7:3
=============================
5 Hilly's; Execuções da função: 10000; resultado: 1.0
25 Hilly's; Execuções da função: 10000; resultado: 1.0
500 Hilly's; Execuções da função: 10000; resultado: 0.8703352617259978
=============================
5 Forest's; Execuções da função: 10000; resultado: 0.8872607468925364
25 Forest's; Execuções da função: 10000; resultado: 0.8177419261242314
500 Forest's; Execuções da função: 10000; resultado: 0.2603521654104144
=============================
5 Megacity's; Execuções da função: 10000; resultado: 0.7492307692307694
25 Megacity's; Execuções da função: 10000; resultado: 0.5833846153846155
500 Megacity's; Execuções da função: 10000; resultado: 0.24415384615384667
=============================
Pontuação total: 6.41246

O Algoritmo Genético Binário (BGA) se beneficia da mutação dos genes, permitindo que eles alcancem instantaneamente qualquer região do espaço de busca sem iterações adicionais. No entanto, neste cenário de teste específico, o BGA se destaca, apesar de às vezes ficar preso em um ótimo local. Nesse sentido, o SDSm parece ser preferível, pois demonstra uma melhor capacidade de evitar tais situações.

No entanto, deve-se dar crédito ao BGA por alcançar os melhores resultados gerais, mesmo considerando suas deficiências. Essa conquista destaca o potencial do algoritmo e a importância de equilibrar pesquisa e exploração no processo de busca. Se nos aprofundarmos na comparação, fica óbvio que cada algoritmo tem suas próprias forças e fraquezas únicas.

Para resumir, podemos dizer que o BGA demonstra resultados impressionantes neste teste, garantindo sua posição de destaque.

2. Melhorando o agente para o BGA

Para realizar esta pesquisa, foi necessário modificar o código do algoritmo BGA para esta tarefa de teste específica. A capacidade de colocar agentes em uma localização arbitrária no espaço de busca pode ser muito útil se você precisar iniciar a otimização com conjuntos definidos pelo usuário.

No BGA, as soluções para o problema são apresentadas na forma de um código binário. Portanto, para colocar agentes da população em coordenadas específicas, é necessário converter os valores das coordenadas de uma representação real para uma binária, neste caso, para um código binário Gray.

Vamos adicionar o método "DoubleToGene" às descrições dos agentes, que converte um valor do tipo "double" em uma representação genética no array "genes". As principais etapas neste método são:

• Se o número de entrada for menor que o valor mínimo válido, a função cria um array de zeros (o número real "0.0" na notação do código Gray) para garantir que o valor permaneça dentro do intervalo válido.

• Se o número de entrada exceder o valor máximo permitido, a função cria um array que copia os valores do array original contendo o número máximo permitido na codificação Gray (este número é salvo para casos como este, quando precisamos retornar ao intervalo se houver um aumento fora do intervalo).
  

• No caso de o número estar dentro do intervalo aceitável, ele é escalado e convertido para o código Gray. Esse valor é então armazenado em um array para uso na representação genética.

Assim, o método "DoubleToGene" converte um valor real em uma representação genética e o escreve no array "genes" correspondente. A função lida com casos em que um valor de entrada está fora do intervalo, inicializando ou copiando arrays específicos e terminando a execução mais cedo. Caso contrário, a função escala o valor, converte as partes inteira e fracionária para o código Gray e as combina na representação genética final.

Código do agente BGA ajustado:

//——————————————————————————————————————————————————————————————————————————————
struct S_Agent
{
  void Init (const int coords, const double &min [], const double &max [], int doubleDigitsInChromo)
  {
    ArrayResize(c, coords);
    f = -DBL_MAX;

    ArrayResize(genes, coords);
    ArrayResize(chromosome, 0, 1000);

    for(int i = 0; i < coords; i++)
    {
      genes [i].Init(min [i], max [i], doubleDigitsInChromo);
      ArrayCopy(chromosome, genes [i].gene, ArraySize(chromosome), 0, WHOLE_ARRAY);
    }
  }

  void ExtractGenes ()
  {
    uint pos = 0;

    for (int i = 0; i < ArraySize (genes); i++)
    {
      c [i] = genes [i].ToDouble (chromosome, pos);
      pos  += genes [i].length;

    }
  }

  void DoubleToGene (const double val, const int genePos)
  {
    double value = val;

    //--------------------------------------------------------------------------
    if (value < genes [genePos].rangeMin)
    {
      ArrayInitialize(genes [genePos].gene, 0);
      ArrayCopy (chromosome, genes [genePos].gene, genePos * genes [genePos].length, 0, WHOLE_ARRAY);
      return;
    }

    //--------------------------------------------------------------------------
    else
    {
      if (value > genes [genePos].rangeMax)
      {
        ArrayCopy (chromosome, genes [genePos].geneMax, genePos * genes [genePos].length, 0, WHOLE_ARRAY);
        return;
      }
    }

    //--------------------------------------------------------------------------
    value = Scale(value, genes [genePos].rangeMin, genes [genePos].rangeMax, 0.0, genes [genePos].maxCodedDistance);

    DecimalToGray ((ulong)value, genes [genePos].integPart);

    value = value - (int)value;

    value *= genes [genePos].digitsPowered;

    DecimalToGray ((ulong)value, genes [genePos].fractPart);

    ArrayInitialize(genes [genePos].gene, 0);

    uint   integGrayDigits = genes [genePos].integGrayDigits;
    uint   fractGrayDigits = genes [genePos].fractGrayDigits;
    uint   digits = ArraySize (genes [genePos].integPart);

    if (digits > 0) ArrayCopy (genes [genePos].gene, genes [genePos].integPart, integGrayDigits - digits, 0, WHOLE_ARRAY);

    digits = ArraySize (genes [genePos].fractPart);

    if (digits > 0) ArrayCopy (genes [genePos].gene, genes [genePos].fractPart, genes [genePos].length - digits, 0, WHOLE_ARRAY);

    ArrayCopy (chromosome, genes [genePos].gene, genePos * genes [genePos].length, 0, WHOLE_ARRAY);
  }

  void InjectGeneToChromosome ()
  {

  }

  //----------------------------------------------------------------------------
  double Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX)
  {
    if (OutMIN == OutMAX) return (OutMIN);
    if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0));
    else
    {
      if (In < InMIN) return OutMIN;
      if (In > InMAX) return OutMAX;

      return (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);
    }
  }

  double c [];           //coordinates
  double f;              //fitness

  S_BinaryGene genes []; //there are as many genes as there are coordinates
  char chromosome    [];
};
//——————————————————————————————————————————————————————————————————————————————

3. Resumo

Vamos resumir os resultados de um estudo comparativo em larga escala de algoritmos de população, que implica sair do mínimo global e superar todos os obstáculos para alcançar o máximo global.
Começaremos visualizando o comportamento mais interessante dos algoritmos durante os testes.

(PO)ES em Megacity

SDOm em Megacity

BFO_GA em Megacity

SDSm em Megacity

BGA em Megacity

Abaixo está a tabela comparativa final, que mostra em detalhes o trabalho de cada algoritmo nas funções de teste.

Figura 1. Graduação de cores dos algoritmos de acordo com os testes relevantes. Resultados maiores ou iguais a 0,99 são destacados em branco

Figura 2. O histograma dos resultados dos testes dos algoritmos (em uma escala de 0 a 100, quanto mais, melhor,

onde 100 é o resultado teórico máximo possível. O arquivo apresenta um script para calcular a tabela de classificação)

Em conclusão, quero enfatizar especificamente que todas as conclusões e julgamentos para cada algoritmo foram feitos exclusivamente dentro do âmbito do experimento.

Toda a discussão e análise do comportamento dos algoritmos de otimização de população sugerem que o sucesso dos algoritmos depende fortemente das condições iniciais de sua aplicação. Para alguns métodos, como DE, EM, GSA, ACOm, testes com uma saída do ponto mínimo da função de teste podem ser tão complexos que levam a dificuldades logo no início. Ao mesmo tempo, para outros, como (P+O)ES, ESG (que inicialmente ocuparam as primeiras posições no ranking, mas se tornaram perdedores), a eficiência é drasticamente reduzida. Pelo contrário, coordenadas iniciais deliberadamente selecionadas podem melhorar significativamente os resultados para algoritmos como PSO, GWO, SFL, BA e ABC. Alguns algoritmos (BFO-GA e SDOm) até demonstraram desempenho excepcional com essa abordagem, superando a inicialização uniforme aleatória dos agentes.

Outros algoritmos, como IWO, HS, SDSm e BGA, mostraram estabilidade universal independentemente da posição inicial dos agentes. Este experimento especial destacou que, embora alguns algoritmos tenham apresentado desempenho ruim durante o teste, eles ainda demonstraram habilidades impressionantes em certos pontos do experimento. Alguns deles exploraram o espaço com sucesso no início do processo, enquanto outros conseguiram melhorar significativamente os resultados em estágios posteriores. Essas características únicas de cada algoritmo podem ser combinadas e hibridizadas com sucesso, aprimorando seus aspectos positivos e reduzindo suas desvantagens, o que pode, em última análise, levar a métodos de otimização mais eficientes.