Archive for Inteligência Artificial

Redes neurais baseadas em competição

Introdução

Em diversos exemplos estudados, as redes às vezes decidiam por mais de um valor como resposta em vez de um único valor correto, como aconteceu quanto a classificação de letras e a rede retornava como resposta a uma entrada que ela tanto poderia ser um E como um K.
Para resolver esse tipo de problema, pode-se forçar a rede a tomar uma decisão por meio de alguma estrutura adicional, mecanismo esse conhecido como competição.
A forma mais extrema de competição é conhecida como “o vencedor leva tudo”, na qual somente um neurônio deve possuir saída diferente de zero ao final da competição.
Algumas redes desse tipo são a Maxnet, Chapéu Mexicano, Quantização do Vetor de Aprendizagem (do inglês, Learning Vector Quantization – LVQ) e Mapeamentos Auto-Organizáveis de Kohonen (cuja abreviação em inglês é SOM).
Além da característica competitiva, podemos destacar o fato de que as redes de Kohonen utilizam-se de aprendizado não supervisionado, buscando similaridades nos vetores de entrada a fim de agrupá-los em clusters.
Várias das redes apresentadas no livro utilizam-se da regra de aprendizado conhecida como “aprendizado Kohonen”. Nesta forma de aprendizado, as unidades que atualizam seus pesos o fazem de forma a determinar o novo vetor de pesos como sendo a combinação linear do antigo vetor peso e do vetor de entrada atual, tomando-se o cuidado de escolher como unidade a ser atualizada aquela cujo vetor peso esteja mais próximo do vetor de entrada a ser aprendido.
Há duas principais abordagens para determinar o vetor peso mais próximo ao vetor padrão em redes auto-organizáveis.
A primeira delas emprega o cálculo do quadrado da distância Euclidiana (Dj) entre o vetor de entrada e o vetor peso, escolhendo o vetor peso de menor valor Dj como sendo o mais próximo.
O segundo método usa o produto escalar (dot product, em inglês) do vetor de entrada e do vetor peso, que é o valor de entrada (y_inj) para cada unidade. Quanto maior o produto escalar menor o ângulo entre os vetores peso e entrada (se o comprimento de ambos for um), podendo assim ser interpretado como a correlação entre esses vetores.

Mapeamentos Auto-Organizáveis de Kohonen

As redes neurais auto-organizáveis propostas por Kohonen possuem a característica de preservar topologias, aspecto esse não identificado em outras redes. Desta forma, assumem uma estrutura topológica entre as unidades de agrupamento (clusters). Essa característica também é observada no cérebro.
Algumas das observações a respeito do funcionamento de um mapa auto-organizável são:

  • Dados p sinais de entrada, cada qual formado por n-tuplas, são capazes de agrupá-los em m clusters;
  • Atualiza somente os vetores peso da unidade j e seus vizinhos (em uma vizinhança de raio R), sendo j a unidade cujo vetor peso está mais próximo do vetor entrada;
  • Seu aprendizado é não supervisionado.

Arquitetura
A figura abaixo apresenta a arquitetura de uma rede de Kohonen:

Já a figura abaixo ilustra as vizinhanças R = 0, 1 e 2 para unidades de uma rede dispostas em um array bidimensional em uma grade retangular:

Em uma grade hexagonal, teríamos a seguinte disposição gráfica:

Algoritmo

  • Inicialize pesos
  • Estabeleça parâmetros de vizinhança topológica
  • Estabeleça parâmetros de taxa de aprendizado
  • Enquanto condição de parada for falsa, faça
    • Para cada vetor de entrada x, faça
      • Para cada j
        • Dj = 0
        • Para cada i
          • Dj = Dj + (wij – xi)2
      • Encontre índice J tal que DJ seja mínimo
      • Para todas as unidades j na vizinhança especificada de J
        • Para todos os i
          • wij = wij + α[xi – wij]
    • Atualize taxa de aprendizado
  • Reduza raio da vizinhança topológica em tempos determinados

Observações:

  • A taxa de aprendizado decresce lentamente em função do tempo;
  • O raio de vizinhança também decresce enquanto o processo de clustering progride;
  • Valores aleatórios podem ser estabelecidos para os pesos inicialmente.

[Conteúdo pertencente ao Material do curso de Redes Neurais Artificiais]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS

Associação de Padrões


Algoritmos de Treinamento para Associação de Padrões

Redes associativas são redes cujo objetivo é associar determinados tipos de padrão a outros a fim de que a rede possa reconhecer ou não uma determinada entrada, mesmo que parte das informações estejam “perdidas” ou “erradas”.

Dado um par associado s:t composto por um vetor s de n elementos e um vetor t de m elementos, necessitamos então de uma rede com n vetores de entrada e m vetores de saída e os pesos podem ser representados em uma matriz W de n linhas por m colunas.

Desta forma, para testarmos se a rede associa corretamente um determinado padrão s a um padrão t, o produto de s por W, sendo aplicado à função de ativação, deverá resultar em t, ou seja:

f(s.W) = t

Regra Hebb

Regra mais simples para a determinação de pesos para uma rede neural associativa.

Algoritmo:

  • Inicialize todos os pesos wij = 0;
  • Para cada vetor de treinamento s:t faça
    • xi = si;
    • yj = tj;
    • wij = wij + xi*yj;

Como se pode perceber Cálculo de pesos de uma rede neural , ou seja, a matriz de pesos W é igual ao produto externo dos vetores s e t.

Matriz dos vetores de treinamento

Perfect recall versus cross talk

Quanto maior for a correlação dos vetores de entrada, maior será o cross talk (ou seja, há contribuições dos vetores nos pesos de forma a perder a precisão).
Já no caso de vetores ortogonais (que são não correlacionados) a rede Hebb irá produzir pesos corretos, conseguindo assim um perfect recall.

Regra Delta

A regra Delta consegue reproduzir melhores resultados que a regra Hebb quando os vetores de entrada do treinamento são não ortogonais.
Como já vimos, a regra Delta original expressa a variação de pesos da seguinte forma:

Variação dos pesos na regra delta original

Uma variação da regra Delta leva em consideração uma função de ativação diferenciável de forma que a diferencial desta entra no cálculo da variação de pesos da seguinte forma:

Variação dos pesos na regra delta modificada

Redes Neurais de Memória Heteroassociativa

São redes em que os pesos são determinados de tal forma que elas podem armazenar um conjunto P de associações padrões.
Uma rede heteroassociativa assemelha-se à representada na figura abaixo:

Exemplo de rede heteroassociativa

Em seu treinamento tanto a regra Hebb quanto a regra Delta pode ser empregada.

A função de ativação das unidades de saída pode ser de uma das seguintes formas:

  • Função de ativação step bipolar Função de ativação step bipolar
  • Função de ativação step binária Função de ativação step binária
  • Função de ativação incluindo um threshold θi (usada em redes de memória associativa bidirecional – BAM) Função de ativação incluindo um threshold

Dado um conjunto de associações padrões S = s(1):t(1), … , s(i):t(i), … , s(P):t(P), se treinarmos uma rede associativa por regra Hebb para cada um desses padrões, teremos matrizes de pesos W(1) , … , W(i), … , W(P). Uma rede heteroassociativa treinada por regra Hebb para o conjunto de padrões S terá uma matriz de pesos W = W(1) + … + W(2) + … + W(P).

Rede Autoassociativa

Uma rede autoassociativa trata-se de um caso especial de rede heteroassociativa na qual o vetor de entrada do treinamento e a saída desejada são idênticos, desta forma, o treinamento resulta naquilo que é chamado de armazenamento do vetor.
A arquitetura de uma rede autoassociativa é, então, da seguinte forma:

Modelo de rede autoassociativa

A matriz W de pesos será tal que possuirá n linhas por n colunas e pode ser encontrada a partir da seguinte forma:

Cálculo da matriz de pesos

Que expressa a soma das matrizes-peso para cada padrão por meio da regra Hebb em um único somatório.
É necessário dizer também que, após o cálculo da matriz W, é comum “zerar-se” (estabelecer seu valor para zero) a diagonal principal dessa matriz, pratica esta que visa aumentar a plausibilidade biológica e previne a produção da matriz identidade para os pesos (quando empregada a regra Delta), além de ser necessário no caso da rede ser iterativa.

Capacidade de Armazenamento

A capacidade de uma rede de armazenamento autoassociativa depende do número de componentes que os vetores armazenados possuem e da correlação existente entre eles, sendo que quanto menor a correlação entre eles, mais vetores podem ser armazenados, alcançando número máximo quando todos os vetores são ortogonais entre si.
Sendo assim, dados vetores bipolares mutuamente ortogonais de n componentes, n – 1 destes vetores é o número máximo que se pode armazenar usando a matriz peso da soma dos produtos externos (com os termos das diagonais “zerados”).

Rede Autoassociativa Iterativa

Algumas redes não são capazes de associar na primeira tentativa um vetor que possua muitas “incertezas” (no caso de padrões bipolares, representadas pelo valor zero), entretanto o fazem muito bem após iterar sobre o resultado, ou seja, utilizar o resultado obtido na iteração anterior como nova entrada, até que não mais haja incertezas sobre os dados.
Essas redes são conhecidas como redes autoassociativas iterativas e encontram nas redes de Hopfield algumas de suas mais fortes representantes.
Nesse tipo de rede é muito comum ter todos os n neurônios conectados entre si, o que leva a deixar de identificar suas camadas como camada de entrada e camada de saída.

Autoassociador Linear Recorrente

