Otimização por colônia de formigas
Ant Colony Optimization – ACO Algoritmo de classificação
Gissely de Souza
Universidade Federal do Paraná
Disc. Aprendizagem de Máquina
Prof. David Menotti
Otimização por colônia de formigas
•
•
•
•
•
•
•
•
Aplicação
TSP - Caixeiro Viajante
Escalonamento
Classificação Estrutural de Proteínas
VRP - Problema de roteamento de veículos
Rede de Telecomunicações
Graficos de Coloração
Rede de Distribuição de Água
Otimização por colônia de formigas
• Um dos principais algoritmos inspirado no
comportamento social é a otimização por colônia de
formigas (do inglês Ant Colony Optimization – ACO)
que tem como fonte de inspiração biológica, ou
natural, o comportamento social das formigas na
tarefa na busca por alimentos:
Um algoritmo simples de otimização por colônia de formigas, a
busca de alimentos é feita inicialmente por caminhos aleatórios
em um espaço.
Formigueiro
Comida
O algoritmo das formigas foi inspirado na observação colônias de
formigas reais.
Formigueiro
Comida
Formiga encontrou a comida e
vai voltar para o formigueiro
Otimização por colônia de formigas
• Quando encontram o alimento, as formigas, voltam
para o ninho e depositam no solo uma substância
química chamada feromônio, em uma quantidade
proporcional a quantidade de alimento formando
uma trilha.
• Quando outra formiga percebe o feromônio é atraída
para a trilha e realiza todo o percurso também
liberando feromônio.
No momento que a formiga encontra o alimento ela volta para
o ninho depositando uma quantidade de feromônios
proporcional a quantidade de alimento.
Formigueiro
Comida
Formiga voltando
Assim outras formigas se juntam a ela para ajudar na coleta de
alimento.
Achou a comida e vai
voltar para o formigueiro
Formigueiro
Comida
Achou a comida e vai
voltar para o formigueiro
Caminho mais curto por colónias de formigas
(biológicas)
Formigueiro
Comida
Caminho mais curto por colónias de formigas
(biológicas)
Tem maior probabilidade de ir
por baixo (trilha onde
passaram mais formigas - mais
feromônio)
Formigueiro
Comida
Esse feromônio evapora constantemente mais cada vez que a
formiga volta ao ninho com o alimento, a trilha é reforçada e ao
mesmo tempo ocorre a otimização natural da trilha de
feromônio.
Formigueiro
Comida
Quando todas as formigas começam a seguir o
mesmo percurso. Isto ocorre devido ao excessivo
crescimento de depósito de feromônio no
caminho por onde elas passam.
A formiga que encontrou o circuito com menor
custo fará que todas as outras comecem a utilizar
o mesmo.
Assim de modo probabilístico, as formigas
preferem o caminho mais proximo.
Comportamento das formigas após o surgimento de um
obstáculo entre o ninho e a fonte de alimento.
Técnica probabilística para solução de
problemas computacionais, proposta por Dorigo
(1992), que podem ser reduzidos em “encontrar
bons caminhos ao longo de um grafo”;
Probabilidade de Transição
 A probabilidade da formiga k que está em i de escolher a
um ponto j é dada pela regra
onde:
pijk 
 ij ij 


il
 jl

, quando j  N ik
lN kj
 Temos ij é valor o feromônio associado à aresta (i, j)
 Njk O valor da distância da vizinhança da formiga K
  e  são parâmetros para determinar a influência do
feromônio, dividido pelo termo que normaliza o produto do
feromônio pelo termo heurístico entre 0 e 1 considerando
todas as arestas incidentes no nó em que a formiga se
encontra.
Algoritmo AS (Ant System)
• ACO (Ant Colony Optimization) executa iterativamente
um loop contendo dois procedimentos básicos, que
são:
• Um procedimento especificando como as formigas
constroem ou modificam as soluções do problema a
ser resolvido; e
• Um procedimento para a atualização das trilhas de
feromônio.
Algoritmo AS (Ant System)
Enquanto (criterio de parada)
Para cada formiga k
Percorrer_caminho()
fim_para
só depois de todas a formigas
terem feito seus caminhos
Atualizar_feromonio()
Decorar_melhor_solucao_atual()
Fim_enquanto
Classificação usando ACO
• Introduzido por Parpinelli et al. (2002), o Ant-Miner é
embasado na meta-heurística de Otimização por
Colônia de Formigas Artificiais (ACO – Ant Colony
Optimization).
• Porém, ao invés de ser aplicado a problemas de
otimização combinatória, o Ant-Miner é um algoritmo
de mineração de dados que tem o objetivo de
descobrir regras e padrões (regras de classificação) a
partir de um conjunto de dados.
Ant-Miner(Ant Colony-based Data Miner)
• Tarefa de classificação pega conjunto de exemplos de
treinamento descobre uma relação entre os atributos
previsores e o meta, de forma que, dado um novo
exemplo, ele possa predizer a classe.
• As regras descobertas são do tipo SE <termo1 E termo2
E ...> ENTÃO <classe>.
• Cada termo é composto por uma tupla
• <atributo, operador, valor> por exemplo,
• <gênero=feminino>
AntMiner algoritmo para a descoberta de regras
de classificação
•
•
•
•
Algoritmo consiste em várias etapas:
Construção regra;
Regra poda;
Atualização de feromônio;
• Formigas incrementalmente constrói/modifica uma
solução para determinado problema alvo, neste caso,
o problema alvo é a descoberta das regras de
classificação.
Construção da Regra
• Uma Formiga começa com regra vazia e
adiciona um termo de cada vez
• A melhor regra (melhor formiga) é selecionada
e adicionada a ListaDeRegras
Regra de poda
• Esta poda auxilia a remoção de termos
irrelevantes que podem ter sido adicionados
desnecessariamente na regra.
Atualização do feromônio
• Aumenta o feromônio na trilha seguida pela
formiga atual de acordo com a qualidade da
regra encontrada.
• Diminui feromônio em outras trilhas que
simula a evaporação do feromônio.
Critérios de paranda
• Num. de regras> = Num. de formigas
• Convergência é cumprida
Lista de regras descobertas é atualizada e
feromônios redefinido para todas as trilhas
Artigo de referência:
Bo Liu , Hussein A. Abbass , and Bob McKay “ Classification Rule Discovery with Ant
Colony Optimization “IEEE Computational Intelligence Bulletin February 2004.