Algoritmos de otimização populacional: algoritmos de estratégias evolutivas (Evolution Strategies, (μ,λ)-ES e (μ+λ)-ES)

Conteúdo:

1. Introdução
2. Descrição do algoritmo
3. Substituição da função de teste
4. Resultados dos testes
5. Conclusões

1. Introdução

Os algoritmos de estratégias evolutivas (Evolution Strategies) são métodos de otimização baseados nos princípios observados na natureza. Eles imitam o processo de seleção natural, onde as melhores soluções sobrevivem e passam suas características para a próxima geração. Esses algoritmos são amplamente usados para resolver problemas de otimização, especialmente em aprendizado de máquina e inteligência artificial, tendo sido desenvolvidos nos anos 1960 pelo professor Ingo Rechenberg e seus colegas na Alemanha para resolver problemas de otimização na indústria e engenharia.

A ideia principal das estratégias evolutivas é criar uma população de soluções e melhorá-las usando operadores de mutação e seleção, similares aos usados na evolução natural. As estratégias evolutivas usam vetores de números reais para representar soluções, permitindo descrever o espaço de soluções de forma mais flexível e precisa, ao contrário dos algoritmos genéticos clássicos que operam com cadeias binárias.

Existem várias versões das estratégias evolutivas, que diferem na forma de geração e processamento da população, bem como nos operadores de mutação e seleção utilizados. Alguns dos mais comuns incluem:

1. (1+1)-ES: Neste caso, apenas um descendente é criado para cada pai, e a melhor solução entre os dois torna-se o pai da próxima geração. Esse método simples e rápido pode ser eficaz para alguns problemas, mas é menos eficiente na otimização de problemas complexos. O algoritmo (1+1)-ES foi criado nos anos 1960 e é um dos métodos mais simples de otimização por estratégias evolutivas. Ele gera um vetor aleatório que é então alterado por um passo aleatório. Se o vetor alterado for melhor, ele substitui o original; caso contrário, o vetor original permanece inalterado. Esse processo se repete até alcançar o ótimo.

1. (μ,λ)-ES: Neste algoritmo, uma população de tamanho μ é criada, gerando λ descendentes, e os melhores descendentes substituem os pais. Pode ser eficaz para vários problemas de otimização. O algoritmo (μ,λ)-ES foi criado por Reinhard Spiegelmann em 1965. Após avaliar os descendentes, apenas as melhores μ soluções são mantidas como pais para a próxima geração, substituindo completamente os pais em cada iteração.

1. (μ+λ)-ES: Neste caso, λ descendentes são criados, e os melhores entre eles, junto com os pais, formam a próxima geração. Nesse método, pais e descendentes competem entre si, o que é uma diferença importante do (μ,λ)-ES. O algoritmo (μ+λ)-ES foi criado nos anos 1970 por Johannes Reichenbächer e Hans-Paul Schwefel e é um método de otimização por estratégias evolutivas. Este método permite uma exploração mais completa do espaço de soluções e pode ser mais eficaz para problemas complexos.

Existem outras variantes das estratégias evolutivas, mas neste artigo, focaremos apenas no (μ,λ)-ES e no (μ+λ)-ES. O método (1+1)-ES é simples e inadequado para resolver problemas multidimensionais. Devido às dificuldades no uso de letras do alfabeto grego e símbolos especiais em nomes de arquivos e variáveis no código, usaremos as notações PO e P_O, onde P representa pais e O representa descendentes.

As estratégias evolutivas em ciências da computação permitem modelar processos de evolução e seleção natural para resolver problemas complexos de otimização. Eles usam princípios semelhantes aos da seleção natural para buscar soluções ótimas no espaço de parâmetros.

Esses algoritmos podem ser especialmente úteis em problemas onde não há uma solução analítica clara ou quando o espaço de busca é muito grande. Eles podem buscar soluções ótimas de forma eficiente, aplicando operações inspiradas na evolução, como cruzamento, mutação e seleção.

É importante notar que o nome "Estratégias Evolutivas" pode ser enganoso, fazendo parecer que se trata de um nome genérico para uma classe de algoritmos evolutivos. No entanto, não é o caso. Na verdade, trata-se de um grupo específico de algoritmos que usam ideias da evolução para resolver problemas de otimização.

2. Descrição do algoritmo

(μ,λ)-ES significa que, a cada iteração do algoritmo, são escolhidos μ pais e gerados λ descendentes. Então, dos λ descendentes, os melhores μ são escolhidos para se tornarem os pais da próxima iteração. Assim, no (μ,λ)-ES, os novos descendentes substituem completamente os pais na formação da próxima geração.

