Algoritmos de otimização populacionais: algoritmo genético binário (Binary Genetic Algorithm, BGA). Parte I

Conteúdo:

1. Introdução
2. Métodos de representação de características: real e binário
3. Vantagens da representação pelo código de Gray binário
4. Métodos de seleção
5. Tipos de método "crossover"
6. Tipos de método "mutação"
7. Considerações finais

1. Introdução

Neste artigo, vamos examinar detalhadamente os métodos e técnicas utilizados em algoritmos genéticos, que podem servir como ferramentas e blocos de construção para criar vários algoritmos de otimização em soluções personalizadas. O objetivo deste artigo é descrever e fornecer ferramentas para a pesquisa de problemas de otimização em qualquer algoritmo de otimização, não apenas em genéticos.

2. Métodos de representação de características: real e binário

Os parâmetros dos problemas de otimização são frequentemente chamados de "características" e devem ser representados de certa forma para serem usados na lógica do algoritmo de otimização. Na genética, essas características são divididas em fenótipo e genótipo. O fenótipo representa a aparência externa do parâmetro a ser otimizado, enquanto o genótipo é a forma como ele é representado no algoritmo. Na maioria dos algoritmos de otimização, o fenótipo coincide com o genótipo e é representado como um número real. O gene é um parâmetro a ser otimizado, enquanto o cromossomo é um conjunto de genes, ou seja, um conjunto de parâmetros a serem otimizados.

A representação em número real é usada para representar números fracionários. Números reais podem ter uma parte inteira e uma parte fracionária, separadas por um ponto decimal. Por exemplo, "3.14" e "0.5" são números reais.

A representação binária de dados, por outro lado, usa o sistema de numeração binária, onde os números são representados usando dois símbolos: "0" e "1" e cada dígito é chamado de bit (de "binary digit"). Por exemplo, o número "5" pode ser representado em binário como "101".

A principal diferença entre a representação real e binária dos dados está na forma de codificar os números. Os números reais geralmente são codificados usando padrões como o IEEE 754, que define formatos para representar números de ponto flutuante. Na linguagem MQL5, para números reais é usado o tipo de dados "double", que pode descrever no total 16 dígitos significativos em um número. Isso significa que o número total de dígitos não pode ser maior que dezesseis, por exemplo, "9 999 999 999 999 999.0" e "9 999 999.999 999 99" e "0.999 999 999 999 999 9" têm dezesseis dígitos "9" no total antes e depois do ponto decimal. Por que isso é importante vamos entender mais adiante.

Números reais são convenientes para uso na programação e no cotidiano, enquanto a representação binária é usada para trabalhar em sistemas de computação e realizar operações em baixo nível, como operações lógicas e operações bit a bit.

No contexto dos algoritmos de otimização, incluindo o algoritmo genético, os dados podem ser representados em forma de números reais ou binários, que são usados para codificar soluções e realizar operações sobre eles.

A vantagem de usar números reais em algoritmos de otimização é a possibilidade de trabalhar com valores contínuos de parâmetros. A representação real permite usar números para codificar características e realizar operações de busca de soluções diretamente com esses números. Por exemplo, se a solução representa um vetor com valores numéricos, cada elemento do vetor pode ser codificado como um número real.

No entanto, a representação real tem desvantagens. Os elementos individuais do problema de otimização podem ser independentes e representar espaços multidimensionais não sobrepostos. Isso cria dificuldades na localização da solução global, pois a busca pode ser dificultada pela separação do espaço em subespaços independentes.

A vantagem da representação binária de características está na possibilidade de unir todas as características em uma descrição completa de espaços multidimensionais não sobrepostos. Isso permite conectar espaços multidimensionais separados em um espaço de busca unificado. A representação binária também facilita a execução de operações elementares bit a bit, como o operador "mutação", ao contrário dos números reais, onde são necessárias operações adicionais laboriosas para realizar tais operações, com a representação binária elas são realizadas de forma mais simples.

As desvantagens da representação binária no algoritmo de otimização incluem a necessidade de conversão para números reais, que eventualmente são manipulados pelo problema de otimização, e operações adicionais laboriosas, como o armazenamento da representação binária em um array de comprimento significativo.

