Redes Neurais Auto-Organizáveis - SOM

Nest post, irei discutir um pouco sobre as redes neurais auto-organizáveis (Self-Organized-Maps -SOM), também conhecidas como Mapas de Kohonen ou mapas topográficos.

Até agora, meus artigos sobre redes neurais focaram no campo de aprendizado supervisionado, isto é, o aprendizado pelo qual apresentamos um conjunto de padrões a uma rede neural em conjunto com as saídas desejadas. A rede então ajusta os pesos visando obter as saídas corretas em função das entradas. Entretanto, vamos supor que não temos de antemão o conjunto de saídas desejadas. E agora ? Como podemos fazer com que a rede neural nos traga alguma informação útil ? Isto se chama o aprendizado não supervisionado. A tarefa agora é explorar as semelhanças entre os exemplos de entrada e agrupar padrões parecidos sem conhecer as classes de antemão. Algumas razões pelo qual escolhemos este método são:

• Agrupamento de padrões (Clusters)
• Redução de dimensionalidade
• Descoberta de correlações escondidas entre os dados (mineração de dados)
• Compressão de dados (Extração de características)
• Classificação
  
  

A rede SOM é uma rede neural de 2 camadas que aceita padrões de N-dimensões como entrada e os mapeia para um conjunto de neurônios de saída, o qual representa o espaço dos dados a serem agrupados. O mapa (camada) de saída, que é tipicamente bi-dimensional, representa as posições dos neurônios em relação aos seus vizinhos. A idéia é que neurônios topologicamente próximos respondam de maneira semelhante a entradas semelhantes. Para isso todos neurônios da camada de entrada são todos conectados aos neurônios de saída.

Modelo de uma rede SOM

Os passos do algoritmo de treinamento do SOM é simples:

1. Inicialize os pesos com valores aleatórios.
2. Apresente o padrão de entrada à rede.
3. Escolha o neurônio de saída com maior estado de ativação (Neurôno "vencedor").
   
4. Atualize os pesos dos neurônios vizinhos ao neurônio vencedor, usando um fator de aprendizado (Geralmente baseado no raio de vizinhança e taxa de aprendizado).
5. Reduza o fator de aprendizado monotonicamente (linearmente).
6. Reduza o raio de vizinhaça monotonicamente (linearmente).
7. Repita os passos a partir do passo 2 até que a atualização dos pesos sejam bem poucas.
   
   
   

O tamanho de vizinhaça irá inicialmente incluir todos neurônios da camada, e sendo reduzindo progressivamente durante a execução do treinamento, até incluir apenas o próprio neurônio vencedor.

Para descrever o treinamento acima, apresentarei um exemplo de uma solução de um problema com a rede SOM. O exemplo consiste de um conjunto de 25 alimentos, onde a rede SOM irá tentar agrupá-los em regiões de similaridade, baseado em três parâmetros, que são as informações nutricionais do alimento: Proteínas, carboidratos e gordura.

Logo, o desafio para esta rede SOM é reduzir os dados contendo três dimensões para apenas 2 dimensões, sem perda de informação. As redes SOM fazem isso automaticamente identificando as características diferenciais que terão maior efeito no resultado final do treinamento da rede.

O conjunto de exemplos de entrada segue abaixo:

Após executada a rede SOM com este conjunto de dados, os alimentos são posicionados em um plano de 10 x 10 agrupados em regiões de acordo com suas semelhanças. Uma representação gráfica do resultado é apresentado abaixo:

Agrupamento de regiões

Como o mapa de características agrupou os itens, reduzindo as três dimensões para apenas 2 dimensões ? Bem, um número de regiões foram geradas. Por exemplo, água, que não contém nenhuma proteína, carboidratos ou gordura foi empurrado para o canto direito superior. Seguindo para o canto superior esquerdo, o açúcar que é formado praticamente de carboidratos, foi posicionado. No canto inferior direito, manteiga reina soberana, sendo composta inteiramente por gordura. Finalmente, o canto esquerdo inferior é ocupado por filé de atum e frango assado, que contêm a maior concentração de proteína em relação aos alimentos apresentados. Os alimentos restantes são distribuídos entre esses extremos, onde os alimentos "fast food" ocupam a zona do centro.

Podemos observar que a rede SOM conseguiu agrupar em regiões os alimentos de acordo com as informações nutricionais. Podemos inferir 4 tipos de grupos: O grupo formado pelos padrões onde a proteína foi a característica determinante, outro pela gordura como característica predominante, e carboidratos como determinante. Por fim o último grupo seriam os alimentos na região central formados por alimentos formados por quantidades balanceadas dos 3 componentes acimas demonstrados. Isso que acabamos de fazer foi uma análise de dados e extração de informações úteis de um conjunto de dados brutos: Mineração de dados.

Abaixo disponibilizo o código em Python da rede SOM, o qual você poderá modificar ou alterar o conjunto de entradas. Tente adicionar mais dimensões no conjunto de entradas (novas infomações nutricionais) e observe os resultados. É claro que não é sempre óbvio ver o que está acontecendo, especialmente com um grande número de dimensões. Entretanto, eventualmente você poderá concluir, e até as vezes inesperadamente, alguma correlação entre os dados. Isso é a magia da mineração de dados!

Não irei exibir o código aqui no site, pois é um pouco grande, mas deixarei o link para download. Espero que usufruam bem e ajudem no seu aprendizado de redes neurais!

Até a próxima,

Marcel Pinheiro Caraciolo

Introdução à Inteligência de Enxame - Otimização por Enxame de Partículas (PSO)

Olá pessoal,

Neste novo tutorial abordarei um novo ramo na área de inteligência artificial, e de certo modo, com grande motivação. Não que os outros artigos não tenham sido motivantes, mas é justificado pelo fato que este tutorial é baseado na área de conhecimento que preparei minha tese de conclusão de curso de graduação: Multi-Ring: Uma nova topologia para o algoritmo de otimização por enxame de partículas (PSO).

Mas antes de entrarmos em detalhes sobre o que é PSO ou enxame de partículas, é necessário entendermos o conceito de inteligência de enxame (swarm intelligence).

Enxame de formigas colaborando para criar uma ponte viva.

O que é Inteligência de enxame ?

Swarm Intelligence (Inteligência de enxame) é o termo utilizado para designar sistemas de inteligência artificial onde o comportamento coletivo dos indivíduos em uma população causa simples soluções coerentes ou padrões a surgir.

O termo "enxame" (ou população) é utilizado de forma genérica para se referir a qualquer coleção estruturada de agentes capazes de interagir. O exemplo clássico de um enxame é um enxame de abelhas. Entretanto, de maneira similar podemos considerar também que outros sistemas, como por exemplo uma colônia de formigas, podem ser vistas como um enxame, onde os agentes são as formigas; uma revoada de pássaros que é um enxame, onde os agentes são os pássaros e até um engarrafamento, onde os agentes são os carros. A noção de enxame sugere um aspecto de movimento coletivo no espaço, todavia, como em um enxame de pássaros, estamos interessados em todos os tipos de comportamentos coletivos, não somente espacial.

Logo, podemos dizer que as interações coletivas de todos os agentes dentro do sistema muitas vezes leva a algum tipo de comportamento ou inteligência coletiva. Este tipo de inteligência artificial inclui qualquer tentativa de projetar algoritmos ou dispositivos distribuídos de solução de problemas sem ter um controle centralizado, inspirado no comportamento coletivo de agentes sociais e outras sociedades animais.

A inteligência coletiva é uma propriedade de sistemas compostos por agentes não (ou pouco) inteligentes com capacidade individual limitada, capazes de apresentar comportamentos coletivos inteligentes. Tais comportamentos seguem as seguintes propriedades:

• Proximidade: Os agentes devem ser capazes de interagir .

• Qualidade: Os agentes devem ser capazes de avaliar seus comportamentos.

• Diversidade: Permite ao sistema reagir a situações inesperadas.

• Estabilidade: Nem todas as variações ambientais devem afetar o comportamento de um agente.

• Adaptabilidade: Capacidade de se adequar a variações ambientais.
  

Exemplos de sistemas de inteligência de enxame

