Algoritmos de otimização populacionais: algoritmo de gotas de água inteligentes (Intelligent Water Drops, IWD)
186
0
Conteúdo:
1. Introdução
2. Descrição do algoritmo
3. Versão modificada do SDSm
4. Resultados dos testes
1. Introdução
O leito do rio é uma das criações mais requintadas da natureza, com cada gota de água desempenhando seu papel na dança única da vida. A cada quilômetro de viagem, o rio forma seus novos limites, irradiando majestosamente sua energia e sabedoria. Assim como este fenômeno natural, o algoritmo de otimização "gotas de água inteligentes" busca harmonia e perfeição em seu funcionamento, utilizando princípios de auto-organização e interação entre as partículas. Este algoritmo reflete a grandeza da natureza e sua capacidade de criar e manter o equilíbrio, tornando-o uma ferramenta importante na otimização de processos e solução de problemas complexos.
Todo rio tem seu próprio vale, formado por processos erosivos sob a ação das águas superficiais e subterrâneas. A parte mais baixa deste vale, escavada no solo pelo fluxo do rio, é chamada de leito. É por ele que ocorre o deslocamento da maior parte do fluxo do rio e dos sedimentos.
O relevo do leito está em constante mudança. As pedras e a areia capturadas pela água formam bancos e corredeiras, que cruzam o leito em um ângulo agudo. Nas curvas, os rios podem abrir novos caminhos e formar meandros, que são partes do antigo leito que gradualmente se transformam em lagos com seus próprios ecossistemas e, mais tarde, secam ou permanecem como pântanos.
Ao observarmos os rios na natureza, notamos muitas voltas as e curvas em seu caminho. Surge a questão: por que essas voltas foram criadas e há alguma lógica ou razão por trás delas? E se for esse o caso, podemos usar os mecanismos que ocorrem nos rios e, como resultado, podemos projetar e desenvolver algoritmos inteligentes baseados neles? O IWD é uma tentativa de modelar alguns dos processos que ocorrem em rios naturais e então implementá-los na forma de um algoritmo.
O algoritmo de gotas de água inteligentes é um dos algoritmos relativamente recentes na área de inteligência de enxame: ele imita a dinâmica dos sistemas fluviais. O IWD é um algoritmo populacional, no qual cada gota representa uma solução, e o uso conjunto das gotas durante a busca leva a melhores soluções.
Em 2007, o cientista iraniano Hamed Shah-Hosseini desenvolveu o algoritmo de comportamento das gotas de água inteligentes. No IWD, várias gotas artificiais de água, que através da interação conseguem mudar seu ambiente de forma a encontrar o caminho ótimo de menor resistência. O IWD é um algoritmo populacional construtivo de otimização.
2. Descrição do algoritmo
O IWD é um modelo no qual gotas de água encontram o caminho ótimo até o destino, modificando o leito do rio. Isso é facilitado por três parâmetros importantes. Devido à sua própria velocidade, as gotas são capazes de capturar solo do fundo do rio, e quanto maior a velocidade, maior a quantidade de solo que cada gota pode carregar consigo, consequentemente, o caminho se torna mais livre para os agentes subsequentes. A velocidade do fluxo aumenta onde não há solo a ser limpo. Um caminho pode ser considerado ótimo quando encontra menos solo e onde se pode desenvolver a maior velocidade possível. Com o IWD, pode-se implementar uma estratégia de otimização onde agentes aleatórios interagem inteligentemente uns com os outros de tal forma que, juntos, mudam o leito do rio e criam o caminho ótimo, onde não se encontra solo e a velocidade do fluxo dos agentes é a mais alta possível.
Princípios fundamentais:
- uma gota de água prefere um caminho com menos solo do que caminhos com mais solo
- uma gota de água prefere um caminho mais curto quando tem que escolher entre várias rotas do ponto de origem ao destino
- a facilidade ou dificuldade de um caminho é determinada pela quantidade de solo presente, um caminho com mais solo é considerado difícil, enquanto um caminho com menos solo é considerado fácil.
Na natureza, muitas gotas de água são observadas em rios, onde formam grandes massas (enxames de gotas de água). Os caminhos pelos quais os rios naturais fluem foram criados por enxames de gotas de água. Enxames de gotas de água (rios) fazem parte do ambiente circundante, que foi significativamente alterado pelo enxame e também está sujeito a mudanças no futuro. Além disso, o próprio ambiente tem uma influência significativa nas rotas de viagem das gotas de água. Elas enfrentam resistência das margens do rio. Por exemplo, um enxame de gotas de água enfrenta mais resistência de partes do ambiente que consistem em solo duro do que de partes de solo macio. O leito natural de um rio é o resultado da competição entre as gotas de água e o ambiente que oferece resistência ao movimento das gotas de água.
Uma das características de uma gota de água que flui para o rio é sua velocidade. Outra característica é o solo, uma certa quantidade do qual pode ser carregada por cada rio. Assim, uma gota de água é capaz de transportar uma quantidade de solo de um lugar para outro. Esse solo é transferido de partículas rápidas para partículas lentas. Ou seja, o solo capturado pelo rio junto com o fluxo rápido se depositará em um local de fluxo lento.
Três mudanças óbvias ocorrerão durante esse período de transição:
- a velocidade da gota de água aumenta
- a saturação do solo pela gota de água aumenta
- entre esses dois pontos, a quantidade de solo no leito do rio diminui (pontos no grafo)
Foi mencionado acima que cada gota de água tem sua própria velocidade. Essa velocidade desempenha um papel direto na coleta de solo no leito do rio. Uma gota de água com alta velocidade coleta mais solo do que uma gota com velocidade mais baixa. Assim, as gotas de água com maior velocidade removem mais solo do fundo do rio do que as gotas com menor velocidade. A remoção do solo, portanto, está relacionada à velocidade da gota de água.
A velocidade da gota de água aumenta mais em um caminho com baixo nível de solo do que em um caminho com alto nível de solo. Assim, um caminho com uma pequena quantidade de solo permite que a gota de água corrente colete mais solo e ganhe maior velocidade, enquanto um caminho com altos níveis de solo leva a uma redução na velocidade.
Portanto, no IWD, as gotas são caracterizadas por duas propriedades principais:
- velocidade
- solo
Ambas essas propriedades podem mudar durante a operação do algoritmo. As gotas no IWD se movem da fonte para o destino e começam seu caminho com velocidade inicial e solo zero. Durante sua jornada, as gotas movem-se no ambiente, removendo alguma quantidade de solo e podem ganhar alguma velocidade. Presume-se que o IWD é executado iterativamente. Do local atual ao próximo, a velocidade da gota aumenta em uma quantidade não linearmente proporcional ao inverso da quantidade de solo entre dois locais:
vel = vel (t-1) + Av / [Bv + Cv * soil^2(i,j)]
onde: Av, Bv, Cv são coeficientes de velocidade (parâmetros de entrada), e soil(i,j) representa a quantidade de solo entre os vértices do grafo.
Logo, um caminho com menos solo permite que a gota IWD se mova mais rápido do que um caminho com mais solo.
A gota IWD coleta solo durante sua jornada pelo ambiente. Esse solo é removido do caminho que conecta dois locais. A quantidade de solo adicionada à gota IWD é não linearmente proporcional ao tempo necessário para mover o IWD de sua localização atual para a próxima. Este intervalo de tempo é calculado usando leis simples de física para movimento linear:
time(i,j,vel) = R / vel
onde: R representa a distância entre dois pontos.
A quantidade de solo adicionada à gota:
dSoil(i,j) = As / [Bs + Cs * time(i,j,vel)]
onde: As, Bs, Cs são os coeficientes de acúmulo de solo.
A nova quantidade de solo no caminho entre os pontos será:
soil (i+1,j+1) = Po * soil(i,j) + Pn * dSoil(i,j)
onde: Po e Pn são coeficientes do processo de mudança da quantidade de solo.
Assim, o tempo gasto em movimento é inversamente proporcional à velocidade de movimento e diretamente proporcional à distância entre dois pontos. Pode-se dizer que o solo é uma medida quantitativa da informação sobre o ambiente. Essas fórmulas determinam a preferência das gotas por escolher caminhos com baixo nível de solo em vez de caminhos com alto nível de solo. Essa escolha de caminho é feita aplicando uma distribuição aleatória uniforme aos caminhos disponíveis. A probabilidade de escolher o próximo caminho é inversamente proporcional ao nível de solo dos caminhos disponíveis. Assim, caminhos com menor nível de solo têm mais chances de serem escolhidos pelas gotas IWD.
O IWD original foi desenvolvido pelo autor com o objetivo de resolver problemas de busca de caminhos ótimos, como problemas de busca em grafos e problemas do caixeiro viajante. No entanto, este algoritmo não é adequado para resolver os problemas que estamos considerando em nossos testes. Por isso, é necessário adaptar o IWD para resolver nossos problemas de otimização. Por outro lado, os algoritmos descritos no artigo "algoritmos populacionais de otimização" são capazes de resolver problemas de qualquer tipo, incluindo problemas de busca em grafos. Em artigos anteriores, já foi apresentado um algoritmo especializado semelhante que necessitava de modificação, nomeadamente "colônia de formigas (ACO)".
Para adaptar o IWD à capacidade de resolver qualquer problema de otimização, bem como para participar de competições de algoritmos populacionais, primeiro precisamos definir como aplicar o processo de deposição e movimento do solo. Não podemos seguir a abordagem usada no algoritmo ACO, em que os feromônios são equivalentes ao valor da função de adaptação. No caso do IWD, o solo é um indicador dinâmico e não corresponde proporcionalmente à adaptação.
Surgiu a ideia de dividir as coordenadas em setores, semelhante à divisão de um vale de rio em áreas de igual área. A ideia é que, se a posição da gota (agente) melhorar, então a quantidade de solo nos setores correspondentes em todas as coordenadas diminuirá. A mudança quantitativa do solo será determinada pela diferença na mudança da função de adaptação nas duas últimas iterações, normalizada para todas as gotas pela diferença entre a mudança máxima e mínima de adaptação.
O comportamento de movimento das gotas será baseado na escolha aleatória de setores que têm a menor quantidade de solo, ou seja, onde a probabilidade será proporcional à quantidade de solo no setor correspondente. As melhores coordenadas em todas as áreas serão armazenadas no repositório global "leito". Após a gota escolher um setor, será feita uma tentativa de melhorar a coordenada armazenada no repositório de tal forma que a probabilidade da nova coordenada obedecerá a uma lei quadrática, pela qual a nova coordenada estará mais próxima da coordenada anterior com maior probabilidade do que mais longe. A largura do setor dentro do qual a nova coordenada será determinada é um parâmetro externo e expressa em partes do tamanho do setor. A ilustração da divisão da coordenada em setores e a distribuição de probabilidade da nova coordenada é mostrada na Figura 1.
Figura 1. Divisão de coordenada em setores e distribuição de probabilidade de escolha da nova coordenada nas proximidades da melhor conhecida.
Com base nas disposições e conceitos acima do IWD, podemos compor o pseudocódigo dividido por etapas:
- Geração aleatória de gotas (primeira iteração)
- Calcular a função de adaptação (FF)
- Atualizar o melhor resultado global
- Geração aleatória de gotas (segunda iteração)
- Calcular a função de adaptação (FF)
- Atualizar o melhor resultado global
- Calcular a mudança de altura de cada gota (altura atual e anterior)
- Atualizar alturas por setores
- Novas gotas (escolher probabilisticamente um setor, gota nas proximidades do poço conhecido)
- Calcular a função de adaptação (FF)
- Atualizar o melhor resultado global
- Repetir a partir do passo 7
Vamos agora proceder à análise do código.
Agente de pesquisa "gota" representado pela estrutura S_Drop, contendo os seguintes campos:
- Init (int coords): função que inicializa o objeto da estrutura, recebendo como argumento o número de coordenadas "coords". Dentro da função, ocorre a alteração dos tamanhos dos arrays "c" e "rSection" para o número especificado de coordenadas, além da inicialização das variáveis "f", "fPrev" e "altChange"
- c: array para armazenar coordenadas
- rSection: array para armazenar seções do rio
- f: indicador de adaptação (fitness) para essa gota (drop)
- fPrev: valor anterior do indicador de adaptação
- altChange: mudança de altura
struct S_Drop { void Init (int coords) { ArrayResize (c, coords); ArrayResize (rSection, coords); f = -DBL_MAX; fPrev = -DBL_MAX; altChange = 0.0; } double c []; //coordinates int rSection []; //river section (number of cells: number of coordinates, cell value: sector index on the coordinate) double f; //fitness double fPrev; //previous fitness double altChange; //change in altitude };
Precisaremos de um repositório onde será descrito o rio (melhores coordenadas das profundidades e as próprias profundidades), então chamaremos essa estrutura de S_Riverbed:
- riverbedDepth: array para armazenar as profundidades do leito do rio, o número de células no array corresponde ao número de setores na coordenada, e o valor de cada célula - profundidade do leito no setor correspondente
- coordOnSector: array para armazenar a coordenada específica do lugar mais profundo no setor, o número de células no array corresponde ao número de setores na coordenada, e o valor de cada célula - coordenada no setor correspondente.
//—————————————————————————————————————————————————————————————————————————————— struct S_Riverbed //riverbed { double riverbedDepth []; //riverbed depth double coordOnSector []; //coordinate on the sector }; //——————————————————————————————————————————————————————————————————————————————
Declararemos a classe C_AO_IWDm (m - modificado), que implementa o algoritmo de otimização artificial baseado em gotas de água. Aqui está a descrição de cada elemento da classe:
Propriedades da classe:
- cB: array para armazenar as melhores coordenadas
- fB: armazena o valor da função objetivo para as melhores coordenadas
- p: array para partículas (gotas de água)
- arrays "rangeMax", "rangeMin" e "rangeStep" são usados para definir o alcance de busca
Métodos da classe:
- Init: inicializa o objeto da classe C_AO_IWDm com parâmetros especificados: "coordsP" - número de coordenadas, "popSizeP" - tamanho da população, "sectorsNumberP" - número de setores, "waterViscosityP" - viscosidade da água.
- Moving: realiza o movimento das gotas de água
- Revision: realiza a revisão do estado das gotas de água
- coords: número de coordenadas
- popSize: número de gotas
- sectorsNumber: número de setores
- waterViscosity: coeficiente de viscosidade da água, em partes do tamanho do setor
- sectorSpace: tamanho do setor
- rb: array por coordenadas, para descrever o leito do rio
- iterationCounter
- revision: flag indicando a necessidade de revisão
- SeInDiSp: calcula o novo valor da coordenada no alcance especificado com o passo determinado
- RNDfromCI: gera um número aleatório no intervalo especificado
- Scale: escala um número para o alcance especificado
//—————————————————————————————————————————————————————————————————————————————— class C_AO_IWDm { //---------------------------------------------------------------------------- public: double cB []; //best coordinates public: double fB; //FF of the best coordinates public: S_Drop p []; //particles (drops) public: double rangeMax []; //maximum search range public: double rangeMin []; //manimum search range public: double rangeStep []; //step search public: void Init (const int coordsP, //coordinates number const int popSizeP, //population size const int sectorsNumberP, //sectors number const double waterViscosityP); //water viscosity (>= 1) public: void Moving (); public: void Revision (); //---------------------------------------------------------------------------- private: int coords; //coordinates number private: int popSize; //population size private: int sectorsNumber; //sectors number private: double waterViscosity; //water viscosity private: double sectorSpace []; //sector space private: S_Riverbed rb []; //riverbed private: int iterationCounter; 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 Init inicializa o objeto da classe C_AO_IWDm com os parâmetros especificados: número de coordenadas, número de gotas, número de setores, viscosidade da água.
Este método executa as seguintes ações:
1. Redefine o gerador de números aleatórios.
2. Inicializa o valor da função objetivo "fB" com o valor "-DBL_MAX"
3. Define o contador de iterações em zero
4. Define o número de coordenadas "coords" e o tamanho da população "popSize" para os valores especificados
5. Define o número de setores "sectorsNumber" e a viscosidade da água "waterViscosity" para os valores especificados
6. Altera o tamanho do array "sectorSpace" para "coord"
7. Altera o tamanho do array "p" para "popSize" e inicializa cada gota de água no array "p"
8. Altera os tamanhos dos arrays "rangeMax", "rangeMin", "rangeStep" e "cB" para "coords"
9. Altera o tamanho do array "rb" para "coords" e inicializa cada elemento do array "rb", incluindo os arrays "riverbedDepth" e "coordOnSector", definindo seus valores padrão
//—————————————————————————————————————————————————————————————————————————————— void C_AO_IWDm::Init (const int coordsP, //coordinates number const int popSizeP, //population size const int sectorsNumberP, //sectors number const double waterViscosityP) //water viscosity (>= 1) { MathSrand ((int)GetMicrosecondCount ()); // reset of the generator fB = -DBL_MAX; iterationCounter = 0; coords = coordsP; popSize = popSizeP; sectorsNumber = sectorsNumberP; waterViscosity = waterViscosityP; ArrayResize (sectorSpace, coords); ArrayResize (p, popSize); for (int i = 0; i < popSize; i++) p [i].Init (coords); ArrayResize (rangeMax, coords); ArrayResize (rangeMin, coords); ArrayResize (rangeStep, coords); ArrayResize (cB, coords); ArrayResize (rb, coords); for (int i = 0; i < coords; i++) { ArrayResize (rb [i].riverbedDepth, sectorsNumber); ArrayResize (rb [i].coordOnSector, sectorsNumber); ArrayInitialize (rb [i].riverbedDepth, 0.0); ArrayInitialize (rb [i].coordOnSector, -DBL_MAX); } } //——————————————————————————————————————————————————————————————————————————————
Vamos examinar em partes o método Moving ().
Este bloco de código é executado apenas nas primeiras e segundas iterações. Ele calcula e define o tamanho de cada setor "sectorSpace" para cada coordenada. O tamanho do setor é determinado dividindo o intervalo de valores "rangeMax - rangeMin" pelo número de setores "sectorsNumber".
Em seguida, as gotas são inicializadas com valores iniciais baseados em valores aleatórios nos intervalos especificados com uma distribuição uniforme.
//---------------------------------------------------------------------------- if (iterationCounter == 0) { for (int i = 0; i < coords; i++) sectorSpace [i] = (rangeMax [i] - rangeMin [i]) / sectorsNumber; } //1,4------------------------------------------------------------------------- if (iterationCounter == 0 || iterationCounter == 1) { double min = 0.0; double max = 0.0; int s = 0; for (int i = 0; i < popSize; i++) { p [i].fPrev = p [i].f; for (int c = 0; c < coords; c++) { s = (int)(RNDfromCI (0, sectorsNumber)); if (s >= sectorsNumber) s = sectorsNumber - 1; p [i].rSection [c] = s; min = rangeMin [c] + sectorSpace [c] * s; max = min + sectorSpace [c]; p [i].c [c] = SeInDiSp (RNDfromCI (min, max), rangeMin [c], rangeMax [c], rangeStep [c]); } } for (int i = 0; i < popSize; i++) p [i].fPrev = p [i].f; return; }
O próximo fragmento de código realiza o cálculo e a normalização das mudanças de altura "altChange" para cada gota na população. A única complicação neste código é a verificação da igualdade entre a mudança de altura máxima e mínima, para evitar a divisão por "0"; neste caso, assumimos que não houve mudanças nas alturas das gotas.
O valor "altChange" para cada gota é calculado como um valor normalizado, que é ajustado para o intervalo de 0 a 1. A normalização é feita subtraindo "minAltChange" de "altChange" e dividindo o resultado pela diferença entre "maxAltChange" e "minAltChange".
//7--------------------------------------------------------------------------- double maxAltChange = -DBL_MAX; double minAltChange = DBL_MAX; double altChange = 0.0; double randSC = 0.0; //random selection component double maxRC = 0.0; double nowRC = 0.0; int indSector = 0; for (int i = 0; i < popSize; i++) { altChange = fabs (p [i].f - p [i].fPrev); p [i].altChange = altChange; if (altChange < minAltChange) minAltChange = altChange; if (altChange > maxAltChange) maxAltChange = altChange; } if (minAltChange == maxAltChange) { for (int i = 0; i < popSize; i++) { p [i].altChange = 0.0; } } else { for (int i = 0; i < popSize; i++) { altChange = p [i].altChange; p [i].altChange = (altChange - minAltChange) / (maxAltChange - minAltChange); } }
O próximo fragmento de código atualiza a profundidade do leito do rio para cada coordenada, se o valor atual da função de adaptação for maior que o valor anterior para a gota correspondente. Isso permite levar em conta as mudanças de altura e influenciar a forma do leito do rio. Assim, sempre que uma gota melhora sua posição, consideramos que o leito do rio mudou.
//8--------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { if (p [i].f > p [i].fPrev) { for (int c = 0; c < coords; c++) { rb [c].riverbedDepth [p [i].rSection [c]] += p [i].altChange; } } }
No próximo fragmento de código, duas ações principais são realizadas para alterar as coordenadas dos agentes, fornecendo a estratégia de busca:
- a gota seleciona outra gota aleatoriamente na população e empresta dela o número do setor, garantindo as propriedades combinatórias do algoritmo
- a gota escolhe aleatoriamente um setor do rio proporcionalmente à profundidade conhecida em cada setor
Assim que o setor é escolhido, uma nova coordenada é gerada para a gota com uma distribuição uniforme se o setor foi tomado de outra gota, e com uma distribuição de função quadrática se o setor foi escolhido a partir da informação armazenada no leito do rio. O valor obtido para cada coordenada é ajustado para o intervalo permitido.
//9--------------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { n = (int)(RNDfromCI (0, popSize)); if (n >= popSize) n = popSize - 1; if (p [n].f > p [i].f) { p [i].rSection [c] = p [n].rSection [c]; min = rangeMin [c] + sectorSpace [c] * p [i].rSection [c]; max = min + sectorSpace [c]; p [i].c [c] = SeInDiSp (RNDfromCI (min, max), rangeMin [c], rangeMax [c], rangeStep [c]); } else { randSC = RNDfromCI (0.0, 1.0); nowRC = rb [c].riverbedDepth [0] * randSC; maxRC = nowRC; indSector = 0; for (int r = 1; r < sectorsNumber; r++) { nowRC = rb [c].riverbedDepth [r] * randSC; if (nowRC > maxRC) { maxRC = nowRC; indSector = r; } } if (rb [c].coordOnSector [indSector] == -DBL_MAX) { min = rangeMin [c] + sectorSpace [c] * indSector; max = min + sectorSpace [c]; p [i].c [c] = RNDfromCI (min, max); } else { double x = RNDfromCI (-1.0, 1.0); double y = x * x; double pit = 0.0; double dif = Scale (y, 0.0, 1.0, 0.0, sectorSpace [c] * waterViscosity, false); pit = rb [c].coordOnSector [indSector]; pit += x > 0.0 ? dif : -dif; p [i].c [c] = pit; } min = rangeMin [c] + sectorSpace [c] * indSector; max = min + sectorSpace [c]; p [i].c [c] = SeInDiSp (p [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); p [i].rSection [c] = indSector; } } }
Em seguida, atualizamos o valor anterior de adaptação "fPrev" para cada gota de água, se o valor atual da função objetivo `f` for maior que o valor anterior. Isso permite monitorar a mudança na função objetivo e usar essa informação no algoritmo para tomar decisões sobre o próximo passo.
for (int i = 0; i < popSize; i++) { if (p [i].f > p [i].fPrev) p [i].fPrev = p [i].f; }
E, finalmente, o método Revision. Ele é projetado para atualizar a melhor solução "cB" e o valor de adaptação correspondente. Se uma solução melhor for encontrada na iteração atual, a coordenada do setor correspondente é salva. Assim, o leito do rio lembra os locais mais profundos em cada setor para cada coordenada. Neste método, aumentamos o contador de iterações "iterationCounter" em uma unidade, para que no método Moving possamos nos orientar e executar as ações correspondentes às iterações.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_IWDm::Revision () { //3,6,11---------------------------------------------------------------------- for (int i = 0; i < popSize; i++) { if (p [i].f > fB) { fB = p [i].f; ArrayCopy (cB, p [i].c, 0, 0, WHOLE_ARRAY); for (int c = 0; c < coords; c++) { rb [c].coordOnSector [p [i].rSection [c]] = p [i].c [c]; } } else { for (int c = 0; c < coords; c++) { if (rb [c].coordOnSector [p [i].rSection [c]] == -DBL_MAX) { rb [c].coordOnSector [p [i].rSection [c]] = p [i].c [c]; } } } } iterationCounter++; } //——————————————————————————————————————————————————————————————————————————————
3. Versão modificada do SDSm
Os resultados do algoritmo IWDm serão discutidos posteriormente, mas eles nos deram a ideia de tentar melhorar outro algoritmo, o melhor na classificação, o SDS, porque tanto o IWDm quanto o SDS usam entidades semelhantes (setores e restaurantes, respectivamente). O método utilizado no IWD, especificamente o uso do refinamento de coordenadas com uma distribuição de probabilidade baseada em função quadrática, ajudou a melhorar ainda mais o SDS: essa técnica de refinamento da melhor posição teve um grande impacto nos resultados finais dos testes. A única diferença é que no SDSm, a distribuição é truncada se ultrapassar para um restaurante adjacente.
Mudanças foram feitas no método Revision do algoritmo SDS, e devido às mudanças significativas na distribuição de novas coordenadas dentro do restaurante (anteriormente era uniforme) e aos resultados dos testes, o algoritmo foi indexado com "m".
No código, vemos que agora a função responsável pela distribuição da variável aleatória é a função Research, que aceita como argumentos o coeficiente de largura da distribuição, o endereço do restaurante, o tamanho do restaurante, o valor mínimo possível para a coordenada, o passo da coordenada, a adaptação no passo anterior, e a coordenada que estamos tentando melhorar.
No algoritmo SDSm, tentamos melhorar três tipos de coordenadas (pratos nos restaurantes):
- a coordenada do candidato entrevistado
- a melhor coordenada em um restaurante escolhido aleatoriamente (assim como no IWDm para o leito do rio, no SDSm mantemos as melhores coordenadas para todos os restaurantes - isso é como manter uma lista dos melhores pratos em todos os restaurantes da cidade)
- a própria coordenada para o restaurante correspondente
Os coeficientes de largura da distribuição de probabilidade poderiam ser externos, mas escolhi não fazer isso, estabelecendo os melhores valores, na minha opinião.
//—————————————————————————————————————————————————————————————————————————————— void C_AO_SDSm::Revision () { /* here is the old code, no changes */ for (int i = 0; i < populationSize; i++) { for (int c = 0; c < coords; c++) { n = (int)(RNDfromCI (0, populationSize)); if (n >= populationSize) n = populationSize - 1; if (cands [n].fPrev > cands [i].fPrev) { cands [i].raddr [c] = cands [n].raddrPrev [c]; Research (0.25, cands [i].raddr [c], restSpace [c], rangeMin [c], rangeStep [c], cands [n].cPrev [c], cands [i].c [c]); } else { rnd = RNDfromCI (0.0, 1.0); if (rnd < probabRest) { n = (int)(RNDfromCI (0, restNumb)); if (n >= restNumb) n = restNumb - 1; cands [i].raddr [c] = n; Research (1.0, cands [i].raddr [c], restSpace [c], rangeMin [c], rangeStep [c], rb [c].coordOnSector [n], cands [i].c [c]); } else { cands [i].raddr [c] = cands [i].raddrPrev [c]; Research (0.25, cands [i].raddr [c], restSpace [c], rangeMin [c], rangeStep [c], cands [i].cPrev [c], cands [i].c [c]); } } } } } //——————————————————————————————————————————————————————————————————————————————
E aqui está aquela "mágica" função Research, que permitiu melhorar o líder anterior dos testes em mais de 12%.
A função faz o seguinte:
- gera um número aleatório no intervalo [-1.0; 1.0],
- o valor obtido é escalado para um incremento correspondente ao tamanho do restaurante com um coeficiente de escala de distribuição
- adicionado à coordenada atual que está sendo melhorada
- são definidos os limites do restaurante
- o número é ajustado para valores permitidos de acordo com o passo do parâmetro otimizado, truncado pelos limites do restaurante
//—————————————————————————————————————————————————————————————————————————————— void C_AO_SDSm::Research (const double ko, const int raddr, const double restSpaceI, const double rangeMinI, const double rangeStepI, const double pitOld, double &pitNew) { double x = RNDfromCI(-1.0, 1.0); double y = x * x; double pit = pitOld; double min = 0.0; double max = 0.0; double dif = Scale(y, 0.0, 1.0, 0.0, restSpaceI * ko, false); pit += x > 0.0 ? dif : -dif; min = rangeMinI + restSpaceI * raddr; max = min + restSpaceI; pitNew = SeInDiSp (pit, min, max, rangeStepI); } //——————————————————————————————————————————————————————————————————————————————
4. Resultados dos testes
Impressão dos resultados do algoritmo IWD na bancada de testes:
C_AO_IWDm:50;10;3.0
=============================
5 Rastrigin's; Func runs 10000 result: 63.304838882364926
Score: 0.78438
25 Rastrigin's; Func runs 10000 result: 49.20424466627239
Score: 0.60967
500 Rastrigin's; Func runs 10000 result: 39.68464591598694
Score: 0.49172
=============================
5 Forest's; Func runs 10000 result: 0.6975685023058024
Score: 0.39458
25 Forest's; Func runs 10000 result: 0.19878497533879688
Score: 0.11244
500 Forest's; Func runs 10000 result: 0.0569274044494088
Score: 0.03220
=============================
5 Megacity's; Func runs 10000 result: 3.44
Score: 0.28667
25 Megacity's; Func runs 10000 result: 1.088
Score: 0.09067
500 Megacity's; Func runs 10000 result: 0.28480000000000005
Score: 0.02373
=============================
All score: 2.82606
Os resultados são, para dizer o mínimo, abaixo da média, conforme a tabela comparativa.
Impressão dos resultados do algoritmo SDSm na bancada de testes:
C_AO_SDSm:100;100;0.05
=============================
5 Rastrigin's; Func runs 10000 result: 80.65976429448276
Score: 0.99942
25 Rastrigin's; Func runs 10000 result: 79.95659847225565
Score: 0.99071
500 Rastrigin's; Func runs 10000 result: 57.23107170601535
Score: 0.70913
=============================
5 Forest's; Func runs 10000 result: 1.7241883676504082
Score: 0.97529
25 Forest's; Func runs 10000 result: 1.497160007591401
Score: 0.84687
500 Forest's; Func runs 10000 result: 0.29481739063639945
Score: 0.16676
=============================
5 Megacity's; Func runs 10000 result: 10.559999999999999
Score: 0.88000
25 Megacity's; Func runs 10000 result: 6.824000000000001
Score: 0.56867
500 Megacity's; Func runs 10000 result: 1.2384
Score: 0.10320
=============================
All score: 6.24004
Os resultados do SDSm são realmente impressionantes.
Na animação visualizada do IWDm, é perceptível uma certa capacidade de agrupar potenciais boas áreas de pesquisa, especialmente notável na função Rastrigin. No entanto, ao longo dos trechos prolongados e suaves do gráfico de convergência, também é visível a estagnação do algoritmo.
IWDm na função de teste Rastrigin.
IWDm na função de teste Forest.
IWDm na função de teste Megacity.
Este artigo analisou o IWDm, que ficou em 19º lugar entre 22 algoritmos, ou 4º lugar de baixo para cima, superando o conhecido e popular algoritmo PSO. O IWDm mostra melhores resultados em funções suaves. A melhoria contínua do gráfico de convergência nas três funções de teste dá esperança de que, com o aumento do número de iterações, o algoritmo continuará a convergir, mas então perde-se o sentido prático e a viabilidade de sua aplicação, uma vez que a condição dos testes é rigorosa, 10000 iterações, nem mais nem menos.
Além disso, deve-se destacar o algoritmo modificado SDSm, que alcançou 7 dos 9 primeiros lugares possíveis. Este algoritmo é um verdadeiro "decatleta" entre os algoritmos de otimização. O aprimoramento dos resultados do SDSm em comparação com o SDS regular é particularmente notável nas funções "agudas" Forest e na complexa função discreta Megacity (nesta última, a melhoria foi de quase 30% com 1000 parâmetros). Assim, além do principal herói do artigo, o IWD, vemos um novo e esplêndido convidado na tabela - SDSm. A animação do trabalho do SDS pode ser vista aqui, e para ver o funcionamento do SDSm é necessário executar o script de teste do arquivo, que está na pasta do SDS.
| № | AO | Description | Rastrigin | Rastrigin final | Forest | Forest final | Megacity (discrete) | Megacity final | Final result | ||||||
| 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1000 p (500 F) | |||||||
| 1 | SDSm | stochastic diffusion search M | 0,99809 | 1,00000 | 0,69149 | 2,68958 | 1,00000 | 1,00000 | 1,00000 | 3,00000 | 1,00000 | 1,00000 | 1,00000 | 3,00000 | 100,000 |
| 2 | SDS | stochastic Diffusion Search | 0,99737 | 0,97322 | 0,58904 | 2,55963 | 0,96778 | 0,93572 | 0,79649 | 2,69999 | 0,78696 | 0,93815 | 0,71804 | 2,44315 | 88,208 |
| 3 | SSG | saplings sowing and growing | 1,00000 | 0,92761 | 0,51630 | 2,44391 | 0,72654 | 0,65201 | 0,83760 | 2,21615 | 0,54782 | 0,61841 | 0,99522 | 2,16146 | 77,678 |
| 4 | HS | harmony search | 0,99676 | 0,88385 | 0,44686 | 2,32747 | 0,99882 | 0,68242 | 0,37529 | 2,05653 | 0,71739 | 0,71842 | 0,41338 | 1,84919 | 70,647 |
| 5 | IWO | invasive weed optimization | 0,95828 | 0,62227 | 0,27647 | 1,85703 | 0,70690 | 0,31972 | 0,26613 | 1,29275 | 0,57391 | 0,30527 | 0,33130 | 1,21048 | 48,267 |
| 6 | ACOm | ant colony optimization M | 0,34611 | 0,16683 | 0,15808 | 0,67103 | 0,86785 | 0,68980 | 0,64798 | 2,20563 | 0,71739 | 0,63947 | 0,05579 | 1,41265 | 47,419 |
| 7 | MEC | mind evolutionary computation | 0,99270 | 0,47345 | 0,21148 | 1,67763 | 0,60691 | 0,28046 | 0,21324 | 1,10061 | 0,66957 | 0,30000 | 0,26045 | 1,23002 | 44,061 |
| 8 | COAm | cuckoo optimization algorithm M | 0,92400 | 0,43407 | 0,24120 | 1,59927 | 0,58309 | 0,23477 | 0,13842 | 0,95629 | 0,52174 | 0,24079 | 0,17001 | 0,93254 | 37,845 |
| 9 | FAm | firefly algorithm M | 0,59825 | 0,31520 | 0,15893 | 1,07239 | 0,51012 | 0,29178 | 0,41704 | 1,21894 | 0,24783 | 0,20526 | 0,35090 | 0,80398 | 33,152 |
| 10 | ABC | artificial bee colony | 0,78170 | 0,30347 | 0,19313 | 1,27829 | 0,53774 | 0,14799 | 0,11177 | 0,79750 | 0,40435 | 0,19474 | 0,13859 | 0,73768 | 29,784 |
| 11 | BA | bat algorithm | 0,40526 | 0,59145 | 0,78330 | 1,78002 | 0,20817 | 0,12056 | 0,21769 | 0,54641 | 0,21305 | 0,07632 | 0,17288 | 0,46225 | 29,488 |
| 12 | CSS | charged system search | 0,56605 | 0,68683 | 1,00000 | 2,25289 | 0,14065 | 0,01853 | 0,13638 | 0,29555 | 0,07392 | 0,00000 | 0,03465 | 0,10856 | 27,914 |
| 13 | GSA | gravitational search algorithm | 0,70167 | 0,41944 | 0,00000 | 1,12111 | 0,31623 | 0,25120 | 0,27812 | 0,84554 | 0,42609 | 0,25525 | 0,00000 | 0,68134 | 27,807 |
| 14 | BFO | bacterial foraging optimization | 0,67203 | 0,28721 | 0,10957 | 1,06881 | 0,39655 | 0,18364 | 0,17298 | 0,75317 | 0,37392 | 0,24211 | 0,18841 | 0,80444 | 27,549 |
| 15 | EM | electroMagnetism-like algorithm | 0,12235 | 0,42928 | 0,92752 | 1,47915 | 0,00000 | 0,02413 | 0,29215 | 0,31628 | 0,00000 | 0,00527 | 0,10872 | 0,11399 | 18,981 |
| 16 | SFL | shuffled frog-leaping | 0,40072 | 0,22021 | 0,24624 | 0,86717 | 0,20129 | 0,02861 | 0,02221 | 0,25211 | 0,19565 | 0,04474 | 0,06607 | 0,30646 | 13,201 |
| 17 | MA | monkey algorithm | 0,33192 | 0,31029 | 0,13582 | 0,77804 | 0,10000 | 0,05443 | 0,07482 | 0,22926 | 0,15652 | 0,03553 | 0,10669 | 0,29874 | 11,771 |
| 18 | FSS | fish school search | 0,46812 | 0,23502 | 0,10483 | 0,80798 | 0,12825 | 0,03458 | 0,05458 | 0,21741 | 0,12175 | 0,03947 | 0,08244 | 0,24366 | 11,329 |
| 19 | IWDm | intelligent water drops M | 0,26459 | 0,13013 | 0,07500 | 0,46972 | 0,28568 | 0,05445 | 0,05112 | 0,39126 | 0,22609 | 0,05659 | 0,05054 | 0,33322 | 10,434 |
| 20 | PSO | particle swarm optimisation | 0,20449 | 0,07607 | 0,06641 | 0,34696 | 0,18873 | 0,07233 | 0,18207 | 0,44313 | 0,16956 | 0,04737 | 0,01947 | 0,23641 | 8,431 |
| 21 | RND | random | 0,16826 | 0,09038 | 0,07438 | 0,33302 | 0,13480 | 0,03318 | 0,03949 | 0,20747 | 0,12175 | 0,03290 | 0,04898 | 0,20363 | 5,056 |
| 22 | GWO | grey wolf optimizer | 0,00000 | 0,00000 | 0,02093 | 0,02093 | 0,06562 | 0,00000 | 0,00000 | 0,06562 | 0,23478 | 0,05789 | 0,02545 | 0,31812 | 1,000 |
Considerações finais
O algoritmo original IWD foi desenvolvido pelo autor com o objetivo de resolver problemas de busca de caminhos mais curtos, como logística de transporte, roteamento de redes e busca de caminhos ótimos em sistemas de informações geográficas. Este artigo não explorou suas capacidades e eficácia nessas tarefas específicas, e o novo algoritmo modificado IWDm, apresentado como universal, não conseguiu mostrar resultados impressionantes. Aumentar o número de setores, infelizmente, não levou a uma maior eficiência do algoritmo.
No entanto, o trabalho no IWDm deixou a impressão de que o potencial deste elegante algoritmo ainda não foi totalmente explorado. A ideia de dividir o espaço de busca em setores e considerar sua classificação, baseada na modelagem do movimento do solo no leito do rio, parece muito interessante. Conforme mostrado pelos resultados, essa abordagem, por exemplo, de manter os melhores pratos em cada restaurante, e possivelmente usar o deslocamento de probabilidade de um novo ponto nas proximidades do anterior, melhorou significativamente as características do algoritmo SDS.
Importante, se aumentarmos o número de restaurantes no novo SDSm (padrão de 100) e dividirmos as coordenadas em partes menores (no SDS usa-se um parâmetro de 1000), os resultados pioram. Isso significa que, com essa abordagem, escolher um restaurante específico torna-se mais importante, e um ponto específico em suas proximidades deixa de ser significativo (o algoritmo se transforma no SDS regular). Desta forma, a distribuição de probabilidade quadrática tem o maior impacto quando o tamanho dos setores nas coordenadas é certo. Isso representa um tipo de equilíbrio entre os vários métodos com diferentes objetivos presentes no algoritmo.
A conclusão mais importante deste artigo é que não se pode afirmar definitivamente quais técnicas ou métodos usados em estratégias de busca individuais são os melhores ou piores. A aplicação de diferentes métodos pode tanto deteriorar alguns algoritmos quanto melhorar significativamente outros. O que importa é a combinação de métodos utilizados nos algoritmos de otimização, e não os métodos individualmente.
Figura 2. Graduação de cores dos algoritmos de acordo com os testes correspondentes.
Histograma dos resultados dos testes dos algoritmos na Figura 3 (em uma escala de 0 a 100, quanto maior, melhor, no arquivo há um script para calcular a tabela de classificação de acordo com a metodologia neste artigo):
Figura 3. Histograma dos resultados finais dos testes dos algoritmos.
Prós e contras do algoritmo modificado de gotas de água inteligentes (IWDm):
Prós:
1. Poucos parâmetros externos.
Contras:
1. Resultados modestos em funções suaves e discretas.
2. Baixa convergência.
3. Tendência a ficar preso em extremos locais.
O artigo inclui um arquivo com versões atualizadas dos códigos dos algoritmos descritos nos artigos anteriores. O autor do artigo não assume responsabilidade pela precisão absoluta na descrição dos algoritmos canônicos, muitos deles foram modificados para melhorar os recursos de pesquisa. As conclusões e julgamentos apresentados nos artigos são baseados nos resultados dos experimentos realizados.
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/13730
Padrões de projeto no MQL5 (Parte I): Padrões criacionais (creational patterns)
Quantificação no aprendizado de máquina (Parte 2): Pré-processamento de dados, seleção de tabelas, treinamento do modelo CatBoost
Criando um Expert Advisor simples multimoeda usando MQL5 (Parte 3): Prefixos/sufixos de símbolos e sessão de negociação
Quantificação no aprendizado de máquina (Parte 1): Teoria, exemplo de código, análise da implementação no CatBoost
- 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