Algoritmos de otimização populacionais: Otimização de colônia de formigas (ACO)

A grande questão de qualquer comportamento é o comportamento em sociedade...

Frederic Bartlett

Conteúdo

1. Introdução
2. Princípios do algoritmo
3. Versão modificada
4. Resultado dos testes

1. Introdução

O cientista belga Marco Dorigo desenvolveu um modelo matemático que descreve cientificamente o processo de inteligência coletiva em colônias de formigas e o publicou em sua dissertação de doutorado de 1992.

Ele também implementou esse modelo como um algoritmo chamado Otimização da Colônia de Formigas (ACO). Este método é baseado em busca estocástica e população para resolver uma ampla variedade de problemas de otimização combinatória. Ele se baseia no conceito de estigmergia, introduzido por Pierre-Paul Grassé em 1959 para explicar o comportamento de construção de ninhos de cupins. Estigmergia é composta de duas palavras gregas: "estigma" (sinal) e "ergonomia" (ação).

A definição canônica de estigmergia é uma forma indireta de interação entre os membros de uma população que se desenvolve ao longo do tempo, através da interação com o meio ambiente. Isso significa que um agente deixa uma marca ou modifica o ambiente de alguma forma, de modo que outro agente possa receber informações. No caso das formigas, a estigmergia se dá através da comunicação com feromônios. Um exemplo disso é a busca de alimentos, onde as formigas se comunicam indiretamente umas com as outras, deixando traços de feromônios no chão, influenciando assim as decisões de outras formigas. Essa forma simples de comunicação entre indivíduos leva a comportamentos complexos e oportunidades para a colônia como um todo.

As formigas são insetos sociais que vivem em colônias e têm um comportamento orientado para a busca de alimento. A busca por alimento é feita por meio de perambulações pelas colônias. Durante esse processo, as formigas deixam traços de um composto orgânico chamado feromônio no chão, que é utilizado como meio de comunicação entre elas. Essas trilhas de feromônios servem como guias para outras formigas na busca de alimento.

Quando uma formiga encontra alimento, ela carrega o máximo que pode e, ao retornar à colônia, deposita feromônios na trilha, de acordo com a quantidade e qualidade do alimento encontrado. As outras formigas sentem o cheiro desses feromônios e seguem a trilha, aumentando a probabilidade de escolha dessa rota. Quanto maior o nível de feromônio, maior a probabilidade de escolha da rota e quanto mais formigas passarem por ela, maior será a quantidade de feromônio depositado. Dessa forma, as formigas se comunicam indiretamente, aumentando a eficiência na busca de alimento para a colônia.

Vamos ilustrar isso com um exemplo. Imagine que existem dois caminhos para alcançar os alimentos desde a colônia e não há feromônio no solo. Neste caso, a probabilidade de escolher cada caminho é de 50%. Suponha que duas formigas escolham caminhos diferentes, com a probabilidade de escolha de cada caminho sendo de 50%. Esses caminhos têm distâncias diferentes, então a formiga que escolhe o caminho mais curto chegará ao alimento antes da outra formiga. Quando ela encontra alimento, ela leva uma parte dele de volta para a colônia e deposita feromônio no solo. Como ela escolheu o caminho mais curto, ela chegará à colônia mais cedo.

Com o tempo, a formiga que escolheu a rota mais curta, será seguida por mais formigas, pois há maior concentração de feromônio nesta rota, tornando-a mais atrativa para as formigas. Como o caminho mais curto tem mais feromônios que o mais longo, a formiga segue o caminho com mais feromônios. Quando a formiga que segue o caminho mais longo retorna à colônia, outras formigas já têm o caminho com níveis mais altos de feromônios. Assim, quando outra formiga tenta alcançar seu destino, ela escolhe aleatoriamente um caminho, pois todos têm o mesmo nível de feromônio. Com o tempo, o caminho mais curto tem um nível de feromônio mais alto do que os outros e as formigas tendem a segui-lo.

O algoritmo ACO é baseado em inteligência de enxame, simulando como uma colônia de formigas procura por alimentos. Ele estabelece o caminho mais curto em diferentes ambientes através do mecanismo de transmissão de informações da colônia de formigas. Durante a busca, as formigas deixam feromônios e as formigas subsequentes escolhem o caminho com base na concentração de feromônios. A probabilidade de escolha de um caminho aumenta quanto maior a concentração de feromônios. A concentração de feromônios diminui com o tempo. Assim, com o comportamento da colônia de formigas, as formigas aprendem e se otimizam continuamente, com um mecanismo de feedback para determinar o caminho mais curto para encontrar alimentos. Devido a essas características, o algoritmo ACO é amplamente utilizado em planejamento de caminhos.

