Programação de expressão gênica - Gene expression programming

Na programação de computadores , programação de expressão genética (GEP) é um algoritmo evolutivo que cria programas de computador ou modelos. Esses programas de computador são estruturas de árvore complexas que aprendem e se adaptam mudando seus tamanhos, formas e composição, como um organismo vivo. E, como os organismos vivos, os programas de computador do GEP também são codificados em cromossomos lineares simples de comprimento fixo. Assim, o GEP é um sistema genótipo-fenótipo , que se beneficia de um genoma simples para manter e transmitir a informação genética e de um fenótipo complexo para explorar o ambiente e se adaptar a ele.

Fundo

Algoritmos evolutivos utilizar populações de indivíduos, indivíduos selecionados de acordo com a aptidão e introduzir variação genética usando um ou mais operadores genéticos . Seu uso em sistemas computacionais artificiais remonta à década de 1950, onde eram usados ​​para resolver problemas de otimização (por exemplo, Box 1957 e Friedman 1959). Mas foi com a introdução das estratégias de evolução por Rechenberg em 1965 que os algoritmos evolutivos ganharam popularidade. Um bom texto de visão geral sobre algoritmos evolutivos é o livro "An Introduction to Genetic Algorithms" de Mitchell (1996).

A programação da expressão gênica pertence à família dos algoritmos evolutivos e está intimamente relacionada aos algoritmos genéticos e à programação genética . De algoritmos genéticos, ele herdou os cromossomos lineares de comprimento fixo; e da programação genética herdou as árvores de análise expressivas de tamanhos e formas variadas.

Na programação de expressão gênica, os cromossomos lineares funcionam como o genótipo e as árvores de análise como o fenótipo, criando um sistema genótipo / fenótipo . Este sistema de genótipo / fenótipo é multigênico , codificando várias árvores de análise em cada cromossomo. Isso significa que os programas de computador criados pelo GEP são compostos de várias árvores de análise. Como essas árvores de análise são o resultado da expressão gênica, no GEP elas são chamadas de árvores de expressão .

Codificação: o genótipo

O genoma da programação da expressão gênica consiste em uma cadeia linear simbólica ou cromossomo de comprimento fixo composto por um ou mais genes de igual tamanho. Esses genes, apesar de seu comprimento fixo, codificam para árvores de expressão de diferentes tamanhos e formas. Um exemplo de um cromossomo com dois genes, cada um de tamanho 9, é a string (a posição zero indica o início de cada gene):

012345678012345678
L+a-baccd**cLabacd

onde “L” representa a função logaritmo natural e “a”, “b”, “c” e “d” representam as variáveis ​​e constantes usadas em um problema.

Árvores de expressão: o fenótipo

Como mostrado acima , os genes de programação de expressão gênica têm todos o mesmo tamanho. No entanto, essas strings de comprimento fixo codificam para árvores de expressão de tamanhos diferentes. Isso significa que o tamanho das regiões codificantes varia de gene para gene, permitindo que a adaptação e a evolução ocorram suavemente.

Por exemplo, a expressão matemática:

também pode ser representado como uma árvore de expressão :

Árvore de expressão GEP, expressão k Q * - + abcd.png

onde "Q" representa a função de raiz quadrada.

Este tipo de árvore de expressão consiste na expressão fenotípica de genes GEP, enquanto os genes são cadeias lineares que codificam essas estruturas complexas. Para este exemplo específico, a string linear corresponde a:

01234567
Q*-+abcd

que é a leitura direta da árvore de expressão de cima para baixo e da esquerda para a direita. Essas strings lineares são chamadas de k-expressões (da notação Karva ).

Ir de k-expressões para árvores de expressão também é muito simples. Por exemplo, a seguinte expressão k:

01234567890
Q*b**+baQba

é composto por dois terminais diferentes (as variáveis ​​“a” e “b”), duas funções diferentes de dois argumentos (“*” e “+”), e uma função de um argumento (“Q”). Sua expressão dá:

Árvore de expressão GEP, expressão k Q * b ** + baQba.png

Expressões K e genes

As k-expressões da programação da expressão gênica correspondem à região dos genes que são expressos. Isso significa que pode haver sequências nos genes que não são expressas, o que de fato é verdadeiro para a maioria dos genes. A razão para essas regiões não codificantes é fornecer um buffer de terminais de forma que todas as k-expressões codificadas em genes GEP correspondam sempre a programas ou expressões válidas.

Os genes da programação da expressão gênica são, portanto, compostos de dois domínios diferentes - uma cabeça e uma cauda - cada um com propriedades e funções diferentes. A cabeça é usada principalmente para codificar as funções e variáveis ​​escolhidas para resolver o problema em questão, enquanto a cauda, ​​embora também seja usada para codificar as variáveis, fornece essencialmente um reservatório de terminais para garantir que todos os programas estejam livres de erros.

Para genes GEP, o comprimento da cauda é dado pela fórmula:

em que h é o comprimento da cabeça e n max é máxima aridade. Por exemplo, para um gene criado usando o conjunto de funções F = {Q, +, -, ∗, /} e o conjunto de terminais T = {a, b}, n max = 2. E se escolhermos um comprimento de cabeça de 15, em seguida, t = 15 (2-1) +1 = 16, o que dá um comprimento gene g de 15 + 16 = 31. A cadeia gerada aleatoriamente abaixo é um exemplo de um tal gene:

0123456789012345678901234567890
*b+a-aQab+//+b+babbabbbababbaaa

Ele codifica a árvore de expressão:

Árvore de expressão GEP, expressão k * b + a-aQa.png

que, neste caso, usa apenas 8 dos 31 elementos que constituem o gene.

Não é difícil perceber que, apesar de seu comprimento fixo, cada gene tem potencial para codificar árvores de expressão de diferentes tamanhos e formas, sendo a mais simples composta por apenas um nó (quando o primeiro elemento de um gene é um terminal) e o o maior é composto por tantos nós quantos forem os elementos do gene (quando todos os elementos da cabeça são funções com aridade máxima).

Também não é difícil ver que é trivial implementar todos os tipos de modificação genética ( mutação , inversão, inserção, recombinação e assim por diante) com a garantia de que todos os descendentes resultantes codificam programas corretos e sem erros.

Cromossomos multigênicos

Os cromossomos da programação da expressão gênica são geralmente compostos por mais de um gene de igual comprimento. Cada gene codifica para uma árvore de subexpressão (sub-ET) ou subprograma. Então, os sub-ETs podem interagir uns com os outros de maneiras diferentes, formando um programa mais complexo. A figura mostra um exemplo de programa composto por três sub-ETs.

Expressão de genes GEP como sub-ETs. a) Um cromossomo três gênico com as caudas mostradas em negrito. b) Os sub-ETs codificados por cada gene.

No programa final, os sub-ETs podem ser vinculados por adição ou alguma outra função, pois não há restrições para o tipo de função de vinculação que se pode escolher. Alguns exemplos de linkers mais complexos incluem tirar a média, a mediana, o midrange, limitar sua soma para fazer uma classificação binomial, aplicar a função sigmóide para calcular uma probabilidade e assim por diante. Essas funções de ligação são geralmente escolhidas a priori para cada problema, mas também podem ser desenvolvidas de maneira elegante e eficiente pelo sistema celular de programação de expressão gênica.

Células e reutilização de código

Na programação de expressão gênica, os genes homeóticos controlam as interações dos diferentes sub-ETs ou módulos do programa principal. A expressão desses genes resulta em diferentes programas ou células principais, ou seja, eles determinam quais genes se expressam em cada célula e como os sub-ETs de cada célula interagem entre si. Em outras palavras, os genes homeóticos determinam quais sub-ETs são chamados e com que freqüência em que programa ou célula principal e que tipo de conexões eles estabelecem entre si.

Genes homeóticos e o sistema celular

Os genes homeóticos têm exatamente o mesmo tipo de organização estrutural dos genes normais e são construídos por meio de um processo idêntico. Eles também contêm um domínio da cabeça e um domínio da cauda, ​​com a diferença de que as cabeças agora contêm funções de ligação e um tipo especial de terminais - terminais gênicos - que representam os genes normais. A expressão dos genes normais resulta normalmente em diferentes sub-ETs, que no sistema celular são chamados de ADFs (funções definidas automaticamente). Já as caudas contêm apenas terminais gênicos, ou seja, recursos derivados gerados em tempo real pelo algoritmo.

Por exemplo, o cromossomo na figura tem três genes normais e um gene homeótico e codifica um programa principal que invoca três funções diferentes em um total de quatro vezes, ligando-as de uma maneira particular.

Expressão de um sistema unicelular com três ADFs. a) O cromossomo é composto por três genes convencionais e um gene homeótico (mostrado em negrito). b) Os ADFs codificados por cada gene convencional. c) O programa ou célula principal.

A partir deste exemplo, fica claro que o sistema celular não apenas permite a evolução irrestrita das funções de ligação, mas também a reutilização de código. E não deve ser difícil implementar recursão neste sistema.

Vários programas principais e sistemas multicelulares

Os sistemas multicelulares são compostos por mais de um gene homeótico . Cada gene homeótico neste sistema reúne uma combinação diferente de árvores de subexpressão ou ADFs, criando várias células ou programas principais.

Por exemplo, o programa mostrado na figura foi criado usando um sistema celular com duas células e três genes normais.

Expressão de um sistema multicelular com três ADFs e dois programas principais. a) O cromossomo composto por três genes convencionais e dois genes homeóticos (mostrados em negrito). b) Os ADFs codificados por cada gene convencional. c) Dois programas principais diferentes expressos em duas células diferentes.

As aplicações desses sistemas multicelulares são múltiplas e variadas e, como os sistemas multigênicos , eles podem ser usados ​​tanto em problemas com apenas uma saída quanto em problemas com saídas múltiplas.

Outros níveis de complexidade