Trata-se do tipo mais simples de rede neural autoassociadora iterativa.
Apresenta todos os seus neurônios interconectados e os pesos podem ser encontrados pela regra Hebb.
Uma vez que a regra Hebb trata-se do somatório das componentes dos vetores de entrada (para ser mais específico, do quadrado das componentes), os pesos correspondentes podem crescer indefinidamente, alterando assim a confiabilidade das informações obtidas por essa rede.
Para resolver isso, desenvolveu-se uma modificação deste tipo de rede, criando assim o “Brain-State-in-a-Box” (redes BSB).
Essas redes possuem esse nome porque impõem limites ao crescimento por meio da modificação da função de ativação, restringindo assim os valores possíveis a um cubo. Neste tipo de rede, as autoconexões (os termos da diagonal principal da matriz) não são “zerados”, havendo uma autoconexão com peso 1.
Uma outra possibilidade é trabalhar com uma função de ativação baseada no threshold. Neste caso, podemos ter vetores de entrada bipolares, pesos simétricos ( wij = wji ) e nenhuma autoconexão ( wii = 0 ) tendo como função threshold a seguinte:
Função de ativação de autoassociador linear recorrente

Rede Discreta de Hopfield

As redes de Hopfield também são completamente interconectadas, possuem pesos simétricos e nenhuma autoconexão. O que realmente as difere das anteriores é o fato de que somente uma unidade terá seu valor de ativação atualizado de cada vez e cada uma dessas unidades continua a receber um sinal externo além do sinal de cada um dos outros neurônios na rede.
Essa atualização assíncrona permite a determinação da função de Lyapunov (ou função de energia), capaz de descrever de que forma a rede convergirá para a solução.
A inicialização dos pesos (lembrando que se trata de armazenamento de padrões, ou seja, uma rede autoassociativa) pode ser feita usando-se a regra Hebb e, após esta, para cada vetor de entrada deve-se atualizar de forma assíncrona (escolhendo aleatoriamente um neurônio de cada vez, mas tendo o cuidado de atualizar todos na mesma proporção) os valores de ativação, até que estes atinjam a convergência para aquilo que será a resposta de nossa rede.
Nossa função de ativação pode trabalhar com um valor θi ou ter como threshold o valor zero.
Inicialmente, a entrada externa (ou seja, os valores do vetor de entrada) era usada somente no início de cada passo, entretanto algumas modificações da rede de Hopfield podem utilizar-se da entrada externa durante todo o processo.

Função Energia

Função energia

Capacidade de Armazenamento
Hopfield para padrões binários – Capacidade de armazenamento para hopfield para padrões binários

Hopfield para padrões bipolares – Capacidade de armazenamento para hopfield para padrões bipolares

Memória Associativa Bidirecional (BAM)

Uma rede BAM é capaz de armazenar um conjunto de associações-padrão por meio da soma de matrizes de correlação bipolares.
Sua arquitetura consiste de duas camadas de neurônios, cada qual conectado a todos os neurônios da outra camada por meio de conexões bidirecionais.
Uma vez que o sinal será enviado e retornado entre essas camadas diversas vezes até convergir, é convencionado denominar essas camadas de “camada X” e “camada Y”, em vez de camadas de entrada e saída.
A arquitetura de uma rede BAM fica, então, da seguinte forma:

Modelo de rede BAM

BAM discreta

Há duas formas de rede BAM que se utilizam de padrões de entrada e saída discretos são as formas binárias e bipolares, ambas com um comportamento muito similar.
O cálculo do peso é encontrado mais uma vez por meio do produto externo das formas bipolares dos vetores pares de treinamento. Além disso, a função de ativação continua sendo uma função step, sendo que, agora, quando o valor de entrada for igual ao threshold, a função de ativação opta por manter o valor de ativação previamente conhecido.
Uma função de ativação pode ser, por exemplo (considerando uma rede BAM bipolar):
Função de ativação para rede BAM bipolar

BAM contínua

Uma rede BAM contínua transforma de forma suave e contínua a saída em um valor no intervalo [0, 1] usando para isso não mais uma função step, mas sim uma função sigmóide logística.
A função de ativação é:

Função de ativação para uma rede BAM contínua

O cálculo do y_inj leva em consideração o valor de um bias, diferentemente das outras redes associativas que temos visto aqui.

Outros Conceitos

Distância Hamming

A distância Hamming entre dois vetores x1 e x2 (denotada por H[x1, x2]) trata-se do número de componentes diferentes que estes possuem.
A distância média Hamming entre dois vetores é Cálculo da distância hamming
, valor este que expressa o percentual de diferenças que há entre os dois vetores.

Apagar uma associação armazenada

Seja xc o complemento de um vetor bipolar x (ou seja, um vetor que inverte os valores 1 por –1 e vice-versa).
Codificar uma matriz-peso para armazenar xc:tc é o mesmo que codificá-la para armazenar x:t.
Entretanto, se ela for treinada para armazenar xc:t ou x:tc, ela perderá as informações armazenadas a respeito do par associado x:t, o que é facilmente provado por meio de álgebra linear.

[Conteúdo pertencente ao Material do curso de Redes Neurais Artificiais]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS

Redes Neurais simples para classificação de padrões

Como afirmamos anteriormente, redes neurais artificiais podem ser empregadas a fim de classificar determinados dados de entrada segundo padrões, buscando assim associar uma resposta a cada um deles. Essa classificação de padrões pode ser feita de diferentes formas, de acordo com o tipo de rede neural adotado, bem como a regra de aprendizado que o mesmo emprega.

Começaremos então nossos estudos analisando alguns modelos de redes neurais mais simples que satisfazem tal proposta.

Arquitetura

Por hora, será estudado o tipo de arquitetura mais simples possível para a classificação de padrões: redes neurais single-layer, isto é, de uma única camada.
Além disso, o uso de bias ajustável será necessário, de tal forma que podemos manter o threshold da função de ativação fixo em zero, variando assim somente
O uso de bias ajustável permitirá que se ajuste a região de separação dos padrões (sem necessitar ajustar o threshold da função de ativação, que permanecerá fixado em zero).
A figura abaixo representa o nosso modelo de uma rede neural para classificação de padrões:

Rede neural singlelayer para classificação de padrões

Separabilidade Linear

Entende-se por separabilidade linear a capacidade de uma rede de separar completamente dois padrões a partir de pesos e bias bem ajustados para tal.
Diz-se que é linearmente separável porque a representação gráfica do domínio dos parâmetros de entrada pode ser dividida por uma reta de forma a manter cada padrão de um dos lados da mesma, conforme demonstra a figura abaixo.

Representação gráfica da separabilidade linear

Tomando-se 1 e –1 como sendo os valores a dizer qual padrão encontrado, o valor zero determina a “fronteira” entre eles, ou seja, a reta que os separa, reta esta determinada por:

É provado também que se uma rede multilayer com funções de ativações lineares for utilizada, ela também só poderá solucionar problemas linearmente separáveis.

Rede Hebb

Na rede Hebb proposta pelo autor deste livro, os vetores de entrada devem estar na forma bipolar (1 ou –1) ou binária (1 ou 0), bem como os valores a serem atingidos (resultado de cada treinamento) será na forma bipolar. Além disso, o treinamento é supervisionado, ou seja, são dados vetores de entrada com seus respectivos resultados (target) a fim de que os pesos possam ser ajustados.
Os pesos são inicialmente zero e a cada vetor de entrada do treinamento os pesos são ajustados por meio da seguinte fórmula:

Onde:
wi – peso para a entrada i (lembrando que a entrada da bias é x0 = 1 e w0=b);
xi – valor da entrada i ( 1 ou – 1);
t – resultado desejado (1 ou –1);

Obs: Apesar de considerarmos a bias como sendo x0, sua representação será sempre ao final do vetor de entrada)

Abaixo, segue o treinamento de uma rede Hebb para a função AND:

INPUT
(x1 x2 1)
TARGET WEIGHT CHANGES
(Δw1 Δw2 Δb)
WEIGHTS
(w1 w2 b)
( 0 0 0 )
( 1 1 1 ) 1 ( 1 1 1 ) ( 1 1 1 )
( 1 0 1 ) -1 ( -1 0 -1 ) ( 0 1 0 )
( 0 1 1 ) -1 ( 0 -1 -1 ) ( 0 0 -1 )
( 0 0 1 ) -1 ( 0 0 1 ) ( 0 0 -2 )

Uma rede Hebb pode ser usada no reconhecimento de alguns padrões simples, por exemplo, distinguir um caractere “x” de um “o”.
Entretanto, não são todos os problemas linearmente separáveis que a rede Hebb é capaz de resolver. Problemas cuja saída não seja da forma bipolar são descartados e alguns, mesmo possuindo vetor de entrada e resultado na forma bipolar, não são possíveis.

Perceptron