2. Princípios do algoritmo

No algoritmo ACO, agentes de software conhecidos como formigas artificiais buscam soluções ótimas para problemas de otimização. Para aplicar o ACO, o problema de otimização é transformado em encontrar o melhor caminho em um grafo ponderado. As formigas artificiais constroem soluções ao se movimentarem pelo grafo. O processo de construção da solução é estocástico e depende do modelo de feromônios, que é um conjunto de parâmetros associados aos componentes do grafo (nós ou arestas) cujos valores mudam com as formigas durante a execução.

Vamos considerar um algoritmo para o problema do caixeiro viajante. É dado um conjunto de locais (como cidades) e as distâncias entre eles. O objetivo é encontrar um caminho fechado de comprimento mínimo que visite cada cidade apenas uma vez. Um grafo é construído a partir desses locais, com vértices representando as cidades e as arestas representando as distâncias entre elas. Esse grafo é chamado de grafo de construção. Como é possível viajar de qualquer cidade para qualquer outra, o grafo de construção é completamente conectado e o número de vértices é igual ao número de cidades. As arestas do grafo são definidas com comprimentos proporcionais às distâncias entre as cidades, e atribuímos valores de feromônio e heurísticos para as arestas. Os valores de feromônio mudam durante a execução e representam a experiência acumulada da colônia de formigas, enquanto os valores heurísticos são dependentes do problema.

As formigas constroem soluções através do seguinte processo: cada formiga inicia em uma cidade escolhida aleatoriamente (um vértice do grafo de construção). Em seguida, em cada etapa da construção, ela se move ao longo das arestas do grafo. Cada formiga mantém um registro de seu caminho e, nas etapas subsequentes, escolhe entre as arestas que não levam a vértices já visitados. Uma formiga completa uma solução depois de visitar todos os vértices do grafo. Em cada etapa da construção, a formiga escolhe probabilisticamente uma aresta para seguir, entre aquelas que levam a vértices ainda não visitados. A regra de probabilidade é baseada nos valores dos feromônios e em informações heurísticas: quanto maior o valor de feromônio e heurísticas associados à uma aresta, maior a probabilidade de uma formiga escolher essa aresta em particular. Depois que todas as formigas concluem suas viagens, os feromônios nas arestas são atualizados. Cada valor do feromônio é inicialmente reduzido em uma determinada porcentagem. Esse processo é repetido até que o critério de conclusão seja atendido.

A comunicação baseada em feromônios é um dos métodos mais eficazes e amplamente utilizados na natureza. Feromônios são usados por insetos sociais, como abelhas, formigas e cupins, tanto para comunicação entre indivíduos quanto para comunicação entre grupos. Devido a sua eficácia, feromônios artificiais são utilizados em sistemas robóticos em enxame e multirrobóticos.

Como saber se nossas formigas realmente encontraram o caminho mais curto? Há um excelente exemplo de teste para isso: pontos dispostos em um círculo. Neste caso, o caminho mais curto será sempre o mesmo, um círculo completo.  

O primeiro algoritmo ACO, chamado sistema de formigas, foi desenvolvido para resolver o problema do caixeiro viajante, cujo objetivo é encontrar a rota mais curta para visitar várias cidades e voltar ao ponto de partida. O algoritmo é relativamente simples e baseado em um conjunto de formigas, cada uma das quais percorre diferentes rotas entre as cidades. Em cada etapa, a formiga escolhe uma rota de uma cidade para outra de acordo com as seguintes regras:

1. Deve visitar cada cidade exatamente uma vez;
2. Cidades distantes têm menor probabilidade de serem escolhidas (baseado em uma medida de visibilidade);
3. Quanto maior a concentração de feromônio deixado na aresta entre duas cidades, maior a probabilidade de essa aresta ser escolhida;
4. Após concluir seu caminho, a formiga deposita mais feromônios em todas as arestas percorridas se o caminho for curto;
5. Após cada iteração, as trilhas de feromônios evaporam.

Figura 1. Exemplo de caminhos possíveis em cinco pontos nodais.

3. Versão modificada

Existem várias versões populares dos algoritmos ACO, vamos listá-las:

Sistema de formigas (AS).
Este sistema é o primeiro algoritmo ACO.

Sistema de colônia de formigas (ACS).
Este algoritmo foi modificado em três aspectos em relação ao AS:
1. A seleção de caminhos foi deslocada em favor do aproveitamento, ou seja, a probabilidade de escolher os caminhos mais curtos com maior quantidade de feromônios aumentou;
2. Durante a construção da solução, as formigas modificam o nível de feromônios nas arestas que escolhem, usando uma regra de atualização local;
3. No final de cada iteração, somente a formiga com a melhor solução é permitida atualizar os trajetos, usando uma regra de atualização global modificada.