Assim, números reais fornecem flexibilidade no trabalho com valores contínuos, enquanto a representação binária permite unir características em um todo e realizar operações bit a bit de maneira mais eficiente. Nos algoritmos de otimização, além dos genéticos, ambos os métodos de representação podem ser usados para obter vantagens de ambos.

3. Vantagens da representação pelo código de Gray binário

Apesar de todas as vantagens da representação binária, ela tem uma desvantagem significativa: dois números decimais próximos na representação binária podem diferir em vários bits de uma só vez. Por exemplo, no código binário, a transição de 7 (0111) para 8 (1000) implica na mudança de todos os quatro bits. Isso significa que é necessário um número diferente de operações bit a bit entre diferentes números próximos, o que leva a uma probabilidade desigual de resultados no espaço de busca, surgindo as chamadas "faixas de alta probabilidade" e, inversamente, "zonas cegas" nos parâmetros otimizados.

Por exemplo, se quisermos realizar uma operação aritmética em dois números que diferem apenas por uma unidade na representação decimal, na representação binária isso pode exigir a mudança de vários bits. Como resultado, a probabilidade de obter o número desejado após a operação será desigual, ao contrário de outro par de números, pois a mudança de cada bit afeta o resultado final. Esse fenômeno pode ser especialmente problemático ao realizar cálculos de ponto flutuante, onde a precisão da representação dos números é muito importante e pequenas mudanças na representação decimal dos números podem levar a mudanças significativas em sua representação binária e, consequentemente, nos resultados dos cálculos.

A representação binária pelo código de Gray, também conhecido como código binário reflexivo, representa cada número como um conjunto de bits, mas cada número sucessivo difere do anterior por apenas um bit alterado. Isso garante uma sequência suave de transição de números, essa propriedade é chamada de "propriedade de distância unitária".

Anteriormente, discutimos que um número "double" pode ser representado por apenas 16 dígitos significativos. Vamos considerar um exemplo para entender melhor como isso pode influenciar na prática.

Suponhamos que temos um número com 15 zeros significativos e um "1" na 16ª posição: "0.0000000000000001". Agora adicione 1.0 a esse número e obtenha "1.0000000000000000". Note que o dígito "1" na 16ª posição desapareceu, e ficamos com 15 dígitos significativos após o ponto decimal. Ao adicionar um novo dígito na parte inteira de um número "double", os dígitos significativos são deslocados para a esquerda. Assim, se tivermos uma parte inteira não nula, não podemos garantir a precisão até a 16ª posição após o ponto decimal.

Na representação binária e, em particular, ao usar o código de Gray, podemos evitar o problema de perda de precisão nas posições, se definirmos esse objetivo ou se isso for necessário no contexto de uma tarefa específica. Vamos explorar este aspecto com interesse.

Os computadores trabalham com programas e números na representação binária, pois é a forma mais eficiente e natural para o processamento de informações pela máquina. No entanto, para conveniência da percepção e escrita de algoritmos de otimização em alto nível, precisaremos de algum esforço adicional para trabalhar com números em forma binária, especialmente no caso de números negativos e números fracionários.

Para trabalhar com números na forma binária em alto nível de programação, existem várias bibliotecas e ferramentas que facilitam o processamento e a representação de números negativos e números fracionários. Mas implementaremos tudo o que for necessário no contexto da escrita de um algoritmo de otimização, na linguagem MQL5.

Para representar números negativos no sistema de numeração binária, é usado o método do complemento de dois. Ele nos permite representar um número negativo invertendo todos os bits do número e adicionando um ao resultado obtido. Mas aplicaremos um pequeno truque e evitaremos operações adicionais ao lidar com números negativos, simplesmente eliminando os números negativos. Suponha que um dos parâmetros otimizáveis tenha limites:

min = -156.675 e max = 456.6789

então a distância entre "max" e "min" é:

distance = max - min = 456.6789 - (-156.675) = 613.3539

Assim, o número desejado no problema de otimização será sempre positivo e estará à direita de 0.0 na linha numérica, com valor máximo igual a 613.3539. Agora, a tarefa é garantir a codificação do número real, para isso, vamos dividir esse número em parte inteira e parte fracionária. A parte inteira no código de Gray será representada da seguinte forma, onde entre parênteses está indicado o método de representação:

613 (decimal) = 1 1 0 1 0 1 0 1 1 1 (binário Gray)

Então, a parte fracionária ficará assim:

3539 (decimal) = 1 0 1 1 0 0 1 1 1 0 1 0 (binário Gray)

Podemos armazenar as partes inteira e fracionária em uma única string, lembrando a quantidade de dígitos usados para ambas as partes, o que nos permitirá fazer a conversão inversa com facilidade. Finalmente, o número real será assim (o símbolo ":" separa as partes inteira e fracionária):

613.3539 (decimal) = 1 1 0 1 0 1 0 1 1 1 :  1 0 1 1 0 0 1 1 1 0 1 0 (binário Gray)

Dessa forma, podemos converter qualquer número real dentro dos limites de 16 dígitos na parte inteira e 16 dígitos após o ponto decimal para números do tipo double. Além disso, isso nos permite ter mais de 16 dígitos significativos no total dos dígitos, até mesmo 32 dígitos significativos ou mais (limitado pelo comprimento do número do tipo ulong, usado nas funções para converter números decimais inteiros para o código de Gray e vice-versa).

Para garantir a precisão da parte fracionária até o 16º dígito, precisaremos converter o número "9 999 999 999 999 999" (o número máximo possível para a parte fracionária):

9999999999999999 (decimal) = 1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (binário Gray)

Então, a representação final do nosso número 613.9999999999999999 (sim, 16 dígitos após o ponto decimal) será assim:

613.9999999999999999 (decimal) = 1 1 0 1 0 1 0 1 1 1 :  1 1 0 0 1 0 0 1 0 0 0 1 0 1 1 0 0 0 1 0 1 1 0 1 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 (binário Gray)

Como podemos ver, o usuário pode definir qualquer precisão após o ponto decimal dentro do comprimento do tipo ulong.

Vamos considerar as funções para converter números decimais inteiros para o código de Gray e vice-versa. Para codificação no código de Gray e decodificação, são usadas funções adicionais para converter para o código binário comum.

A função "DecimalToGray" aceita como parâmetros o número decimal "decimalNumber" e uma referência ao array "array", onde o resultado da conversão será armazenado. Ela realiza a conversão do número do sistema decimal para o código de Gray. Para isso, ela primeiro calcula o valor do código de Gray "grayCode", aplicando a operação bit a bit XOR entre "decimalNumber" e seu deslocamento de um bit para a direita. Em seguida, ela chama a função "IntegerToBinary" para converter o valor obtido "grayCode" para a representação binária e armazená-lo no array "array". Para o array, é usado o armazenamento mais econômico de números inteiros do tipo char.

A função "IntegerToBinary" aceita como parâmetros o número "number" e uma referência ao array "array", onde o resultado da conversão será armazenado. Ela realiza a conversão do número do sistema decimal para o sistema binário. No laço, ela obtém o resto da divisão de "number" por 2 e o adiciona ao array "array". Em seguida, ela divide "number" por 2 e incrementa o contador "cnt". O laço continua enquanto "number" for maior que zero. Após o laço, o array "array" é invertido para obter a ordem correta dos bits.

A função "GrayToDecimal" aceita como parâmetros uma referência ao array "grayCode", o índice inicial "startInd" e o índice final "endInd". Ela realiza a conversão do número do código de Gray para o sistema decimal. Primeiro, ela chama a função "BinaryToInteger" para converter o array "grayCode" na representação binária e armazena-o na variável "grayCodeS". Em seguida, ela inicializa a variável "result" com o valor de "grayCodeS". Depois, ela executa um laço, no qual desloca "grayCodeS" um bit para a direita e aplica a operação bit a bit XOR com "result". O laço continua enquanto "grayCodeS" for deslocado para a direita e for maior que zero. No final, a função retorna o valor de "result".

A função "BinaryToInteger" aceita como parâmetros uma referência ao array "binaryStr", o índice inicial "startInd" e o índice final "endInd". Ela realiza a conversão do número do sistema binário para o sistema decimal. A função inicializa a variável "result" com zero. Em seguida, ela executa um laço, no qual desloca "result" um bit para a esquerda e adiciona o valor de "binaryStr[i]" (bit) a "result". O laço continua de "startInd" a "endInd". No final, a função retorna o valor de "result".

