Algoritmo baseado em fractais - Fractal-Based Algorithm (FBA)
508
0
Introdução
Os algoritmos metaheurísticos se consolidaram como uma ferramenta poderosa para resolver tarefas complexas de otimização, graças à sua capacidade de encontrar soluções aceitáveis em um tempo razoável. Nas últimas décadas, foram desenvolvidos inúmeros métodos metaheurísticos, inspirados em diferentes processos naturais e sociais, como algoritmos genéticos, otimização por enxame de partículas, evolução diferencial, otimização por colônia de formigas e muitos outros, que já analisamos em artigos anteriores.
Neste artigo, vamos analisar um novo algoritmo metaheurístico para resolver tarefas de otimização contínua, o Fractal-Based Algorithm (FBA), de Marjan Kaedi, de 2017. Essa abordagem é baseada nas propriedades geométricas dos fractais e utiliza o conceito de auto-semelhança para a diversificação adaptativa do espaço. No núcleo do algoritmo está uma heurística inovadora que avalia a perspectiva de diferentes áreas de busca com base na densidade de soluções de qualidade localizadas nelas.
Um aspecto central do método proposto é a divisão iterativa do espaço de busca em subespaços, com a identificação das zonas mais promissoras, que depois são submetidas a uma análise mais detalhada e intensiva. Durante o funcionamento do algoritmo, formam-se estruturas fractais auto-semelhantes, direcionadas para a solução ótima, garantindo um equilíbrio entre diversificação global e refinamento local das soluções encontradas. No artigo, analisaremos em detalhe os fundamentos teóricos do algoritmo, os detalhes de sua implementação, a configuração dos parâmetros-chave e apresentaremos os resultados de uma análise comparativa com outros métodos populares de otimização em funções de teste padrão.
Implementação do algoritmo
Imagine que você está procurando um tesouro em um campo enorme. Como você agiria? Provavelmente não começaria a cavar cada centímetro do solo, pois isso levaria tempo demais. É exatamente esse tipo de problema que o algoritmo fractal (FBA) resolve, ele ajuda a encontrar o "tesouro", que é a solução ótima, em um espaço gigantesco de possibilidades, sem verificar cada ponto.
Como é possível representar o funcionamento desse algoritmo? Primeiro, dividimos todo o território de busca em quadrados iguais, como um tabuleiro de xadrez. Em seguida, lançamos "buscadores" (pontos aleatórios) por todo o campo para obter uma primeira noção do terreno. Cada buscador reporta a adaptabilidade da área que encontrou. O algoritmo seleciona os mais bem-sucedidos, isto é, 60% dos melhores pontos, e observa em quais quadrados eles se concentram. Esses quadrados são marcados como "zonas promissoras", correspondentes a 30% dos melhores quadrados.
Agora, a atenção se concentra exatamente nas áreas promissoras. Cada uma dessas áreas é dividida em quadrados menores, criando-se uma estrutura fractal. A maioria dos novos buscadores de tesouro é direcionada justamente para essas áreas promissoras e, para não perder o tesouro fora das zonas já exploradas, o algoritmo faz com que alguns buscadores, cerca de 5%, ajam de forma um pouco caótica, desviando-se de suas posições em direções aleatórias e explorando locais inesperados.
O processo se repete continuamente. A cada passo, o algoritmo determina com mais precisão onde o tesouro pode estar e direciona mais buscadores para lá. Gradualmente, forma-se uma estrutura hierárquica de quadrados de diferentes tamanhos, lembrando um fractal, daí o nome do algoritmo.
Figura 1. Representação visual do funcionamento do algoritmo FBA
A ideia principal do FBA, mostrada na figura acima, consiste na divisão gradual do espaço de busca em áreas cada vez menores de forma fractal, concentrando os recursos computacionais nas regiões mais promissoras. Isso cria uma estrutura auto-semelhante que explora o espaço de soluções. Passamos à escrita do pseudocódigo do algoritmo FBA.
- Dividir todo o espaço de busca em subespaços iguais
- Gerar a população inicial de forma uniforme em todo o espaço
- Avaliar a adaptabilidade de cada ponto
- Determinação dos pontos promissores: selecionar P1% dos pontos com melhor adaptabilidade.
- Cálculo dos postos dos subespaços: contar quantos pontos promissores caem em cada subespaço.
- Seleção dos subespaços promissores: selecionar P2% dos subespaços com os postos promissores mais altos.
- Divisão dos subespaços promissores: divisão adicional das áreas promissoras em subespaços menores.
- Geração da nova população: criação de novos pontos com maior densidade nas regiões promissoras.
- Aplicação da mutação: adicionar ruído gaussiano a P3% dos pontos, mecanismo de diversificação.
- Integração das populações: união da população atual com a nova população, preservando os melhores pontos.
- Continue até que o critério de parada seja alcançado, como número máximo de iterações, limiar de adaptabilidade etc.
- Retorne a melhor solução encontrada
Como já compreendemos o conceito do algoritmo, podemos passar à escrita do código. A classe "C_AO_FBA" representa uma implementação especializada do algoritmo de otimização baseado em princípios fractais e deriva da classe base "C_AO".
A classe possui métodos públicos e parâmetros responsáveis pela configuração e pelas ações principais do algoritmo. O construtor define os parâmetros iniciais, como o tamanho da população, as porcentagens de pontos e subespaços promissores, a fração de pontos para alterações aleatórias e o número de intervalos para a divisão de cada dimensão. O método "SetParams" permite atualizar dinamicamente os parâmetros a partir de fontes externas. O método "Init" e as funções subsequentes "Moving" e "Revision" controlam os estágios e as iterações do algoritmo.
Na classe também é declarada uma representação estrutural interna "S_Subspace", que é utilizada para descrever um subespaço de busca. Cada subespaço é caracterizado pelos limites mínimos e máximos em cada dimensão, pelo grau de sua adaptabilidade, pelo nível na hierarquia e pela ligação com o subespaço pai.
Os principais métodos dentro da classe incluem funcionalidades para:
- Verificar se um ponto se encontra dentro de um determinado subespaço.
- Criar a anotação inicial do espaço e sua divisão posterior.
- Identificar pontos promissores, calcular seus postos e selecionar os melhores subespaços para divisões adicionais.
- Gerar uma nova população por meio de união, mutações e ordenação segundo o critério de eficiência ou adaptabilidade.
Dessa forma, a classe "C_AO_FBA" implementa um algoritmo adaptativo, hierárquico e baseado em fractais para a busca de soluções ótimas em tarefas complexas e multidimensionais, utilizando a divisão dinâmica do espaço, a avaliação de áreas promissoras e operadores heurísticos para aumentar a eficiência da busca.
//—————————————————————————————————————————————————————————————————————————————— class C_AO_FBA : public C_AO { public: //-------------------------------------------------------------------- ~C_AO_FBA () { } C_AO_FBA () { ao_name = "FBA"; ao_desc = "Fractal-Based Algorithm"; ao_link = "https://www.mql5.com/en/articles/17458"; popSize = 50; // population size P1 = 60; // percentage of promising points P2 = 30; // percentage of promising subspaces P3 = 0.8; // percentage of points for random modification m_value = 10; // number of intervals to split each dimension into ArrayResize (params, 5); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "P1"; params [1].val = P1; params [2].name = "P2"; params [2].val = P2; params [3].name = "P3"; params [3].val = P3; params [4].name = "m_value"; params [4].val = m_value; } void SetParams () { popSize = (int)params [0].val; P1 = (int)params [1].val; P2 = (int)params [2].val; P3 = params [3].val; m_value = (int)params [4].val; } bool Init (const double &rangeMinP [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step change const int epochsP = 0); // number of epochs void Moving (); void Revision (); //---------------------------------------------------------------------------- int P1; // percentage of promising points int P2; // percentage of promising subspaces double P3; // share of points for random modification int m_value; // number of intervals to split each dimension into private: //------------------------------------------------------------------- // Structure for representing a subspace struct S_Subspace { double min []; // minimal boundaries of the subspace double max []; // maximum boundaries of the subspace double promisingRank; // potential rank (normalized value) bool isPromising; // flag of potential int parentIndex; // index of the parent subspace (-1 for root ones) int level; // level in hierarchy (0 for original space) void Init (int coords) { ArrayResize (min, coords); ArrayResize (max, coords); promisingRank = 0.0; isPromising = false; parentIndex = -1; level = 0; } }; S_Subspace subspaces []; // array of subspaces // Auxiliary methods bool IsPointInSubspace (const double &point [], const S_Subspace &subspace); void CreateInitialSpacePartitioning (); void DivideSubspace (int subspaceIndex); void IdentifyPromisingPoints (int &promisingIndices []); void CalculateSubspaceRanks (const int &promisingIndices []); void SelectPromisingSubspaces (); void DividePromisingSubspaces (); void GenerateNewPopulation (); void MutatePoints (); void SortByFitness (double &values [], int &indices [], int size, bool ascending = false); void QuickSort (double &values [], int &indices [], int low, int high, bool ascending); int Partition (double &values [], int &indices [], int low, int high, bool ascending); }; //——————————————————————————————————————————————————————————————————————————————
O método de inicialização "Init" é destinado à definição das condições iniciais de funcionamento do algoritmo. Ele recebe arrays com os limites mínimos e máximos das variáveis e os passos de variação para cada parâmetro, bem como o número de épocas. Dentro do método, inicialmente é chamada a inicialização base e, em seguida, é criada a divisão inicial do espaço de busca, isto é, forma-se a estrutura inicial de subespaços com base nos intervalos e passos definidos. Se todas as operações forem bem-sucedidas, o método retorna "true", caso contrário, retorna "false".
O método principal de movimento "Moving" executa o ciclo de busca pela solução por meio de iterações sequenciais. A primeira iteração corresponde à inicialização da população inicial de pontos de forma uniforme em todo o espaço investigado, em que cada valor da variável é escolhido aleatoriamente dentro do intervalo e ajustado ao passo definido.
Em seguida, no processo principal de trabalho, ocorrem vários passos. Primeiro, são identificados os pontos mais promissores, isto é, uma pequena parte dos melhores segundo o valor da função de eficiência. Depois, é realizado o cálculo dos postos desses pontos em relação à sua adaptabilidade para cada subespaço. Com base nesses postos, são selecionados os subespaços mais promissores para posterior divisão em áreas menores. Após isso, essas áreas promissoras são subdivididas, criando localizações de busca mais precisas. Em seguida, forma-se uma nova população de pontos levando em conta seus postos de adaptabilidade, o que permite concentrar os esforços nas regiões mais promissoras. Ao final, é realizada a modificação aleatória dos pontos, isto é, a mutação, para aumentar a diversificação e evitar o aprisionamento em soluções locais.
//—————————————————————————————————————————————————————————————————————————————— bool C_AO_FBA::Init (const double &rangeMinP [], // minimum values const double &rangeMaxP [], // maximum values const double &rangeStepP [], // step change const int epochsP = 0) // number of epochs { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //---------------------------------------------------------------------------- // Create an initial partition of the search space CreateInitialSpacePartitioning (); return true; } //—————————————————————————————————————————————————————————————————————————————— //+----------------------------------------------------------------------------+ //| Basic optimization method | //+----------------------------------------------------------------------------+ void C_AO_FBA::Moving () { // First iteration - initialization of the initial population if (!revision) { // Initialize the initial population uniformly throughout the space for (int i = 0; i < popSize; i++) { for (int c = 0; c < coords; c++) { a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [i].c [c] = u.SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; return; } // Main optimization // 1. Identifying promising points (P1% of points with the best function values) int promisingIndices []; IdentifyPromisingPoints (promisingIndices); // 2. Calculation of potential ranks for each subspace CalculateSubspaceRanks (promisingIndices); // 3. Selecting the P2% most promising subspaces SelectPromisingSubspaces (); // 4. Dividing promising subspaces into smaller ones DividePromisingSubspaces (); // 5. Generating new points taking into account potential ranks GenerateNewPopulation (); // 6. Random modification (mutation) MutatePoints (); } //——————————————————————————————————————————————————————————————————————————————
O método "Revision" é responsável por atualizar a melhor solução encontrada no processo de execução do algoritmo. Ele percorre todos os elementos da população atual e compara o valor da função objetivo de cada elemento com o melhor valor atual. Se algum elemento apresentar um resultado melhor, a variável que armazena o melhor resultado é atualizada e o array de variáveis associado a ele, isto é, as coordenadas, é copiado para fixar essa solução ótima. Dessa forma, o método garante o acompanhamento contínuo e a preservação do melhor resultado encontrado até o momento.
//+----------------------------------------------------------------------------+ //| Update the best solution | //+----------------------------------------------------------------------------+ void C_AO_FBA::Revision () { // Search for the best solution for (int i = 0; i < popSize; i++) { // Update the best solution if (a [i].f > fB) { fB = a [i].f; ArrayCopy (cB, a [i].c, 0, 0, WHOLE_ARRAY); } } } //——————————————————————————————————————————————————————————————————————————————
O método de criação da divisão inicial do espaço é destinado à formação da estrutura de subespaços que será utilizada para localizar a busca por soluções ótimas. Ele determina o número total de subespaços com base no grau de divisão definido e na dimensionalidade. No caso de dimensionalidade muito elevada, esse número é limitado por um máximo previamente estabelecido, a fim de evitar custos excessivos de recursos.
Em seguida, ocorre a inicialização do array de subespaços, a cada um dos quais são atribuídos os parâmetros iniciais de nível e de limites para cada coordenada. Dependendo da dimensionalidade do espaço, é escolhido o método de divisão mais adequado:
- Para um espaço unidimensional, ele é dividido em intervalos uniformes, e cada subespaço criado ocupa um determinado trecho do intervalo.
- Para um espaço bidimensional, a divisão ocorre ao longo de dois eixos, formando uma grade de regiões retangulares.
- No caso de dimensões mais altas, é utilizada uma abordagem iterativa, em que, de forma análoga a um sistema de contadores, são geradas combinações de índices para cada coordenada e, para cada região criada, são definidos limites com base nos intervalos correspondentes.
O cálculo dos limites ocorre por meio da divisão dos intervalos de cada dimensão em partes iguais, e para cada subespaço são estabelecidos os limites mínimos e máximos de acordo com os índices atuais. A iteração continua até que todos os subespaços necessários sejam criados ou até que seja atingido o limite de sua quantidade. Como resultado, forma-se uma estrutura que representa a divisão inicial do espaço de busca, pronta para posterior refinamento e para a busca de soluções.
//+----------------------------------------------------------------------------+ //| Create the initial partition of the search space | //+----------------------------------------------------------------------------+ void C_AO_FBA::CreateInitialSpacePartitioning () { // Create an initial partition of space int totalSubspaces = (int)MathPow (m_value, coords); // For very large dimensions, limit the number of subspaces if (totalSubspaces > 10000) totalSubspaces = 10000; ArrayResize (subspaces, totalSubspaces); // Initialize all subspaces for (int i = 0; i < totalSubspaces; i++) { subspaces [i].Init (coords); subspaces [i].level = 0; // Initial level } // Divide the initial space into equal subspaces int index = 0; // Select the division method depending on the dimensionality of the space if (coords == 1) { // One-dimensional case double intervalSize = (rangeMax [0] - rangeMin [0]) / m_value; for (int i = 0; i < m_value && index < totalSubspaces; i++) { subspaces [index].min [0] = rangeMin [0] + i * intervalSize; subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize; index++; } } else if (coords == 2) { // Two-dimensional case double intervalSize0 = (rangeMax [0] - rangeMin [0]) / m_value; double intervalSize1 = (rangeMax [1] - rangeMin [1]) / m_value; for (int i = 0; i < m_value && index < totalSubspaces; i++) { for (int j = 0; j < m_value && index < totalSubspaces; j++) { subspaces [index].min [0] = rangeMin [0] + i * intervalSize0; subspaces [index].max [0] = rangeMin [0] + (i + 1) * intervalSize0; subspaces [index].min [1] = rangeMin [1] + j * intervalSize1; subspaces [index].max [1] = rangeMin [1] + (j + 1) * intervalSize1; index++; } } } else { // Multidimensional case - use an iterative approach int indices []; ArrayResize (indices, coords); for (int i = 0; i < coords; i++) indices [i] = 0; while (index < totalSubspaces) { // Calculate the boundaries of the current subspace for (int c = 0; c < coords; c++) { double intervalSize = (rangeMax [c] - rangeMin [c]) / m_value; subspaces [index].min [c] = rangeMin [c] + indices [c] * intervalSize; subspaces [index].max [c] = rangeMin [c] + (indices [c] + 1) * intervalSize; } // Move on to the next subspace int c = coords - 1; while (c >= 0) { indices [c]++; if (indices [c] < m_value) break; indices [c] = 0; c--; } // If the full loop completed, exit if (c < 0) break; index++; } } } //——————————————————————————————————————————————————————————————————————————————
O método seguinte é destinado a determinar se um determinado ponto pertence a um subespaço específico. Ele verifica sequencialmente cada coordenada do ponto, comparando seu valor com os limites do subespaço correspondente. Se ao menos para uma coordenada o ponto ultrapassar os limites permitidos, isto é, for menor que o mínimo ou maior ou igual ao máximo, o método retorna "false", o que significa que o ponto não está contido nesse subespaço. Se todas as coordenadas satisfizerem as condições, o método confirma a pertença do ponto ao subespaço, retornando true.
//+----------------------------------------------------------------------------+ //| Determine whether a point belongs to a subspace | //+----------------------------------------------------------------------------+ bool C_AO_FBA::IsPointInSubspace (const double &point [], const S_Subspace &subspace) { // Check if the point is in the specified subspace for (int c = 0; c < coords; c++) { if (point [c] < subspace.min [c] || point [c] >= subspace.max [c]) { return false; } } return true; } //——————————————————————————————————————————————————————————————————————————————
O método de determinação de pontos promissores é destinado a destacar as soluções mais "promising" da população atual. Ele começa com a criação de arrays temporários para armazenar os valores da função de adaptabilidade de cada elemento e seus respectivos índices. Em seguida, esses arrays são preenchidos com os valores e índices correspondentes dos elementos da população.
Depois disso, ocorre a ordenação dos elementos pelo valor da função de adaptabilidade em ordem decrescente. Após a ordenação, é selecionada uma determinada porcentagem das melhores soluções, definida como P1%, e a partir delas é formada uma lista de índices que representam os pontos promissores. A quantidade de pontos selecionados é garantida, no mínimo um, e não excede o tamanho total da população. Como resultado, a função retorna um array de índices das soluções promissoras.
//+----------------------------------------------------------------------------+ //| Identify promising points | //+----------------------------------------------------------------------------+ void C_AO_FBA::IdentifyPromisingPoints (int &promisingIndices []) { // Select P1% points with the best function values // Create arrays for sorting double values []; int indices []; ArrayResize (values, popSize); ArrayResize (indices, popSize); // Fill in the arrays for (int i = 0; i < popSize; i++) { values [i] = a [i].f; indices [i] = i; } // Sort in descending order (for the maximization problem) SortByFitness (values, indices, popSize); // Select P1% best points int numPromisingPoints = (int)MathRound (popSize * P1 / 100.0); numPromisingPoints = MathMax (1, MathMin (numPromisingPoints, popSize)); ArrayResize (promisingIndices, numPromisingPoints); for (int i = 0; i < numPromisingPoints; i++) { promisingIndices [i] = indices [i]; } } //——————————————————————————————————————————————————————————————————————————————
Em seguida, o método é destinado à avaliação e ao ranqueamento dos subespaços de acordo com sua adaptabilidade. Ele começa com a reinicialização dos valores atuais de classificação para todos os subespaços. Depois disso, é contabilizado quantos pontos promissores caem em cada subespaço, comparando as coordenadas de cada ponto promissor com os limites de cada subespaço e incrementando o contador correspondente quando há coincidência.
É importante que cada ponto seja considerado apenas em um único subespaço. Após a contagem dos valores quantitativos, os postos de cada subespaço são normalizados pela divisão pelo número total de pontos promissores, o que fornece uma avaliação relativa da adaptabilidade de cada subespaço, em que o valor varia entre 0 e 1 e corresponde à proporção de pontos promissores dentro de cada subespaço em relação à população total de pontos promissores. Como resultado, obtém-se um ranking.
//+----------------------------------------------------------------------------+ //| Calculate potential ranks of subspaces | //+----------------------------------------------------------------------------+ void C_AO_FBA::CalculateSubspaceRanks (const int &promisingIndices []) { // Reset the ranks of subspaces for (int i = 0; i < ArraySize (subspaces); i++) { subspaces [i].promisingRank = 0.0; } // Calculate promising points in each subspace for (int i = 0; i < ArraySize (promisingIndices); i++) { int pointIndex = promisingIndices [i]; for (int j = 0; j < ArraySize (subspaces); j++) { if (IsPointInSubspace (a [pointIndex].c, subspaces [j])) { subspaces [j].promisingRank++; break; // A point can only be in one subspace } } } // Normalize the potential ranks according to the article // PromisingRank = Number of promising points in s / Total promising points int totalPromisingPoints = ArraySize (promisingIndices); if (totalPromisingPoints > 0) { for (int i = 0; i < ArraySize (subspaces); i++) { subspaces [i].promisingRank = subspaces [i].promisingRank / totalPromisingPoints; } } } //——————————————————————————————————————————————————————————————————————————————
O método "SelectPromisingSubspaces" determina quais subespaços devem ser considerados promissores com base em seus postos. São criados arrays temporários "ranks" e "indices" para armazenar os rankings dos subespaços e seus respectivos índices. Os valores dos rankings e os índices dos subespaços são copiados para os arrays temporários. Para cada subespaço, o flag "isPromising" é definido como "false". Isso é necessário para começar do zero e não considerar os resultados de iterações anteriores. O array "ranks" é ordenado em ordem decrescente e, em paralelo, o array "indices" é reorganizado de forma a preservar a correspondência entre os índices e os rankings.
Dessa forma, após a ordenação, o array "indices" contém os índices dos subespaços classificados em ordem decrescente de seus rankings. É calculada a quantidade de subespaços que serão considerados promissores com base no parâmetro "P2", que representa a porcentagem dos melhores subespaços. O valor obtido é limitado ao intervalo entre 1 e o número total de subespaços. Em seguida, percorrem-se os primeiros "numPromisingSubspaces" elementos do array "indices". Para cada índice nesse array, o flag "isPromising" é definido como "true" para o subespaço correspondente. Isso significa que o subespaço em questão é considerado promissor.
Também é realizada uma verificação do índice para garantir que ele esteja dentro do intervalo permitido, evitando erros ao acessar o array "subspaces". Como resultado da execução do método, o flag "isPromising" fica definido como "true" para P2% dos subespaços com os postos mais altos.
//+----------------------------------------------------------------------------+ //| Select promising subspaces | //+----------------------------------------------------------------------------+ void C_AO_FBA::SelectPromisingSubspaces () { // Select P2% subspaces with the highest ranks as promising ones // Create arrays for sorting double ranks []; int indices []; int numSubspaces = ArraySize (subspaces); ArrayResize (ranks, numSubspaces); ArrayResize (indices, numSubspaces); // Fill in the arrays for (int i = 0; i < numSubspaces; i++) { ranks [i] = subspaces [i].promisingRank; indices [i] = i; // Reset the potential flag subspaces [i].isPromising = false; } // Sort by descending ranks SortByFitness (ranks, indices, numSubspaces); // Select P2% most promising subspaces int numPromisingSubspaces = (int)MathRound (numSubspaces * P2 / 100.0); numPromisingSubspaces = MathMax (1, MathMin (numPromisingSubspaces, numSubspaces)); // Mark promising subspaces for (int i = 0; i < numPromisingSubspaces && i < ArraySize (indices); i++) { // Protection against exceeding the array size if (indices [i] >= 0 && indices [i] < ArraySize (subspaces)) { subspaces [indices [i]].isPromising = true; } } } //——————————————————————————————————————————————————————————————————————————————
O método "DividePromisingSubspaces" é destinado à divisão dos subespaços promissores em partes menores. Inicialmente, ele identifica todos os subespaços marcados como promissores por meio da verificação do flag "isPromising". Os índices desses subespaços são coletados em um array temporário "promisingIndices". Em seguida, para cada subespaço cujo índice está presente no array "promisingIndices", é chamada a função "DivideSubspace", passando o índice desse subespaço.
Dessa forma, o método percorre todos os subespaços promissores identificados e aplica sequencialmente a divisão a cada um deles por meio da função "DivideSubspace".
//+----------------------------------------------------------------------------+ //| Separate promising subspaces | //+----------------------------------------------------------------------------+ void C_AO_FBA::DividePromisingSubspaces () { // Collect indices of promising subspaces int promisingIndices []; int numPromising = 0; for (int i = 0; i < ArraySize (subspaces); i++) { if (subspaces [i].isPromising) { numPromising++; ArrayResize (promisingIndices, numPromising); promisingIndices [numPromising - 1] = i; } } // Divide each promising subspace for (int i = 0; i < numPromising; i++) { DivideSubspace (promisingIndices [i]); } } //——————————————————————————————————————————————————————————————————————————————
O método "DivideSubspace" é destinado à divisão de um subespaço específico em partes menores. Inicialmente, o subespaço pai é selecionado com base no índice fornecido. É verificado se o número total de subespaços não ultrapassa o limite estabelecido de 10 000. Em seguida, é determinado o número total de novos subespaços que serão gerados como resultado da divisão de cada dimensão em "m_value" partes, o que corresponde à elevação de "m_value" à potência igual ao número de dimensões.
O array que armazena todos os subespaços é expandido pelo número de novos subespaços a serem criados. Para cada novo subespaço, são definidos os parâmetros iniciais, como o nível, o índice do subespaço pai e os limites de cada coordenada, que são calculados com base nos limites do subespaço pai e na divisão em partes iguais.
Para cada dimensão, é determinado o tamanho do intervalo, e os limites do subespaço atual são estabelecidos de acordo com os índices correntes. Após a criação de cada novo subespaço, ocorre o incremento dos índices das dimensões para passar à próxima divisão no sistema de multi-índices. Quando o índice de uma dimensão atinge "m_value", ele é reiniciado para zero, e o índice da próxima dimensão é incrementado, realizando-se a enumeração de todas as combinações.
O processo continua até que todos os novos subespaços sejam completamente criados ou até que o limite seja atingido. No caso de enumeração completa de todas as combinações por meio do sistema de contadores, a finalização ocorre de forma natural. Como resultado da execução do método, o subespaço pai é dividido em diversos subespaços menores, cada um cobrindo a respectiva parte do intervalo original em todas as dimensões.
//+----------------------------------------------------------------------------+ //| Partition a specific subspace | //+----------------------------------------------------------------------------+ void C_AO_FBA::DivideSubspace (int subspaceIndex) { // Divide the specified subspace into m_value^coords subspaces S_Subspace parent = subspaces [subspaceIndex]; // Limit the maximum number of subspaces if (ArraySize (subspaces) > 10000) return; // For each dimension, divide by m_value parts int totalNewSubspaces = (int)MathPow (m_value, coords); int currentSize = ArraySize (subspaces); ArrayResize (subspaces, currentSize + totalNewSubspaces); // Create new subspaces int newIndex = currentSize; int indices []; ArrayResize (indices, coords); for (int i = 0; i < coords; i++) indices [i] = 0; for (int idx = 0; idx < totalNewSubspaces && newIndex < ArraySize (subspaces); idx++) { subspaces [newIndex].Init (coords); subspaces [newIndex].level = parent.level + 1; subspaces [newIndex].parentIndex = subspaceIndex; // Calculate the boundaries of the current subspace for (int c = 0; c < coords; c++) { double intervalSize = (parent.max [c] - parent.min [c]) / m_value; subspaces [newIndex].min [c] = parent.min [c] + indices [c] * intervalSize; subspaces [newIndex].max [c] = parent.min [c] + (indices [c] + 1) * intervalSize; } // Move on to the next subspace int c = coords - 1; while (c >= 0) { indices [c]++; if (indices [c] < m_value) break; indices [c] = 0; c--; } // If the full loop completed, exit if (c < 0) break; newIndex++; } } //——————————————————————————————————————————————————————————————————————————————
O método "GenerateNewPopulation" cria uma nova população de pontos, distribuindo-os pelos subespaços de acordo com sua "adaptabilidade", determinada pelo parâmetro "promisingRank".
Primeiramente, é calculada a soma total de "promisingRank" de todos os subespaços. Esse valor será utilizado para determinar a quantidade proporcional de pontos que deve ser gerada em cada subespaço. Se a soma dos postos se mostrar próxima de zero, isto é, menor que 0.0001, o que pode ocorrer quando todos os subespaços apresentam posto zero, então todos os subespaços recebem um posto positivo mínimo, igual a 1.0, para garantir uma distribuição uniforme dos pontos. Em seguida, para cada subespaço, é calculado o número de pontos que devem ser gerados nele, de forma proporcional ao seu "promisingRank" em relação à soma total dos postos.
É utilizada a fórmula (subspaces[i].promisingRank / totalRank) * popSize, em que popSize é o tamanho desejado da população. O resultado é arredondado para o inteiro mais próximo. A quantidade de pontos é limitada superiormente para não ultrapassar "popSize". Dentro de cada subespaço, é gerado o número calculado de pontos e, para cada ponto, são geradas "coords" coordenadas, utilizando uma distribuição uniforme dentro dos limites do subespaço. Para cada dimensão, o valor da coordenada é limitado pelos valores mínimo e máximo definidos e ajustado à grade com passo "rangeStep[c]".
Se, após a distribuição dos pontos pelos subespaços, o número total de pontos gerados for menor que "popSize", os pontos restantes são gerados de forma uniforme em todo o espaço de busca, utilizando os limites globais do espaço "rangeMin[c]" e "rangeMax[c]", respeitando as restrições e ajustando à grade com passo "rangeStep[c]". Isso garante que a população sempre tenha o tamanho "popSize".
//+----------------------------------------------------------------------------+ //| Generate a new population | //+----------------------------------------------------------------------------+ void C_AO_FBA::GenerateNewPopulation () { // Calculate the sum of the ranks of all subspaces double totalRank = 0.0; for (int i = 0; i < ArraySize (subspaces); i++) { totalRank += subspaces [i].promisingRank; } // If all ranks are 0, set the uniform distribution if (totalRank <= 0.0001) // Check for approximate equality to zero { for (int i = 0; i < ArraySize (subspaces); i++) { subspaces [i].promisingRank = 1.0; } totalRank = ArraySize (subspaces); } int points = 0; for (int i = 0; i < ArraySize (subspaces) && points < popSize; i++) { // Calculate the number of points for this subspace according to the equation int pointsToGenerate = (int)MathRound ((subspaces [i].promisingRank / totalRank) * popSize); // Limitation against exceeding the limits pointsToGenerate = MathMin (pointsToGenerate, popSize - points); // Generate points in this subspace for (int j = 0; j < pointsToGenerate; j++) { // Create a new point uniformly within the subspace for (int c = 0; c < coords; c++) { a [points].c [c] = u.RNDfromCI (subspaces [i].min [c], subspaces [i].max [c]); a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } points++; if (points >= popSize) break; } } // If not all points were generated, fill the remaining ones uniformly throughout the space while (points < popSize) { for (int c = 0; c < coords; c++) { a [points].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [points].c [c] = u.SeInDiSp (a [points].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } points++; } } //——————————————————————————————————————————————————————————————————————————————
O método "MutatePoints" da classe "C_AO_FBA" é destinado à realização da mutação dos pontos na população e faz parte do procedimento do algoritmo para aumentar a variabilidade das soluções e evitar o aprisionamento em armadilhas locais.
Na parte inicial do método, estava prevista a ideia de adicionar ruído gaussiano às coordenadas de pontos selecionados aleatoriamente, conforme o algoritmo FBA original. No entanto, com esse tipo de mutação o algoritmo apresenta um desempenho muito fraco e praticamente não se diferencia dos resultados de um algoritmo aleatório, razão pela qual esse bloco foi comentado, pois foi encontrada uma implementação mais eficaz.
A principal parte implementada do método consiste em percorrer toda a população. Para cada agente, isto é, cada ponto, e para cada coordenada, é verificada uma condição probabilística. Se ela for satisfeita, com base em uma probabilidade de mutação previamente definida, o valor da coordenada é alterado por meio de uma função baseada em uma distribuição de potência, cuja intensidade permite controlar o grau de variação. Em seguida, o valor é refinado e limitado por uma função que garante que ele permaneça dentro dos intervalos estabelecidos e leve em consideração os passos de discretização.
Como resultado, o método assegura mutações aleatórias de pontos individuais da população, promovendo a diversidade das soluções e melhorando a capacidade de busca pelo ótimo global.
//+----------------------------------------------------------------------------+ //| Mutation of points in the population | //+----------------------------------------------------------------------------+ void C_AO_FBA::MutatePoints () { // Add Gaussian noise to P3% of randomly selected points from the new population /* int numToMutate = (int)MathRound (popSize * P3 / 100.0); numToMutate = MathMax (1, MathMin (numToMutate, popSize)); for (int i = 0; i < numToMutate; i++) { int index = u.RNDminusOne (popSize); // Add noise to each coordinate for (int c = 0; c < coords; c++) { // Standard deviation of 10% of the range //double stdDev = (rangeMax [c] - rangeMin [c]) * 0.1; // Gaussian noise using the Box-Muller method //double noise = NormalRandom (0.0, stdDev); // Add noise and limit the value a [index].c [c] += noise; a [index].c [c] = u.SeInDiSp (a [index].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } */ for (int p = 0; p < popSize; p++) { for (int c = 0; c < coords; c++) { if (u.RNDprobab () < P3) { a [p].c [c] = u.PowerDistribution (cB [c], rangeMin [c], rangeMax [c], 20); a [p].c [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } } } //——————————————————————————————————————————————————————————————————————————————
O método "SortByFitness" é destinado à ordenação de dois arrays, um contendo os valores da função de adaptabilidade e o outro contendo os índices correspondentes dos elementos. Ele recebe como parâmetros o array de valores, o array de índices, o tamanho dos arrays e um flag opcional que indica a ordem de ordenação.
Se o tamanho do array for maior que um, o método chama a função interna "QuickSort", que executa a ordenação rápida dos elementos. Nesse processo, ambos os arrays são ordenados simultaneamente, de modo que a correspondência entre valores e índices seja preservada. Como resultado, após a execução do método, os elementos ficam ordenados de acordo com o valor da função de adaptabilidade, conforme a ordem selecionada.
//+----------------------------------------------------------------------------+ //| Sort by fitness function value | //+----------------------------------------------------------------------------+ void C_AO_FBA::SortByFitness (double &values [], int &indices [], int size, bool ascending = false) { if (size > 1) QuickSort (values, indices, 0, size - 1, ascending); } //——————————————————————————————————————————————————————————————————————————————
O método "QuickSort" implementa o algoritmo de ordenação rápida para dois arrays relacionados, "values", que é o array de valores, e "indices", que é o array de índices. Ele divide e ordena recursivamente os arrays de forma a manter a correspondência entre cada valor e seu índice original. Os parâmetros incluem os arrays a serem ordenados, os limites da região de ordenação, low e high, e o flag "ascending", que define a ordem da ordenação.
//+----------------------------------------------------------------------------+ //| Quick sort algorithm | //+----------------------------------------------------------------------------+ void C_AO_FBA::QuickSort (double &values [], int &indices [], int low, int high, bool ascending) { if (low < high) { int pi = Partition (values, indices, low, high, ascending); QuickSort (values, indices, low, pi - 1, ascending); QuickSort (values, indices, pi + 1, high, ascending); } } //——————————————————————————————————————————————————————————————————————————————
O método "Partition" é a parte central do algoritmo de ordenação rápida. Sua tarefa é selecionar um elemento pivô e redistribuir os elementos do array "indices" de modo que todos os elementos "menores" que o pivô, ou "maiores", dependendo da ordem de ordenação, fiquem à esquerda, enquanto os "maiores", ou "menores", fiquem à direita. Os conceitos de "menor" e "maior" são definidos em relação aos valores no array "values", para os quais apontam os índices contidos em "indices".
//+----------------------------------------------------------------------------+ //| Partition function for QuickSort | //+----------------------------------------------------------------------------+ int C_AO_FBA::Partition (double &values [], int &indices [], int low, int high, bool ascending) { double pivot = values [indices [high]]; int i = low - 1; for (int j = low; j < high; j++) { bool condition = ascending ? (values [indices [j]] < pivot) : (values [indices [j]] > pivot); if (condition) { i++; // Exchange values int temp = indices [i]; indices [i] = indices [j]; indices [j] = temp; } } // Exchange values int temp = indices [i + 1]; indices [i + 1] = indices [high]; indices [high] = temp; return i + 1; } //——————————————————————————————————————————————————————————————————————————————
Resultados dos testes
O resultado apresentado pelo algoritmo é bom.FBA|Fractal-Based Algorithm|50.0|60.0|30.0|0.8|10.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.7900044352090774
25 Hilly's; Func runs: 10000; result: 0.6513385092404853
500 Hilly's; Func runs: 10000; result: 0.2896548031738138
=============================
5 Forest's; Func runs: 10000; result: 0.8715768614282637
25 Forest's; Func runs: 10000; result: 0.5682316842631675
500 Forest's; Func runs: 10000; result: 0.18876552479611478
=============================
5 Megacity's; Func runs: 10000; result: 0.6107692307692306
25 Megacity's; Func runs: 10000; result: 0.46061538461538465
500 Megacity's; Func runs: 10000; result: 0.12398461538461655
=============================
All score: 4.55494 (50.61%)
Na visualização, é possível observar como o algoritmo divide o espaço de busca em subespaços cada vez menores. Também se percebe uma alta variabilidade dos resultados ao trabalhar com funções de baixa dimensionalidade.
FBA na função de teste Hilly
FBA na função de teste Forest
FBA na função de teste Megacity
De acordo com os resultados dos testes, o algoritmo FBA ocupa a 29ª posição em nossa tabela de classificação.
| # | AO | Description | Hilly | Hilly Final | Forest | Forest Final | Megacity (discrete) | Megacity Final | Final Result | % of MAX | ||||||
| 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 | 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 |
| 2 | 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 |
| 3 | 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 |
| 4 | (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 |
| 5 | 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 |
| 6 | 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 |
| 7 | 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 |
| 8 | 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 |
| 9 | 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.548 | 61.64 |
| 10 | 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 |
| 11 | 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 |
| 12 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | TSEA | turtle shell evolution algorithm (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 |
| 19 | 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 |
| 20 | 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 |
| 21 | CRO | chemical reaction optimization | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | SSG | saplings sowing and growing | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | (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 |
| 29 | 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 |
| 30 | 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 |
| 31 | 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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | SOA | simple optimization algorithm | 0.91520 | 0.46976 | 0.27089 | 1.65585 | 0.89675 | 0.37401 | 0.16984 | 1.44060 | 0.69538 | 0.28031 | 0.10852 | 1.08422 | 4.181 | 46.45 |
| 38 | ABHA | artificial bee hive algorithm | 0.84131 | 0.54227 | 0.26304 | 1.64663 | 0.87858 | 0.47779 | 0.17181 | 1.52818 | 0.50923 | 0.33877 | 0.10397 | 0.95197 | 4.127 | 45.85 |
| 39 | ACMO | atmospheric cloud model optimization | 0.90321 | 0.48546 | 0.30403 | 1.69270 | 0.80268 | 0.37857 | 0.19178 | 1.37303 | 0.62308 | 0.24400 | 0.10795 | 0.97503 | 4.041 | 44.90 |
| 40 | ADAMm | adaptive moment estimation M | 0.88635 | 0.44766 | 0.26613 | 1.60014 | 0.84497 | 0.38493 | 0.16889 | 1.39880 | 0.66154 | 0.27046 | 0.10594 | 1.03794 | 4.037 | 44.85 |
| 41 | CGO | chaos game optimization | 0.57256 | 0.37158 | 0.32018 | 1.26432 | 0.61176 | 0.61931 | 0.62161 | 1.85267 | 0.37538 | 0.21923 | 0.19028 | 0.78490 | 3.902 | 43.35 |
| 42 | ATAm | artificial tribe algorithm M | 0.71771 | 0.55304 | 0.25235 | 1.52310 | 0.82491 | 0.55904 | 0.20473 | 1.58867 | 0.44000 | 0.18615 | 0.09411 | 0.72026 | 3.832 | 42.58 |
| 43 | CROm | coral reefs optimization M | 0.78512 | 0.46032 | 0.25958 | 1.50502 | 0.86688 | 0.35297 | 0.16267 | 1.38252 | 0.63231 | 0.26738 | 0.10734 | 1.00703 | 3.895 | 43.27 |
| 44 | CFO | central force optimization | 0.60961 | 0.54958 | 0.27831 | 1.43750 | 0.63418 | 0.46833 | 0.22541 | 1.32792 | 0.57231 | 0.23477 | 0.09586 | 0.90294 | 3.668 | 40.76 |
| 45 | ASHA | artificial showering algorithm | 0.89686 | 0.40433 | 0.25617 | 1.55737 | 0.80360 | 0.35526 | 0.19160 | 1.35046 | 0.47692 | 0.18123 | 0.09774 | 0.75589 | 3.664 | 40.71 |
| RW | neuroboids optimization algorithm 2(joo) | 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 | |
Considerações finais
A versão do algoritmo FBA com mutação modificada, com resultado de 50.61%, demonstra uma melhoria de duas vezes na eficiência em comparação com os resultados da versão original.
FBA|Fractal-Based Algorithm|50.0|60.0|30.0|5.0|
=============================
5 Hilly's; Func runs: 10000; result: 0.4780639253626462
25 Hilly's; Func runs: 10000; result: 0.3222029113692554
500 Hilly's; Func runs: 10000; result: 0.25720991988937014
=============================
5 Forest's; Func runs: 10000; result: 0.36567166223346415
25 Forest's; Func runs: 10000; result: 0.22043205527307377
500 Forest's; Func runs: 10000; result: 0.15869146061036057
=============================
5 Megacity's; Func runs: 10000; result: 0.2861538461538461
25 Megacity's; Func runs: 10000; result: 0.15015384615384622
500 Megacity's; Func runs: 10000; result: 0.09838461538461622
=============================
All score: 2.33696 (25.97%)
Graças a mudanças fundamentais no mecanismo de mutação, a nova abordagem garante um equilíbrio mais razoável entre a diversificação global do espaço de busca e a intensificação local das soluções promissoras encontradas.
A principal conquista reside no fato de que o algoritmo agora utiliza o conhecimento acumulado sobre o relevo do espaço de busca para direcionar o processo de mutação, em vez de realizar alterações completamente aleatórias. Isso está mais alinhado com processos naturais de otimização, nos quais aleatoriedade e determinismo coexistem de forma equilibrada. Essa abordagem permite que o algoritmo convirja mais rapidamente para o ótimo global, especialmente em espaços multidimensionais complexos com numerosos extremos locais, o que explica a melhoria significativa de desempenho.
Figura 2. Gradiente de cores dos algoritmos de acordo com os testes correspondentes
Figura 3. Histograma dos resultados de teste dos algoritmos (em uma escala de 0 a 100, quanto maior, melhor, onde 100 — o resultado teórico máximo possível, no arquivo há um script para o cálculo da tabela de classificação)
Prós e contras do algoritmo FBA:
Prós:
- Resultados estáveis em funções de média e alta dimensionalidade.
Contras:
- Grande dispersão dos resultados em funções de baixa dimensionalidade.
- Ideia base do algoritmo interessante, porém relativamente "fraca".
Está anexado ao artigo um arquivo com as versões atualizadas dos códigos dos algoritmos. O autor do artigo não se responsabiliza pela absoluta precisão na descrição dos algoritmos canônicos, pois muitos deles sofreram modificações para melhorar as capacidades de busca. As conclusões e julgamentos apresentados nos artigos baseiam-se nos resultados dos experimentos realizados.
Programas utilizados no artigo
| # | Nome | Tipo | Descrição |
|---|---|---|---|
| 1 | #C_AO.mqh | Arquivo incluído | Classe pai dos algoritmos populacionais de otimização |
| 2 | #C_AO_enum.mqh | Arquivo incluído | Enumeração dos algoritmos populacionais de otimização |
| 3 | TestFunctions.mqh | Arquivo incluído | Biblioteca de funções de teste |
| 4 | TestStandFunctions.mqh | Arquivo incluído | Biblioteca de funções do banco de testes |
| 5 | Utilities.mqh | Arquivo incluído | Biblioteca de funções auxiliares |
| 6 | CalculationTestResults.mqh | Arquivo incluído | Script para cálculo dos resultados na tabela comparativa |
| 7 | Testing AOs.mq5 | Script | Banco de testes unificado para todos os algoritmos populacionais de otimização |
| 8 | Simple use of population optimization algorithms.mq5 | Script | Exemplo simples de uso de algoritmos populacionais de otimização sem visualização |
| 9 | Test_FBA.mq5 | Script | Banco de testes para o FBA |
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/17458
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.
Modelos ocultos de Markov em sistemas de trading com aprendizado de máquina
Redefinindo os Indicadores MQL5 e MetaTrader 5
Construindo Expert Advisors Auto-Otimizáveis em MQL5 (Parte 4): Dimensionamento Dinâmico de Posição
Desenvolvimento do Kit de Ferramentas de Análise de Price Action (Parte 9): Fluxo Externo
- 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