Otimização por Colônia de Formigas (ANT Colony Optimization - ACO)

O comportamento da colônia de formigas tem sido um dos mais populares modelos de comportamento de enxame. Formigas por si só podem parecer agir de forma aleatória e sem qualquer efeito discernível, mas quando a interação entre as formigas são tomadas em conjunto, emerge uma inteligência coletiva e de comportamento que tem a capacidade de resolver uma série de problemas. A idéia por trás deste algoritmo é a busca de um melhor caminho em um conjunto de rotas baseado no comportamento das formigas procurando um caminho entre o seu formigueiro (colônia) e o local do alimento. Uma técnica probabilística muito poderosa para resolver problemas computacionais de otimização.

O algoritmo de otimização por colônia de formigas já foi aplicada na solução de diversos problemas de otimização combinatória nos últimos anos, como roteamento de otimização de redes de comunicação, programação de fábricas e roteamento de veículos. Não entraremos em detalhe agora sobre o ACO (Ant Colony Optimization) já que não é o foco deste artigo, mas fiquem à vontade para descobrir mais sobre o algoritmo e sua implementação. Em outras oportunidades poderemos detalhar mais este algoritmo. Mais informações sobre o mesmo podem ser encontradas neste link.

Este artigo irá tratar de outro algoritmo popular na área de inteligência de enxame , o algoritmo de otimização por enxame de partículas (PSO).

Otimização por enxame de partículas (Particle Swarm Optimization - PSO)

O algoritmo de otimização por enxame de partículas, por outro lado, é um tipo de inteligência de enxame inspirado no comportamento de bandos de pássaros. A busca por alimentos e a interação entre aves ao longo do vôo são modeladas como um mecanismo de otimização. No caso, a área sobrevoada é equivalente ao espaço de busca e encontrar o local com comida corresponde a encontrar a solução ótima. O algoritmo é modelado por pássaros (doravante chamados de partículas) que fazem uso de sua experiência e da experiência do próprio bando para encontrar a melhor região do espaço de busca.

Aves voando "alinhadas" em busca de alimento

Há anos vem sendo estudado o comportamento social de alguns grupos de animais como a organização de abelhas, formigas e pássaros na busca de alimentos ou novos locais para estabelecer sua nova moradia. Este último grupo, em especial despertou um grande interesse de alguns pesquisadores, na década de 80, onde se destaca dentre eles o biológo Frank Heppner. Após diversas observações sobre o comportamento de bando de pássaros em revoada, Heppner decidiu modelar aquela inteligência coletiva para usá-la em métodos de busca para solução de problemas. Os estudos de Heppner consideravam que o comportamento de várias espécies de pássaros, em bando ao longo do vôo, fazia o uso de alguma lógica e de alguma forma de comunicação. Após vários estudos e observações, Heppner descreveu o raciocínio por trás daquele comportamento, qualificando-o como comportamento social.

James Kennedy e Russel Eberhart, inspirados no comportamento social dos pássaros estudados por Heppner, desenvolveram uma técnica de otimização que veio a ser conhecida como enxame de partículas. Essa denominação se deu, pois se notou que o modelo escrito por Heppner demonstrava características de um enxame inteligente, onde seus membros que apresentavam tal comportamento foram generalizados para o termo partículas.

Não só o nome do algoritmo, como os demais aspectos do modelo estudado por Heppner ganharam uma nova conotação. Fazendo uma analogia, o termo partícula foi adotado para simbolizar os pássaros e representar as possíveis soluções do problema a ser resolvido. A área sobrevoada pelos pássaros é equivalente ao espaço de busca e encontrar o local com comida, ou o ninho, corresponde a encontrar a solução ótima.

Para que o bando de pássaros sempre se aproxime do objetivo, ao invés de se perder ou nunca alcançar o alvo focado, utiliza-se o indicador denominado fitness, função que irá avaliar o desempenho das partículas. Para alcançar o alvo focado, sejam os alimentos ou os ninhos, os pássaros fazem uso de suas experiências e da experiência do próprio brando.

O termo indicador da experiência ou conhecimento individual de cada partícula, isto é, seu histórico de vida, é o pbest. Em uma abordagem mais simples, o responsável por representar o conhecimento do enxame como um todo é o gbest. A Tabela 1 apresenta de forma resumida as nomenclaturas descritas acima:

O algoritmo de técnica de otimização por enxame de partículas é um algoritmo que possui uma população de partículas, onde cada partícula representa uma possível solução para o problema de otimização. Cada partícula do exame pode ser representada por um objeto que possui associado a ele um vetor posição, isto é, a posição da partícula no espaço de busca, e um vetor velocidade, responsável por guiar as mudanças da posição das partículas durante a execução do processo.

A idéia é que as partículas voem pelo espaço de busca (mudanças de posição) tendo suas velocidades atualizadas dinamicamente de acordo com o histórico das experiências individuais e coletiva de todo o enxame. Logo, a evolução do algoritmo do PSO está associada à trajetória percorrida pelo enxame e ao tempo gasto para encontrar a melhor solução do problema.

O algoritmo básico de otimização por enxame de partículas pode ser descrito brevemente utilizando os seguintes passos: dada uma população inicial de partículas, atualiza-se o vetor posição a partir do vetor velocidade de cada partícula até que se atinja o critério de parada pré-definido. A figura abaixo ilustra essa lógica:

Fluxograma-Algoritmo PSO

O enxame é inicializado com os valores dos vetores de velocidade e posição gerados aleatoriamente. A primeira iteração do algoritmo inicia com a atribuição de valores aos parâmetros da equação de velocidade. Definem-se então os valores referentes ao enxame, constantes e o critério de parada. Tendo já definido os valores para posição das partículas e suas respectivas velocidades, aplica-se o cálculo do fitness a cada partícula desta população. Conforme explicado anteriormente, o fitness avalia o desempenho da partícula. Com as partículas do enxame avaliadas, extraem-se os pbest e o gbest, isto é, a melhor posição encontrada pela partícula e pelo enxame. Depois as velocidades e as posições de cada partícula do enxame são atualizadas. Diante das novas posições, caso o critério de parada tenha sido atingido, a solução do problema encontrada é apresentada. Caso contrário, aplica-se novamente o fitness a este enxame, atualizam-se os valores de pbest e gbest, caso seja apresentada uma solução melhor, seguido da velocidade e posição de cada partícula do enxame. O laço prossegue até o critério de parada ter sido atingido.

Existem duas variantes bastante utilizadas na literatura para a escolha do critério de parada do algoritmo PSO. Uma é pelo número de iterações, ou seja, quando o algoritmo chega ao fim por que atingiu a última iteração. A outra é pela função de avaliação (Fitness), ou seja, quando o algoritmo chegou ao fim por que alcançou um valor pré-definido para a função.

Outro componente importante que influencia no desempenho do algoritimo PSO é a estrutura ou topologia da comunicação das partículas. Ela rege como as partículas do enxame trocam informações e se comunicam. Logo, a escolha da topologia influencia na avaliação da velocidade das partículas. A depender de como as partículas se comunicam entre si e do problema a ser tratado, a busca pela solução ótima pode priorizar tanto a velocidade de convergência, a qualidade da solução ou ambas. As principais topologias utilizadas como mecanismos de comunicação entre as partículas são: a topologia global e a topologia local. A figura abaixo apresenta a estrutura de tais topologias.

a) Topologia local b) Topologia Global

Na topologia local, conforme ilustrado na figura a), o enxame está organizado em formato de anel e cada partícula deste possui dois vizinhos. Logo, a partícula troca informações apenas com seus vizinhos diretos. Embora a troca de informação entre as partículas seja mais lenta, esta estrutura provê uma melhor qualidade de soluções para problemas multimodais em comparação ao mesmo provido pela topologia global, visto a seguir.

Na topologia global, conforme ilustrado na figura b) acima, o enxame está organizado em formato estrela e todas as partículas estão conectadas entre si. Esta topologia utiliza o mecanismo de vizinhança global, também denominado de gbest para a troca de informação. Ao contrário da topologia anteriormente descrita, esta topologia permite uma convergência mais acelerada, visto que a informação da melhor posição é disseminada rapidamente entre todas as partículas do enxame,porém não garante a qualidade da solução obtida. Nestes casos o algoritmo pode atingir um mínimo local, devido a sua convergência precoce.

