Algoritmo de estrutura cristalina, Crystal Structure Algorithm (CryStAl)
17
0
Sumário
Introdução
Durante uma análise, tive a oportunidade de estudar um dos algoritmos de otimização cuja implementação revelou algumas "armadilhas" de uma ideia promissora. Apresento o Crystal Structure Algorithm (CryStAl), um algoritmo meta-heurístico de otimização inspirado no processo físico de formação de estruturas cristalinas. Ele foi proposto em 2021 pelos pesquisadores A. Kaveha e M. Kooshkebaghi e publicado no artigo de Siamak Talatahari. O CryStAl modela a formação de cristais, em que as soluções representam átomos e a busca pelo ótimo corresponde ao ordenamento desses átomos em uma estrutura estável. O algoritmo utiliza uma base e um retículo cristalino como analogia para a distribuição espacial das soluções, emprega simetria e regularidade para formar uma população equilibrada e aplica critérios energéticos para descartar soluções instáveis.
Implementação do algoritmo
Vamos examinar o funcionamento do algoritmo CryStAl por meio de um pseudocódigo detalhado de todas as suas etapas:
Parâmetros de entrada do algoritmo
Tamanho da população de cristais, quantidade de cristais na população (normalmente 30)
Quantidade de cristais aleatórios, número de cristais selecionados aleatoriamente para calcular Fc (normalmente 3)
Dimensionalidade do problema, número de variáveis a serem otimizadas
Número máximo de iterações, quantidade de vezes que o algoritmo repetirá o laço de otimização
Limites de busca, valores mínimo e máximo de cada variável
ETAPA 1: INICIALIZAÇÃO DA POPULAÇÃO
Criação dos cristais iniciais
Para cada cristal da população e para cada coordenada (variável) desse cristal:
- Fórmula 3, inicialização aleatória: Nova coordenada = Limite mínimo + Número aleatório × (Limite máximo - Limite mínimo), em que Número aleatório segue uma distribuição uniforme de 0 a 1
Calcular o valor da função de fitness desse cristal e registrar seus recordes individuais
Inicialização dos recordes globais
Encontrar o cristal com o maior valor da função de fitness
Encontrar o cristal com o maior valor da função de fitness
ETAPA 2: LAÇO PRINCIPAL DE OTIMIZAÇÃO
Repetir as etapas a seguir da primeira até a última iteração:
PASSO 1: Cálculo da posição média de todos os cristais (Cr_main)
Para cada coordenada: inicializar a soma dessa coordenada com zero
Para cada cristal da população: adicionar à soma o valor dessa coordenada no cristal
Dividir a soma pela quantidade de cristais para obter o valor médio
Resultado: obtém-se um vetor com os valores médios de todas as coordenadas
PASSO 2: Determinação do melhor cristal (Cr_b)
Definir o índice do melhor cristal como o índice do primeiro cristal
Para cada cristal seguinte, do segundo ao último:
Se o fitness desse cristal for maior que o fitness do melhor cristal atual: atualizar o índice do melhor cristal com o índice desse cristal
Resultado: obtém-se o índice do cristal com o melhor valor da função de fitness
PASSO 3: Atualização das posições de todos os cristais
Para cada cristal da população:
Etapa 3.1: Armazenamento do estado atual
Salvar a posição atual do cristal como posição anterior
Etapa 3.2: Seleção da estratégia de atualização
Selecionar aleatoriamente uma das quatro estratégias de atualização:
- Estratégia 0: Atualização cúbica simples
- Estratégia 1: Atualização cúbica com o melhor cristal
- Estratégia 2: Atualização cúbica com a média de cristais aleatórios
- Estratégia 3: Atualização combinada com o melhor cristal e a média
Etapa 3.3: Aplicação da estratégia selecionada
SE a ESTRATÉGIA 0 for selecionada, Atualização cúbica simples:
Para cada coordenada do cristal: gerar um número aleatório r de 0 a 1
- Fórmula 4, Nova coordenada = Coordenada anterior + r × Coordenada média de todos os cristais
CASO CONTRÁRIO, SE a ESTRATÉGIA 1 for selecionada, Com o melhor cristal:
Para cada coordenada do cristal: gerar dois números aleatórios r1 e r2 de 0 a 1
- Fórmula 5, Nova coordenada = Coordenada anterior + r1 × Coordenada média de todos os cristais + r2 × Coordenada do melhor cristal
CASO CONTRÁRIO, SE a ESTRATÉGIA 2 for selecionada, Com a média de cristais aleatórios:
Subetapa 2.1: Cálculo da média de cristais aleatórios (Fc)
Para cada coordenada: inicializar a soma dessa coordenada com zero
Repetir o número especificado de vezes (normalmente 3): selecionar aleatoriamente um cristal da população, excluindo o cristal que está sendo processado
Para cada coordenada: adicionar à soma o valor dessa coordenada no cristal selecionado aleatoriamente
Para cada coordenada: dividir a soma pela quantidade de cristais aleatórios selecionados
Resultado: obtém-se a média de vários cristais selecionados aleatoriamente
Subetapa 2.2: Atualização da posição
Para cada coordenada do cristal: gerar dois números aleatórios r1 e r2 de 0 a 1
- Fórmula 6, Nova coordenada = Coordenada anterior + r1 × Coordenada média de todos os cristais + r2 × Coordenada média dos cristais aleatórios
CASO CONTRÁRIO, foi selecionada a ESTRATÉGIA 3, Combinada:
Subetapa 3.1: Cálculo da média de cristais aleatórios (Fc)
(Executado exatamente da mesma forma que na estratégia 2)
Subetapa 3.2: Atualização da posição
- Para cada coordenada do cristal: gerar três números aleatórios r1, r2 e r3 de 0 a 1
- Fórmula 7, Nova coordenada = Coordenada anterior + r1 × Coordenada média de todos os cristais + r2 × Coordenada do melhor cristal + r3 × Coordenada média dos cristais aleatórios
Etapa 3.4: Tratamento da ultrapassagem dos limites (Boundary Handling)
Para cada coordenada da nova posição do cristal: se a coordenada for menor que o limite mínimo OU maior que o limite máximo, o cristal ultrapassou os limites permitidos e precisa ser corrigido
- Gerar um número aleatório de 0 a 1
- Recalcular a coordenada dentro dos limites permitidos: Coordenada = Limite mínimo + Número aleatório × (Limite máximo - Limite mínimo)
Atualizar a posição do cristal com a nova posição calculada
PASSO 4: Avaliação das novas posições e atualização dos melhores e piores resultados
Para cada cristal da população:
Etapa 4.1: Cálculo do fitness
Calcular o valor da função de fitness para a nova posição do cristal
Etapa 4.2: Atualização dos melhores e piores resultados individuais do cristal
Se o novo valor de fitness for melhor que o melhor valor individual: atualizar o melhor valor individual de fitness com o valor atual e salvar a posição atual como a melhor posição individual
Se o novo valor de fitness for pior que o pior valor individual: atualizar o pior valor individual de fitness com o valor atual e salvar a posição atual como a pior posição individual
Etapa 4.3: Atualização dos melhores e piores resultados globais
Se o valor de fitness desse cristal for melhor que o melhor valor global: atualizar o melhor valor global com o fitness desse cristal e salvar a posição desse cristal como a melhor posição global
Se o valor de fitness desse cristal for pior que o pior valor global: atualizar o pior valor global com o fitness desse cristal e salvar a posição desse cristal como a pior posição global
PASSO 5: Passagem para a próxima iteração
Avançar para a próxima iteração do laço principal de otimização
Fim do laço principal de otimização
ETAPA 3: ENCERRAMENTO DA EXECUÇÃO DO ALGORITMO
Após concluir todas as iterações, retornar o resultado:
- A melhor posição global (solução do problema de otimização)
- O melhor valor global da função de fitness
O diagrama da figura abaixo apresenta o esquema do laço principal, a visualização das quatro estratégias e um exemplo do espaço de busca com os cristais.
Figura 1. Fluxograma de funcionamento do algoritmo CryStAl
O algoritmo CryStAl procura manter o equilíbrio entre dois aspectos importantes da otimização:
Diversificação (exploration), exploração de novas regiões do espaço de busca: é promovida pela estratégia 0 por meio do movimento em direção à posição média e reforçada pela estratégia 2 com informações de cristais aleatórios, ajudando a evitar a estagnação em ótimos locais.
Intensificação (exploitation), busca mais aprofundada nas proximidades de boas soluções: é implementada pela estratégia 1 por meio do movimento em direção ao melhor cristal, o que acelera a convergência para o ótimo e permite aproveitar de forma eficiente as informações já obtidas.
Abordagem combinada:
- A estratégia 3 reúne os três componentes
- A seleção aleatória das estratégias em cada iteração proporciona adaptabilidade
- Cada estratégia tem a mesma probabilidade de seleção, 25%
Função dos principais componentes:
Posição média (Cr_main), representa o centro de massa da população, direciona a busca para as regiões centrais das áreas já visitadas do espaço de busca e é atualizada a cada iteração com base nas posições atuais de todos os cristais.
Melhor cristal (Cr_b), contém a melhor solução encontrada até o momento, atrai os demais cristais para uma região promissora e intensifica a busca em torno das boas soluções já encontradas.
Média dos cristais selecionados aleatoriamente (Fc), representa informações locais provenientes dos vizinhos, acrescenta estocasticidade e diversidade à busca e ajuda a evitar a convergência prematura.
Agora que examinamos detalhadamente os princípios de funcionamento do algoritmo, podemos passar à sua implementação em código. Vamos criar a classe "C_AO_CryStAl", derivada da classe "C_AO", para implementar o algoritmo "Crystal Structure Algorithm".
Construtor:- São inicializados dois parâmetros: "popSize" (tamanho da população de cristais, 30 por padrão) e "numRandomCrystals" (quantidade de cristais selecionados aleatoriamente usados em um dos cálculos de "Fc", 3 por padrão).
- Esses parâmetros são adicionados à estrutura que armazena as informações sobre os parâmetros do algoritmo.
- Este método permite atualizar os valores dos parâmetros "popSize" e "numRandomCrystals" com os dados fornecidos por uma estrutura externa de parâmetros.
- É feita uma validação para garantir que "numRandomCrystals" seja sempre pelo menos 1 e não ultrapasse "popSize" menos 1, evitando cálculos inválidos.
- Init (), método responsável pela inicialização do algoritmo, que recebe informações sobre os intervalos e passos das variáveis de entrada, além da quantidade de épocas;
- Moving (), método que implementa a etapa de movimentação dos cristais no algoritmo;
- Revision (), método responsável por revisar ou atualizar o estado da população.
- numRandomCrystals, quantidade de cristais aleatórios usada no cálculo de "Fc".
- meanPosition, array que armazena a posição média de todos os cristais da população;
- bestCrystalIdx, índice do melhor cristal da população atual;
- isFirstIteration, flag booleana que indica se a iteração atual é a primeira após a inicialização;
- CalculateMeanPosition (), método para calcular a posição média dos cristais;
- CalculateFc (), método para calcular o valor de "Fc", um critério que depende dos cristais selecionados;
- SelectRandomCrystal (), método para selecionar aleatoriamente um cristal da população, com a possibilidade de excluir um cristal específico.
De modo geral, a classe "C_AO_CryStAl" implementa um algoritmo de otimização inspirado no comportamento dos cristais. Ela opera sobre uma população de "cristais", cada um com sua própria posição. O algoritmo inclui etapas de movimentação dos cristais, avaliação de seus valores de fitness e determinação da melhor solução.
//———————————————————————————————————————————————————————————————————— class C_AO_CryStAl : public C_AO { public: //---------------------------------------------------------- ~C_AO_CryStAl () { } C_AO_CryStAl () { ao_name = "CryStAl"; ao_desc = "Crystal Structure Algorithm"; ao_link = "https://www.mql5.com/ru/articles/19899"; popSize = 30; // crystal population size numRandomCrystals = 3; // number of random crystals for Fc ArrayResize (params, 2); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "numRandomCrystals"; params [1].val = numRandomCrystals; } void SetParams () { popSize = (int)params [0].val; numRandomCrystals = (int)params [1].val; if (numRandomCrystals < 1) numRandomCrystals = 1; if (numRandomCrystals > popSize - 1) numRandomCrystals = popSize - 1; } bool Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP); void Moving (); void Revision (); //------------------------------------------------------------------ int numRandomCrystals; // number of random crystals for calculating Fc private: //--------------------------------------------------------- double meanPosition []; // the mean position of all crystals (Cr_main) int bestCrystalIdx; // best crystal index bool isFirstIteration; // flag for the first iteration after initialization void CalculateMeanPosition (); void CalculateFc (int currentCrystal, double &fcArray []); int SelectRandomCrystal (int excludeCrystal); }; //————————————————————————————————————————————————————————————————————
O método "Init" é responsável por inicializar o algoritmo "Crystal Structure Algorithm" antes do início de sua execução.
Primeiro, é chamado o método "StandardInit", que executa as operações básicas de preparação comuns a todos os algoritmos derivados de "C_AO". Se essa etapa básica falhar, o método "Init" também falhará. Em seguida, é criado o array "meanPosition" (posição média). O tamanho desse array é definido pela variável "coords", que armazena o número de dimensões. Todos os seus elementos são inicializados com zero. Isso significa que, no início da execução do algoritmo, a posição média de todos os cristais é considerada igual a zero.
Definição dos valores iniciais dos flags:- bestCrystalIdx (índice do melhor cristal) recebe o valor 0. Assim, no início, considera-se que o primeiro cristal da população é o melhor.
- isFirstIteration (flag da primeira iteração) recebe o valor "true". Isso indica que a próxima iteração executada será a primeira após a inicialização completa.
//———————————————————————————————————————————————————————————————————— //--- Initialization bool C_AO_CryStAl::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Array initialization ArrayResize (meanPosition, coords); ArrayInitialize (meanPosition, 0.0); bestCrystalIdx = 0; isFirstIteration = true; return true; } //————————————————————————————————————————————————————————————————————
O método "CalculateMeanPosition" é responsável por calcular a posição média de todos os "cristais" da população. Primeiro, todos os elementos do array "meanPosition" (que armazena a média de cada coordenada) são reinicializados com zero. Dessa forma, antes de começar a somar as posições atuais dos cristais, o cálculo sempre parte do zero.
Em seguida, o método percorre cada cristal da população. Para cada cristal, percorre também todas as suas coordenadas, cujo número é definido por "coords". O valor de cada coordenada do cristal atual é adicionado ao elemento correspondente do array "meanPosition". Assim, "meanPosition" acumula gradualmente a soma dos valores de cada coordenada de todos os cristais.
Depois que a soma é concluída, o método percorre novamente todas as coordenadas. Cada valor acumulado em "meanPosition" é dividido pela quantidade total de cristais "popSize". Essa transformação converte a soma das coordenadas em seu valor médio. Ao final da execução do método, o array "meanPosition" contém o valor médio de cada coordenada considerando todos os cristais da população.
//———————————————————————————————————————————————————————————————————— //--- Calculating the mean position of all crystals (Cr_main) void C_AO_CryStAl::CalculateMeanPosition () { // Reset the mean values to zero ArrayInitialize (meanPosition, 0.0); // Sum the current positions of all crystals for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { meanPosition [c] += a [i].c [c]; } } // Divide by the number of crystals to obtain the mean for (int c = 0; c < coords; c++) { meanPosition [c] /= (double)popSize; } } //————————————————————————————————————————————————————————————————————
O método "CalculateFc" é responsável por calcular a chamada "média dos cristais selecionados aleatoriamente". Ele recebe como entrada o índice do cristal atual "currentCrystal" e o array "fcArray", no qual o resultado será armazenado.
No início, todos os elementos do array "fcArray" são reinicializados com zero. Isso garante que, a cada novo cálculo de "Fc", a soma comece do zero. Em seguida, o método executa um laço que se repete "numRandomCrystals" vezes. Em cada iteração desse laço:
- é selecionado aleatoriamente um índice de cristal "randomCrystal". É importante observar que a seleção exclui o próprio "currentCrystal", ou seja, o cristal para o qual "Fc" está sendo calculado naquele momento;
- as coordenadas do cristal selecionado aleatoriamente são adicionadas aos elementos correspondentes do array "fcArray". Assim, esse array acumula a soma das coordenadas de todos os cristais selecionados aleatoriamente.
Ao final, o array "fcArray" conterá as coordenadas do cristal "médio", obtido pela média das posições de vários cristais selecionados aleatoriamente da população, excluindo o cristal atual.
//———————————————————————————————————————————————————————————————————— //--- Calculation of Fc (average value of randomly selected crystals) void C_AO_CryStAl::CalculateFc (int currentCrystal, double &fcArray []) { // Initialize the array with zeros ArrayInitialize (fcArray, 0.0); // Select numRandomCrystals random crystals (excluding the current one) for (int i = 0; i < numRandomCrystals; i++) { int randomCrystal = SelectRandomCrystal (currentCrystal); // Sum the positions of the selected crystals for (int c = 0; c < coords; c++) { fcArray [c] += a [randomCrystal].c [c]; } } // Calculate the mean value for (int c = 0; c < coords; c++) { fcArray [c] /= (double)numRandomCrystals; } } //————————————————————————————————————————————————————————————————————
O método "SelectRandomCrystal" é responsável por selecionar aleatoriamente um "cristal" de toda a população, com uma condição importante: o cristal indicado por "excludeCrystal" não pode ser selecionado.
O método inicia um laço infinito, que continua até que a condição de saída seja satisfeita. Dentro desse laço, é gerado aleatoriamente um índice no intervalo correspondente aos cristais da população, de 0 a "popSize" menos 1.
Depois que o índice aleatório é gerado, é feita a seguinte verificação:
- se o índice gerado "selected" for igual ao índice do cristal que deve ser excluído, "excludeCrystal", o laço continua e um novo índice aleatório é gerado;
- se o índice gerado for diferente de "excludeCrystal", a condição de saída do laço é satisfeita.
//———————————————————————————————————————————————————————————————————— //--- Selecting a random crystal (excluding the specified one) int C_AO_CryStAl::SelectRandomCrystal (int excludeCrystal) { int selected; do selected = u.RNDminusOne (popSize); while (selected == excludeCrystal); return selected; } //————————————————————————————————————————————————————————————————————
O método "Moving" implementa o principal laço do algoritmo e é responsável pela evolução da população de "cristais" a cada iteração. Na primeira execução do algoritmo, quando "revision" é igual a "false", o método inicializa as posições de todos os cristais da população. Para cada cristal e cada uma de suas coordenadas, é gerado um valor aleatório entre 0 e 1. Esse valor é então escalonado para o intervalo entre rangeMin e rangeMax da respectiva coordenada. Em seguida, aplica-se a discretização para ajustar a posição ao passo permitido "rangeStep". Após a inicialização, o flag "revision" é definido como "true", para que as chamadas seguintes do método executem a atualização das posições em vez de uma nova inicialização.
Após a primeira iteração, calcula-se inicialmente a posição média de todos os cristais da população. O algoritmo identifica o cristal com o melhor valor da função de fitness "f" na iteração atual e armazena seu índice.
Para cada cristal da população, percorrendo os índices de 0 até "popSize" menos 1:
- a posição atual do cristal é copiada para um armazenamento temporário, que será usado como "posição anterior" (Cr_old) nos cálculos;
- uma das estratégias disponíveis para atualização da posição é selecionada aleatoriamente. Ao todo, são quatro estratégias, numeradas de 0 a 3;
- em duas das quatro estratégias, as estratégias 2 e 3, é calculada a "média dos cristais selecionados aleatoriamente" (Fc), que também será usada na atualização;
- de acordo com a estratégia selecionada, a nova posição do cristal "Cr_new" é calculada com base em sua posição anterior, na posição média da população, na posição do melhor cristal e em "Fc". Cada estratégia utiliza uma combinação própria desses componentes e de números aleatórios (r, r1, r2, r3) para atualizar a posição;
- depois que a nova posição é calculada, verifica-se se cada coordenada permanece dentro dos intervalos definidos por rangeMin e rangeMax. Se uma coordenada ultrapassar os limites permitidos, ela é substituída por um novo valor aleatório gerado dentro desses limites;
- por fim, a discretização é aplicada novamente a cada coordenada por meio da função u.SeInDiSp ().
O método "Moving" desloca iterativamente os "cristais" pelo espaço de busca, utilizando diferentes estratégias baseadas nas informações atuais da população, como a posição média e o melhor cristal, além de fatores aleatórios.
//———————————————————————————————————————————————————————————————————— //--- Main algorithm step void C_AO_CryStAl::Moving () { // Initial population setup (formula 3) if (!revision) { // Random initialization of the crystal population for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { double xi = u.RNDfromCI (0.0, 1.0); a [i].c [j] = rangeMin [j] + xi * (rangeMax [j] - rangeMin [j]); a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } revision = true; return; } // CRITICAL: Calculate the mean position and find the best crystal BEFORE updating CalculateMeanPosition (); // Find the best crystal for the current iteration bestCrystalIdx = 0; for (int i = 1; i < popSize; i++) { if (a [i].f > a [bestCrystalIdx].f) { bestCrystalIdx = i; } } // Main position update loop (formulas 4–7) for (int i = 0; i < popSize; i++) { // Save the current position as the old one (Cr_old) ArrayCopy (a [i].cP, a [i].c, 0, 0, coords); // Select a random strategy (0–3) int strategy = u.RNDminusOne (5); // Prepare the array for Fc (only for strategies 2 and 3) double fc []; ArrayResize (fc, coords); if (strategy == 2 || strategy == 3) { CalculateFc (i, fc); } // Apply the selected position update strategy switch (strategy) { case 0: // Strategy 1: Simple Cubic (formula 4) // Cr_new = Cr_old + r * Cr_main for (int c = 0; c < coords; c++) { double r = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].cP [c] + r * meanPosition [c]; } break; case 1: // Strategy 2: Cubic with the best crystals (formula 5) // Cr_new = Cr_old + r1 * Cr_main + r2 * Cr_b for (int c = 0; c < coords; c++) { double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].cP [c] + r1 * meanPosition [c] + r2 * a [bestCrystalIdx].c [c]; } break; case 2: // Strategy 3: Cubic update with the mean crystals (formula 6) // Cr_new = Cr_old + r1 * Cr_main + r2 * Fc for (int c = 0; c < coords; c++) { double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].cP [c] + r1 * meanPosition [c] + r2 * fc [c]; } break; case 3: // Strategy 4: Cubic update with the best and mean crystals (formula 7) // Cr_new = Cr_old + r1 * Cr_main + r2 * Cr_b + r3 * Fc for (int c = 0; c < coords; c++) { double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); double r3 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].cP [c] + r1 * meanPosition [c] + r2 * a [bestCrystalIdx].c [c] + r3 * fc [c]; } break; } // Checking and correcting bounds for a new position for (int c = 0; c < coords; c++) { // If the position went out of bounds, apply boundary handling if (a [i].c [c] < rangeMin [c] || a [i].c [c] > rangeMax [c]) { // Generate a new random position within the valid range double xi = u.RNDfromCI (0.0, 1.0); a [i].c [c] = rangeMin [c] + xi * (rangeMax [c] - rangeMin [c]); } // Apply discretization a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //————————————————————————————————————————————————————————————————————
O método "Revision" é responsável por atualizar e armazenar as melhores soluções encontradas tanto no nível de cada "cristal" individual, isto é, sua melhor solução pessoal, quanto no nível de toda a população, ou seja, a melhor solução global.
O método percorre cada "cristal" da população para avaliar seu estado atual. Para cada cristal, seu valor atual de fitness "f" é comparado ao melhor valor de fitness já obtido por esse cristal, "fB". Se o valor atual for melhor que o melhor anterior, o valor de fitness pessoal "fB" é atualizado com o valor atual, e a posição do cristal correspondente a esse novo melhor resultado é copiada para sua melhor solução pessoal "cB".
Paralelamente à atualização das melhores soluções pessoais, o algoritmo acompanha a melhor solução encontrada por toda a população até o momento. O valor atual de fitness "f" do cristal também é comparado ao melhor valor global da população "fB". Se o valor atual do cristal superar o melhor valor global existente, o valor global "fB" é atualizado com o valor atual, e a posição do cristal correspondente a esse novo melhor resultado é copiada para a melhor solução global "cB".
Ao final da execução do método "Revision", as variáveis "fB" e "cB" armazenam, respectivamente, o maior valor da função de fitness e as coordenadas correspondentes encontradas durante toda a execução do algoritmo. Cada cristal também mantém sua própria melhor solução encontrada.
//———————————————————————————————————————————————————————————————————— //--- Updating and checking results void C_AO_CryStAl::Revision () { // Updating the best and worst solutions for each crystal for (int i = 0; i < popSize; i++) { // Update the personal best solution if (a [i].f > a [i].fB) { a [i].fB = a [i].f; ArrayCopy (a [i].cB, a [i].c, 0, 0, coords); } // Update the global best solution if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, coords); } } } //————————————————————————————————————————————————————————————————————
Resultados dos testes
De acordo com os resultados dos testes, o algoritmo apresenta um desempenho bastante modesto. O próprio resultado, 26,33%, chama a atenção por se enquadrar no patamar do (random walk) em nossa tabela de classificação. Então, o que isso significa? Voltaremos a essa questão mais adiante.
CryStAl|Crystal Structure Algorithm|30.0|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.49130791883895686
25 Hilly's; Func runs: 10000; result: 0.3254668138312991
500 Hilly's; Func runs: 10000; result: 0.25762861219210875
=============================
5 Forest's; Func runs: 10000; result: 0.3770837459944563
25 Forest's; Func runs: 10000; result: 0.21650897859329796
500 Forest's; Func runs: 10000; result: 0.158890697466887
=============================
5 Megacity's; Func runs: 10000; result: 0.2938461538461538
25 Megacity's; Func runs: 10000; result: 0.1498461538461539
500 Megacity's; Func runs: 10000; result: 0.09889230769230854
=============================
All score: 2.36947 (26.33%)
Esses resultados me levaram a fazer algumas alterações para melhorar a convergência do algoritmo. Como se constatou, a lógica de interação entre seus componentes não é particularmente eficiente. Isso permitiu revisar algumas abordagens pouco coerentes sem abandonar a ideia geral. Vamos ver o resultado obtido na versão modificada.
Formulação da atualização das posições (Estratégias 0-3): a modificação utiliza uma abordagem diferente para atualizar as posições, baseada na adição de um deslocamento à posição atual a [i].c [c]. As fórmulas são reformuladas, embora preservem os mesmos conceitos de cada estratégia. A introdução de uma parcela da diferença entre a posição atual e a posição média representa uma alteração significativa na formulação matemática.
Perturbação aleatória adicional:é introduzida a condição adicional "if (u.RNDprobab () < 0.1)". Com probabilidade de 10%, essa condição é satisfeita e a coordenada do cristal é atualizada por meio de a[i].c[c] = u.PowerDistribution (cB[c], rangeMin[c], rangeMax[c], 20), reduzindo a probabilidade de o algoritmo ficar estagnado. As demais estratégias são aplicadas com probabilidade de 90%.
Em seguida, vem o armazenamento da posição anterior em "a[i].cP": a versão original salva a posição anterior em "a[i].cP" antes de calcular a nova posição. Na versão modificada, essa posição não é armazenada nem utilizada; a atualização é feita diretamente a partir da posição atual "a[i].c[c]".
Tratamento dos limites: na versão original, depois de aplicar a estratégia de atualização, o método percorre todas as coordenadas e, se a nova posição ultrapassar os limites, gera uma posição aleatória totalmente nova dentro do intervalo permitido. Em "C_AO_CryStAlm", primeiro é aplicada a estratégia de atualização e, em seguida, apenas a discretização por meio do método "u.SeInDiSp".
//———————————————————————————————————————————————————————————————————— //--- Main step of the algorithm void C_AO_CryStAlm::Moving () { // Initial population initialization (formula 3) if (!revision) { // Random initialization of the crystal population for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { double xi = u.RNDfromCI (0.0, 1.0); a [i].c [j] = rangeMin [j] + xi * (rangeMax [j] - rangeMin [j]); a [i].c [j] = u.SeInDiSp (a [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } revision = true; return; } // CRITICAL: Calculate the mean position and find the best crystal BEFORE updating CalculateMeanPosition (); // Main position update loop (formulas 4–7) for (int i = 0; i < popSize; i++) { // Select a random strategy (0–3) int strategy = u.RNDminusOne (5); // Prepare the array for Fc (only for strategies 2 and 3) double fc []; ArrayResize (fc, coords); if (strategy == 2 || strategy == 3) { CalculateFc (i, fc); } for (int c = 0; c < coords; c++) { if (u.RNDprobab () < 0.1) { a [i].c [c] = u.PowerDistribution (cB [c], rangeMin [c], rangeMax [c], 20); } else { // Apply the selected position update strategy switch (strategy) { case 0: // Strategy 1: Simple cubic (formula 4) { // Cr_new = Cr_old + r * Cr_main double r = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].c [c] + r * (meanPosition [c] - a [i].c [c]); } break; case 1: // Strategy 2: Cubic with the best crystals (formula 5) { // Cr_new = Cr_old + r1 * Cr_main + r2 * Cr_b double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].c [c] + r1 * (meanPosition [c] - a [i].c [c]) + r2 * (cB [c] - a [i].c [c]); } break; case 2: // Strategy 3: Cubic with the mean crystals (formula 6) { // Cr_new = Cr_old + r1 * Cr_main + r2 * Fc double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].c [c] - r1 * (meanPosition [c] - a [i].c [c]) + r2 * (fc [c] - a [i].c [c]); } break; case 3: // Strategy 4: Cubic with the best and mean crystals (formula 7) { // Cr_new = Cr_old + r1 * Cr_main + r2 * Cr_b + r3 * Fc double r1 = u.RNDfromCI (0.0, 1.0); double r2 = u.RNDfromCI (0.0, 1.0); double r3 = u.RNDfromCI (0.0, 1.0); a [i].c [c] = a [i].c [c] + r1 * (meanPosition [c] - a [i].c [c]) + r2 * (cB [c] - a [i].c [c]) + r3 * (fc [c] - a [i].c [c]); } break; } } // Apply discretization a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } //————————————————————————————————————————————————————————————————————
A inicialização não foi alterada. O método "CalculateMeanPosition" não apresenta nenhuma diferença entre as versões "C_AO_CryStAl" e "C_AO_CryStAlm"; o mesmo vale para os métodos "CalculateFc" e "SelectRandomCrystal". O método "Revision" também é implementado de forma absolutamente idêntica nas duas versões, C_AO_CryStAl e C_AO_CryStAlm.
Vamos analisar os novos resultados abaixo: eles confirmam a validade das minhas premissas teóricas. Agora veremos por que a versão original transforma uma busca direcionada em um random walk com deriva.
CryStAlm|Crystal Structure Algorithm M|30.0|3.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.8065665859751701
25 Hilly's; Func runs: 10000; result: 0.5614723387106613
500 Hilly's; Func runs: 10000; result: 0.2909726108642525
=============================
5 Forest's; Func runs: 10000; result: 0.7522883470073202
25 Forest's; Func runs: 10000; result: 0.48674341114821484
500 Forest's; Func runs: 10000; result: 0.2101468006131327
=============================
5 Megacity's; Func runs: 10000; result: 0.48461538461538467
25 Megacity's; Func runs: 10000; result: 0.2701538461538461
500 Megacity's; Func runs: 10000; result: 0.11110769230769342
=============================
All score: 3.97407 (44.16%)
Quando comparamos as duas versões do Crystal Structure Algorithm, à primeira vista pode parecer que as alterações são mínimas. Ambas as versões inicializam a população da mesma forma, ambas calculam a posição média e ambas utilizam quatro estratégias de atualização. No entanto, por trás dessa semelhança aparente existem diferenças fundamentais que resultam em uma diferença de desempenho próxima de duas vezes. Vamos analisar cada alteração para entender por que a versão modificada é tão mais eficiente.
Erro fundamental: soma de coordenadas absolutas em vez de movimento direcionado.Para compreender o principal problema do algoritmo original, considere uma otimização unidimensional em que buscamos o máximo de uma função no intervalo de 0 a 100. A posição média da população, isto é, o ponto para o qual os cristais são atraídos, está em 60. Temos três cristais em posições diferentes: o primeiro em 10, o segundo em 60 e o terceiro em 90. O coeficiente aleatório r é o mesmo para todos, 0,5.
Fórmula original: x_new = x_old + r × mean
- Cristal 1: 10 + 0,5 × 60 = 10 + 30 = 40 (deslocamento +30)
- Cristal 2: 60 + 0,5 × 60 = 60 + 30 = 90 (deslocamento +30)
- Cristal 3: 90 + 0,5 × 60 = 90 + 30 = 120 (deslocamento +30, FORA DOS LIMITES!)
Percebeu o problema? TODOS OS TRÊS CRISTAIS SE DESLOCARAM +30, independentemente da posição em que estavam! O primeiro cristal estava muito à esquerda do alvo e se moveu para a direita, o que faz sentido. O segundo JÁ ESTAVA no alvo e foi empurrado para a direita, o que é absurdo. O terceiro estava à direita do alvo, foi empurrado ainda mais para a direita e ultrapassou os limites, o que é um desastre.
Isso não é "movimento em direção ao alvo". É o mesmo empurrão para todos na mesma direção, como se um vento forte soprasse e deslocasse todos pela mesma distância. Além disso, a direção e a intensidade desse "vento" são determinadas pelos valores absolutos das coordenadas do alvo, e não pela posição relativa dos cristais.
Fórmula modificada: x_new = x_old + r × (mean - x_old)
- Cristal 1: 10 + 0,5 × (60 - 10) = 10 + 25 = 35 (percorreu 50% do caminho até o alvo)
- Cristal 2: 60 + 0,5 × (60 - 60) = 60 + 0 = 60 (já estava no alvo e permaneceu no lugar)
- Cristal 3: 90 + 0,5 × (60 - 90) = 90 - 15 = 75 (percorreu 50% do caminho DE VOLTA ao alvo)
Percebe a diferença? Cada cristal se desloca EM DIREÇÃO ao seu alvo, proporcionalmente à distância até ele. Quem está longe dá um passo maior. Quem está perto dá um passo menor. Quem já chegou permanece no lugar. Quem ultrapassou o alvo volta. É exatamente esse o comportamento desejável em um algoritmo de otimização.
Problema 1: explosão com coordenadas de grande magnitude. Se as variáveis otimizadas tiverem, por exemplo, um intervalo de 0 a 1000 e a posição média da população estiver em torno de 600-700, então será acrescentado a CADA cristal um valor da ordem de 600-700, multiplicado por um coeficiente aleatório entre 0 e 1. Até mesmo um cristal situado na posição 650, praticamente no alvo, receberá um deslocamento de +300...+600 e será lançado para o limite 1000 ou além dele. O algoritmo acaba se transformando em um gerador de valores aleatórios nas bordas do espaço de busca.
Problema 2: dependência da escala das coordenadas. Se o problema tiver variáveis em escalas diferentes, por exemplo, x de 0 a 10 e y de 0 a 1000, os deslocamentos em y serão 100 vezes maiores que os deslocamentos em x simplesmente por causa da diferença de escala! Isso não tem qualquer relação com a distância do cristal até o ótimo em cada coordenada.
Problema 3: todos os cristais se deslocam na mesma direção. Quando o mesmo vetor é adicionado a todos os cristais, ainda que com coeficientes aleatórios diferentes, toda a população se desloca como um todo na mesma direção. Isso não é uma "busca pelo ótimo", mas uma "deriva da população". Imagine um bando de aves que deveria procurar alimento, mas, em vez disso, todas voam sincronizadamente para nordeste, com apenas pequenos desvios aleatórios. Isso não é busca, é migração.
Problema 4: reinicializações constantes. Devido aos enormes deslocamentos, os cristais ultrapassam os limites com frequência. O algoritmo precisa então reinicializá-los em posições aleatórias. Isso significa que toda a informação acumulada sobre a direção do movimento é perdida. O cristal estava se deslocando em direção a uma região promissora, ultrapassou os limites e foi "teletransportado" para um ponto aleatório, apagando todo o histórico de seu movimento. Na prática, a cada poucas iterações o algoritmo volta a se comportar como uma busca aleatória.
Memória da melhor solução: local versus global.A segunda alteração importante está relacionada a qual "melhor solução" é usada nas fórmulas. A versão modificada mantém um registro global dos melhores resultados. Quando alguém encontra uma altitude de 3000 metros, essa informação é registrada e nunca mais esquecida. Mesmo que depois todos os pesquisadores desçam, o algoritmo continua se lembrando: "O melhor lugar que já encontramos foi ali, a 3000 metros de altitude". É justamente para esse ponto que os demais exploradores são atraídos. Isso é especialmente importante em problemas de otimização, nos quais a população pode sofrer uma piora temporária. Por exemplo, após aplicar uma mutação, todas as soluções podem ficar piores. Na versão original, o algoritmo passará a seguir essas soluções inferiores. Na versão modificada, ele continuará orientado para a melhor solução efetivamente encontrada durante toda a execução.
Adição de intensificação local. A terceira alteração fundamental diz respeito a um novo mecanismo que não existe na versão original. Na versão modificada, com probabilidade de 10%, cada coordenada do cristal é gerada de maneira especial nas proximidades da melhor solução global por meio da função "PowerDistribution", com o parâmetro 20. O algoritmo original funciona como uma meta-heurística pura: os cristais se deslocam por todo o espaço de busca de acordo com suas estratégias. Já a versão modificada acrescenta um elemento de busca local: cada coordenada tem 10% de probabilidade de ser gerada nas proximidades da melhor solução encontrada. O parâmetro 20 em PowerDistribution produz uma concentração muito forte, algo semelhante a procurar as chaves em um raio de meio metro do local onde você se lembra de tê-las visto pela última vez. Não se trata de escolher um ponto aleatório qualquer nessa região, mas de gerar um ponto com probabilidade muito alta de ficar bem próximo do centro.
Simplificação do tratamento dos limites. A quarta alteração diz respeito ao que acontece quando um cristal tenta ultrapassar os limites permitidos do espaço de busca. Na versão modificada, a coordenada é simplesmente passada para a função "u.SeInDiSp", que limita o valor ao intervalo permitido e aplica a discretização. Por que essa mudança se tornou possível? Porque, graças às fórmulas corretas de movimentação, os cristais da versão modificada raramente ultrapassam os limites.
Na versão original, devido à soma direta de vetores de coordenadas absolutas, os cristais ultrapassam os limites constantemente, tornando a reinicialização necessária. Mas essa reinicialização tem um custo elevado: primeiro, exige a geração de números aleatórios e cálculos adicionais; segundo, transforma um movimento direcionado em um deslocamento aleatório. O cristal podia estar se movendo em uma direção promissora, ultrapassar o limite e acabar em uma posição completamente aleatória, perdendo toda a trajetória acumulada.
Otimização do uso da memória. A quinta alteração pode parecer tecnicamente pequena, mas mostra uma compreensão mais precisa do que o algoritmo realmente precisa para funcionar. Na versão original, antes de atualizar a posição do cristal, sua posição atual é copiada para um array especial cP, que armazena a posição anterior, e essa cópia passa a ser usada nas fórmulas. Por exemplo, a nova coordenada é calculada como a coordenada anterior armazenada em cP mais algum termo adicional. Na versão modificada, essa cópia deixa de existir. A fórmula simplesmente utiliza o valor atual da coordenada, calcula a alteração e grava o resultado de volta na mesma variável.
Por que a versão original precisava dessa cópia? Porque a fórmula tinha a forma "x_new = x_old + algo". Para calcular o lado direito, era necessário preservar x_old antes de iniciar as alterações. Na versão modificada, a fórmula foi reorganizada de modo que seja possível trabalhar diretamente com o valor atual: "x = x + alteração". Para uma população de 30 cristais em um espaço de 10 dimensões, isso elimina 300 operações de cópia de dados a cada iteração. Pode parecer pouco, mas, quando o algoritmo executa milhares de iterações, esses pequenos custos se acumulam.
Na visualização, podemos acompanhar como a versão modificada forma "formas cristalinas" durante a execução. Também é possível observar a dispersão dos valores nas funções de baixa e média dimensionalidade.
CryStAlm na função de teste Hilly
CryStAlm na função de teste Forest
CryStAlm na função de teste Forest
CryStAlm na função de teste padrão Ackley
Na tabela de classificação, o algoritmo CryStAlm é apresentado apenas para referência, pois faltou muito pouco para que obtivesse uma posição no ranking.
| № | AO | Description | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of MAX | ||||||
| 10 p (5 F) | 50 p (25 F) | 1.000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1.000 p (500 F) | 10 p (5 F) | 50 p (25 F) | 1.000 p (500 F) | ||||||||
| 1 | DOAdingom | dingo_optimization_algorithm_M | 0,47968 | 0,45367 | 0,46369 | 1,39704 | 0,94145 | 0,87909 | 0,91454 | 2,73508 | 0,78615 | 0,86061 | 0,84805 | 2,49481 | 6,627 | 73,63 |
| 2 | ANS | across neighbourhood search | 0,94948 | 0,84776 | 0,43857 | 2,23581 | 1,00000 | 0,92334 | 0,39988 | 2,32323 | 0,70923 | 0,63477 | 0,23091 | 1,57491 | 6,134 | 68,15 |
| 3 | CLA | code lock algorithm (joo) | 0,95345 | 0,87107 | 0,37590 | 2,20042 | 0,98942 | 0,91709 | 0,31642 | 2,22294 | 0,79692 | 0,69385 | 0,19303 | 1,68380 | 6,107 | 67,86 |
| 4 | AMOm | animal migration ptimization M | 0,90358 | 0,84317 | 0,46284 | 2,20959 | 0,99001 | 0,92436 | 0,46598 | 2,38034 | 0,56769 | 0,59132 | 0,23773 | 1,39675 | 5,987 | 66,52 |
| 5 | (P+O)ES | (P+O) evolution strategies | 0,92256 | 0,88101 | 0,40021 | 2,20379 | 0,97750 | 0,87490 | 0,31945 | 2,17185 | 0,67385 | 0,62985 | 0,18634 | 1,49003 | 5,866 | 65,17 |
| 6 | CTA | comet tail algorithm (joo) | 0,95346 | 0,86319 | 0,27770 | 2,09435 | 0,99794 | 0,85740 | 0,33949 | 2,19484 | 0,88769 | 0,56431 | 0,10512 | 1,55712 | 5,846 | 64,96 |
| 7 | TETA | time evolution travel algorithm (joo) | 0,91362 | 0,82349 | 0,31990 | 2,05701 | 0,97096 | 0,89532 | 0,29324 | 2,15952 | 0,73462 | 0,68569 | 0,16021 | 1,58052 | 5,797 | 64,41 |
| 8 | SDSm | stochastic diffusion search M | 0,93066 | 0,85445 | 0,39476 | 2,17988 | 0,99983 | 0,89244 | 0,19619 | 2,08846 | 0,72333 | 0,61100 | 0,10670 | 1,44103 | 5,709 | 63,44 |
| 9 | BOAm | billiards optimization algorithm M | 0,95757 | 0,82599 | 0,25235 | 2,03590 | 1,00000 | 0,90036 | 0,30502 | 2,20538 | 0,73538 | 0,52523 | 0,09563 | 1,35625 | 5,598 | 62,19 |
| 10 | AAm | archery algorithm M | 0,91744 | 0,70876 | 0,42160 | 2,04780 | 0,92527 | 0,75802 | 0,35328 | 2,03657 | 0,67385 | 0,55200 | 0,23738 | 1,46323 | 5,598 | 61,64 |
| 11 | ESG | evolution of social groups (joo) | 0,99906 | 0,79654 | 0,35056 | 2,14616 | 1,00000 | 0,82863 | 0,13102 | 1,95965 | 0,82333 | 0,55300 | 0,04725 | 1,42358 | 5,529 | 61,44 |
| 12 | SIA | simulated isotropic annealing (joo) | 0,95784 | 0,84264 | 0,41465 | 2,21513 | 0,98239 | 0,79586 | 0,20507 | 1,98332 | 0,68667 | 0,49300 | 0,09053 | 1,27020 | 5,469 | 60,76 |
| 13 | EOm | extremal_optimization_M | 0,76166 | 0,77242 | 0,31747 | 1,85155 | 0,99999 | 0,76751 | 0,23527 | 2,00277 | 0,74769 | 0,53969 | 0,14249 | 1,42987 | 5,284 | 58,71 |
| 14 | BBO | biogeography based optimization | 0,94912 | 0,69456 | 0,35031 | 1,99399 | 0,93820 | 0,67365 | 0,25682 | 1,86867 | 0,74615 | 0,48277 | 0,17369 | 1,40261 | 5,265 | 58,50 |
| 15 | ACS | artificial cooperative search | 0,75547 | 0,74744 | 0,30407 | 1,80698 | 1,00000 | 0,88861 | 0,22413 | 2,11274 | 0,69077 | 0,48185 | 0,13322 | 1,30583 | 5,226 | 58,06 |
| 16 | DA | dialectical algorithm | 0,86183 | 0,70033 | 0,33724 | 1,89940 | 0,98163 | 0,72772 | 0,28718 | 1,99653 | 0,70308 | 0,45292 | 0,16367 | 1,31967 | 5,216 | 57,95 |
| 17 | BHAm | black hole algorithm M | 0,75236 | 0,76675 | 0,34583 | 1,86493 | 0,93593 | 0,80152 | 0,27177 | 2,00923 | 0,65077 | 0,51646 | 0,15472 | 1,32195 | 5,196 | 57,73 |
| 18 | ASO | anarchy society optimization | 0,84872 | 0,74646 | 0,31465 | 1,90983 | 0,96148 | 0,79150 | 0,23803 | 1,99101 | 0,57077 | 0,54062 | 0,16614 | 1,27752 | 5,178 | 57,54 |
| 19 | RFO | royal flush optimization (joo) | 0,83361 | 0,73742 | 0,34629 | 1,91733 | 0,89424 | 0,73824 | 0,24098 | 1,87346 | 0,63154 | 0,50292 | 0,16421 | 1,29867 | 5,089 | 56,55 |
| 20 | AOSm | atomic orbital search M | 0,80232 | 0,70449 | 0,31021 | 1,81702 | 0,85660 | 0,69451 | 0,21996 | 1,77107 | 0,74615 | 0,52862 | 0,14358 | 1,41835 | 5,006 | 55,63 |
| 21 | TSEA | algoritmo de evolução do casco de tartaruga (joo) | 0,96798 | 0,64480 | 0,29672 | 1,90949 | 0,99449 | 0,61981 | 0,22708 | 1,84139 | 0,69077 | 0,42646 | 0,13598 | 1,25322 | 5,004 | 55,60 |
| 22 | BSA | backtracking_search_algorithm | 0,97309 | 0,54534 | 0,29098 | 1,80941 | 0,99999 | 0,58543 | 0,21747 | 1,80289 | 0,84769 | 0,36953 | 0,12978 | 1,34700 | 4,959 | 55,10 |
| 23 | DE | differential evolution | 0,95044 | 0,61674 | 0,30308 | 1,87026 | 0,95317 | 0,78896 | 0,16652 | 1,90865 | 0,78667 | 0,36033 | 0,02953 | 1,17653 | 4,955 | 55,06 |
| 24 | SRA | successful restaurateur algorithm (joo) | 0,96883 | 0,63455 | 0,29217 | 1,89555 | 0,94637 | 0,55506 | 0,19124 | 1,69267 | 0,74923 | 0,44031 | 0,12526 | 1,31480 | 4,903 | 54,48 |
| 25 | CRO | chemical reaction optimisation | 0,94629 | 0,66112 | 0,29853 | 1,90593 | 0,87906 | 0,58422 | 0,21146 | 1,67473 | 0,75846 | 0,42646 | 0,12686 | 1,31178 | 4,892 | 54,36 |
| 26 | BIO | blood inheritance optimization (joo) | 0,81568 | 0,65336 | 0,30877 | 1,77781 | 0,89937 | 0,65319 | 0,21760 | 1,77016 | 0,67846 | 0,47631 | 0,13902 | 1,29378 | 4,842 | 53,80 |
| 27 | DOA | dream_optimization_algorithm | 0,85556 | 0,70085 | 0,37280 | 1,92921 | 0,73421 | 0,48905 | 0,24147 | 1,46473 | 0,77231 | 0,47354 | 0,18561 | 1,43146 | 4,825 | 53,62 |
| 28 | BSA | bird swarm algorithm | 0,89306 | 0,64900 | 0,26250 | 1,80455 | 0,92420 | 0,71121 | 0,24939 | 1,88479 | 0,69385 | 0,32615 | 0,10012 | 1,12012 | 4,809 | 53,44 |
| 29 | DEA | dolphin_echolocation_algorithm | 0,75995 | 0,67572 | 0,34171 | 1,77738 | 0,89582 | 0,64223 | 0,23941 | 1,77746 | 0,61538 | 0,44031 | 0,15115 | 1,20684 | 4,762 | 52,91 |
| 30 | HS | harmony search | 0,86509 | 0,68782 | 0,32527 | 1,87818 | 0,99999 | 0,68002 | 0,09590 | 1,77592 | 0,62000 | 0,42267 | 0,05458 | 1,09725 | 4,751 | 52,79 |
| 31 | SSG | semeadura e crescimento de mudas | 0,77839 | 0,64925 | 0,39543 | 1,82308 | 0,85973 | 0,62467 | 0,17429 | 1,65869 | 0,64667 | 0,44133 | 0,10598 | 1,19398 | 4,676 | 51,95 |
| 32 | BCOm | bacterial chemotaxis optimization M | 0,75953 | 0,62268 | 0,31483 | 1,69704 | 0,89378 | 0,61339 | 0,22542 | 1,73259 | 0,65385 | 0,42092 | 0,14435 | 1,21912 | 4,649 | 51,65 |
| 33 | ABO | african buffalo optimization | 0,83337 | 0,62247 | 0,29964 | 1,75548 | 0,92170 | 0,58618 | 0,19723 | 1,70511 | 0,61000 | 0,43154 | 0,13225 | 1,17378 | 4,634 | 51,49 |
| 34 | (PO)ES | (PO) evolution strategies | 0,79025 | 0,62647 | 0,42935 | 1,84606 | 0,87616 | 0,60943 | 0,19591 | 1,68151 | 0,59000 | 0,37933 | 0,11322 | 1,08255 | 4,610 | 51,22 |
| 35 | FBA | fractal-based Algorithm | 0,79000 | 0,65134 | 0,28965 | 1,73099 | 0,87158 | 0,56823 | 0,18877 | 1,62858 | 0,61077 | 0,46062 | 0,12398 | 1,19537 | 4,555 | 50,61 |
| 36 | TSm | tabu search M | 0,87795 | 0,61431 | 0,29104 | 1,78330 | 0,92885 | 0,51844 | 0,19054 | 1,63783 | 0,61077 | 0,38215 | 0,12157 | 1,11449 | 4,536 | 50,40 |
| 37 | BSO | brain storm optimization | 0,93736 | 0,57616 | 0,29688 | 1,81041 | 0,93131 | 0,55866 | 0,23537 | 1,72534 | 0,55231 | 0,29077 | 0,11914 | 0,96222 | 4,498 | 49,98 |
| 38 | WOAm | wale optimization algorithm M | 0,84521 | 0,56298 | 0,26263 | 1,67081 | 0,93100 | 0,52278 | 0,16365 | 1,61743 | 0,66308 | 0,41138 | 0,11357 | 1,18803 | 4,476 | 49,74 |
| 39 | AEFA | artificial electric field algorithm | 0,87700 | 0,61753 | 0,25235 | 1,74688 | 0,92729 | 0,72698 | 0,18064 | 1,83490 | 0,66615 | 0,11631 | 0,09508 | 0,87754 | 4,459 | 49,55 |
| 40 | AEO | artificial ecosystem-based optimization algorithm | 0,91380 | 0,46713 | 0,26470 | 1,64563 | 0,90223 | 0,43705 | 0,21400 | 1,55327 | 0,66154 | 0,30800 | 0,28563 | 1,25517 | 4,454 | 49,49 |
| 41 | CAm | camel algorithm M | 0,78684 | 0,56042 | 0,35133 | 1,69859 | 0,82772 | 0,56041 | 0,24336 | 1,63149 | 0,64846 | 0,33092 | 0,13418 | 1,11356 | 4,444 | 49,37 |
| 42 | ACOm | ant colony optimization M | 0,88190 | 0,66127 | 0,30377 | 1,84693 | 0,85873 | 0,58680 | 0,15051 | 1,59604 | 0,59667 | 0,37333 | 0,02472 | 0,99472 | 4,438 | 49,31 |
| 43 | CMAES | covariance_matrix_adaptation_evolution_strategy | 0,76258 | 0,72089 | 0,00000 | 1,48347 | 0,82056 | 0,79616 | 0,00000 | 1,61672 | 0,75846 | 0,49077 | 0,00000 | 1,24923 | 4,349 | 48,33 |
| 44 | DA_duelist | duelist_algorithm | 0,92782 | 0,53778 | 0,27792 | 1,74352 | 0,86957 | 0,47536 | 0,18193 | 1,52686 | 0,62153 | 0,33569 | 0,11715 | 1,07437 | 4,345 | 48,28 |
| 45 | BFO-GA | bacterial foraging optimization - ga | 0,89150 | 0,55111 | 0,31529 | 1,75790 | 0,96982 | 0,39612 | 0,06305 | 1,42899 | 0,72667 | 0,27500 | 0,03525 | 1,03692 | 4,224 | 46,93 |
| CryStAlm | crystal_structure_algorithm_M | 0,80656 | 0,56147 | 0,29097 | 1,65900 | 0,75228 | 0,48674 | 0,21014 | 1,44916 | 0,48461 | 0,27015 | 0,11111 | 0,86587 | 3,974 | 44,16 | |
| RW | random walk | 0,48754 | 0,32159 | 0,25781 | 1,06694 | 0,37554 | 0,21944 | 0,15877 | 0,75375 | 0,27969 | 0,14917 | 0,09847 | 0,52734 | 2,348 | 26,09 | |
Conclusões
Uma ideia elegante arruinada pela implementação. O Crystal Structure Algorithm surgiu em 2021 com uma proposta atraente: aplicar os princípios de formação das estruturas cristalinas à otimização global. Os autores propuseram um algoritmo populacional em que os "cristais" se deslocam sob a influência da posição média da população, da melhor solução encontrada e de vizinhos selecionados aleatoriamente. Quatro estratégias de movimentação e um modelo matemático elegante. No papel, tudo parecia convincente.
O problema é que entre a ideia conceitual e uma implementação funcional existe uma etapa crítica: traduzir a metáfora física em operações matemáticas concretas. E é justamente nesse ponto que o CryStAl original falha. Fórmulas que parecem razoáveis no artigo acabam, na prática, transformando uma busca direcionada em um movimento errático. Não se trata apenas de uma história de "encontramos um bug e o corrigimos", mas de uma lição fundamental: no desenvolvimento de meta-heurísticas, o conceito e sua formulação matemática precisam estar em sintonia. Caso contrário, o algoritmo se comportará de maneira diferente da pretendida ou simplesmente não funcionará.
O descompasso entre a ideia e a execução. Vamos analisar o que os autores QUERIAM implementar no CryStAl original. A ideia é clara: os cristais deveriam ser atraídos por três pontos principais: a posição média de toda a população (centro de massa, informação global), o melhor cristal encontrado (intensificação) e a média dos vizinhos selecionados aleatoriamente (informação local, diversidade). As quatro estratégias combinam essas atrações de maneiras diferentes. Em teoria, isso cria um equilíbrio entre a diversificação para novas regiões do espaço de busca e a intensificação da busca em regiões promissoras. A analogia física é elegante: os átomos interagem com seus vizinhos e tendem a uma configuração de equilíbrio. Os autores QUERIAM implementar uma "atração em direção ao alvo", mas ESCREVERAM uma "adição de um vetor". São operações diferentes!
Erro sistêmico de raciocínio: fórmulas em vez de geometria. A raiz do problema é mais profunda do que uma única fórmula incorreta. Trata-se de um erro conceitual no projeto do algoritmo: concentrar-se nas fórmulas sem compreender o que elas realmente fazem na geometria do espaço de busca. Os autores do CryStAl original escreveram: "o cristal se desloca em direção à posição média, fórmula: x + r × mean". Eles se concentraram na expressão algébrica sem visualizar o que aconteceria com os cristais situados em diferentes regiões do espaço. A abordagem correta exige fazer algumas perguntas:
- O que deve acontecer com um cristal que já se encontra no ponto-alvo? Resposta: ele deve permanecer ali ou dar um passo muito pequeno. A fórmula original o afasta desse ponto. A fórmula modificada o mantém no lugar (quando x_old = mean, temos x + 0 × (mean - x) = x).
- O que deve acontecer com um cristal que está além do alvo? Resposta: ele deve retornar em direção ao alvo. A fórmula original o empurra ainda mais na mesma direção. A fórmula modificada inverte o movimento (uma diferença negativa produz um deslocamento de volta).
- A magnitude do passo deve depender dos valores absolutos das coordenadas? Resposta: não, ela deve depender da distância até o alvo. A fórmula original depende dos valores absolutos. A modificada depende das distâncias.
- O que acontece quando as variáveis têm escalas diferentes? Na versão original, os deslocamentos nas diferentes coordenadas não são proporcionais às respectivas distâncias relativas até o alvo. Na versão modificada, os deslocamentos são automaticamente escalonados de acordo com essas distâncias relativas.
As respostas a essas perguntas mostram imediatamente que a fórmula x + r × target é geometricamente inadequada para modelar uma atração. Já a fórmula x + r × (target - x) está geometricamente correta: trata-se de uma interpolação, um deslocamento correspondente à fração r do caminho até o alvo, com a propriedade natural de reduzir o passo à medida que o cristal se aproxima.
Muitas fórmulas não corrigem uma base incorreta. Pode parecer que as quatro estratégias do CryStAl compensariam as deficiências umas das outras. A estratégia 0, com um único ponto-alvo, funciona mal, mas a estratégia 3, com três pontos-alvo, não deveria funcionar melhor? Na prática, ocorre o contrário: combinar operações incorretas apenas agrava o problema.
Fórmula da estratégia 3: x_new = x_old + r1 × mean + r2 × best + r3 × fc, em que fc é a média dos cristais selecionados aleatoriamente. Agora estamos somando TRÊS valores elevados, isto é, as coordenadas absolutas de três pontos-alvo. Considere o seguinte exemplo: variáveis de 0 a 1000, cristal em [640, 430, 770], mean = [650, 420, 780], best = [645, 425, 775], fc = [655, 415, 785], com coeficientes r1 = r2 = r3 = 0,4.
Primeira coordenada: 640 + 0,4 × 650 + 0,4 × 645 + 0,4 × 655 = 640 + 260 + 258 + 262 = 1420, ainda mais além do limite permitido!
A estratégia 3 deveria ser a mais sofisticada e eficiente, pois combina informação global, informação local e intensificação. Na prática, porém, ela gera os maiores valores anômalos justamente por somar ainda mais grandezas absolutas. O problema não está na quantidade de componentes, mas no fato de que a operação básica, a soma direta de coordenadas absolutas, é fundamentalmente incorreta.
Da busca aleatória à otimização direcionada. O que o CryStAl original realmente faz na prática? Após algumas iterações, estabelece-se o seguinte padrão de funcionamento: a cada passo, a população recebe deslocamentos enormes, a maioria dos cristais ultrapassa os limites e suas coordenadas são reinicializadas aleatoriamente. Na prática, a cada 2 ou 3 iterações o algoritmo gera uma nova população quase aleatória, preservando apenas uma pequena parcela das coordenadas da geração anterior.
O CryStAlm modificado funciona de maneira fundamentalmente diferente. Os cristais realmente se deslocam em direção aos pontos-alvo, em vez de se moverem de forma caótica. As trajetórias são suaves e controladas. Os cristais raramente ultrapassam os limites. A população converge gradualmente e de forma ordenada para regiões promissoras, preservando ao mesmo tempo a diversidade graças às estratégias aleatórias e ao mecanismo de repulsão. Cada iteração acumula informações sobre a paisagem da função e as utiliza nos passos seguintes, sem apagar o estado anterior por meio de regenerações aleatórias.
Lição metodológica para pesquisadores. A história do CryStAl não é apenas um exemplo de implementação malsucedida. Trata-se de um problema sistêmico no desenvolvimento de algoritmos meta-heurísticos.
Contexto mais amplo: a epidemia de algoritmos fracos. O CryStAl não é um caso isolado. Na literatura sobre meta-heurísticas dos últimos 15 anos, existem centenas de "novos" algoritmos inspirados em diferentes metáforas, e muitos deles sofrem do mesmo problema: uma ideia atraente, uma implementação pouco rigorosa, testes em um conjunto limitado de problemas e uma publicação que reivindica competitividade. Depois, outros pesquisadores adotam esses algoritmos como baseline e fazem comparações com eles, criando uma cadeia de comparações apoiada em bases fundamentalmente frágeis.
A modificação do CryStAl para CryStAlm permite uma análise mais profunda do comportamento do algoritmo. As alterações no código são mínimas: reescrever as fórmulas de movimentação, adicionar PowerDistribution e usar cB em vez de bestCrystalIdx. No entanto, as mudanças no comportamento são fundamentais.
A comparação entre CryStAl e CryStAlm oferece várias lições importantes para a comunidade de pesquisa em otimização meta-heurística:
Lição 1: conceito não é implementação.. Uma boa ideia de algoritmo é apenas o começo. Traduzir essa ideia em operações matemáticas exige uma compreensão profunda da geometria do espaço de busca. As fórmulas precisam fazer aquilo que se espera delas, e não apenas parecer plausíveis no papel. Verifique não só "o que a fórmula calcula", mas também "o que ela faz com os agentes em diferentes situações".
Lição 2: a abstração esconde erros. Quando se escreve que "o cristal é atraído para a posição média", é fácil deixar passar o fato de que a fórmula implementa não uma atração, mas um deslocamento paralelo. O raciocínio abstrato, como "movimento em direção ao alvo", precisa ser acompanhado por uma verificação concreta, como "de que maneira exatamente as coordenadas serão alteradas". Sempre teste as fórmulas com exemplos numéricos específicos.
Lição 3: testes padronizados não são suficientes.. Testes em benchmarks CEC com variáveis normalizadas podem esconder problemas críticos que só aparecem em escalas realistas ou com intervalos distintos entre as variáveis. Inclua testes em condições "desfavoráveis": intervalos muito amplos, escalas distintas entre as variáveis e ótimos estreitos. Visualize o comportamento do algoritmo, e não apenas os resultados finais.
Lição 4: vários mecanismos não compensam uma base incorreta.. Se a operação fundamental, como a fórmula de movimentação, estiver errada, adicionar camadas mais sofisticadas não resolverá o problema. Primeiro, certifique-se de que a base funciona corretamente; depois, acrescente melhorias. Um mecanismo correto vale mais do que dez mecanismos incorretos.
Lição 5: comparações exigem validação do baseline. Se o seu novo algoritmo supera um método existente, faça uma pergunta simples: esse baseline realmente funciona? Uma verificação rápida consiste em compará-lo com uma busca aleatória. Se a diferença for pequena, você está se comparando com uma referência sem capacidade real, e o seu resultado, por si só, não significa muita coisa.
Lição 6: os detalhes da implementação são fundamentais. A diferença entre uma fórmula "quase correta" e uma fórmula "correta" pode ter um impacto enorme no desempenho. x + r × mean e x + r × (mean - x) diferem por apenas alguns caracteres no código, mas podem resultar em uma diferença de aproximadamente duas vezes na qualidade dos resultados. Os detalhes importam. Não os trate como "minúcias técnicas".
O CryStAl demonstra que uma meta-heurística não é apenas uma coleção de metáforas e fórmulas. Trata-se de uma disciplina de engenharia, na qual compreender como as operações afetam a dinâmica da busca no espaço de soluções é tão importante quanto a ideia original. Uma boa ideia implementada sem o devido rigor resulta em um algoritmo que se comporta como uma busca aleatória. A mesma ideia, implementada com compreensão da geometria e da dinâmica da busca, resulta em uma ferramenta que realmente funciona.
Para que essa área avance, não basta criar novas metáforas. É preciso desenvolver algoritmos que realmente façam aquilo que se afirma que fazem: percorrer o espaço de busca de forma direcionada, acumular informações e convergir para soluções ótimas. E isso exige mais do que simplesmente escrever fórmulas; é necessário analisar profundamente se essas fórmulas realmente implementam a ideia pretendida.
Figura 2. Gradação de cores dos algoritmos nos testes correspondentes
Figura 3. Histograma dos resultados dos testes dos algoritmos (em uma escala de 0 a 100, quanto maior, melhor, sendo 100 o resultado teórico máximo possível; o arquivo contém um script para calcular a tabela de classificação)
Vantagens e desvantagens do algoritmo CryStAlm:
Vantagens:
- Implementação relativamente simples.
- Rápido.
- Resultados médios consistentes (cor amarela, sem resultados muito fracos em testes individuais).
Desvantagens:
- Dispersão dos valores em funções de baixa e média dimensionalidade.
O artigo inclui um arquivo compactado com as versões atuais dos códigos dos algoritmos. O autor do artigo não se responsabiliza pela exatidão absoluta da descrição dos algoritmos canônicos, pois muitos deles foram modificados para melhorar sua capacidade de busca. As conclusões e avaliações apresentadas nos artigos baseiam-se nos resultados dos experimentos realizados.
Programas utilizados neste artigo
| # | Nome | Tipo | Descrição |
|---|---|---|---|
| 1 | #C_AO.mqh | Arquivo de inclusão | Classe base dos algoritmos de otimização populacional |
| 2 | #C_AO_enum.mqh | Arquivo de inclusão | Enumeração dos algoritmos de otimização populacional |
| 3 | TestFunctions.mqh | Arquivo de inclusão | Biblioteca de funções de teste |
| 4 | TestStandFunctions.mqh | Arquivo de inclusão | Biblioteca de funções do ambiente de testes |
| 5 | Utilities.mqh | Arquivo de inclusão | Biblioteca de funções auxiliares |
| 6 | CalculationTestResults.mqh | Arquivo de inclusão | Script para calcular os resultados da tabela comparativa |
| 7 | Testing AOs.mq5 | Script | Ambiente de testes unificado para todos os algoritmos de otimização populacional |
| 8 | Simple use of population optimization algorithms.mq5 | Script | Exemplo simples de uso de algoritmos de otimização populacional sem visualização |
| 9 | Test_AO_CryStAlm.mq5 | Script | Ambiente de testes do CryStAlm |
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/19899
Aviso: Todos os direitos sobre esses materiais pertencem à MetaQuotes Ltd. É proibida a reimpressão total ou parcial.
Esse artigo foi escrito por um usuário do site e reflete seu ponto de vista pessoal. A MetaQuotes Ltd. não se responsabiliza pela precisão das informações apresentadas nem pelas possíveis consequências decorrentes do uso das soluções, estratégias ou recomendações descritas.
Redes neurais no trading: abordagem semântica baseada em spikes para identificação espaçotemporal (Conclusão)
Análise da influência dos ciclos solares e lunares sobre os preços das moedas
Métodos de amostragem MCMC - Algoritmo de Metropolis-Hastings
Redes neurais em trading: abordagem semântica baseada em spikes para identificação espaço-temporal (Componentes principais)
- 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