(μ+λ)-ES funciona de forma semelhante, mas em vez de escolher os melhores descendentes dentre λ, eles são combinados com os pais para formar uma nova população de tamanho μ+λ. Então, os melhores μ indivíduos dessa população combinada são escolhidos para se tornarem os pais da próxima iteração. No (μ+λ)-ES, os novos descendentes trabalham junto com os pais, formando a próxima população e competindo entre si.

A principal diferença entre (μ,λ)-ES e (μ+λ)-ES está em como os novos descendentes competem com os pais por um lugar na próxima população. No (μ,λ)-ES, os novos descendentes competem com os pais por um número limitado de lugares, o que pode levar a uma convergência precoce para um ótimo local. No (μ+λ)-ES, os novos descendentes trabalham junto com os pais, levando a uma exploração mais ampla do espaço de soluções.

Ambos os algoritmos de estratégias evolutivas são baseados na combinação de operadores genéticos: mutação e seleção. Em cada rodada do algoritmo, escolhe-se uma solução a partir da população atual e aplica-se o operador de mutação nela. Depois, calcula-se a adaptação da nova solução e a mais apta vai para a próxima população. Para gerar a população inicial, define-se um intervalo para cada componente do vetor de parâmetros variáveis e distribuem-se uniformemente os valores iniciais desses componentes nesse intervalo. O algoritmo pode usar vários critérios para parar, como alcançar um número fixo de gerações, um estado específico da população ou um nível de convergência definido previamente. No caso do algoritmo (μ+λ), a população inclui todos os indivíduos, enquanto no algoritmo (μ,λ) só os descendentes entram. Para o algoritmo (μ+λ), a convergência probabilística é comprovada, mas para o algoritmo (μ,λ) a questão da convergência ainda está aberta.

Comparando (μ+λ)-ES com (μ,λ)-ES, nota-se que (μ+λ)-ES é mais eficiente em usar indivíduos muito aptos, fazendo-os competir com os descendentes. Isso intensifica a busca, mas pode levar a uma convergência precoce para um extremo local. O operador de mutação no algoritmo evolutivo padrão é o único operador evolutivo e usa o algoritmo de mutação gaussiana.

O algoritmo clássico (μ,λ)-ES pode ser descrito pelo seguinte pseudocódigo:

1. Inicializar a população inicial com indivíduos aleatórios.
2. Repetir até atingir o critério de parada:
2.1. Cada um dos μ pais gera λ descendentes na população atual usando o operador de mutação.
2.2. Escolher os melhores μ descendentes para formar a próxima população.
3. Retornar o melhor indivíduo da última população.

O algoritmo clássico (μ+λ)-ES pode ser descrito pelo seguinte pseudocódigo:

1. Inicializar a população inicial com indivíduos aleatórios.
2. Repetir até atingir o critério de parada:
2.1. Cada um dos μ pais gera λ descendentes na população atual usando o operador de mutação.
2.2. Combinar pais e descendentes para obter uma população combinada de tamanho μ+λ.
2.3. Escolher os melhores μ indivíduos da população combinada para formar a próxima população.
3. Retornar o melhor indivíduo da última população.

Acima, discutimos as versões clássicas dos dois principais algoritmos de "Estratégias Evolutivas". Em ambos os casos, os pais geram λ descendentes usando apenas sua informação genética. Isso leva a um desenvolvimento independente de cada descendente, sem troca de informações entre os pais, o que elimina a possibilidade de combinar suas propriedades genéticas. Como resultado, as qualidades combinatórias estão completamente ausentes.

Os resultados dos testes mostraram que ambas as variantes das ES têm baixa eficiência, e para melhorar essa eficiência, tentei usar a recombinação.

A recombinação permite combinar material genético de diferentes indivíduos e criar novas combinações que podem ter melhores propriedades ou características. Este processo promove a diversidade na população.

A recombinação (ou cruzamento) é o processo de combinar material genético de indivíduos parentais para criar descendentes. Esse processo é parecido com o cruzamento natural na evolução biológica. Durante a recombinação, os genes dos pais se misturam para criar um novo material genético para os descendentes. Normalmente, a recombinação acontece no nível dos genes ou características genéticas. Os genes são pedaços de informação no genoma que codificam certas propriedades ou características do organismo.

Depois da recombinação, os genes dos descendentes são modificados pelo operador de mutação, que faz mudanças aleatórias nos genes. Isso ajuda a introduzir novas variantes de busca na população e promove a diversidade genética.

Então, para cada gene dos descendentes, usaremos genes de pais escolhidos aleatoriamente, onde o gene é a coordenada correspondente do pai. Assim, os descendentes herdarão características de todos os pais na população.

Algoritmo (μ,λ)-ES.