A regra de aprendizado do perceptron permite abranger soluções para um número muito maior de problemas do que a regra de aprendizado Hebb.
Os primeiros perceptrons possuíam três camadas de neurônios – unidades sensoriais, unidades associadoras e uma unidade de resposta – formando um modelo aproximado da retina.
Os valores de entrada para cada neurônio, bem como da saída dos mesmos, podem ser 1 (atuando de forma excitatória), -1 (atuando de forma inibitória e 0 (indicando indecisão).
Para tal, a função de ativação passa a ser da forma:

Uma análise de como se comporta o threshold ( θ ) em um perceptron e percebe-se que o bias ( b ) apresenta agora um papel diferente daquele, já que o θ representa não somente o threshold, mas também a dimensão da região de indecisão (de – θ a + θ).
Um gráfico representando uma classificação de padrões por uma rede perceptron para o problema da função lógica AND pode possuir a seguinte forma:

Os pesos são inicialmente zero e a cada vetor de entrada do treinamento os pesos são ajustados por meio da seguinte fórmula:

Onde:
α – taxa de aprendizado ( )
wi – peso para a entrada i (lembrando que a entrada da bias é x0 = 1 e w0=b);
xi – valor da entrada i ( 1 ou – 1);
t – resultado desejado (1 ou –1);

Após a execução do treinamento para todos os vetores de entrada, verifica-se se houve algum peso alterado. Caso algum peso tenha sido alterado, executa-se novamente todo o processo para todos os vetores de entrada e, no momento em que não mais houver variações nos pesos, interrompe-se o treinamento: foram encontrados pesos adequados na classificação dos mesmos.
As duas retas que dividem o espaço em três regiões podem ser assim determinadas:

O treinamento de um perceptron para a função AND com entrada na forma binária e saída bipolar seria da seguinte forma (adotando-se θ = 0.2 e α = 1 , com todos os pesos inicialmente zero):

Clique aqui para ver a tabela com os dados do treinamento dessa rede Perceptron.

Como durante toda a época 10 não houve variação de pesos, então, alcançamos os pesos que classificam corretamente os vetores do treinamento.

O treinamento de um perceptron para a função AND com entrada na forma binária e saída bipolar seria da seguinte forma (adotando-se θ = 0.2 e α = 1 , com todos os pesos inicialmente zero):

Clique aqui para ver a tabela com os dados do treinamento dessa rede Perceptron.

Como durante toda a época 2 não houve variação de pesos, então, alcançamos os pesos que classificam corretamente os vetores do treinamento.
Com isso, fica claro que a forma como os dados são representados nos vetores de entrada e saída, bem como o threshold escolhido influenciam no tempo que levará para se alcançar os pesos adequados.

Adaline

Adaline (Adaptive Linear Neuron) utiliza principalmente ativações bipolares para a entrada e para a saída, entretanto não se restringe a estes.
A regra de aprendizado de redes Adaline é a regra delta, baseada na variação entre a saída esperada e a entrada da rede para cada neurônio. Apesar de ser aplicada a redes de uma única camada, há uma outra versão desta (a Madaline) que se encarrega do treinamento em redes de múltiplas camadas, conforme será visto mais adiante.
A função de ativação é dada por:

E o cálculo da variação de cada peso associado a um neurônio yj é:

Onde:
α – taxa de aprendizado ( 0 < α ≤ 1 )
wi – peso para a entrada i (lembrando que a entrada da bias é x0 = 1 e w0=b);
xi – valor da entrada i ( 1 ou – 1);
t – resultado desejado (1 ou –1);

O algoritmo para uma rede Adaline é (este algoritmo considera wn+1 = b, isto é, o bias é o peso associado à (n+1)-ésima entrada):


Inicializar todos os pesos (com valores aleatórios pequenos);
Atribuir valor de alpha;
HouveMudanca = verdadeiro (indica se houve alteração de pesos);
Enquanto (houveMudanca) Faça
houveMudanca = falso;
Para cada par de treinamento (entrada : target) faça
y_in = 0;
Para i = 1 até n
Para j = 1 até m+1
y_in = y_in + entradaj*wij;

Se y_in >= 0 então
y = 1;
Senão
y = -1;

Se y ≠ targeti então
houveMudanca = verdadeiro;
Para j = 1 até m+1
weightsij = weightsij + alpha*(targeti – y_in)*entradaj;
// Fim de todo o algoritmo;

Onde:
n número de neurônios na camada de saída;
m número de neurônios de entrada para cada neurônio na camada de saída;
target array de valores esperados na saída para cada neurônio para dada vetor de entrada;
entrada vetor de entrada do treinamento (para facilitar a resolução, assumimos que a última posição do vetor de entrada – m+1 – é sempre 1 – o valor de ativação para o bias);

Madaline

Madaline (Many Adaptive Linear Neuron) comporta-se como sendo um arranjo de vários Adalines agrupados em uma rede de múltiplas camadas.
Devido à estrutura de múltiplas camadas, o processo de treinamento de uma rede Madaline é mais complexo quando comparado com as anteriores.
Há duas formas de se treinar esta rede: por MRI (o algoritmo de treinamento original para uma Madaline), que varia somente os pesos associados aos neurônios da camada oculta, e por MRII (variação do MRI), que permite variar todos os pesos da rede em busca da solução.

No MRI, os pesos associados aos neurônios de saída são fixados (podendo estes, assim, atuar como AND ou OR, dependendo de seus valores) e os pesos dos neurônios ocultos são calculados da seguinte forma:

  • Calcule z_in (entrada da rede) e z (saída do neurônio por meio da função de ativação) para cada neurônio;
  • Calcule então y_in e y do neurônio de saída;
  • Se y for diferente do target, então é necessário ajustar;
    • Se o target é 1, então escolha o neurônio Zj cuja entrada de rede (z_in) for mais próximo de zero e incremente seus pesos por meio da fórmula:
    • Se o target é –1, então decremente os pesos de todos os neurônios Zj cuja entrada de rede são positivas:

O MRII procede similar ao MRI, alterando somente a forma como calcula-se a variação dos pesos dos neurônios. Este algoritmo procura selecionar dentre cada neurônio qual possui a entrada de rede mais próxima de zero, mudando então o sinal da saída e testando se, com o novo valor, o erro entre y e target é reduzido. Caso seja, ajusta-se os pesos nesta unidade (ou seja, encontrou-se uma unidade cuja saída é efetiva para a correção).

[Conteúdo pertencente ao Material do curso de Inteligência Artificial e ao Material do curso de Redes Neurais Artificiais]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS

Introdução às Redes Neurais

Em Inteligência Artificial, as Redes Neurais, ou se preferir Redes Neuronais, constituem principal objeto de estudo da abordagem conexionista, que estuda a forma como a informação é processada

Uma abordagem sobre as redes neurais

Uma rede neural (biológica) trata-se de uma complexa estrutura formada por neurônios e suas conexões, capaz de processar informações adquiridas a fim de armazená-las e aprender sobre elas, classificando-as por meio de padrões.

Cada neurônio é conectado a n outros neurônios por meio de dendritos (por onde os impulsos chegam) e axônio (por onde os impulsos são transmitidos).

O neurônio biológico é composto por três partes:

  • Dendritos – recebem os sinais de outros neurônios e os conduzem até o soma;
  • Soma – região da célula capaz de efetuar o somatório dos impulsos recebidos e, caso o impulso seja suficiente, transmitirá novos impulsos a outros neurônios por meio do axônio;
  • Axônio – parte do neurônio que conduz os impulsos produzidos pela mesma até outros neurônios.

Uma rede neural artificial trata-se de um sistema de processamento de informações que possui certas características de performance e processamento dos dados em comum com redes neurais biológicas.

Em uma rede neural, cada neurônio recebe impulsos de vários neurônios (x1, x2, …, xn), aplica pesos sobre cada um desses impulsos (w1, w2, …, wn), efetua o somatório desses valores (y_in), processando então por meio de alguma função a fim de encontrar um valor resultante (y) que irá lhe dizer se deve ou não transmitir novos impulsos a novos neurônios (z1, z2, …, zn) e quais devem ser os novos pesos (v1, v2, …, vn).

Desta forma, podemos dizer que as seguintes equações compõem parte do modelo matemático:
y_in = w1x1 + w2x2 + … + wnxn
y = f (y_in)
v1 = g1(y)
v2 = g2(y)

vn = gn(y)

Aplicações de Redes Neurais
Em Computação, várias são as possíveis aplicações de Redes Neurais, devido à capacidade de aprendizado que as mesmas possuem. Sendo assim, algumas das que podemos destacar aqui são:

  • Processamento de sinais, como em uma linha telefônica, por exemplo, onde se podem utilizar redes neurais a fim de eliminar ruídos e ecos nas chamadas telefônicas, causados por interferências. Redes do tipo ADALINE podem ser aplicadas para essa finalidade;
  • Controle de navegação e movimentação de veículos automatizados;
  • Reconhecimento de padrões, onde redes neurais multicamada são largamente empregadas;
  • Aplicações na medicina, onde uma rede neural pode ser treinada para reconhecer os sintomas e, assim, diagnosticar o tratamento adequado;
  • Reconhecimento e reprodução de voz.

Arquitetura de uma Rede Neural

A arquitetura de uma rede é formada por camadas, onde cada neurônio de uma dada camada somente se relaciona com neurônios de outra(s) camada(s) e possui função de ativação e pesos com algum tipo de padrão em relação aos outros neurônios da mesma camada em que se encontra.

Segundo o número de camadas (os neurônios de entrada não contam no momento da contagem de camadas), uma arquitetura pode ser classificada como:

  • Redes de uma única camada (singlelayer) – neste modelo, há somente unidades de entrada e unidades de saída;
  • Redes de várias camadas (multilayer) – neste modelo, além das unidades de entrada e unidades de saída, há neurônios denominados unidades ocultas.

A figura abaixo ilustra uma rede neural, onde os círculos representam neurônios e as setas indicam o fluxo de impulso (dados) de um neurônio para o outro. O neurônio Y é chamado de neurônio de saída, responsável por emitir o sinal resultante dos estímulos recebidos.

Exemplo de Rede Neural

Há também a aplicação de camadas competitivas, cuja representação gráfica difere um pouco daquelas que estamos discutindo.

O Treinamento de uma Rede Neural

O treinamento de uma rede geralmente é feito de forma iterativa por meio do ajuste de seus pesos.
Desta forma, podemos classificar uma rede quanto ao tipo de treinamento da seguinte forma:

  • Treinamento supervisionado – o treinamento é realizado por meio de testes sobre vetores de entrada cuja saída já é conhecida (memória associativa), desta forma, os pesos são ajustados de acordo com o algoritmo de aprendizado a fim de refletir o resultado esperado. Este tipo de treinamento é muito comum em classificação de padrões, podendo-se utilizar redes multilayer com treinamento por backpropagation para resolução de problemas mais difíceis;
  • Treinamento não-supervisionado – as redes são auto-organizáveis e o treinamento é feito por meio de uma seqüência de vetores testes provida, mas sem vetor de saída a ser associado. Desta forma, a rede modifica seus pesos a fim de conseguir associar os vetores de saída aos vetores de entrada.

Uma rede também pode ser projetada com pesos fixos, sendo capazes de resolver problemas de solução complicada se utilizando técnicas tradicionais. Além disso, alguns autores apontam uma terceira categoria: treinamento auto-supervisionado.

Funções de Ativação

Uma função de ativação representa aquela receberá o resultado do somatório do produto de cada entrada por cada peso e responderá com um único valor, usado como entrada para o próximo neurônio ou como resposta da rede neural.

Há várias funções de ativação possíveis de serem aplicadas, de acordo com o tipo de saída que desejamos. As mais comuns são:

  • Função identidade: empregada principalmente nas unidades de entrada, uma vez que as respostas destas devem ser iguais aos valores passados pelo ambiente;
  • Função identidade em rede neural

  • Função step, com threshold Ө: muito usada em redes single-layer a fim de restringir os parâmetros passados em valores binários (1 ou 0) ou bipolares ( 1 ou –1);
    • Step binária;
    • Função step binária em rede neural

    • Step bipolar;
    • Função step bipolar em rede neural

  • Função sigmóide: é especialmente útil em redes treinadas por backpropagation. Há principalmente dois tipos:
    • Sigmóide binária;
    • Sigmóide bipolar.

Observações a serem consideradas

Dada uma matriz W = (wij) formada pelos pesos para cada unidade Yj a partir dos estímulos recebidos das unidades Xi, podemos calcular y_inj para cada unidade como sendo produto de dois vetores, ou seja:

Cálculo dos estímulos recebidos por um neurônio artificial

Além disso, pode-se incluir um componente x0 = 1 como sendo um dos valores de entrada e utilizar-se de um peso w0j = bj, conhecido como bias. Desta forma, a equação fica:

Cálculo dos estímulos recebidos por um neurônio artificial com bias

O uso de bias em nossas redes neurais mostra-se importante, pois permite que fixemos o valor de threshold adotado em nossa função de ativação, sendo necessário então atualizar somente os pesos e o bias na rede. Como o bias pode ser encarado como sendo o peso para um neurônio cuja entrada é sempre 1, percebe-se que a mesma regra para atualização dos pesos é válida também para a atualização do bias, tornando assim mais fácil nossa tarefa. Ficou difícil de entender? Vamos então mostrar alguns números…

Suponha uma rede neural cuja função de ativação é a step bipolar, isto é, f(y_in) = 1, se y_in θ e f(y_in) = -1, caso contrário.

Sabemos que y_in = x1*w1 + x2*w2 + … + xn*wn, então podemos resumir nosso problema à inequação:

x1*w1 + x2*w2 + … + xn*wn θ

Que, sendo verdadeira, fará f(y_in) ter valor 1.

Então, para que nossa rede neural seja corretamente ajustada, precisaríamos ajustar não somente os pesos, mas também o threshold θ, tarefa não muito simples, já que precisaríamos ter alguma fórmula de ajuste do threshold. Entretanto, podemos fazer algumas alterações, veja só:

x1*w1 + x2*w2 + … + xn*wn θ

θ + x1*w1 + x2*w2 + … + xn*wn 0

1*(-θ) + x1*w1 + x2*w2 + … + xn*wn 0

Agora, podemos considerar o primeiro termo 1*(θ) = x0*w0, isto é, o valor de entrada sempre 1 um peso (que nós chamamos de bias, lembra?) cujo valor poderá ser ajustado da mesma forma que ajustamos os demais pesos (isto é, utilizando a mesma regra de aprendizado), o que seria o mesmo que ajustar o threshold. Ficou mais fácil de entender agora? :)