Sistema de formigas elite.
Ele é semelhante ao algoritmo do AS, mas com uma estratégia de elite adicionada. Nesta estratégia, a melhor solução global deixa feromônio em sua trilha após cada iteração, junto com todas as outras formigas. A ideia é direcionar a busca de todas as formigas para a construção de uma solução que contenha as referências do melhor caminho atual.

Sistema de formigas max-min (MMAS).
Este algoritmo controla a quantidade máxima e mínima de feromônio em cada trilha. Somente o melhor trajeto global ou o melhor trajeto repetido podem adicionar feromônios em sua trilha. Para evitar estagnação do algoritmo de busca, o intervalo de quantidade de feromônio possíveis em cada trilha é limitado entre [τ max, τ min]. Todas as arestas são inicializadas com o valor τ max para acelerar a pesquisa de solução. As trilhas também são reinicializadas para τ max quando a estagnação se aproxima.

Sistema de formigas baseado na classificação (Asrank).
O sistema Asrank se baseia em um sistema de classificação, no qual todas as soluções são classificadas de acordo com sua duração. Somente um número fixo de melhores formigas nesta iteração pode atualizar suas tentativas. A quantidade de feromônio depositado é ponderada para cada solução, de modo que as soluções com caminhos mais curtos depositam mais feromônio do que as soluções com caminhos mais longos. Isso permite que o sistema priorize soluções mais curtas e eficientes.

Otimização paralela da colônia de formigas (PACO).
A PACO foi desenvolvida com base no sistema de colônia de formigas (ACS) com estratégias de comunicação.
As formigas artificiais são divididas em vários grupos e sete métodos de comunicação são propostos para atualizar o nível de feromônios entre os grupos no ACS, que trabalham na solução do problema do caixeiro viajante.

Colônia de formigas ortogonal contínua (COAC).
Ela utiliza um mecanismo de deposição de feromônios que permite que as formigas trabalhem juntas e de forma eficiente para encontrar soluções. Usando o método de projeção ortogonal, as formigas podem rapidamente e eficientemente explorar áreas selecionadas dentro de uma região permitida, com ampliadas capacidades e precisão de busca global. O método de projeto ortogonal e o método de ajuste adaptativo do raio também podem ser aplicados a outros algoritmos de otimização para proporcionar benefícios mais amplos ao resolver problemas práticos.

Otimização recursiva da colônia de formigas.
Este algoritmo recursivo divide a área de busca em subdomínios e, em seguida, resolve o problema em cada subdomínio. Os resultados dos subdomínios são comparados e os melhores são selecionados para serem divididos novamente. Este processo é repetido até que se alcance a precisão desejada. Este método foi testado em problemas de inversão geofísica sem correção e funciona bem.

Os anteriores algoritmos de colônia de formigas são altamente especializados e foram desenvolvidos originalmente para resolver problemas de otimização em gráficos. As condições do problema são dadas como parâmetros do algoritmo, como as coordenadas dos nós em um gráfico. Esses algoritmos, baseados nos princípios do ACO, não são aplicáveis para problemas que não utilizam coordenadas fixas, como as tarefas de otimização em instrumentos financeiros e treinamento de redes neurais. Portanto, é necessário desenvolver um novo algoritmo universal, que seja capaz de passar em nossos testes específicos e seja um ACO completamente novo e sem paralelo.

Vamos refinar a concepção do algoritmo. Assim como na versão canônica, teremos uma colônia de formigas. Não podemos marcar os caminhos percorridos com feromônios, pois eles podem se mover em qualquer direção no espaço multidimensional, armazenar e salvar rotas, especialmente com um passo contínuo, não é viável, pois a probabilidade de seguir o mesmo caminho é próxima de zero. Além disso, não há necessidade de armazenar nós, pois não há necessidade de percorrer sem repetições - precisamos remover essa tarefa do algoritmo. Então, o que fazer? Neste ponto, não está claro, levando em consideração o que foi dito acima, qual direção seguir na concepção do algoritmo.

Bem, mais uma vez notamos por nós mesmos os principais pontos que distinguem nosso novo algoritmo do canônico:

1. Não há pontos fixos no espaço.

2. Não é necessário seguir um determinado ordem ao percorrer o caminho.

3. Como não há caminhos fixos, não é necessário marcá-los com feromônios.

