Algoritmos genéticos: Matemática
Algoritmos genéticos são usados para fins de otimização. Um exemplo desse tipo de fim pode ser o aprendizado neuronet, ou seja, a seleção de valores de peso tais que permitam se chegar ao erro mínimo. Além disso, o algoritmo genético é baseado no método de busca aleatória. O principal problema de buscas aleatórias é o fato de que nós não podemos prever quanto tempo será necessário para a resolução do problema. Para evitar perdas de tempo significativas, são aplicados métodos desenvolvidos na biologia. Especificamente, métodos desenvolvidos nos estudos da origem das espécies e da evolução. Apenas os animais mais aptos sobrevivem durante o processo evolucionário. Como resultado disso, a aptidão de uma população cresce, o que lhe permite se ajustar ao ambiente dinâmico.
Um algoritmo do tipo foi proposto pela primeira vez por John H. Holland, da Universidade de Michigan, EUA, em 1975. Ele foi chamado de Plano reprodutivo de Holland, e é a base de quase todos os tipos de algoritmos genéticos. Contudo, antes de examinarmos este plano mais detalhadamente, vamos discutir a questão de como realidades podem ser codificadas para serem usadas em algoritmos genéticos.
Apresentação de objetos
A biologia nos ensina que qualquer organismo pode ser representado como seu fenótipo, que determina, de fato, o que este objeto é no mundo real, e como seu genótipo, que contém toda a informação sobre este objeto em seu conjunto de cromossomos. Além disso, todo gene, ou seja, todo elemento das informações do genótipo, reflete no fenótipo. Portanto, para resolver o nosso problema, nós temos que apresentar cada caractere do objeto de uma forma tal que possa ser utilizada em um algoritmo genético. Os mecanismos do algoritmo genético também funcionarão no nível do genótipo, sem precisarem de informações sobre o padrão interno do objeto, o que torna esses algoritmos amplamente utilizáveis em uma grande variedade de tarefas diferentes.
As sequências de bits são usadas para a apresentação do genótipo do objeto na variação mais comum do algoritmo genético. Além disso, um gene do genótipo do objeto corresponde a todos os atributos do objeto em seu fenótipo. O gene é uma sequência de bits de comprimento fixo que representa o valor desta característica.
Codificação de atributos de números inteiros
A forma mais simples de codificação desse tipo de atributo é a utilização de seu valor de bits. Então se torna bastante simples usar um gene de um certo comprimento suficiente para representar todos os valores possíveis de um atributo do tipo. Mas, infelizmente, essa forma de codificação possui desvantagens. A principal desvantagem é que os números vizinhos diferem uns dos outros por valores de vários bits. Portanto, 7 e 8, em sua representação de bits, diferem em 4 posições, o que torna o funcionamento do algoritmo genético difícil e aumenta o tempo necessário para a sua convergência. Para evitar isso, é melhor usar a codificação na qual os números vizinhos diferem um dos outros por um número menor de posições. Idealmente, pelo valor de um bit. Esse tipo de codificação é representado pelo código de Gray que é recomendado para a realização de um algoritmo genético. Os valores do código de Gray são fornecidos na tabela abaixo:
Codificação binária | Codificação de Gray | ||||
---|---|---|---|---|---|
Código decimal | Código binário |
Código hexadecimal | Código decimal | Código binário | Código hexadecimal |
0 | 0000 | 0h | 0 | 0000 | 0h |
1 | 0001 | 1h | 1 | 0001 | 1h |
2 | 0010 | 2h | 3 | 0011 | 3h |
3 | 0011 | 3h | 2 | 0010 | 2h |
4 | 0100 | 4h | 6 | 0110 | 6h |
5 | 0101 | 5h | 7 | 0111 | 7h |
6 | 0110 | 6h | 5 | 0101 | 5h |
7 | 0111 | 7h | 4 | 0100 | 4h |
8 | 1000 | 8h | 12 | 1100 | Ch |
9 | 1001 | 9h | 13 | 1101 | Dh |
10 | 1010 | Ah | 15 | 1111 | Fh |
11 | 1011 | Bh | 14 | 1110 | Eh |
12 | 1100 | Ch | 10 | 1010 | Ah |
13 | 1101 | Dh | 11 | 1011 | Bh |
14 | 1110 | Eh | 9 | 1001 | 9h |
15 | 1111 | Fh | 8 | 1000 | 8h |
Portanto, ao codificar um atributo de número inteiro, nós o dividimos em tétrades e transformamos cada tétrade de acordo com as regras da codificação de Gray.
Em realizações práticas de algoritmos genéticos, geralmente não há necessidade de transformar os valores de atributo em valores de gene. Na prática, ocorre o problema inverso, quando é preciso encontrar o valor do atributo a partir do valor do gene correspondente.
Logo, a tarefa de decodificar os valores dos genes, que possuem atributos de número inteiro, é trivial.
Codificação de atributos de ponto flutuante
Neste caso, a forma mais simples de se codificar parece ser o uso da representação de bits. Contudo, essa forma possui as mesmas desvantagens que a de números inteiros. É por isso que, na prática, a seguinte sequência de operações será executada:
- O intervalo inteiro de valores permitidos ao atributo é dividido em partes com a precisão desejada.
- O valor do gene é considerado um número inteiro que numera o intervalo (através do uso do código de Gray).
- O número que é o meio deste intervalo é considerado o valor do parâmetro.
Vamos examinar novamente a sequência de operações acima no seguinte exemplo:
Vamos assumir que os valores do atributo estão na faixa de [0,1]. A faixa foi dividida em 256 intervalos para a codificação. Para codificar o seu número, nós vamos precisar de 8 bits. O valor do gene é, por exemplo, 00100101bG (a letra maiúscula G significa que se trata do código de Gray). Primeiramente, usando o código de Grau, vamos encontrar o número do intervalo correspondente: 25hG->36h->54d. Agora vamos ver qual intervalo corresponde com ele. Através de cálculos simples, nós chegamos ao intervalo de [0,20703125, 0,2109375]. Ou seja, o valor do intervalo será (0,20703125+0,2109375)/2=0,208984375.
Codificação de dados não-numéricos
Os dados não-numéricos devem ser transformados em números antes de serem codificados. Este processo é descrito em maiores detalhes nos artigos contidos no nosso website, que descrevem o uso de redes neurais.
Como determinar o fenótipo do objeto a partir do seu genótipo
Para determinar o fenótipo do objeto (ou seja, os valores dos atributos do objeto), nós precisamos saber apenas os valores dos genes que correspondem a esses atributos (ou seja, o genótipo do objeto). Além disso, a integridade de genes que descrevem o genótipo do objeto representa um cromossomo. Em algumas realizações, ela também é chamada de espécime. Portanto, na realização do algoritmo genético, o cromossomo representa uma sequência de bits de comprimento fixo. Além disso, cada intervalo da sequência corresponde a um gene. O comprimento dos genes no interior de um cromossomo pode ser igual ou diferente. Os genes de comprimento igual são usados mais frequentemente. Vamos considerar um exemplo de um cromossomo e as interpretações do seu valor. Vamos supor que o objeto tenha 5 atributos, cada um codificado em um gene de 4 elementos de comprimento. Portanto o comprimento do cromossomo será de 5*4=20 bits:
0010 | 1010 | 1001 | 0100 | 1101 |
Agora nós podemos determinar os valores dos atributos.
Atributo | Valor do gene | Valor binário do atributo | Valor decimal do atributo | ||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
Atributo 1 | 0010 | 0011 | 3 | ||||||||
Atributo 2 | 1010 | 1100 | 12 | ||||||||
Atributo 3 | 1001 | 1110 | 14 | ||||||||
Atributo 4 | 0100 | 0111 | 7 | ||||||||
Atributo 5 | 1101 | 1001 | 9 |
Os operadores genéticos básicos
Como se sabe, a forma com que as características parentais são passadas à prole é muito importante para a teoria da evolução. Em algoritmos genéticos, o cruzamento é um operador genético usado para variar a programação de um cromossomo, ou vários cromossomos, de uma geração para a outra. Este operador trabalha da seguinte forma:
- duas unidades são selecionadas em uma população para se tornarem pais;
- o ponto de parada é determinado (aleatoriamente, por regra);
- a prole é determinada como a concatenação das partes do primeiro e do segundo pai.
Vamos dar uma olhada no funcionamento deste operador:
Cromossomo_1: | 0000000000 | ||||
Cromossomo_2: | 1111111111 |
Vamos assumir que o ponto de parada está após o terceiro bit do cromossomo, então:
Cromossomo_1: | 0000000000 | >> | 000 | 1111111 | Cromossomo_resultante_1 | ||||||||||||
Cromossomo_2: | 1111111111 | >> | 111 | 0000000 | Cromossomo_resultante_2 |
Então um dos cromossomos resultantes é determinado com uma probabilidade de 0,5 como prole.
O outro operador genético serve para manter a diversidade em uma população: Ele é chamado de operador mutação. Este é o operador que altera um ou mais valores do gene em um cromossomo em relação ao seu estado inicial. Conformemente, todo bit em um cromossomo é invertido com uma certa probabilidade.
Além disso, mais um operador é usado, chamado inversão. Ele divide o cromossomo em duas partes, que então invertem posições. Isso pode ser representado esquematicamente da seguinte forma:
000 | 1111111 | >> | 1111111 | 000 |
Teoricamente, estes dois operadores genéticos são suficientes para criar a função do algoritmo genético. Contudo, na prática, são usados alguns operadores adicionais, assim como modificações desses dois operadores. Por exemplo, pode haver não apenas um cruzamento de ponto único (descrito acima), mas também um de pontos múltiplos. Neste último caso, vários pontos de parada (geralmente dois) são criados. Além disso, em algumas implementações do algoritmo, o operador mutação realiza a inversão de apenas um bit, escolhido aleatoriamente, de um cromossomo.
Fluxograma do algoritmo genético
Agora que sabemos como interpretar os valores do gene, nós podemos discutir como o algoritmo genético funciona. Vamos examinar mais detalhadamente o fluxograma do algoritmo genético em sua representação clássica.
- Inicialize o tempo de início, t=0. Forme aleatoriamente a população inicial que consiste em k unidades. B0 = {A1,A2,…,Ak)
- Calcule a aptidão de cada unidade, FAi = fit(Ai) , i=1…k, e a aptidão da população inteira, Ft = fit(Bt). O valor dessa função determina até que ponto a unidade descrita por este cromossomo é adequada para resolver o problema.
- Selecione a unidade Ac da população. Ac = Get(Bt)
- Selecione a segunda unidade da população com uma determinada probabilidade (a probabilidade Pc de cruzamento), Аc1 = Get(Bt), e execute o operador cruzamento, Ac = Cruzamento(Ac,Ac1).
- Execute o operador mutação com uma determinada probabilidade (a probabilidade Pm de mutação), Ac = mutação(Ac).
- Execute o operador inversão com uma determinada probabilidade (a probabilidade Pi de inversão), Ac = mutação(Ac).
- Coloque o novo cromossomo obtido na nova população, insert(Bt+1,Ac).
- Os passos 3 a 7 devem ser repetidos k vezes.
- Aumente o número do período atual, t=t+1.
- Caso a condição de parada seja alcançada, encerre o ciclo. Do contrário, vá ao passo 2.
Alguns estágios do algoritmo exigem consideração mais atenta.
Os passos 3 e 4, o estágio de seleção dos cromossomos pais, desempenham o papel mais importante no funcionamento bem sucedido do algoritmo. Podem haver várias alterativas possíveis a ele. O método de seleção usado com maior frequência é chamado roleta. Quando este método é usado, a probabilidade um determinado cromossomo ser selecionado é determinada pela sua aptidão, ou seja, PGet(Ai) ~ Fit(Ai)/Fit(Bt). O uso deste método resulta em um aumento da probabilidade de que atributos pertencentes a unidades mais bem ajustadas se propaguem pela prole. Outro método usado frequentemente é a seleção por torneio. Nele, várias unidades (2, por regra) são selecionadas aleatoriamente entre a população. A unidade mais apta será selecionada como vencedora. Além disso, em algumas implementações do algoritmo, é usada a chamada estratégia do elitismo, o que significa que as unidades mais bem ajustadas possuem a garantia de entrar na nova população. Essa abordagem geralmente permite a aceleração da convergência do algoritmo genético. A desvantagem dessa estratégia é a probabilidade aumentada do algoritmo chegar ao mínimo local.
A determinação dos critérios de parada do algoritmo é outro ponto importante. Usam-se como estes critérios ou a limitação dos períodos de funcionamento do algoritmo ou a determinação da convergência do algoritmo (normalmente através da comparação da aptidão da população em vários períodos para que se pare quando este parâmetro estabilize).
Traduzido do russo pela MetaQuotes Ltd.
Artigo original: https://www.mql5.com/ru/articles/1408
- Aplicativos de negociação gratuitos
- 8 000+ sinais para cópia
- Notícias econômicas para análise dos mercados financeiros
Você concorda com a política do site e com os termos de uso