O domínio cabeça / cauda dos genes GEP (normais e homeóticos) é o bloco de construção básico de todos os algoritmos GEP. No entanto, a programação de expressão gênica também explora outras organizações cromossômicas que são mais complexas do que a estrutura cabeça / cauda. Essencialmente, essas estruturas complexas consistem em unidades funcionais ou genes com um domínio básico cabeça / cauda mais um ou mais domínios extras. Esses domínios extras geralmente codificam constantes numéricas aleatórias que o algoritmo afina implacavelmente para encontrar uma boa solução. Por exemplo, essas constantes numéricas podem ser os pesos ou fatores em um problema de aproximação de função (consulte o algoritmo GEP-RNC abaixo); eles podem ser os pesos e limites de uma rede neural (consulte o algoritmo GEP-NN abaixo); as constantes numéricas necessárias para o projeto de árvores de decisão (consulte o algoritmo GEP-DT abaixo); os pesos necessários para indução polinomial; ou as constantes numéricas aleatórias usadas para descobrir os valores dos parâmetros em uma tarefa de otimização de parâmetros.

O algoritmo básico de expressão gênica

As etapas fundamentais do algoritmo básico de expressão gênica estão listadas abaixo em pseudocódigo:

  1. Selecione o conjunto de funções;
  2. Selecione o conjunto de terminais;
  3. Carregar conjunto de dados para avaliação de aptidão;
  4. Crie cromossomos da população inicial aleatoriamente;
  5. Para cada programa na população:
    1. Cromossomo expresso;
    2. Execute o programa;
    3. Avalie a aptidão;
  6. Verifique a condição de parada;
  7. Selecione programas;
  8. Replicar programas selecionados para formar a próxima população;
  9. Modifique os cromossomos usando operadores genéticos;
  10. Vá para a etapa 5.

As primeiras quatro etapas preparam todos os ingredientes necessários para o loop iterativo do algoritmo (etapas 5 a 10). Destas etapas preparativas, a crucial é a criação da população inicial, que é criada aleatoriamente usando os elementos dos conjuntos de funções e terminais.

Populações de programas

Como todos os algoritmos evolutivos, a programação da expressão gênica funciona com populações de indivíduos, que neste caso são programas de computador. Portanto, algum tipo de população inicial deve ser criada para iniciar as coisas. As populações subsequentes são descendentes, via seleção e modificação genética , da população inicial.

No sistema genótipo / fenótipo de programação de expressão gênica, é necessário apenas criar os cromossomos lineares simples dos indivíduos sem se preocupar com a solidez estrutural dos programas para os quais codificam, pois sua expressão sempre resulta em programas sintaticamente corretos.

Funções de fitness e o ambiente de seleção

As funções de condicionamento físico e os ambientes de seleção (chamados de conjuntos de dados de treinamento no aprendizado de máquina ) são as duas facetas do condicionamento físico e, portanto, estão intimamente conectados. Na verdade, a aptidão de um programa depende não apenas da função de custo usada para medir seu desempenho, mas também dos dados de treinamento escolhidos para avaliar a aptidão

O ambiente de seleção ou dados de treinamento

O ambiente de seleção consiste no conjunto de registros de treinamento, também chamados de casos de fitness. Esses casos de aptidão podem ser um conjunto de observações ou medições relativas a algum problema e formam o que é chamado de conjunto de dados de treinamento.

A qualidade dos dados de treinamento é essencial para a evolução de boas soluções. Um bom conjunto de treinamento deve ser representativo do problema em questão e também bem equilibrado, caso contrário, o algoritmo pode travar em algum ótimo local. Além disso, também é importante evitar o uso de conjuntos de dados desnecessariamente grandes para treinamento, pois isso tornará as coisas mais lentas desnecessariamente. Uma boa regra prática é escolher registros suficientes para treinamento para permitir uma boa generalização nos dados de validação e deixar os registros restantes para validação e teste.

Funções de fitness

Em termos gerais, existem essencialmente três tipos diferentes de problemas com base no tipo de previsão que está sendo feita:

  1. Problemas envolvendo previsões numéricas (contínuas);
  2. Problemas envolvendo previsões categóricas ou nominais, binomiais e multinomiais;
  3. Problemas envolvendo previsões binárias ou booleanas.

O primeiro tipo de problema é conhecido como regressão ; a segunda é conhecida como classificação , com a regressão logística como um caso especial onde, além das classificações nítidas como "Sim" ou "Não", uma probabilidade também é atribuída a cada resultado; e o último está relacionado à álgebra booleana e síntese lógica .

Funções de fitness para regressão

Na regressão , a resposta ou variável dependente é numérica (geralmente contínua) e, portanto, a saída de um modelo de regressão também é contínua. Portanto, é bastante simples avaliar a adequação dos modelos em evolução, comparando a saída do modelo com o valor da resposta nos dados de treinamento.

Existem várias funções básicas de adequação para avaliar o desempenho do modelo, sendo a mais comum baseada no erro ou residual entre a saída do modelo e o valor real. Tais funções incluem o erro médio quadrático , raiz do erro quadrático médio , erro médio absoluto , erro quadrado relativa, raiz relativa erro quadrado, erro absoluto relativo, e outros.

Todas essas medidas padrão oferecem uma granularidade fina ou suavidade para o espaço de solução e, portanto, funcionam muito bem para a maioria das aplicações. Mas alguns problemas podem exigir uma evolução mais grosseira, como determinar se uma previsão está dentro de um determinado intervalo, por exemplo, menos de 10% do valor real. No entanto, mesmo se alguém estiver interessado apenas em contar os acertos (ou seja, uma predição que está dentro do intervalo escolhido), fazer com que as populações de modelos evoluam com base apenas no número de acertos que cada pontuação de programa geralmente não é muito eficiente devido ao grosso granularidade da paisagem de fitness . Assim, a solução geralmente envolve a combinação dessas medidas grosseiras com algum tipo de função suave, como as medidas de erro padrão listadas acima.

