Algoritmo de Otimização Aritmética (AOA): O caminho do AOA até o SOA (Simple Optimization Algorithm)

Conteúdo

1. Introdução
2. Implementação do algoritmo
3. Resultados dos testes

Introdução

O Algoritmo de Otimização Aritmética (Arithmetic Optimization Algorithm, AOA) é um método original baseado em operações aritméticas simples, como adição, subtração, multiplicação e divisão. Ele busca soluções ótimas em uma variedade de problemas por meio do uso desses princípios matemáticos básicos. Desenvolvido por uma equipe de pesquisadores, incluindo Laith Abualigah, o AOA foi apresentado pela primeira vez em 2021. Esse algoritmo pertence à classe dos métodos metaheurísticos (algoritmos de alto nível), que visam buscar, gerar e selecionar probabilisticamente entre várias heurísticas capazes de fornecer soluções suficientemente boas em tempo razoável para problemas complexos de otimização, nos quais métodos exatos podem ser ineficazes ou inviáveis.

O que me atraiu nesse método foi a ideia simples e, ao mesmo tempo, elegante de aplicar operadores aritméticos absolutamente elementares. A conexão entre essas ações matemáticas básicas e os enfoques metaheurísticos cria uma interação que permite resolver problemas complexos de otimização. Os métodos metaheurísticos aplicados no AOA incluem alguns princípios-chave:

1. Abordagem populacional. O AOA utiliza uma população de soluções, o que permite cobrir de forma mais ampla o espaço de soluções possíveis. Isso ajuda a evitar ótimos locais e amplia os horizontes da busca.

2. Aleatoriedade e estocasticidade. A inclusão de elementos aleatórios no processo de busca ajuda os algoritmos a não ficarem presos em ótimos locais e garante uma exploração mais completa do espaço de soluções, o que aumenta a chance de encontrar o ótimo global.

3. Equilíbrio entre diversificação e intensificação. Assim como muitos outros algoritmos metaheurísticos, o AOA busca um equilíbrio entre explorar novas áreas do espaço de soluções e intensificar a busca nas soluções já conhecidas como eficazes. Isso é feito através da aplicação de operações aritméticas para atualizar as posições das soluções.

Assim, o AOA é um exemplo marcante de algoritmo metaheurístico que utiliza de forma eficaz os princípios da abordagem populacional, da aleatoriedade e do equilíbrio entre diversificação e intensificação para resolver problemas de otimização. No entanto, sua eficácia específica em encontrar soluções ótimas em espaços complexos e multidimensionais será discutida após sua implementação e testes.

Implementação do algoritmo

A ideia principal do AOA está no uso do comportamento distributivo dos operadores aritméticos para buscar soluções ótimas. O algoritmo se caracteriza por princípios simples, poucos parâmetros e fácil implementação. Ele utiliza as propriedades distributivas dos quatro operadores aritméticos básicos da matemática, a saber: Multiplicação (Mε × ε), Divisão (Dε ÷ ε), Subtração (Sε − ε) e Adição (Aε + ε). No AOA, a população inicial é gerada aleatoriamente no intervalo [U; L], onde U e L representam, respectivamente, os limites superior e inferior do espaço de busca da função objetivo, utilizando a seguinte equação:

x = L + (U − L) × δ, onde x representa uma solução da população e δ é uma variável aleatória com valores entre [0, 1].

A cada iteração, a escolha da estratégia de diversificação ou intensificação, ou seja, a escolha entre os dois grupos de operadores, (divisão; multiplicação) ou (subtração; adição), depende do resultado da função MoA (math optimizer accelerated), que é, na essência, um valor probabilístico calculado e que varia a cada iteração, sendo computado pela equação:

MoA(t) = Min + t × (Max − Min) ÷ Maxt, onde MoA(t) representa o resultado funcional na iteração t, t indica a iteração atual dentro do intervalo de 1 até o número máximo de iterações (Maxt). O valor mínimo possível de MoA é representado por Min, e o valor máximo por Max, ambos sendo parâmetros externos do algoritmo.

Nas quatro fórmulas que envolvem operadores aritméticos, é utilizado o coeficiente MoP (math optimizer), calculado da seguinte forma:

MoP(t) = 1 − (t ÷ Maxt)^(1 ÷ θ), onde MoP(t) representa o valor da função MoP na iteração t. θ é um parâmetro crítico que controla a eficácia da intensificação ao longo das iterações. No trabalho original dos autores do algoritmo, esse valor foi definido como 5.

