Algoritmo de Busca com Retrocesso — Backtracking Search Algorithm (BSA)
18
0
Conteúdo
Introdução
No labirinto infinito de possibilidades, onde cada curva pode levar tanto ao triunfo quanto a um beco sem saída, o viajante sábio deixa para trás rastros invisíveis, algo etéreo, mas ao mesmo tempo mais confiável: a memória dos caminhos percorridos. Essa sabedoria antiga, olhar para trás para enxergar o futuro, serviu de base para o algoritmo de otimização. Cada passo no desconhecido é dado com base na experiência do passado, em que a história vira bússola e as lembranças viram mapa.
Neste artigo, vamos analisar um algoritmo que achei muito interessante, graças à sua ideia de busca. Backtracking Search Algorithm (BSA) é um novo algoritmo evolutivo (EA) para resolver problemas de otimização numérica com valores reais, proposto por Pinar Civicioglu em 2013. É um método de busca da melhor solução que sabe "aprender com a experiência passada".
Implementação do algoritmo
O BSA funciona pelo princípio dos algoritmos evolutivos, mas tem características únicas, usando duas populações:- população atual (P), população em evolução ativa
- população histórica (oldP), população selecionada aleatoriamente de gerações passadas
O BSA usa uma estratégia aleatória de mutação, que produz apenas uma solução direcional para cada indivíduo-alvo. Fórmula de mutação:
Mutant = P + F × (oldP - P)
onde F é o fator de amplitude, que controla o tamanho do passo de busca.
O processo de crossover do BSA inclui dois passos. A primeira estratégia usa "mixrate". A segunda estratégia permite que apenas um indivíduo escolhido aleatoriamente em cada amostra sofra mutação. Imagine que você com seus amigos (esta é a nossa população) está procurando a melhor pizzaria da cidade.
Situação inicial:
- você tem 10 amigos (tamanho da população),
- cada um começa a busca em um bairro aleatório da cidade,
- cada um tem um smartphone com o mapa das saídas anteriores (memória histórica).
Dia 1: todos se espalharam pela cidade. O primeiro amigo encontrou uma pizzaria com nota 7/10, o segundo amigo encontrou uma pizzaria com nota 5/10 e o terceiro amigo encontrou uma pizzaria com nota 8/10...e assim por diante.
Dia 2: usamos a experiência acumulada.
Passo 1: "lembramos do passado" (Selection-I). Algoritmo: "Jogamos uma moeda!", se der cara, então "Vamos lembrar onde todos estavam ontem" (atualizamos o histórico), se der coroa, "Usamos lembranças antigas" (não atualizamos), depois "Embaralhamos as lembranças" (como um baralho de cartas).
Passo 2: "seguimos os rastros" (Mutation). Cada amigo pensa: "Onde eu estou agora? (posição atual) e onde eu estava antes?" (posição histórica). Então a fórmula do movimento será: Novo lugar = Lugar atual + Passo aleatório × (Lugar antigo - Lugar atual). Por exemplo: o primeiro amigo agora está na rua A., 10, o "fantasma do passado" dele estava na rua B., 20, passo aleatório = 2. Novo lugar = A.,10 + 2 × (B.,20 - A.,10) = movimento na direção da rua B, mas 2 vezes mais longe!
"Corrigimos a rota" (Crossover). O algoritmo joga uma moeda e escolhe uma estratégia. Estratégia A: "Alteração parcial". O primeiro amigo planejava ir para um determinado endereço, mas o algoritmo diz: "Mude apenas a rua, mantenha o número da casa como está". Resultado: certo, mudamos a rua e mantemos o número da casa. Estratégia B: "Alteração mínima". O primeiro amigo planejava ir para um determinado endereço, porém o algoritmo diz: "Permaneça no lugar antigo, mas mude apenas o número da casa". Resultado: certo, mudamos o número da casa.
"Verificamos o resultado geral" (Selection-II). O amigo 1 chegou a um novo lugar:
- Se a nova pizzaria for melhor (nota 9/10): "Excelente, fico aqui!"
- Se for pior (nota 4/10): "Não, vou voltar!"
Vamos observar a ilustração do funcionamento do algoritmo na figura abaixo.
Figura 1. Ilustração do funcionamento das fases do algoritmo BSA.
Esta ilustração mostra como o algoritmo BSA procura a solução ótima em um espaço bidimensional. Imagine que você está olhando um mapa topográfico de cima, em que o objetivo é encontrar o ponto mais alto (o centro vermelho).
A ilustração está dividida em três painéis que mostram a evolução da busca: Iteration 1 Random Initialization. Campo quadrado de busca com linhas de contorno, como em um mapa topográfico, ponto vermelho no centro que é o ótimo global (a melhor solução), 4 pontos azuis (P1, P2, P3, P4) que são as posições aleatórias iniciais dos "exploradores". O algoritmo posiciona aleatoriamente 4 agentes no espaço de busca, nesta etapa oldP = P (a população histórica copia a atual) e este é o ponto inicial da busca.
Iteration 2 - Mutation Step. Pontos azuis representam as posições atuais dos agentes, pontos verdes semitransparentes representam as posições da memória histórica (embaralhadas) e as setas vermelhas representam as direções de movimento durante a mutação.
Elementos principais: as setas vermelhas mostram a fórmula de mutação em funcionamento: M = P + F × (oldP - P). Cada agente se move em relação ao seu "par histórico". Algumas setas apontam em direção às posições históricas, outras apontam para longe delas, dependendo do sinal de F. A fórmula no quadro vermelho: F = 3 × randn(); M = P + F × (oldP - P). Esta é a fórmula principal de mutação do BSA.
Iteration 3 - After Crossover & Selection. Pontos roxos representam as novas posições após o crossover (Trial population), pontos azuis semitransparentes representam as posições anteriores, usados para comparação, e as setas verdes mostram apenas as melhorias, onde a nova posição é melhor que a anterior. O crossover combinou informações da população mutante e da população atual. A seleção gulosa manteve apenas os deslocamentos que melhoraram a solução. A população aproximou-se do ótimo, o centro vermelho.
BSA Process Summary, ciclo completo do algoritmo apresentado como uma sequência de círculos coloridos:- Init (azul) inicialização aleatória
- Select-I (verde) atualização da memória com probabilidade de 50%
- Mutate (vermelho) aplicação da fórmula de mutação
- Crossover (roxo) combinação das soluções
- Evaluate (laranja) cálculo da qualidade
- Select-II (turquesa) seleção gulosa das melhores soluções
A seta tracejada mostra que o processo se repete até a convergência. Esta ilustração demonstra claramente por que o BSA é eficiente: ele "lembra" onde esteve antes e usa essa informação para realizar uma busca mais inteligente do que uma simples caminhada aleatória.
Passamos agora à escrita do pseudocódigo do algoritmo BSA.
Preparação para o trabalho
Parâmetros iniciais:
- Definir o tamanho da população
- Definir o parâmetro de crossover mixrate
- Criar contêineres vazios para:
- população atual
- população histórica
- população mutante
- população de teste
- mapas de crossover para cada indivíduo
Inicialização:
- Posicionar todos os indivíduos da população histórica aleatoriamente no espaço de busca
- Considerar a discretização, se um passo estiver definido
- Definir o indicador "seleção necessária" como "não"
Ciclo principal do algoritmo
PASSO 1: Primeira execução
Se for a primeira iteração:
- Posicionar a população atual aleatoriamente
- Aplicar discretização às coordenadas
- Marcar que a inicialização foi concluída
- Encerrar e aguardar o cálculo da adaptabilidade
PASSO 2: Seleção gulosa (se necessário)
Se o indicador "seleção necessária" estiver ativado:
- Para cada indivíduo comparar:
- se a nova solução for pior que a armazenada, restaurar as coordenadas e a adaptabilidade anteriores
- se for melhor, manter a nova
- Redefinir o indicador de seleção
PASSO 3: Salvamento do estado atual
Para cada indivíduo:
- Registrar a adaptabilidade atual
- Salvar uma cópia das coordenadas atuais
PASSO 4: Atualização da memória histórica (Selection-I)
- Lançar uma moeda (probabilidade de 50%)
- Se o resultado for "cara":
- copiar toda a população atual para a memória histórica
- salvar suas adaptabilidades
- Embaralhar a população histórica como um baralho de cartas:
- percorrer do último indivíduo até o primeiro
- para cada um escolher uma posição aleatória para troca
- trocar as posições
PASSO 5: Mutação
- Gerar o fator de movimento F a partir de uma distribuição normal
- média = 0, limites de -3 a +3
- algo semelhante a lançar um dado, mas com distribuição em forma de sino
- Para cada indivíduo e para cada coordenada:
- Nova posição = Atual + F × (Histórica - Atual)
- se F for positivo, movimento em direção à posição histórica
- se F for negativo, movimento para longe da posição histórica
PASSO 6: Crossover
- Copiar a população mutante para a população de teste
- Lançar uma moeda ponderada (40% / 60%)
Se sair 40% (Estratégia 1):
Para cada indivíduo:
- determinar quantas coordenadas serão alteradas, de 0 até todas, usando mixrate
- escolher aleatoriamente quais coordenadas
- para as coordenadas selecionadas usar valores da população atual
- as demais permanecem da população mutante
Se sair 60% (Estratégia 2):
Para cada indivíduo:
- escolher apenas uma coordenada aleatória
- substituí-la pelo valor da população atual
- todas as outras permanecem da população mutante
PASSO 7: Controle de limites
Para cada indivíduo da população de teste:
- Verificar cada coordenada
- Se ultrapassar os limites:
- lançar uma moeda (50/50)
- se sair "cara", gerar um novo valor aleatório dentro dos limites
- se sair "coroa", colocar no limite mais próximo
- Aplicar discretização, se um passo estiver definido
PASSO 8: Preparação para avaliação
- Copiar a população de teste para a população principal para avaliação
- Definir o indicador "seleção necessária" como "sim"
- Transferir o controle para o cálculo da adaptabilidade
Após o cálculo da adaptabilidade
- Encontrar o indivíduo com a melhor adaptabilidade
- Se for melhor que o recorde global:
- atualizar o recorde global
- salvar as coordenadas da melhor solução
Repetição
Voltar ao PASSO 2 e continuar, até que:
- a convergência seja alcançada
- ou o limite de iterações seja esgotado
Agora que os pontos principais estão claros, vamos partir para a escrita do código do algoritmo. A classe "C_AO_BSA_Backtracking" vai representar a implementação do algoritmo de Busca com Retrocesso BSA para resolver problemas de otimização. Ela será herdeira da classe base "C_AO", que define a interface geral para algoritmos de otimização.
Principais características e finalidade:
Parâmetros de otimização:- popSize, tamanho da população, quantidade de "agentes" ou "soluções" que o algoritmo considera ao mesmo tempo.
- mixrate, parâmetro de crossover, controla o grau de "mistura" de informação entre os agentes ao criar novas soluções.
- O construtor da classe inicializa os parâmetros base e adiciona "popSize" e "mixrate" ao array "params", que é usado para gerenciar os parâmetros do algoritmo.
- O método "SetParams" permite atualizar os parâmetros internos do algoritmo com base nos valores obtidos do array "params". Ele também inclui verificações básicas de validade dos valores.
- Init, para a configuração inicial do algoritmo, incluindo a definição dos intervalos de variação das variáveis (valores mínimos, máximos e passos) e a quantidade de épocas de otimização.
- Moving, descreve a iteração principal do algoritmo, responsável por gerar novos "candidatos" ou soluções "móveis" com base na população atual.
- Revision, realiza a avaliação das soluções geradas e a atualização da população com base na qualidade delas.
- oldP, array que representa a população "histórica" ou anterior de agentes.
- M, array para a população obtida como resultado da mutação.
- T, array para a população de "teste", usada para comparação com a população atual antes da tomada de decisão.
- F, fator de amplitude da mutação, influencia o tamanho da mudança durante a mutação.
- needSelection, indicador que aponta a necessidade de executar a segunda etapa de seleção.
- prevFitness, array para armazenar os valores de fitness dos agentes da iteração anterior.
- S_Map, estrutura auxiliar que contém um mapa binário, usada no processo de crossover para definir quais variáveis do agente serão "misturadas" a partir de diferentes pais.
- map, array desses mapas binários, um para cada agente.
- SelectionI, primeira etapa de seleção, responsável por escolher os agentes para criar novas soluções.
- Mutation, aplica a operação de mutação aos agentes selecionados.
- Crossover, executa a operação de crossover (mistura) entre os agentes para criar novas soluções de "teste".
- BoundaryControl, verifica se os valores dos parâmetros do agente permanecem dentro dos limites definidos (mínimos e máximos).
- ShufflePopulation, método para embaralhamento aleatório da população.
Assim, a classe "C_AO_BSA_Backtracking" implementa um algoritmo evolutivo de otimização que usa os conceitos de população, mutação e crossover, além de mecanismos específicos do BSA, como a busca com retrocesso, para resolver tarefas de otimização.
//———————————————————————————————————————————————————————————————————— class C_AO_BSA_Backtracking : public C_AO { public: //---------------------------------------------------------- ~C_AO_BSA_Backtracking () { } C_AO_BSA_Backtracking () { ao_name = "BSA"; ao_desc = "Backtracking Search Algorithm"; ao_link = "https://www.mql5.com/ru/articles/18568"; popSize = 10; // размер популяции mixrate = 1.0; // параметр кроссовера ArrayResize (params, 2); params [0].name = "popSize"; params [0].val = popSize; params [1].name = "mixrate"; params [1].val = mixrate; } void SetParams () { popSize = (int)params [0].val; mixrate = params [1].val; // Проверка корректности параметров //if (popSize < 2) popSize = 2; if (mixrate < 0.0) mixrate = 0.0; if (mixrate > 1.0) mixrate = 1.0; } bool Init (const double &rangeMinP [], // минимальные значения const double &rangeMaxP [], // максимальные значения const double &rangeStepP [], // шаг изменения const int epochsP = 0); // количество эпох void Moving (); void Revision (); //------------------------------------------------------------------ double mixrate; // параметр кроссовера private: //--------------------------------------------------------- S_AO_Agent oldP []; // историческая популяция S_AO_Agent M []; // мутантная популяция (Mutant) S_AO_Agent T []; // пробная популяция (Trial) double F; // фактор амплитуды для мутации bool needSelection; // флаг необходимости выполнения Selection-II double prevFitness []; // массив для хранения предыдущих fitness // Вспомогательные структуры для кроссовера struct S_Map { int val []; // бинарная карта для кроссовера void Init (int size) { ArrayResize (val, size); ArrayInitialize (val, 0); } }; S_Map map []; // массив бинарных карт для каждого агента // Методы алгоритма void SelectionI (); void Mutation (); void Crossover (); void BoundaryControl (S_AO_Agent &agent); void ShufflePopulation (S_AO_Agent &pop []); }; //————————————————————————————————————————————————————————————————————
O método "Init" é responsável por preparar o algoritmo para funcionamento antes do início da otimização. Primeiramente, é chamada a função base de inicialização, que define os parâmetros principais relacionados aos intervalos de valores das variáveis, valores mínimos, máximos e passo de alteração. Se essa etapa básica não for concluída com sucesso, o método é interrompido e retorna falha.
Em seguida ocorre a alocação e preparação das estruturas internas de dados específicas do algoritmo BSA. Em particular, são criados e ajustados ao tamanho necessário os arrays das populações: a população histórica "oldP", a população mutante "M", a população de teste "T", bem como o array de mapas binários para crossover "map" e o array para armazenamento dos valores anteriores de fitness de cada agente "prevFitness". O indicador de necessidade de seleção adicional é inicialmente definido como falso.
Depois disso, para cada agente na população são chamados os métodos de inicialização que preparam as estruturas internas de cada agente de acordo com a quantidade de parâmetros do problema.
Em seguida ocorre o preenchimento da população histórica com valores iniciais. Para cada agente e para cada parâmetro em seu conjunto é gerado um valor aleatório dentro do intervalo definido, após o que esse valor é ajustado conforme o passo de alteração especificado. Após a execução bem-sucedida de todas essas etapas, o método retorna um valor que indica a inicialização bem-sucedida do objeto do algoritmo e a prontidão para a execução posterior da otimização.
//———————————————————————————————————————————————————————————————————— //--- Инициализация bool C_AO_BSA_Backtracking::Init (const double &rangeMinP [], const double &rangeMaxP [], const double &rangeStepP [], const int epochsP = 0) { if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; //------------------------------------------------------------------ // Инициализация дополнительных структур BSA ArrayResize (oldP, popSize); ArrayResize (M, popSize); ArrayResize (T, popSize); ArrayResize (map, popSize); ArrayResize (prevFitness, popSize); needSelection = false; for (int i = 0; i < popSize; i++) { oldP [i].Init (coords); M [i].Init (coords); T [i].Init (coords); map [i].Init (coords); } // Инициализация исторической популяции oldP for (int p = 0; p < popSize; p++) { for (int c = 0; c < coords; c++) { oldP [p].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); oldP [p].c [c] = u.SeInDiSp (oldP [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } return true; } //————————————————————————————————————————————————————————————————————
O método "Moving" descreve o passo principal do algoritmo de otimização BSA e é responsável pela geração de novos candidatos de solução na população. Na primeira chamada do método, quando o indicador "revision" é falso, ocorre o preenchimento inicial da população ativa "a". Para cada agente na população e para cada um de seus parâmetros é gerado um valor aleatório dentro do intervalo definido, mínimo e máximo. Em seguida esse valor aleatório é ajustado conforme o passo definido de alteração do parâmetro. Após a inicialização o indicador "revision" é definido como verdadeiro, para que esse bloco não seja executado nas chamadas seguintes, e o indicador "needSelection" é redefinido. O método é encerrado.
Execução da seleção gulosa (Selection-II) (executada se necessário): se o indicador "needSelection" for verdadeiro, isso significa que no passo anterior foi gerada uma nova população e agora é necessário comparar seu fitness com o fitness das soluções anteriores. É realizada uma iteração sobre cada agente na população. O valor atual de fitness do agente "a [i].f", que foi calculado para a solução de teste, é comparado com seu fitness do passo anterior armazenado em "prevFitness [i]". Se a solução de teste "a [i]" for pior que a anterior, então os valores das coordenadas do agente atual "a [i].c" são restaurados a partir de "a [i].cP", que são as coordenadas do agente no passo anterior, e seu fitness "a [i].f" também é restaurado para "prevFitness [i]". Isso garante que a população não se deteriore. Após a execução da seleção, o indicador "needSelection" é redefinido.
Passos principais do algoritmo BSA (após a inicialização ou seleção): antes da geração de novas soluções, os valores atuais de fitness de todos os agentes de "a" são salvos em "prevFitness" para uso posterior em "Selection-II" e as coordenadas atuais dos agentes de "a [i].c" são copiadas para "a [i].cP", para permitir reversão caso as novas soluções sejam piores.
É chamado o método interno "SelectionI". Este passo é responsável por escolher ou preparar a população "arquivada" "oldP", que será utilizada na mutação. Em seguida é chamado o método interno "Mutation". Neste passo é gerada a população "mutante" "M" com base na população ativa e ou na população arquivada. Depois é chamado o método interno "Crossover". Neste passo ocorre a mistura da população mutante "M" com a população ativa atual "a", formando como resultado a população de "teste" "T".
As coordenadas dos agentes da população de teste gerada "T" são copiadas para a população ativa "a". Agora "a" contém novas soluções de "teste", cujo fitness ainda precisa ser calculado. O indicador "needSelection" é definido como "true". Isso sinaliza que na próxima chamada de "Moving", após o cálculo do fitness das novas soluções em "a", deve ser executada a seleção gulosa (Selection-II).
Assim, o método "Moving" encapsula uma iteração completa ou "época" do algoritmo BSA, incluindo inicialização, seleção, mutação, crossover e preparação para comparação dos resultados.
//———————————————————————————————————————————————————————————————————— //--- Основной шаг алгоритма void C_AO_BSA_Backtracking::Moving () { // Начальная инициализация популяции if (!revision) { for (int p = 0; p < popSize; p++) { for (int c = 0; c < coords; c++) { a [p].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]); a [p].c [c] = u.SeInDiSp (a [p].c [c], rangeMin [c], rangeMax [c], rangeStep [c]); } } revision = true; needSelection = false; return; } // Если нужно выполнить жадный отбор после вычисления fitness if (needSelection) { // Selection-II: Жадный отбор for (int i = 0; i < popSize; i++) { // Если текущее решение (из T) хуже предыдущего, возвращаем предыдущее if (a [i].f < prevFitness [i]) { ArrayCopy (a [i].c, a [i].cP, 0, 0, WHOLE_ARRAY); a [i].f = prevFitness [i]; } } needSelection = false; } //--- Основные шаги BSA: // Сохраняем текущие fitness перед генерацией новой популяции for (int i = 0; i < popSize; i++) { prevFitness [i] = a [i].f; ArrayCopy (a [i].cP, a [i].c, 0, 0, WHOLE_ARRAY); } // 1. Selection-I SelectionI (); // 2. Mutation Mutation (); // 3. Crossover Crossover (); // 4. Копируем пробную популяцию T в основную популяцию a для вычисления fitness for (int i = 0; i < popSize; i++) { ArrayCopy (a [i].c, T [i].c, 0, 0, WHOLE_ARRAY); } // Устанавливаем флаг для выполнения Selection-II после вычисления fitness needSelection = true; } //————————————————————————————————————————————————————————————————————
O método "SelectionI" implementa a primeira etapa de seleção no algoritmo BSA e é responsável pela escolha da população histórica que posteriormente será usada na mutação.
Atualização probabilística da população histórica: com probabilidade de 50%, ou de forma simples, com probabilidade igual, a população histórica "oldP" é atualizada pela população atual "a". Se for gerado um número aleatório menor que o limite definido (0.5), então ocorre a cópia do conteúdo ("c", coordenadas) de cada agente da população atual "a" para o agente correspondente na população histórica "oldP", e também é copiado o fitness "f" do agente.
Embaralhamento da população histórica: independentemente de a população histórica ter sido atualizada no passo anterior ou não, o método "ShufflePopulation (oldP)" é chamado para embaralhar os agentes na população histórica. Isso é feito para introduzir aleatoriedade no processo de mutação. O embaralhamento garante que os agentes da população histórica sejam selecionados em ordem aleatória, e não na ordem em que estavam originalmente posicionados.
Assim, "SelectionI" ou atualiza a população de arquivo com os candidatos atuais de solução, ou mantém seu estado anterior e, em qualquer caso, embaralha os agentes na população de arquivo, o que permite diversificar a busca na mutação posterior.
//———————————————————————————————————————————————————————————————————— //--- Selection-I: выбор исторической популяции void C_AO_BSA_Backtracking::SelectionI () { // С вероятностью 50% обновляем историческую популяцию if (u.RNDprobab () < 0.5) // эквивалент if (a < b) где a,b ~ U(0,1) { // Копируем текущую популяцию в историческую for (int i = 0; i < popSize; i++) { ArrayCopy (oldP [i].c, a [i].c, 0, 0, WHOLE_ARRAY); oldP [i].f = a [i].f; } } // Перемешиваем историческую популяцию ShufflePopulation (oldP); } //————————————————————————————————————————————————————————————————————
O método "ShufflePopulation" é destinado ao embaralhamento aleatório dos elementos em uma determinada população de agentes, representados pela estrutura "S_AO_Agent". Ele recebe como entrada um array de agentes "pop []" e executa o embaralhamento no próprio array, isto é, altera a ordem dos elementos diretamente no array recebido.
Algoritmo de embaralhamento: o método utiliza o algoritmo de embaralhamento Fisher-Yates (Fisher-Yates shuffle) para misturar aleatoriamente os elementos da população. O algoritmo garante que cada permutação, isto é, cada ordem possível dos elementos, tenha a mesma probabilidade.
O laço "for" começa a partir do último elemento do array (popSize - 1) e segue em ordem inversa até o segundo elemento (índice 1). O primeiro elemento (índice 0) não precisa ser embaralhado, pois até esse momento ele já terá sido "movido" durante a execução do algoritmo. Para cada elemento com índice "i" é escolhido um índice aleatório "j" no intervalo de "0" até "i", inclusive. Isso é feito usando a função "u.RNDminusOne (i + 1)", que retorna um número inteiro aleatório no intervalo especificado, incluindo "0" e excluindo "i + 1".
Os elementos com índices "i" e "j" trocam de posição. Para isso é usada uma variável temporária "temp" do tipo "S_AO_Agent". Como "S_AO_Agent" contém o array "c" (coordenadas), é realizada a cópia desse array. Também é copiado o valor de fitness "f". Os valores das coordenadas e do fitness do elemento "pop [i]" são armazenados na variável temporária "temp", depois os valores das coordenadas e do fitness do elemento "pop [j]" são copiados para "pop [i]". Em seguida, os valores salvos em "temp", que correspondem ao valor original de "pop [i]", são copiados para "pop [j]". Como resultado, após a conclusão do laço, a ordem dos elementos no array "pop []" será aleatória.
//———————————————————————————————————————————————————————————————————— //--- Перемешивание популяции void C_AO_BSA_Backtracking::ShufflePopulation (S_AO_Agent &pop []) { for (int i = popSize - 1; i > 0; i--) { int j = u.RNDminusOne (i + 1); // Обмен местами элементов i и j S_AO_Agent temp; temp.Init (coords); ArrayCopy (temp.c, pop [i].c, 0, 0, WHOLE_ARRAY); temp.f = pop [i].f; ArrayCopy (pop [i].c, pop [j].c, 0, 0, WHOLE_ARRAY); pop [i].f = pop [j].f; ArrayCopy (pop [j].c, temp.c, 0, 0, WHOLE_ARRAY); pop [j].f = temp.f; } } //————————————————————————————————————————————————————————————————————
O método "Mutation" é responsável por gerar a população mutante, que é uma etapa essencial no algoritmo BSA. Ele se baseia na diferença entre a população atual e a população histórica.
Primeiro é gerado um fator de amplitude aleatório "F", que determina a intensidade da influência da população histórica sobre a população atual. Depois, para cada agente da população e para cada coordenada dentro desse agente, é calculado um novo valor de coordenada na população mutante. Isso é feito adicionando à coordenada atual o produto do fator de amplitude "F" pela diferença entre a coordenada correspondente na população histórica e a coordenada atual. Dessa forma, a população mutante é criada deslocando a população atual na direção determinada pela população histórica, com uma amplitude dependente do fator "F".
//———————————————————————————————————————————————————————————————————— //--- Mutation: генерация мутантной популяции void C_AO_BSA_Backtracking::Mutation () { // Генерируем фактор амплитуды F = u.GaussDistribution (0.0, -3.0, 3.0, 2); // Применяем мутацию: M = P + F * (oldP - P) for (int i = 0; i < popSize; i++) { for (int j = 0; j < coords; j++) { M [i].c [j] = a [i].c [j] + F * (oldP [i].c [j] - a [i].c [j]); } } } //————————————————————————————————————————————————————————————————————
O método "Crossover" é responsável pela formação da população de teste com base na população mutante atual, utilizando a estratégia de crossover escolhida. Esse processo é voltado para a combinação das características das soluções herdadas com o objetivo de encontrar variantes mais otimizadas.
Inicialmente, a população de teste é copiada da população mutante, para servir como base para modificações posteriores. Em seguida ocorre a escolha da estratégia de crossover: com probabilidade de 40% é usada a primeira estratégia, caso contrário é usada a segunda.
Se a primeira opção for escolhida, aplica-se a estratégia chamada "mixrate". Nesse caso, para cada agente é determinado o número de elementos, dentro das coordenadas, que serão retirados do agente atual, levando em consideração o coeficiente definido "mixrate". Esses elementos são escolhidos aleatoriamente, sem repetição. Depois disso, para os índices selecionados, as coordenadas correspondentes do agente da população de teste são copiadas da solução atual.
Se a segunda estratégia for escolhida, então para cada agente é selecionado um elemento aleatório, isto é, uma coordenada, e na população de teste ocorre a substituição desse elemento na posição correspondente pelo seu valor proveniente da solução atual.
Após a conclusão do crossover, é realizado o controle de limites para cada agente da população de teste, para garantir que todas as soluções sejam válidas e estejam de acordo com os requisitos dos intervalos de valores.
//———————————————————————————————————————————————————————————————————— //--- Crossover: генерация пробной популяции void C_AO_BSA_Backtracking::Crossover () { // Инициализируем пробную популяцию как копию мутантной for (int i = 0; i < popSize; i++) { ArrayCopy (T [i].c, M [i].c, 0, 0, WHOLE_ARRAY); } // Выбираем стратегию кроссовера if (u.RNDprobab () < 0.4) { //--- СТРАТЕГИЯ 1: Использование mixrate for (int i = 0; i < popSize; i++) { // Сброс карты ArrayInitialize (map [i].val, 0); // Определяем количество элементов для кроссовера int numElements = (int)MathCeil (mixrate * u.RNDprobab () * coords); // Генерируем уникальные индексы для кроссовера for (int n = 0; n < numElements; n++) { int idx; do { idx = u.RNDminusOne (coords); } while (map [i].val [idx] == 1); // пока не найдем неиспользованный индекс map [i].val [idx] = 1; } // Применяем кроссовер for (int j = 0; j < coords; j++) { if (map [i].val [j] == 1) { T [i].c [j] = a [i].c [j]; } } } } else { //--- СТРАТЕГИЯ 2: Мутация только одного элемента for (int i = 0; i < popSize; i++) { // Выбираем один случайный элемент int randomIndex = u.RNDminusOne (coords); T [i].c [randomIndex] = a [i].c [randomIndex]; } } // Контроль границ для всех агентов пробной популяции for (int i = 0; i < popSize; i++) { BoundaryControl (T [i]); } } //————————————————————————————————————————————————————————————————————
O método "BoundaryControl" é destinado à verificação e correção dos valores das soluções do agente, para que permaneçam dentro dos limites permitidos, além de ajustar as soluções ao formato discreto necessário.
Para cada elemento das coordenadas do agente é feita uma verificação: se o valor ultrapassar os limites mínimos ou máximos definidos, então esse desvio é tratado de acordo com a estratégia escolhida. Caso a probabilidade selecionada aleatoriamente seja menor que 50%, ocorre uma regeneração aleatória do valor dentro do intervalo permitido. Caso contrário, o valor é definido no limite mais próximo, seja o mínimo ou o máximo.
Depois disso, cada valor de coordenada passa por discretização, isto é, é convertido para o valor válido mais próximo que corresponde ao intervalo definido e ao passo de discretização. Isso garante que a solução esteja de acordo com os requisitos de tipo de dado e de intervalo de valores.
//———————————————————————————————————————————————————————————————————— //--- Контроль границ void C_AO_BSA_Backtracking::BoundaryControl (S_AO_Agent &agent) { for (int j = 0; j < coords; j++) { if (agent.c [j] < rangeMin [j] || agent.c [j] > rangeMax [j]) { // Выбор стратегии обработки границ if (u.RNDprobab () < 0.5) { // Случайная регенерация agent.c [j] = u.RNDfromCI (rangeMin [j], rangeMax [j]); } else { // Установка на границу if (agent.c [j] < rangeMin [j]) agent.c [j] = rangeMin [j]; else agent.c [j] = rangeMax [j]; } } // Дискретизация agent.c [j] = u.SeInDiSp (agent.c [j], rangeMin [j], rangeMax [j], rangeStep [j]); } } //————————————————————————————————————————————————————————————————————
O método "Revision" é responsável pela seleção e atualização da melhor solução encontrada na população atual. Percorrendo todas as soluções, ele procura aquela cujo valor da função de avaliação, o fitness, seja o máximo. Se tal solução for encontrada, ela é armazenada como o melhor resultado atual, e suas coordenadas são copiadas para um array separado destinado ao armazenamento da melhor solução no momento. Dessa forma, esse método garante o acompanhamento constante e a atualização da solução ótima encontrada ao longo das iterações do algoritmo.
//———————————————————————————————————————————————————————————————————— //--- Selection-II и обновление лучшего решения void C_AO_BSA_Backtracking::Revision () { int bestIND = -1; for (int i = 0; i < popSize; i++) { // Обновляем глобальное лучшее решение if (a [i].f > fB) { fB = a [i].f; bestIND = i; } } // Копируем координаты лучшего решения if (bestIND != -1) { ArrayCopy (cB, a [bestIND].c, 0, 0, WHOLE_ARRAY); } } //————————————————————————————————————————————————————————————————————
O método "GaussDistribution" gera um número aleatório com distribuição Gaussiana, isto é, normal, centrada em torno de um valor de entrada definido e limitada por um intervalo específico, utilizando o método de Box-Muller para obter variáveis aleatórias com distribuição normal.
Primeiro ele gera duas variáveis aleatórias com distribuição uniforme. Em seguida, com base nessas variáveis, é calculada uma variável aleatória com distribuição normal padrão, que pode ser utilizada para obter uma distribuição Gaussiana.
Depois disso, o método verifica se o valor gerado está dentro do intervalo definido de desvios, determinado pelo parâmetro sigma. Se o valor gerado estiver fora desses limites, o método é chamado recursivamente novamente para gerar um novo valor, até que ele se encontre dentro do intervalo permitido.
Por fim, o desvio gerado com distribuição normal é escalado de forma que corresponda ao intervalo de saída definido, de "outMin" até "outMax", em relação ao valor de entrada "In". Isso permite deslocar e escalar a distribuição para que ela corresponda aos parâmetros desejados. O resultado é um número com distribuição Gaussiana, centrado em "In", mas considerando as restrições de valor mínimo e máximo de saída.
//—————————————————————————————————————————————————————————————————————————————— double C_AO_Utilities :: GaussDistribution (const double In, const double outMin, const double outMax, const double sigma) { double logN = 0.0; double u1 = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0); double u2 = 2.0 * MathRand () / 32767.0 - 1.0;//RNDfromCI (0.0, 1.0); logN = u1 <= 0.0 ? 0.000000000000001 : u1; double z0 = sqrt (-2 * log (logN)) * cos (2 * M_PI * u2); double sigmaN = sigma > 8.583864105157389 ? 8.583864105157389 : sigma; // Если z0 выходит за пределы [-sigmaN, sigmaN], генерируем заново if (z0 >= sigmaN || z0 <= -sigmaN) { return GaussDistribution(In, outMin, outMax, sigma); // Рекурсивный вызов } if (z0 >= 0.0) z0 = Scale (z0, 0.0, sigmaN, 0.0, outMax - In, false); else z0 = -Scale (fabs (z0), 0.0, sigmaN, 0.0, In - outMin, false); return In + z0; } //——————————————————————————————————————————————————————————————————————————————
Resultados dos testes
Os resultados do funcionamento do algoritmo BSA são muito bons.
=============================
5 Hilly's; Func runs: 10000; result: 0.9730917210619289
25 Hilly's; Func runs: 10000; result: 0.5453406317593932
500 Hilly's; Func runs: 10000; result: 0.2909827609772065
=============================
5 Forest's; Func runs: 10000; result: 0.9999986842258451
25 Forest's; Func runs: 10000; result: 0.5854340780208712
500 Forest's; Func runs: 10000; result: 0.21747482800959225
=============================
5 Megacity's; Func runs: 10000; result: 0.8476923076923077
25 Megacity's; Func runs: 10000; result: 0.3695384615384615
500 Megacity's; Func runs: 10000; result: 0.12978461538461658
=============================
All score: 4.95934 (55.10%)
Na visualização do funcionamento do algoritmo BSA é possível observar uma dispersão dos valores nos resultados em funções de baixa e média dimensionalidade, no entanto, com o aumento do tamanho da população nos parâmetros, essa dispersão diminui. Para uma convergência melhor, é necessário aumentar o número de iterações.
BSA na função de teste Hilly
BSA na função de teste Forest
BSA na função de teste Megacity
O algoritmo BSA ocupa a 20ª posição na tabela classificatória dos algoritmos populacionais de otimizaçã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 | 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 |
| 13 | 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 |
| 14 | 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 |
| 15 | 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 |
| 16 | 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 |
| 17 | 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 |
| 18 | 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 |
| 19 | 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 |
| 20 | 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 |
| 21 | 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 |
| 22 | 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 |
| 23 | 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 |
| 24 | 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 |
| 25 | 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 |
| 26 | 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 |
| 27 | 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 |
| 28 | 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 |
| 29 | 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 |
| 30 | 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 |
| 31 | (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 |
| 32 | 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 |
| 33 | 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 |
| 34 | 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 |
| 35 | 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 |
| 36 | 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 |
| 37 | 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 |
| 38 | 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 |
| 39 | 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 |
| 40 | 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 |
| 41 | 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 |
| 42 | 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 |
| 43 | 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 |
| 44 | 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 |
| 45 | 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 |
| 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 | |
Considerações finais
O BSA representa um compromisso entre simplicidade de implementação e eficiência de busca, ocupando uma posição estável na metade da tabela classificatória dos algoritmos populacionais de otimização. Sua principal vantagem, uma interessante concepção de memória histórica, permite que o algoritmo evite convergência prematura sem complicar o esquema computacional. Diferentemente de muitas metaheurísticas modernas, sobrecarregadas com parâmetros e operadores complexos, o BSA utiliza um conjunto mínimo de configurações, o que o torna uma escolha atraente para profissionais que não desejam gastar tempo com ajustes finos de parâmetros externos.
O único parâmetro realmente significativo, "mixrate", é intuitivamente compreensível e não exige entendimento profundo da mecânica interna do algoritmo. Ao mesmo tempo, o BSA demonstra desempenho estável em uma ampla classe de problemas, desde funções unimodais simples até paisagens complexas multimodais com numerosos ótimos locais. O algoritmo não pretende ser campeão em velocidade de convergência ou precisão de solução, mas sua confiabilidade e previsibilidade o tornam um verdadeiro cavalo de batalha. É particularmente valioso que, com o aumento da população, o BSA apresenta baixa suscetibilidade à estagnação. O mecanismo de atualização aleatória da população histórica garante um fluxo constante de diversidade mesmo nas fases finais da busca.
Sua posição intermediária no ranking não é sinal de mediocridade, mas sim evidência de universalidade e praticidade, pois nem sempre para resolver problemas reais é necessário o instrumento mais complexo e moderno. Às vezes basta um algoritmo confiável, com lógica de funcionamento clara, que produza bons resultados sem necessidade de configuração especializada, e o BSA preenche com sucesso esse espaço.
Figura 2. Graduação de cores dos algoritmos nos testes correspondentes
Figura 3. Histograma dos resultados dos testes dos algoritmos (na escala de 0 a 100, quanto maior, melhor, onde 100 — resultado teórico máximo possível, no arquivo há o script para cálculo da tabela classificatória)
Vantagens e desvantagens do algoritmo BSA:
Vantagens:
- Boa convergência nas funções.
- Além do tamanho da população, apenas um parâmetro externo adicional.
Desvantagens:
- Existe certa tendência de ficar preso em problemas de baixa dimensionalidade quando a população é pequena.
Um arquivo compactado com as versões atualizadas dos códigos dos algoritmos está anexado ao artigo. O autor do artigo não se responsabiliza pela precisão absoluta na descrição dos algoritmos canônicos, pois muitos deles foram modificados 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 de inclusão | Classe base dos algoritmos populacionais de otimização |
| 2 | #C_AO_enum.mqh | Arquivo de inclusão | Enumeração dos algoritmos populacionais de otimização |
| 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 cálculo dos resultados na tabela comparativa |
| 7 | Testing AOs.mq5 | Script | Ambiente 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_AO_BSA.mq5 | Script | Ambiente de testes para BSA |
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/18568
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 em trading: Segmentação periódica adaptativa (Criação de tokens)
Redes neurais em trading: Segmentação periódica adaptativa (LightGTS)
Operando com o Calendário Econômico do MQL5 (Parte 6): Automatizando a Entrada de Trades com Análise de Eventos de Notícias e Temporizadores de Contagem Regressiva
A análise de lacunas temporais de preço em MQL5 (Parte I): Criando um indicador básico
- 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