Algumas redes neurais

  • Neurônios de McCulloch-Pitts – primeiras redes neurais, foram concebidas como uma combinação de neurônios utilizando um tempo de espera entre a transmissão de um neurônio e outro, o que permitiu modelar alguns processos fisiológicos, como a percepção de quente e frio. Utiliza-se de um valor de threshold na tomada de decisões;
  • Aprendizagem Hebb – primeiras redes neurais capazes de aprender por meio do reajuste de pesos. Também se utiliza de uma função de threshold;
  • Perceptron – contando com regras de aprendizagem mais poderosas que o Hebb, utiliza-se de pesos fixos entre as unidades de entrada e suas conexões e pesos ajustáveis entre as demais unidades. Da mesma forma que os dois anteriores, utiliza-se de uma função threshold;
  • Adaline – trata-se de uma rede single-layer que se utiliza de uma regra de aprendizagem conhecida como regra delta, que busca reduzir a diferença entre a saída de uma dada unidade e a saída realmente desejada. Madaline é uma extensão multilayer do Adaline;
  • Backpropagation – utiliza-se da propagação das informações sobre os erros nas unidades de saída para as unidades ocultas, a fim de realizar o reajuste;
  • Redes de Hopfield – Estas redes funcionam como redes de memória associativa, o que permite resolver problemas em um número de iterações mais satisfatório;
  • Neocognitron – redes neurais especializadas em reconhecimento de caracteres;
  • Máquina de Boltzman – redes neurais não-determinísticas, nas quais os pesos e ativações são alterados por meio de funções de densidade probabilística;
  • Implementações em Hardware.

Alguns nomes que se destacaram nos anos 70 são Kohonen (desenvolvedor de redes para reconhecimento de voz e problema do caixeiro viajante), Anderson (aplicações em diagnósticos médicos), Grossberg (146 trabalhos publicados) e Carpenter (desenvolvedor da teoria da ressonância adaptativa).

O Neurônio de McCulloch-Pitts

Principais características do modelo de neurônio proposto por McCulloch e Pitts:

  • A ativação do neurônio de McCulloch-Pitts é binária;
  • Neurônios são conectados por caminhos direcionados e baseados em pesos;
  • Uma conexão é excitatória se o peso associado for positivo, caso contrário, ela é inibitória;
  • Há um threshold fixado para cada neurônio;
  • Caso haja uma entrada inibitória diferente de zero, o neurônio não pode disparar (inibição absoluta);
  • Há um tempo de atraso na transmissão do sinal de um neurônio para outro.

Função de ativação para um neurônio de McCulloch-Pitts

Algumas redes neuronais de McCulloch-Pitts

(Usando θ = 1 como threshold)

Rede Neural AND
Rede Neural AND

Rede Neural OR
Rede Neural OR

Rede Neural AND NOT
Rede Neural AND NOT

Rede Neural XOR
Rede Neural XOR

Rede Neural Quente-Frio
Rede Neural Quente-Frio

[Conteúdo pertencente ao Material do curso de Inteligência Artificial e ao Material do curso de Redes Neurais Artificiais]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS

Uma Introdução aos Algoritmos Genéticos – Parte 3

Esta é a terceira e última parte de nossa introdução aos algoritmos genéticos. Desta vez, vamos discutir a respeito dos parâmetros que mais influenciam o sucesso de nosso algoritmo genético, como e por que efetuar o ajuste de fitness, o que é o elitismo, bem como apresentar algumas aplicações de algoritmos genéticos.

Caso você não tenha lido um dos outros dois artigos, os mesmos são:

Uma Introdução aos Algoritmos Genéticos – Parte 1

Uma Introdução aos Algoritmos Genéticos – Parte 2

Parâmetros Genéticos

Para o bom sucesso de um algoritmo genético, quatro parâmetros devem ser bem vigiados e testados:

  • Tamanho da população: o tamanho da população afeta e muito o desempenho do algoritmo, pois, quanto maior é a população, maior é a a cobertura do espaço de busca que a mesma promove, entretanto, mais processamento, memória e outros recursos serão consumidos;
  • Taxa de crossover (cruzamento): quanto maior for a taxa de cruzamento, mais rapidamente novas estruturas serão introduzidas, entretanto quando esta taxa é muito alta, pode provocar a perda de estruturas de alta aptidão, dificultando assim chegar na resposta de forma clara, rápida e precisa. Já quando a taxa de crossover for muito baixa, transforma-se em outro problema onde o algoritmo converge para a solução mais lentamente;
  • Taxa de mutação: uma baixa taxa (porém, não nula!) de mutação pode auxiliar a não permitir que as informações em um cromossomo fiquem estagnadas, o que poderia dificultar para chegar na solução. Já taxas altas de mutação podem levar a índices muito altos de aleatoriedade nas informações;
  • Intervalo de Geração: indica a porcentagem da população que pode ser substituída na próxima geração. Com valores baixos, ou seja, uma pequena parte da população sendo alterada a cada geração, pode-se demorar muito até chegar na solução. Já no caso de valores muito altos pode-se ocorrer a perda de estruturas de aptidão.

Ajuste de Fitness

O ajuste de fitness permite ajustar a pontuação calculada para cada cromossomo a fim de “zerar” a pontuação daqueles que são considerados os piores cromossomos, evitando, assim, que o mesmo seja selecionado pela “roda da roleta”.
Se tivermos uma pontuação em que grandess valores representam cromossomos mais apropriados para a solução, podemos fazer o ajuste de fitness simplesmente subtraindo o valor do pior cromossomo de todos (inclusive dele próprio, o que reduzirá sua contagem a zero).

Elitismo

Elitismo trata-se da repetição dos cromossomos com melhores resultados na próxima geração a fim de evitar que todos os bons cromossomos sejam alterados pelo crossover e pela mutação, desta forma, o uso de elitismo permite que o algoritmo convirja mais rapidamente para uma solução.
Da mesma forma que com os parâmetros genéticos, deve-se tomar cuidado com o uso de elitismo, pois quanto maior for o número de cromossomos a serem mantidos, maior a probabilidade de convergirmos para um máximo local.

Aplicações de algoritmos genéticos