Passamos a considerar o código e começamos com o algoritmo mais simples (μ,λ)-ES, modificado com a adição de recombinação (herança de genes de múltiplos pais).

Para o pai e o descendente, que atuam como agente, é adequada a estrutura S_Agent, que contém um array de coordenadas "c" e uma variável "f" - valor de adaptação. A função "Init" inicializa o agente, alterando o tamanho do array "c" e definindo o valor de "f" como "-DBL_MAX" (o pior valor possível de adaptação).

//——————————————————————————————————————————————————————————————————————————————
struct S_Agent
{
  void Init (int coords)
  {
    ArrayResize (c, coords);
    f = -DBL_MAX;
  }

  double c []; //coordinates
  double f;    //fitness
};
//——————————————————————————————————————————————————————————————————————————————

Para descrever o algoritmo (μ,λ)-ES, declaramos a classe C_AO_POES.

A classe contém os seguintes elementos:

• Variáveis públicas "cB", "fB", "a", "rangeMax", "rangeMin", "rangeStep": essas variáveis são usadas para armazenar a melhor coordenada, o valor correspondente da função de adaptação, agentes, valores máximos e mínimos de busca e o passo de busca, respectivamente.
• Função pública "Init()": essa função inicializa o algoritmo de otimização. Ela recebe vários argumentos, como o número de coordenadas, o tamanho da população, o número de agentes parentais, a força da mutação e o valor de sigma. Dentro da função, as variáveis e arrays usados no algoritmo são inicializados.
• Funções públicas "Moving()" e "Revision()": essas funções são usadas para mover os agentes e revisar a população, respectivamente.
• Variáveis privadas "coords", "popSize", "parentsNumb", "mutationPower", "sigmaM", "revision": essas variáveis são usadas para armazenar o número de coordenadas, o tamanho da população, o número de agentes parentais, a força da mutação, o valor de sigma e o sinal de revisão, respectivamente.
• Arrays privados "parents", "ind", "val", "pTemp": esses arrays são usados para armazenar informações sobre agentes parentais, índices, valores e variáveis temporárias, respectivamente.
• Funções privadas "GaussDistribution(), SeInDiSp(), RNDfromCI(), Scale(), Sorting()": essas funções são usadas para gerar números aleatórios, escalar valores e ordenar arrays.

//——————————————————————————————————————————————————————————————————————————————
class C_AO_POES
{
  //----------------------------------------------------------------------------
  public: double  cB [];  //best coordinates
  public: double  fB;     //FF of the best coordinates
  public: S_Agent a  [];  //agent

  public: double rangeMax  []; //maximum search range
  public: double rangeMin  []; //manimum search range
  public: double rangeStep []; //step search

  public: void Init (const int    coordsP,          //coordinates number
                     const int    popSizeP,         //population size
                     const int    parentsP,         //number of parents, < Population size
                     const double mutationPowerP,   //mutation power
                     const double sigmaP);          //sigma

  public: void Moving   ();
  public: void Revision ();

  //----------------------------------------------------------------------------
  private: int    coords;        //coordinates number
  private: int    popSize;       //population size
  private: int    parentsNumb;   //number of parents
  private: double mutationPower; //mutation power
  private: double sigmaM;
  private: bool   revision;

  private: S_Agent parents [];  //parents
  private: int     ind     [];
  private: double  val     [];
  private: S_Agent pTemp   [];

  private: double GaussDistribution   (const double In, const double outMin, const double outMax, const double sigma);
  private: double SeInDiSp  (double In, double InMin, double InMax, double Step);
  private: double RNDfromCI (double min, double max);
  private: double Scale     (double In, double InMIN, double InMAX, double OutMIN, double OutMAX,  bool revers);
  private: void   Sorting   (S_Agent &p [], int size);
};
//——————————————————————————————————————————————————————————————————————————————

Para inicializar o algoritmo de otimização, a função "Init" da classe C_AO_POES é usada. A função recebe vários argumentos: número de coordenadas, tamanho da população, número de agentes parentais, força da mutação e valor de sigma.

Dentro da função, as variáveis e arrays usados no algoritmo são inicializados. A função realiza as seguintes ações:

• Reset do gerador de números aleatórios e definição do valor da variável "fB" como "-DBL_MAX". 
• Definição dos valores das variáveis "coords", "popSize", "parentsNumb", "mutationPower" e "sigmaM". 
• Redimensionamento dos arrays "ind", "val", "pTemp", "a", "parents", "rangeMax", "rangeMin", "rangeStep" e "cB" usando a função "ArrayResize". 
• Os arrays "a" e "parents" são inicializados usando a função "Init" da classe "S_Agent", que inicializa as coordenadas do agente e define o valor da variável "f" como "-DBL_MAX".