Depois dessa breve introdução sobre o algoritmo PSO, vamos agora vê-lo em execução. Iremos utilizar o PSO implementado em Python para solucionar um problema matemático de otimização: a minimização da função esfera (sphere). O objetivo é encontrar a solução ótima, que para esta função seria o seu mínimo global localizado pelo ponto (x,y) através das coordenadas (0,0).

Gráfico em Três dimensões da função esfera

Como podemos observar acima no gráfico plotado da função sphere, que o mínimo desta função encontra-se na região mais baixa (vértice inferior) da função esfera, e é a solução desejada a ser obtida pelo algoritmo de otimização por enxame de partículas.

Para este problema, padronizamos as fronteiras do espaço de busca, a região de inicialização das posições das partículas e o número de dimensões. Utilizamos também uma variação do PSO, com o fator de enxugamento (constriction factor - CONSTRICTED) no cálculo do vetor velocidade, o qual tem obtido um grande desempenho para solução de problemas multi-modais difíceis. A topologia utilizada para a solução deste problema foi a topologia global (todas as partículas conectadas entre si), o qual é bastante utilizada na literatura.

Todo o enxame é inicializado aleatoriamente na sub-região do espaço de busca disponível longe da solução ótima em todas as dimensões de acordo com a função a ser minimizada, neste caso, longe da posição (0,0).

Ao iniciar a execução do PSO, podemos observar o estado das partículas distribuídas aleatoriamente na região do espaço de busca com um alto valor de fitness ( O objetivo é minimizar a função, ou seja foca na redução do fitness). Vejam o histograma/gráfico abaixo:

Histograma -Distribuição Fitness x Partículas- (Iteração: 0)

Distribuição das partículas no espaço de busca (Iteração: 0)

Podemos inferir que há uma dispersão na distribuição das partículas com altos valores de fitness, o que significa que as partículas são inicializadas aleatoriamente em regiões distantes da solução ótima.
A simulação do algoritmo PSO é executada por 10.000 iterações, o qual no fim da mesma, obtemos os seguintes resultados:

Simulação do PyPSO para a solução do problema Sphere

Podemos observar pela figura acima, que após 9000 iterações, o melhor fitness encontrado é o valor 4.46.. e-164 e a melhor posição com o valor 3.03...e-83, ou seja, aproximadamente 0.00. Isto prova que o algoritmo convergiu até a solução ótima, isto é, as partículas se moveram pelo espaço de busca em direção à região que contém a solução ótima, o mínimo global da função matemática o qual estamos tentando minimizar. Claro, que o algoritmo consegue convergir bem antes que 9000 iterações, mas a fim de ilustrar o desempenho do PSO, decidimos executar com 10.000 iterações.

Plotando o histograma de distribuição de fitness e o gráfico da posição das partículas no fim da execução do algoritmo PSO, podemos concluir que os fitness de cada partículas estão com valores na ordem de grandeza e -160, bem próximo ao valor 0.0, o que significa que as partículas convergiram para a solução ótima, pela trajetória no espaço de busca. Observer também o gráfico de distribuição das posições das partículas na iteração 10.000, o qual ilustra as partículas concentradas numa região ao redor do ponto ótimo localizado nas coordenadas (0,0). Embora este seja um estudo de caso, demonstramos o poder do algoritmo PSO que se mostra eficiente na solução de problemas de busca e otimização de alta dimensionalidade.

Histograma - Distribuição de Fitness das partículas (Iteração: 10000)


Distribuição das posições das partículas na região de busca (Iteração: 10000)

Segue abaixo, o código principal utilizado para este experimento:

#Pso Demo

from pypso import Pso
from pypso import Consts
from pypso import GlobalTopology

#This is the Sphere Function
def sphere(position):
    n = len(position)
    total = 0.0
    for i in xrange(n):
        total += (position[i] ** 2.0)
    return total

#Parameters
dimensions = 30
swarm_size = 30
timeSteps = 10000

# PSO Instance

pso = Pso.PSO()
pso.setPsoType(Consts.psoType["CONSTRICTED"])
pso.setTimeSteps(timeSteps)
pso.setTopology(GlobalTopology.GlobalTopology(swarm_size,dimensions))

# The evaluator function (objective function)
pso.setFunction(sphere)
pso.initializeBounds(dimensions)
pso.definePositionBounds(0, dimensions, (-100.0, 100.0))
pso.defineInitialPositionBounds(0,dimensions, (50.0,100.0))
pso.defineVelocityBounds(0,dimensions,100.0)

#Do the swarm movement, with stats
#dump frequency of 10 timeSteps
#import psyco

#psyco.full()

pso.execute(freq_stats=20)

(Código PSODemo.py)

Na época da execução desta simulação, tomei a iniciativa de construir um framework (ainda em desenvolvimento - versão 0.1) denominado PyPsoBox -Python PSO Toolbox- para execução de testes e avaliação de desempenho de algoritmos de otimização por enxame de partículas (PSO) e suas variações. O framework está sendo construído em Python e com suporte apenas para plataformas Windows. Em breve, novas funcionalidades serão adicionadas ao projeto que é gratuito e open-source. Todos estes gráficos acima foram gerados através do framework, que tem suporte para plotagem de gráficos de análise de simulação. Em um próximo post, disponibilizarei um tutorial de como usar o framework para simulações.

O projeto está hospedado no Google Code Hosting e o código está acessível através deste link.

Quero agradecer especialmente ao colega Christian S. Perone, criador do projeto PyEvolve (Um Framework similar implementado em Python para algoritmos genéticos). O trabalho dele serviu-me como forte inspiração para o meu trabalho.

Quaisquer dúvidas, dicas, sugestões para este artigo, framework, fiquem à vontade.

Até a próxima,

Marcel P. Caraciolo

[Artigo] Introdução a Árvores de decisão para classificação e mineração de dados

Um dos maiores dilemas enfrentados por quaisquer sistemas de tomada de decisão é determinar um meio eficiente para produzir classificadores a partir de base de dados em relação ao tempo de processamento e à forma de representação simbólica simples e compreensível que facilite a análise do problema em questão.

Este artigo introduz uma ferramenta bastante popular no processo de descoberta de conhecimento em um banco de dados e consequentemente no auxílio na tomada de decisões : as Árvores de decisão.

Os classificadores baseados na árvore de decisão são um dos ramos na área de inteligência artificial. Mais especificamente, eles pertencem ao sub-campo de aprendizagem de máquina. Isto se deve à sua habilidade de aprender através de exemplos com o objetivo de classificar registros em uma base de dados.

Irei abordar os conceitos iniciais sobre árvores de decisão e como elas podem auxiliar no processo de tomada de decisões através de um exemplo prático. Para isso, usarei uma das heurísticas mais conhecidas durante o processo de aprendizagem para construção da árvore de decisão mais eficiente. E para o desfecho deste artigo, demonstrarei através de implementação em Python uma simples árvore de decisão.

"O seu sucesso depende de fazer escolhas de forma inteligente."

O que são Árvores de decisão ?

Amplamente utilizadas em algoritmos de classificação, as árvores de decisão são representações simples do conhecimento, e um meio eficiente de construir classificadores que predizem ou revelam classes ou informações úteis baseadas nos valores de atributos de um conjunto de dados. Eles são muito úteis em atividades de mineração de dados, isto é, o processo de extração de informações previamente desconhecida, a partir de grandes bases de dados. Aplicações desta técnica podem ser vista em diversas áreas, desde cenários de negócios até sistemas de piloto automático de aeronaves e diagnósticos médicos.

Uma árvore de decisão é essencialmente uma série de declarações if-elses, que quando aplicados a um registro de uma base de dados , resultam na classificação daquele registro. O mais interessante sobre o programa de árvores de decisão não é a sua construção a partir de classificação de um conjunto de treinamento, e sim a sua habilidade de aprendizado. Quando o treinamento é finalizado, é possível alimentar sua árvore de decisão construída a partir de exemplos com novos casos a fim de classífica-los.