As funções de aptidão baseadas no coeficiente de correlação e R-quadrado também são muito suaves. Para problemas de regressão, essas funções funcionam melhor combinando-as com outras medidas porque, por si mesmas, elas tendem apenas a medir a correlação , não se importando com a faixa de valores de saída do modelo. Portanto, ao combiná-los com funções que trabalham na aproximação da faixa dos valores alvo, eles formam funções de adequação muito eficientes para encontrar modelos com boa correlação e bom ajuste entre os valores previstos e reais.

Funções de fitness para classificação e regressão logística

O projeto de funções de adequação para classificação e regressão logística tira proveito de três características diferentes de modelos de classificação. O mais óbvio é apenas contar os acertos, ou seja, se um registro for classificado corretamente é contabilizado como acerto. Esta função de adequação é muito simples e funciona bem para problemas simples, mas para problemas mais complexos ou conjuntos de dados altamente desequilibrados, ela fornece resultados ruins.

Uma maneira de melhorar esse tipo de função de aptidão baseada em acertos consiste em expandir a noção de classificações corretas e incorretas. Em uma tarefa de classificação binária, as classificações corretas podem ser 00 ou 11. A representação "00" significa que um caso negativo (representado por "0") foi classificado corretamente, enquanto "11" significa que um caso positivo (representado por "1 ”) Foi classificado corretamente. As classificações do tipo "00" são chamadas de verdadeiros negativos (TN) e "11" verdadeiros positivos (TP).

Existem também dois tipos de classificações incorretas e são representados por 01 e 10. São chamados de falsos positivos (FP) quando o valor real é 0 e o modelo prevê 1; e falsos negativos (FN) quando o alvo é 1 e o modelo prevê um 0. As contagens de TP, TN, FP e FN são geralmente mantidas em uma tabela conhecida como matriz de confusão .

Matriz de confusão para uma tarefa de classificação binomial.
  Aula prevista
sim Não

Aula real
sim TP FN
Não FP TN

Portanto, contando TP, TN, FP e FN e atribuindo pesos diferentes a esses quatro tipos de classificações, é possível criar funções de aptidão mais suaves e, portanto, mais eficientes. Algumas funções de fitness populares baseadas na matriz de confusão incluem sensibilidade / especificidade , recall / precisão , medida F , similaridade de Jaccard , coeficiente de correlação de Matthews e matriz de custo / ganho que combina os custos e ganhos atribuídos aos 4 tipos diferentes de classificações.

Essas funções baseadas na matriz de confusão são bastante sofisticadas e adequadas para resolver a maioria dos problemas de forma eficiente. Mas há outra dimensão para os modelos de classificação que é a chave para explorar de forma mais eficiente o espaço de solução e, portanto, resulta na descoberta de melhores classificadores. Essa nova dimensão envolve a exploração da estrutura do próprio modelo, que inclui não apenas o domínio e o intervalo, mas também a distribuição da saída do modelo e a margem do classificador.

Explorando essa outra dimensão dos modelos de classificação e, em seguida, combinando as informações sobre o modelo com a matriz de confusão, é possível projetar funções de fitness muito sofisticadas que permitem a exploração suave do espaço de solução. Por exemplo, pode-se combinar alguma medida com base na matriz de confusão com o erro quadrático médio avaliado entre os resultados do modelo bruto e os valores reais. Ou combine a medida F com o quadrado R avaliado para a saída do modelo bruto e o destino; ou a matriz de custo / ganho com o coeficiente de correlação e assim por diante. As funções de aptidão mais exóticas que exploram a granularidade do modelo incluem a área sob a curva ROC e a medida de classificação.

Também relacionada a essa nova dimensão dos modelos de classificação, está a ideia de atribuir probabilidades à saída do modelo, que é o que se faz na regressão logística . Então, também é possível usar essas probabilidades e avaliar o erro quadrático médio (ou alguma outra medida semelhante) entre as probabilidades e os valores reais e, em seguida, combinar isso com a matriz de confusão para criar funções de adequação muito eficientes para regressão logística. Exemplos populares de funções de adequação com base nas probabilidades incluem estimativa de máxima verossimilhança e perda de dobradiça .

Funções de fitness para problemas booleanos

Na lógica, não há estrutura de modelo (conforme definido acima para classificação e regressão logística) para explorar: o domínio e a gama de funções lógicas compreende apenas 0's e 1's ou falso e verdadeiro. Portanto, as funções de aptidão disponíveis para álgebra booleana só podem ser baseadas nos acertos ou na matriz de confusão, conforme explicado na seção acima .

Seleção e elitismo

A seleção da roda da roleta é talvez o esquema de seleção mais popular usado na computação evolutiva. Envolve mapear a aptidão de cada programa para uma fatia da roda da roleta proporcional à sua aptidão. Em seguida, a roleta é girada tantas vezes quanto houver programas na população, a fim de manter o tamanho da população constante. Assim, com a roleta, os programas de seleção são selecionados de acordo com a aptidão e a sorte do sorteio, o que significa que algumas vezes as melhores características podem ser perdidas. Porém, ao combinar a seleção da roleta com a clonagem do melhor programa de cada geração, garante-se que pelo menos as melhores características não sejam perdidas. Esta técnica de clonagem do melhor programa de geração é conhecida como elitismo simples e é usada pela maioria dos esquemas de seleção estocástica.

Reprodução com modificação

A reprodução de programas envolve primeiro a seleção e depois a reprodução de seus genomas. A modificação do genoma não é necessária para a reprodução, mas sem ela a adaptação e a evolução não ocorrerão.

Replicação e seleção

O operador de seleção seleciona os programas para o operador de replicação copiar. Dependendo do esquema de seleção, o número de cópias que um programa origina pode variar, com alguns programas sendo copiados mais de uma vez, enquanto outros são copiados apenas uma vez ou não. Além disso, a seleção geralmente é configurada de forma que o tamanho da população permaneça constante de uma geração para outra.

A replicação de genomas na natureza é muito complexa e os cientistas demoraram muito para descobrir a dupla hélice do DNA e propor um mecanismo para sua replicação. Mas a replicação de strings é trivial em sistemas evolucionários artificiais, onde apenas uma instrução para copiar strings é necessária para passar todas as informações no genoma de geração em geração.

A replicação dos programas selecionados é uma peça fundamental de todos os sistemas evolutivos artificiais, mas para que a evolução ocorra ela precisa ser implementada não com a precisão usual de uma instrução de cópia, mas sim com alguns erros inseridos. De fato, a diversidade genética é criado com operadores genéticos como mutação , recombinação , transposição , inversão e muitos outros.

Mutação

Na programação da expressão gênica, a mutação é o operador genético mais importante. Ele muda o genoma ao trocar um elemento por outro. O acúmulo de muitas pequenas mudanças ao longo do tempo pode criar grande diversidade.

Na programação da expressão gênica, a mutação é totalmente irrestrita, o que significa que em cada domínio gênico qualquer símbolo de domínio pode ser substituído por outro. Por exemplo, nos chefes dos genes, qualquer função pode ser substituída por um terminal ou outra função, independentemente do número de argumentos nessa nova função; e um terminal pode ser substituído por uma função ou outro terminal.

Recombinação

A recombinação geralmente envolve dois cromossomos pais para criar dois novos cromossomos combinando diferentes partes dos cromossomos pais. E, desde que os cromossomos pais estejam alinhados e os fragmentos trocados sejam homólogos (isto é, ocupem a mesma posição no cromossomo), os novos cromossomos criados pela recombinação sempre codificarão programas sintaticamente corretos.

Diferentes tipos de crossover são facilmente implementados alterando o número de pais envolvidos (não há razão para escolher apenas dois); o número de pontos de divisão; ou a forma como alguém escolhe trocar os fragmentos, por exemplo, aleatoriamente ou de alguma forma ordenada. Por exemplo, a recombinação de genes, que é um caso especial de recombinação, pode ser feita pela troca de genes homólogos (genes que ocupam a mesma posição no cromossomo) ou pela troca de genes escolhidos aleatoriamente em qualquer posição no cromossomo.

Transposição

A transposição envolve a introdução de uma sequência de inserção em algum lugar de um cromossomo. Na programação da expressão gênica, as sequências de inserção podem aparecer em qualquer parte do cromossomo, mas são inseridas apenas nas cabeças dos genes. Este método garante que mesmo as sequências de inserção das caudas resultem em programas sem erros.

Para que a transposição funcione corretamente, ela deve preservar o comprimento dos cromossomos e a estrutura do gene. Assim, na programação de expressão gênica, a transposição pode ser implementada usando dois métodos diferentes: o primeiro cria um deslocamento no local de inserção, seguido por uma deleção no final da cabeça; o segundo substitui a sequência local no site de destino e, portanto, é mais fácil de implementar. Ambos os métodos podem ser implementados para operar entre cromossomos ou dentro de um cromossomo ou mesmo dentro de um único gene.

Inversão

A inversão é um operador interessante, especialmente poderoso para otimização combinatória . Consiste em inverter uma pequena sequência dentro de um cromossomo.

Na programação de expressão gênica, ele pode ser facilmente implementado em todos os domínios gênicos e, em todos os casos, a prole produzida é sempre sintaticamente correta. Para qualquer domínio de gene, uma sequência (variando de pelo menos dois elementos a tão grande quanto o próprio domínio) é escolhida aleatoriamente dentro desse domínio e, em seguida, invertida.

Outros operadores genéticos

Existem vários outros operadores genéticos e na programação da expressão gênica, com seus diferentes genes e domínios gênicos, as possibilidades são infinitas. Por exemplo, operadores genéticos, como recombinação de um ponto, recombinação de dois pontos, recombinação de gene, recombinação uniforme, transposição de gene, transposição de raiz, mutação específica de domínio, inversão específica de domínio, transposição específica de domínio e assim por diante, são facilmente implementado e amplamente utilizado.

O algoritmo GEP-RNC

As constantes numéricas são elementos essenciais dos modelos matemáticos e estatísticos e, portanto, são importantes para permitir a sua integração nos modelos concebidos por algoritmos evolutivos.

A programação de expressão gênica resolve esse problema de maneira muito elegante, por meio do uso de um domínio genético extra - o Dc - para lidar com constantes numéricas aleatórias (RNC). Combinando este domínio com um marcador de posição de terminal especial para os RNCs, um sistema ricamente expressivo pode ser criado.

Estruturalmente, o Dc vem depois da cauda, ​​tem um comprimento igual ao tamanho da cauda t e é composto pelos símbolos usados ​​para representar os RNCs.

Por exemplo, abaixo é mostrado um cromossomo simples composto por apenas um gene e tamanho de cabeça de 7 (o Dc se estende pelas posições 15-22):

01234567890123456789012
+?*+?**aaa??aaa68083295

onde o terminal "?” representa o espaço reservado para os RNCs. Este tipo de cromossomo é expresso exatamente como mostrado acima , fornecendo:

Árvore de expressão GEP com espaço reservado para RNCs.png

Em seguida, os? 'S na árvore de expressão são substituídos da esquerda para a direita e de cima para baixo pelos símbolos (para simplificar representados por números) no Dc, dando:

Árvore de expressão GEP com símbolos (numerais) para RNCs.png

Os valores correspondentes a esses símbolos são mantidos em uma matriz. (Para simplificar, o número representado pelo numeral indica a ordem na matriz.) Por exemplo, para a seguinte matriz de 10 elementos de RNCs:

C = {0,611, 1,184, 2,449, 2,98, 0,496, 2,286, 0,93, 2,305, 2,737, 0,755}

a árvore de expressão acima fornece:

Árvore de expressão GEP com RNCs.png

Essa estrutura elegante para lidar com constantes numéricas aleatórias está no coração de diferentes sistemas GEP, como redes neurais GEP e árvores de decisão GEP .

Como o algoritmo básico de expressão gênica , o algoritmo GEP-RNC também é multigênico e seus cromossomos são decodificados como de costume, expressando um gene após o outro e ligando-os todos juntos pelo mesmo tipo de processo de ligação.

Os operadores genéticos usados ​​no sistema GEP-RNC são uma extensão dos operadores genéticos do algoritmo GEP básico (veja acima ), e todos eles podem ser implementados diretamente nesses novos cromossomos. Por outro lado, os operadores básicos de mutação, inversão, transposição e recombinação também são usados ​​no algoritmo GEP-RNC. Além disso, operadores específicos de Dc especiais, como mutação, inversão e transposição, também são usados ​​para ajudar em uma circulação mais eficiente dos RNCs entre programas individuais. Além disso, existe também um operador de mutação especial que permite a introdução permanente de variação no conjunto de RNCs. O conjunto inicial de RNCs é criado aleatoriamente no início de uma execução, o que significa que, para cada gene na população inicial, um número especificado de constantes numéricas, escolhido a partir de um determinado intervalo, é gerado aleatoriamente. Então, sua circulação e mutação são ativadas pelos operadores genéticos.

Redes neurais

Uma rede neural artificial (ANN ou NN) é um dispositivo computacional que consiste em muitas unidades simples conectadas ou neurônios. As conexões entre as unidades são geralmente ponderadas por pesos com valores reais. Esses pesos são o meio principal de aprendizado em redes neurais e um algoritmo de aprendizado é geralmente usado para ajustá-los.

Estruturalmente, uma rede neural tem três classes diferentes de unidades: unidades de entrada, unidades ocultas e unidades de saída. Um padrão de ativação é apresentado nas unidades de entrada e, em seguida, se espalha para frente das unidades de entrada através de uma ou mais camadas de unidades ocultas para as unidades de saída. A ativação que chega em uma unidade de outra unidade é multiplicada pelos pesos nos links sobre os quais ela se espalha. Todas as ativações recebidas são então somadas e a unidade é ativada apenas se o resultado de entrada estiver acima do limite da unidade.

Em resumo, os componentes básicos de uma rede neural são as unidades, as conexões entre as unidades, os pesos e os limites. Portanto, para simular totalmente uma rede neural artificial, deve-se de alguma forma codificar esses componentes em um cromossomo linear e, então, ser capaz de expressá-los de maneira significativa.

Em redes neurais GEP (redes GEP-NN ou GEP), a arquitetura da rede é codificada na estrutura usual de um domínio cabeça / cauda. A cabeça contém funções / neurônios especiais que ativam as unidades ocultas e de saída (no contexto GEP, todas essas unidades são mais apropriadamente chamadas de unidades funcionais) e terminais que representam as unidades de entrada. A cauda, ​​como de costume, contém apenas terminais / unidades de entrada.

Além da cabeça e da cauda, ​​esses genes da rede neural contêm dois domínios adicionais, Dw e Dt, para codificar os pesos e limites da rede neural. Estruturalmente, o Dw vem depois da cauda e seu comprimento d w depende do tamanho da cabeça h e da aridade máxima n max e é avaliado pela fórmula:

O Dt vem depois de Dw e tem um comprimento d t igual a t . Ambos os domínios são compostos de símbolos que representam os pesos e limites da rede neural.

Para cada gene NN, os pesos e limiares são criados no início de cada execução, mas sua circulação e adaptação são garantidas pelos operadores genéticos usuais de mutação , transposição , inversão e recombinação . Além disso, operadores especiais também são usados ​​para permitir um fluxo constante de variação genética no conjunto de pesos e limites.

Por exemplo, abaixo é mostrada uma rede neural com duas unidades de entrada ( i 1 e i 2 ), duas unidades ocultas ( h 1 e h 2 ) e uma unidade de saída ( o 1 ). Tem um total de seis conexões com seis pesos correspondentes representados pelos numerais de 1 a 6 (para simplificar, os limites são todos iguais a 1 e são omitidos):

Rede neural com 5 unidades.png

Essa representação é a representação da rede neural canônica, mas as redes neurais também podem ser representadas por uma árvore, que, neste caso, corresponde a:

Rede neural GEP com 7 nodes.png

onde "a" e "b" representam as duas entradas i 1 e i 2 e "D" representa uma função com conectividade dois. Esta função adiciona todos os seus argumentos ponderados e, em seguida, limita esta ativação a fim de determinar a saída encaminhada. Esta saída (zero ou um neste caso simples) depende do limite de cada unidade, ou seja, se a ativação total de entrada é igual ou maior que o limite, então a saída é um, caso contrário zero.

A árvore NN acima pode ser linearizada da seguinte forma:

0123456789012
DDDabab654321

onde a estrutura nas posições 7–12 (Dw) codifica os pesos. Os valores de cada peso são mantidos em uma matriz e recuperados conforme necessário para a expressão.

Como um exemplo mais concreto, abaixo é mostrado um gene da rede neural para o problema ou exclusivo . Tem um tamanho de cabeça de 3 e tamanho Dw de 6:

0123456789012
DDDabab393257

Sua expressão resulta na seguinte rede neural:

Expressão de uma rede neural GEP para o exclusivo-or.png

que, para o conjunto de pesos:

W = {−1,978, 0,514, −0,465, 1,22, −1,686, −1,797, 0,197, 1,606, 0, 1,753}

dá:

Solução de rede neural GEP para o exclusivo-or.png

que é uma solução perfeita para a função ou exclusiva.

Além de funções booleanas simples com entradas binárias e saídas binárias, o algoritmo GEP-nets pode lidar com todos os tipos de funções ou neurônios (neurônio linear, neurônio tanh, neurônio atan, neurônio logístico, neurônio limite, neurônios de base radial e de base triangular, todos os tipos de neurônios de degrau e assim por diante). Também interessante é que o algoritmo GEP-nets pode usar todos esses neurônios juntos e deixar a evolução decidir quais funcionam melhor para resolver o problema em questão. Portanto, as redes GEP podem ser usadas não apenas em problemas booleanos, mas também em regressão logística , classificação e regressão . Em todos os casos, as redes GEP podem ser implementadas não apenas com sistemas multigênicos, mas também com sistemas celulares , tanto unicelulares quanto multicelulares. Além disso, os problemas de classificação multinomial também podem ser resolvidos de uma vez por redes GEP, tanto com sistemas multigênicos quanto com sistemas multicelulares.

Árvores de decisão

Árvores de decisão (TD) são modelos de classificação onde uma série de perguntas e respostas são mapeadas usando nós e arestas direcionadas.

As árvores de decisão têm três tipos de nós: um nó raiz, nós internos e nós folha ou terminais. O nó raiz e todos os nós internos representam condições de teste para diferentes atributos ou variáveis ​​em um conjunto de dados. Os nós de folha especificam o rótulo de classe para todos os caminhos diferentes na árvore.

A maioria dos algoritmos de indução de árvore de decisão envolve a seleção de um atributo para o nó raiz e, a seguir, toma o mesmo tipo de decisão informada sobre todos os nós de uma árvore.

Árvores de decisão também podem ser criadas por programação de expressão gênica, com a vantagem de que todas as decisões relativas ao crescimento da árvore são feitas pelo próprio algoritmo sem qualquer tipo de entrada humana.

Existem basicamente dois tipos diferentes de algoritmos de TD: um para induzir árvores de decisão com apenas atributos nominais e outro para induzir árvores de decisão com atributos numéricos e nominais. Este aspecto da indução da árvore de decisão também leva à programação de expressão gênica e há dois algoritmos GEP para a indução da árvore de decisão: o algoritmo de árvores de decisão evolucionáveis ​​(EDT) para lidar exclusivamente com atributos nominais e o EDT-RNC (EDT com constantes numéricas aleatórias) para lidar com atributos nominais e numéricos.

Nas árvores de decisão induzidas pela programação de expressão gênica, os atributos se comportam como nós de função no algoritmo básico de expressão gênica , enquanto os rótulos de classe se comportam como terminais. Isso significa que os nós de atributo também têm associado a eles uma aridade ou número de ramos específicos que irão determinar seu crescimento e, em última instância, o crescimento da árvore. Os rótulos de classe se comportam como terminais, o que significa que para uma tarefa de classificação de k -class, um conjunto de terminais com k terminais é usado, representando as k classes diferentes.

As regras para codificar uma árvore de decisão em um genoma linear são muito semelhantes às regras usadas para codificar expressões matemáticas (veja acima ). Assim, para a indução da árvore de decisão, os genes também têm uma cabeça e uma cauda, ​​com a cabeça contendo atributos e terminais e a cauda contendo apenas terminais. Isso novamente garante que todas as árvores de decisão projetadas pelo GEP sejam sempre programas válidos. Além disso, o tamanho da cauda t também é ditado pelo tamanho da cabeça h e o número de ramos do atributo com mais ramos n max e é avaliado pela equação:

Por exemplo, considere a árvore de decisão abaixo para decidir se joga ao ar livre:

Árvore de decisão para jogar fora.png

Ele pode ser codificado linearmente como:

01234567
HOWbaaba

onde “H” representa o atributo Umidade, “O” o atributo Outlook, “W” representa Ventoso e “a” e “b” os rótulos de classe "Sim" e "Não" respectivamente. Observe que as arestas que conectam os nós são propriedades dos dados, especificando o tipo e o número de ramificações de cada atributo e, portanto, não precisam ser codificadas.

O processo de indução da árvore de decisão com programação de expressão gênica começa, como de costume, com uma população inicial de cromossomos criados aleatoriamente. Em seguida, os cromossomos são expressos como árvores de decisão e sua aptidão avaliada em relação a um conjunto de dados de treinamento. De acordo com a aptidão, eles são então selecionados para reproduzir com modificações. Os operadores genéticos são exatamente os mesmos que são usados ​​em um sistema unigênico convencional, por exemplo, mutação , inversão , transposição e recombinação .

Árvores de decisão com atributos nominais e numéricos também são facilmente induzidas com programação de expressão gênica usando a estrutura descrita acima para lidar com constantes numéricas aleatórias. A arquitetura cromossômica inclui um domínio extra para codificar constantes numéricas aleatórias, que são usadas como limites para dividir os dados em cada nó de ramificação. Por exemplo, o gene abaixo com um tamanho de cabeça de 5 (o Dc começa na posição 16):

012345678901234567890
WOTHabababbbabba46336

codifica a árvore de decisão mostrada abaixo:

Árvore de decisão GEP, expressão k WOTHababab.png

Neste sistema, cada nó na cabeça, independentemente do seu tipo (atributo numérico, atributo nominal ou terminal), tem associado a ele uma constante numérica aleatória, que para simplicidade no exemplo acima é representada por um numeral 0-9. Essas constantes numéricas aleatórias são codificadas no domínio Dc e sua expressão segue um esquema muito simples: de cima para baixo e da esquerda para a direita, os elementos em Dc são atribuídos um a um aos elementos na árvore de decisão. Portanto, para a seguinte matriz de RNCs:

C = {62, 51, 68, 83, 86, 41, 43, 44, 9, 67}

a árvore de decisão acima resulta em:

Árvore de decisão GEP com atributos numéricos e nominais, k-expression WOTHababab.png

que também pode ser representado de forma mais colorida como uma árvore de decisão convencional:

Árvore de decisão GEP com atributos numéricos e nominais.png

Crítica

GEP foi criticado por não ser um grande aprimoramento em relação a outras técnicas de programação genética . Em muitos experimentos, ele não teve um desempenho melhor do que os métodos existentes.


Programas

Aplicações comerciais

GeneXproTools
GeneXproTools é uma suíte de análise preditiva desenvolvida pela Gepsoft . Os frameworks de modelagem GeneXproTools incluem regressão logística , classificação , regressão , previsão de séries temporais e síntese lógica . GeneXproTools implementa o algoritmo básico de expressão gênica e o algoritmo GEP-RNC , ambos usados ​​em todos os frameworks de modelagem de GeneXproTools.

Bibliotecas de código aberto

GEP4J - GEP para Projeto Java
Criado por Jason Thomas, GEP4J é uma implementação de código aberto de programação de expressão gênica em Java . Ele implementa diferentes algoritmos GEP, incluindo árvores de decisão em evolução (com atributos nominais, numéricos ou mistos) e funções definidas automaticamente . GEP4J está hospedado no Google Code .
PyGEP - Programação de expressão gênica para Python
Criado por Ryan O'Neil com o objetivo de criar uma biblioteca simples adequada ao estudo acadêmico da programação de expressão gênica em Python , visando facilidade de uso e rápida implementação. Ele implementa cromossomos multigênicos padrão e os operadores genéticos de mutação, cruzamento e transposição. O PyGEP está hospedado no Google Code .
jGEP - kit de ferramentas Java GEP
Criado por Matthew Sottile para construir rapidamente códigos de protótipo Java que usam GEP, que podem então ser escritos em uma linguagem como C ou Fortran para velocidade real. O jGEP está hospedado no SourceForge .

Leitura adicional

  • Ferreira, C. (2006). Programação da Expressão Gênica: Modelagem Matemática por uma Inteligência Artificial . Springer-Verlag. ISBN 3-540-32796-7.
  • Ferreira, C. (2002). Programação da Expressão Gênica: Modelagem Matemática por uma Inteligência Artificial . Portugal: Angra do Heroísmo. ISBN 972-95890-5-4.

Veja também

Referências

links externos