A figura 1 abaixo apresenta os gráficos da dependência de MoA e MoP em relação à iteração atual. Os gráficos mostram que, a cada iteração, o MoA cresce linearmente, o que significa um aumento na probabilidade de escolha do grupo de operadores (subtração; adição), enquanto a probabilidade de escolha do grupo de operadores (divisão; multiplicação) diminui proporcionalmente. Em contrapartida, o coeficiente MoP diminui de forma não linear, reduzindo assim o incremento aplicado à posição atual dos agentes na população, o que indica um maior grau de refinamento das soluções durante o processo de otimização.

Figura 1. O gráfico roxo representa a probabilidade MoA, enquanto o gráfico verde representa o coeficiente MoP

Diversificação ou busca global no AOA é realizada com o uso de estratégias baseadas nos operadores de Divisão (D) e Multiplicação (M), quando a probabilidade MoA é atendida, formulada da seguinte maneira, onde os seguintes operadores são executados com igual probabilidade:

xi,j(t+1) = best(xj) ÷ (MoPr + 𝜖) × ((Uj − Lj) × 𝜇 + Lj), se rand2 < 0.5; 

caso contrário:

xi,j(t+1) = best(xj) × (MoPr) × ((Uj − Lj) × 𝜇 + Lj), onde xi(t+1) representa a i-ésima solução na iteração (t+1), x(i,j)(t) representa a j-ésima posição do i-ésimo indivíduo na geração atual, best(xj) representa a j-ésima posição da melhor solução encontrada até o momento, ε é um pequeno número positivo, e os limites superior e inferior dos valores da j-ésima posição são representados como Uj e Lj, respectivamente. O parâmetro de controle μ foi definido no nível de 0.5. 

Se a probabilidade MoA não for atendida, então o AOA executa a estratégia de intensificação (refinamento da solução), que foi desenvolvida usando os operadores de Subtração (S) ou Adição (A). Aqui, μ também é uma constante, fixada no nível de 0.5 conforme o projeto dos autores. 

xi,j(t+1) = best(xj) − (MoPr) × ((Uj − Lj) × 𝜇 + Lj), se rand3 < 0.5

xi,j(t+1) = best(xj) + (MoPr) × ((Uj − Lj) × 𝜇 + Lj), caso contrário.

No AOA, os parâmetros 𝜇 e θ são extremamente importantes, pois participam do equilíbrio entre diversificação e intensificação. Manter esse equilíbrio é, geralmente, uma tarefa bastante desafiadora. No trabalho original do AOA, o valor de 𝜇 foi fixado em 0.5 tanto para diversificação quanto para intensificação. Já o parâmetro θ, que influencia a eficácia da intensificação ao longo das iterações, foi definido como 5. Os autores realizaram experimentos com diferentes valores de 𝜇 e θ e descobriram que 𝜇 = 0.5 e θ = 5 forneceram, com mais frequência, os melhores resultados para funções de teste unimodais e multimodais em diversas dimensionalidades. 

Agora, vamos escrever o pseudocódigo do algoritmo AOA:

Agora passamos à implementação do código. A classe "C_AO_AOA" representa a implementação do algoritmo AOA e é destinada à resolução de tarefas de otimização utilizando o método baseado em operações aritméticas. Métodos públicos:

1. O método "SetParams ()" define os valores dos parâmetros a partir do array "params". Esse método permite alterar os parâmetros do algoritmo após sua inicialização.

2. O método "Init ()":

• Inicializa o algoritmo, recebendo como entrada os limites mínimo e máximo da busca, o passo da busca e a quantidade de épocas. 
• Retorna "true", se a inicialização foi bem-sucedida, caso contrário retorna "false".

3. O método "Moving ()" — realiza o deslocamento das partículas no espaço de soluções. Esse método implementa a lógica de atualização das posições das partículas com base nos parâmetros definidos e no estado atual.

4. O método "Revision()" — realiza a revisão das posições atuais das partículas, atualizando o melhor valor encontrado da função e as coordenadas da partícula correspondente.

Campos privados, parâmetros da classe:

• minT — valor mínimo da probabilidade MoA.
• maxT — valor máximo da probabilidade MoA.
• θ — parâmetro que influencia o equilíbrio entre diversificação e intensificação.
• μ — parâmetro utilizado para controlar as mudanças nas posições das partículas (amplitude de deslocamento).
• ϵ — número pequeno para evitar divisão por zero.

Informações sobre o estado do algoritmo:

• epochs — quantidade total de épocas pelas quais o algoritmo irá passar.
• epochNow — época atual, usada para acompanhar o progresso do algoritmo, influencia a probabilidade MoA e o coeficiente MoP.

A classe "C_AO_AOA" implementa os principais componentes do algoritmo AOA, incluindo a inicialização, o deslocamento das partículas e a revisão.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_AOA : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_AOA () { }
  C_AO_AOA ()
  {
    ao_name = "AOA";
    ao_desc = "Arithmetic Optimization Algorithm";
    ao_link = "https://www.mql5.com/ru/articles/16364";

    popSize = 50;   // Размер популяции
    minT    = 0.1;  // Минимальное значение T
    maxT    = 0.9;  // Максимальное значение T
    θ       = 10;   // Параметр θ
    μ       = 0.01; // Параметр μ

    ArrayResize (params, 5); // Изменение размера массива параметров

    // Инициализация параметров
    params [0].name = "popSize"; params [0].val = popSize;
    params [1].name = "minT";    params [1].val = minT;
    params [2].name = "maxT";    params [2].val = maxT;
    params [3].name = "θ";       params [3].val = θ;
    params [4].name = "μ";       params [4].val = μ;
  }

  void SetParams () // Метод для установки параметров
  {
    popSize = (int)params [0].val; // Установка размера популяции
    minT    = params      [1].val; // Установка минимального T
    maxT    = params      [2].val; // Установка максимального T
    θ       = params      [3].val; // Установка параметра θ
    μ       = params      [4].val; // Установка параметра μ
  }

  bool Init (const double &rangeMinP  [], // Минимальный диапазон поиска
             const double &rangeMaxP  [], // Максимальный диапазон поиска
             const double &rangeStepP [], // Шаг поиска
             const int     epochsP = 0);  // Количество эпох

  void Moving   (); // Метод перемещения частиц
  void Revision (); // Метод ревизии

  //----------------------------------------------------------------------------
  double minT; // Минимальное значение T
  double maxT; // Максимальное значение T
  double θ;    // Параметр θ
  double μ;    // Параметр μ
  double ϵ;    // Параметр для предотвращения деления на ноль

  private: //-------------------------------------------------------------------
  int epochs;    // Общее количество эпох
  int epochNow;  // Текущая эпоха
};
//——————————————————————————————————————————————————————————————————————————————

O método "Init" da classe "C_AO_AOA" é responsável por inicializar o algoritmo de otimização, configurando os parâmetros do intervalo de busca, os passos e a quantidade de épocas durante as quais a otimização será executada. A lógica de funcionamento do método:

1. O método chama primeiro o "StandardInit", que inicializa os parâmetros padrão do algoritmo. Se essa inicialização falhar, o método "Init" encerra imediatamente a execução e retorna "false".

2. Definição de parâmetros:

• Define o número total de épocas "epochs" com base no parâmetro recebido "epochsP".
• Inicializa a época atual "epochNow" com o valor "0".
• Define o valor de "ϵ" (valor pequeno para evitar divisão por zero) como "DBL_EPSILON", que é o valor padrão representando o menor número positivo possível no tipo "double".

3. Se todas as etapas forem realizadas com sucesso, o método retorna "true", indicando que a inicialização do algoritmo foi bem-sucedida.

O método "Init" é uma parte importante da preparação do algoritmo para execução, pois define os principais parâmetros que serão utilizados no processo de otimização. A chamada a este método resulta na redefinição de todos os parâmetros e variáveis para seu estado inicial.

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_AOA::Init (const double &rangeMinP  [], // Минимальный диапазон поиска
                     const double &rangeMaxP  [], // Максимальный диапазон поиска
                     const double &rangeStepP [], // Шаг поиска
                     const int     epochsP = 0)   // Количество эпох
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; // Инициализация стандартных параметров

  //----------------------------------------------------------------------------
  epochs   = epochsP;     // Установка общего количества эпох
  epochNow = 0;           // Инициализация текущей эпохи
  ϵ        = DBL_EPSILON; // Установка значения ϵ

  return true;            // Возвращаем true при успешной инициализации
}
//——————————————————————————————————————————————————————————————————————————————

O método "Moving" é responsável pelo deslocamento das partículas no espaço de soluções dentro do algoritmo AOA. Ele implementa a lógica principal de atualização das posições das partículas com base no estado atual e nos parâmetros do algoritmo. A lógica de funcionamento do método:

1. Incrementa o valor de "epochNow", indicando o início de uma nova época de otimização.