//——————————————————————————————————————————————————————————————————————————————
void C_AO_POES::Init (const int    coordsP,          //coordinates number
                      const int    popSizeP,         //population size
                      const int    parentsP,         //number of parents, < Population size
                      const double mutationPowerP,   //mutation power
                      const double sigmaP)           //sigma
{
  MathSrand ((int)GetMicrosecondCount ()); // reset of the generator
  fB       = -DBL_MAX;
  revision = false;

  coords        = coordsP;
  popSize       = popSizeP;
  parentsNumb   = parentsP;
  mutationPower = mutationPowerP;
  sigmaM        = sigmaP;

  ArrayResize (ind,   popSize);
  ArrayResize (val,   popSize);
  ArrayResize (pTemp, popSize);
  ArrayResize (a,     popSize);
  for (int i = 0; i < popSize; i++) a [i].Init (coords);

  ArrayResize (parents, parentsNumb);
  for (int i = 0; i < parentsNumb; i++) parents [i].Init (coords);

  ArrayResize (rangeMax,  coords);
  ArrayResize (rangeMin,  coords);
  ArrayResize (rangeStep, coords);
  ArrayResize (cB,        coords);
}
//——————————————————————————————————————————————————————————————————————————————

Para mover os agentes no espaço de busca, o método "Moving" é usado.

A função contém dois blocos de código, separados pela condição "if (!revision)".

1. No primeiro bloco, são geradas coordenadas aleatórias para cada agente, caso o sinal de revisão "revision" seja igual a "false". Para cada coordenada, é gerado um número aleatório com distribuição uniforme no intervalo entre "rangeMin" e "rangeMax", e esse número é normalizado usando a função "SeInDiSp", que define o valor da coordenada para o valor mais próximo múltiplo de "rangeStep".
2. No segundo bloco, ocorre o movimento dos agentes, caso o sinal de revisão "revision" seja igual a "true". Para cada agente, é escolhido um agente parental aleatório do array "parents". Então, para cada coordenada do agente, é calculado o valor da mutação "dist", que depende da força da mutação "mutationPower" e do intervalo de busca "rangeMin" e "rangeMax". O valor da coordenada do agente é alterado usando a função "GaussDistribution", que gera um número aleatório com distribuição normal em torno do valor parental da coordenada, usando o valor de sigma "sigmaM". Em seguida, o valor da coordenada é normalizado usando a função "SeInDiSp".
   