Os algoritmos genéticos podem ser usados em praticamente todas as ocasiões onde pudermos codificar nossos parâmetros e empregar o método gerar-e-testar para encontrar uma possível solução ou mesmo melhoria em relação aos parâmetros trabalhados anteriormente.
Para melhor ilustrar isso, podemos imaginar um jogo (já que esta é primariamente a minha área :) ) de estratégia em tempo real onde os exércitos são comandados por comandantes (agentes inteligentes), porém cada unidade conserva suas habilidades para tomada de decisão. Desta forma, poderíamos combinar vários parâmetros a fim de determinar o cromossomo de cada unidade com características como força, coragem, lealdade, esperteza, raio de ajuda, etc.
Seguindo algumas restrições sobre algumas características para a criação de uma unidade e gerando os dados aleatoriamente, poderemos então criar exércitos onde cada unidade possui seu próprio comportamento, sua própria personalidade.
Eis que as próprias partidas seriam nosso treinamento e, a cada nova unidade criada, levar em consideração a pontuação obtida pelos cromossomos já criados, assim, aos poucos, teríamos unidades que vão se tornando mais inteligentes durante as batalhas.
Obviamente será necessário também algum treinamento em paralelo às partidas a fim de agilizar o processo de aprendizado, mas com certeza o resultado final será muito interessante!
Não somente em jogos de estratégia, mas em todos os jogos onde há tomada de decisões este tipo de algoritmo pode ser empregado, desde o cálculo de um pathfinding até a tomada de decisões sobre atacar, acelerar, mover uma peça no tabuleiro, etc.

Podemos empregar também em aplicações onde podemos testar, “treinar” o nosso sistema inicialmente. Criaríamos um número qualquer de cromossomos dispostos a tentar resolver o problema dado e após algumas gerações selecionaríamos aqueles com melhor desempenho.

Esperamos que esta série de artigos o tenha ajudado a compreender como funcionam e como implementar algoritmos genéticos.

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS

Uma Introdução aos Algoritmos Genéticos – Parte 2

Continuando nossos estudos em Algoritmos Genéticos, podemos lembrar que em Uma Introdução aos Algoritmos Genéticos – Parte 1, nós iniciamos estudos sobre o que são algoritmos genéticos e como pode ser elaborado um cromossomo para um algoritmo genético.

Agora, vamos estudar cada um dos passos necessários em um algoritmo genético a fim de que o mesmo possa reproduzir e selecionar os seres.

Criação da população inicial

A criação da população inicial não deve ser tão complexa, uma vez que seus valores são aleatórios, entretanto, se houver alguma regra quanto a como os parâmetros devem ser distribuídos, é bom atentar-se a eles.
Tomemos como exemplo nossos NPCs da seção anterior. Quando criamos os personagens para combate e queremos que eles estejam bem balanceados, é necessário que eles sejam criados em condições de equilíbrio, e este equilíbrio pode ser encontrado distribuindo-se uma mesma quantidade (via de regra, personagens no sistema 3D&T são criados inicialmente com 12 pontos distribuídos entre suas características). Isso evita que criemos um personagem muito bom não pela correta combinação das habilidades, mas sim porque o mesmo fora construído com mais pontos, desfazendo o equilíbrio exigido.

A criação de cada ser corresponde, então, à criação de um cromossomo qualquer, e a população inteira poderá ser armazenada na estrutura de dados que melhor convier: um array, uma lista dinâmica, etc.

Simulação e Pontuação

A simulação deve ser executada a fim de testar como cada ser (cujo comportamento e características estão determinados pelo seu cromossomo) se comporta em ação real e, portanto, saber se ele será uma boa escolha ou não.
A simulação deve ser feita de acordo com aquilo para o qual aquele ser foi projetado: se se trata de um carro de corrida, a simulação será uma corrida, se se trata de um personagem de luta, a simulação seria uma luta.
Além disso, é necessário criar boas regras para pontuar cada ser. No caso do nosso jogo de luta, podemos estimar que em primeiro lugar mereça mais pontuação aquele que derrota um inimigo, em segundo lugar aquele que consegue golpear um inimigo e, por fim, aquele que sobrevive mais tempo no combate.
Desta forma, podemos agora criar uma função que será invocada o tempo todo em nossa simulação a fim de pontuar cada cromossomo da seguinte forma:

  • Derrotar inimigo – 50 pontos;
  • Golpear inimigo – 10 pontos;
  • Para cada cinco segundos vivo em arena – 1 ponto.

Outra forma de pontuar é fazendo a avaliação e atribuindo a pontuação em um dado momento da “vida” de cada ser. Neste caso, no momento em que um personagem morresse calcular-se-ia sua pontuação e, quando acabasse o tempo de luta, calcular-se-ia dos sobreviventes.
O que importa é que devemos ter algum meio de simular a ação e contabilizá-la em pontos a fim de mais tarde poder determinar quem são os “cromossomos vencedores”.

Seleção de cromossomos

Após a simulação e pontuação dos cromossomos, precisamos selecionar os cromossomos que melhor servirão como “pais” e “mães” para os novos cromossomos a serem criados (ou como resposta para o nosso problema, caso tenhamos atingido a condição de parada).
Um jeito óbvio seria selecionar sempre os melhores. Mas podemos encontrar aqui um problema conhecido como “máximo local” (ou mínimo local, como é conhecido em alguns livros, como é o caso do “AI Techniques for Game Programming”).
O máximo local trata-se de um valor que, quando comparado com a sua vizinhança, parece ser o melhor de todos. Imagine então que temos um cromossomo que, pareça ser o melhor dentre os demais que guardem características similares a ele (ou seja, cromossomos que sofreram crossover e mutações para serem criados a partir dele), mas que não seja efetivamente a melhor solução.
Eis que, caso peguemos tal cromossomo como pai e criemos os filhos, na próxima geração ele continuará sendo o melhor e, portanto, nossa solução não convergirá na melhor resposta.
Para evitar isso, pode-se utilizar métodos para seleção que não obrigatoriamente pegarão o melhor cromossomo, como é o caso do método de seleção “roda da roleta” (do inglês, roulette wheel), onde se atribui a cada cromossomo uma probabilidade de ser selecionado de acordo com a sua pontuação obtida.
Suponha que a soma da pontuação de todos os cromossomos seja 2000 e que um dado cromossomo tenha conseguido 200 pontos. Neste caso, a probabilidade de seleção deste cromossomo é 200 / 2000 = 0.1 ou 10%.
Após isso, dispondo todos os cromossomos em alguma ordem, podemos dizer que, ao sortear um número fracionário aleatório entre 0 e 1, o cromossomo selecionado será o primeiro se o número for entre 0 e 0.35 (para um cromossomo com 35% de chances), ou o cromossomo será o segundo se o número estiver entre 0.35 e 0.45 (para um cromossomo com 10% de chances), e assim por diante até completar a “roda”.
Após a seleção de dois ou mais cromossomos para serem os pais, podemos começar o processo de reprodução, que pode ser feito da seguinte forma:

  • Escolha dois cromossomos;
  • Faça o crossover se necessário;
  • Faça mutações nos genes em que for necessário.

Com isso, obtêm-se dois novos cromossomos. Vejamos agora o que queremos dizer com crossover e mutações.
Obs: Lembre-se de que estamos REPRODUZINDO um novo cromossomo e não somente alterando os cromossomos pai e mãe, sendo assim, lembre-se de, no início do estágio de reprodução, criar cópias com as informações necessárias.

Crossover

Crossover trata-se do cruzamento (termo como pode ser encontrado na literatura brasileira) entre dois cromossomos.
Para efetuarmos este cruzamento, precisamos de duas coisas:

  • Saber se realmente devemos fazer o cruzamento por meio de uma taxa de crossover;
  • Saber em que ponto dos cromossomos fazer o crossover.

Vamos supor que tenhamos uma taxa de crossover de 70% (ou 0.7 se representado de 0 a 1). Se ao tirarmos um número aleatório de 0 a 1 encontrarmos um número maior ou igual a 0.7, então nós não faremos crossover entre os cromossomos (eles permanecerão do jeito que estão); agora, caso o valor seja menor que 0.7, então devemos efetuar um “corte de cruzamento” e, para tal, basta sortearmos uma posição no cromossomo e, então, trocar o pedaço de um cromossomo com o respectivo do outro. Graficamente, o resultado de um crossover seria o seguinte:

Exemplo de crossover em algoritmo genético

Exemplo de crossover em algoritmo genético

Mutações

Uma mutação é a alteração de uma informação genética que, na Biologia, pode ser ocasionada por diferentes agentes externos e internos do organismo em questão e, na Computação, geralmente é realizada a fim de garantir a diversidade da infomação.
Enquanto que o crossover cuida do cruzamento, isto é, da troca de informações entre dois cromossomos, as mutações cuidam de alteração da informação dos genes de um cromossomo sem relacioná-la com outro cromossomo.
Há diversos tipos de mutações e eles recebem, aqui, os mesmos nomes que recebem na área biológica de acordo com a forma como mutação altera os genes do cromossomo. Dois dos diversos tipos são a inversão, processo no qual a informação em um gene é invertida, e a permutação, processo no qual a informação de mais de um gene é trocado entre si. Vale lembrar que a permutação pode ser executada mesmo com genes não-consecutivos no cromossomo.
A fim de executar uma mutação em um cromossomo, deve-se usar uma taxa de mutação (deve ser testada da mesma forma que foi feita com a taxa de crossover), testando cada gene para saber se ele deverá sofrer mutação ou não.

Na terceira e última parte do nosso estudo sobre algoritmos genéticos, compreenderemos os principais parâmetros que influenciam o sucesso de um algoritmo, cuidados e aplicações na área de jogos.

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS

Uma Introdução aos Algoritmos Genéticos – Parte 1

Introdução aos Algoritmos Genéticos

Na área de Inteligência Artificial, há uma grande diversidade de abordagens existentes: simbólica, evolutiva, conexionista, híbrida e distribuída.
Para cumprir o nosso objetivo de formar sólidos conhecimentos em computação inteligente, estudaremos agora a abordagem evolutiva.
A abordagem evolutiva inspira-se na forma como seres vivos sobrevivem e passam seu material genético geração após geração, ou seja, por meio da evolução das espécies.
Enquanto que as espécies sofrem seleção natural segundo suas capacidades (expressas por meio de seus comportamentos – fenótipo – e genomas – genótipo) a fim de determinar quais são mais aptas a sobreviver e, conseqüentemente, ter maiores chances de reproduzir novos seres, de forma similar ocorre naquilo que chamamos de Inteligência Artificial Evolutiva, que se baseia principalmente na evolução das espécies como forma de alcançar a solução para um problema. Em outras palavras, a abordagem evolutiva baseia-se na “lei do mais forte”, onde aqueles que são mais aptos à sobrevivência permanecem, repassando, assim, a sua combinação genética para seus herdeiros.