2. Posicionamento aleatório inicial: caso ainda não tenha sido realizada a atualização (revisão), são geradas posições aleatórias para cada partícula dentro dos intervalos definidos por "rangeMin" e "rangeMax". Cada posição é então convertida em valor discreto usando o método "SeInDiSp" com o passo especificado.

3. MoAc e MoPr — são calculados com base na época atual e nos parâmetros definidos. Esses valores determinam as probabilidades utilizadas para atualizar as posições das partículas.

4. Fase de diversificação. Para cada partícula e para cada coordenada, a posição é atualizada com base em valores aleatórios e nos parâmetros calculados. As posições podem ser atualizadas utilizando diferentes operadores (divisão e multiplicação), bem como condições probabilísticas.

5. Após a atualização, a posição também é convertida em valor discreto por meio do método "SeInDiSp".

//——————————————————————————————————————————————————————————————————————————————
// Метод перемещения частиц
void C_AO_AOA::Moving ()
{
  epochNow++; // Увеличиваем номер текущей эпохи

  // Начальное случайное позиционирование
  if (!revision) // Если еще не было ревизии
  {
    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;          // Выход из метода
  }

  //----------------------------------------------------------------------------
  double MoAc = minT + epochNow * ((maxT - minT) / epochs); // Вычисление значения MoAc
  double MoPr = 1.0 - pow (epochNow / epochs, (1.0 / θ));   // Вычисление значения MoPr
  double best = 0.0;                                        // Переменная для хранения лучшего значения

  // Фаза исследования с использованием операторов Деления (D) и Умножения (M)
  for (int i = 0; i < popSize; i++) // Для каждой частицы
  {
    for (int c = 0; c < coords; c++) // Для каждой координаты
    {
      double rand1 = u.RNDprobab (); // Генерация случайного значения
      double rand2 = u.RNDprobab (); // Генерация случайного значения
      double rand3 = u.RNDprobab (); // Генерация случайного значения

      best = cB [c];                 // Сохранение текущего лучшего значения

      if (rand1 < MoAc)              // Если случайное значение меньше MoAc
      {
        if (rand2 > 0.5)             // Если случайное значение больше 0.5
        {
          a [i].c [c] = best / (MoPr + ϵ) * ((rangeMax [c] - rangeMin [c]) * μ + rangeMin [c]); // Обновление позиции частицы
        }
        else
        {
          a [i].c [c] = best * (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ + rangeMin [c]);     // Обновление позиции частицы
        }
      }
      else // Если случайное значение больше или равно MoAc
      {
        if (rand3 > 0.5) // Если случайное значение больше 0.5
        {
          a [i].c [c] = best - (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ + rangeMin [c]);     // Обновление позиции частицы
        }
        else
        {
          a [i].c [c] = best + (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ + rangeMin [c]);     // Обновление позиции частицы
        }
      }

      a [i].c [c] = u.SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);       // Приведение к дискретным значениям
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método "Revision" na classe "C_AO_AOA" atualiza a informação sobre a melhor partícula da população. Ele percorre todas as partículas, compara seus valores de função com o valor atual considerado como o melhor e, se encontrar um valor superior, atualiza esse valor e armazena o índice correspondente. Em seguida, copia as coordenadas da melhor partícula para o array "cB".

//——————————————————————————————————————————————————————————————————————————————
void C_AO_AOA::Revision ()
{
  int ind = -1;                     // Индекс для хранения лучшей частицы

  for (int i = 0; i < popSize; i++) // Для каждой частицы
  {
    if (a [i].f > fB)               // Если значение функции лучше, чем текущее лучшее
    {
      fB = a [i].f;                 // Обновление лучшего значения функции
      ind = i;                      // Сохранение индекса лучшей частицы
    }
  }

  if (ind != -1) ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY); // Копирование координат лучшей частицы
}
//——————————————————————————————————————————————————————————————————————————————

O método "SeInDiSp" da classe "C_AO_Utilities" limita o valor de entrada "In" ao intervalo [InMin, InMax] com o passo especificado "Step".

1. Se "In" for menor ou igual a "InMin", retorna "InMin".
2. Se "In" for maior ou igual a "InMax", retorna "InMax".
3. Se "Step" for igual a 0, retorna o valor original "In".
4. Caso contrário, arredonda o valor de (In − InMin) ÷ Step e retorna o valor ajustado dentro do intervalo, considerando o passo.

double C_AO_Utilities :: SeInDiSp (double In, double InMin, double InMax, double Step)
{
  if (In <= InMin) return (InMin);
  if (In >= InMax) return (InMax);
  if (Step == 0.0) return (In);
  else return (InMin + Step * (double)MathRound ((In - InMin) / Step));
}

Resultados dos testes

O algoritmo AOA é bastante simples, então vejamos seu desempenho em tarefas de teste.

Segundo os resultados do teste, o algoritmo alcança apenas 21,18% do total de 100% possível. Um resultado muito fraco, infelizmente inferior até mesmo ao último da tabela de classificação atual. Vamos tentar modificar a lógica do algoritmo para obter resultados melhores. Faremos as mudanças em etapas e monitoraremos os resultados.

A lógica do algoritmo AOA original prevê uma busca estocástica baseada exclusivamente no caráter probabilístico da escolha entre os quatro operadores matemáticos. Vamos adicionar ao coeficiente de deslocamento μ um elemento de aleatoriedade, multiplicando-o por um número aleatório entre 0 e 1.

// Фаза исследования с использованием операторов Деления (D) и Умножения (M)
  for (int i = 0; i < popSize; i++) // Для каждой частицы
  {
    for (int c = 0; c < coords; c++) // Для каждой координаты
    {
      double rand1 = u.RNDprobab (); // Генерация случайного значения
      double rand2 = u.RNDprobab (); // Генерация случайного значения
      double rand3 = u.RNDprobab (); // Генерация случайного значения

      best = cB [c];                 // Сохранение текущего лучшего значения

      μ *= u.RNDfromCI (0, 1);       // Случайное изменение параметра μ

      if (rand1 < MoAc)              // Если случайное значение меньше MoAc
      {
        if (rand2 > 0.5)             // Если случайное значение больше 0.5
        {
          a [i].c [c] = best / (MoPr + ϵ) * ((rangeMax [c] - rangeMin [c]) * μ + rangeMin [c]); // Обновление позиции частицы
        }
        else
        {
          a [i].c [c] = best * (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ + rangeMin [c]);     // Обновление позиции частицы
        }
      }
      else // Если случайное значение больше или равно MoAc
      {
        if (rand3 > 0.5) // Если случайное значение больше 0.5
        {
          a [i].c [c] = best - (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ + rangeMin [c]);     // Обновление позиции частицы
        }
        else
        {
          a [i].c [c] = best + (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ + rangeMin [c]);     // Обновление позиции частицы
        }
      }

      a [i].c [c] = u.SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);       // Приведение к дискретным значениям
    }
  }