É importante notar que, na conversão reversa do código de Gray, são usados os índices de posição inicial e final. Isso permite extrair apenas determinados números dos parâmetros otimizáveis da "string", onde todos os parâmetros otimizáveis são armazenados. Sabemos o comprimento total da string, incluindo as partes inteira e fracionária, e, portanto, podemos determinar a posição exata dos números na string geral do cromossomo, incluindo o local de junção das partes inteira e fracionária.

//——————————————————————————————————————————————————————————————————————————————
//Converting a decimal number to a Gray code
void DecimalToGray (ulong decimalNumber, char &array [])
{
  ulong grayCode = decimalNumber ^(decimalNumber >> 1);
  IntegerToBinary(grayCode, array);
}

//Converting a decimal number to a binary number
void IntegerToBinary (ulong number, char &array [])
{
  ArrayResize(array, 0);
  ulong temp;
  int cnt = 0;
  while (number > 0)
  {
    ArrayResize (array, cnt + 1);
    temp = number % 2;
    array [cnt] = (char)temp;
    number = number / 2;
    cnt++;
  }

  ArrayReverse (array, 0, WHOLE_ARRAY);
}
//——————————————————————————————————————————————————————————————————————————————

//——————————————————————————————————————————————————————————————————————————————
//Converting from Gray's code to a decimal number
ulong GrayToDecimal (const char &grayCode [], int startInd, int endInd)
{
  ulong grayCodeS = BinaryToInteger(grayCode, startInd, endInd);
  ulong result = grayCodeS;

  while ((grayCodeS >>= 1) > 0)
  {
    result ^= grayCodeS;
  }
  return result;
}

//Converting a binary string to a decimal number
ulong BinaryToInteger (const char &binaryStr [], const int startInd, const int endInd)
{
  ulong result = 0;
  if (startInd == endInd) return 0;

  for (int i = startInd; i <= endInd; i++)
  {
    result = (result << 1) + binaryStr [i];
  }
  return result;
}
//——————————————————————————————————————————————————————————————————————————————

4. Métodos de seleção

Nos algoritmos de otimização, a seleção é o processo de escolha das melhores soluções da população ou do conjunto de candidatos para criar a próxima geração e desempenha um papel crucial nos métodos de otimização. A escolha de uma variante específica de seleção afeta não apenas as capacidades de busca do algoritmo, mas também a velocidade de sua convergência. Todos os métodos de seleção têm suas vantagens e desvantagens e podem ser mais eficazes em alguns algoritmos e menos eficazes em outros. A aplicação de cada um deles depende da estratégia específica de busca.

Existem vários tipos principais de seleção que são usados para escolher indivíduos parentais e formar a nova geração. Vamos examinar detalhadamente cada um desses tipos de seleção:

• Seleção Uniforme (Uniform Selection) — é um método de escolha de indivíduos parentais no qual cada indivíduo tem chances iguais de ser escolhido. Neste método, cada indivíduo na população tem a mesma probabilidade de ser escolhido para a reprodução. A vantagem da seleção uniforme é que ela garante chances iguais para todas as pessoas serem escolhidas. No entanto, esse método não leva em consideração a adaptação dos indivíduos, portanto, pode ser menos eficaz na busca pela solução ideal, especialmente quando alguns indivíduos têm uma adaptação significativamente maior do que outros. A seleção uniforme pode ser útil em alguns casos, por exemplo, quando é necessário explorar diferentes áreas do espaço de soluções ou manter um alto grau de diversidade na população.

• Seleção por Ranking (Rank Selection) — neste método, os indivíduos são classificados de acordo com sua adaptação, e a probabilidade de seleção de um indivíduo depende de sua posição no ranking. Quanto mais alta a posição do indivíduo, maiores são suas chances de ser escolhido. A seleção por ranking pode ser totalmente proporcional, onde a probabilidade de seleção de um indivíduo é proporcional ao seu ranking (número de ordem), ou parcialmente proporcional, onde a probabilidade de seleção de um indivíduo aumenta com o crescimento do ranking de forma não linear. A seleção por ranking tem várias vantagens. Primeiro, permite manter a diversidade na população, pois indivíduos menos adaptados também têm a chance de serem escolhidos. Segundo, ajuda a evitar o problema da convergência prematura, quando a população converge rapidamente para um ótimo local. A seleção por ranking promove a manutenção da diversidade e a exploração de um espaço de soluções mais amplo. A seleção por ranking é semelhante à seleção uniforme, mas dá mais ênfase à escolha de indivíduos mais adaptados, deixando uma chance de serem escolhidos para os menos adaptados.
  