Os algoritmos que se utilizam dos princípios da abordagem evolutiva são conhecidos como algoritmos genéticos.

Sendo assim, neste (e em artigos posteriores), discutiremos sobre algoritmos genéticos e como melhor empregá-los.

Algoritmos genéticos e a evolução genética dos seres vivos

Conforme enunciamos anteriormente, os algoritmos genéticos inspiram-se na evolução genética dos seres vivos a fim de melhor compreender como a natureza competitiva em que se encontram ajuda-os a buscarem ser o “mais forte”, que não significa somente força, mas um conjunto de informações que, quando processadas no meio em que se encontram, trazem melhores resultados que outras combinações daquelas informações.
Tomemos como exemplo uma população de tigres. A vida de um tigre não é fácil, pois precisa correr bastante para garantir cada refeição. Eis que, dentre os membros de uma comunidade de tigres, alguns deles melhor se sobressaem em relação aos outros. O que acontecerá?
Bem, segundo a teoria da “sobrevivência do mais forte”, esses membros com melhor desempenho terão maiores chances de sobrevivência no meio em que se encontram. Sendo assim, é provável que muitos dos membros dessa comunidade da próxima geração sejam seus herdeiros.
Vale lembrar também que os herdeiros carregam características de seus pais. Isso se dá pelo fato de ter recebido uma combinação feita a partir de seus cromossomos, sendo, portanto os cromossomos responsáveis por manter as informações sobre as características daquele ser.
Perceba que, nesta nossa história, tivemos alguns elementos importantes: uma população de seres a ser testada (pode ser a observação da rotina daquela população), a estrutura onde armazenaremos a informação (no caso, os cromossomos), a seleção dos seres com melhor desempenho e, então, a sua reprodução (combinando, assim, seus cromossomos).
Algoritmos genéticos trabalham de forma bem similar a este processo, usando uma população inicialmente configurada com parâmetros escolhidos aleatoriamente para os seus cromossomos, simulação e testes da mesma a fim de dar alguma pontuação a cada indivíduo, seleção dos mais aptos e, então, a reprodução destes.
Perceba com isso que, ao final do processo, geramos uma nova população. Se conseguirmos encontrar seres um pouco melhores, mais “inteligentes”, com uma iteração, por que não aplicar várias outras?
Sendo assim, a nova população gerada serve como população para novos testes, onde selecionaremos novamente os melhores para reproduzi-los, criando assim um ciclo de busca progressiva de seres com comportamentos ideais.
Os algoritmos genéticos baseiam-se assim na combinação da estratégia “gerar-e-testar” combinada com a teoria darwiniana da evolução e com a genética.
Desta forma, podemos dizer que um algoritmo genético executa os seguintes passos:

  • (1) Cria uma população de seres inicialmente atribuindo valores aleatórios aos seus cromossomos;
  • (2) Executa-se um teste / simulação com a atual população visando pontuar cada um de seus membros;
  • (3) Selecionam-se os membros com melhor desempenho (pontuação);
  • (4) Se condição de parada foi atingida (um número máximo de gerações, por exemplo), encerre algoritmo e retorne os membros encontrados em (3) como sendo a solução;
  • (5) Executa-se a reprodução de uma nova população, onde os pais serão os melhores membros encontrados em (3). Durante a reprodução, podem-se aplicar técnicas a fim de garantir que a diversidade de cromossomos não será perdida. Diversidade esta que pode ser conquistada por meio de crossover e mutações, por exemplo;
  • (6) Retornar ao passo (2).

Antes de começarmos a descrever cada etapa apontada, precisamos compreender a estrutura de um cromossomo.

O Cromossomo

Um cromossomo trata-se de uma estrutura que irá armazenar todas as informações que nós desejamos que possam sofrer alterações durante a evolução de nossos “seres”, desta forma, para cada tipo de problema que queiramos resolver, teremos um determinado conjunto de parâmetros (genes) a serem inseridos em nosso cromossomo.
Suponhamos que estejamos trabalhando em um jogo de RPG com combate em que os personagens possuam cinco características primárias: força, poder de fogo, habilidade, armadura e resistência (sim, estas são as cinco características primárias existentes no sistema de RPG chamado 3D&T).
Desta forma, se quisermos simular partidas entre NPCs (personagens não jogáveis) a fim de descobrir qual a melhor combinação destas habilidades, podemos criar um cromossomo que contenha estas cinco informações e iterar por várias gerações, tendo então um cromossomo mais ou menos da seguinte forma:

Exemplo de características para um cromossomo em um algoritmo genético

Exemplo de características para um cromossomo em um algoritmo genético

Perceba que os dados foram todos agrupados em uma única estrutura e cada uma das características é agora um gene (ou um conjunto de genes).
Vamos supor que criemos um personagem aleatoriamente com:
•    Força = 4;
•    Poder de Fogo = 3;
•    Habilidade = 2;
•    Resistência = 1;
•    Armadura = 2.
O cromossomo deste personagem teria, então, estes valores:

Exemplo de cromossomo para um algoritmo genético

Exemplo de cromossomo para um algoritmo genético