Vamos testar o algoritmo com os mesmos parâmetros:

Infelizmente, o resultado foi ainda pior. É necessário tomar medidas adicionais. No entanto, o simples fato de adicionar aleatoriedade a uma expressão determinística deve, sem dúvida, melhorar a variabilidade da estratégia de busca. Observemos atentamente as fórmulas dos operadores matemáticos — em cada uma delas há o termo "rangeMin[c]". Na prática, as expressões desses operadores são sempre centradas em torno do limite mínimo dos parâmetros otimizados. Isso não parece ter uma lógica evidente, então removeremos esse elemento de todas as fórmulas.

// Фаза исследования с использованием операторов Деления (D) и Умножения (M)
for (int i = 0; i < popSize; i++) // Для каждой частицы
{
  for (int c = 0; c < coords; c++) // Для каждой координаты
  {
    double rand1 = u.RNDprobab (); // Генерация случайного значения
    double rand2 = u.RNDprobab (); // Генерация случайного значения
    double rand3 = u.RNDprobab (); // Генерация случайного значения

    best = cB [c];                 // Сохранение текущего лучшего значения

    μ *= u.RNDfromCI (0, 1);       // Изменение параметра μ

    if (rand1 < MoAc)              // Если случайное значение меньше MoAc
    {
      if (rand2 > 0.5)             // Если случайное значение больше 0.5
      {
        a [i].c [c] = best / (MoPr + ϵ) * ((rangeMax [c] - rangeMin [c]) * μ);// + rangeMin [c]); // Обновление позиции частицы
      }
      else
      {
        a [i].c [c] = best * (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ);// + rangeMin [c]);     // Обновление позиции частицы
      }
    }
    else // Если случайное значение больше или равно MoAc
    {
      if (rand3 > 0.5) // Если случайное значение больше 0.5
      {
        a [i].c [c] = best - (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ);// + rangeMin [c]);     // Обновление позиции частицы
      }
      else
      {
        a [i].c [c] = best + (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ);// + rangeMin [c]);     // Обновление позиции частицы
      }
    }

    a [i].c [c] = u.SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);       // Приведение к дискретным значениям
  }
}