É uma das estruturas de dados mais fácies de entender com uma boa representação gráfica. A figura 1 abaixo ilustra um exemplo de árvore de decisão.

Figura 1. Exemplo de árvore de decisão

Observe que a estrutura realmente é na forma de árvore. Dessa maneira, é possível utilizar técnicas recursivas para criar e percorrer a árvore de decisão. Você poderá utilizar quaisquer conceitos de representação de árvores aprendidos durante o seu curso de estrutura de dados para representar sua árvore. Neste artigo, para deixar as coisas bem simples, construirei a minha árvore de decisão apenas com objetos do tipo dicionário em Python.

Entendendo o problema...

Neste exemplo, são trabalhados objetos que relatam as condições propícias de uma ação de marketing baseado em uma análise demográfica do comportamento de clientes, onde se analisa se os mesmos compram ou não compra seus produtos. Para isto, é considerado um conjunto de exemplos para treinar a árvore de decisão. Considere que, os dados vieram de uma pesquisa por e-mail anônima e que existem alguns positivos (os que compram) e outros negativos (os que não compram). Depois de organizar toda essa massa de dados, chegamos a seguinte tabela:

A partir de uma árvore de decisão é possível derivar regras. As regras são escritas considerando o trajeto do nó raiz até uma folha da árvore. Estas regras determinam como as árvores classificam os registros de uma base de dados. Com basen a árvore de decisão apresentada na figura 1, pode-se exemplificar a derivação de regras. Dois exemplos de regras obtidas a partir desta árvore são mostradas a seguir: Iniciando do nó-pai (Age), verifica que o valor do atributo do primeiro exemplo casa com o valor 36-55, o qual desce para o próximo nó da árvore (Marital Status) e repete o processo até finalmente chegar a um nó-folha (um nó sem filhos). Este nós abriga a resposta para a questão de se o cliente irá ou não comprar o produto (Neste exemplo, o cliente irá comprar, porque seu estado civil ("marital status") é solteiro.

Se Age = 36-55 e Marital Status= single então Class= will buy .

É interessante também observar que este tipo de operação de derivação de regras é feita sobre um processo recursivo (não necessariamente a mais eficiente para o programa, mas é de forma elegante).

A árvore de decisão apresentada acima é uma de várias árvores que poderiam ser construídas para solucionar o problema acima apresentado. A tarefa de achar a melhor árvore de decisão é um problema NP-completo, isto é, que o tempo de processamento necessário para achar a "melhor" árvore de decisão pode ser exponencial a medida que o número de de dados usados no treinamento da rede. Embora, pareça ser impossível encontrar a menor árvore de decisão em um tempo considerável, é possível encontrar uma que seja "pequena suficiente", satisfatória a partir do uso de heurísticas especiais. A tarefa da heurística é realizar esta tarefa escolhendo o "melhor próximo" atributo que divida o conjunto de dados baseado em um critério pré-definido.

Há vários algoritmos de construção de árvore de decisão (C4.5,CART,CHAID, entre outros). Entretanto, para este artigo escolhemos o mais popular deles: a heurística ID3, para a escolha dos "melhores próximos" atributos baseados em conceitos encontrados em teoria da informação.

O algoritmo ID3 usa o conceito de entropia para calcular qual o melhor atributo será utilizado para dividir os dados em sub-grupos. Após a construção de uma árvores de decisão é importante avaliá-la. Esta avaliação é realizada através da utilização de dados que não tenham sido usados no treinamento. Esta estratégia permite estimar como a árvore generaliza os dados e se adapta a novas situações, podendo, também, se estimar a proporção de erros e acertos ocorridos na construção da árvore .

A próxima seção fala um pouco sobre como esta heurística funciona. E posteriormente, entraremos em detalhes em como criarmos a árvore de decisão e classificar clientes existentes em seu conjunto de dados em "will buy" ou "won't buy", tornando sua companhia mais lucrativa.

A heurística ID3

A física usa o termo entropia para descrever a quantidade de desordem associada a um sistema. Na teoria da informação, este termo tem uma significado semelhante, -- ele mede o grau de desordem de um conjunto de dados. A heurística ID3 usa este conceito para encontrar o próximo melhor atributo de um dado para ser utilizado como nó de uma árvore de decisão. Logo , a idéia por trás do algoritmo ID3 é achar um atributo que reduza em maior valor a entropia de um conjunto de dados, assim reduzindo a aleatoriedade - dificuldade de previsão - da variável que define classes. Seguindo esta heurística, você estará essencialmente encontrando o melhor atributo para classificar os registros (de acordo com a redução da quantia de informação necessária para descrever a partição dos dados que foram divididos ) a fim de que os mesmos tenham utilidade máxima (exemplos são da mesma classe).

O algoritmo ID3 segue os seguintes passos:

1. Começar com todos os exemplos do treinamento
2. Escolher o atributo que melhor divide os exemplos, ou seja agrupar os exemplos da mesma classe ou exemplos semelhantes
3. Para o atributo escolhido, criar um nó filho para cada valor possível do atributo
4. Transportar os exemplos para cada filho tendo em conta o valor do filho
5. Repetir o procedimento para cada filho não "puro". Um filho é puro quando cada atributo X tem o mesmo valor para todos os exemplos.

Na etapa 2 do algoritmo, para achar o melhor atributo é necessário encontrar a entropia para cada atributo possível naquele nó. Para isto usamos a fórmula da entropia:

Onde calculamos a proporção do número de exemplos positivos e o mesmo para o número de exemplos negativos para aquele atributo em questão multiplicado pelo logaritmo destas proporções. Um exemplo prático: Considere S uma coleção de 14 exemplos, incluindo 9 positivos ("will buy") e 5 negativos ("won't buy"). Logo a entropia para esta coleção S seria :

Notação: [+9,-5]

O próximo passo na heurística ID3 é calcular o ganho de informação para cada atributo que pode ser selecionado como nó na árvore. Essencialmente é apenas calcular a entropia de todo o conjunto de dados e diminuir este da entropia do sub-conjunto particionado para tal atributo. Este processo é feito para cada atributo do conjunto de dados, e o atributo com o maior ganhor de informação será o selecionado para o próximo nó da árvore.

O raciocínio por trás do ganho de informação é semelhante ao cálculo de entropia demonstrado acima. Agora considerando os sub-conjuntos particionados de acordo com o valor do atributo em questão. Considere o atributo "Vento" que pode ter os valores "Fraco" ou "Forte". Calcula-se então a entropia para cada um desses valores e depois a diferença entre a entropia do atributo vento e a soma das entropias de cada um dos valores associados ao atributo, multiplicado pela proporção de exemplos particionados de acordo com o valor (separados de um lado os exemplos com Vento = "Weak" e do outro lado Vento = "Strong").

Depois dessa breve explicação sobre a heurística ID3, vamos ao código-fonte.

Código-Fonte
O código-fonte a seguir ilustra a função principal do programa usada na construção da árvore de decisão:

##Returns the new decision tree based on the examples given
#@param data: Copy of the data list.
#@param attributes: List of all attributes 
#@param target_attr: The targer attribute that will be the evaluated
#@param fitness_func: The target function
def create_decision_tree(data,attributes,target_attr,fitness_func):
    
    data = data[:]
    vals = [record[target_attr] for record in data]
    default = majority_value(data, target_attr)
    
    #if the dataset is empty or the attributes list is empty, return the
    #the default value. When checking the attributes list for emptiness,
    #we need to subtract 1 to account for the target attribute.
    if not data or (len(attributes)-1) <= 0:
        return default
    #if all the records in the dataset have the same classification,
    #return the classification.
    elif vals.count(vals[0]) == len(vals):
        return vals[0]
    
    else:
        #Choose the next best attribute to best classify our data
        best = choose_attribute(data,attributes,target_attr,fitness_func)
        
        #Create a new decision tree/node with the best attribute.
        tree = {best:{}}
        
        #Create a new decision tree/sub-node for each of the values in the
        #best attribute field
        for val in get_values(data,best):
            #create a subtree for the current value under the "best" field
            subtree = create_decision_tree(get_examples(data,best,val),
                [attr for attr in attributes if attr != best],
                target_attr,
                fitness_func)
        
            # Add the new subtree to the empty dictionary object in our new
            # tree/node we just created.
            tree[best][val] = subtree
        
    return tree

A heurística ID3 usa o conceito de entropia para formular o ganho de informação na escolha de um atributo particular para ser o próximo nó na árvore de decisão. Aqui segue o código da função de entropia e do ganho de informação:

##Calculates the entropy of the given data set for the target attribute.
#@param data: the data list
#@param target_attr = the target attribute
def entropy(data,target_attr):
    val_freq = {}
    data_entropy = 0.0
    
    #Calculates the frequency of each of the values in the target attribute.
    for record in data:
        if val_freq.has_key(record[target_attr]):
            val_freq[record[target_attr]] += 1.0
        else:
            val_freq[record[target_attr]] = 1.0
    
    #Calculate the entropy of the data for the target attribute
    for freq in val_freq.values():
            data_entropy += (-freq/len(data)) * math.log(freq/len(data),2)
    

    return data_entropy

##Calculates the information gain (reduction in entropy) that
##would result by splitting the data on the chosen attribute (attr).
def gain(data, attr, target_attr):
    val_freq = {}
    subset_entropy = 0.0
    
    #Calculate the frequency of each of the value in the target attribute
    for record in data:
        if val_freq.has_key(record[attr]):
            val_freq[record[attr]] += 1.0
        else:
            val_freq[record[attr]] = 1.0
    
    #Calculate the sum of the entropy for each subset of records weighted
    #by their probability of ocurring in the training set.
    for val in val_freq.keys():
        val_prob = val_freq[val] / sum(val_freq.values())
        data_subset = [record for record in data if record[attr]==val]
        subset_entropy += val_prob * entropy(data_subset,target_attr)
 
    #subtract the entropy of the chosen attribute from the entropy of the
    #whole data set with respect to the target attribute (and return it)
    return (entropy(data,target_attr) - subset_entropy)

Mineração de dados com Árvores de decisão
Além de classificação de dados, árvores de decisão são úteis para inferir padrões a partir dos dados, também referenciado como mineração de dados. Apenas dando uma observada na árvore de decisão representada pela figura 1 no início deste artigo, você pode já inferir algumas tendências a partir do conjunto de dados. A mais óbvia tendência no dados é que jovens (idades entre 18 e 35) e idosos (> 55) não compram seus produtos. Isto poderia direcionar seu foco em outro público mais jovem (<>

O ponto mais importante é que olhando por cima o conjunto de dados, mesmo com apenas 20 registros, nenhum dessas tendências ou padrões são fáceis de encontrar a olho nu. Quando esse número aumenta para centenas, milhares ou até milhões de registros, achar essas tendências pode ser impossível. Usando árvores de decisão, você não apenas pode prever os gostos do seu cliente na hora de compra do seu produto, mas como também você pode apontar tendências importantes no seu conjunto de dados de teste a fim de auxiliar na melhora de práticas de marketing, e consequentemente atingir uma nova classe de clientes.

Conclusão

Os códigos acima apresentados são os componentes principais do programa. O resto das funções auxiliares para a construção da árvore de decisão podem ser encontradas no código-fonte disponível para download. Não tentei entrar muito em detalhes no código, pois acredito que o código é auto-explicatório, já que está bem comentado.
Quando executado o programa, uma árvore de decisão é construída e os dados são classificados de acordo com a árvore moldada.
Espero ter ajudado nesse pequeno tutorial sobre árvores de decisão, quaisquer dúvidas estou à disposição.

Até a próxima e boa programação!

Marcel Pinheiro Caraciolo

Referências

Arvores de Decisão - Prof. PHD Teresa Ludermir CIN/UFPE

Resolvendo o problema do caixeiro viajante com Algoritmos Genéticos

Olá Pessoal,

Como eu tinha citado no post anterior, sobre algoritmos genéticos, desenvolvi um pequeno simulador que soluciona o problema clássico NP-completo do caixeiro viajante (Traveling Salesman Problem - TSP) usando algoritmos genéticos (GA). Neste problema, o objetivo é encontrar a rota de menor distância entre N diferentes cidades. O caminho que o caixeiro faz é denominado de tour.

Se um caixeiro inicia do ponto A, e se as distâncias entre cada par de pontos é conhecida, qual é o menor caminho que visita todos os ponto e retorna ao ponto A ?

Para testar todas possibilidades de rotas para N cidades seria necessário calcular a permutação N!. Tudo bem, para um rota com 3 a 5 cidades, é fácil de calcular. Agora imagine um tour com 30 cidades! Seria necessário calcular a distância total de cada uma dessas 2.65 X 10³² diferentes rotas, assumindo um trilhão de cálculos por segundo, o que levaria aproximadamente 252,333,390,232,297 anos para achar a menor rota. Adicione mais uma cidade a esta rota e o tempo aumentaria em um fator exponencial elevado a 31. Fica claro, que é uma solução impossível calculando manualmente.

Algoritmos genéticos podem ser usados para solucionar este problema em menor tempo. Embora não haja garantias de encontrar a melhor solução, ela pode achar uma solução satisfatória bem próxima da ótima para um tour de 100 cidades em menos de 1 minuto. Há algums passos básicos para solucionar o problema do caixeiro viajante usando algoritmos genéticos, vejamos cada um deles a seguir:

• Primeiro, um conjunto aleatório de rotas são criadas, inicializando assim a população. Este algoritmo cria uma população inicial 'gulosa', o qual dá preferência em montar conexões entre as cidades que estão mais próximas uma da outra.

• Segundo, escolha as 2 melhores rotas (menores) da população para o cruzamento (crossover) e combine-os para gerar 2 novas rotas filhas. Grandes chances destas novas rotas filhas serem melhores que os seus pais.

• Em raros casos, as rotas filhas sofrem o processo de mutação. Isto é feito para prevenir que todas as rotas da população sejam idênticas

• As novas rotas filhas são inseridas na população substituindo no lugar de 2 rotas das maiores existentes. O tamanho da população se mantém constante.

• As novas rotas filhas são repetidamente criadas até atingirem um critério de parada desejado (melhor rota).

Os dois maiores problemas encontrados usando Algoritmos Genéticos para solucionar o problema do caixeiro viajante são a codificação/representação da rota e o algoritmo de cruzamento (crossover) utilizado para combinar dois indíviduos (rotas) para gerar novos filhos.

No algoritmo genético padrão, cada cromossomo é codificado através de uma sequência de números ou bits e o cruzamento (crossover) é realizado, selecionando um ponto de corte aleatório da sequência de genes dos cromossomos-pai e após a troca de cada número na sequência a partir do ponto selecionado. Neste exemplo, o ponto de corte está entre o 3^rde 4^th item da lista. Para criar um filho, todos os items da sequência de genes a partir do ponto de corte são trocados entre os cromossomos pais.

Parent1	F A B | E C G D
Parent2	D E A | C G B F
Child1	F A B | C G B F
Child1	D E A | E C G D

A maior dificuldade do problema do caixeiro viajante é que toda cidade só pode ser usada apenas uma vez dentro de uma rota (tour). Se considerarmos que as letras apresentadas no exemplo acima representam cidades, então as rotas filhas criadas pela operação de crossover seriam consideradas inválidas. Já que Child1 vai para cidades F e B duas vezes, e nunca passa pela cidades D ou E.

A codificação das rotas não pode ser simplesmente a lista de cidades na ordem em que elas são percorridas. Outros métodos de codificação também foram criados para solucionar o problema do crossover. Embora estes métodos não criem rota inválidas, eles não levam em conta de que a rota "A B C D E F G" é a mesma rota "G F E D C B A". Para solucionar o problema do crossover, precisamos de um algoritmo mais sofisticado.

Minha solução consiste de criar links em ambas direções para cada rota. No nosso exemplo anterior, Parent1 poderia ser armazenado como:

City	First Connection	Second Connection
A	F	B
B	A	E
C	E	G
D	G	F
E	B	C
F	D	A
G	C	D

A operação de crossover é mais complicada do que apenas simplesmente combinar 2 sequências. O cruzamento deve considerar todos os links existentes nas rotas pais e colocá-los nas rotas filhas. Logo, para o Child 1, são utilizados os links existentes no Parent 2 e depois no Parent 1. Para o Child 2, alterna-se entre Parent 2 e Parent 1 selecionando um diferente conjunto de links. Para ambos os filhos, há uma chane de o link criado torne a rota inválida, onde em vez de ter uma rota completa para todas as cidades, há vários trechos desconectados. Neste caso, tais links devem ser rejeitados. Para completar os links faltantes, cidades são selecionadas aleatoriamente.

Eventualmente, o algoritmo genético poderá criar soluções idênticas, o que não é o ideal. Todos indivíduos semelhantes em uma população acarreta na não convergência do algoritmo até achar a solução ótima. Para solucionar isso, usamos o processo de mutação, onde algumas rotas filhas são aleatoriamente modificadas a fim de produzir uma nova rota distinta.

Este algoritmo genético usa uma população inicial gulosa. Isto significa que o algoritmo genético não cria uma população individuos totalmente aleatória. Ele preferirá criar rotas com links entre cidades que sejam bem próximas uma das outras. Isto não é feito 100% do tempo, porque, claro, poderia acarretar na criação de uma população de rotas bastante similares.

Há 6 parâmetros para controlar a execução do Algoritmo Genético:

• Tamanho da população- O tamanho da população é o número de quantas rotas devem ser criadas aleatoriamente quando o algoritmo é iniciado. Uma imensa população faz com que o algoritmo demore mais para encontrar a solução. Em contrapartida, uma pequena população aumenta as chances de que todas as rotas criadas sejam eventualmente bem semelhantes. Consequentemente, isto aumenta as chances de que a melhor solução não seja encontrada.

• Seleção - A cada geração, um número N de rotas são selecionadas da população. As 2 melhores rotas são utilizadas para o cruzamento (crossover). As 2 piores rotas são substituídas pelos 2 novos filhos gerados. Um valor alto para N aumenta as chances de que rotas com alto valor de aptidão sejam escolhidas, porém pode provocar a redução de chances de outras rotas não tão boas serem escolhidas.

• Mutação% - A taxa de mutação informa as chances de cada filho após o crossover sofram o processo de mutação. Quando uma rota é modificada, uma das cidades é aleatoriamente movida de um ponto para outro ponto dentro da rota.

• Número máximo de gerações - Quantas gerações devem ser criadas até que a execução do algoritmo finalize. Utilizada como críterio de parada para este problema.

• Lista de cidades - Neste programa temos a opção de importar nomes de cidades já previamente construídas ou gerá-las em tempo de execução. Em futuras versões, poderemos fazer com que sejam importadas as cidades e suas localizações a partir de um arquivo XML.

Os parâmetros iniciais do algoritmo são:

Parâmetro	Valor inicial
Tam. Pop.	10,000
Seleção N	5
Mutação	3 %

Para execução, é necessário ter instalado o ambiente de execução Python (> 2.5) e o pluggin para construção de interfaces gráficas PyFltk (versão de acordo com o Python instalado na sua máquina).

Clique aqui para fazer o download do TSP GA Simulator.

Para executar, após extrair todo o conteúdo em uma pasta, basta abrir o arquivo Tsp.py pelo IDLE (ambiente de edição de arquivos) do Python e clicar em Run -> RunModule.

Vale salientar que esse simulador não é a versão final e nem tão sofisticada. Quaisquer sugestões ou melhorias são válidas para tornar este simulador mais interessante. Algumas melhorias devem ser realizadas no processo de crossover. Mandem comentários!

Referências:

Problema do caixeiro viajante - Wikipedia
Algoritmos Genéticos - UFRJ


Até a próxima!

Marcel Pinheiro Caraciolo

Computação Evolucionária: Algoritmos Genéticos

Olá pessoal,

Neste post vamos sair um pouco do foco no tema de redes neurais, e entrarmos em outra área muito estudada e cobiçada no ramo de inteligência artificial: Computação evolutiva ou evolucionária. Mas do que se trata esse campo ?

Computação Evolutiva de fato!

Computação evolucionária

A computação evolucionária (CE) é um ramo da ciência da computação que propõe um paradigma alternativo ao processamento de dados convencional. Este novo paradigma tenta resolver problemas a partir de mecanismos evolutivos encontrados na natureza, tais como a auto-organização e o comportamento adaptativo. Esses conceitos foram introduzidos e formalizados por Charles Darwin na sua teoria da evolução natural, segundo a qual, a vida na terra é resultado de um processo de seleção, pelo meioa ambiente, do mais aptos e adaptados, e por isto mesmo com mais chances de reproduzir-se. A diversidade da vida, associada ao fato de que todos os seres vivos compartilham uma bagagem genética comum, pelo menos em termos de seus componentes básicos, é um exemplo eloqüente das possibilidades do mecanismo de evolução natural.

Um dos clássicos modelos computacionais inspirados neste paradigma (CE) são os algoritmos genéticos, o tema a ser discutido nesse post. Mas antes de entrarmos a fundo neste poderoso modelo computacional, vamos entender um pouco a sua aplicação.

Aplicações

Problemas compostos de múltiplas variáveis e diversas soluções estão presentes em uma grande variedade de problemas de otimização. Esses problemas são caracterizados por circunstâncias em que se desejam maximizar ou minimizar uma função numérica de várias variáveis, em um contexto que podem existir restrição. Apesar da existência de diversas técnicas clássicas de otimização para a solução desses tipos de problema, a sua falta de robustez e alta complexidade em problemas de alta dimensionalidade impulsionaram a busca por novas alternativas.
A sofisticação dos recursos computacionais desenvolvidos nos últimos anos tem motivado um grande avanço nas técnicas de otimização. Com isso, uma forte tendência tem acompanhado esse avanço através de estudos de métodos heurísticos que permitem encontrar soluções ótimas em diferentes espaços de busca, inclusive vários com máximos e mínimos locais. Dentre essas heurísticas, os algoritmos evolucionários têm tido grande sucesso em solucionar problemas de otimização de múltiplas soluções. Um desses algoritmos é o algoritmo genético, visto como otimizador de funções, embora a quantidade de problemas para qual os AG's se aplicam seja bastante abrangente. Então podemos resumir que os algoritmos genéticos são eficientes otimizadores de problemas de múltiplas soluções. Vamos citar alguns exemplos:

-- Problemas de otimização complexos: problemas com muitas variáveis e espaços de soluções de dimensões elevadas. Ex: problema do caixeiro viajante, gerenciamento de carteiras de fundos de investimento.

-- Otimização de funções matemáticas.

--Gerenciamento de redes: supervisão do tráfego nos links e das filas nos "buffers" de roteadores para descobrir rotas ótimas e para reconfigurar as rotas existentes no caso de falha de algum link .

-- Roteamento de veículos, otimização de solução de jogos como quebra-cabeças, cubo mágicos, etc.

Como podemos ver a gama de problemas solucionáveis por algoritmos genéticos é muito abrangente. Neste post de teor introdutório, iremos descrever o algoritmo genético através de uma implementação simples na linguagem de programação Python a fim de encontrar o máximo/mínimo de uma função númerica contínua (Otimização de funções numéricas).

O problema consiste em achar o máximo da função:

f(x) = x * sen(10*pi*x) + 1.0 ,
restrita ao intervalo x em [-1.0,2.0]

Gráfico da função f(x) = x * sen(10*pi*x) + 1.0

Podemos observar que a função a ser otimizada é uma função multimodal com vários pontos de máximo e que para encontrarmos manualmente o máximo global é muito dispendioso em tempo e esforço. Como podemos solucionar essa busca ? Algoritmos genéticos!

Afinal ,o que são algoritmos genéticos ?

Os algoritmos genéticos são uma família de modelos computacionais inspirados na evolução, que incorporam uma solução potencial para um problema específico numa estrutura semelhante a de um cromossomo e aplicam operadores de seleção e "cross-over" a essas estruturas de forma a preservar informações críticas relativas à solução do problema.

Uma de suas vantagens é a simplificação que permite na formulação e solução de problemas otimização. Algoritmos genéticos normalmente com descrições de entradas formadas por cadeias de bits de tamanho fixo. Eles possuem um paralelismo implícito decorrente da avaliação independente de cada uma dessas cadeias de bits, ou seja, pode-se avaliar paralelamente a viabilidade de um conjunto de parâmetros para a solução do problema de otimização em questão.

Existem três tipos de representação possíveis para os cromossomos: binária, inteira ou real. A essa representação se dá o nome de alfabeto do Algoritmo Genético. De acordo com a classe de problema que se deseje resolver pode-se usar qualquer um dos três tipos.

Uma implementação de um algoritmo genético começa com uma população aleatória de cromossomos. Essas estruturas são, então, avaliadas e associadas a uma probabilidade de reprodução de tal forma que as maiores probabilidades são associadas aos cromossomos que representam uma melhor solução para o problema de otimização do que àqueles que representam uma solução pior. A aptidão da solução é tipicamente definida com relação à população corrente.

A função objetivo de um problema de otimização é construída a partir dos parâmetros envolvidos no problema. Ela fornece uma medida da proximidade da solução em relação a um conjunto de parâmteros. Os parâmetros podem ser conflitantes, ou seja, quando um aumenta o outro diminui. O objetivo é encontrar o ponto ótimo. A função objetivo permite o cálculo da aptidão bruta de cada indivíduo, que fornecerá o valor a ser usado para o cálculo de sua probabilidade de ser selecionado para reprodução.

Depois dessa explicação formal, é chegada a hora de botar a mão na massa. Vamos primeiramente resumir os principais conceitos apresentados acima e o que eles representam no mundo real. Vejam a tabela abaixo:

Tabela: Algoritmos Genéticos x Mundo Real

A idéia por trás do algoritmo genético consiste em gerar, através de regras específicas, um grande número de cromossomos (indivíduos), população, de forma a provmover uma varredura tão extensã quanto necessária do espaço de soluções. Vale salientar que cada cromossomo corresponde a um ponto no espaço de soluções do problema de otimização.

Como o código-fonte é extenso, explicarei por seções o algoritmo do algoritmo genético.

O Algoritmo dos algoritmos genéticos

A estrutura básica do algoritmo genético é mostrado na figura abaixo:

Fluxograma do Algoritmo Genético

Com referência ao fluxograma da figura acima, observa-se que cada iteração do algoritmo genético corresponde à aplicação de um conjunto de quatro operações básicas: cálculo de aptidão (fitness evaluation), seleção (selection), cruzamento (crossover) e mutação (mutation). Ao fim destas operações cria-se uma nova população, chamada de geração (generation) que, espera-se, representa uma melhor aproximação da solução (best solution) do problema de otimização que a população anterior. A população inicial é gerada atribuindo-se aleatoriamente valores aos genes (pense um gene como um repositório que armazena algo) de cada cromossomo. A aptidão bruta de um indivíduo da população é medida por uma função de erro, também chamada de função objetivo (fitness function) do problema de otimização.

A aptidão bruta é em seguida normalizada (aptidão normalizada), para permitir um melhor controle do processo de seleção. Como critérios de parada do algoritmo em geral são usados a aptidão do melhor indivíduo em conjunto com a limitação do número de gerações. Outros critérios podem envolver, por exemplo, um erro abaixo de um valor especificado pelo projetista para um determinado parâmetro do problema.

Vamos aos passos do algoritmo:

Inicialização (Generation of population)

Uma população de P individuos é gerada aleatoriamente. Cada um dos indivíduos da população representa uma possível solução para o problema, ou seja, um ponto no espaço de soluções.

"""
Represents a possible solution for the problem
"""
import random
import math

MAXIMIZE,MINIMIZE = (0,1)

STR_DELIMITER = ''

class Individual(object):

#The length of the chromosome
length = 22
#Values that the gene can be
alleles = (0,1)
#Function range
range = (-1.0,2.0)
#Optimization's type
optimization = MAXIMIZE

#Creates a simple individual
#@param chromosome: Data Structure that codificates the solution of the problem.
def __init__(self,chromosome=None):
  #The Fitness score
  self.score = None
  #Collection of genes.
  self.chromosome = chromosome or self._makeChromosome()

#Creates a new chromosome made up of genes limited by its length.
def _makeChromosome(self):
 return [random.choice(self.alleles) for gene in xrange(self.length)]

#Evaluates the fitness score
#@param optimum: Optimization method
def evaluate(self,optimum=None):
  #Decodification of the chromosome
  coff = float(int(STR_DELIMITER.join(map(str,self.chromosome)),2)) / float(pow(2,self.length) - 1)
  x = self.range[0] + (self.range[1] - self.range[0]) * coff
  #Evaluation of the function
  y =  x * math.sin(10.0 * math.pi * x) + 1.0
  #Calculates the fitness score
  self.score = y

#combination of the parents to produce a new child
def crossover(self,mate):
  #Two-point crossover
  return self._twopoint(mate)

#Create a new individual replacing a gene allele with a random one.
#@param gene: The gene of chromosome
def mutate(self,gene):
  self._pick(gene)

##Invert the gene's allele to create a new individual.
#param gene: The gene that will be replaced.
def _pick(self,gene):
  self.chromosome[gene] = int(not self.chromosome[gene])

#Creates offspring via two-point crossover between mates."
#param mate: the other mate
def _twopoint(self,other):
  left,right = self._pickPivots()
  def mate(p0,p1):
      #Creates a new copy of p0.
      chromosome = p0.chromosome[:]
      #Two-point crossover
      chromosome[left:right] = p1.chromosome[left:right]
      child = p0.__class__(chromosome)
      child.repair(p0,p1)
      return child
  return mate(self,other), mate(other,self)

#Helper function to get the cutting point.
def _pickPivots(self):
  left = random.randrange(1,self.length-2)
  right = random.randrange(left,self.length-1)
  return left,right

#Crossover helper, if necessary, to fix duplicated genes
#@param parent1 : The mate 01
#@param parent2 : The mate 02
def repair(self,p0,p1):
  pass

#Returns string representation of itself
def __repr__(self):
  return '<%s chromosome="%s" score=%s>' % \
      (self.__class__.__name__,
       STR_DELIMITER.join(map(str,self.chromosome)),self.score)

#The comparison method with other individual
#@param other: The other individual that will be compared.
def __cmp__(self,other):
  if self.optimization == MINIMIZE:
          return cmp(self.score,other.score)
  else:
      #MAXIMIZE
      return cmp(other.score,self.score)

#Creates a replicate of itself.
def copy(self):
  clone = self.__class__(self.chromosome[:])
  clone.score = self.score
  return clone


"""
Enviroment necessary to run the Genetic Algorithm.
"""
class Environment(object):
#Initialize the enviroment parameters necessary to run the algorithm.
#@param population : The initial population of individuals.
#@param size: Size of the population.
#@param maxgenerations: The maximum generations.
#@param crossover_rate: Crossover rate.
#@param mutation_rate: Mutation rate.
#@param optimum :  Optimization type.
def __init__(self,population=None,size=100,maxgenerations=100,
           crossover_rate=0.90,mutation_rate=0.01,optimum=None):
  #Size of the population
  self.size = size
  #Optimization method
  self.optimum = optimum
  #Initialize the population
  self.population = population or self._makePopulation()
  #Start the evaluation of the population
  for individual in self.population:
      individual.evaluate(self.optimum)
  #Crossover rate
  self.crossover_rate = crossover_rate
  #Mutation rate
  self.mutation_rate = mutation_rate
  #Max number of generations
  self.maxGenerations = maxgenerations
  #Initialize the generation
  self.generation = 0
  #Report the algorithm running status
  self.report()

#Initialize the population (Generate the individuals)
def _makePopulation(self):
  return [Individual() for individual in xrange(self.size)]

(...)

Calculo da aptidão (Evaluation of fitness)

Geralmente a aptidão do indivíduo é determinada através do cálculo da função objetivo, que depende das especificações de projeto. Neste projeto, cada indivíduo é uma entrada para uma função de análise de desempenho (evaluate), cuja saída fornece medidas que permitem ao algoritmo genético o cálculo da aptidão do indivíduo. Ainda nesta fase os indivíduos são ordenados conforme a sua aptidão.

#Evaluates the fitness score
#@param optimum: Optimization method
def evaluate(self,optimum=None):

   #Decodification of the chromosome
   coff = float(int(STR_DELIMITER.join(map(str,self.chromosome)),2)) / float(pow(2,self.length) - 1)
   x = self.range[0] + (self.range[1] - self.range[0]) * coff
   #Evaluation of the function
   y =  x * math.sin(10.0 * math.pi * x) + 1.0
   #Calculates the fitness score
   self.score = y

Seleção (Selection)

Nesta fase os indivíduos mais aptos da geração atual são selecionados. Esses indivíduos são utilizados para gerar uma nova população por cruzamento. São selecionados os n melhores indivíduos daquela geração e depois faz uma espécie de torneio. Neste método, denominado "amostragem universal estocática", cada indivíduo tem uma probabilidade de ser selecionado proporcional à sua aptidão. Para visualizar este método considere um círculo dividido em n regiões (tamanho da população), onde a área de cada região é proporcional à aptidão do indivíduo.Coloca-se sobre este círculo uma "roleta" com n cursores, igualmente espaçados. Após um giro da roleta a posição dos cursores indica os indivíduos selecionados. Isto significa que quanto melhores são os cromossomos, mais chances de serem selecionados. O lado de cada secção da roleta é proporcional ao valor de adequação (aptidão) de cada cromossomo: quanto maio valor, mais larga a secção. Veja a imagem a seguir para um exemplo:

Método de seleção de cromossomos por Roleta

Evidentemente, tais condições são mensuradas por valores, que quando elevados, o melhor indivíduo da população terá maior probabilidade de ser selecionado várias vezes. Como consequência, a seleção de indivíduos pode conter várias cópias de um mesmo indivíduo enquanto outros podem desaparecer.

class Environment(object):
 (...)

  #The step-by-step running algorithm
  def run(self):
      while not self._goal():
          self.step()

  #The conditions to stop the algorithm.
  def _goal(self):
      return (self.generation > self.maxGenerations) or (self.best.score == self.optimum)

  #The step done by the genetic algorithm
  def step(self):
      #Sort the individuals of the population based on their score
      self.population.sort()
      #Make the crossover
      self._crossover()
      #Increments the generation
      self.generation+=1
      #Report the current status
      self.report()

  (...)
    
  #Selection method of the individuals for crossover
  def _select(self):
      return self._tournament()

  (...)

  #sample selection method
  def _tournament(self):
      competitors = []
      total_score = sum([math.ceil(self.population[i].score) for i in xrange(self.size)])
      for index in xrange(self.size):
          temp = [index] * int((math.ceil(self.population[index].score /total_score) * 100))
          competitors.extend(temp)
        
      return self.population[random.choice(competitors)]

  (...)

Cruzamento (Crossover)

Os indivíduos selecionados na etapa anterior são cruzados. A forma como se realiza este cruzamento é ilustrada na figura abaixo. Os cromossomos de cada par de indivíduos a serem cruzados são particionados em um ponto, chamado ponto de corte, sorteado aleatoriamente. Um novo cromossomo é gerado permutando-se a metade inicial de um cromossomo coma metade final do outro. Deve-se notar que se o cromossomo for representado por uma cadeia de bits, como na figura figura 3, o ponto de corte pode incidir em qualquer posição (bit) no interior de um gene, não importando os limites do gene. No caso de genes representados por números reais, a menor unidade do cromossomo que pode ser permutada é o gene.

Exemplo de crossover com genes (bits)

class Environment(object):
   (...)
    
    #Crossover proccess
    def _crossover(self):
        #Elistism proccess (best individual is copied to the next generation)
        next_population = [self.best.copy()]
        while len(next_population) < self.size:
            mate1 = self._select()
            if random.random() < self.crossover_rate:
                mate2 = self._select()
                offspring = mate1.crossover(mate2)
            else:
                #make a copy of individual
                offspring = [mate1.copy()]
            for individual in offspring:
                self._mutate(individual)
                individual.evaluate(self.optimum)
                next_population.append(individual)
        self.population = next_population[:self.size]
    
 (...)  

Mutação (Mutation)

A operação de mutação é utilizada para garantir uma maior varredura do espaço de estados e evitar que o algoritmo genético convirja muito cedo para mínimos locais. A mutação é efetuada alterando-se o valor de um gene de um indivíduo sorteado aleatoriamente com uma determinada probabilidade, denominada probabilidade de mutação, ou seja, vários indivíduos da nova população podem ter um de seus genes alterado aleatoriamente.

class Environment(object):
   (...)
   
    #Mutation method.
    #@param individual: Individual to be mutated.
    def _mutate(self,individual):
        for gene in xrange(individual.length):
            if random.random() < self.mutation_rate:
                individual.mutate(gene)
    
    #Get the individual with best fitness score in population.
    def best():
        def fget(self):
            return self.population[0]
        return locals()
    best = property(**best())
    
    #Shows the results report
    def report(self):
        print "="*70
        print "generation: " , self.generation
        print "best:       " , self.best

Para executarmos o código demonstrado acima, instanciamos a classe Enviroment passando como parâmetros o tamanho da população, número máximo de gerações, o ótimo global (pode er usado também como condição de parada) e as taxas de crossover e mutação respectivamente,de acordo com o tipo de problema em questão. Neste pequeno exemplo, tentamos solucionar um problema de maximização, onde a solução ótima se encontra no valor x = 1,85055 f(x) = 2,85027.

#########################################################################
"""
   Main loop
"""
if __name__ == "__main__":
   env = Environment(maxgenerations=50, optimum=2.85026911722)
   env.run()

Executando o código acima, temos o seguinte resultado no console. (A partir da geração 26 já se tem o valor máximo da função a ser buscada):

generation:  25
best:        Individual chromosome="1111001100101010101110" score=2.84947534214
======================================================================
generation:  26
best:        Individual chromosome="1111001100101111011110" score=2.84980345657
======================================================================
generation:  27
best:        Individual chromosome="1111001100111111011110" score=2.85027356577
======================================================================
generation:  28
best:        Individual chromosome="1111001100111111011110" score=2.85027356577
======================================================================
generation:  29
best:        Individual chromosome="1111001100111111011110" score=2.85027356577
======================================================================
generation:  30
best:        Individual chromosome="1111001100111111011110" score=2.85027356577
======================================================================
generation:  31
best:        Individual chromosome="1111001100111111011100" score=2.85027360267

Como se pode observar, algoritmos genéticos prova-se ser bastante eficiente na solução de problemas de otimização, garantido convergir à solução ótima. É claro, que há casos de problemas mais complexos, com diversas regiões de mínimos locais, que exigem do projetista uma análise mais refinada na forma de como o cromossomo é codificado, (representação da solução no algoritmo genético) e além de vários parâmetros do algoritmo que podem ser escolhidos para melhorar o seu desempenho, adaptando-o às características particulares de determinadas classes de problemas. Entre eles os mais importantes são: o tamanho da população, o número de gerações, a probabilidade de cross-over e a probabilidade de mutação.

A influência de cada parâmetro no desempenho do algoritmo depende da classe de problemas que se está tratando. Assim, a determinação de um conjunto de valores otimizado para estes parâmetros dependerá da realização de um grande número de experimentos e testes. Na maioria da literatura os valores encontrados estão na faixa de 60 a 65% para a probabilidade de cross-over e entre 0,1 e 5% para a probabilidade de mutação. O tamanho da população e o número de gerações dependem da complexidade do problema de otimização e devem ser determinados experimentalmente. No entanto, deve ser observado que o tamanho da população e o número de gerações definem diretamente o tamanho do espaço de busca a ser coberto. Existem estudos que utilizam um AG como método de otimização para a escolha dos parâmetros de outro AG, devido à importância da escolha correta destes parâmetros.


É isso pessoal, recomendo a leitura deste artigo do autor Márcio Nunes de Miranda (UFRJ) utilizado como referência principal para a construção deste tutorial. O download do código acima está disponível neste link. Espero que tenha sido útil!

No próximo post, irei trazer um problema mais "realista" de otimização para ser solucionado pela técnica evolucionária dos algoritmos genéticos.

Até a próxima!

Marcel P. Caraciolo