Uma heurística para guiar os usuários da
Internet baseada no comportamento da formiga
Wesley Martins Teles, Li Weigang, Célia Ghedini Ralha
Universidade de Brasília
Índice
•
•
•
•
Introdução.
Pesquisas sobre o uso da Web.
A meta heurística da formiga.
Como encaixar a meta-heurística da formiga
na navegação na Web.
• AntWeb adaptativo.
• Conclusão e Recomendação
I. Introdução
A formiga
Os usuários na Internet
um inseto social que
trabalha em prol da colônia
não lhe permitem ter uma
visão global do seu
ambiente, cegas.
quando caminha deixa uma
substância chamada
feromônio no chão.
num imenso ciberespaço
sem saber onde estão e por
vezes nem por onde iniciar
seu processo de busca.
o feromônio das trilhas em
desuso evapora, ficando
apenas as trilhas que são
mais interessantes
achar com eficiência a fonte
de alimento e determinar o
menor caminho
não possuem nenhum tipo
de comunicação grupal
durante o processo de
navegação.
???
se encontra em uma
gigantesca teia de páginas
interligadas por links
Objetivo
É o estudo da aplicação do comportamento da
formiga na Web. Usando a idéia do
feromônio, os usuários não só poderão
encontrar as páginas que procuram com
maior facilidade, como também descobrir
o menor caminho entre o ponto em que se
encontram e o objetivo, tornando o
processo de navegação na Internet mais
fácil.
Dois aspectos de AntWeb
Para avaliação de estruturas de WebSites
–
L. Weigang, M. Dib, W. Teles, V. de Andrade, A. Alves de
Melo, J. Cariolano, "Using ants’ behavior based simulation
model AntWeb to improve website organization", in Proc.
SPIE's Aerospace/Defense Sensing and Controls Symposium:
Data Mining, USA, 2002.
Adaptativo
–
W. Teles, L. Weigang, C. Ralha, AntWeb – The Adaptive
Web Server Based on the Ants’ Behavior, WI (International
Conference on Web Intelligence), IEEE/WIC, Halifax,
Canada, 2003.
O que é o AntWeb adaptativo
• Envolve o desenvolvimento de uma
heurística para guiar o usuário da internet
baseada no comportamento da formiga.
• Desenvolvida a partir da meta-heurística da
formiga.
• Modifica estrutura da pagina de Web na site
adaptativo
II. Pesquisas sobre o uso da Internet
Pesquisas sobre o uso da internet
60% do tempo em que as pessoas permanecem
conectadas a um site é gasto sem que elas
encontrem a informação que procuram.
Número alto de páginas consultadas por seção.
A grande maioria dos usuários não encontram sua
página depois de 4 clicks.
Estado de arte
M. Dorigo, V. Maniezzo and A. Colorni, “The Ant System:
Optimization by a Colony of Cooperating Agents”, IEEE
Transactions on Systems, Man, and Cybernetics-Part B, 1996.
P. Brusilovski, Methods e Techniques of Adaptive Hypermedia. User
Modeling and User Adapted Interaction. n.2-3, Special issue on
adaptive hypertext and hypermedia, 1996.
R. Srikant e Y. Yang, Mining Web Logs to Improve Website
Organization, In Proc. of the Tenth International World Wide Web
Conference, Hong Kong, (2001).
Joachims, D. Freitag, T. Mitchell, "WebWatcher: A Tour Guide
for the World Wide Web" , Proceedings of IJCAI97, August
1997.
A meta-heurística da formiga
A meta heurística da formiga
•Baseada no comportamento da formiga real.
A formiga real pode encontrar o caminho mais curto
entre o formigueiro e a fonte de alimento sem o
auxílio da visão.
•Indica os caminhos mais curtos.
•Comunicação através do feromônio.
•Desenvolvida por Marco Dorigo e colegas.
Ciclo auto-catalítico
Caminhos
mais curtos
Tempo menor
para percorrer
o caminho
Maior freqüência de
formigas
Aumento da quantidade
de feromônio no caminho
Como a heurística se aplica na
computação
G. Di Caro e M. Dorigo. AntNet: A mobile agents
approach to adaptive routing. Technical Report
97-12, IRIDIA, 1997.
M. Dorigo e L. M. Gambardella. Ant Colonies for the
Traveling Salesman Problem, BioSystems, Also
Tecnical Report TR/IRIDIA/1996-3, IRIDIA, 1997.
B. Bullnheimer, et. al. Applying the ant system to
the vehicle routing problem, Kluwer Academics,
1998.
Como encaixar a meta-heurística da
formiga na navegação na
Web
Internet X Meta-heurística da formiga
Estados discretos = páginas
Transições = links
Formigas = Usuários
• Informações do log.
• Banco de dados.
• Técnicas de hipermídia adaptativa.
Indicação direta, Anotação, Classificação,
Ocultação.
AntWeb adaptativo
Modelo 1
• Funciona exatamente como a estratégia da
formiga real.
• A quantidade de feromônio adicionada é
constante (cada formiga deixa a quantidade 1
de feromônio nas páginas por onde passa).
• A evaporação ocorre com o decorrer do
tempo.
Atualização do feromônio
i (p)  (1-)*i (p) + *i (p)
0 <  < 1 é o coeficiente de evaporação
i (p)
é a quantidade de formigas que
passaram pela página i
Implementação
Implementação
Implementação
1-requisição da
página ao
AntWeb
Usuário
6-página
modificada
2-requisição da
página
Servidor web
AntWeb
5-log
3-página
4-feromonio dos
links
Servidor Banco
de Dados
Servidor web
CIC UnB
Destaque dos links
• Só destaca os links que estão acima de um
determinado limite (threshold).
• Destaca no máximo três links (número
máximo de links a destacar).
Modelo 2
• O feromônio é adicionado quando a formiga
termina seu trajeto.
Metáfora do modelo 2
• As páginas conteúdos são objetos que
exalam cheiro.
• Os links nas páginas índice são túneis por
onde o cheiro da página objetivo escapa.
• Os usuários seguem os túneis que o cheiro
exala mais forte.
Goodness
• Cada página destino d possui um coeficiente
gd (goodness) que diz o quanto a página d é
boa para o usuário.
• gd pode ser popularidade ou outro índice que
diz o quanto a página é boa.
• Em termos prático é a intensidade do cheiro
que a página deve exalar.
Modelo 2
• A atualização do feromônio serve apenas
para aprendizagem da estrutura da Web.
• A quantidade de feromônio a ser acrescida
muda conforme a distância da página ao
destino na trajetória.
• A evaporação ocorre a cada acréscimo feito.
Representação do feromônio