Então, vamos refletir sobre como funciona o nosso novo algoritmo, que utiliza uma colônia de formigas. Ao invés de marcar os caminhos percorridos com feromônios, marcaremos os pontos onde as formigas estão. Utilizaremos a quantidade de feromônios presente em um ponto como medida da adaptação da solução. Dessa forma, as formigas se movem em direção aos pontos com maior quantidade de feromônios. No entanto, podemos encontrar um problema onde todas as formigas se concentram em um único ponto, que pode não ser a melhor solução para o problema. Lembramos que, no algoritmo clássico de colônia de formigas, o comprimento do caminho até um ponto também é importante, quanto menor, melhor. Portanto, precisamos considerar a distância entre o ponto atual e o destino da formiga. Além disso, incluir uma certa aleatoriedade no movimento das formigas em direção umas às outras também pode ser benéfico.

Como podemos adicionar aleatoriedade à movimentação das formigas em nosso algoritmo? Para tornar o movimento das formigas mais imprevisível, podemos incluir dois coeficientes de aleatoriedade:

• Um baseado na quantidade de feromônio presente na posição (PheromoneEffect_P)
• e outro baseado na distância entre a posição atual e a próxima (PathLengthEffect_P).

Dessa forma, as formigas considerarão tanto a quantidade de feromônio quanto a distância para selecionar a próxima posição. No entanto, para evitar que as formigas se movam apenas em direção às costelas de uma figura imaginária, devemos incluir outros critérios de seleção.

Neste caso, vamos adicionar o raio de influência do feromônio PheromoneRadius_P (coeficiente da distância entre os pontos), dentro do qual as formigas podem senti-lo, então as formigas poderão deslizar além do ponto para o qual se moveu. Isso dará um grau adicional de liberdade às formigas ao se moverem no espaço multidimensional.

Para garantir que as formigas possam explorar novas áreas, é importante permitir que elas possam desviar-se do vetor de direção em qualquer uma das coordenadas. Para isso, vamos introduzir o coeficiente PathDeviation_P, que permitirá que as formigas desviem seu incremento em uma determinada coordenada. Como estamos lidando com um espaço multidimensional, é possível que algumas coordenadas tenham incrementos positivos e outras negativos, e os valores de incremento podem ser diferentes. Esse coeficiente permitirá considerar esses pontos e dará às formigas uma certa liberdade para buscar o extremo da função.

Então, qual é o vetor deslocamento e como medimos a distância que a formiga tem que percorrer? Para fazer isso, usamos a fórmula para calcular a distância entre dois pontos no espaço tridimensional:

A Figura 2 mostra o vetor deslocamento.

Figura 2. Vetor deslocamento da formiga.

Para espaços n-dimensionais, o cálculo é semelhante.

A formiga se move do ponto A para o ponto B em uma iteração (época), com possível deslizamento para o ponto R. A distância entre o ponto R e o ponto B depende do coeficiente PheromoneRadius_P e pode ser calculada da seguinte forma: BR = AB x PheromoneRadius_P.

A probabilidade de uma nova localização na linha AR é mostrada esquematicamente (não em escala) na Figura 2 como uma área cinza. Assim, é mais provável que a nova localização da formiga tenda para a vizinhança do ponto B. O princípio da mudança de probabilidade foi discutido no artigo anterior.

O algoritmo inclui as seguintes etapas em cada iteração:

1) Disposição aleatória das formigas no espaço.
2) Determinação do valor da quantidade de feromônio (função de adaptação) das formigas.
3) Cálculo da distância entre formigas.
4) Cálculo da escolha do ponto preferencial por onde a formiga se deslocará.
5) Cálculo da probabilidade de um ponto no vetor AR.
6) Cálculo das coordenadas do ponto obtido no vetor AR.
7) Repetição a partir do ponto 2) até que a condição de parada seja atendida.

Vamos proceder à descrição do código do algoritmo. Primeiramente, vamos escrever uma estrutura contendo uma descrição da formiga, onde:

• c[] - suas coordenadas, 
• cLast [] - coordenadas anteriores,
• cB [] - melhores coordenadas para todas as iterações,
• f - valor atual do feromônio,
• fB - valor máximo do feromônio alcançado em todas as iterações.

No construtor da estrutura da formiga, inicializamos o valor de f e fB com o menor valor possível, que pode ser representado pelo tipo double.

//——————————————————————————————————————————————————————————————————————————————
struct S_Ants
{
    double cLast  []; //last coordinates
    double c      []; //coordinates
    double cB     []; //best coordinates

    double f;     //pheromone of the current coordinates
    double fB;    //pheromone of the best coordinates

    S_Ants ()
    {
      f  = -DBL_MAX;
      fB = -DBL_MAX;
    }
};
//——————————————————————————————————————————————————————————————————————————————

Precisamos de uma estrutura cuja matriz nos permita armazenar distâncias pareadas entre todas as formigas.

struct S_Paths
{
    double a [];
};