Testando. Abaixo estão os resultados obtidos:

As modificações realizadas não levaram à melhoria do desempenho, o que é bastante estranho, considerando que já aplicamos mudanças significativas na estratégia de busca. Isso pode indicar que a própria estratégia apresenta deficiências e que a remoção de componentes isolados não tem impacto significativo nos resultados.

Na estratégia de busca há o componente MoA, que cresce linearmente a cada iteração (ver figura 1). Vamos tentar utilizar esse componente como critério probabilístico para escolher uma das coordenadas da melhor solução e copiá-la para a solução em trabalho atual. Isso deve adicionar propriedades combinatórias à estratégia de busca, por meio da troca de informações com a melhor solução da população (na versão original dos autores, não há troca de informações entre os agentes).

// Фаза исследования с использованием операторов Деления (D) и Умножения (M)
for (int i = 0; i < popSize; i++) // Для каждой частицы
{
  for (int c = 0; c < coords; c++) // Для каждой координаты
  {
    double rand1 = u.RNDprobab (); // Генерация случайного значения
    double rand2 = u.RNDprobab (); // Генерация случайного значения
    double rand3 = u.RNDprobab (); // Генерация случайного значения

    best = cB [c];                 // Сохранение текущего лучшего значения

    μ *= u.RNDfromCI (0, 1);       // Изменение параметра μ

    if (rand1 < MoAc)              // Если случайное значение меньше MoAc
    {
      if (rand2 > 0.5)             // Если случайное значение больше 0.5
      {
        a [i].c [c] = best / (MoPr + ϵ) * ((rangeMax [c] - rangeMin [c]) * μ); // Обновление позиции частицы
      }
      else
      {
        a [i].c [c] = best * (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ);     // Обновление позиции частицы
      }
    }
    else // Если случайное значение больше или равно MoAc
    {
      if (rand3 > 0.5) // Если случайное значение больше 0.5
      {
        a [i].c [c] = best - (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ);     // Обновление позиции частицы
      }
      else
      {
        a [i].c [c] = best + (MoPr) * ((rangeMax [c] - rangeMin [c]) * μ);     // Обновление позиции частицы
      }
    }

    if (u.RNDbool () < MoAc) a [i].c [c] = cB [c];                                            // Установка на лучшее значение

    a [i].c [c] = u.SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);       // Приведение к дискретным значениям
  }
}

Resultados obtidos após a introdução da lógica de troca de informações por meio da melhor solução:

Observamos melhorias no desempenho, embora ainda dentro da margem de variação dos próprios resultados. Agora vamos adicionar, nessa mesma parte do código, uma probabilidade de gerar um valor aleatório para a coordenada dentro de todo o intervalo permitido dos parâmetros otimizados, que diminui de forma não linear de acordo com a fórmula de MoP.

// Вероятностное обновление позиции частицы
if (u.RNDbool () < MoAc) a [i].c [c] = cB [c];                                        // Установка на лучшее значение
else
  if (u.RNDbool () < MoPr) a [i].c [c] = u.RNDfromCI (rangeMin [c], rangeMax [c]);    // Генерация новой случайной позиции

Analisemos os próximos resultados:

Surpreendentemente, o desempenho aumentou drasticamente! Isso indica que estamos seguindo na direção certa. Vale destacar o que foi adicionado à lógica do AOA: no início da otimização, na primeira época, a probabilidade de copiar coordenadas da melhor solução global para a solução atual é mínima. Isso faz sentido, já que no estágio inicial da otimização a estratégia está apenas começando a explorar o espaço de busca. Ao mesmo tempo, a probabilidade de gerar soluções aleatórias dentro de todo o espaço de busca é máxima na primeira iteração. Ao longo das épocas, essas probabilidades se alteram: a probabilidade de copiar coordenadas da solução global aumenta, enquanto a de gerar soluções aleatórias diminui (ver figura 1).

Como o desempenho melhorou após as alterações que implementei — e como já havia sido observado anteriormente que mudanças na lógica original dos autores não traziam melhorias significativas — faz sentido remover completamente todos os operadores aritméticos. Vamos testar o algoritmo resultante nas tarefas de teste:

Como se pode ver, a performance aumentou quase 5% a mais, o que confirma novamente a correção do meu raciocínio. Obtivemos resultados interessantes usando os parâmetros padrão, no entanto, as mudanças na lógica foram tão profundas que agora é necessário ajustar os parâmetros externos do algoritmo para obter o melhor desempenho. Um bônus adicional do ganho de desempenho foi:

• aceleração significativa na execução, já que eliminamos gerações desnecessárias de números aleatórios
• redução de um parâmetro externo do algoritmo

Vejamos os resultados finais do algoritmo resultante:

O resultado obtido já merece um lugar na tabela de classificação, e a versão final da estratégia de busca perdeu completamente os elementos da lógica original do algoritmo dos autores. Por isso, decidi dar a esse novo algoritmo um novo nome — Simple Optimization Algorithm, ou SAO (Algoritmo de Otimização Simples). Vamos conferir o código final completo do algoritmo SAO.

#include "#C_AO.mqh"

//——————————————————————————————————————————————————————————————————————————————
class C_AO_SOA : public C_AO
{
  public: //--------------------------------------------------------------------
  ~C_AO_SOA () { }
  C_AO_SOA ()
  {
    ao_name = "SOA";
    ao_desc = "Simple Optimization Algorithm";
    ao_link = "https://www.mql5.com/ru/articles/16364";

    popSize = 50;   // Размер популяции
    minT    = 0.1;  // Минимальное значение T
    maxT    = 0.9;  // Максимальное значение T
    θ       = 10;   // Параметр θ

    ArrayResize (params, 4); // Изменение размера массива параметров

    // Инициализация параметров
    params [0].name = "popSize"; params [0].val = popSize;
    params [1].name = "minT";    params [1].val = minT;
    params [2].name = "maxT";    params [2].val = maxT;
    params [3].name = "θ";       params [3].val = θ;
  }

  void SetParams () // Метод для установки параметров
  {
    popSize = (int)params [0].val; // Установка размера популяции
    minT    = params      [1].val; // Установка минимального T
    maxT    = params      [2].val; // Установка максимального T
    θ       = params      [3].val; // Установка параметра θ
  }

  bool Init (const double &rangeMinP  [], // Минимальный диапазон поиска
             const double &rangeMaxP  [], // Максимальный диапазон поиска
             const double &rangeStepP [], // Шаг поиска
             const int     epochsP = 0);  // Количество эпох

  void Moving   (); // Метод перемещения частиц
  void Revision (); // Метод ревизии

  //----------------------------------------------------------------------------
  double minT; // Минимальное значение T
  double maxT; // Максимальное значение T
  double θ;    // Параметр θ

