Algoritmos de otimização populacionais: Enxame de partículas (PSO)
265
0
«Eles formam enxames individuais, graças aos quais podem permanecer sob a luz do sol
ou mover-se atrás de nuvens de trovão, é possível que eles retirem energia das descargas atmosféricas.
Mas no momento do perigo ou, mais amplamente, de uma mudança repentina que ameaça sua existência, eles se unem...»
Stanislaw Lem, A Nave Invencível (1964)
Conteúdo:
1. Introdução
Muitas pessoas já leram o clássico de ficção científica A Nave Invencível de Stanislaw Lem. Surpreendentemente, a obra foi uma das primeiras a descrever a inteligência coletiva ou de enxame. A narrativa segue robôs que sobrevivem de forma distribuída, isto é, descentralizado, com os espécimes mais adaptáveis e simples tendo vantagem sobre os mais complexos e poderosos.
Estes autômatos, ao longo de milhares de anos de "necro-evolução" (evolução dos não-vivos), aprenderam a lutar efetivamente contra os concorrentes que os superaram tanto em inteligência quanto em poder. Não só tinham que lutar contra outros robôs, mas também contra o mundo vivo do planeta, e vencer. Os elementos fantásticos deste trabalho, como a necro-evolução, podem ser comparados diretamente à ação da natureza e da própria evolução.
Desde tempos imemoriais, as pessoas têm se interessado pelo comportamento em grupo de animais, conhecido como comportamento de enxame. Como as aves funcionam como um bando ao se dirigir para climas mais quentes, como um enxame de abelhas se alimenta, como uma colônia de formigas sobrevive criando estruturas complexas, e como os peixes se comportam em um cardume, com comportamento tão sincronizado. A organização dos indivíduos em uma sociedade, apesar da descentralização do controle, pode parecer como se estivessem sob a liderança de uma única mente. Alguns padrões desse tudo coordenado único e interconexões observadas na natureza inspiram a criação e o desenvolvimento de novas ideias no campo da otimização algorítmica.
A inteligência de enxame (Swarm intelligence) descreve a imitação do comportamento coletivo de um sistema auto-organizado. Há uma série de algoritmos desse tipo. Na versão canônica, escrita em 1995 por J. Kennedy e R. Eberhart, o modelo subjacente a este método foi derivado de uma simplificação do modelo de Reynolds. Como resultado desta simplificação, cada indivíduo da população era representado como um objeto separado, não tendo tamanho, mas alguma velocidade.
Devido a sua extrema semelhança com partículas, os objetos simples resultantes foram chamados de partículas e sua população de enxames. A cada instante (a cada iteração) as partículas têm alguma posição e vetor de velocidade no espaço. Para cada posição da partícula é calculado o valor correspondente da função alvo e nesta base, de acordo com certas regras, a partícula muda sua posição e velocidade no espaço de busca. Ao determinar a próxima posição da partícula, são levadas em conta as informações sobre a melhor posição de todas as outras partículas vizinhas, correspondentes às tarefas da função adaptativa.
Exemplos de algoritmos de enxame:
- Otimização por enxame de partículas
- Otimização por colônia de formigas
- Otimização por colônia de abelhas
- Sistema imunológico artificial
- Otimização do lobo cinzento
- Otimização por colonia de morcegos
- Algoritmo de busca gravitacional
- Algoritmo de altruísmo
- E muitos outros
A modelagem do comportamento coletivo com o objetivo de alcançar a otimização coletiva se baseia na ideia biológica de que os organismos se reúnem em colônias para melhorar suas condições de sobrevivência. Cada organismo em uma colônia, em média, tem mais chances de sobreviver contra predadores, e a colônia é capaz de procurar, processar e armazenar alimentos de forma mais eficiente quando comparado com indivíduos isolados. Em resumo, a colônia resolve várias tarefas de otimização ao longo de sua existência, com diferentes níveis de eficiência, como maximizar a quantidade de alimentos e minimizar as perdas devido aos predadores. Essa base biológica é utilizada para desenvolver uma variedade de métodos matemáticos para otimização.
O enxame de partículas é um dos algoritmos de otimização mais conhecidos e populares desde seu início, muitos autores de suas várias implementações afirmam que o algoritmo é muito eficaz na otimização de funções complexas com muitos argumentos e é adequado para o treinamento de redes neurais.
Este artigo busca avaliar a eficácia do algoritmo para resolver problemas complexos. A versão clássica do algoritmo e suas variações apresentam limitações significativas, como a necessidade de que a função a ser otimizada seja suave e contínua, o que é inadequado para funções discretas. No entanto, como proposto nesta série de artigos, todos os algoritmos serão modificados, se necessário, para eliminar essas restrições e garantir que eles possam funcionar tanto em problemas contínuos quanto discretos. Assim, todos os algoritmos serão avaliados puramente tecnicamente, sem restrições nas etapas de argumentação.
2. Princípios do algoritmo
O artigo anterior ofereceu uma introdução básica ao mundo da otimização, mas não abordou como o programa principal (Expert Advisor, script, indicador) interage com o núcleo do algoritmo de otimização. Isso é uma questão importante a ser considerada, pois pode levantar dúvidas sobre por que os algoritmos e programas de exemplo são escritos de determinada forma. Os algoritmos de otimização disponíveis publicamente são construídos de tal forma que o algoritmo acessa a função de adaptação como um objeto externo a ele, enquanto ele próprio é o programa principal executável.
A Figura 1 mostra como o algoritmo transfere os parâmetros a serem otimizados para a função de adaptação e como é retornado o valor de adaptação (critério de avaliação). No entanto, esse esquema pode ser pouco conveniente para os usuários, especialmente os operadores, ao construir um programa de solução de problemas. Isso se deve ao fato de que não é possível, por exemplo, fazer com que um testador rode usando o histórico.
Figura 1. Diagrama de interação entre o algoritmo PSO e a função de adaptação.
O esquema mostrado na Figura 2 é muito mais conveniente, pois o algoritmo de otimização não é um programa autônomo, mas sim um módulo separado ou "caixa preta". Esse módulo possui os parâmetros min, max, step para cada argumento a ser otimizado. O programa MQL recebe os argumentos a serem otimizados através de uma solicitação e retorna valores de adaptação, ou seja, valores da função de adaptação. Esse esquema permite a construção de soluções flexíveis, desde a utilização da otimização automática em EAs até a escrita de um gerente de otimização personalizado.
Figura 2. Esquema de interação entre o MQL e o PSO.
Em separado, é importante mencionar a realização de chamadas ao método de otimização (bloco MQL na Figura 2), que pode ser representado por um esquema geral que é o mesmo para todos os algoritmos de otimização (AO), como a seguir:
Inicialização_AO_0
Ciclo de iterações (épocas)
{
1) Método_AO_1
2) Obtenção de valores de adaptação para cada variante dos parâmetros otimizados
3) Método_AO_2
}
Assim, vemos que apenas três métodos públicos são utilizados: Inicialização_AO_0, Método_AO_1 e Método_AO_2. Isto é suficiente para levar a cabo o processo de otimização em projetos personalizados de qualquer complexidade.
O próprio OSP é mostrado na Figura 3 e inclui os seguintes passos:
- Geração de partículas aleatórias (primeira iteração)
- Obtenção do valor de adaptação de cada partícula
- Obtenção do valor de adaptação para todas as partículas de forma conjunta
- Ajuste da velocidade da partícula
- Ponto de parada, ou ir para o passo 2
- Conclusão do programa.
Figura 3. Esquema de operação do PSO.
Vamos dar uma olhada mais de perto no algoritmo enxame de partículas.
O sistema de inteligência de enxame é composto por uma multidão de partículas que interagem entre si e com o ambiente. Cada partícula segue regras simples, sem necessidade de um sistema centralizado de controle de comportamento. As interações locais e aleatórias entre as partículas produzem um comportamento de grupo inteligente, que não é controlado pelos indivíduos.
Podemos comparar esse sistema com o de um rebanho, onde cada partícula tem tarefas simples a realizar.
- evitar a sobreposição com outras partículas;
- ajustar sua velocidade para corresponder às velocidades das partículas ao redor;
- tente manter a distância entre si e o ambiente ao seu redor suficientemente pequena.
O algoritmo PSO começa com a inicialização da população. O segundo passo é calcular os valores de adaptação de cada partícula, com base na qual os melhores resultados individuais e globais são atualizados. Em seguida, a velocidade e a posição das partículas são ajustadas. Com o PSO, a solução para o problema de otimização numérica é representada pela posição da partícula. Além disso, cada partícula tem o valor de sua adaptação, posição atual, posição mais conhecida
(ou seja, a posição anterior com a adaptação mais conhecida) e a adaptação da posição mais conhecida. Esses passos são repetidos até que a condição de término seja atingida. Na primeira iteração, todas as partículas são dispersas para encontrar a melhor solução, cada partícula é avaliada e as melhores soluções de topologia de vizinhança são encontradas, e as melhores partículas pessoais e globais para cada membro do enxame são atualizadas. A convergência é alcançada atraindo todas as partículas para a partícula com a melhor solução.
Embora o algoritmo PSO seja relativamente simples, é importante compreendê-lo para ser capaz de modificar o código deste artigo de acordo com suas necessidades. O PSO é um processo iterativo e, em cada iteração no ciclo principal de processamento, a velocidade atual de cada partícula é atualizada. Isso leva em conta a velocidade atual das partículas, as informações locais sobre as partículas e as informações globais sobre o enxame. Em seguida, a posição de cada partícula é atualizada com base no valor da nova velocidade.
Em termos matemáticos, as equações para atualizar as coordenadas de uma partícula se assemelham a esta:
v(t+1) = w * v(t) + c1 * rp * (p(t) – x(t)) + (c2 * rg * (g(t) – x(t))
x(t+1) = x(t) + v(t+1)
O processo de atualização da posição é, na verdade, bastante simples. A primeira equação é utilizada para atualizar a velocidade da partícula.
O termo v(t+1) se refere à velocidade no tempo t+1. A nova velocidade é determinada por três fatores:
- O primeiro é w * v(t), onde w é a fração de peso da inércia, uma constante, e v(t) é a velocidade atual no tempo t.
- O segundo é c1 * rp * (p(t) - x(t)), onde c1 é uma constante chamada de fração de peso cognitiva ou pessoal ou local; rp é uma variável aleatória dentro da faixa [0,1]; o vetor p(t) representa a melhor posição encontrada até agora para a partícula, e x(t) é a posição atual da partícula.
- O terceiro é a velocidade de atualização c2 * rg * (g(t) - x(t)), onde c2 é uma constante chamada de fator de ponderação social (ou global) e rg é uma variável aleatória na faixa [0,1]. O vetor g(t) representa a posição mais conhecida encontrada pelo enxame até o momento. Uma vez calculada a nova velocidade v(t+1), ela é utilizada para calcular a nova posição x(t+1) da partícula.
3. Implementação clássica
O algoritmo de otimização baseado em inteligência de enxame utiliza a estrutura da partícula para representar as coordenadas no espaço de parâmetros otimizáveis. A estrutura inclui as seguintes informações: coordenadas atuais da partícula (c[]), melhores coordenadas encontradas pelas iterações (cB[]), velocidade atual da partícula (v[]), valor atual de adaptação da partícula (ff) e melhor valor de adaptação encontrado pelas iterações (ffB). No construtor da estrutura da partícula, inicializamos o valor de ff e ffB com o menor valor possível representado pelo tipo double. Lembre-se de que para encontrar o mínimo da função, é necessário adicionar um sinal negativo antes do valor de adaptação resultante.
//—————————————————————————————————————————————————————————————————————————————— struct S_Particles { public: double c []; //coordinates double cB []; //best coordinates double v []; //velocity double ff; //the value of the fitness function double ffB; //best value fitness function S_Particles () { ff = -DBL_MAX; ffB = -DBL_MAX; } }; //——————————————————————————————————————————————————————————————————————————————
Na verdade, o próprio algoritmo PSO é escrito como uma classe com apenas três métodos públicos, InitPS (), Preparation (), e Dwelling () (Inicialização_AO_0, Método_AO_1 e Método_AO_2). Dos métodos privados, os GenerateRNDparticles () e ParticleMovement () são exclusivos do PSO, e nós cobrimos os outros no artigo anterior. A matriz de estruturas p [] é o enxame de partículas. Além do fato de que cada partícula tem valores de adaptação, suas coordenadas e melhores coordenadas, todo o enxame de forma conjunta tem melhores coordenadas cB e melhor valor de adaptação ffB.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_PSO { public: //---------------------------------------------------------------------------- S_Particles p []; //particles double rangeMax []; //maximum search range double rangeMin []; //manimum search range double rangeStep []; //step search double cB []; //best coordinates double ffB; //FF of the best coordinates void InitPS (const int params, //number of opt. parameters const int size, //swarm size const double inertiaP, //inertia const double selfBoostP, //boost const double groupBoostP); //group boost void Preparation (); void Dwelling (); private: //---------------------------------------------------------------------------- int swarmSize; //swarm size int parameters;//number of optimized parameters double inertia; double selfBoost; double groupBoost; bool dwelling; void GenerateRNDparticles (); void ParticleMovement (); double SeInDiSp (double in, double inMin, double inMax, double step); double RNDfromCI (double min, double max); }; //——————————————————————————————————————————————————————————————————————————————
O método InitPS () é utilizado para a inicializar o algoritmo antes do início da otimização (no esquema, Inicialização_AO_0), atribui membros privados aos argumentos do método e atribui um tamanho ao enxame e parâmetros internos a cada partícula do enxame.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::InitPS (const int paramsP, const int sizeP, const double inertiaP, const double selfBoostP, const double groupBoostP) { ffB = -DBL_MAX; parameters = paramsP; swarmSize = sizeP; ArrayResize (rangeMax, parameters); ArrayResize (rangeMin, parameters); ArrayResize (rangeStep, parameters); dwelling = false; inertia = inertiaP; selfBoost = selfBoostP; groupBoost = groupBoostP; ArrayResize (p, swarmSize); for (int i = 0; i < swarmSize; i++) { ArrayResize (p [i].c, parameters); ArrayResize (p [i].cB, parameters); ArrayResize (p [i].v, parameters); } ArrayResize (cB, parameters); } //——————————————————————————————————————————————————————————————————————————————
O método Preparation () é chamado a cada iteração (época) primeiro (Método_AO_1). O método é simples, mas muito importante. Dependendo de se o método é chamado na primeira época ou em épocas posteriores (determinadas pelo sinalizador dwelling), a adaptação do enxame será reiniciada e será criada uma população de enxame aleatória, ou as partículas serão movidas para novas coordenadas.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::Preparation () { if (!dwelling) { ffB = -DBL_MAX; GenerateRNDparticles (); dwelling = true; } else ParticleMovement (); } //——————————————————————————————————————————————————————————————————————————————
No método GenerateRNDparticles (), é gerada uma população de enxame aleatória, as partículas têm coordenadas aleatórias no intervalo dado para cada uma delas, e uma velocidade aleatória para cada uma das coordenadas.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::GenerateRNDparticles () { for (int s = 0; s < swarmSize; s++) { for (int k = 0; k < parameters; k++) { p [s].c [k] = RNDfromCI (rangeMin [k], rangeMax [k]); p [s].c [k] = SeInDiSp (p [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); p [s].cB [k] = p [s].c [k]; p [s].v [k] = RNDfromCI (0.0, (rangeMax [k] - rangeMin [k]) * 0.5); } } } //——————————————————————————————————————————————————————————————————————————————
O método ParticleMovement () implementa um algoritmo para calcular a nova posição das partículas baseando-se na fórmula fornecida. Embora o termo "velocidade" seja utilizado, ele se refere ao deslocamento, ou seja, a diferença entre a posição atual da partícula e sua nova posição. Essa diferença é calculada para cada coordenada e então adicionada aos valores atuais. Também é verificado se os parâmetros otimizados (como as coordenadas) não são excedidos no passo atual.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::ParticleMovement () { double rp; //random component of particle movement double rg; double velocity; double posit; double positBest; double groupBest; for (int i = 0; i < swarmSize; i++) { for (int k = 0; k < parameters; k++) { rp = RNDfromCI (0.0, 1.0); rg = RNDfromCI (0.0, 1.0); velocity = p [i].v [k]; posit = p [i].c [k]; positBest = p [i].cB [k]; groupBest = cB [k]; p [i].v [k] = inertia * velocity + selfBoost * rp * (positBest - posit) + groupBoost * rg * (groupBest - posit); p [i].c [k] = posit + p [i].v [k]; p [i].c [k] = SeInDiSp (p [i].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); } } } //——————————————————————————————————————————————————————————————————————————————
O método Dwelling () é o terceiro método público do algoritmo, usado pelo usuário em seu programa para otimizar (de acordo com o esquema Método_AO_2). Seu objetivo é atualizar as melhores coordenadas e valores de adaptação de cada partícula em relação ao seu desempenho anterior, além de, se necessário, atualizar a adaptabilidade do enxame e as melhores coordenadas. Ele é chamado após a obtenção dos valores de adaptação no loop de iteração.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSO::Dwelling () { for (int i = 0; i < swarmSize; i++) { //remember the best position for the particle if (p [i].ff > p [i].ffB) { p [i].ffB = p [i].ff; for (int k = 0; k < parameters; k++) p [i].cB [k] = p [i].c [k]; } if (p [i].ff > ffB) { ffB = p [i].ff; for (int k = 0; k < parameters; k++) cB [k] = p [i].c [k]; } } } //——————————————————————————————————————————————————————————————————————————————
Função para discretizar um número double com um passo especificado em um determinado intervalo.
//—————————————————————————————————————————————————————————————————————————————— // Choice in discrete space double C_AO_PSO::SeInDiSp (double in, double inMin, double inMax, double step) { if (in <= inMin) return (inMin); if (in >= inMax) return (inMax); if (step == 0.0) return (in); else return (inMin + step * (double)MathRound ((in - inMin) / step)); } //——————————————————————————————————————————————————————————————————————————————
Função para obter um número double aleatório dentro de um determinado intervalo.
//—————————————————————————————————————————————————————————————————————————————— // Random number generator in the custom interval double C_AO_PSO::RNDfromCI (double min, double max) { if (min == max) return (min); double Min, Max; if (min > max) { Min = max; Max = min; } else { Min = min; Max = max; } return (double(Min + ((Max - Min) * (double)MathRand () / 32767.0))); } //——————————————————————————————————————————————————————————————————————————————
Acabamos com a teoria. Vamos começar com a prática.
Como utilizamos o mesmo esquema de construção do algoritmo que no primeiro artigo da série (e continuaremos fazendo isso), descrito na Figura 2, não temos problemas para incluir o algoritmo na bateria de testes.
Ao iniciar essa bateria, será possível visualizar animações semelhantes às mostradas abaixo. Neste exemplo, é possível ver claramente como o enxame de partículas se comporta, movendo-se como uma nuvem densa no mapa de calor da função.
É importante lembrar que o círculo preto representa o ótimo global (máximo) da função e o ponto preto representa as melhores coordenadas médias obtidas pelo algoritmo de busca na iteração atual. As coordenadas são calculadas como a média entre as medidas, já que a função a ser otimizada pode incluir centenas de variáveis.
PSO sobre a função de teste Skin.
PSO sobre a função de teste Forest.
PSO sobre uma função de teste Megacity.
De acordo com a animação, os testes mostraram que o PSO (Particle Swarm Optimization) funciona bem com a primeira função, especialmente quando otimizando apenas duas variáveis. No entanto, à medida que a dimensionalidade do espaço de busca aumenta, a eficiência do algoritmo diminui significativamente, especialmente na segunda e terceira função discretas. Os resultados são notavelmente inferiores aos obtidos pelo algoritmo aleatório descrito no artigo anterior. Discutiremos esses resultados em detalhes e os compararemos com outros algoritmos na tabela comparativa de resultados.
É surpreendente ver o famoso algoritmo PSO perdendo para um algoritmo aleatório, o que nos leva a tentar modificá-lo na próxima seção deste artigo.
4. Versão modificada
Na minha opinião, as principais fraquezas do PSO incluem:
1) A probabilidade de alteração de cada coordenada é quase igual a 1, o que significa que cada partícula do enxame oscila em algum lugar próximo ao extremo local ou global, mas nunca atinge exatamente o ponto do extremo global, levando a uma fraca convergência.
2) O algoritmo não funciona bem com funções discretas, devido à tendência das partículas saltarem para os "locais" mais próximos da superfície da função a ser otimizada, sem investigar em detalhes as vizinhanças com os extremos locais.
3) O enxame tem uma fraca capacidade de explorar novas áreas, concentrando-se em um único lugar e não tentando se afastar do "buraco" local. A literatura menciona tentativas de implementar modificações multi-enxame, mas essas questões ainda são incertas para funções complexas multi-variáveis, uma vez que o princípio de afastamento mútuo não é claro. Além disso, não há necessidade de fazer um grande esforço para otimizar funções simples de uma ou duas variáveis, pois esses problemas podem ser resolvidos com métodos mais simples e obter uma excelente convergência.
Uma vez que identificamos as deficiências específicas da OSP, é possível melhorá-la de várias maneiras:
Uma delas é garantir que as melhores coordenadas individuais sejam transferidas para partículas de outras partículas, com a probabilidade de que as melhores coordenadas sejam as coordenadas gerais da partícula "doadora". A Figura 4 mostra uma representação esquemática dessa mudança na probabilidade de seleção de partículas. Isso pode ser alcançado gerando um número aleatório de 0 a 1, transformando-o com uma função parabólica e escalando-o para a faixa de números ordinais das partículas no enxame, de 0 a SwarmSize-1. Para isso, é necessário adicionar um parâmetro adicional ao PSOm (o nome dado ao algoritmo modificado) - probabilidade de cópia de coordenadas e também é preciso classificar o enxame de forma que quanto melhor a partícula, mais próxima está do índice 0.
Figura 4. Probabilidade enviesada de seleção da partícula.
Para melhorar o método ParticleMovement(), é possível fazer uma pequena alteração. Primeiro, geramos um número aleatório entre 0 e 1. Se esse número for maior do que o parâmetro de cópia, realizamos as operações normais de movimento de partícula descritas anteriormente. Caso contrário, copiamos a coordenada de outra partícula com um índice escolhido de acordo com a regra mostrada graficamente na Figura 4.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSOm::ParticleMovement () { double rp; //random component of particle movement double rg; double velocity; double posit; double positBest; double groupBest; for (int i = 0; i < swarmSize; i++) { for (int k = 0; k < parameters; k++) { rp = RNDfromCI (0.0, 1.0); rg = RNDfromCI (0.0, 1.0); double rC = RNDfromCI (0.0, 1.0); if (rC > copy) { velocity = p [i].v [k]; posit = p [i].c [k]; positBest = p [i].cB [k]; groupBest = cB [k]; p [i].v [k] = inertia * velocity + selfBoost * rp * (positBest - posit) + groupBoost * rg * (groupBest - posit); p [i].c [k] = posit + p [i].v [k]; p [i].c [k] = SeInDiSp (p [i].c [k], rangeMin [k], rangeMax [k], rangeStep [k]); } else p [i].c [k] = p [GetPartcileAdress ()].cB [k]; } } } //——————————————————————————————————————————————————————————————————————————————
O método Dwelling () também precisará ser alterado. Vamos adicionar uma chamada para a função SortParticles ().
//—————————————————————————————————————————————————————————————————————————————— void C_AO_PSOm::Dwelling () { for (int i = 0; i < swarmSize; i++) { //remember the best position for the particle if (p [i].ff > p [i].ffB) { p [i].ffB = p [i].ff; for (int k = 0; k < parameters; k++) p [i].cB [k] = p [i].c [k]; } if (p [i].ff > ffB) { ffB = p [i].ff; for (int k = 0; k < parameters; k++) cB [k] = p [i].c [k]; } } SortParticles (); } //——————————————————————————————————————————————————————————————————————————————
A função GetParticleAdress () garante a seleção de endereço de partícula com uma probabilidade deslocada para a melhor partícula.
//—————————————————————————————————————————————————————————————————————————————— //shift of probability in the smaller party (to an index 0) int C_AO_PSOm::GetParticleAdress () { double x = RNDfromCI (-1.0, 0.0); x = x * x; x = Scale (x, 0.0, 1.0, 0, swarmSize - 1); x = SeInDiSp (x, 0, swarmSize - 1, 1); return ((int)x); } //——————————————————————————————————————————————————————————————————————————————
A função SortParticles () é um algoritmo de ordenação por flutuação.
//—————————————————————————————————————————————————————————————————————————————— //Sorting of particles void C_AO_PSOm::SortParticles () { //---------------------------------------------------------------------------- int cnt = 1; int t0 = 0; double t1 = 0.0; //---------------------------------------------------------------------------- // We will put indexes in the temporary array for (int i = 0; i < swarmSize; i++) { ind [i] = i; val [i] = p [i].ffB; //ffPop [i]; } while (cnt > 0) { cnt = 0; for (int i = 0; i < swarmSize - 1; i++) { if (val [i] < val [i + 1]) { t0 = ind [i + 1]; t1 = val [i + 1]; ind [i + 1] = ind [i]; val [i + 1] = val [i]; ind [i] = t0; val [i] = t1; cnt++; } } } // On the received indexes create the sorted temporary population for (int u = 0; u < swarmSize; u++) pT [u] = p [ind [u]]; // Copy the sorted array back for (int u = 0; u < swarmSize; u++) p [u] = pT [u]; } //——————————————————————————————————————————————————————————————————————————————
A função de escalonamento é utilizada para transformar um número de um intervalo numérico para outro.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_PSOm::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); } } //——————————————————————————————————————————————————————————————————————————————
5. Resultado dos testes
Em resumo, o algoritmo PSO não se mostrou tão eficiente quanto esperávamos. Estudos têm revelado uma fraca convergência para funções discretas, com falhas frequentes e um grande número de argumentos. Mesmo nossa tentativa de modificar o algoritmo não teve sucesso, com resultados ainda piores do que a implementação clássica.
Aumentar o parâmetro de cópia para valores próximos a 0,8 mostrou convergência apenas para a primeira função suave nos testes e com apenas dois argumentos, enquanto para os outros testes esse parâmetro piorou os resultados. A implementação clássica do PSO mostrou algum destaque apenas na função Skin com 1000 argumentos, mas em outros testes os resultados foram medíocres.
O resultado final do teste foi de 0,47695 para o clássico e 0,45144 para o modificado, respectivamente. Os resultados podem ser vistos na tabela abaixo. A bateria de testes permite que o número de repetições de teste seja selecionado nas configurações (a configuração padrão é 5), para que os leitores possam obter resultados estatisticamente mais precisos ao definir este parâmetro mais alto, se a potência do computador permitir.
| AO | Runs | Skin | Forest | Megacity (discrete) | Final result | ||||||
| 2 params (1 F) | 40 params (20 F) | 1000 params (500 F) | 2 params (1 F) | 40 params (20 F) | 1000 params (500 F) | 2 params (1 F) | 40 params (20 F) | 1000 params (500 F) | |||
| RND | 1000 | 0,98744 | 0,61852 | 0,49408 | 0,89582 | 0,19645 | 0,14042 | 0,77333 | 0,19000 | 0,14283 | 0,51254 |
| 10000 | 0,99977 | 0,69448 | 0,50188 | 0,98181 | 0,24433 | 0,14042 | 0,88000 | 0,20133 | 0,14283 | ||
| PSO | 1000 | 0,98436 | 0,72243 | 0,65483 | 0,71122 | 0,15603 | 0,08727 | 0,53333 | 0,08000 | 0,04085 | 0,47695 |
| 10000 | 0,99836 | 0,72329 | 0,65483 | 0,97615 | 0,19640 | 0,09219 | 0,82667 | 0,10600 | 0,04085 | ||
| PSOm | 1000 | 0,96678 | 0,64727 | 0,57654 | 0,80616 | 0,13388 | 0,06800 | 0,53333 | 0,08067 | 0,04211 | 0,45144 |
| 10000 | 0,99505 | 0,64986 | 0,57654 | 0,90401 | 0,18194 | 0,07104 | 0,74667 | 0,10400 | 0,04211 | ||
Para resumir, o algoritmo PSO tende a levar a uma convergência rápida e prematura nos pontos ideais, além de uma convergência lenta na área de busca refinada (que tem fraca capacidade de busca local). Ele não é adequado para otimizar funções complexas e discretas, especialmente aquelas com muitos argumentos.
Existem várias técnicas que podem ser utilizadas para melhorar o desempenho do PSO. O tamanho do enxame é um fator importante, pois um enxame maior pode aumentar a probabilidade de uma convergência rápida e precisa, mas, na prática, há um limite no número de iterações permitidas e aumentar o tamanho do enxame reduzirá proporcionalmente o número de iterações e diminuirá a possibilidade de evolução do enxame.
O segundo enfoque consiste em alcançar um equilíbrio entre a busca de novas soluções e o aproveitamento das melhores encontradas. No início das iterações, uma alta busca permitiria encontrar soluções próximas ao ótimo global, enquanto que no final das iterações, um alto aproveitamento permitiria encontrar soluções mais precisas em áreas promissoras. Outra maneira de aumentar a eficiência do PSO é através de uma pré-otimização grosseira com outros métodos, algo comum atualmente. Além disso, distribuir diferentes tarefas ou objetivos para cada subgrupo também pode melhorar o desempenho do PSO em tarefas multiobjetivo.
Outra abordagem para melhorar o desempenho do PSO é definir os componentes da equação de velocidade (ajuste dinâmico de velocidade). Essa abordagem pode direcionar as partículas em diferentes direções e levar à convergência mais rápida para o ótimo global, mas isso é apenas uma suposição.Prós:
- O algoritmo é simples e não exige muitos recursos computacionais. O código funciona muito rápido, pois na implementação clássica nem mesmo é necessário ordenar arrays.
- Ele se sai bem com funções suaves. Atualmente, o PSO é líder na tabela de otimização de funções suaves com muitos argumentos.
Contras:
- Baixa qualidade na investigação da função otimizada, o algoritmo não pode ser aplicado em problemas que requerem várias soluções únicas.
- Baixa velocidade e precisão na convergência.
- Inadequado para otimização de funções discretas.
- Praticamente não escalável.
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/11386
Algoritmos de otimização populacionais: Otimização de colônia de formigas (ACO)
Como desenvolver um sistema de negociação baseado no indicador Oscilador Acelerador
Redes neurais de maneira fácil (Parte 31): Algoritmos evolutivos
DoEasy. Controles (Parte 22): SplitContainer. Alterando as propriedades do objeto criado
- 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