Escreveremos nosso algoritmo ACO modificado como uma classe, na qual ainda existem apenas três métodos públicos, suficientes e necessários dentro da estrutura do conceito desenvolvido de construção de algoritmos de otimização, discutidos nos artigos anteriores, InitAnts (), Preparation (), e Dwelling () ). Agora existem os métodos privados GenerateRNDants() e AntsMovement(), e outros métodos privados que já se tornaram padrão para nossos algoritmos. A matriz de estruturas ants [] é uma colônia de formigas.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_ACO
{
  public:
  //----------------------------------------------------------------------------
  S_Ants ants      []; //ants
  double rangeMax  []; //maximum search range
  double rangeMin  []; //manimum search range
  double rangeStep []; //step search
  double cB        []; //best coordinates
  double fB;           //pheromone of the best coordinates

  void InitAnts (const int    coordinatesP,       //number of opt. parameters
                 const int    antHillSizeP,
                 double       pheromoneEffectP,
                 double       pathLengthEffectP,
                 double       pheromoneRadiusP,
                 double       pathDeviationP);

  void Preparation ();
  void Dwelling ();

  private:
  //----------------------------------------------------------------------------
  S_Paths paths [];
  int coordinates;        //number of coordinates
  int antHillSize;        //ant hill size

  double goals     [];

  double pheromoneEffect;
  double pathLengthEffect;
  double pheromoneRadius;
  double pathDeviation;
  bool   dwelling;

  void   GenerateRNDants ();
  void   AntsMovement    ();

  double SeInDiSp             (double in, double inMin, double inMax, double step);
  double RNDfromCI            (double min, double max);
  double Scale                (double In, double InMIN, double InMAX, double OutMIN, double OutMAX, bool revers);
};
//——————————————————————————————————————————————————————————————————————————————

No método de inicialização, atribuímos valores iniciais às variáveis e o tamanho dos arrays.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::InitAnts (const int    coordinatesP,       //number of opt. parameters
                         const int    antHillSizeP,
                         double       pheromoneEffectP,
                         double       pathLengthEffectP,
                         double       pheromoneRadiusP,
                         double       pathDeviationP)
{
  fB = -DBL_MAX;

  coordinates      = coordinatesP;
  antHillSize      = antHillSizeP;
  pheromoneEffect  = pheromoneEffectP;
  pathLengthEffect = pathLengthEffectP;
  pheromoneRadius  = pheromoneRadiusP;
  pathDeviation    = pathDeviationP;

  ArrayResize (rangeMax,  coordinates);
  ArrayResize (rangeMin,  coordinates);
  ArrayResize (rangeStep, coordinates);

  dwelling = false;

  ArrayResize (ants,  antHillSize);
  ArrayResize (paths, antHillSize);

  for (int i = 0; i < antHillSize; i++)
  {
    ArrayResize (ants  [i].c,      coordinates);
    ArrayResize (ants  [i].cLast,  coordinates);
    ArrayResize (ants  [i].cB,     coordinates);
    ArrayResize (paths [i].a,      antHillSize);
  }

  ArrayResize (cB,    coordinates);
  ArrayResize (goals, antHillSize);
}
//——————————————————————————————————————————————————————————————————————————————

O método Preparation () é chamado primeiro em cada iteração.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::Preparation ()
{
  if (!dwelling)
  {
    fB = -DBL_MAX;
    GenerateRNDants ();
    dwelling = true;
  }
  else AntsMovement ();
}
//——————————————————————————————————————————————————————————————————————————————