• Seleção por Torneio (Tournament Selection) — neste método, um pequeno subconjunto de indivíduos (chamado de torneio) é escolhido aleatoriamente, e o indivíduo com a maior adaptação é selecionado desse subconjunto. O tamanho do torneio determina quantos indivíduos participarão de cada torneio. A seleção por torneio permite manter a diversidade na população, pois mesmo indivíduos menos adaptados podem ser selecionados devido ao fator aleatório. A seleção por torneio tem várias vantagens. Primeiro, permite levar em conta a aleatoriedade na escolha dos pais, o que promove a diversidade da prole. Segundo, permite escolher pais de qualquer área da população, incluindo tanto os melhores indivíduos quanto os menos adaptados. A seleção por torneio é um dos principais métodos de escolha de pais em algoritmos evolutivos e é frequentemente usada em combinação com outros operadores, como crossover e mutação, para criar uma nova prole e continuar a evolução da população.
  

• Seleção por Roleta (Roulette Wheel Selection) — neste método, cada indivíduo é representado em uma roda de roleta imaginária proporcionalmente à sua adaptação. A roda da roleta "gira" e o indivíduo em que o "ponteiro" parar é escolhido. Quanto maior a adaptação do indivíduo, maior o setor da roda de roleta que ele ocupa e maiores são suas chances de ser escolhido. A seleção por roleta permite escolher pais com probabilidades proporcionais à sua adaptação. Os indivíduos com maior adaptação têm uma chance maior de serem selecionados, mas mesmo os indivíduos menos adaptados têm uma probabilidade não nula de serem escolhidos. Isso permite manter a diversidade genética na população e explorar diferentes regiões do espaço de busca de soluções. No entanto, é importante notar que a seleção por roleta pode ter problemas de convergência prematura, especialmente se houver grandes diferenças na adaptação dos indivíduos. Indivíduos altamente adaptados terão uma chance muito maior de serem escolhidos, o que pode levar à perda de diversidade genética, resultando na predominância de soluções semelhantes e na estagnação em ótimos locais.

Como uma medida adicional que pode ser aplicada junto com qualquer método de seleção, pode-se usar o método do "elitismo". Ele consiste em preservar os melhores indivíduos da população atual e transferi-los para a próxima geração sem alterações. A aplicação do método do "elitismo" permite manter os melhores indivíduos de geração em geração, o que ajuda a manter uma alta adaptação e evitar a perda de informações úteis. Isso contribui para acelerar a convergência do algoritmo e melhorar a qualidade da solução encontrada.

No entanto, é necessário considerar que o uso do "elitismo" pode levar à perda de diversidade genética, especialmente se o nível de elitismo for alto. Portanto, é importante escolher um valor apropriado de elitismo para manter o equilíbrio entre a preservação dos melhores indivíduos e a exploração do espaço de busca de soluções.

5. Tipos de método "crossover"

Crossover (ou cruzamento) é uma das operações mais importantes nos algoritmos genéticos, que imita o processo de cruzamento na evolução natural. Ele consiste em combinar informações genéticas de dois indivíduos parentais para criar descendentes e transmitir características hereditárias aos indivíduos filhos. O crossover é significativo não apenas para a transmissão de informações, mas também tem um enorme impacto nas qualidades combinatórias do algoritmo.

O crossover opera no nível dos genótipos e permite combinar genes dos indivíduos parentais para criar novos descendentes.

O princípio geral do método "crossover" é o seguinte:

1. Escolha dos Indivíduos Parentais: da população são escolhidos dois indivíduos ou mais que irão cruzar.
   