Levando-se em consideração que cada atributo pode ter um valor máximo de 15, poderíamos representar esse mesmo cromossomo como uma cadeia de bits (armazenada em uma string ou em uma variável numérica), onde cada um dos genes ocuparia 4 bits, assim: 0100.0011.0010.0001.0010 (os pontos aqui somente são usados para facilitar a compreensão de quais bits estão representando qual gene, pois na verdade armazenaríamos somente a cadeia em si.
Sendo assim, alguns problemas podem ter uma melhor solução quando usando a cadeia de bits, enquanto que outros podem ser mais facilmente compreensíveis usando uma cadeia de números inteiros ou reais ou até mesmo strings.
Em nosso próximo artigo, falaremos sobre cada um dos passos necessários em um algoritmo genético.

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS

Processamento de Linguagem Natural

Processamento de Linguagem Natural

Em muitas das áreas que estudam e empregam o uso de Inteligência Artificial, este é um recurso que vem sendo pouco estudado e empregado devido a diversos problemas e dificuldades que há, não somente na própria tarefa, como na utilização de forma adequada, bem como na relação custo x benefício.
A fim de entendermos do que se trata o processamento de linguagem natural, precisamos inicialmente estudar o que significa compreender, conceito-base para a interpretação de suas funcionalidades.

Definição de Compreensão

A compreensão é o ato de transformar uma forma de representação em outra que seja significativa para o ambiente em questão e que permita o mapeamento para um conjunto de ações apropriadas.
Estamos compreendendo algo quando vemos certa cena e processamos quais os acontecimentos ocorridos na mesma. Da mesma forma, estamos compreendendo algo quando interpretamos o significado de algo lido ou ouvido, tanto para fins de armazenamento da informação, quanto para a tomada de algum tipo de decisão.
Uma grande dificuldade existente na compreensão de uma informação é quanto à forma de representar o objeto a ser compreendido e à interpretação do mesmo.
Por exemplo, dada uma fotografia, como identificar os elementos que devem ser considerados importantes? Como representar tais informações?

Riscos de ambiguidade/má interpretação na compreensão

Rabuske (1995), em sua obra Inteligência Artificial, lembra-nos que há várias possíveis formas de mapear, isto é, de relacionar, objetos e seus possíveis significados. Os mapeamentos mais comuns são:

  • Um-para-um – acontece quando um dado objeto somente admite um único significado. Um exemplo disso seria a expressão matemática a = b*c + d, que possui somente uma forma de ser interpretada;
  • Um-para-vários – ocorre quando um dado objeto admite vários significados, isto é, temos várias possíveis interpretações para uma expressão. Um exemplo poderia ser a frase “eles estão no avião”, que não deixa claro, por exemplo, se o avião encontra-se no chão ou no ar, bem como não descreve o que “eles” estão fazendo no avião;
  • Vários-para-um – ocorre quando vários objetos apresentam um mesmo significado. É o caso de palavras sinônimas, onde várias palavras podem ser definidas como assumindo o mesmo significado ou significado similar.

Quando se fala de Processamento de Linguagem Natural, sabe-se que o mapeamento “um-para-vários” representa um desafio a ser vencido, pois enquanto que cada palavra pode ter mais de um significado, em uma frase as mesmas geralmente admitem somente um possível uso e cabe ao algoritmo identificar qual o correto uso.
O Que é Ruído?

Ruído é qualquer interferência capaz de alterar o objeto a ser compreendido de uma forma indesejada, podendo levar inclusive à incapacidade de compreensão do mesmo.

Geralmente, quando se busca compreender algo primeiro tenta-se eliminar possíveis ruídos. Um ruído pode ser facilmente isolado ou estar tão inserido na mensagem que sua remoção leva inevitavelmente à perda de parte da informação.

O Que é Processamento de Linguagem Natural?

É a compreensão de uma informação falada ou escrita por meio de regras equivalentes àqueles existentes na comunicação lingüística humana.
Os mesmos problemas existentes na compreensão em geral encontram-se aqui, no processamento de linguagem natural (PLN), devendo-se reforçar os cuidados quanto à ambigüidade da informação bem como na interpretação de dados dependentes do contexto.

Aplicações do Processamento da Linguagem Natural

Uma vez que PLN lida diretamente com mensagens possíveis de serem geradas por seres humanos sem grandes dificuldades (desde que estes estejam aptos à fala e/ou escrita em mesma linguagem que a empregada), esse tipo de técnica possui grande utilidade em sistemas que necessitem de grande interação com os usuários.
Um exemplo disso são aplicações de chatting, ou seja, que lidam com conversas com seres humanos. Esse tipo de aplicações geralmente é conhecido como chatbot, chatterbot ou mesmo chatting robot.
Essas aplicações de chatting podem ser usadas de diversas formas, desde um serviço de atendimento ao consumidor automatizado a um sistema de identificação e tratamento de problemas de saúde. E não podemos esquecer da possibilidade de emprego também na educação, por meio de um possível tutor inteligente, por exemplo, e nos jogos, oferecendo um ambiente com maior interação com o jogador.

Fases do Processamento de Linguagem Natural

A fim de compreendermos melhor como se dá o processamento de uma informação textual, tomemos como exemplo a frase “Eu quero imprimir o arquivo .init do Mário”, que deve ser processada e atendida pelo computador. As cinco fases (ou etapas) que o programa deverá executar a fim de atender corretamente são:

Análise Morfológica

Cada palavra é analisada e classificada isoladamente, levando em consideração a sua própria estrutura. Analogamente ao estudo da língua portuguesa, equivaleria a classificar cada palavra segundo sua classificação morfológica (adjetivo, substantivo, verbo, etc).

Palavras cuja estrutura (grafia, por exemplo) estejam incorretas podem ser ignoradas/descartadas neste ponto.

No exemplo dado, deve-se separar cada parte da expressão morfologicamente. A expressão “do Mário”, por exemplo, tornar-se -á preposição “de” mais artigo “o” mais substantivo próprio “Mário”.

“.init” deve ser reconhecido como um adjetivo qualificando a extensão de um arquivo.

Análise Sintática

Analisa-se uma sequência linear de palavras a fim de analisar o seu relacionamento e emprego na frase.Comparando com o estudo da gramática portuguesa, equivaleria a classificar cada expressão segundo seu emprego (análise sintática) na frase, como sujeito, predicado verbal, etc.

Sequências de palavras criadas/organizadas de forma errônea podem ser rejeitadas aqui, como: “Carro o meu azul é”, que apesar de ser correta morfologicamente (cada palavra está escrita corretamente), não satisfaz as regras gramaticais sintáticas.

Abaixo, uma imagem de como seria a árvore da análise sintática para a frase em questão, segundo Elaine Rich & Kevin Knight:

Análise sintática de um texto

Análise sintática do texto "Eu quero imprimir o arquivo .init do Mário"

No processamento sintático (etapa correspondente à transformação da frase plana em estrutura hierárquica das unidades de significado da frase), também conhecido como parsing, geralmente encontramos dois componentes principais:

  • Uma gramática, que é a representação declarativa dos fatos sintáticos da linguagem, isto é, que é capaz de reconhecer e validar todas as regras sintáticas (bem como os elementos morfológicos) da linguagem em questão;
  • Um analisador, que se trata de um procedimento que compara a gramática com as frases de entrada a fim de produzir corretamente as estruturas a serem analisadas.

Análise Semântica

Neste passo, as estruturas criadas pelo analisador sintático recebem significado, mapeando assim cada estrutura sintática a um objeto no domínio da tarefa.

Novamente, caso não seja possível fazer um mapeamento adequado, uma estrutura pode ser descartada. Rich & Knight citam Chomsky, ao exemplificar a construção frasal “Ideias verdes sem cor dormem furiosamente”, que apesar de bem construída sintaticamente, pode ser considerada semanticamente anômala.

Duas coisas devem ser feitas aqui (mais uma vez, segundo Rich & Knight):

  • Mapear palavras isoladas para objetos apropriados na base de conhecimentos ou na base de dados. Este processo é conhecido como processamento léxico e é responsável por identificar o significado de cada palavra em um dicionário, resolvendo problemas de ambiguidade por meio de alguma das técnicas possíveis. Wilks (1972), por exemplo, sugere o emprego da semântica de preferência;
  • Criar estruturas corretas que correspondam ao modo como os significados das palavras isoladas combinam entre sim. Esta etapa é denominada processamento em nível de frase, e várias são as abordagens aqui possíveis, como  gramáticas semânticas, gramáticas de casos, análise conceitual e interpretação semântica aproximadamente conceitual.

Aqui, deve-se ter uma base de conhecimentos suficiente para que possamos associar cada expressão/palavra a fim de determinar o relacionamento entre elas.

Integração de Discurso

Geralmente, o significado de uma frase é melhor compreendido (às vezes, somente pode ser compreendido) a partir da interpretação da mesma junto com todas as frases antecedentes e sucessoras a ela. Esta parte pode ser comparada à interpretação do texto, onde a compreensão do todo é importante para que se possa compreender cada parte.

No exemplo dado, precisamos determinar quem são os usuários “Eu” e “Mário” a fim de saber quem está requisitando e quem é o proprietário do arquivo requisitado. Isso pode ser determinado por meio de análise de frases anteriores, bem como numa verificação do sistema (verificando quais os usuários chamados Mário existem no sistema, por exemplo).

Análise Pragmática

Finalmente, a estrutura frasal é reinterpretada a fim de determinar o que se disse (se uma solicitação, pergunta, afirmação, etc.) a fim de determinar melhor qual deverá ser a reação do programa.

Um exemplo disso seria a frase “Qual é o seu nome?” que deve, ao final, ser interpretada como uma solicitação para que o programa responda com o seu “nome”.

No exemplo dado, a resposta dada será a execução do comando:

lpr /wspires/coisas.init

Onde lpr é o comando para impressão e /wspires/coisas.init é o arquivo .init do Mário.

Bibliografia Sugerida

Quem desejar aprofundar-se no assunto, pode procurar pelos livros:

  • INTELIGÊNCIA ARTIFICIAL, de Renato Antônio Rabuske – possui linguagem bastante didática e de muito fácil compreensão, aconselhando-se então principalmente para início de estudos;
  • INTELIGÊNCIA ARTIFICIAL, de Elaine Rich e Kevin Knight – um pouco mais aprofundado e detalhado, descrevendo muito dos conceitos aqui apresentados. Aliás, este e o anterior foram tomados como referências bibliográficas para a elaboração deste artigo;
  • INTELIGÊNCIA ARTIFICIAL UTILIZANDO LINGUAGEM C – um pouco diferente dos anteriores, este aqui é um pouco mais prático, apresentando algoritmos e código-fonte em C para aqueles que gostam de ver “um pouco mais de perto” como as coisas funcionam.

A obra de Rich & Knight são geralmente muito bem indicadas e deve estar presente em sua leitura!

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS

Uma Introdução aos Agentes Inteligentes

Agentes Inteligentes

Conforme avançamos na área de Inteligência Artificial percebemos a importância de criar uma entidade que possa modelar mais naturalmente (em meio virtual!) o que nós conhecemos por um ser inteligente, surgindo assim o conceito de um agente inteligente.

Podemos compreender um agente inteligente como sendo um sistema (ou um componente de um sistema) capaz de organizar, selecionar, produzir informações e tomar decisões a partir de alguma fonte de dados.
Em outras palavras, um agente é um subsistema criado com a finalidade de reter e analisar informações e responder da melhor forma possível. No caso de aplicações para a área de robótica, “melhor forma possível” geralmente quer dizer com a resposta mais perfeita possível, já no caso de jogos, um bom agente inteligente deve ter um comportamento não perfeito, mas o mais próximo possível do comportamento humano.
Segundo palavras de Menezes, Fuks e Garcia, “a tecnologia de agentes permite que se repense a natureza da interação entre homem e computador, na qual esse último torna-se um parceiro do usuário, cooperando para o alcance dos objetivos traçados”.

Características

Todo agente, a fim de ser dito autônomo, deve manifestar em sua estrutura as seguintes propriedades:

  • Autonomia, de modo a agir sem qualquer tipo de intervenção, possuindo controle sobre suas ações e estado interno;
  • Sociabilidade, de modo a interagir com outros agentes (artificiais ou humanos) através de algum tipo de linguagem de comunicação;
  • Reatividade, de modo a perceber alterações em seu ambiente, reagindo a tempo;
  • Proatividade, não só reagindo ao ambiente, mas tomando iniciativas quando conveniente.

Arquitetura e Aprendizado de Máquina

A arquitetura utilizada no desenvolvimento de um agente pode variar muito, de acordo com o tipo de aprendizado que desejamos que ele tenha.
Um agente pode, por exemplo, ser construído por meio de sistemas de produção ou reconhecimento baseado em casos. Tais formas de aprendizado não permitem que o agente aprenda durante a execução das tarefas, mas são algumas das mais simples para quem quiser implementar um agente inteligente.
Um agente pode, também, utilizar-se de algoritmos genéticos (IA evolutiva) ou redes neurais (IA conexionista) a fim de buscar aprender durante sua execução, bem como modelar dois ótimos fatores que tais linhas trazem: a evolução e a conexão como meios de aprendizado.
Um outro exemplo seria o bom uso de máquinas de estados finitos e algoritmos de pathfinding em agentes inteligentes, muito úteis em jogos de estratégia em tempo real, por exemplo.

Na verdade, geralmente fazemos uma mescla de várias técnicas e formas de aprendizado, a fim de compor um agente com o perfil que melhor se adequa ao da tarefa proposta.

Planejamento, Reação e Pró-Ação

Em computação, quando não aplicamos recursos e/ou técnicas de IA em desenvolvimento de software, terminamos com um sistema que é capaz de responder corretamente a solicitações, mas só àquelas previamente planejadas. O que acontecerá, então, caso o sistema se depare com algum tipo de dados para o qual ele não foi preparado previamente?
A princípio, uma hipótese (e provavelmente a que mais ocorre) é a de que o sistema irá quebrar (ocorrerá um crash, consumindo assim vários recursos para, então, voltar 100%).
Uma segunda hipótese, menos desinteressante, é a de que o programador cria condições especiais a serem executadas sempre que dados estranhos são visualizados.
Bem, por mais que possamos ter bons resultados por meio do emprego do bom planejamento em um sistema, ele por si só não nos basta, principalmente na área de jogos.
Surge assim a necessidade de algo mais reativo, que pudesse compreender melhor as opções a fim de fazer suas escolhas. Surge assim a idéia de agente como um ser altamente reativo, capaz de responder as decisões do usuário.
Entretanto, somente a capacidade reativa não basta, isto é, não é suficiente para que possamos ter um sistema com um “comportamento humano”: humanos não são somente reativos, mas também (ou ao menos uma boa parte de nós) pró-ativos.
Por pró-ação, entenda-se a capacidade não somente de tomar decisões em resposta a outra (reação), mas também de tomar decisões por iniciativa própria tendo como base um comportamento dirigido ao(s) objetivo(s) principal(is).
E, como falamos anteriormente, a pró-ação é uma das características de nossos agentes inteligentes, o que os torna tão interessantes na área de jogos.
É importante salientar que um agente inteligente somente é pró-ativo se o mesmo possui autonomia na execução de suas tarefas!

____________________________________________________________________

Agora que já falamos um pouco sobre agentes inteligentes, você pode experimentar elaborar algum sistema que utilize um ou mais agentes.

Os tipos de sistemas que podem utilizá-los são inúmeros, por exemplo:

  • Como tutores na educação (leia o artigo O uso de agentes inteligentes na educação para saber mais sobre agentes inteligentes no processo ensino-aprendizagem);
  • Como atores em jogos ou simuladores;
  • Na determinação de soluções para problemas específicos (conhecidos principalmente como sistemas especialistas).

Escolha o que melhor lhe convier, escolha qual a abordagem irá usar na implementação (citamos algumas neste artigo) e mãos à obra!

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS

Exploração de Grafos, Caixeiro-Viajante e o Algoritmo A Star em Problemas de Pathfinding

Exploração de grafos em Inteligência Artificial

Enquanto podemos encontrar a solução para diversos jogos de tabuleiro e análise de árvores de decisão, outros problemas podem necessidtar de estruturas mais complexas, que permitam buscas em percursos possivelmente cíclicos, como é o caso dos grafos.

Grafos são utilizados em diversos problemas, por exemplo em problemas que envolvem exploração de informações interconectadas, como a exploração de um mapa rodoviário a fim de estabelecer a melhor rota, um problema de logística contemporâneo.

Dentre os vários problemas que envolvem exploração de grafos, estudaremos o problema do “caixeiro-viajante” e o algoritmo A-Star, um dos vários algoritmos propostos na resolução de problemas de pathfinding.

O problema do Caixeiro-Viajante

Àqueles que não conhecem o problema do caixeiro-viajante, trata-se de um problema bastante conhecido no campo da computação.

Um caixeiro-viajante precisa visitar N cidades, sendo que as distâncias entre elas são variáveis. Ele deve partir de uma dessas cidades, visitar exatamente uma vez todas as demais e retornar à primeira. Como as distâncias entre as cidades não são sempre iguais, é necessário que se busque qual a melhor rota a fim de percorrer a menor distância possível.

Apesar de ser um problema aparentemente simples que pode ser resolvido testando todas as permutações possíveis do conjunto de cidades, é fácil perceber que esse problema cresce exponencialmente em relação ao número de cidades.

Em outras palavras, até pode ser fácil resolver por força bruta, testando todas as combinações, quando o número de cidades é pequeno, mas quanto maior for o número delas, mais demorado será para encontrar a solução.

Este é um problema NP-Completo, isto é, um problema cuja solução não pode ser determinada em tempo polinomial.

Várias soluções são propostas para o problema do Caixeiro-Viajante, sendo duas delas:

  • Tentativa-e-erro – testa todas as permutações possíveis, como dito anteriormente, devolvendo a melhor solução. Tais algoritmos são de ordem exponencial;
  • Estratégia gulosa – consiste em buscar, na i-ésima iteração, a cidade vizinha com menor custo (distância) em relação à cidade atual. Apesar de encontrar uma boa solução em tempo hábil, tal abordagem não garante que a solução seja ótima!

Curiosidade: atualmente, o recorde é de 24.978 cidades. Isso mesmo: conseguiu-se, por meio de bom uso de hardware e software (escolha adequada de algoritmos) resolver o problema para 24.978 cidades!

Pathfinding

Similar ao problema do caixeiro-viajante, um algoritmo de pathfinding deve encontrar o melhor caminho entre dois pontos no plano/espaço, a partir de sua representação em um grafo.

É possível encontrar a aplicação de técnicas/algoritmos de pathfinding principalmente em áreas que exploram simulação, como simuladores, jogos, etc.

Da mesma forma que o problema do caixeiro-viajante, tal problema pode ser resolvido por força bruta, entretanto também cresce exponencialmente, o que nos obriga a procurar novas e melhores técnicas.

Algumas possíveis soluções são:

  • Tentativa-e-erro;
  • Algoritmo Dijkstra;
  • Algoritmo A-Star (A* );
  • Algoritmos Genéticos.

Como o nosso foco aqui é ter uma visão geral da área de Inteligência Artificial e de suas aplicações, estudaremos somente um destes algoritmos, no caso, o algoritmo A-Star.

O Algoritmo A-Star (A*)

O algoritmo A-Star é um algoritmo do tipo “gera-e-testa”, isto é, ele gera uma possível situação e testa se ela é a solução. Se for, retorna-a com sucesso, caso contrário, gera outra até encontrar a solução ou não ter mais possíveis situações, quando então retorna fracasso.

Até aqui, ele parece idêntico ao clássico “tentativa-e-erro” usando força bruta, onde todas as possibilidades são obrigatoriamente testadas a fim de poder selecionar a melhor. O que difere ambos os algoritmos está na forma como o A-Star seleciona o próximo nó a ser aberto (no caso, a próxima situação a ser testada), que lhe garante encontrar em primeiro lugar a melhor solução, podendo então interromper a busca.

Para conseguir isso, o algoritmo A-Star trabalha com a ideia de “busca melhor-primeiro” e, para determinar qual deverá ser o possível próximo melhor passo para efetuar todo o seu percurso, ele baseia-se na distância percorrida até encontrar o tal nó mais a menor distância possível para encontrar o nó-destino, obtida por meio de uma função heurística.

O que garante o sucesso do algoritmo A-Star é justamente essa análise não somente da qualidade do nó para chegar no destino, obtida por uma função heurística h , mas também da qualidade do caminho percorrido até chegar àquele nó a partir da origem, conhecida aqui como função g. Denominando a soma de ambas de f = g + h, teremos então que o algoritmo de A-Star funciona da seguinte forma:

  • Inicialmente temos somente o nó origem em uma lista de nós abertos. Calculamos valores para g (igual a 0), h (distância heurística até o nó destino) e f (igual a h). Fechados é inicialmente uma lista vazia;
  • Verifique se abertos está vazia, se sim, retorne erro e encerre o algoritmo. Caso contrário, seleciona-se o nó em abertos com o menor valor de f, remove-o e chama-o de melhor_no. Se este for igual ao nó destino, ou seja, se for solução, retorne a solução (que pode ser somente este nó ou todo o percurso, o que nos obriga a ter um ponteiro para cada “nó-pai” a fim de recuperar qual foi o percurso até chegar a ele) com sucesso e encerra o algoritmo. Caso contrário, precisamos verificar cada sucessor de melhor_no a fim de procurar o caminho. Inicialmente, calcule o g(sucessor) como sendo g(melhor_no) + custo para ir de melhor_no a sucessor;
  • Verifique se sucessor já está em abertos, pois se estiver, precisamos verificar qual o caminho com melhor g, se o antigo ou o novo. Se o antigo caminho (aquele que usava o mesmo sucesso anteriormente) for o melhor (com o g menor), simplesmente ignore este sucessor e vá para o próximo. Caso contrário, faça aquele nó que representa o sucessor apontar para o melhor_no e atualize seu g para o valor calculado no item anterior;
  • Se sucessor não estava em abertos, precisamos ainda verificar se o mesmo não já está em fechados. Se ele estiver, significa que não somente já criamos esse nó, como também já criamos os seus vizinhos/sucessores, em outras palavras, precisamos ajustar não somente ele, mas também os que estão após ele em seu percurso. Para tal, verifique se o antigo nó (aquele que você encontrou em fechados) possui menor g que o atual sucessor. Se sim, não é necessário atualizar, pois o anterior já era um melhor caminho. Caso contrário, comece atualizando o g daquele nó e fazendo ele apontar para melhor_no. Depois disso, recursivamente, atualize o valor de g e f em cada um dos nós sucessores dele, dos nós sucessores de seus sucessores e assim por diante, de forma recursiva;
  • Se o nó sucessor analisado até então não está nem em abertos nem em fechados, coloque-o em abertos e acrescente-o à lista de sucessores de melhor_no. Após fazer isso para todos os possíveis nós sucessores de melhor_no, coloque melhor_no na lista de fechados e retorne ao segundo passo/item.

Esta descrição do algoritmo A-Star baseia-se na descrição apresentada por Elaine Rich e Kevin Knight em seu livro Inteligência Artificial, a qual eu acho bastante completa e compreensível para a implementação do algoritmo, sendo assim, se você tiver alguma dúvida quanto à implementação baseando-se em minha explicação, você pode procurar o livro dos autores supracitados a fim de mais alguma explicação.

Quem tiver interesse de ver uma aplicação de A-Star em busca pelo melhor caminho, aqui está:

Aplicação de A-Star para encontrar a distância entre uma cidade do mapa e Bucareste

Essa aplicação possui seu código-fonte em Delphi (acredito que a versão 2006) e pode ser usada por qualquer um. Então, divirta-se. :)

[Conteúdo pertencente ao Material do curso de Inteligência Artificial]

Share and Enjoy

  • Facebook
  • Twitter
  • Delicious
  • LinkedIn
  • StumbleUpon
  • Add to favorites
  • Email
  • RSS