//——————————————————————————————————————————————————————————————————————————————
void C_AO_POES::Moving ()
{
  //----------------------------------------------------------------------------
  if (!revision)
  {
    for (int i = 0; i < popSize; i++)
    {
      for (int c = 0; c < coords; c++)
      {
        a [i].c [c] = RNDfromCI (rangeMin [c], rangeMax [c]);
        a [i].c [c] = SeInDiSp (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
      }
    }

    revision = true;
    return;
  }

  //----------------------------------------------------------------------------
  int    indx = 0;
  double min  = 0.0;
  double max  = 0.0;
  double dist = 0.0;

  for (int i = 0; i < popSize; i++)
  {
    for (int c = 0; c < coords; c++)
    {
      indx = (int)RNDfromCI (0, parentsNumb);
      if (indx >= parentsNumb) indx = parentsNumb - 1;

      a [i].c [c] = parents [indx].c [c];

      dist = (rangeMax [c] - rangeMin [c]) * mutationPower;

      min = a [i].c [c] - dist; if (min < rangeMin [c]) min = rangeMin [c];
      max = a [i].c [c] + dist; if (max > rangeMax [c]) max = rangeMax [c];

      a [i].c [c] = GaussDistribution (a [i].c [c], min, max, sigmaM);
      a [i].c [c] = SeInDiSp  (a [i].c [c], rangeMin [c], rangeMax [c], rangeStep [c]);
    }
  }
}
//——————————————————————————————————————————————————————————————————————————————

A revisão da população é realizada pelo método "Revision", que é usado para revisar o estado atual dos agentes no algoritmo de otimização.

A função contém dois blocos de código.

1. No primeiro bloco, é procurado o melhor agente no array "a" usando um loop "for". Se for encontrado um agente com um valor de adaptação maior que o melhor agente atual "fB", o índice desse agente é salvo na variável "indx". Em seguida, o valor "fB" e as coordenadas "cB" do melhor agente atual são atualizados conforme o novo melhor agente.
2. No segundo bloco, o array "a" é ordenado em ordem decrescente de adaptação usando a função "Sorting", e então os "parentsNumb" melhores agentes do array "a" são copiados para o array "parents".

Dessa forma, a função "Revision" permite atualizar o estado atual dos agentes e manter os melhores agentes no array "parents", onde os melhores descendentes substituem completamente todos os pais.

//——————————————————————————————————————————————————————————————————————————————
void C_AO_POES::Revision ()
{
  //----------------------------------------------------------------------------
  int indx = -1;

  for (int i = 0; i < popSize; i++)
  {
    if (a [i].f > fB) indx = i;
  }

  if (indx != -1)
  {
    fB = a [indx].f;
    ArrayCopy (cB, a [indx].c, 0, 0, WHOLE_ARRAY);
  }

  //----------------------------------------------------------------------------
  Sorting (a, popSize);
  for (int i = 0; i < parentsNumb; i++)
  {
    parents [i] = a [i];
  }
}
//——————————————————————————————————————————————————————————————————————————————

Algoritmo (μ+λ)-ES.

As mudanças começam com a adição da duração da vida do indivíduo como um parâmetro "yearsNumber". Isso permitirá controlar a idade máxima na população e evitar a presença de indivíduos muito antigos, que podem impedir a exploração de novos horizontes do espaço vital infinito e a realização de novas descobertas. Esperamos que isso seja útil no algoritmo.

Por que esse contador não está presente no algoritmo "(μ,λ)-ES?" Porque foi assim projetado: substituir completamente os pais pelos descendentes. Isso também faz sentido, assim como acontece com os semélparos no mundo animal, onde algumas espécies se reproduzem apenas uma vez na vida. Exemplos dessas espécies incluem salmões, agaves, bambus, caranguejos-coco e cigarras. No entanto, em nosso algoritmo, daremos aos indivíduos a oportunidade de se reproduzir várias vezes, viver infinitamente ou morrer, como um orgulhoso bambu. A duração da vida pode ser um parâmetro externo ajustável, e em nossos testes, foi encontrada uma duração ótima de 10 anos.

Além disso, o contador de vidas pode ajudar a evitar o "overfitting" do modelo, quando a população começa a "memorizar" e acumular soluções específicas em vez de encontrar novas soluções bem-sucedidas em outras partes do espaço de busca. Limitar o tempo de vida dos indivíduos permite manter a diversidade da população e continuar buscando soluções mais otimizadas.

//——————————————————————————————————————————————————————————————————————————————
struct S_Agent
{
  void Init (int coords)
  {
    ArrayResize (c, coords);
    f = -DBL_MAX;
    yearsNumber = 0;
  }

  double c []; //coordinates
  double f;    //fitness
  int yearsNumber;
};
//——————————————————————————————————————————————————————————————————————————————

No método "Init", aumentaremos o tamanho da população parental para incluir o número de descendentes, permitindo que pais e descendentes sejam classificados juntos, embora, assim como no algoritmo (μ,λ)-ES, apenas uma parte μ da população combinada será usada para gerar novos descendentes. Se no algoritmo anterior o número de pais precisava ser menor ou igual à população de descendentes, neste algoritmo isso não importa, e o tamanho da população parental pode ser qualquer, inclusive muito grande, sem afetar o número de iterações. Foi descoberto experimentalmente que, com uma população de 100 descendentes (não mais do que isso - reduz o número de iterações), uma população parental de 150 é ideal. Aumentar ainda mais a população parental leva a uma diversidade genética excessiva, e o algoritmo começa a ter uma convergência pior (isso é interessante por si só).

ArrayResize (ind,   popSize + parentsNumb);
ArrayResize (val,   popSize + parentsNumb);
ArrayResize (pTemp, popSize + parentsNumb);
ArrayResize (a,     popSize);
for (int i = 0; i < popSize; i++) a [i].Init (coords);

ArrayResize (parents, popSize + parentsNumb);
for (int i = 0; i < popSize + parentsNumb; i++) parents [i].Init (coords);

No método "Moving", ao criar novos descendentes, definimos o contador de idade do indivíduo para 1.

a [i].yearsNumber = 1;

Mudanças também foram feitas no método "Revision", que, considerando as mudanças, realiza as seguintes ações:

• Aumenta o valor "yearsNumber" de cada pai em 1.
• Se o valor de "yearsNumber" exceder o limite estabelecido (lifespan), define o valor de adaptação "f" do pai correspondente para "-DBL_MAX", o que significa remover o indivíduo da população.
  
• Copia novos descendentes do array "a" para o array de pais "parents".
• Ordena o array "parents" pelo valor de adaptação "f".

//----------------------------------------------------------------------------
for (int i = 0; i < parentsNumb; i++)
{
  parents [i].yearsNumber++;

  if (parents [i].yearsNumber > lifespan)
  {
    parents [i].f = - DBL_MAX;
  }
}

for (int i = parentsNumb; i < parentsNumb + popSize; i++)
{
  parents [i] = a [i - parentsNumb];
}

Sorting (parents, parentsNumb + popSize);

3. Substituição da função de teste

Anteriormente, usávamos a função de Rastrigin como função de teste para avaliar os algoritmos de otimização. No entanto, a função de Rastrigin não é uma escolha ideal para esses fins. Ela possui periodicidade estrita e mínimos e máximos balanceados, o que pode ser relativamente simples de descobrir por alguns algoritmos. Assim, na função de Rastrigin, surgem padrões que podem afetar a capacidade do algoritmo de identificar os extremos da função.

Para uma avaliação mais confiável e objetiva dos algoritmos de otimização, é recomendável usar funções com propriedades diversificadas e imprevisíveis. Essas funções geralmente não possuem padrões óbvios ou equilíbrio entre mínimos e máximos. Exemplos dessas funções podem ser funções ruidosas, funções com dependências não lineares ou funções com muitos extremos locais. Essa escolha de funções permite avaliar mais precisamente a capacidade dos algoritmos de encontrar e convergir para ótimos globais em diferentes condições.

Condicionalmente, todas as funções podem ser divididas em "simples" e "complexas". As funções simples são aquelas cuja maior parte da superfície está acima da linha média entre max e min, e quanto mais da superfície estiver próxima do max, mais fácil será para os algoritmos de otimização. Assim, se colocarmos pontos aleatoriamente na superfície dentro do domínio da função, obteremos uma falsa impressão de "altos" resultados de otimização, pois os resultados estarão próximos do máximo global absoluto. Um exemplo de uma função simples pode ser um desenho esquemático de uma função hipotética na Figura 1.

Figura 1. Exemplo de função "simples" para algoritmos de otimização.

Devido ao exposto, a função "Rastrigin" pode ser considerada uma função simples, que pode gerar resultados inflacionados em alguns algoritmos de otimização. Isso se deve às características das estratégias de busca desses algoritmos, que podem distribuir seus agentes de forma dispersa por toda a superfície da função.

Esse efeito é particularmente notável na função "Rastrigin" com um grande número de variáveis, como 1000. Enquanto alguns algoritmos tentam "honestamente" encontrar o extremo global, outros podem simplesmente distribuir agentes uniformemente por toda a superfície da função. Essa abordagem não demonstra a capacidade do algoritmo de otimização para buscas precisas, mas apenas cria a ilusão de tal capacidade.

A função "Rastrigin" foi significativamente modificada para criar um ambiente mais complexo e desafiador para os algoritmos de otimização. Na nova versão da função, foram adicionados vários "montes" e "vales", mantendo a periodicidade na parte da superfície que não ajuda na busca pelo extremo global. Essas mudanças criam obstáculos adicionais, distraindo os agentes e funcionando como "armadilhas".

Agora, não é possível alcançar o extremo global apenas pulando pelos degraus com periodicidade, como na versão clássica de "Rastrigin". Além disso, o ótimo global foi deslocado da borda, dificultando sua localização na presença de artefatos nos algoritmos, que muitas vezes se concentram nas bordas do domínio da função.

A nova função foi chamada de "Hilly" (Fig. 2) e, assim como "Forest" e "Megacity", pertence a funções de teste complexas. Essas três funções têm aproximadamente a mesma área de superfície acima de 50% da altura máxima, que é cerca de 20% da área total da função.

As funções "Hilly", "Forest" e "Megacity" representam cenários complexos e realistas de otimização que podem ajudar a avaliar o desempenho dos algoritmos em condições difíceis e variadas. Usar essas funções em testes abrangentes de algoritmos de otimização pode fornecer uma visão mais completa sobre sua capacidade de encontrar ótimos globais e superar "armadilhas" locais.

Além disso, a metodologia de teste foi modificada. Agora, realiza-se um teste 10 vezes em vez de 5 vezes (número de reinicializações do processo de otimização) para reduzir "valores atípicos" nos resultados.

Figura 2. Função de teste "Hilly" (montanhosa).

4. Resultados dos testes

A execução do algoritmo (μ,λ)-ES no teste:

C_AO_(PO)ES:100:10:0.025:8.0
=============================
5 Hilly's; Func runs: 10000; result: 0.7902459324049909
25 Hilly's; Func runs: 10000; result: 0.6264667539839893
500 Hilly's; Func runs: 10000; result: 0.42934981087827656
=============================
5 Forest's; Func runs: 10000; result: 0.8761631782479373
25 Forest's; Func runs: 10000; result: 0.6094343681829253
500 Forest's; Func runs: 10000; result: 0.19591138782930953
=============================
5 Megacity's; Func runs: 10000; result: 0.5900000000000001
25 Megacity's; Func runs: 10000; result: 0.37933333333333336
500 Megacity's; Func runs: 10000; result: 0.11321666666666666
=============================
All score: 4.61012

Impressão do desempenho do algoritmo (μ+λ)-ES no teste:

C_AO_(P_O)ES:100:150:0.02:8.0:10
=============================
5 Hilly's; Func runs: 10000; result: 0.9993447297882565
25 Hilly's; Func runs: 10000; result: 0.9189524317647721
500 Hilly's; Func runs: 10000; result: 0.562968579605404
=============================
5 Forest's; Func runs: 10000; result: 1.0
25 Forest's; Func runs: 10000; result: 0.9352215748931851
500 Forest's; Func runs: 10000; result: 0.3917923122543615
=============================
5 Megacity's; Func runs: 10000; result: 0.8316666666666664
25 Megacity's; Func runs: 10000; result: 0.6443333333333332
500 Megacity's; Func runs: 10000; result: 0.21155000000000007
=============================
All score: 6.49583

A visualização abaixo é para o algoritmo (μ+λ)-ES, que demonstra uma exploração excelente do espaço de busca, sem deixar de lado áreas potencialmente promissoras.

(μ+λ)-ES na função de teste Hilly.

  (μ+λ)-ES na função de teste Forest.

  (μ+λ)-ES na função de teste Megacity.

Decidimos retornar aos valores absolutos dos resultados dos testes e abandonar os relativos. Para isso, as funções de teste foram alteradas para retornarem valores no intervalo de 0.0 a 1.0. Agora, se o resultado for 1.0, significa 100% de convergência, e, por exemplo, um resultado de 0.32527 significa 32.5% do máximo global da função de teste. Assim, como o número total de testes é 9, teoricamente os algoritmos podem obter um resultado máximo de 9.0 em caso de 100% de convergência do algoritmo em cada teste na coluna "Final result" da tabela. Além disso, foi adicionada a coluna "% of MAX", que mostra a porcentagem do resultado máximo possível.

Agora, os números dos resultados não mudarão ao adicionar novos algoritmos na tabela, pois estão representados em valores absolutos.

Então, vamos aos resultados dos algoritmos analisados, em particular o (μ+λ)-ES. Este algoritmo realmente me impressionou com seus resultados fenomenais: obteve um total de 72.18% do resultado teoricamente possível. Para confirmar esses resultados impressionantes, foi realizado um teste 20 vezes especificamente para este algoritmo. E cada uma das 20 execuções mostrou 100% de convergência na função complexa "Forest" - isso é simplesmente grandioso! Além disso, os resultados nas outras funções também foram notáveis.

Agora, algumas palavras sobre o (μ,λ)-ES. Este algoritmo mostrou resultados estáveis e bons. Na tabela de cores, está uniformemente "verde", sem mudanças bruscas de cor.

№	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	(P+O)ES	(P+O) evolution strategies	0,99934	0,91895	0,56297	2,48127	1,00000	0,93522	0,39179	2,32701	0,83167	0,64433	0,21155	1,68755	6,496	72,18
2	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
3	SIA	simulated isotropic annealing	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
4	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
5	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
6	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
7	(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
8	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
9	MEC	mind evolutionary computation	0,69533	0,53376	0,32661	1,55569	0,72464	0,33036	0,07198	1,12698	0,52500	0,22000	0,04198	0,78698	3,470	38,55
10	IWO	invasive weed optimization	0,72679	0,52256	0,33123	1,58058	0,70756	0,33955	0,07484	1,12196	0,42333	0,23067	0,04617	0,70017	3,403	37,81
11	COAm	cuckoo optimization algorithm M	0,75820	0,48652	0,31369	1,55841	0,74054	0,28051	0,05599	1,07704	0,50500	0,17467	0,03380	0,71347	3,349	37,21
12	SDOm	spiral dynamics optimization M	0,74601	0,44623	0,29687	1,48912	0,70204	0,34678	0,10944	1,15826	0,42833	0,16767	0,03663	0,63263	3,280	36,44
13	NMm	Nelder-Mead method M	0,73807	0,50598	0,31342	1,55747	0,63674	0,28302	0,08221	1,00197	0,44667	0,18667	0,04028	0,67362	3,233	35,92
14	FAm	firefly algorithm M	0,58634	0,47228	0,32276	1,38138	0,68467	0,37439	0,10908	1,16814	0,28667	0,16467	0,04722	0,49855	3,048	33,87
15	GSA	gravitational search algorithm	0,64757	0,49197	0,30062	1,44016	0,53962	0,36353	0,09945	1,00260	0,32667	0,12200	0,01917	0,46783	2,911	32,34
16	ABC	artificial bee colony	0,63377	0,42402	0,30892	1,36671	0,55103	0,21874	0,05623	0,82600	0,34000	0,14200	0,03102	0,51302	2,706	30,06
17	BFO	bacterial foraging optimization	0,54626	0,43533	0,31907	1,30066	0,41626	0,23156	0,06266	0,71048	0,35500	0,15233	0,03627	0,54360	2,555	28,39
18	BA	bat algorithm	0,59761	0,45911	0,35242	1,40915	0,40321	0,19313	0,07175	0,66810	0,21000	0,10100	0,03517	0,34617	2,423	26,93
19	SA	simulated annealing	0,55787	0,42177	0,31549	1,29513	0,34998	0,15259	0,05023	0,55280	0,31167	0,10033	0,02883	0,44083	2,289	25,43
20	IWDm	intelligent water drops M	0,54501	0,37897	0,30124	1,22522	0,46104	0,14704	0,04369	0,65177	0,25833	0,09700	0,02308	0,37842	2,255	25,06
21	PSO	particle swarm optimisation	0,59726	0,36923	0,29928	1,26577	0,37237	0,16324	0,07010	0,60572	0,25667	0,08000	0,02157	0,35823	2,230	24,77
22	MA	monkey algorithm	0,59107	0,42681	0,31816	1,33604	0,31138	0,14069	0,06612	0,51819	0,22833	0,08567	0,02790	0,34190	2,196	24,40
23	SFL	shuffled frog-leaping	0,53925	0,35816	0,29809	1,19551	0,37141	0,11427	0,04051	0,52618	0,27167	0,08667	0,02402	0,38235	2,104	23,38
24	FSS	fish school search	0,55669	0,39992	0,31172	1,26833	0,31009	0,11889	0,04569	0,47467	0,21167	0,07633	0,02488	0,31288	2,056	22,84
25	RND	random	0,52033	0,36068	0,30133	1,18234	0,31335	0,11787	0,04354	0,47476	0,25333	0,07933	0,02382	0,35648	2,014	22,37
26	GWO	grey wolf optimizer	0,59169	0,36561	0,29595	1,25326	0,24499	0,09047	0,03612	0,37158	0,27667	0,08567	0,02170	0,38403	2,009	22,32
27	CSS	charged system search	0,44252	0,35454	0,35201	1,14907	0,24140	0,11345	0,06814	0,42299	0,18333	0,06300	0,02322	0,26955	1,842	20,46
28	EM	electroMagnetism-like algorithm	0,46250	0,34594	0,32285	1,13129	0,21245	0,09783	0,10057	0,41085	0,15667	0,06033	0,02712	0,24412	1,786	19,85

Figura 3. Graduação de cor dos algoritmos conforme os respectivos testes.

Figura 4. Histograma dos resultados dos testes dos algoritmos (em uma escala de 0 a 100, quanto maior, melhor,

onde 100 é o resultado teórico máximo possível, no arquivo zip há um script para calcular a tabela de classificação).

5. Considerações finais

O uso de estratégias evolutivas abre novas possibilidades em diversas áreas, incluindo otimização de parâmetros em aprendizado de máquina, design de robôs e controle de sistemas complexos. Eles permitem obter as melhores soluções, baseadas nos princípios biológicos da evolução.

Temos um novo líder absoluto na tabela até o momento, superando o concorrente mais próximo, o SDSm, em quase 10%.

Vantagens e desvantagens do algoritmo de estratégia evolutiva (μ,λ)-ES:

Vantagens:

1. Poucos parâmetros externos.
2. Alta eficiência na resolução de diversas tarefas.
3. Facilidade de implementação do algoritmo.
4. Resistência a aprisionamentos locais.
5. Altos resultados em funções suaves e complexas.
6. Alta convergência.

Desvantagens:

1. Grande variação nos resultados em funções discretas.
   

Vantagens e desvantagens do algoritmo de estratégia evolutiva (μ+λ)-ES:

Vantagens:

1. Poucos parâmetros externos.
2. Alta eficiência na resolução de diversas tarefas.
3. Facilidade de implementação do algoritmo.
4. Resistência a aprisionamentos locais.
5. Altos resultados em funções suaves e complexas.
6. Alta convergência.

Desvantagens:

1. Grande variação nos resultados em funções discretas (embora ainda sejam os melhores resultados até o momento).

O artigo inclui um arquivo zip com versões atualizadas dos códigos dos algoritmos descritos em artigos anteriores. O autor do artigo não se responsabiliza pela precisão absoluta na descrição dos algoritmos canônicos, pois muitas modificações foram feitas para melhorar as capacidades de busca. As conclusões e julgamentos apresentados nos artigos são baseados nos resultados dos experimentos realizados.