2. Definição do Ponto de Cruzamento: o ponto de cruzamento determina o local onde os cromossomos dos pais serão divididos para criar descendentes.
3. Criação de Descendentes: os cromossomos dos pais são divididos no ponto de cruzamento, e partes dos cromossomos de ambos os pais são combinadas para criar um novo genótipo do descendente. Como resultado do crossover, um ou mais descendentes são formados, que podem ter uma combinação de genes de ambos os pais.

Figura 1. Princípio geral do método "crossover".

Vamos listar os principais tipos de crossover binário:

• Crossover de Ponto Único (Single-Point Crossover): dois cromossomos são divididos em um ponto aleatório, e dois descendentes são formados trocando os segmentos dos cromossomos dos pais após esse ponto.
• Crossover Multiponto (Multi-Point Crossover): semelhante ao crossover de ponto único, mas com vários pontos de ruptura, entre os quais os segmentos dos cromossomos são trocados.
  
• Crossover Uniforme (Uniform Crossover): cada bit do descendente é escolhido independentemente de um dos pais com igual probabilidade.
  
• Crossover Cíclico (Cycle Crossover): determina ciclos de posições que serão trocados entre os pais, mantendo a unicidade dos elementos.
• Crossover Parcialmente Mapeado (PMX - Partially Mapped Crossover): preserva a ordem relativa e a posição dos elementos dos cromossomos parentais, utilizado em problemas onde a ordem é importante, como no problema do caixeiro-viajante.
• Crossover de Ordem (Order Crossover - OX): cria um descendente mantendo a ordem dos genes de um dos pais e herdando os genes faltantes do outro pai na ordem de aparição.
  

Os crossovers também são aplicados não apenas para a representação binária, mas também para a representação real, ou seja, os principais tipos de crossover real incluem:

• Crossover Blend (BLX-α): cria descendentes cujos valores são escolhidos aleatoriamente dentro de um intervalo determinado pelos valores dos pais e pelo parâmetro "α", que expande esse intervalo.
• Crossover Blend Simétrico (SBX - Simulated Binary Crossover): utiliza várias distribuições de probabilidade para gerar descendentes cujos valores estão entre os valores dos pais, considerando o grau de diferença entre eles.
  
• Crossover Codificado em Real (Real-coded Crossover): aplica operações aritméticas aos números reais, por exemplo, através da média ou soma ponderada dos valores dos pais.
  
• Crossover Diferencial (Differential Crossover): utilizado, por exemplo, na evolução diferencial, onde um novo vetor é gerado adicionando a diferença ponderada entre dois indivíduos a um terceiro.
  
• Crossover de Interpolação (Interpolation Crossover): cria descendentes interpolando entre os valores dos pais, podendo incluir interpolação linear ou não linear.
  
• Crossover com Distribuição Normal (Normal Distribution Crossover): os descendentes são gerados utilizando a distribuição normal em torno dos valores dos pais, permitindo explorar o espaço de soluções ao redor dos pontos parentais.
  

6. Tipos de método "mutação"

O operador de mutação é uma das operações principais nos algoritmos genéticos e é usado para introduzir mudanças aleatórias na informação genética dos indivíduos da população. Ele ajuda a explorar novas soluções e evitar a estagnação em ótimos locais.

Na biologia, a mutação é extremamente rara e geralmente tem um impacto limitado na prole. O número de indivíduos de cada espécie na natureza é contado em milhões, portanto, o material genético da população é muito diverso, a menos que se trate de espécies em extinção (há até a definição de "gargalo de garrafa" - um número mínimo de indivíduos abaixo do qual a espécie se extingue). Ao contrário da natureza, na maioria das implementações de algoritmos genéticos, as mutações também são raras, cerca de 1-2%. Isso é especialmente importante nos algoritmos genéticos, onde o tamanho da população geralmente é pequeno, e a endogamia pode se tornar um problema, com becos sem saída evolutivos ocorrendo mais frequentemente do que na evolução biológica. Na biologia, geralmente falamos de populações compostas por milhões de indivíduos, enquanto nos algoritmos genéticos (e nos algoritmos de otimização em geral) lidamos com apenas dezenas ou centenas de indivíduos, e a mutação é a única maneira de adicionar novas informações ao pool genético da população.

Assim, se alguma informação genética estiver ausente na população, a mutação permite introduzir essa informação.