d
p
• Para cada página existem várias taxas de
feromônio associadas (uma para cada
destino possível)
Onde p é página e d o destino.
Acréscimo de feromônio
1

d,k
 p
se
i

T
 d ,k
d ,k
 i  p    nli  p     1

0
se i  T d,k  p 
Onde nli d,k(p) é a distância de i a d em Td,k (p) e
 é um parâmetro que diz o quanto a distância
afeta o decremento do feromônio.
Atualização do feromônio

d
i
 p  1    p      p
d
i
0 <  < 1 é o coeficiente de evaporação
(esquema de média continuada)
d ,k
i
Tabela de roteamento


d





p


j
j
d


aij p 
j  N i


d
 l  p   l 
lN i
Onde Ni são os vizinhos de i.
j = 1/wtj wtj = ltj + vtj
ltj - Tempo de download
vtj - tempo de visita
Probabilidade
p 
D
ij
 a  p   g 
 a  p   g 
d D
d
ij
d
il
d D ,lN i
d
d
Onde Ni são os vizinhos de i, D é o conjunto de
destinos a levar o usuário e gd o parâmetro que
diz o quanto a página d é boa para o usuário.
Simulação
• Foram geradas 50 formigas em 50 iterações
•  = 0,3
• Fatores que prejudicam o AntWeb foram
exagerados
• Foi considerado o caso que o usuário toma o
caminho errado para sua página
• Foi desconsiderado o efeito auto-catalítico
• Características do site fictício
Feromônio para 3
1A
0,032 2A
2B 0,337
3A
1
3B 0,206
2
3
0,810
Caso 1
D = {1,2}
1A
0,87
2A
2B
3A
0,32
g1 = 1
g2 = 2
0,13
3B
0,68
3A
1
1
2
3
2*
Caso 2
D = {1,3}
1A
0,45
2A
2B
0,8
0,2
3A
1,0
g1 = 1
g3 = 1
0,55
3B
1A
0,0
2A
1
2
3
2B (0.55)
Conclusão
• Desenvomemos o AntWeb adaptativo.
• Implementamos o modelo 1 para situações
reais.
• Fizemos estudos de casos envolvendo o
modelo 2.
Perspectivas
• Uma alternativa ao fornecimento do link
direto em sistemas de busca.
• Busca de qualquer item em sites.
• Aprimoramento de outras heurísticas de
navegação adaptativa.
Obrigado pela participação