Download MetaTrader 5

Algoritmos genéticos: Matemática

18 fevereiro 2016, 12:16
MetaQuotes Software Corp.
0
415

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
Tabela 1. Concordância de códigos binários e códigos de Gray

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:

  1. O intervalo inteiro de valores permitidos ao atributo é dividido em partes com a precisão desejada.
  2. O valor do gene é considerado um número inteiro que numera o intervalo (através do uso do código de Gray).
  3. 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:

  1. duas unidades são selecionadas em uma população para se tornarem pais;
  2. o ponto de parada é determinado (aleatoriamente, por regra);
  3. 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.

  1. Inicialize o tempo de início, t=0. Forme aleatoriamente a população inicial que consiste em k unidades. B0 = {A1,A2,…,Ak)
  2. 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.
  3. Selecione a unidade Ac da população. Ac = Get(Bt)
  4. 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).
  5. Execute o operador mutação com uma determinada probabilidade (a probabilidade Pm de mutação), Ac = mutação(Ac).
  6. Execute o operador inversão com uma determinada probabilidade (a probabilidade Pi de inversão), Ac = mutação(Ac).
  7. Coloque o novo cromossomo obtido na nova população, insert(Bt+1,Ac).
  8. Os passos 3 a 7 devem ser repetidos k vezes.
  9. Aumente o número do período atual, t=t+1.
  10. 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 por MetaQuotes Software Corp.
Artigo original: https://www.mql5.com/ru/articles/1408

Gráficos "sem buracos" Gráficos "sem buracos"

O artigo trata da realização de gráficos sem barras puladas.

Comentador do sistema do expert. Uso prático dos indicadores integrados a um programa MQL4 Comentador do sistema do expert. Uso prático dos indicadores integrados a um programa MQL4

O artigo descreve o uso de indicadores técnicos na programação com o MQL4.

Algoritmos genéticos vs. busca simples no otimizador do MetaTrader 4 Algoritmos genéticos vs. busca simples no otimizador do MetaTrader 4

O artigo compara o tempo e os resultados obtidos pela otimização dos Expert Advisors usando algoritmos genéticos e aqueles obtidos por buscas simples.

O MQL4 como uma ferramenta do trader, ou a análise técnica avançada O MQL4 como uma ferramenta do trader, ou a análise técnica avançada

As transações comerciais são, antes de tudo, um cálculo de probabilidades. O ditado que diz que o ócio é um motivador do progresso revela a razão pela qual todos os indicadores e sistemas de transações que conhecemos foram desenvolvidos. O fato é que a maioria dos novatos no mundo das transações estuda teorias "prontas" de transação. Mas, por sorte, há ainda mais segredos de mercado a serem descobertos, e as ferramentas usadas na análise de movimentos de preços existem, basicamente, sob a forma de indicadores técnicos e conjuntos matemáticos ou estatísticos não realizados. Devemos agradecer a Bill Williams por sua contribuição à teoria dos movimentos de mercado. Mas talvez ainda seja cedo para descansar.