Portanto, a mutação desempenha vários papéis importantes:

1. Exploração de novas soluções: Permite que o algoritmo explore novas soluções potenciais para o problema, que podem estar fora do espaço de soluções explorado pelo cruzamento. A mutação permite que o algoritmo "salte" pelo espaço de soluções e descubra novas opções.
2. Manutenção da diversidade genética: Sem mutação, o algoritmo pode enfrentar o problema de convergência para um ótimo local, onde todos os indivíduos têm informações genéticas semelhantes. A mutação permite fazer mudanças aleatórias, o que ajuda a evitar a convergência prematura e a manter a diversidade na população.
3. Superação de becos sem saída evolutivos: No processo evolutivo, os algoritmos genéticos às vezes podem ficar presos em becos sem saída evolutivos, onde o espaço de soluções está esgotado e não é possível encontrar uma solução melhor. A mutação pode ajudar a superar esses becos sem saída, fazendo mudanças aleatórias que podem abrir novas possibilidades e permitir que o algoritmo avance.

Uma probabilidade de mutação muito alta pode levar à degeneração do algoritmo em uma busca aleatória, enquanto uma probabilidade muito baixa pode levar a problemas de convergência e perda de diversidade.

Para algoritmos com representação binária, podemos destacar os seguintes tipos de métodos de mutação:

• Mutação de ponto único (single-point mutation): neste caso, ocorre a inversão do valor de um bit escolhido aleatoriamente na string binária. Por exemplo, se tivermos a string "101010", a mutação de ponto único pode mudá-la para "100010".
• Mutação de múltiplos pontos (multi-point mutation): neste caso, várias posições aleatórias na string binária são escolhidas, e os valores nessas posições são invertidos. Por exemplo, se tivermos a string "101010", a mutação de múltiplos pontos pode mudá-la para "100000" ou "001010".
  
• Mutação com probabilidade de mudança de cada bit (probability-based mutation) ou mutação estocástica (stochastic mutation): neste caso, cada bit tem uma certa probabilidade de mudar durante a mutação.
  
• Inversão completa (complete inversion): neste caso, ocorre a inversão completa dos bits na string binária. Por exemplo, se tivermos a string "101010", a inversão completa a mudará para "010101".
• Inversão de ponto (point inversion): neste caso, um ponto de ruptura é escolhido aleatoriamente na sequência genética, o cromossomo é dividido em duas partes nesse ponto, e as partes são trocadas de lugar.  

Figura 2. Mutação com probabilidade de mudança de cada bit (probability-based mutation).

Nos algoritmos de otimização com representação real, distinguimos os seguintes tipos de mutações, sobre os quais não entraremos em detalhes:

• Operador de mutação aleatória (Random Mutation Operator).
• Operador de mutação gaussiana (Gaussian Mutation Operator).
• Operador aritmético de desvio real, também conhecido como operador de desvio de número real aritmético (arithmetic real number creep operator).
• Operador geométrico de desvio real, também conhecido como operador de desvio de número real geométrico (geometrical real number creep operator).
• Operador de mutação de potência (power mutation operator).
• Operador de mutação não uniforme de Michalewicz (Michalewicz's non-uniform mutation operator).
• Operador de mutação dinâmica (dynamic mutation operator).

Em geral, em todos os algoritmos de otimização, todas as operações que alteram componentes do espaço de busca, se não houver troca de informações entre os agentes (indivíduos), podem ser chamadas de mutação e, na verdade, são mutações, muitas vezes específicas de acordo com a estratégia de busca do algoritmo.

7. Considerações finais

Esta é a primeira parte do artigo sobre o "Algoritmo Genético Binário", na qual examinamos praticamente todos os métodos utilizados não apenas neste algoritmo, mas também em outros algoritmos populacionais de otimização, mesmo que não utilizem os termos "seleção", "crossover" e "mutação". Ao estudar e entender bem esses métodos, poderemos abordar as tarefas de otimização de maneira mais consciente, e novas ideias para a implementação e modificação de algoritmos conhecidos, bem como para a criação de novos, podem surgir. Também examinamos várias maneiras de representar informações em algoritmos de otimização, suas vantagens e desvantagens, o que pode levar ao surgimento de novas ideias e abordagens frescas.