O método GenerateRNDants() é responsável por criar uma colônia de formigas aleatória, as coordenadas das formigas são atribuídas aleatoriamente dentro dos limites especificados.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::GenerateRNDants ()
{
  for (int s = 0; s < antHillSize; s++)
  {
    for (int k = 0; k < coordinates; k++)
    {
      ants [s].c     [k] = RNDfromCI (rangeMin [k], rangeMax [k]);
      ants [s].c     [k] = SeInDiSp (ants [s].c [k], rangeMin [k], rangeMax [k], rangeStep [k]);
      ants [s].cLast [k] = ants [s].c [k];
      ants [s].cB    [k] = ants [s].c [k];
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Vamos lembrar as coordenadas atuais das formigas no método Dwelling () e, ao mesmo tempo, atualizar os valores máximos de feromônio obtidos no momento da iteração atual.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::Dwelling ()
{
  for (int i = 0; i < antHillSize; i++)
  {
    ArrayCopy (ants [i].cLast, ants [i].c, 0, 0, WHOLE_ARRAY);

    //remember the best coordinates for the ant
    if (ants [i].f > ants [i].fB)
    {
      ants [i].fB = ants [i].f;
      ArrayCopy (ants [i].cB, ants [i].c, 0, 0, WHOLE_ARRAY);
    }

    //remember the best coordinates for the anthill
    if (ants [i].f > fB)
    {
      fB = ants [i].f;
      ArrayCopy (cB, ants [i].c, 0, 0, WHOLE_ARRAY);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

O método principal do algoritmo é AntsMovement(). Ele executa várias ações: calcula a distância entre cada formiga, calcula a escolha do ponto preferido para onde a formiga se moverá, calcula a probabilidade de um ponto no vetor AR. Cálculo das coordenadas do ponto obtido no vetor AR:

//——————————————————————————————————————————————————————————————————————————————
void C_AO_ACO::AntsMovement ()
{
  double rndPh;
  double rndPt;
  double summCoordinates = 0.0;
  double scores [];
  ArrayResize (scores, antHillSize);

  double maxPh = -DBL_MAX;
  double minPh =  DBL_MAX;
  double maxPt = -DBL_MAX;
  double minPt =  DBL_MAX;
  double goal;
  double goalBest = -DBL_MAX;
  int    goalInd  = 0;

  //measure the distance between all the ants-----------------------------------
  for (int i = 0; i < antHillSize; i++)
  {
    for (int k = 0; k < antHillSize; k++)
    {
      if (i == k)
      {
        paths [i].a [k] = DBL_MAX;
        continue;
      }
         
      for (int c = 0; c < coordinates; c++) summCoordinates += pow (ants [i].cLast [c] - ants [k].cLast [c], 2.0);

      paths [i].a [k] = pow (summCoordinates, 0.5);

      if (maxPt < paths [i].a [k]) maxPt = paths [i].a [k];
      if (minPt > paths [i].a [k]) minPt = paths [i].a [k];
    }
  }

  //----------------------------------------------------------------------------
  for (int i = 0; i < antHillSize; i++)
  {
    maxPh = -DBL_MAX;
    minPh =  DBL_MAX;

    for (int k = 0; k < antHillSize; k++)
    {
      if (i != k)
      {
        if (maxPh < ants [k].f) maxPh = ants [k].f;
        if (minPh > ants [k].f) minPh = ants [k].f;
      }
    }

    goalBest = -DBL_MAX;
    goalInd  = 0;

    for (int k = 0; k < antHillSize; k++)
    {
      if (i != k)
      {
        rndPh = RNDfromCI (0.0, pheromoneEffect);
        rndPt = RNDfromCI (0.0, pathLengthEffect);

        goal = Scale (ants  [k].f,     minPh, maxPh, 0.0, 1.0, false) * rndPh *
               Scale (paths [i].a [k], minPt, maxPt, 0.0, 1.0, true)  * rndPt;

        if (goalBest < goal)
        {
          goalBest = goal;
          goalInd  = k;
        }
      }
    }
    
    double wayToGoal      = paths [i].a [goalInd];
    double radiusNearGoal = wayToGoal * pheromoneRadius;
    double endWay         = wayToGoal + radiusNearGoal;

    double x = RNDfromCI (-1.0, 1.0);
    double y = x * x;
    
    if (x > 0.0) y = Scale (y, 0.0, 1.0, wayToGoal, endWay,    false);
    else         y = Scale (y, 0.0, 1.0, 0.0,       wayToGoal, true);

    for (int j = 0; j < coordinates; j++)
    {
      double incrementFactor = y / wayToGoal;
      double coordDistance = ants [goalInd].cLast [j] - ants [i].cLast [j];
      
      ants [i].c [j] =  ants [i].cLast [j] + (coordDistance * incrementFactor);
      double w = coordDistance * RNDfromCI (-1.0, 1.0) * pathDeviation;
      ants [i].c [j] += w;
      
      ants [i].c [j] = SeInDiSp (ants [i].c [j], rangeMin [j], rangeMax [j], rangeStep [j]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

Vale a pena prestar atenção à função de escalonamento de números de uma faixa numérica para outra. Já o encontramos em artigos anteriores, desta vez vamos expandir sua funcionalidade. O parâmetro de entrada revers inverte a direção da escala, como mostrado na figura abaixo.

Figura 3. Exemplo de escalonamento de um número de um intervalo numérico para outro.

1) Escalonamento direto; 2) Escalonamento reverso.

//——————————————————————————————————————————————————————————————————————————————
double C_AO_ACO::Scale (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers)
{
  if (OutMIN == OutMAX) return (OutMIN);
  if (InMIN == InMAX) return (double((OutMIN + OutMAX) / 2.0));
  else
  {
    if (In < InMIN) return revers ? OutMAX : OutMIN;
    if (In > InMAX) return revers ? OutMIN : OutMAX;

    double res = (((In - InMIN) * (OutMAX - OutMIN) / (InMAX - InMIN)) + OutMIN);

    if (!revers) return res;
    else         return OutMAX - res;
  }
}
//——————————————————————————————————————————————————————————————————————————————

4. Resultado dos testes

ACO na função de teste Skin.

ACO na função de teste Forest.

ACO na função de teste Megacity.

Portanto, é hora de fazer um balanço. Por um lado, o clássico algoritmo de colônia de formigas não é aplicável a problemas de otimização para negociação de instrumentos financeiros e pode não ser levado em consideração. No entanto, alguns lances da imaginação nos permitiram evitar as limitações da versão clássica e escrever uma nova versão inédita. Você testemunhou o surgimento de um conceito completamente novo, o algoritmo da colônia de formigas, dentro do qual o desenvolvimento posterior do ACO é possível. Tal algoritmo já pode ser aplicado a uma ampla gama de problemas, incluindo o mesmo problema do caixeiro viajante.

Além disso, obtivemos um novo líder da tabela de classificação. Consideremos os resultados com mais detalhes. Para começar, vejamos os resultados da bateria de testes:

2022.10.27 16:46:28.678    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:46:50.599    Test_AO_ACO (EURUSD,M1)    1 Skin's; Func runs 1000 result: 13.969156176320473; Func runs 10000 result: 13.986949123110085
2022.10.27 16:46:50.599    Test_AO_ACO (EURUSD,M1)    Score1: 0.99502; Score2: 0.99599
2022.10.27 16:47:12.424    Test_AO_ACO (EURUSD,M1)    20 Skin's; Func runs 1000 result: 8.514904198298202; Func runs 10000 result: 11.56159524595023
2022.10.27 16:47:12.424    Test_AO_ACO (EURUSD,M1)    Score1: 0.69826; Score2: 0.86403
2022.10.27 16:48:04.200    Test_AO_ACO (EURUSD,M1)    500 Skin's; Func runs 1000 result: 4.962716036996786; Func runs 10000 result: 6.488619274853463
2022.10.27 16:48:04.200    Test_AO_ACO (EURUSD,M1)    Score1: 0.50498; Score2: 0.58800
2022.10.27 16:48:04.200    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:48:25.999    Test_AO_ACO (EURUSD,M1)    1 Forest's; Func runs 1000 result: 15.805601165115196; Func runs 10000 result: 15.839944455892518
2022.10.27 16:48:25.999    Test_AO_ACO (EURUSD,M1)    Score1: 0.99087; Score2: 0.99302
2022.10.27 16:48:47.897    Test_AO_ACO (EURUSD,M1)    20 Forest's; Func runs 1000 result: 3.568897096569507; Func runs 10000 result: 10.45940001108266
2022.10.27 16:48:47.897    Test_AO_ACO (EURUSD,M1)    Score1: 0.22374; Score2: 0.65571
2022.10.27 16:49:41.855    Test_AO_ACO (EURUSD,M1)    500 Forest's; Func runs 1000 result: 1.3412234994286016; Func runs 10000 result: 2.7822130728041756
2022.10.27 16:49:41.855    Test_AO_ACO (EURUSD,M1)    Score1: 0.08408; Score2: 0.17442
2022.10.27 16:49:41.855    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:50:03.740    Test_AO_ACO (EURUSD,M1)    1 Megacity's; Func runs 1000 result: 11.8; Func runs 10000 result: 11.8
2022.10.27 16:50:03.740    Test_AO_ACO (EURUSD,M1)    Score1: 0.78667; Score2: 0.78667
2022.10.27 16:50:26.002    Test_AO_ACO (EURUSD,M1)    20 Megacity's; Func runs 1000 result: 1.75; Func runs 10000 result: 3.9200000000000004
2022.10.27 16:50:26.002    Test_AO_ACO (EURUSD,M1)    Score1: 0.11667; Score2: 0.26133
2022.10.27 16:51:21.075    Test_AO_ACO (EURUSD,M1)    500 Megacit 's; Func runs 1000 result: 0.6335999999999999; Func runs 10000 result: 1.2312
2022.10.27 16:51:21.075    Test_AO_ACO (EURUSD,M1)    Score1: 0.04224; Score2: 0.08208

2022.10.27 16:49:41.075    Test_AO_ACO (EURUSD,M1)    =============================
2022.10.27 16:51:21.075    Test_AO_ACO (EURUSD,M1)    All score for C_AO_ACO: 0.5468768583006471

O algoritmo teve um bom desempenho na função suave Skin, mostrando excelente convergência e boa capacidade de escalonamento, especialmente superando notavelmente nos testes com 20 e 500 funções. Na função Forest suave com quebras acentuadas, a quebra é ainda mais perceptível, o algoritmo continua a busca mesmo quando atinge extremos locais. Na função Megacity discreta, o algoritmo cedeu ao algoritmo aleatório RND apenas em um problema com 500 funções.

AO	Runs	Skin			Forest			Megacity (discrete)			Final result
		2 params (1 F)	40 params (20 F)	1000 params (500 F)	2 params (1 F)	40 params (20 F)	1000 params (500 F)	2 params (1 F)	40 params (20 F)	1000 params (500 F)
ACOm	1000	0,99502	0,69826	0,50498	0,99087	0,22374	0,08408	0,78667	0,11667	0,04224	0,54688
	10000	0,99599	0,86403	0,58800	0,99302	0,65571	0,17442	0,78667	0,26133	0,08208
RND	1000	0,98744	0,61852	0,49408	0,89582	0,19645	0,14042	0,77333	0,19000	0,14283	0,51254
	10000	0,99977	0,69448	0,50188	0,98181	0,24433	0,14042	0,88000	0,20133	0,14283
PSO	1000	0,98436	0,72243	0,65483	0,71122	0,15603	0,08727	0,53333	0,08000	0,04085	0,47695
	10000	0,99836	0,72329	0,65483	0,97615	0,19640	0,09219	0,82667	0,10600	0,04085
PSOm	1000	0,96678	0,64727	0,57654	0,80616	0,13388	0,06800	0,53333	0,08067	0,04211	0,45144
	10000	0,99505	0,64986	0,57654	0,90401	0,18194	0,07104	0,74667	0,10400	0,04211

Conclusões

O algoritmo possui vários parâmetros que podem ser ajustados para obter resultados ainda melhores e adaptado a tipos específicos de tarefas. Um exemplo é o parâmetro PheromoneEffect_P, que afeta diretamente a velocidade de convergência. Isso é especialmente útil para funções monotônicas suaves, como uma parábola, onde a convergência será de 100%. No entanto, se definido como grande, pode contribuir para ficar preso em extremos locais de funções discretas.

O segundo parâmetro, PathLengthEffect_P, indica o nível de preguiça das formigas. Quanto mais alto o valor deste parâmetro, mais provável que as formigas escolham alvos mais próximos para se moverem. É importante equilibrar este parâmetro com o primeiro, para obter os melhores resultados. Ele foi projetado para oferecer um contrapeso ao desejo da formiga de ir ao ponto onde há mais alimento, permitindo que elas selecionem alvos próximos para uma inspeção mais detalhada de pequenas áreas, o que pode ser muito útil, como no caso da função Forest, onde o melhor ponto pode estar inesperadamente próximo.

A maior conquista do algoritmo da colônia de formigas é a superação do principal problema do ACO canônico, que é a capacidade de resolver apenas problemas combinatórios discretos. Com as melhorias feitas, o algoritmo da colônia de formigas pode ser utilizado para treinar redes neurais, ampliando sua aplicabilidade em diferentes áreas.

Visualmente, a observação da bateria de testes é interessante devido à forma como as formigas se concentram em dimensões da função multidimensional, destacando grupos característicos dos extremos locais. É possível utilizar este efeito para resolver problemas específicos, no entanto, é necessário realizar mais pesquisas para compreender como aproveitar essa característica.

Foi observado que o algoritmo apresenta uma propriedade interessante: quando resolvido para problemas com duas variáveis, há uma maior probabilidade de ficar preso em um extremo local em comparação com otimizações com 40 variáveis. Ainda assim, o algoritmo continua buscando soluções quando existem muitas variáveis. Acredito que isso seja resultado da utilização de um vetor para relacionar todas as coordenadas do espaço de busca. Por exemplo, quando uma formiga se move para um novo local melhor, todas as coordenadas espaciais melhoram em conjunto, ao invés de algumas isoladas.

Eu desenvolvi um novo algoritmo, que ainda não foi analisado em profundidade. Portanto, ficaria agradecido se alguém pudesse compartilhar configurações eficazes para esse algoritmo nos comentários deste artigo. Meu objetivo é obter resultados superiores a 0,6 na bateria de testes e, caso isso seja alcançado, atualizarei a tabela de resultados. Essa solicitação também se aplica aos algoritmos anteriormente mencionados.

Prós:
1. O algoritmo é bastante rápido.
2. Versatilidade. Pode ser usado em uma grande variedade de tarefas de otimização.
3. É capaz de não focar apenas em extremos locais.
4. Possui uma convergência razoavelmente boa para funções suaves e discretas.
5. Escalabilidade.

Contras:
1. Talvez sejam necessárias mais iterações para aumentar a convergência do que o mesmo PSO para funções suaves, mas isso é parcialmente compensado pela capacidade de continuar a busca mesmo onde o PSO já parou.
2. Forte influência dos parâmetros do algoritmo no resultado.