  private: //-------------------------------------------------------------------
  int epochs;    // Общее количество эпох
  int epochNow;  // Текущая эпоха
  double ϵ;      // Параметр для предотвращения деления на ноль
};
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
bool C_AO_SOA::Init (const double &rangeMinP  [], // Минимальный диапазон поиска
                     const double &rangeMaxP  [], // Максимальный диапазон поиска
                     const double &rangeStepP [], // Шаг поиска
                     const int     epochsP = 0)   // Количество эпох
{
  if (!StandardInit (rangeMinP, rangeMaxP, rangeStepP)) return false; // Инициализация стандартных параметров

  //----------------------------------------------------------------------------
  epochs   = epochsP;     // Установка общего количества эпох
  epochNow = 0;           // Инициализация текущей эпохи
  ϵ        = DBL_EPSILON; // Установка значения ϵ

  return true;            // Возвращаем true при успешной инициализации
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
// Метод перемещения частиц
void C_AO_SOA::Moving ()
{
  epochNow++; // Увеличиваем номер текущей эпохи

  // Начальное случайное позиционирование
  if (!revision) // Если еще не было ревизии
  {
    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;          // Выход из метода
  }

  //----------------------------------------------------------------------------
  double MoAc = minT + epochNow * ((maxT - minT) / epochs); // Вычисление значения MoAc
  double MoPr = 1.0 - pow (epochNow / epochs, (1.0 / θ));   // Вычисление значения MoPr
  double best = 0.0;                                        // Переменная для хранения лучшего значения

  // Фаза исследования с использованием операторов Деления (D) и Умножения (M)
  for (int i = 0; i < popSize; i++) // Для каждой частицы
  {
    for (int c = 0; c < coords; c++) // Для каждой координаты
    {
      // Вероятностное обновление позиции частицы
      if (u.RNDbool () < MoAc) a [i].c [c] = cB [c];                                        // Установка на лучшее значение
      else
        if (u.RNDbool () < MoPr) 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]);   // Приведение к дискретным значениям
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
void C_AO_SOA::Revision ()
{
  int ind = -1;                     // Индекс для хранения лучшей частицы

  for (int i = 0; i < popSize; i++) // Для каждой частицы
  {
    if (a [i].f > fB)               // Если значение функции лучше, чем текущее лучшее
    {
      fB = a [i].f;                 // Обновление лучшего значения функции
      ind = i;                      // Сохранение индекса лучшей частицы
    }
  }

  if (ind != -1) ArrayCopy (cB, a [ind].c, 0, 0, WHOLE_ARRAY); // Копирование координат лучшей частицы
}
//——————————————————————————————————————————————————————————————————————————————

Obtivemos um dos algoritmos de otimização com código mais compacto dentre todos os que analisamos até agora. Apenas o código do algoritmo RW (RandomWalk), que será abordado em um dos próximos artigos, é ainda mais curto.

A visualização do funcionamento das estratégias de busca no espaço de soluções fala mais do que qualquer explicação. Reuni os três testes (Hilly, Forest e Megacity) para o algoritmo AOA em uma única animação, já que praticamente não há diferença perceptível no comportamento do algoritmo em diferentes tipos de tarefas. Abaixo são mostradas visualizações individuais do funcionamento do SOA para cada uma das três funções de teste.

É possível destacar o desempenho do novo algoritmo SOA em tarefas de baixa dimensionalidade — pequena dispersão nos resultados e qualidade aceitável em intervalos razoáveis. 

AOA nas funções de teste Hilly, Forest, Megacity

SOA na função de teste Hilly

  SOA na função de teste Forest

SOA na função de teste Megacity

Como resultado dos testes, o algoritmo original AOA não entrou na tabela de classificação, já que sua pontuação ficou abaixo da 45ª posição. Por outro lado, o novo algoritmo “Simple Optimization Algorithm” (SOA) entrou no ranking e ficou em 29º lugar.

Considerações finais

Analisamos detalhadamente o Algoritmo de Otimização Aritmética, cuja implementação se mostrou realmente simples. No entanto, como às vezes acontece, simplicidade nem sempre garante resultados excelentes. O verdadeiro segredo do sucesso é a super simplicidade! Claro que isso é uma brincadeira. Os principais problemas do AOA estão na ausência de interação e troca de informações entre os membros da população, o que leva à completa falta de propriedades combinatórias nessa estratégia de busca.

Outro ponto fraco do algoritmo está na ausência de variabilidade em seus operadores de busca. Apesar de os operadores serem escolhidos aleatoriamente para cada coordenada, isso não permite que o algoritmo se conecte eficientemente ao relevo multidimensional do espaço de busca. Ainda assim, o algoritmo AOA apresenta abordagens racionais e logicamente fundamentadas, como os elementos MoA e MoP, que variam a cada época. Foram esses elementos que se tornaram a base para a recriação do algoritmo e sua evolução para uma nova estratégia de busca extremamente simples e interessante baseada na abordagem probabilística de copiar informações das melhores soluções da população e gerar soluções aleatórias dentro do espaço de busca.

A cada época, a aleatoriedade nas soluções da população diminui, enquanto aumenta a concentração nas direções bem-sucedidas. Isso pode ser comparado ao processo de construção de uma ponte elegante sobre um rio: nas etapas iniciais, são utilizados diversos materiais e estruturas que, talvez, não sejam adequados para o resultado final. No entanto, à medida que o projeto avança, as melhores soluções se tornam mais evidentes e os elementos desnecessários são descartados. Como resultado, a ponte torna-se cada vez mais harmônica e resistente, conectando as margens com elegância e solidez.

Figura 2. Gradação de cores dos algoritmos conforme os respectivos testes. A cor branca destaca resultados maiores ou iguais a 0,99

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 cálculo da tabela de classificação)

Vantagens e desvantagens do algoritmo SOA:

Vantagens:

1. Poucos parâmetros externos.
2. Bons resultados em tarefas de baixa dimensionalidade, especialmente nas discretas.
3. Rápido.
4. Baixa variação nos resultados em tarefas de baixa dimensionalidade.
   
5. Implementação extremamente simples.
   

Desvantagens:

1. Baixa escalabilidade.
   

Está anexado ao artigo um arquivo compactado contendo as versões mais recentes dos códigos dos algoritmos. O autor do artigo não se responsabiliza pela precisão absoluta da descrição dos algoritmos canônicos, já que muitos deles foram modificados para aprimorar suas capacidades de busca. As conclusões e observações apresentadas nos artigos baseiam-se nos resultados dos experimentos realizados.

• github: https://github.com/JQSakaJoo/Population-optimization-algorithms-MQL5

Programas utilizados no artigo