Home

Sistema adaptativo para web sites baseado no comportamento da

Contents

1. 54 1 3 2 Situa o 2 Dois caminhos sendo 1 de 5 links e outro com 4 links 56 1 3 3 Situa o 3 Dois caminhos sendo 1 com 5 links e outro com 2 links 58 I11 3 4 An lise dos resultados Es sun ee ee 59 Cap tulo IV AntWeb Adaptativo see ee sae ee Re Ge RE RE RE ER ERGE AR RR RE RR RE GER ER EG EA RR Rae 60 IV 1 A concep o do AntWeb Adaptativo nn 61 IV 2 Como unir a meta heur stica da formiga com a navega o na Internet 64 IV 3 Como associar o feFOMTO I Oi in nene 66 IV 4 Compara o entre o AntWeb adaptativo e outros sistemas 68 IV 5 Esquema do AntWeb adaptativo na Web mnn nennen ee ee ee 69 IV 6 Modelo 1 do AntWeb adaptativo eie ee RR RR RR RA ee ke ee ee nn 70 IV 6 1 A representa o do ferom nio no modelo 1 eee 71 IV 6 2 Atualiza o do SFMOMA ER EE ene Es RR ee ee Ge 71 IV 6 3 Formas de destacar um link ea sn DE Rd 72 IV 7 Modelo 2 do AntWeb adaptativo neon RR RR RR RA ee ke ee ee ee ee 77 IV 7 1 A representa o do ferom nio no modelo 2 nn eenn 78 IV 7 2 Modelo 2 BASICO Hs un aan ne 79 IV 7 3 Extens o do modelo para mais de um destin0 oon eeen 81 IV 7 4 Identificando a pagina destino do usu rio a 82 IV 7 5 O algoritmo para atualiza o do ferom nio een eenn 83 IV 7 6 O processo de adapta o da apresenta o da p gina 84 Cap tulo V Implementa o ss AE de en 85 Vat Componentes T SICOS is EER EE
2. query value while list value each this gt links query value query AND pheromone gt this gt configuration gt data threshold query ORDER BY pheromone desc LIMIT this gt configuration gt data max links to show return query return false gt lt PHP class CacheLinksSelector extends LinksSelector var cache function getOut if lisset this gt cache this gt cache LinksSelector getOut 187 unset this gt next unset this gt querySelectLinks return this gt cache gt lt PHP class LinksFilter extends Decorator function amp getOut e amp Decorator getOut if lisset e return e while isset e if e gt isTag and e gt getName A and e gt getType START return e e amp Decorator getOut return null gt lt PHP 188 class LinksArrayMaker extends Decorator function amp getOut return array for e amp Decorator getOut if lisset e break array_push return e gt getAtribute HREF return return gt lt PHP class QuerylnsertLog extends Query var configuration var url var linksSelector var parserHtml var fields var values var adaptabilityChecker function setAdaptabilityChecker amp p this gt adaptabilityChecker amp
3. return this gt buffer 142 unset this gt buffer return return gt lt PHP class StringCache extends Decorator End var cacheString function pushString h this gt cacheString h function getOut return this gt cacheString this gt cacheString return return gt lt PHP class ReturnKeeper extends Decorator var return array function getOut if count this gt return 0 return parent getOut 143 if lisset return return return return return else return array_shift this gt return function giveBack r array_push this gt return r gt lt PHP class StringDecomposer extends Decorator var buffer function giveBack c this gt buffer c this gt buffer function getOut if this gt buffer this gt buffer parent getOut if lisset this gt buffer 144 return null if this gt buffer return null return this gt buffer 0 this gt buffer substr this gt buffer 1 return return gt lt PHP class InternalUrlsProcessor extends Decorator var url function setUrl amp url this gt url amp url function isRelative u array parse_url u if lisset array scheme return true return false 145 function makeAbsolutePath amp p
4. Ent o destaque o link correspondente Fim Fim O m nimo significativo um valor constante que na met fora das formigas significa a quantidade m nima de ferom nio que pode ser percebida por uma formiga Se a formiga est em um dilema entre dois caminhos a seguir e em um deles conter ferom nio mas a taxa de ferom nio for em quantidade t o pequena que a formiga n o po a perceber a probabilidade de escolha de qualquer dos dois caminhos continua sendo 50 IV 7 Modelo 2 do AntWeb adaptativo A principal diferen a do modelo 2 em rela o ao 1 a separa o feita entre a fun o de indicar o menor caminho da fun o de determinar a p gina mais interessante para o usu rio No modelo 1 estas duas fun es est o fundidas no ferom nio No modelo 2 o ferom nio serve apenas para a indica o do menor caminho A determina o da relev ncia de uma p gina para o usu rio no modelo 2 representada por um valor associado p gina que chamamos de goodness No modelo 2 o goodness pode representar qualquer heur stica que diga o quanto a p gina interessante para o usu rio Dependendo da forma como esta heur stica for determinada n o teremos mais a vantagem do usu rio n o precisar entender o sistema como temos no modelo 1 Por exemplo se determinarmos que a heur stica que vai ser usado no goodness for a popularidade da p gina o modelo 2 vai se comportar de forma parecida com o modelo 1 n o sendo necess rio
5. P gina inicial P gina da p s gradua o P gina do Corpo Docente P gina dos professores da p s gradua o Site Li Weigang Figura 43 Estrutura parcial do site do CIC As navega es foram feitas conforme mostrado na Tabela 10 Nesta 100 tabela cada linha representa uma trajet ria executada A ordem cronol gica das trajet rias est listada de baixo para cima nesta tabela As trajet rias em que n o foi destacado nenhum link foram executadas quando as taxas de ferom nio ainda eram iguais a zero e as trajet rias que a tabela informa que foram simultaneamente destacados os dois links foram executadas quando as taxas de ferom nio para os dois links estavam iguais o que quer dizer que devemos desconsiderar o destacamento de links nestes casos A Departamento de Ci ncia da Computa o CIC Microsoft Internet Explorer laf Arquivo Editar Exibir Favoritos Ferramentas Ajuda votar Dr fil Aresquisar G Favoritos Hist rico Sr RI 4 ki 2 Links 2 Sr Universidade de Brasilia Instituto de Ci ncias Exatas Departamento DE CI NCIA DA COMPUTA O Corpo Docente Pa Curso de Graduag o Ea N Pesquisa Extens o Lig es de Computag o Debates sobre Seguran a Figura 44 Uma das p ginas obtidas durante o experimento Quando o sistema n o indicava nenhum dos links ou os dois links eram destacados simultaneamente as trajet rias eram realizadas nos dois
6. Tabela 9 As m dias de throughput das tr s situa es Tempo seg 60 360 660 960 1260 1560 1860 2160 2460 Situa o 1 0 39 17 67 95 76 85 82 6 86 33 88 24 89 9 90 9 Situa o 2 0 44 31 69 47 79 19 83 51 87 12 89 03 90 74 91 69 Situac o 3 10 83 49 58 72 54 80 08 86 31 88 97 90 39 91 59 92 48 O acr scimo de um link para a p gina objetivo na pagina http intranet menus menu relacao equipamentos quadro total htm resultando na situa o 2 aumentou a efici ncia do site Da mesma o link na p gina http intranet menus menu relacao equipamentos quadro resumo htm da situa o 3 apresentando uma melhora mais significativa pelo fato de diminuir a distancia da p gina objetivo para dois links ao inv s de quatro como feito na situa o 2 Outro fato observado que com o aumento do tempo de simula o o aumento do rendimento em rela o a situa o anterior diminui 60 CAPITULO IV ANTWEB ADAPTATIVO Denominamos de AntWeb o estudo da aplicabilidade da meta heuristica da formiga na Web Este estudo at o momento possui dois aspectos o aspecto para avalia o de estruturas de sites apresentado no cap tulo anterior e o aspecto adaptativo que estudaremos neste cap tulo O aspecto adaptativo diferente do primeiro aspecto trata do emprego da meta heur stica da formiga no sentido de orientar o usu rio da Interne
7. http intranet recursos tecnologicos relacao equipamentos fabrica projetos quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos atendimento usuario quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos area suporte quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos linha digitalizacao quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos fabrica software quadro total maquinas htm http intranet recursos tecnologicos softwares homologados htm http intranet recursos tecnologicos cronogramas cronograma manutencao 3 1999 htm http intranet recursos tecnologicos cronogramas cronograma manutencao 4 1999 htm http intranet recursos tecnologicos cronogramas cronograma manutencao 1 2000 htm http intranet recursos tecnologicos cronogramas cronograma manutencao 2 2000 htm http intranet recursos tecnologicos topologias topologia da internet htm 136 http intranet recursos_tecnologicos topologias topologia_da_intranet htm http intranet recursos_tecnologicos topologias topologia_da_extranet htm http intranet recursos_tecnologicos trafego_de_rede htm http bsbserv006 mrtg 200 252 229 192_2 html http bsbserv006 mrtg 10 61 254 2_2 html http bsbserv006 mrtg 10 61 254 2_5 html http bsbserv006 mrtg 10 61 254 2_3 html http bsbserv006 mrtg 10 61 254 1_2
8. http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo area_tecnica desenvolvimento htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo area_tecnica linha_producao htm 130 http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo area_tecnica suporte htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo fabrica_software htm http bsbserv003 sasp consulta default htm mailto recrutamento bsb politec com br http intranet recursos_humanos perfil_profissional perfil_pessoal htm http intranet recursos_humanos perfil_profissional mapa_recursos jose_silvino_filho html http intranet recursos_humanos perfil_profissional mapa_recursos luciana_oliveira_macedo html http intranet recursos_humanos perfil_profissional mapa_recursos marcos_antonio_quezado_soares html http intranet recursos_humanos perfil_profissional mapa_recursos maria_rosa_steimpaj_matoso html http intranet recursos_humanos perfil_profissional mapa_recursos sergio_frossard_de_almeida html http intranet recursos_humanos perfil_profissional mapa_recursos simone_silva_ferreira html http intranet recursos_humanos perfil_profissional mapa_recursos carlos_eduardo_bianchi_ferratoni html http intranet recursos_humanos perfil_profissional mapa_recursos etel_cristina_pires html http intranet recursos_humanos perfil_profissional mapa_recursos george
9. Assim AntWeb nos apresenta uma rea de estudo atrav s da aplica o de uma heur stica um servi o na Web e um sistema que prop e uma nova metodologia para guiar o usu rio Neste cap tulo falaremos sobre a concep o do AntWeb e descreveremos os dois modelos desenvolvidos para aplica o da meta heur stica da formiga na Web Apresentaremos tamb m uma compara o entre o AntWeb e outros sistemas formiga tradicionais o algoritmo utilizado para atualiza o 61 do ferom nio e o processo de adaptac o da apresentac o da p gina entre outros aspectos estudados para implementac o do modelo AntWeb na Web IV 1 A concepc o do AntWeb Adaptativo Nesta sess o descreveremos como surgiu a ideia do AntWeb adaptativo e a sequ ncia de fatos e conclus es que levaram ao desenvolvimento dos dois modelos do AntWeb adaptativo A primeira concep o sobre um sistema adaptativo que usasse o comportamento da formiga como fundamento foi inspirada principalmente no fato da formiga seguir os caminhos mais populares e secundariamente na caracter stica que a formiga tem de conseguir descobrir o menor caminho entre o formigueiro e a fonte de alimento Esta concep o baseou se na observa o de que na maioria das vezes que o usu rio est navegando em algum site a p gina que ele est procurando na verdade a p gina mais popular do site naquele instante Por exemplo suponhamos que em um site de um supermercado na v spera do dia dos
10. function generateQuery return CREATE TABLE IF NOT EXISTS Urls url CHAR 255 BINARY PRIMARY KEY pheromone DOUBLE UNSIGNED gt lt PHP class ExtractingElement extends Decorator var description function setDescription p this gt description amp p function getDescription return this gt description gt lt PHP class ExtractingNonTag extends ExtractingElement function ExtractingNonTag 171 this gt setDescription Sending non tag function getOut return parent getOut if lisset return return return if return lt exit erro sending non tag for car parent getOut if lisset car or car lt this gt next gt giveBack car return return return car gt lt PHP class Extracting Tag extends ExtractingElement function ExtractingTag 172 this gt setDescription Sending tag function extractUntilDoubleQuote return car parent getOut while isset car return car if car break car parent getOut return return function extractUntilSimpleQuote car parent getOut while isset car return car if car break car parent getOut return return function getOut 173 return parent getOut if lisset return return return if r
11. o com o AntWeb Como um dia algu m disse Fazer ci ncia como cavar um buraco no ch o Quanto mais cavamos mais surge o que cavar E foi exatamente o que aconteceu com o AntWeb Hoje existe muito mais o que fazer do que existia antes de come armos o nosso trabalho 113 VII 2 O que sobrou para fazer na implementa o A implementa o do modelo 1 funcionou de maneira satisfat ria ao ser disponibilizado na Web mas ainda cont m algumas limita es que o impedem de auxiliar uma gama maior de usu rios A principal delas a restri o p ginas escritas em linguagem HTML Hoje em dia existe uma variedade enorme de tecnologias dispon veis na Web e a cada dia que passa essa variedade cresce ainda mais Tornar a implementa o do AntWeb compat vel com todas essas tecnologias atualmente imposs vel Mas apesar disto a linguagem HTML ainda uma linguagem muito usada na Web o que implica que o AntWeb compat vel com um grande volume de p ginas No entanto se essa situa o mudar no futuro a sobreviv ncia do sistema depende de adapta es para que ele se torne compat vel com outras tecnologias Entre essas tecnologias podemos citar que seria de grande valia fazer com que a implenta o fosse compat vel com a linguagem XHTML uma deriva o da linguagem XML flash shockwave e Java Claro que como toda implementa o especialmente na sua primeira vers o o AntWeb precisa ampliar sua fase de testes com v
12. this gt buildAdaptabilityChecker antW eb this gt buildLog antWeb var queries var i 0 function QueryExecuter this gt queries array this gt queries this gt i amp p this gt i 161 function execute reset this gt queries while list query each amp this gt queries if return query gt execute return return gt lt PHP class HandlerHtmlParser extends Decorator var htmiParser var closed false function setHtmlParser amp i this gt htmlParser amp i id function getOut return this gt htmlParser gt shiftElement if lisset return in parent getOut if isset in this gt htmlParser gt pushHtml in 162 return this gt htmlParser gt shiftElement return return function getOut if this gt closed while html parent getOut this gt htmlParser gt pushHtml html this gt closed true return this gt htmlParser gt shiftElement gt lt PHP class MySqlConection var conection var mysqlhost var username var password var databasename var configuration function setConfiguration amp c this gt configuration amp c 163 function loadConfiguration this gt mysqlhost this gt configuration gt data mysqlhost this gt username this gt configuration gt data username this
13. PheromoneUpdaterTrigger Configuration Pheromonelncrease PheromoneUpdater lt gt UpdateRecorder QuemManager MySalConnection Figura 41 Diagrama de Classes simplificado do modulo de atualizacao A Figura 41 mostra um diagrama de classes simplificado da implementa o do m dulo de atualiza o de ferom nio Este m dulo fica sendo executado em segundo plano no servidor e respons vel por manter as taxas de ferom nio das p ginas atualizado As classes mostradas na Figura 41 s o PheromoneUpdaterTrigger respons vel por disparar todo o processo de atualiza o que permanece sendo executada em um la o infinito Ap s disparar um processo de atualiza o ela causa uma pausa na execu o do programa de acordo com o tempo de intera o obtido de Configuration e somente ap s esta pausa ela dispara outro processo de atualiza o recome ando o ciclo novamente PheromoneUpdater respons vel pela atualiza o do ferom nio em si O processo de atualiza o corresponde na altera o das taxas de todas as p ginas determinada pelos valores obtidos de Phermonelncrease Pheromonelncrease Nesta classe est a fun o de acr scimo de 93 ferom nio Assim ao trocarmos a fun o de acr scimo de ferom nio do sistema basta apenas trocar esta classe sem causar nenhuma altera o no restante do sistema Configuration respons vel por controlar os par metros usados na atualiza o de ferom nio
14. descrito abaixo CrieTabelaLog Inicio Se arquivo de log estiver vazio Ent o Saia V para o primeiro log do arquivo de log Repita Se o log atual for de um arquivo existente na Tabela de P ginas Ent o Inclua log na tabela de Logs Ate estar no ltimo log do arquivo de log Fim O algoritmo inicialmente verifica se o arquivo de log est vazio ou seja se existe algum log para ser filtrado Em seguida o algoritmo percorre todo arquivo de log selecionando os logs de interesse do sistema O algoritmo sabe se um log interessante verificando se o arquivo deste log est registrado na tabela de p ginas Se o log for de interesse o algoritmo inclui o log na tabela de log caso contr rio n o o inclui Preenchimento da tabela de backtracks A tabela de backtracks o objetivo deste processo Este processo depende do processo descrito anteriormente pois a mat ria prima que ele usa para cria o da tabela de localiza es esperada a tabela de logs O algoritmo usado neste processo descrito a seguir 119 PreenchaTabBacktracks Inicio ConstruaHash T Construa Tabela Hash dos links do website Particione Tabela de log por visitante Ordene todas as parti es pela seq amp ncia cronol gica de acessos Para cada Parti o de Visitante Fa a Particione novamente de tal forma que cada nova parti o termine com a P gina Objetivo Para cada Parti o de Visitante e P gina Objetivo Fa a
15. element each selections 191 suggestion element key pheromone element value this gt fields suggestion ind pheromone ind this gt values suggestion pheromone ind else this gt fields isAdaptable this gt values 0 function generateQuery gt lt PHP this gt generateFieldsValues query INSERT DELAYED INTO Logs this gt fields VALUES this gt values return query class Sender extends Decorator function sendWholePage buffer amp Decorator getOut while isset buffer echo buffer buffer amp Decorator getOut 192 gt lt PHP class PageLoader extends DecoratorEnd var file var url function setUrl amp u this gt url amp u J function PageLoader u this gt url amp u function openFile return this gt file fopen this gt url gt get r function amp getOut if isset this gt file if feof this gt file fclose this gt file unset this gt file 193 else return fgets this gt file if return fclose this gt file this gt openFile return null return return return null gt lt PHP class LinksGuider extends Decorator var configuration function setConfiguration amp p this gt configuration amp p function process
16. this gt url gt testUrl p url parse_url this gt url gt get if substr url path 1 url path p url path dirname url path p p Miscellaneous glue_url url function process amp u if this gt isRelative u this gt makeAbsolutePath u function amp getOut element amp Decorator getOut if lisset element return element if element and element gt isTag and element gt getType START if element gt getName A and a HREF 146 u element gt getAtribute a if isset u this gt process u element gt setAtribute a u if element gt getName IMG and a SRC u element gt getAtribute a if isset u this gt process u element gt setAtribute a u if element gt getName FRAME and a SRC u element gt getAtribute a if isset u this gt process u element gt setAtribute a u if element gt getName BODY and a BACKGROUND u element gt getAtribute a if isset u this gt process u element gt setAtribute a u return element gt lt PHP class Query var conection function setConection amp p this gt conection amp p function execute if query this gt generateQuery return false if return mysql_query
17. zi 4 E Done Local intranet Figura 37 Home page do CIC com o AntWeb E assim nosso usu rio pode continuar navegando pela Internet usando o AntWeb Para ele deixar de usar o AntWeb basta digitar outro endereco na barra de endereco de seu browser que ele sair do sistema Para entendermos melhor como funciona este esquema vamos imaginar um cen rio em que nosso usu rio acessaria o site do CIC sem o AntWeb O usu rio digita o endere o do site no seu browser e em seguida seria mandado uma requisi o pela Internet ao servidor web CIC da p gina desejada 1 conforme mostra a Figura 39 Em seguida o seu browser receberia o c digo HTML da p gina 2 e apresentaria a p gina ao usu rio Agora vamos imaginar um cen rio em que nosso usu rio acessa o site do CIC pelo AntWeb Primeiro nosso usu rio acessa a p gina do AntWeb e clica no link correspondente Neste momento enviada uma requisi o ao servidor do AntWeb 1 conforme mostra a Figura 40 O AntWeb ent o busca a p gina requisitada 2 3 no servidor web do CIC e verifica a quantidade de ferom nio em cada link da p gina e outros dados no banco de dados 4 para ele saber qual link ser destacado O 88 AntWeb destaca os links correspondes e depois altera a URL de todos os links na p gina de forma que os links passem a apontar para o servidor do AntWeb Em seguida o AntWeb grava um log no banco de dados que servir para o processo de atualiza o do ferom nio
18. 1998 57 W M Teles L Weigang C G Ralha AntWeb The Adaptive Web Server Based on the Ants Behavior WI International Conference on Web Intelligence IEEE WIC Halifax Canada 2003 58 W M Teles L Weigang C G Ralha Uma heuristica para guiar os usu rios da Internet baseada no comportamento da formiga ENIA SBC Brasil 2003 59 W Viegas Orienta o aos alunos na reda o e apresenta o gr fica de monografias teses e disserta es Departamento de Administra o da Universidade de Bras lia Bras lia 1995 60 E Gamma R Helm J Vlissides R Johnson Design Patterns Elements of Reusable Object Oriented Software Designed by Grady Booch Hardcover Addison Wesley Longman ISBN 0201633612Inc 1994
19. Execu o 6 0 00 54 17 68 18 80 21 86 11 86 54 90 05 89 58 91 87 Execu o 7 0 00 44 44 70 45 79 17 83 33 86 22 89 25 91 90 91 87 Execu o 8 0 00 47 22 70 45 77 60 83 33 88 14 90 32 91 20 91 87 Execu o 9 0 00 45 83 68 18 80 73 81 75 84 94 87 90 89 81 90 85 Execu o 10 0 00 44 44 68 94 76 04 81 75 89 42 88 17 90 05 91 26 Execu o 11 0 00 40 28 66 67 79 69 82 54 88 46 89 78 90 51 92 68 Execu o 12 0 00 41 67 68 18 77 60 83 73 87 82 88 98 91 44 91 87 Execu o 13 0 00 48 61 71 21 79 17 82 54 87 82 87 63 90 51 92 48 Execu o 14 0 00 41 67 69 70 79 69 83 73 86 22 89 52 91 20 92 28 Execug o 15 0 00 41 67 75 00 78 65 83 73 86 54 89 78 92 36 91 67 Execu o 16 0 00 48 61 66 67 77 08 83 33 86 22 89 78 89 35 91 06 Execu o 17 0 00 43 06 67 42 80 73 83 73 88 46 89 78 89 35 92 48 Execu o 18 0 00 41 67 71 21 80 73 84 92 86 54 88 71 91 44 91 87 Execu o 19 0 00 41 67 69 70 79 69 84 13 86 22 88 44 91 90 91 26 Execu o 20 0 00 45 83 70 45 80 21 84 52 88 14 88 98 90 74 91 67 M dia 0 00 44 31 69 47 79 19 83 51 87 12 89 08 90 74 91 69 Desvio Padr o 0 00 3 55 2 23 1 50 1 38 1 10 0 78 0 89 0
20. M Phillips e D S Pugh How to get a PhD a handbook for students and their supervisors 2 ed Open University Press USA 1987 12 G Booch J Rumbaugh I Jacobson UML guia do usu rio Editora Campus Rio de Janeiro 2000 13 G Di Caro e M Dorigo AntNet A mobile agents approach to adaptive routing Technical Report 97 12 IRIDIA Universite Libre de Bruxelles 1997 14 G Di Caro e M Dorigo AntNet Distributed stigmergetic control for communications networks Journal of Artificial Intelligence Research JAIR 1998 9 317 365 15 G Di Caro e M Dorigo Extending AntNet for best effort Quality of Service routing Umpublisherd presentation at ANTS 98 From Ant Colonies to Artificial Ants First International Workshop on Ant Colony Optimization 1998 16 G Di Caro e M Dorigo Two ant colony algorithms for best effort routing in datagram networks In Proceedings of the Tenth IASTED International Conference on Parallel and Distributed Computing and Systems PDC 98 217 IASTED ACTA Press 1998 541 546 17 J T Cariolano Ant Web Algoritmos formiga aplicados a avalia o de websites projeto final de gradua o Departamento de Ci ncia da Computa o da Universidade de Bras lia 2002 18 L A M Palazzo Sistemas de Hiperm dia Adaptativa Universidade Cat lica de Pelotas Escola de Inform tica 1999 19 L M Gambardella e M Dorigo Ant Q A Reinforcement Learning Approach to the
21. Um nodo uma cole o de dados organizados sobre um t pico espec fico A hiperm dia a uni o da tecnologia do hipertexto com os recursos da multim dia hipertexto multim dia hiperm dia um estilo de desenvolvimento de sistemas para a cria o manipula o recupera o e apresenta o de informa o Na maioria dos estudos sobre hipertexto a descri o das no es b sicas como ncora nodo e link variam muito N o poss vel encontrar uma lista comum de defini es Existem diferentes termos usados para se referir a nodo como cart es bloco e p gina Nodos podem ser categorizados de diferentes formas Por exemplo um nodo de alto n vel um nodo que contem somente refer ncias e ponteiros para outros nodos Um nodo de controle somente permite que os usu rios controlem sua navega o atrav s da rede Nodos de controle podem ser chamados de nodos 30 transacionais nodos navegacionais ou p ginas indices 44 39 Os nodos ou p ginas que possuem o conte do da informa o que os usu rios costumam procurar s o chamados de p ginas conte do 44 Um link uma informa o contida em um nodo referenciando outro nodo ou um ponteiro entre nodos O nodo no qual est situado determinado link chamado de nodo ncora deste link O nodo que o link referencia chamado de nodo destino Os links s o geralmente representados por algum objeto situado no nodo de partid
22. WresetParam PsetAlfag A Poet A ltfad jg setBetal iMgetBetal set Rol Paget Rol Figura 25 Diagrama de classes de interface A seguir apresentamos as principais classes usadas no sistema 52 Classe Col nia Classe responsavel pela coordenac o entre as formigas Classe ControladorColonia a classe respons vel pela intera o entre as classes Col nia TelaPrincipal Website e Par metros Classe Formiga a classe que corresponde aos componentes de localiza o corrente software que percorrem o WebSite em busca da p gina alvo definida Todas elas t m como ponto de partida a homepage do website Uma formiga escolhe a pr xima p gina a visitar com base no ferom nio presente em cada um dos links de sua Classe Link Classe respons vel pelo relacionamento entre as p ginas e 53 guarda uma determinada quantidade de ferom nio Classe Pagina Representa uma p gina do WebSite Cada p gina pode possuir links para outras p ginas Classe Website Guarda refer ncias a todas as p ginas do WebSite Armazena tamb m refer ncias para a homepage e a p gina objetivo 11 3 Resultados obtidos Para testar o funcionamento de AntWeb foi utilizada a estrutura do site da Politec inform tica O site possui 358 p ginas e 389 links e tem em m dia 2700 visitantes por dia Cerca de 17 dos acessos s o feitos pelos pr prios funcion rios A estrutura do site montada em tempo
23. amp u u this gt configuration gt data application_address url urlencode u function amp getOut element amp Decorator getOut gt lt PHP 194 if lisset element return element if element gt isTag and element gt getType START if element gt getName A u element gt getAtribute HREF this gt process u element gt setAtribute HREF u if element gt getName FRAME u element gt getAtribute SRC this gt process u element gt setAtribute SRC u return element class ExceptionProcessor extends Decorator function amp getOut t amp Decorator getOut if lisset t return t 195 if t gt isTag e t gt getElement e str_replace lt imgSRC lt IMG SRC e t gt setElement e return t gt lt PHP class Unwrapper extends Decorator function amp getOut e amp Decorator getOut if lisset e return e if get class e htmlelementparser e e gt getElement return e gt lt PHP class LinksHighlighter extends Decorator 196 var configuration var linksSelector var links function setLinksSelector amp p this gt linksSelector amp p function setConfiguration amp p this gt configuration amp p function hasToHighlight element i
24. gt password this gt configuration gt data password this gt databasename this gt configuration gt data databasename function conect this gt loadConfiguration if this gt conection mysql_connect this gt mysqlhost this gt username this gt password mysql select db this sdatabasename this gt conection return true else echo n o possivel fazer aconex o com o Banco de dadosin mysql error return false function get if this gt conection this gt conect return this gt conection function close gt 164 if this gt conection mysql close this gt conection unset this gt conection lt PHP class Configuration var iniFile var configuration var dBAccess function setDBAccess amp p this gt dBAccess amp p function Configuracao if this gt iniFile if function setlniFile if this gt iniFile if function data d ret this gt configuration d return ret 165 function load if this gt configuration parse_ini_file this gt iniFile this gt configuration mysqlhost this gt dBAccess gt data mysalhost this gt configuration usernameY this gt dBAccess gt data username this gt configuration password this gt dBAccess gt data password this gt configuration databasename this gt d
25. intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade recursos_humanos treinamento htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade recursos_humanos departamento_pessoal htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade recursos_humanos medicina_trabalho htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade area_tecnica area_tecnica htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade area_tecnica atendimento_usuario htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade area_tecnica consultoria htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade area_tecnica desenvolvimento htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade area_tecnica linha_producao htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade area_tecnica suporte htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade fabrica_software htm http intranet menus menu_pessoal_telefones_enderecos htm http intranet recursos_humanos pessoal endereco_telefones gerencia_operacional gerencia_operacional htm http intranet recursos_humanos pessoal endereco_telefones gerencia_comercial gerencia_comercial htm http intranet recursos_humanos pessoal endereco_telefones administrativa_financeira administrativa_fi
26. o de otimiza o de rotas da fun o de determinar a p gina mais interessante para o usu rio fazendo com que o ferom nio servisse apenas para indicar o caminho mais curto at determinado s destino s Assim usando o modelo 2 podemos levar o usu rio para qualquer p gina mesmo que esta n o seja a p gina mais popular do site Com essas duas fun es separadas pode se aplicar outras heur sticas al m da popularidade para determinar quanto uma p gina relevante para o usu rio 64 O modelo 2 at o momento n o foi implementado em nenhum site da Web mas experimentos feitos com simula es usando sites fict cios mostram que o modelo 2 alcan a os objetivos propostos na sua concep o IV 2 Como unir a meta heur stica da formiga com a navega o na Internet No mundo real as formigas naturais caminham em um espa o bidimensional partindo do formigueiro a procura da fonte de alimento Elas usam o rastro de ferom nio deixado por outras formigas para saber qual caminho seguir e ao mesmo tempo deixam no ch o o seu pr prio ferom nio para que outras formigas tamb m sigam seu rastro As formigas artificiais de Marco Dorigo possu am um ambiente um pouco diferentes Ao inv s de um espa o bidimensional elas caminham por estados discretos passando de um estado para outro atrav s de transi es estabelecidas entre eles 29 Semelhante s formigas naturais as formigas artificiais escolhem caminhos com maior quantidad
27. o os recursos usados pelos sistemas de HA para informar ou influenciar o usu rio no seu processo 36 de navegac o As principais t cnicas de Navegac o Adaptativa s o Orientac o Direta OD Classifica o Adaptativa CA Oculta o Adaptativa OA Anota o Adaptativa Gera o de Links e Mapas Adaptativos MA A Orientac o Direta a t cnica mais simples de suporte a navegac o adaptativa Consiste em decidir em cada ponto da navegac o qual o melhor nodo a ser visitado a seguir Esta t cnica tem como desvantagem n o oferecer suporte no caso do usu rio n o desejar seguir a sugest o do sistema A Classificac o Adaptativa consiste em classificar os links de um nodo de acordo com sua relev ncia Apesar de bastante til seu uso na pr tica se restringe aos links n o contextuais Ocultac o Adaptativa a t cnica mais frequentemente empregada em navega o adaptativa Consiste em restringir o espa o de navega o ocultando os links para nodos n o relevantes Seu uso protege o usu rio da complexidade de um hiperespa o irrestrito e reduz a sobrecarga cognitiva Uma das vantagens desta t cnica que pode ser empregada com todos os tipos de links exceto claro os do browser A Anota o Adaptativa consiste em aumentar a informa o existente nos links com alguma forma de anota o ou coment rio que podem dizer mais sobre o estado corrente dos nodos a que se conectam
28. quantidade de acessos feitos a esta p gina nos ltimos 30 segundos com as quantidades de acesso dos intervalos anteriores de forma que quanto mais antigo um intervalo menos influ ncia ele tem no ferom nio atual Prefer ncia por caminhos mais curtos Esta caracter stica era esperada uma vez que o comportamento das formigas reais conduz a rotas otimizadas e estamos reproduzindo o mesmo ambiente da formiga real na Internet Consideremos que o modelo 1 otimize rotas em caso de exist ncia de caminhos com diferentes custos na estrutura do site Assim haveria uma otimiza o na navega o dos usu rios uma vez que os caminhos mais curtos seriam indicados Esta caracter sca do comportamento da formiga de otimizar caminhos chamada na literatura de avalia o implicita da solu o 29 Indica o de p ginas interessantes para o usu rio Este benef cio uma deriva o da primeira caracter stica Uma vez que o sistema leva os usu rios as p ginas mais populares existe uma grande probabilidade destas p ginas serem as p ginas que a maioria dos usu rios est o procurando ou ao menos serem 97 p ginas interessantes para a maioria dos usu rios Diminuic o de erros na trajet ria do usu rio Um outro problema que costuma ocorrer na navegac o do usu rio s o os erros de trajet ria Ocorrem quando o usu rio espera que sua pagina objetivo esteja embaixo de uma determinada hierarquia na estrutura do site e na verdade e
29. this gt i j 206 this gt queries j gt setInterval amp i gt lt PHP class IntervalMaker var configuration var lastUpdate function setConfiguration amp c this gt configuration amp c function setLastUpdate amp u this gt lastUpdate amp u function amp getOut return array if lastUpdateStr this gt lastUpdate gt get lastUpdate strtotime lastUpdateStr interationTime this gt configuration gt data iteration_time now strtotime now inteval lastUpdate intervalsMaked 0 while inteval interationTime lt now intervalsMaked 207 array_push return new Interval date Y m d H i s inteval date Y m d H i s inteval interationTime if intervalsMaked gt 10 break return return gt lt PHP class IntervalMakerCache extends IntervalMaker var cache function getOut if lisset this gt cache this gt cache parent getOut return this gt cache gt lt PHP class QueryAdditionsCalculator extends Query var function Not definied 208 var interval function setlnterval amp p this gt interval amp p function getFunction return this gt function gt lt PHP class QueryAdditionsCalculatorQClicks extends QueryAdditionsCalculator l function QuervAdditionsCalculatorQClicks this functions gu
30. vil TSP Traveling Salesman Problem Problema do Caixeiro Viajante UnB Universidade de Brasilia URL Uniform Resource Locator localizador de recurso unificado XML Extended Marked Language WML Web Mining Log WWW World Wide Web viii LISTA DE FIGURAS FIGURA 1 EXPERIMENTO DA PONTE BIN RIA iese sesse se see ee ee ee ee ee ee ee ee see ee ee ee ee ee ee ee ee ee ee ee ee 10 FIGURA 2 GR FICO DE USO DOS DOIS CAMINHOS PELA FORMIGA uses sees esse se see ee ee ee ee ee ee ee 11 FIGURA 3 FORMIGAS CAMINHADO ENTRE O NINHO E A FONTE DE ALIMENTO ae 12 FIGURA 4 UM OBST CULO NA TRILHA DE FORMIGAS uses esse ees ese ee see ee ee ee ee ee see ee ee ee ee ee ee ee 13 FIGURA 5 AS FORMIGAS SE DIVIDEM NA ESCOLHA DO CAMINHO A SEGUIR esse sesse esse se ee ee 13 FIGURA 6 O CAMINHO MAIS CURTO ACABA PREVALECENDO nnn ee ee esse se see ee ee ee ee ee ee ee 14 FIGURA 7 DIST NCIAS ENTRE OS PONTOS PARA FAZER A SIMULA O 14 FIGURA 8 ESTADO DA SIMULA O NO TEMPO 0 aaan ee ee ee ee ee ee ee Re ee ee ee ee ee 15 FIGURA 9 ESTADO DA SIMULA O NO TEMPO l ees ees ee ee ee ee ee oenen ee ee ee ee ee ee ee ee ee 15 FIGURA 10 ESTADO DA SIMULA O NO TEMPO 2 ees ees ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee 16 FIGURA 11 ESTADO DA SIMULA O NO TEMPO 3 aaan ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee 17 FIGURA 12 ESTADO DA SIMULA O NO TEMPO
31. 4 ees ees esse ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee 17 FIGURA 13 TRILHA DE FEROM NIO FORMADA NA SIMULA O ee esse ee ee esse se see ee ee ee ee ee ee ee 18 FIGURA 14 AS FORMIGAS SEGUEM A TRILHA DE FEROM NIO FORMADA an se see ee ee ee ee se ee ee 18 FIGURA 15 MODELO DE REDE annae ee ees ee ee ee ee ee ee ee ee EENES o aE KiE ee ee ee ee ee ee ee ee 25 FIGURA 16 CICLO CL SSICO DE ADAPTA O ee ee ee eeen ee Re Ee ee Re ee ee 34 FIGURA 17 TRAJETO EXECUTADO POR USU RIOS PARA ENCONTRAR A P GINA 9 38 FIGURA 18 NOVA ESTRUTURA DO SITE AP S A INSER O DE UM NOVO LINK ees ese sees ees ee 39 FIGURA 19 PROCESSO DE FILTRAGEM DO ARQUIVO DE LOG sees sesse see ee ee ee ee ee ee ee ee ee ee ee ee 41 FIGURA 20 PROCESSO DE PREENCHIMENTO DA TABELA DE BACKTRACK snee 43 FIGURA 21 PROCESSO DE EXTRA O DE INFORMA ES DA TABELA DE BACKTRACK 43 FIGURA 22 A ESTRUTURA DE UM WEBSITE SIMPLES asana ese ee ae ee ee ee ee ee see ee ee ee ee ee ee ee 46 FIGURA 23 RELACIONAMENTOS ENTRE AS TABELAS DO BD nssssnssnnennnnnnnn een 50 FIGURA 24 DIAGRAMA DE CLASSES DE ENTIDADE ee sesse ee ee ees see ee see ee ee ee ee ee see ee ee ee ee ee ee ee 51 FIGURA 25 DIAGRAMA DE CLASSES DE INTERFACE esse see sees sees ee ese ee ee ee ee ee ee ee ee ee ee ee ee ee 52 FIGURA 26 SITUA O COM APENAS 1 CAMINHO DE 5 LINKS ss sesse san oon onee sene
32. 67 92 13 94 11 Execu o 8 833 43 06 72 73 79 69 84 92 89 10 90 32 91 67 92 89 59 Execu o 9 8 33 50 00 68 94 80 21 86 90 89 42 90 86 91 90 93 29 Execuc o 10 16 67 50 00 74 24 81 25 85 71 89 74 90 59 91 44 92 28 Execu o 11 8 33 52 78 76 52 78 65 86 90 88 46 89 78 92 36 92 68 Execu o 12 8 33 48 61 72 73 85 42 84 92 88 46 89 52 92 82 91 67 Execu o 13 0 00 47 22 68 18 80 21 85 32 88 14 90 59 91 90 91 67 Execu o 14 8 33 50 00 68 94 80 21 86 90 89 42 90 86 91 90 93 29 Execu o 15 33 33 47 22 72 73 80 21 87 30 88 46 89 78 90 51 91 06 Execuc o 16 33 33 58 33 72 73 81 77 87 30 87 50 91 13 91 20 92 89 Execu o 17 25 00 56 94 75 00 81 25 87 70 90 71 91 13 91 90 92 68 Execuc o 18 8 33 54 17 71 21 79 17 87 30 90 38 90 32 90 51 92 68 Execuc o 19 0 00 44 44 73 48 80 21 87 30 89 42 91 40 90 28 93 09 Execuc o 20 8 33 41 67 75 76 79 69 86 51 89 10 89 52 91 90 92 07 Media 10 83 49 58 72 54 80 08 86 31 88 97 90 39 91 59 92 48 Desvio Padr o 10 15 5 16 2 46 2 01 1 16 0 82 0 85 0 63 0 81 11 3 4 An lise dos resultados Estas foram as m dias de throughput obtidas das tr s situa es
33. A conclus o que chegamos a seguinte No processo de busca de alimento da formiga real as formigas fazem o caminho de ida e volta entre o formigueiro e a fonte de alimento Uma mesma formiga pode executar v rias vezes a trajet ria entre o ninho e a fonte de alimento As formigas que otimizam o caminho das formigas que est o indo para a fonte de alimento s o as formigas que est o voltando e vice vesa isto que produz a avalia o implicita da solu o Esta caracter stica somada ao efeito autocatal tico faz com os caminhos mais curtos prevale am No caso do usu rio da internet isto n o ocorre Normalmente o usu rio come a sua navega o na home page do site navega at sua p gina destino e depois sai do site ou come a uma nova trajet ria at outra p gina destino 44 Ele n o costuma fazer caminhos de ida e volta entre a home page e a p gina destino Portanto observamos que apesar do modelo 1 poduzir um efeito autocatal tico como no comportamento das formigas ele n o 103 produz a avaliac o implicita da soluc o VI 2 Experimentos com o modelo 2 O modelo 2 na verdade um aperfeicoamento do modelo 1 sendo muito mais complexo que seu antecessor No modelo 2 a func o de determinar a p gina que se deve conduzir o usu rio desincorporada fazendo com que agora sua funcao seja apenas indicar o menor caminho para as p ginas que especificamos atrav s do goodness Se estabelecermos que o goodness a popularidade
34. DR ais REED ER EE E aaa 89 V 2 Banco de dados do AntWeb ia ina i ed ee 91 V 3 Os dois m dulos do Antweb asas RE HL 91 V 3 1 M dulo de atualiza o do ferom nio nn 92 V 3 2 M dulo de Adapta o de p gina nnn ana 94 Capitulo Mis Experimentos as das a sa 96 VI 1 Experimentos com o modelo 1 ia en See En br 96 VI 2 Experimentos com o modelo A ass a ee 108 V1 2 1 A diminui o de erros na trajet ria do usu rio nnee 103 V1 2 2 A indica o de caminhos mais curtos aanne onee nnnnnnennneen nennen 106 V1 2 3 Indica o de mais de uma p gina destino ennen 107 Capitulo VII Conclus o ies i a mannen nenn 111 MH Satisfa o dos obJelinGs is ni einen ae 111 VIL2 O que sobrou para fazer na implementa o nnen erneer 113 VILS As dificuldades durante a pesquisa nnn nennen eneen 113 VIL4 Conclus o sobre o experimento nn 114 VILS Recomenda es e trabalhos futurOS nnen nennen enen 115 VIL6 Publica es referentes a este trabalho nnen 116 Anexo A Algoritmos da implementa o de Webmining 118 BIOCESSO de Made neten a e E aT E E A E E EEE E 118 Preenchimento da tabela de backtracks iese ee ee ee ee RR Re 118 Extra o de informa es da tabela de backtracks nnn se ee ee ee ee ee ee 122 Abordagem somente 0 primeirO annen eneen Ee Ee ee ee ee ee ee ee ee 123 Abordagem do aprimoramento do beneficio nn 124 Anexo B Estrut
35. E TE EN E 6 p gina Servidor web sans Servidor web Usu rio modificada AntWeb pag CIC UnB 5 log 4 feromonio dos links ICH Servidor Banco de Dados Figura 40 Acesso a p gina com o AntWeb No caso espec fico desta implementa o do AntWeb os usu rios s o conduzidos usando a t cnica indica o direta A figura de uma formiga colocada logo frente do link que desejamos destacar Usando esta t cnica cada link da p gina poder ficar em um dos estados Destacado ou n o destacado Desta forma a influ ncia que podemos causar no usu rio discreta Esta t cnica foi escolhida por ser a t cnica que menos agride o layout da p gina e pode ser aplicada a quase todas as p ginas que utilizam HTML V 1 Componentes f sicos Em termos de componentes f sicos o AntWeb foi implementado na forma de tr s arquivos de c digo PHP e um arquivo com extens o ini listados abaixo index php pheromoneupdater php Classes php antweb ini O arquivo index php na verdade uma pagina metam rfica que pode se transformar em qualquer outra p gina da Web com as devidas adaptac es ou seja com os links destacados com a formiga se necess rio e os links redirecionados Esta p gina PHP possui o parametro URL que informa a URL da p gina no qual a 90 p gina index php vai se transformar Ao invocarmos por exemplo index php url http www cic unb br a p gina index se transforma
36. In D Corne M Dorigo and F Glover editors New Ideas in Optimization McGraw Hill 1999 11 32 27 M Dorigo e L M Gambardella Ant Colonies for the Traveling Salesman Problem BioSystems Also Tecnical Report TR IRIDIA 1996 3 IRIDIA Universit Libre de Bruxelles 1997 43 73 81 28 M Dorigo e L M Gambardella Ant Colony System A Cooperative Learning Approach to the Traveling Salesman Problem IEEE Transactions on Evolutionary Computation Also Tecnical Report TR IRIDIA 1996 5 IRIDIA Universite Libre de Bruxelles 1997 1 1 53 66 29 M Dorigo G Di Caro e L M Gambardella Ant Algorithms for Discrete Optimization Artificial Life Also available as Tech Rep IRIDIA 98 10 Universit Libre de Bruxelles Belgium 1999 5 2 137 172 30 M Dorigo V Maniezzo e A Colorni Positive Feedback as a Search Strategy Technical Report No 91 016 Politecnico di Milano Italy 1991 31 M Dorigo V Maniezzo e A Colorni The Ant System An Autocatalytic Optimizing Process Technical Report No 91 016 Revised Politecnico di Milano Italy 1991 32 M Dorigo V Maniezzo e A Colorni The Ant System Optimization by a 219 Colony of Cooperating Agents IEEE Transactions on Systems Man and Cybernetics Part B 1996 26 1 29 41 33 M Dorigo Optimization Learning and Natural Algorithms Ph D Thesis Dipartimento di Elettronica Politecnico di Milano Italy in Italian 1992 34 M Heusse S Gu rin D S
37. Para cada registro da partic o Faca Inicio m n mero de valores preenchidos de Localiza aoEsperadal a N Para j de 1 ate m Fa a Inicio Seja P i o item correspondente a P gina Ej P i Peso P i Peso m1 j Fim Fim P gina O item de P com maior Peso Se Peso P gina gt S Ent o Inicio Adicione lt P gina Peso P gina gt a lista R lista de P ginas recomendas Para cada registro Faca Inicio Para k de 1 ate n Faca Inicio Se Valor Ek P Atribua nulo a Ek Ek 1 En Fim Fim Inicialize a lista P com Peso 0 Fim Ate Peso P gina lt S O algoritmo semelhante ao algoritmo do Aprimoramento do beneficio 128 mudando apenas na forma como as p ginas s o ponderadas por isso as explicac es de como o algoritmo trabalha se restringir o a forma como ele pondera as p ginas em P O m todo pondera as p ginas da seguinte forma Seja m a posic o da ltima localizac o esperada preenchida e j a posic o da localizac o esperada em quest o O peso dado por ValorDelncremento m j 1 Equa o 21 Dessa forma se a p gina em quest o a ltima do registro seu peso ser 1 se for a primeira seu peso ser m seguindo a defini o da abordagem na qual as primeiras p ginas do registro devem possuir um peso maior que as ltimas Assim no momento em que o algoritmo estiver percorrendo os registros da parti o e os atributos de cada regi
38. QueryDropUpdatesAux queryDropUrlsAux new QueryDropUrlsAux queryFirstLog new QueryFirstLog queryInsertUpdate new QuerylnsertUpdate querylnsertUpdates new QueryInsertUpdates queryInsertUrls new QuervinsertUris queryLastUpdate new QueryLastUpdate decoratorBuilder gt setNext pheromoneUpdater decoratorBuilder gt setNext dissolver decoratorBuilder gt setNext flushCloser decoratorBuilder gt setNext intervalMaker intervalMaker gt setLastUpdate lastUpdateExtractor lastUpdateExtractor gt setQueryFirstLog queryFirstLog lastUpdateExtractor gt setQueryLastUpdate queryLastUpdate pheromonelpdater setlntervalSetter intervalSetter pheromoneUpdater gt setQueriesPheromoneUpdater queriesPheromoneUpdater intervalSetter gt pushQuery query AdditionCalculator intervalSetter gt pushQuery queryInsertUpdate 157 intervalSetter gt pushQuery queryInsertUrls queriesPheromoneUpdater gt pushQuery queryInsertUpdate queriesPheromoneUpdater gt pushQuery queryDecayPheromone queriesPheromoneUpdater gt pushQuery queryInsertUrls queriesPheromoneUpdater gt pushQuery queryAdditionCalculator queriesPheromoneUpdater gt pushQuery queryCreateUrlsAux queriesPheromoneUpdater gt pushQuery queryAddAdditions queriesPheromoneUpdater gt pushQuery queryDeleteUrls queriesPheromoneUpdater gt pushQuery queryDropUrlsAux queriesPheromoneUpdater gt pushQuery
39. Traveling Salesman Problem Proceedings of ML 95 Twelfth International Conference on Machine Learning Tahoe City CA A Prieditis and S Russell Eds Morgan Kaufmann 1995 252 260 20 L M Gambardella e M Dorigo HAS SOP An hybrid ant system for the sequential ordering problem Technical Report 11 97 IDSIA Lugano CH 1997 21 L M Gambardella e M Dorigo Solving Symmetric and Asymmetric TSPs by Ant Colonies Proceedings of IEEE Intenational Conference on Evolutionary Computation IEEE EC 96 IC 18 IEEE EC96 Nagoya Japan 1996 622 627 22 L M Gambardella E D Taillard e G Agazzi Macs vrptw A multiple ant colony system for vehicle routing problems with time windows In D Corne M Dorigo and F Glover editors New Methods in Optimisation McGraw Hill 1999 23 L M Gambardella E D Taillard e M Dorigo Ant colonies for the QAP Technical Report 4 97 IDSIA Lugano Switzerland 1997 24 L M Gambardella E D Taillard e M Dorigo Ant colonies for the QAP 218 Journal of the Operational Research Society JORS 1999 50 2 167 176 25 L Weigang M V P Dib W M Teles V M de Andrade A C M Alves de Melo J T Cariolano Using ants behavior based simulation model AntWeb to improve website organization in Proc SPIE s Aerospace Defense Sensing and Controls Symposium Data Mining Orlando USA 4730 2002 26 M Dorigo e G Di Caro The Ant Colony Optimization Meta Heuristic
40. caminhos de forma alternada para simular 50 de usu rios em cada caminho caso contr rio foi seguido a orienta o do sistema Como o link Corpo Docente leva a um caminho mais curto era esperado que o sistema indicasse este link Mas o que se observou foi que o sistema indicou o link P s Gradua o A explica o que encotramos para isto foi que como o link P s Gradua o foi usado primeiro no momento em que ocorreu a primeira atualiza o depois que iniciamos as navega es a p gina no 101 qual o link P s Gradua o levava tinha um acesso a mais que a p gina corpo docente E com o efeito autocatal tico tornou se imposs vel que o link Corpo Docente se tornasse destacado Portanto apesar do nosso esfor o em reproduzir o comportamento das formigas o modelo 1 sempre favorece o caminho mais utilizado independente do qu o melhor o caminho Tabela 10 Bateria de navega es com o modelo 1 Link destacado Rota escolhida Corpo Docente P s Gradua o P s Gradua o Corpo Docente P s Gradua o P s Gradua o P s Gradua o P s Gradua o P s Gradua o P s Gradua o P s Gradua o P s Gradua o P s Gradua o P s Gradua o P s Gradua o P s Gradua o P s Gradua o P s Gradua o Xixi DS x x XI XI XI XI XI XI XI XI x Pos Graduac o Pos
41. cidade cada formiga possui uma lista de todas as cidades j visitadas cnamada lista tabu A cada itera o cada uma das m formigas realiza uma transi o entre as cidades Ap s n itera es todas as formigas ter o visitado todas as cidades e ter o completado um ciclo Completado o ciclo as trilhas de ferom nio s o atualizadas conforme ser detalhado mais adiante e cada formiga esvazia sua lista tabu Um novo ciclo ent o iniciado A quantidade de formigas e o n mero m ximo de ciclos s o par metros do sistema Sejam e j duas cidades do grafo O comprimento da aresta i j representado por di A probabilidade da k sima formiga na cidade i escolher mover se para a cidade j dada pela seguinte f rmula 22 le t Di Im lf Pi 1 gt c OF A r ke permitidos se je permitidos 0 emoutro caso Equac o 3 Onde ti t a quantidade de ferom nio na aresta i j no momento t e ni a visibilidade da aresta dada por nij 1 dj Os par metros a e B determinam a participac o relativa da quantidade de ferom nio e da visibilidade na tomada da decis o O conjunto permitidos formado por todas as cidades que n o pertencem a lista tabu da formiga A atualiza o do ferom nio feita com base na seguinte f rmula vilten 1 0 vijlt Ati Equa o 4 Onde t t n a quantidade de ferom nio na aresta i j passadas n itera es a partir do tempo t p o coeficiente de ev
42. combinatorial optimization problems In S VoB S Martello I H Osman and C Roucairol editors Meta Heuristics Advances and Trends in Local Search Paradigms for Optimization Kluwer Boston 1998 137 154 50 T St tze e H Hoos The MAX MIN Ant System and local Search for Combinatorial Optimization Problems Towards Adaptive Tools for Global Optimization 2nd Metaheuristics International Conference MIC 97 Sophia Antipolis France 1997 21 24 51 T White B Pagurek e F Oppacher Connection management using adaptive mobile agents In H R Arabnia editor Proceedings of the International Conference on Parallel and Distributed Processing Techniques and Applications PDPTA 98 CSREA Press 1998 802 809 52 U Eco Como se faz uma Tese 12 ed S o Paulo SP Editora Perspectiva 1995 53 V Bush As We May Think Atlantic Monthly 176 1 1945 101 108 54 V Maniezzo e A Colorni The ant system applied to the guadratic assinment problem IEEE Trans Knowledge and Data Engineering in press 1999 55 V Maniezzo A Colorni e M dorigo The ant system applied to the quadratic assignment problem Technical Report IRIDIA 94 98 Universit Libre de Bruxelles Belgium 1994 56 V Maniezzo Exact and approximate nondeterministic tree search procedures for the quadratic assignment problem Technical Report CSR 98 1 C L In 222 Scienze dell Informazione Universita di Bologna sede de Cesena Italy
43. como o coeficiente de evapora o e o tempo de itera o UpdateRecorder respons vel por gravar na tabela Updates os dados correspondentes de cada atualiza o feita QueryManager respons vel por gerenciar as transa es feitas no banco de dados MySalConection respons vel por gerenciar a conex o entre a aplica o e o servidor de banco de dados 94 V 3 2 M dulo de Adaptac o de pagina next D getOut gt Decorator TagsExtractor J gt EE E setNext next DecoratorEnd lens ll A ac idea sendWholePageO LinksExtractor InternalLinksProcessor PageLoader getOut String getOut String getOut String setUrl url String PheromoneSetter LinksGuider LinksHighlighter getOut String getOut String selector LinksSelectr getOut Array url String oe Uri ud String get String recordQ Boolean MySqlConnection handleQ connection Int mySqlHost String QueryManager userName String password String run query String Boolean dataBaseName String Configuration openQ Boolean iniFile String get0 loadQ oloseO Configuration iniFile String Configuratipn setHost host String data data setDBName dbn String setP asaword p String setUserName u String Figura 42 Diagrama de Classe do modulo de adaptac o da pagina A Figura 42 mostra o diag
44. compartimentos No primeiro compartimento de cima para 51 baixo foi colocado o nome da classe no segundo foram listados os atributos e no compartimento inferior foram listados os m todos Colonia from AntWeb Principal Website 7 A from AntWeb from AntWeb Ebintervalo int l i ai RPP rincipall gegetPagina MrFormigas Ym ain GPegetNumPaginas Ebwebsite T FesetHomePagel Ebnamez Ni Ps etObjetivo ControladorColonia eoetHomePagel PPColonia from AntWeb 2 getObjetivo PegeraFormiga M tempo int 7 RachePagina GMpassaTempol x g addPaginal MtotE ncontraram MControladorColonia g addP aginal PatualizaFeromonio Ps etTelaPrincipal WadaLink PgetNumFormigas WexecutaSimulacao PW ebsite iMgetFormigal PegravaResultados l N paal EPrpad p mostraCaminhoColonia Link Parametros PsetArquivoSaida from AntWeb from AntWeb AN Bsferomonio double alfa double ye F Ebbeta double Fomiga G LINkI ro double BPP arametros res etP aram PsetAlfa Egetalfa setBeta from AntWeb delay int alfa double beta double aleatorio double atualizou boolean PegetFeromonio MatualizaFeromonio Roget Proxima PoetBeta gerormigal Pagina setRo Wencontrour l from AntWeb PegetR
45. de execu o em mem ria facilitando recursos de m quina e tempo de leitura e compara es A estrutura do site listada no Anexo A Foram feitas 3 baterias de teste com as tr s situa es descritas a seguir Situa o 1 A estrutura original do website A p gina alvo situa se a 5 links de profundidade a partir da homepage Situa o 2 A mesma estrutura da situa o 1 com um link a mais na p gina http intranet menus menu relacao equipamentos quadro total htm apontando para a p gina objetivo Com este acr scimo surge um caminho alternativo para que a formiga alcan ar seu objetivo diminuindo a dist ncia para 4 links Situagao3 A estrutura original com um link a mais na p gina http intranet menus menu relacao equipamentos quadro resumo htm apontando para a p gina objetivo fornecendo um caminho alternativo para a formiga com apenas 2 links de dist ncia O objetivo do experimento foi estimar o benef cio de altera es feitas no website Em todas as situa es foi utilizada a p gina http intranet recursos tecnologicos relacao equipamentos gerencia filial quadro g eral m quinas htm como p gina objetivo O intervalo de gera o de formigas foi 5 segundos Todos os links receberam uma taxa inicial de ferom nio igual a 1 A taxa de evapora o de ferom nio configurada como 0 5 e os par metros Alfa e Beta foram configurados como 1 e 5 respectivamente Para cada uma das situa es descritas foram realiz
46. de ferom nio associada Fim Este algoritmo ser executado a cada unidade de tempo determinado A forma como a instru o Obtenha dados para calcular ferom nio ser executada poder ser percorrendo log do servidor e obtendo as informa es necess rias atrav s deste ou atrav s de algum sistema de captura de clicks na p gina que o 75 usu rio vai receber IV 6 3 2 Abordagem do destaque proporcional Esta abordagem semelhante a abordagem anterior diferenciando se apenas no fato que ao inv s de ser mostrado a quantidade exata de ferom nio em cada link ser feito um destaque relativo a quantidade de ferom nio contido em cada link como na Figura 33 Neste exemplo foi usado o tamanho do link para simular a quantidade de ferom nio mas poderia ser usado outro m todo como a espessura do tra o da fonte ou a tonalidade da cor usada no link Esta abordagem possui a desvantagem de alterar o projeto visual da p gina Por outro lado tem a vantagem do usu rio n o ter que entender necessariamente o significado dos valores apresentados pelo o sistema formiga como na primeira abordagem Xi Esta uma lista hier rquica det fel x File Edit view Go Communicator Help EET Stead Bookmarks Location GE What s Related a D ss HP a Figura 33 Abordagem do destaque proporcional O algoritmo desta abordagem muito semelhante ao da abordagem anterior diferenciando apenas no fat
47. de preenchimento da tabela de backtrack Depois de preenchida a tabela de backtracks realizado o processo de extrac o de informac es da tabela de backtracks Este o processo que obt m as informac es teis para reestruturac o do site Este processo usa a tabela de backtracks e dependendo da abordagem escolhida outras informac es como o beneficio de visitas do site informar localizac es recomenda das localizac es partic o de recomendadas p ginas objetivo Administrador tabela de backtracks Web Figura 21 Processo de extrac o de informac es da tabela de backtrack O algoritmos usado nas duas etapas descritas nesta sec o est o descritos em detalhe no Anexo A 44 11 2 Modelo AntWeb para avalia o de estruturas Este trabalho desenvolvido por Li Weigang e sua equipe na Universidade de Brasilia 25 consistia na mensurac o de estruturas de website usando os principios do algoritmo formiga desenvolvido por Marco Dorigo O trabalho comecou da observac o de que muitos websites perdiam visitantes por n o ter uma estrutura eficiente Na Politec Inform tica Ltd foi pedido a 12 analistas para abrirem contas em dois bancos conhecidos no Brasil que chamaremos de banco A e banco B Em media os usu rios levaram 22 segundos para concluir a tarefa no banco A passou por 3 p ginas para chegar no formul rio apropriado enquanto no banco B a m dia foi de 106 segundos A raz o para o sucesso do banco A f
48. determinar a escolha da formiga A Tabela 13 mostra os acr scimos de ferom nio feitos em cada p gina em rela o ao tempo As linhas representam as p ginas e as colunas os intervalos 1A 0 3 0 7 2A 2B 2C N A N 3A 3B 5 6 9 10 KA KA Page 9 a p gina objetivo 2 4 Figura 45 Site estruturado em rvore Tabela 12 Simulac o com uma estrutura em arvore 105 At 5 sec Time 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 t 1 2 3 4 ss 6 7 8 9 10 11 12 13 14 15 16 Alt 0 13 2A 3A 3B 2C A 2 t 0 39 2C A 3 t 0 43 20 A 4 t 0 45 2C A 5 t 0 09 2A 3A 3B 2C A 6 t 0 21 2A 3A 3B 2C A 7 t 0 34 20 A 8 t 0 47 2C A 9 t 0 09 2A 3A 3B 2C A 10 t 0 46 2C A 11 t 0 18 2A 3A 3B 2C A 12 t 0 82 20 A 13 t 0 20 2A 3A 3B A 14 t 0 077 2A 3A A 15 t 0 56 2C A 16 t 0 88 Tabela 13 Ferom nios adicionados 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 t 1 3 ds NG 7 Be ee AO ie AS 14 15 16 1A 2A 0 2 0 2 0 2 0 2 0 2 2C 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 0 5 3A 0 25 0 25 0 25 0 25 0 25 3B 0 33 0 33 0 33 0 33 0 33 9 1 1 1 1 1 1 1 1 1 1 1 1 Os dois l
49. e modelo 2 O modelo 1 foi implementado e testado no website do Departamento de Ci ncias da Computa o da UnB Com o modelo 2 foram feitas simula es que mostraram de forma otimista que o modelo 2 pode auxiliar o usu rio da Web O objetivo deste trabalho relatar as pesquisas feitas com o AntWeb Palavras chaves Sistema formiga Web Mining Hiperm dia Adaptativa Web Inteligente xili ABSTRACT The ant behavior can be used as a metaphor to improve web systems performance The present Internet browse tools embody user that can be assumed as ants foraging process But different from the ants Internet users dont have pheromone for a cooperative help Based in this observation and because of lack of research work that has as objective to guide web user through optimized routes this research was developed In this research we present AntWeb This research was divided in two different application of AntWeb The AntWeb for evaluation of websites and the adaptive AntWeb In relation to the AntWeb for evaluation of websites an evaluation methodology was developed and implemented In this case the input is the structure of a website and as output a measure of performance of the structure is computed In relation to the adaptive AntWeb two heuristic models had been developed to guide the web user in a context of adaptive hypermedia that we named model 1 and model 2 Model 1 was implemented and tested in UnB Department of Computer Sciences w
50. ele encontrar com certeza a sua p gina Mas e no caso de existirem duas ou mais p ginas que satisfa am o desejo do usu rio Nesse caso podemos permitir que essas duas ou mais p ginas exalem seu cheiro simultaneamente Dessa forma como todas as p ginas possuem 82 o mesmo cheiro ganhar a prefer ncia do usu rio a p gina que estiver a uma dist ncia mais curta lembrando que quando mais um objeto est pr ximo de n s mas podemos sentir seu cheiro A Equa o 19 expressa a situa o em que o usu rio possa ter interesse em mais de um destino Neste caso a probabilidade expressa por gt lai p g D VdeD mS Tal p er VdeD VIeN Equac o 19 Onde D o conjunto de p ginas destino que desejamos levar o usu rio e 9 um coeficiente que indica a import ncia da pagina d para o interesse do usu rio Quanto maior o valor de g maior o cheiro que esta p gina exalar em rela o a outras p ginas Observe que se existir apenas um destino d no conjunto D e g for diferente de zero a Equa o 19 se comportar como a Equa o 16 IV 7 4 Identificando a p gina destino do usu rio Para identifica o da p gina destino correspondente a cada navega o ocorrida usando o AntWeb foram usados os mesmos m todos descritos em 44 Existem dois m todos que s o utilizados em conjunto A p gina uma p gina de conte do Em Alguns sites existe uma clara separa o entre p gina ndice e p gina conte d
51. explorando centrais com capacidade ociosa reduzindo assim a perda de chamadas Encontrar o caminho mais curto entre a origem e o destino de uma chamada pode ajudar a reduzir o n mero de nodos envolvidos na liga o por m nem sempre a melhor abordagem para o balanceamento uma vez que pode haver um n mero excessivo de chamadas envolvendo o mesmo caminho m nimo Controlar sistemas distribu dos por meio de um nico controlador central tem v rias desvantagens Uma delas que os nodos precisam constantemente enviar informa es central a respeito de sua carga aumentando ainda mais o fluxo na rede e reduzindo a escalabilidade do sistema Outro problema inerente ao controle centralizado baixa toler ncia falhas no caso de falha no controlador central todo o sistema fica inoperante Dessa forma a natureza desses sistemas distribu dos altamente din mica complexa e estoc stica e seu comportamento 24 n o pode ser previsto ou explicado reduzindo a a um unico fator central control vel A solu o pode estar em um bom sistema descentralizado Uma abordagem baseada em algoritmos formiga completamente distribu da e altamente adapt vel a mudan as na rede ou em seus padr es de tr fego Essa solu o faz uso de capacidade de processamento distribu do j inerentemente presentes na rede na forma dos nodos A natureza distribu da dessa abordagem pode tornar o sistema muito robusto contra falhas de entidades de cont
52. fosse uma vari vel global do programa Neste m todo a ponderac o para que uma localizac o esperada seja ou n o recomendada ser o beneficio O algoritmo que implementa esta abordagem amp descrito a seguir AprimoramentoBeneficio S R Inicio Crie a lista P da estrutura P gina Peso Coloque em P todas as p ginas indice de Tabela de P ginas com Peso 0 Repita Para cada registro da partic o Faca Inicio m n mero de valores preenchidos de Localiza aoEsperadal a N Para j de 1 ate m Fa a Inicio a Seja P i o item correspondente a P gina Ej oo x Us Localiza aoEsperada j P i Peso Pl i Peso BI 1 Fim Fim P gina O item de P com maior Peso Se Peso P gina gt S Ent o Inicio Adicione lt P gina Peso P gina gt a lista R lista de P ginas recomendas Para cada registro Faca Inicio Para k de 1 ate n Faca Inicio Se Valor Ek P Atribua nulo a Ek Ek 1 En Fim Fim Inicialize a lista P com Peso 0 Fim Ate Peso P gina lt S Este algoritmo implementa o m todo guloso para encontrar a melhor localiza o esperada para p gina Este m todo pondera as poss veis localiza es esperadas da seguinte forma Cada vez que uma p gina aparece no atributo 126 Localizac oEsperadaK em algum registro da parti o seu peso incrementado com o valor de B K que o benef cio da K zima tentativa Inicial
53. gina 2A ele vai encontrar as probabilidades pP3ar 1 e pPPaa2 0 Isto se deve ao fato que a pagina 1 est dentro do conjunto de p ginas destinos que estamos procurando enquanto a p gina 2 n o 111 CAP TULO VII CONCLUS O Todos os seres humanos tem como miss o melhorar um pouco o mundo em que vivemos Cada um na sua rea de atua o O m dico atendendo os enfermos os engenheiros civis projetando casas o professor ensinando e os pesquisadores talvez tenham a fun o mais estrat gica neste cen rio que gerar conhecimento para que todas as outras fun es possam ser realizadas Hoje milhares de pesquisadores no mundo nas mais diversas reas est o lutando nas universidades para fazer desse mundo um mundo melhor para as pessoas viverem De repente dentro deste mesmo mundo surge um mundo paralelo que a World Wide Web Tornou se um mundo alternativo para as pessoas se encontrarem fazerem compras aprimorarem conhecimentos montarem seus neg cios se divertirem entre outros E a miss o de todos n s cientistas da Computa o seja da rea de Web hiperm dia adaptativa intelig ncia artificial e reas afins fazer desse mundo virtual um mundo melhor para as pessoas viverem E quanto mais a Internet se infiltra em outros setores da sociedade quanto mais a Web cresce mais nossa miss o se torna importante E esse mundo que cresce a cada dia que passa e cada vez mais vai adquirindo dimens es infinitas Assim espera
54. lemptv urif scheme l url scheme user amp pass if empty url user uri url user url pass host uri url host port port empty url port url port uri port path uri url path fragment or query if isset url fragment gt lt PHP class BuilderWithCache 153 uri url fragment elseif isset url query uri 7 urif querv return uri var adaptabilityChecker var conection new mySdlConection var configuration new Configuration var htmlParser var linksSelector new CacheLinksSelector var url new Url function buildHtmlParser amp antWeb cache new Cachel decoratorBuilder new DecoratorBuilder elementExtractor new ElementExtractor exceptionProcessor new ExceptionProcessor extractingNonTag new ExtractingNonTag extractingTag new ExtractingTag internalUrlsProcessor new InternalUrlsProcessor pageLoader new PageLoader returnKeeper new ReturnKeeper stringDecomposer new StringDecomposer wrapper new Wrapper 154 decoratorBuilder gt setNext cache decoratorBuilder gt setNext internalUrlsProcessor decoratorBuilder gt setNext exceptionProcessor decoratorBuilder gt setNext wrapper decoratorBuilde
55. m ltiplos agentes para otimiza o de problemas combinat rios dif ceis como por exemplo o problema do caixeiro viajante TSP Existem no mundo algumas pesquisas em andamento para a resolu o de problemas dif ceis de otimiza o usando o sistema formiga 29 O AntWeb pertence a este grupo de aplica es O algoritmo formiga foi inspirado na observa o de formigas reais e se baseia principalmente na forma como a formiga procura seu alimento As formigas s o insetos sociais que cooperam entre si para manter a sobreviv ncia da col nia Seu comportamento dirigido de forma que a sobreviv ncia da col nia mais importante do que a sobreviv ncia de um nico indiv duo 29 O principal fato observado no comportamento das formigas reais que inspirou os sistemas formiga foi a capacidade de encontrar o menor caminho entre a fonte de alimento e o seu ninho A formiga tem a capacidade de enxergar mas sua vis o possui um alcance muito curto sendo a formiga capaz de ver apenas a uma dist ncia muito pequena Assim imposs vel para as formigas encontrarem o menor caminho entre seu ninho e a fonte de alimento usando somente sua vis o Mas apesar desta limita o a formiga capaz de encontrar o menor caminho usando outros meios e de forma muito eficiente garantido assim a sobreviv ncia da col nia Para isto a formiga utiliza um horm nio arom tico chamado ferom nio Quando a formiga caminha entre a fonte de alimento e o seu
56. mais de um destino vamos considerar duas situa es descritas a seguir VI 2 3 1 Situa o 1 Nesta situa o o conjunto de p ginas destino ser D 1 2 com g 1 e g 2 Nessas condi es quando o usu rio estiver em 1A teremos as probabilidades pPsaza 1e pla 2e O Isto quer dizer que seguir o link para a p gina 2A far com que encontremos mais r pido nossos destinos o que condiz com a estrutura do site mostrada em Figura 47 uma vez que todos os nossos destinos do conjunto D se 110 encontram abaixo da p gina 2A Quando o usu rio estiver na p gina 3A os valores que dever o ser considerados ser o p sa1 0 35 e p saz 0 65 A indica o condiz com nossos par metros iniciais pois estabelecemos um g maior do que o g VI 2 3 2 Situa o 2 Nesta outra situa o o conjunto de p ginas destino ser D 1 3 com g 1 e g 1 Dessa forma como as duas p ginas possuem goodness iguais o sistema indicar a p gina que estiver mais pr xima Nessas condi es quando o usuario estiver em 1A teremos as probabilidades pP a aas 0 4 e pia 2e 0 6 O fato da probabilidade de 2B ser maior significa que indo para l encontraremos umas das p ginas que estamos procurando de forma mais r pido Mas a probabilidade de 2A n o t o baixa em rela o de 2B que reflete o fato de que o link para 2B tamb m leva a alguma p gina que estamos procurando apesar do caminho ser mais longo Se o usu rio for para a p
57. materiais escolares e passar por outras sess es relacionadas Neste caminho voc v l pis a venda e se lembra que tamb m precisa de l pis e acaba comprando Se voc tivesse ligado para o supermercado e comprado a caneta com entrega a domicilio voc teria sua caneta da mesma forma mas nunca ia se lembrar que estava precisando de l pis dessa forma que o usu rio perde com os sistemas de busca Esses sistemas levam o usu rio diretamente para a p gina que contem aquela palavra mas o usu rio n o toma conhecimento de outras p ginas que estavam pr ximas no hiperespa o IV 7 1 A representa o do ferom nio no modelo 2 No modelo 2 diferente do modelo 1 v rias taxas de ferom nio est o associadas a uma p gina Nesta abordagem as indica es heur sticas para os destinos que uma p gina pode levar est o separadas em taxas diferentes Para cada destino que poss vel atingir a partir de uma p gina existe uma taxa de ferom nio Essa abordagem possu a a desvantagem do grande n mero de taxas de ferom nio Por exemplo se nos limitarmos a representar as taxas de ferom nio somente para um site em que poss vel chegar a qualquer p gina a partir de qualquer outra p gina deste site a quantidade de taxas de ferom nio a representar seria o quadrado do n mero de p ginas existente neste site Para amenizar este 79 problema em uma possivel implementac o do modelo 2 as taxas com valores iguais a zero que ser o maioria
58. nio e a heur stica 7 1 wij uma heur stica relacionada ao custo de usar a p gina j wt o tempo estimado na p gina j que calculado conforme a Equa o 15 mostrada abaixo wi It Vt Equac o 15 Onde It o tempo estimado para obter a pagina j atrav s do browser vi o tempo que o usu rio levar para visitar a p gina Os valores para a e f s o determinados empiricamente n o existindo ainda nenhum m todo objetivo para determina los Esta caracter stica de ponderar o ferom nio e o custo de mover se para o nodo vizinho uma das otimiza es propostas pelo AntSystem de Marco Dorigo 29 Recomendamos a 1 e 5 0 para a maioria dos casos Em site cujas p ginas ndices s o muito heterog neas em rela o a quantidade de conte do e custo de download remendamos um valor maior para A Equa o 16 mostra como feito o c lculo da probabilidade na qual uma formiga escolhe ir da p gina i para a p gina je N PR p l a p VIeN Equac o 16 Podemos perceber que no modelo 2 a atualizac o do ferom nio ocorre de forma distinta do modelo 1 No modelo 1 a atualizac o era feita periodicamente em intervalos uniformes No modelo 2 a atualizac o ocorre todas as vezes em que uma formiga termina um trajeto at a sua pagina destino Dessa forma diferente do modelo 1 n o o fator tempo que far com que o ferom nio diminua e sim o uso de outras p ginas para chegar at determinado destino A Equac o 17
59. nome recursos humanos area recrumento selecao htm http intranet recursos humanos pessoal telefones pessoal telefone nome recursos humanos area treinamento htm http intranet recursos humanos pessoal telefones pessoal telefone nome recursos humanos departamento pessoal htm http intranet recursos humanos pessoal telefones pessoal telefone nome recursos humanos medicina trabalho htm http intranet recursos humanos pessoal telefones pessoal telefone nome area tecnica area tecnica htm http intranet recursos humanos pessoal telefones pessoal telefone nome area tecnica atendimento usuario htm http intranet recursos humanos pessoal telefones pessoal telefone nome area tecnica consultoria htm http intranet recursos humanos pessoal telefones pessoal telefone nome area tecnica desenvolvimento htm http intranet recursos humanos pessoal telefones pessoal telefone nome area tecnica linha producao htm http intranet recursos humanos pessoal telefones pessoal telefone nome area tecnica suporte htm http intranet recursos humanos pessoal telefones pessoal telefone nome fabrica software htm http intranet recursos humanos pessoal telefones pessoal telefone nome coordenadores contrato htm http intranet menus menu pessoal telefones cargo htm http intranet recursos humanos pessoal telefones pessoal telefone cargo gerencia operacional htm http intranet recursos_humanos pessoal_telefones pessoal_tel
60. o menor caminho para o usu rio usando sua pr pria navega o para o processo de aprendizagem Este novo sistema tem como caracter stica a extensabilidade que permite que ele seja incorporado com outros sistemas de navega o adaptativa j existente 1 5 Organiza o do trabalho Acabamos de apresentar uma vis o geral sobre o trabalho desenvolvido abrangendo objetivos motiva o e seu relacionamentos com outros trabalhos No Cap tulo II descrevemos os fundamentos do nosso trabalho ou seja a meta heur stica da formiga que serviu de base para o desenvolvimento do AntWeb uma vis o geral sobre a World Wide Web Web a tecnologia de hipertexto e hiperm dia bem como as t cnicas de hiperm dia adaptativa que foram utilizadas como solu o para o ferom nio atrair o usu rio No Cap tulo Ill apresentamos o sistema AntWeb para avalia o de estruturas de websites que o relacionado ao AntWeb adaptativo Neste cap tulo descrito o algoritmo os experimentos que precederam surgimento deste e os experimentos que serviram para valida o O AntWeb adaptativo apresentado no Cap tulo IV podendo ser considerado o principal cap tulo deste trabalho pois concentra nossa contribui o cient fica A implementa o do primeiro modelo da heur stica do AntWeb no aspecto adaptativo descrita no Cap tulo V atrav s da descri o da escolha da plataforma o Banco de Dados do sistema e os dois modulos b sicos de atualiza o do
61. o sistema pedir nenhuma informa o ao usu rio Mas se for definido que o goodness o n mero de palavras em comum que uma p gina tem em rela o a uma query que o usu rio digitou o usu rio ter que entender que os links que est o sendo indicados para ele s o os links que levam s p ginas que contem as palavras informadas por ele 78 Em suma o objetivo do modelo 2 do AntWeb adaptativo levar o usu rio as p ginas que desejamos sem fornecer o link direto para a pagina Ao inv s disso conduzimos ele pelos links j existentes na estrutura da Web Um exemplo de aplica o disso seria qualquer sistema de busca na Internet tipo o Yahoo onde o usu rio poderia digitar as palavras de t picos que est procurando e ent o poderia se considerar a heur stica por exemplo que quanto mais palavras uma p gina tiver em comum com o conjunto de palavras que o usu rio digitou melhor seria esta p gina para o usu rio Dessa forma poderia usar o AntWeb para conduzir o usu rio pelos links para ele chegar at sua p gina de interesse Presumimos que isto seja mais interessante do que os sistemas tradicionais de busca fazem quando criam um link direto para as p ginas que contem as palavras que o usu rio digitou pois assim o usu rio perde a oportunidade de passar por muitas p ginas que talvez lhe interessassem como se voc fosse para o supermercado comprar uma caneta Para chegar at essa caneta voc tem que ir para a sess o de
62. os recursos que dispomos IV 3 Como associar o ferom nio Durante nosso estudo do AntWeb tivemos que optar pela forma de associar o ferom nio estrutura do site Haviam tr s possibilidades Associar o ferom nio ao link haveria uma taxa de ferom nio para cada link no site Associar o ferom nio a transic o como nos demais sistemas que usam a meta heuristica da formiga se existir um ou mais links entre as p ginas P1 e P2 seria armazenado uma nica taxa de ferom nio para o par lt P1 P2 gt para indicar a presenca de algum link entre as duas p ginas independente da quantidade de links Associar o ferom nio p gina Para esta opc o levou se em conta alguns fatores como o custo de armazenamento o custo de manutenc o das taxas de ferom nio o custo do aprendizado e a efici ncia na representac o do aprendizado obtido Ap s a analise destas tr s possibilidades foi decidido associar o ferom nio p gina pois o objeto de procura do usu rio sempre a p gina e n o o link Assim fizemos com que os objetos procurados as p ginas exalassem cheiros e n o o acesso at elas Outros fatores que levaram a escolha da p gina s o listados abaixo A escolha das duas primeiras abordagens tornaria poss vel o surgimento de situa es incoerentes como a indica o diferenciada pelas taxas de ferom nio para caminhos que possuem custo equivalente Por exemplo considere a estrutura do site da Figura 29 Suponha que exi
63. p 189 function setParserHtml amp p this gt parserHtml amp p function setLinksSelector amp p this gt linksSelector amp p function setUrl amp p this gt url amp p function setConfiguration amp p this gt configuration amp p function generateFieldsValues datetime date Y m d His if datetime this gt fields dateTime this gt values datetime if isset _SERVER REMOTE_ADDR ip SERVER REMOTE ADDR this gt fields ip this gt values Sip if url this gt url gt get this gt fields url 190 this gt values url if isset SERVER HTTP_HOST host _SERVER HTTP_HOST this gt fields host this gt values host if max_links_to_show this gt configuration gt data max links to show this gt fields maxLinksToShow this gt values max_links_to_show if numberLinks this gt linksSelector gt getNumberOfLinksOnPage this gt fields numberLinks this gt values numberLinks if threshold this gt configuration gt data threshold this gt fields threshold this gt values threshold if this gt adaptability Checker gt isAdaptable this gt fields isAdaptable this gt values 1 ind 1 selections this gt linksSelector gt getOut reset selections while
64. podem ser omitidas do banco de dados Dessa forma quando n o existir uma taxa de ferom nio em uma p gina para determinado destino no Banco de Dados presume se que esta taxa possui o valor zero A representa o do ferom nio no modelo 2 feita da seguinte forma Tas Onde p a p gina em que est situada a taxa de ferom nio e d o destino no qual a taxa se refere IV 7 2 Modelo 2 b sico No modelo 2 pif expressa o quanto a escolha da p gina j boa quando o usu rio est na p gina ie ele est procurando a p gina d A Equa o 13 mostra a restri o que deve ser aplicada a pi Zpil 1 jeN Equac o 13 Onde i amp a p gina em que o usu rio est d a p gina destino que desejamos levar o usu rio j p gina vizinha a candidata a ser a escolhida pelo o usu rio para chegar a d N o conjunto dos vizinhos da p gina i Para que seja feito o c lculo de pi utilizada uma tabela de roteamento localizada na p gina em que o usu rio est Cada p gina do site ter sua pr pria tabela de roteamento Esta tabela din mica e pode mudar a cada iterac o Os valores desta tabela s o calculados conforme a Equa o 14 Mi c p m VjeN Ta Vle N Equac o 14 Onde af p corresponde aos valores da tabela de roteamento na itera o 80 D 77 p a quantidade de ferom nio na pagina j na itera o p ae 5 s o par metros que permitem controlar os pesos entre a trilha de ferom
65. registro e novamente inicializa os pesos da lista P e volta a procurar a pr xima localiza o esperada como na primeira vez Cada nova localiza o esperada que encontrada adicionada a lista R de localiza es esperadas recomendadas Como caracter stica do m todo guloso ap s encontrar alguma localiza o esperada recomendada abaixo do valor do S o algoritmo encerra sua execu o assumindo que as melhores localiza es esperadas recomendadas j foram encontradas sem reconsiderar sua resposta Abordagem do aprimoramento de tempo Esta abordagem considera o tempo que o visitante economizaria se sua p gina alvo estivesse na localiza o que ele esperava Na verdade a parti o n o 127 possui nenhuma informa o como quantidade de segundos ou minutos que o visitante gastou procurando sua p gina Por isso o algoritmo considera a ordem em que a localiza o esperada foi visitada pelo visitante O algoritmo infere a prov vel economia de tempo da seguinte forma se a localiza o esperada A foi a primeira a ser visitada pelo visitante e a B a segunda o visitante teria economizado mais tempo se a localiza o de sua p gina fosse a p gina A do que se fosse na p gina B Assim ter amos que atribuir um peso maior a A O algoritmo descrito a seguir AprimoramentoTempo S R Inicio Crie a lista P da estrutura Pagina Peso Coloque em P todas as paginas indice de Tabela de Paginas com Peso 0 Repita
66. rico que usado para adaptar p ginas 1 Para cada p gina i a ser adaptada Calcule a probabilidade de cada p gina vizinha de i ser boa para conduzir o usu rio considerando o conjunto de p ginas destino Use a t cnica de navega o adaptativa em quest o para conduzir o usu rio para os links que levam as p ginas com maior probabilidade Neste processo de adapta o da apresenta o da p gina a principal diferen a em rela o ao modelo 1 o uso da probabilidade No modelo 1 usado diretamente o valor do ferom nio para decidir qual link destacar Aqui n o daremos exemplos de como as p ginas podem ser adaptadas no modelo 2 como fizemos no modelo 1 porque os exemplos do modelo 1 servem para o modelo 2 A nica diferen a o uso da probabilidade ao inv s do ferom nio 85 CAPITULO V IMPLEMENTAC O As informac es desta sec o s o relacionadas amp implementac o do modelo 1 Neste capitulo todas as vezes que mencionar o termo AntWeb sem especificag es estaremos nos referindo a implementac o do modelo 1 do AntWeb adaptativo O modelo 1 foi implementado em linguagem PHP usando banco de dados MySQL A Figura 36 mostra p gina do AntWeb que os usu rios acessam para navegar no site do Departamento de Ci ncia da Computac o da UnB Quando o usu rio acessa essa p gina ele deve clicar no link cligue aqui para comegar para iniciar a navegac o na Internet Este endereco inicial apenas um ponto de pa
67. t 0 21 2A SA 1 A 4 t 0 39 2A 3A 2 AG 0 63 2A 3 2 A 6 t 0 58 27 3A A 7 t 0 73 2B A 8 t 0 17 2A 3A 1 A 9 t 0 33 2A 3A 2 109 A 10 t 0 2A 3A 1 A 11 t 0 75 B 3 A 12 t 0 7 2B 3 A 13 t 0 14 2A 3A 1 A 14 t 0 79 2B 3 A 15 t 0 9 2B A 16 t 0 88 Tabela 17 Adic es de ferom nio 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 t 3 a s el 7 sa 9 10 11 12 13 14 15 16 1A 2A 0 3 0 3 0 32 0 3 0 32 0 31 0 32 0 34 0 3 2B 0 53 0 53 0 53 0 53 0 53 3A 0 5 0 54 0 52 0 52 0 52 0 51 0 52 0 54 0 5 1 TEE F E i Ta l ie 12 13 13 13 13 13 Os ferom nios que dever o ser considerados para a tomada de decis o por parte do usu rio s o aqueles das p ginas 2A 2B 1 e 2 Conforme salientado na Tabela 17 verificamos que a p gina 2A recebeu 5 atualiza es de 0 33 para o destino 1 e 4 atualiza es para 2 ficando com 0 27 e 0 252 de ferom nio A p gina 2B recebeu 5 atualiza es de 0 5 para 3 ficando com 0 423 de ferom nio A p gina 1 recebeu 5 atualiza es de 1 ficando com 0 83 de ferom nio A p gina 2 recebeu 4 atualiza es de 1 ficando com 0 762 de ferom nio Para o teste da heur stica com
68. tabela de backtracks uma tabela tempor ria por esta raz o n o nos preocupamos defini la de forma normalizada Esta tabela definida desta forma mais facilmente manipulada pelos processos seguintes Extra o de informa es da tabela de backtracks Este o processo que obt m as informa es teis para reestrutura o do site Este processo usa a tabela de backtracks e dependendo da abordagem escolhida outras informa es como o benef cio de visitas do site O algoritmo b sico deste processo descrito a seguir Inicio Particione a tabela de backtracks por p gina alvo Para cada parti o Fa a Inicio Crie a lista R com a estrutura P gina Peso Re a lista da p ginas recomendas AcheLocalizac esRecomendas S R Mostre as localizac es recomendas em R para a p gina alvo desta partic o Fim Fim O algoritmo primeiro particiona a tabela de localizac es esperadas pela p gina alvo Cada partic o de determinada p gina alvo servir para descobrir as localiza es recomendadas O algoritmo trabalhar cada parti o separadamente Em cada parti o o algoritmo aplicar a fun o AcheLocaliza esRecomendas S R que aqui representa uma das tr s abordagens para otimiza o de navega o explicadas mais adiante Esta fun o encontra as 123 localizag es recomendadas para a p gina alvo correspondente a partic o que est sendo trabalhada e as armazena na lista R A vari vel S um pont
69. uma solu o concreta que nos mostra como o comportamento da formiga pode ser aplicado navega o da Internet Mas apesar do significativo passo que demos acreditamos que ainda existe muito trabalho a ser feito O estudo para determinar diferen as entre a peregrina o da formiga e a navega o na Internet foi insignificante perto do que ainda falta ser feito necess rio disponibilizar a implementa o do modelo 1 na Web por um per odo maior e a implementa o pode ser aprimorada ainda mais para se tornar mais fiel ao comportamento da formiga real No que diz respeito ao modelo 2 ele talvez possa incorporar mais t cnicas de otimiza o dispon veis na literatura especializada preciso tamb m realizar aplica es do AntWeb adaptativo para que este se consolide como um m todo maduro no cen rio de desenvolvimento de Websites adaptativos Apesar de n o ter sido poss vel a implementa o do modelo 2 na Web em raz o dos prazos serem escassos este trabalho escrito cont m todas informa es necess rias para a sua implementa o Al m disso o trabalho de implementa o ser consideravelmente diminu do com o aproveitamento do c digo da implementa o j realizada O modelo 1 foi implementado atrav s de uma abordagem orientada objetos justamente para que suas classes possam ser aproveitadas na futura implementa o do modelo 2 Apesar de todo trabalho que falta ser feito acreditamos que demos uma grande contribui
70. utiliza uma lista P que conter todas as p ginas que podem ser localiza es esperadas para a p gina alvo cadastradas na tabela de p ginas Inicialmente o algoritmo carrega todas as poss veis p ginas na lista P e inicializa o valor de Peso para 0 Depois para cada item da lista P conta quantas vezes a p gina aparece no atributo Localiza oEsperada1 da parti o que a pondera o usada neste m todo e coloca em peso da lista P o valor encontrado Este algoritmo inclui em R somente p ginas que possuem peso maior ou igual a S que o limite informado pelo administrador do site Abordagem do aprimoramento do benef cio Na abordagem do aprimoramento do benef cio usaremos o objeto a mais de informa o que o benef cio do site em si Este objeto representado em nosso algoritmo pela lista B que uma lista simples de n meros reais Esta lista representa o benef cio da seguinte forma O item B 1 o benef cio do visitante encontrar sua p gina alvo na 1 tentativa O item B 2 o benef cio do visitante encontrar sua p gina alvo na 2 tentativa E assim por diante O benef cio pode ser inferido estatisticamente baseado na raz o entre a quantidade total de visitantes que encontraram sua p gina na k zima tentativa e sobre o total Ou pode ser informado empiricamente pelo Administrador Web com base na sua experi ncia Neste algoritmo vamos considerar que a lista B j esteja dispon vel 125 como se
71. 06 M dia 0 00 39 17 67 95 76 85 82 60 86 33 88 24 89 90 90 90 Desvio Padr o 0 00 3 79 2 47 1 55 1 39 0 94 0 84 0 71 0 49 56 11 3 2 Situa o 2 Dois caminhos sendo 1 de 5 links e outro com 4 links http intranet homepage N outras http intranet recursos_tecnologicos menu_recursos_tecnologicos htm 280 N outras http intranet menus menu_relacao_equipamentos_quadro_resumo htm 154 N outras http intranet menus menu_relacao_equipamentos_quadro_total htm 155 outras http intranet recursos_tecnologicos relacao_equipamentos gerencia_filial quadro_total_maquinas htm 310 N outras http intranet recursos_tecnologicos relacao_equipamentos gerencia filial quadro geral m quinas htm 308 Figura 27 Situa o com um caminho de 4 links para o objetivo Tabela 7 Rendimento obtido com p gina alvo a 3 links de profundidade Tempo seg 60 360 660 960 1260 1560 1860 2160 2460 Tempo min 1 6 11 16 21 26 31 36 41 Execug o 1 0 00 45 83 71 21 76 56 82 14 86 54 88 98 89 81 92 48 Execu o 2 0 00 44 44 68 18 80 73 85 71 85 90 88 71 90 28 92 07 Execu o 3 0 00 38 89 71 21 78 65 81 75 87 18 89 52 91 20 91 26 Execu o 4 0 00 44 44 65 15 80 21 81 75 87 50 87 90 91 44 90 04 Execu o 5 0 00 41 67 71 21 80 73 85 71 87 50 88 44 90 74 90 85
72. 2 88 46 88 44 91 20 90 04 Execu o 3 0 00 34 72 66 67 73 96 82 94 85 58 88 44 90 28 91 06 Execu o 4 0 00 41 67 71 97 75 00 80 16 85 58 87 63 90 28 90 65 Execu o 5 0 00 31 94 63 64 77 08 84 13 85 90 87 90 90 28 90 65 Execu o 6 0 00 45 83 68 94 78 13 82 94 85 26 87 63 90 05 91 06 Execu o 7 0 00 41 67 68 94 78 13 83 73 85 90 88 71 91 20 91 46 Execu o 8 0 00 36 11 71 21 77 08 82 14 85 90 88 17 90 51 91 46 Execu o 9 0 00 43 06 63 64 75 52 82 94 86 54 88 44 89 58 90 65 Execu o 10 0 00 45 83 68 18 78 13 84 92 86 22 89 78 89 58 90 65 Execu o 11 0 00 40 28 69 70 78 65 82 54 87 50 87 90 90 05 90 04 Execu o 12 0 00 37 50 67 42 78 13 82 54 84 62 89 25 89 12 91 06 Execu o 13 0 00 40 28 72 73 73 96 80 16 86 54 88 71 88 66 90 45 Execu o 14 0 00 40 28 68 18 77 60 80 95 86 22 88 71 89 12 90 85 Execu o 15 0 00 41 67 68 18 76 04 82 14 86 86 87 37 89 81 91 06 Execu o 16 0 00 34 72 67 42 77 60 82 14 87 82 89 25 89 12 91 06 Execu o 17 0 00 40 28 64 39 75 52 82 14 85 58 87 37 88 89 91 46 Execu o 18 0 00 38 89 65 15 77 60 81 75 86 54 86 02 90 28 90 24 Execu o 19 0 00 40 28 68 18 75 52 84 52 86 54 88 17 90 51 91 87 Execu o 20 0 00 38 89 67 42 79 69 80 95 87 50 88 98 89 58 91
73. 2A 3B A 4 t 0 38 1A 2A 3B A 5 t 0 11 1A 2A 3B A 6 t 0 22 1A 2A 3B 107 0 77 1A 2B 7 t A 8 t 0 68 TA 2B 9 t t 0 13 1A 2A 3B 0 48 1A 2A 3B 0 05 1A 2A 3B 0 23 1A 2A 0 92 1A it 0 72 TA 2B 0 57 A Tabela 14 mostra a simula o de visitas de formigas A Tabela 15 mostra as quantidades de ferom nio que ser o acrescidas em cada p gina em rela o ao tempo Tabela 15 Adi es de ferom nio 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 T 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 1A 0 3 0 3 0 25 0 25 0 25 0 55 0 3 0 3 0 25 0 25 0 55 2A 0 3 0 3 0 3 0 3 0 3 0 3 0 3 2B 0 5 0 5 0 5 0 5 0 5 0 5 3B 0 5 0 5 0 5 0 5 0 5 0 5 0 5 Os links que ir o decidir qual o caminho o usu rio vai pegar est o na p gina 1A Portanto ser o os ferom nios de 2A e 2B que far o diferenca na hora do usu rio escolher o link Ao final da simulac o conforme mostrado na Tabela 15 a p gina 2A que corresponde ao caminho mais longo recebeu 7 atualizac es de 0 3 no final da simulac o ficando com 0 28 de ferom nio A p gina 2B recebeu 6 atualizac es
74. 5 E finalmente o AntWeb retorna a p gina modificada para o usu rio 6 Quando o usu rio clicar em algum link que ele recebeu do AntWeb ele mandar uma nova requisi o ao AntWeb recome ando todo o ciclo novamente A Professores Microsoft Internet Explorer d slal File Edit Yiew Favorites Tools Help El lt Back gt A A search Favorites 4 64 HI Ad Address http f antweb linf unb br urlehttp ffwww cic unb br docentes docentes html Be Go Links gt Ci ncia da Computa o Corpo DocENTE AbaCristha Medo Aluizio Arce la AE ho Nano de Castro Santa Rosa Celta Rala Fernando A A C Abigterg te Francisco de Assis Cartao Pinheiro Gerson Pitcher Homero Latz Piccolo Jogo J C Gordm Jos Carbs Rala Juma F C Warde rey u waag Lutz ant bo da Frota Matos Marcelo Lade ira March da Costa P Branco Marco Aur lio de Canal o Marta Ekaia M Nascimento Marta Em lita Te les Water Marta de Fatma R Brando Mark Ant nio Ribeiro Dantas Mario Sila de Camargo lei 4 E Done Local intranet Figura 38 P gina de Corpo Docente 1 requisi o da p gina E WW he TERE N ad 2 p gina Servidor web Usu rio CIC UnB ICH Figura 39 Acesso a p gina sem o AntWeb 89 1 requisic o da p gina ao 2 requisic o da mms
75. 67 57 58 11 3 3 Situa o 3 Dois caminhos sendo 1 com 5 links e outro com 2 links http intranet homepage N outras http intranet recursos_tecnologicos menu_recursos_tecnologicos htm outras http intranet menus menu_relacao_equipamentos_quadro_resumo htm N outras http intranet menus menu_relacao_equipamentos_quadro_total htm N outras http intranet recursos_tecnologicos relacao_equipamentos gerencia_filial quadro_total_maquinas htm N outras http intranet recursos_tecnologicos relacao_equipamentos gerencia_filial quadro_geral_m quinas htm Figura 28 Situac o 3 com um caminho com dois links para o objetivo Tabela 8 Rendimento obtido com p gina alvo a 2 links de profundidade Tempo seg 60 360 660 960 1260 1560 1860 2160 2460 Tempo min 1 6 11 16 21 26 31 36 41 Execu o 1 0 00 44 44 69 70 77 08 86 90 88 14 88 71 91 67 92 07 Execu o 2 8 33 47 22 70 45 80 73 86 51 89 10 89 52 91 20 92 89 Execu o 3 16 67 48 61 72 73 81 77 83 73 88 46 91 67 91 90 91 06 Execu o 4 16 67 59 72 75 00 79 17 86 90 89 10 89 25 91 20 93 29 Execu o 5 833 54 17 74 24 80 21 87 30 88 78 91 13 91 90 91 46 Execu o 6 0 00 43 06 70 45 75 00 85 71 87 82 90 05 91 44 92 48 Execu o 7 0 00 50 00 75 00 79 69 84 13 89 74 91
76. 8 692 701 41 R Michel e M Middendorf An ACO algorithm for the shortest common supersequence problem In D Corne M Dorigo and F Glover editors New Methods in Optimisation McGraw Hill 1999 42 R Schoonderwoerd O Holland and J Bruten Ant like agents for load balancing in telecommunications networks In Proceedings of the First International Conference on Autonomous Agents ACM Press 1997 pages 209 216 43 R Schoonderwoerd O Holland J Bruten e L Rothkrantz Ant based load balacing in telecommunications networks Adaptative Behavior 1996 5 2 169 217 44 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 45 R van der Put and L Rothkrantz Routing in packet switched networks using agents Simulation Practice and Theory 1999 46 R van der Put Routing in the faxfactory using mobile agents Technical Report R amp D SV 98 276 KPN Research 1998 47 1 Joachims D Freitag T Mitchell WebWatcher A Tour Guide for the World Wide Web Proceedings of IJCAI97 1997 48 T St tzle e H Hoos Improvements on the Ant System Introducing the MAX MIN Ant System ICANNGA97 Third International Conference on Artificial 221 Neural Networks and Genetic Algorithms University of East Anglia Norwich UK Wien Springer Verlag 1997 49 T St tzle e H Hoos MAX MIN Ant system and local search for
77. BAccess sdata databasename return true else echo arquivo this gt iniFile n o foi encontrado return null gt lt PHP class DBAccess var configuration function DBAccess this gt setConfiguration function setConfiguration 166 bd linf if bd linf this sconfigurationf mvsglhost l ftp linf unb br this sconfigurationf username antweb this gt configuration password 123456 Sthis sconfigurationf databasename l antweb function data d ret this gt configuration d return ret gt lt PHP class Url var url var configuration var element var tested true function get return this gt url function testUrl f if this gt tested if substr this gt url 1 167 url this gt url f if fopen url r this gt url this gt tested true function putSlash url parse_url this gt url path pathinfo url path if isset path extension this gt url function parse this gt element parse_url this gt url function setUrl u this gt url u function setConfiguration amp c this gt configuration amp c function processExcetion amp u 168 if u http www exatas unb br cic mestrado u function handle if empty this gt url this gt url t
78. CAO IT SE ER DEE ED A 81 A O IS ann OE E ER EO N NR NE OS od 81 A O TO SR EG GR ee a De DE dn UN ta Ca ee EE vate 82 NEE EE ER EE OE ER EE EE Sethe 121 A O ER EE NE EE EN I 128 xii RESUMO O comportamento da formiga pode ser usado como metafora para melhorar a performance de sistemas tipo Web Com a tecnologia atual de navegac o na Internet as condic es em que o usu rio navega procurando suas p ginas alvo s o muito parecidas com o procedimento das formigas para encontrar alimento Mas de forma distinta ao procedimento das formigas os usu rios da Internet n o possuem ferom nio para que eles possam cooperar entre si no processo de navegac o Com base nestas observac es e pela inexist ncia de um trabalho que tenha como objetivo orientar o usu rio da web dando nfase a otimiza o de rotas foi desenvolvido um estudo com o objetivo de preencher esta lacuna aplicando o comportamento da formiga na Web que denominamos AntWeb Este estudo foi dividido em duas partes O AntWeb para avalia o de websites e o AntWeb adaptativo Em rela o ao AntWeb para avalia o de websites foi desenvolvida uma metodologia de avalia o que foi implementada em um software que tinha como entrada a estrutura de um website e como sa da uma medida de performance da estrutura Em rela o ao AntWeb adaptativo foram desenvolvidos dois modelos heuristicos para guiar o usu rio da Web em um contexto de hipermidia adaptativa que chamamos de modelo 1
79. Cada vez que uma pagina de servidor web acessada gravado um registro no final do arquivo de log com informac es sobre o acesso como a data e a hora que a pagina foi acessada o endere o IP do usu rio que acessou a p gina e a URL da p gina acessada Assim com base nestas informa es pode se estimar a quantidade de ferom nio existente na p gina Desta forma notamos que a adi o de ferom nio que o usu rio faz de forma involunt ria bastando que ele passe por uma determinada p gina para que o ferom nio seja depositado Outra solu o encontrada trata do uso de tecnologias Esta tecnologia consiste em adicionar tags contendo um script um programa feito em alguma linguagem de programa o normalmente interpretada dentro do c digo HTML da p gina Quando o usu rio acessa esta p gina o servidor web executa todos os scripts que est o dentro do c digo HTML e retorna para o browser do usu rio apenas as sa das dos programas executados inseridas no c digo HTML Isso poderia ser usado por exemplo quando o usu rio acessa a p gina e o script executado Este script pode executar alguma a o que seja equivalente a a o das formigas em depositar ferom nio no lugar onde est o passando Nas duas solu es o ferom nio seria representado por n meros reais associados p gina Devido s restri es existentes na Web atual a associa o destes n meros s p ginas teria que ser feita de forma indireta e centralizada
80. Esta informa o adicional pode ser oferecida sob a forma de texto ou sob a forma de indicadores visuais A Gera o de Links consiste em criar links adicionais automaticamente nos nodos Uma das desvantagens desta t cnica o aumento no n mero de links existentes nos nodos aumentando a sobrecarga cognitiva e tornando o hiperespa o mais complexo Os Mapas Adaptativos gr ficos ou ndices criados automaticamente com o objetivo de ajudar o usu rio a entender a estrutura do hiperespa o locais ou simplesmente fornecer uma vis o do hiperespa o em algum aspecto Outras t cnicas de navega o adaptativa podem ser empregadas nos mapas adaptativos O AntWeb como um sistema de orienta o global puro orienta o usu rio na navega o da estrutura original de links e nodos j existentes no hiperespa o evitando criar novos elementos na estrutura do hipertexto Assim todas as t cnicas com exce o dos mapas adaptativos e a gera o de links s o empreg veis no contexto do AntWeb A escolha da melhor t cnica para influenciar o usu rio vai 37 depender das restric es impostas pelo ambiente em que est sendo empregado o sistema 38 CAPITULO Ill ANTWEB PARA AVALIA O DE ESTRUTURAS DE WEB Este cap tulo descrever o principal trabalho relacionado ao AntWeb adaptativo que o AntWeb para avalia o de estrutura de Web Sites desenvolvido por Li Weigang e colegas 17 36 e 25 O AntWeb para avalia o de estruturas de We
81. Graduac o x Para confirmar nossa conclusao atribuimos zero novamente as taxas de ferom nio e repetimos as simulac es novamente mas desta vez usando o link Corpo Docente em primeiro lugar O resultado mostrado na Tabela 11 Tabela 11 Bateria inicianco com o link Corpo Docente Link destacado Rota escolhida Corpo Docente P s Gradua o Corpo Docente P s Gradua o Corpo Docente P s Gradua o 102 Corpo Docente P s Gradua o Corpo Docente P s Gradua o Corpo Docente P s Gradua o Corpo Docente P s Gradua o Corpo Docente P s Gradua o Xi DS x x xi XI xi x x Corpo Docente Corpo Docente Corpo Docente Xi x DS XI xi X XI XI XI XI XI x Corpo Docente Os novos resultados confirmam nossa conclus o Nesta nova simulac o quando ocorre a primeira atualizac o as taxas de ferom nio est o empatadas fazendo com que o sistema destaque os dois links Na segunda atualiza o ocorre o mesmo que aconteceu com a primeira bateria de navega es e o link Corpo Docente destacado por ter sido o primeiro a ser utilizado Portanto a hip tese para o modelo 1 de que ele leva o usu rio aos caminhos que possuem menor custo falsa Mas por que a avalia o implicita da solu o ocorre com as formigas reais e n o ocorre com o modelo 1 do AntWeb
82. Inicio Crie Lista de P ginas P e insira a parti o nela Crie uma Lista de Backtracks B vazia Para i de 2 ate n 2 Fa a Onde n o tamanho da parti o Inicio Se P i 1 P i 1 n o existir link entre as duas Ent o SP i era uma localiza o esperada Adicione P i a Lista de Backtracks B Fim Se B n o est vazio Ent o Adicione lt P n B P n 1 gt a Tabela de Backtracks Fim Fim Este algoritmo baseado na seguinte id ia Seja esta a sequ ncia de p ginas visitadas por um visitante qualquer P1 P2 P1 P3 P4 Note que o visitante acessou a p gina P1 em seguida acessou a p gina P2 e novamente acessou a p gina P1 Se existe um link entre P1 para P2 o visitante ent o pode ter usado este link para mudar de p gina Se n o existe nenhum link em P2 para P1 evidente que o visitante usou o bot o de voltar do seu navegador para acessar P1 novamente Portanto dada uma p gina P qualquer Se a p gina acessada anterior a P for igual p gina acessada posterior a P ent o essa p gina um ponto de backtrack Para descobrir se o visitante usou o bot o voltar do navegador para passar de uma p gina para outra ou se usou um link necess rio saber se existem links entre as duas p ginas Esta a fun o da tabela hash de links montada no 1 O s mbolo ser usado na descri o dos algoritmos para indicar o in cio de um coment rio 120 algoritmo O sistema monta a ta
83. PHP 184 if this gt getName ASDF jecho this gt getName this gt setElement lt asdf a s b asd gt if Sthis sgetTvpe l end jecho this gt getType if this gt getName ASDF echo this gt getName this load var dump S this class LinksSelector extends Decorator var querySelectLinks var numberOfLinksOnPage function getNumberOfLinksOnPage return this gt numberOfLinksOnPage function setQuerySelectLinks amp p this gt querySelectLinks amp p function getOut return array links parent getOut if lisset links return links this gt numberOfLinksOnPage count links if this gt numberOfLinksOnPage 0 185 return return this gt querySelectLinks gt setLinks links if result this gt querySelectLinks gt execute while line mysql_fetch_row result return line 0 line 1 return return gt lt PHP class QuerySelectLinks extends Query var configuration var conection var links function setLinks amp p this gt links amp p function setConection amp c this gt conection amp c function setConfiguration amp c this gt configuration amp c 186 function generateQuery reset this gt links if list 6value each this gt links query SELECT url pheromone FROM Urls WHERE BINARY url in
84. PLIFICADO DO MODULO DE ATUALIZA O 92 FIGURA 42 DIAGRAMA DE CLASSE DO MODULO DE ADAPTA O DA P GINA ne 94 FIGURA 43 ESTRUTURA PARCIAL DO SITE DO CIC aaan ee ee oren ee ee ee ee ee ee ee ee ee 99 FIGURA 44 UMA DAS P GINAS OBTIDAS DURANTE O EXPERIMENTO annen see ee ese ee 100 FIGURA 45 SITE ESTRUTURADO EM RVORE aan ee see ee ee ee ee ee ee see ee ee ee ee ee ee ee ee ee ee ee 104 FIGURA 46 SITE COM CAMINHOS DE TAMANHOS DIFERENTES an se ee see ee ee ee ee ee ee ee 106 FIGURA 47 ESTRUTURA COM MAIS DE UMA P GINA DESTINO sanar ees see ee ee ee ee ee ee ee ee ee 108 LISTA DE TABELAS TABELA APLICA ES DE ACO PARA PROBLEMAS EST TICOS uses ees esse se see ee ee ee ee ee ee ee 19 TABELA 2 APLICA ES DE ACO PARA PROBLEMAS DIN MICOS anos ee see ee ee ee ee ee ee ee 20 TABELA 3 TABELA DE PROBABILIDADE anna ees ee ee eren ee ee ee ee ee ee ee ee ee ee ee ee ee ee ee LT 25 TABELA 4 SIMULA O COM UM MODELO SIMPLES ee ese sesse ees see ee see ee ee ee ee ee ee ee ee ee ee 46 TABELA 5 SIMULA O USANDO O MODELO ANTWEB aaa ee ee ee ee oren ee ee ee ee ee ee ee ee ee 49 TABELA 6 RENDIMENTO OBTIDO COM PAGINA ALVO A 4 LINKS DE PROFUNDIDADE 54 TABELA 7 RENDIMENTO OBTIDO COM PAGINA ALVO A 3 LINKS DE PROFUNDIDADE 56 TABELA 8 RENDIMENTO OBTIDO COM P GINA ALVO A 2 LINKS DE PROFUNDIDADE 58 TABELA 9 AS M DIAS DE THROUGHPUT DAS T
85. Projeto 20e 20Software htm http bsbserv004 cnm menu_cnap Faturamento htm http bsbserv004 cnm menu_cnap Informagdes 20Gerenciais htm http bsbserv004 cnm menu_cnap Tecnologia htm http bsbserv004 cnm menu_cnap Controle 20de 20Despesas htm http bsbserv004 cnm menu_cnap Ger ncia 20de 20Projetos htm http bsbserv004 cnap menu cnap Procedimento 20de 20Avalia o 20T cnica DOC http bsbserv004 cnm menu cnap relatorio de acompanhamento htm http bsbserv004 cnm menu cnap gest ol htm http bsbserv004 cnm menu_cnap gestaoll_II htm http osbserv004 cnap menu_cnap Documentos 20de 20Gestao0 20IlI XLS http bsbserv004 cnm menu_cnap 07 20de 20junho htm http bsbserv004 cnm menu_cnap 11 20de 20julho htm http bsbserv004 gestaoprojetos http bsbserv004 gestaoprojetos abertura psq_registro_projeto asp http osbserv004 gestaoprojetos perfil_profissional psq_tecnico asp http bsbserv004 gestaoprojetos capacidade_produtiva psq_capacidade_produtiva asp http osbserv004 cnm menu_cnm menu_cnm htm http osbserv004 cnm Apresentacao Apresentagao 20CNAP 20e 20CNM PPT http bsbserv004 cnm menu cnm apresentacao metodologia junho 2000 modulo tatico filial ppt http bsbserv004 cnm menu cnm diagrama Il htm http bsbserv004 cnm menu_cnm fase01_agosto htm http bsbserv004 cnm menu_cnm fase03_agosto htm http bsbserv004 cnm menu_cnm fase05_agosto htm http bsbserv004 cnm m
86. R S SITUA ES aaan ee ee oenen ee ee see ee ee ee ee 59 TABELA 10 BATERIA DE NAVEGA ES COM O MODELO 1 ie se see see see ee see ee ee ee ee ee ee ee 101 TABELA 11 BATERIA INICIANCO COM O LINK CORPO DOCENTE neee ee ee ee ee 101 TABELA 12 SIMULA O COM UMA ESTRUTURA EM ARVORE nn san see ee see ee ee ee ee ee ee ee 105 TABELA 13 FEROM NIOS ADICIONADOS ees ese se ees ees ee ee ee ee ee ee ee ee Re ee ee ee ee Re ee ee 105 TABELA 14 SIMULA ES COM CAMINHOS DE TAMANHOS DIFERENTES eeen 106 TABELA 15 ADI ES DE FEROM NIO sanar oenennnne neer ersenensnsseerseenennensseeeseenennsnnven 107 TABELA 16 SIMULA O COM MAIS DE UM DESTINO ueeesssssssssssnensnnnnnnnnnnnnnnnnnnnnnnnns nn 108 TABELA 17 ADI ES DE FEROM NIO snaar see ee see ee ee ee ee ee ee ee ee ee ee ee 109 Xi EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU EQU LISTA DE EQUAC ES NSN O A RE AE N N EE N OE ay so EE AE DI 11 TNO 12 Ne ee N EES EE EE N N RE ai 22 ACKO A TE EE EE EE N GE EA EE Shia 22 A O DEERE EE OE a GE A A S a 22 eel OE EE RE ORE EE EE 23 INON OE E EE LT ER OU TE i 26 A O ME RE N RE NE EE N N ene 27 Ne OE EE OE N ARR 47 je en EE EE NE OE N ia OE RR 47 A O DEMEN 48 NENA PEE E EE E EE A 71 A O MS et DE rg iba A 79 ACAOTA EE EE E OON A EN 79 A O De MEE AE N ee ee Ee A AE GODE OE DE 80 AC O VO AE N N RR AR N EE N N GE N 80 A
87. UNIVERSIDADE DE BRASILIA INSTITUTO DE CIENCIAS EXATAS DEPARTAMENTO DE CI NCIA DA COMPUTA O SISTEMA ADAPTATIVO PARA WEB SITES BASEADO NO COMPORTAMENTO DA FORMIGA Wesley Martins Teles BRAS LIA 2003 WESLEY MARTINS TELES SISTEMA ADAPTATIVO PARA WEB SITES BASEADO NO COMPORTAMENTO DA FORMIGA Dissertac o apresentada como requisito parcial a obtenc o do grau de Mestre Departamento de Ci ncia da Computac o Instituto de Ci ncias Exatas Universidade de Brasilia Orientador Prof Dr Li Wegang Co orientadora Prof Dr C lia Ghedini Ralha BRASILIA 2003 Se queres paz te prepara para a guerra Se n o queres nada descansa em paz Humberto Gessinger AGRADECIMENTOS A Deus pelos acontecimentos bons desfrutei e pelos ruins que me fortaleceram A toda minha familia por ter me apoiado em todos os sentidos Ao meu orientador Prof Dr Li Weigang por ter aceitado como discipulo sem hesitar um tecn logo em processamento de dados que acabara de conhecer mesmo tendo alunos suficientes para preencher suas vagas Ao Prof Li novamente por ter confiado a mim o desenvolvimento de sua ideia e por ter transmitido a mim o oficio da pesquisa tendo me apoiado durante todo o mestrado Prof 2 Dra Celia Ghedini Ralha por ter me adotado como aluno co orientado e por ter dado um apoio fundamental ao desenvolvimento desta disserta o bem como s publica es referentes este trabalho Ao Prof Dr Marco A
88. Usuario Modelo do Usuario Processa t Adapta o Modifica Efeito Adaptativo Figura 16 Ciclo cl ssico de adapta o Segundo 18 o ciclo cl ssico de adapta o dos sistemas de HA mostrado na Figura 16 O ciclo constitui se basicamente na coleta de dados do usu rio no processamento desses dados para se obter o modelo do usu rio na gera o do efeito adaptativo baseado no modelo do usu rio e na aplica o do efeito adaptativo no sistema de HA que ser mostrado ao usu rio Ap s o usu rio receber a nova hiperm dia adaptada este gerar mais dados que ser o coletados novamente pelo sistema Todos os processos s o feitos pelo sistema de HA Para fazer a modelagem do usu rio o sistema HA faz uso das regras de modelagem Para fazer a adapta o ou seja obter o efeito adaptativo atrav s do modelo de usu rio o sistema de HA faz uso das regras de adapta o 35 11 4 3 Navegac o Adaptativa O objetivo da Navegac o Adaptativa auxiliar o usu rio a encontrar seu caminho no hiperespaco No contexto deste trabalho navega o o movimento efetuado por usu rios ao longo das estruturas do hipertexto enquanto procura a informa o desejada Promover uma navega o adaptativa significa apresentar uma interface adaptada para o usu rio medida que este navega rumo informa o desejada Os m todos de navega o adaptativa s o as estrat gias usadas pelos sistemas de HA para auxiliar o usu rio
89. VRP Ordenamento Gambardella amp Dorigo 1997 20 HAS SOP seq encial Colora o de Costa amp Hertz 1997 7 ANTCOL grafos Superseq ncia Michel amp Middendorf 1998 40 41 AS SCS mais comum A Tabela 2 lista aplica es de ACO para problemas din micos de otimiza o combinatorial ou seja problemas no qual as caracter sticas podem mudar no decorrer do processo de busca da solu o como o problema do roteamento de pacotes em uma rede Tabela 2 Aplica es de ACO para problemas din micos Problema Autor Ano Refer ncias Nome do Algoritmo Roteamento de Schoonderwoerd Holland Bruten amp 1996 42 43 ABC rede orientado a Rothkrantz 1998 51 ASGA conex o White Pagurek amp Oppacher 1998 15 AntNet FS Di Caro amp Dorigo 1998 10 ABC smart ants Bonabeau Hnaux Gu rin Snyers Kuntz amp Theraulaz Roteamento de Di Caro amp Dorigo 1997 13 14 16 AntNet amp AntNet FA rede n o orientado Subramanian Druschel amp Chen 1997 9 Regular ants a conex o Heusse Gu rin Snyers amp Kuntz 1998 34 CAF Van der Put amp Rothkrantz 1998 46 45 ABC backward A seguir ser o descritas em um nivel maior de detalhe duas aplicac es da meta heur stica da formiga para a resolu o de problemas na Ci ncia da Computa o Uma para a resolu o do problema do caixeiro viajante e outra para o problema do balanceamento de cargas em redes de telecomunica es Elas serv
90. _contratos pessoal contratos relacao_contrato_caixa_salvador htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_Cassi htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_Codeplan htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_DNPM htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_ELETRONORTE htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_ECT htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_FISEPE htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_FUBUNB htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_ICS htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_INCRA htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_MRE htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_MTE htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_SEA htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_SEFP htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_STF htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_STJ htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_TRF_Recife htm http intranet a_politec cli
91. _lanes_messias_nascimento html http intranet recursos_humanos perfil_profissional mapa_recursos henrique_pedra_jaber html http intranet recursos_humanos perfil_profissional mapa_recursos jairo_da_silva_santos html http intranet recursos_humanos perfil_profissional mapa_recursos janaina_fioravante_torres html http intranet recursos_humanos perfil_profissional mapa_recursos jemima_coelho_de_souza html http intranet menus menu_pessoal_telefones_equipe htm http intranet recursos humanos pessoal telefones pessoal telefone unidade gerencia filial htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade administrativa_financeira htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade area_tecnica area_tecnica htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade fabrica_software htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade recursos_humanos recursos_humanos htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade gerencia_comercial htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade administrativa_financeira htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade recursos_humanos recursos_humanos htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_unidade recursos_humanos recrutamento_selecao htm http
92. a como uma palavra ou figura Um dos requisitos do hipertexto que os links devem ser autom ticos ou seja quando o leitor selecionar um link no hipertexto o movimento entre os dois nodos devem ser autom tico 11 3 1 Um breve hist rico de hipertexto O termo hipertexto foi cunhado em 1967 pelo vision rio Ted Nelson o qual definiu atrav s do seu artigo Literary Machines 6 como uma forma n o linearizada de escrita Mas a vis o que trouxe a g nesis do hiperm dia foi elaborada por Bush em um artigo intitulado As we may think 53 Neste artigo Bush elaborou uma vis o de um sistema de extens o da mem ria chamado de Memex Bush descreveu o Memex como um tipo de arquivo privado mecanizado e um dispositivo em que um indiv duo armazena seus livros registros e comunica es que poderia ser consultado com velocidade e flexibilidade Segundo Nielsen Nielsen 1990 6 Bush foi capaz de prever as consequ ncias da explos o de informa es que era a principal raz o para o desenvolvimento do Memex Mais que um simples reposit rio o sistema Memex era um ndice associativo Esta caracter stica foi essencial para Bush descobrir que as t cnicas de indexa o contempor neas estavam impondo restri es artificiais na recupera o da informa o for ando pesquisadores a tra ar seus requerimentos por uma r gida classifica o alfab tica ou num rica Bush disse A mente humana n o funciona desta m
93. a medida que as formigas caminham pelo site elas v o depositando ferom nio nos links fazendo com 47 que a probabilidade que as formigas posteriores escolham o caminho com ferom nio aumente na mesma propor o que a quantidade de ferom nio depositado no link A seguir explicaremos o modelo matem tico usado no AntWeb Seja fuma formiga visitando uma p gina i no instante t Seja Ko conjunto dos links de i que n o foram visitados por f at o instante t A probabilidade da formiga f escolher o link i j caso je K dada pela seguinte f rmula OF o pokon 0 caso o contr rio Vke K caso je K Equa o 9 onde Tijit a quantidade de ferom nio na aresta i j no instante t e f s o par metros que definem a participa o relativa do ferom nio e do valor heur stico 77 no c lculo da probabilidade nj definido como 77 1 w onde w soma do tempo de download com o tempo de visita da p gina j 25 Ap s encontrar a p gina alvo uma formiga k deposita uma quantidade Ar t em todos os links segundo a f rmula l 1 nl p se i De T t At 0 lo se i pe TO Equac o 10 onde T t o trajeto percorrido pelo formiga no instante t ni t o n mero de links no trajeto T t A adi o de ferom nio e a evapora o s o implementadas pela seguinte regra aplicada a todos os links 48 Hide 1 p Tjlt 1 Ati t Equac o 11 Onde p um par metro do si
94. adas baterias de 54 testes para calcular o rendimento thoughput do site cada bateria composta de 20 execuc es da simulac o A primeira bateria foi composta de simulac es de 60 segundos de execuc o cada uma As demais baterias foram compostas de simulac es de 360 660 960 1260 1560 1860 2160 e 2460 segundos cada uma Tabulados os dados foram calculados a m dia e o desvio padr o de cada uma das baterias 11 3 1 Situa o 1 Apenas 1 caminho de 5 links para o objetivo http intranet homepage gt outras http intranet recursos_tecnologicos menu_recursos_tecnologicos htm gt outras http intranet menus menu_relacao_equipamentos_quadro_resumo htm gt outras http intranet menus menu_relacao_equipamentos_quadro_total htm gt outras http intranet recursos_tecnologicos relacao_equipamentos gerencia_filial quadro_total_maquinas htm gt outras http intranet recursos_tecnologicos relacao_equipamentos gerencia_filial quadro_geral_m quinas htm Figura 26 Situac o com apenas 1 caminho de 5 links Tabela 6 Rendimento obtido com p gina alvo a 4 links de profundidade Tempo seg 60 360 660 960 1260 7 1560 1860 2160 2460 EES SE BE AE SE AE TE 55 Execu o 1 0 00 34 72 68 94 76 56 83 73 85 58 87 90 89 81 91 26 Execu o 2 0 00 34 72 68 18 77 08 84 5
95. ado o trabalho de Luiz A Multigeo Palazzo 18 e o trabalho de Peter Brusilovsky 37 que tratam exatamente de fornecer uma vis o geral da rea revisando t cnicas e fornecendo seus conceitos A descric o do AntWeb para avaliac o de estruturas de Web sites foi baseada no trabalho de Li Weigang e colegas 25 A parte correspondente aos experimentos feitos envolvendo o sistema AntWeb para avaliac o de estruturas de Web sites foi baseada no projeto final de graduac o desenvolvido por Judas Tadeu Cariolano 17 no segundo semestre de 2001 que consistiu na implementa o do software necess rio para a realiza o do experimento de valida o do AntWeb para avalia o de Websites e nos relat rios escritos relativos aos experimentos de Webmining realizados no departamento de Ci ncia da Computa o da UnB O desenvolvimento dos Modelos do AntWeb adaptativo foi feito usando se conceito de WebMining Hiperm dia Adaptativa e ACO como base para a formaliza o Os experimentos de valida o do AntWeb adaptativo foram feitos de duas formas Com a implementa o do modelo usando a Server Side Script Language SSSL PHP em conjunto com banco de dados MySQL al m de m todos de projeto de sistemas como a UML e os padr es de projeto Simula o de trafego de usu rios em sites fict cios 1 4 A contribui o do AntWeb no contexto de outros trabalhos Em rela o a meta heur stica da formiga o AntWeb aplicou o comportamento da formiga na W
96. ados a simula es de navega es fict cias utilizando a implementa o do AntWeb Para os experimentos listados abaixo foram considerados os seguintes valores para os par metros do sistema decay coefficient coeficiente de evapora o 0 02 iteration time dura o dos intervalos entre as atualiza es 30 segundos max links to show n mero de links a destacar 1 link threshold valor m nimo para se salientar um link 0 01 Os valores foram escolhidos para que o sistema reagisse de forma r pida e produzisse resultados vis veis aos acessos feitos em baixa escala das simula es O threshold foi colocado abaixo do coeficiente de evapora o e o par metro iteration time foi estabelecido com uma dura o curta para que o sistema destacasse os links em no m ximo 30 segundos ap s o seu uso O baixo valor do coeficiente de evapora o foi estabelecido devido grande quantidade de atualiza es ocorridas durante o curto intervalo entre as atualiza es De outra forma o ferom nio evaporaria r pido demais E finalmente o n mero de links a destacar foi estabelecido igual a 1 link por que os experimentos envolviam duas escolhas de rota e se o sistema destacasse mais de um link n o seria poss vel visualizar o caminho prefer ncial Outras informa es importantes para o sucesso dos experimentos descritos a seguir s o a desabili o do sistema de cache de p ginas do browser e a desativa o do uso do servidor proxy no b
97. amento de formigas artificiais O m todo usado para atualizar as probabilidades bastante simples quando uma formiga atinge um nodo a entrada na tabela de ferom nio correspondente ao nodo ao qual a formiga acaba de sair aumentada de acordo com a f rmula P anterior E Ap 1 Ap Equac o 7 Onde p a nova probabilidade e Ap o aumento na probabilidade As outras entradas na tabelas s o diminu das de acordo com a f rmula 27 p anterior REE Equac o 8 Uma vez que os novos valores somam 1 eles ainda podem ser interpretados como probabilidades 11 1 5 2 3 Idade e lat ncia de formigas Um requisito fundamental no trabalho de Schoonderwoerd foi desenvolver m todos simples para encorajar formigas a entrar em caminhos relativamente curtos e ao mesmo tempo evitar nodos congestionados 43 Dois m todos s o usados O primeiro fazer 4p o valor usado para alterar as tabelas de ferom nio reduzir progressivamente de acordo com a idade da formiga Uma formiga leva uma unidade de tempo para mover se de um nodo para outro assim a idade de uma formiga corresponde ao tamanho do trajeto j percorrido Dessa forma formigas que percorrem caminhos mais curtos t m mais influ ncia sobre o sistema O segundo m todo que depende do primeiro retardar formigas em nodos congestionados O tempo de retardo depende do grau de congestionamento Esse retardo tem dois efeitos complementares Temporariamente reduz o fluxo
98. amp getOut t Decorator getOut if lisset t return t e new HtmlElementParser t return e gt lt PHP class HtmlParser 176 var stringCache var wrapper function HtmIParser stringCache new StringCache stringDecomposer new StringDecomposer elementExtractor new ElementExtractor wrapper new Wrapper extractingTag new ExtractingTag extractingNonTag new ExtractingNonTag this gt wrapper amp wrapper this gt stringCache amp stringCache wrapper gt setNext elementExtractor elementExtractor gt setNext stringDecomposer stringDecomposer gt setNext stringCache elementExtractor gt setExtractingNonTag extractingNonTag elementExtractor gt setExtractingTag extractingTag elementExtractor gt setNextToStates function pushHtml h this gt stringCache gt pushString h function shiftElement return this gt wrapper gt getOut he function setStringCache amp p this gt stringCache amp p function setWrapper amp p this gt wrapper amp p sk gt lt PHP class HtmlElementParser var dataProcessing var isTag var type var name var atributes function HtmlElementParser e if isset e this gt setElement e exit erro O construtor n o est sem parametros function setElement s unset this gt is Tag
99. aneira Ela opera por associa o Com a compreens o de um item ela busca instantaneamente o pr ximo que sugerido por associa es de id ias de acordo com alguma intrigante rede suportada pelas c lulas do c rebro Bush definiu Memex em termos da tecnologia foto mec nica dispon vel 31 nos anos 40 tr s anos antes o transistor foi inventado e 30 anos antes dos computadores pessoais em conjunto com sua vis o de como estas tecnologias poderiam ser estendidas e otimizadas No Memex o operador poderia entrar com textos desenhos e notas usando equipamentos de registro de imagens Para armazenar estas informa es era usado um sistema de arquivamento de microfilmes Para mostrar v rios arquivos de microfilmes simultaneamente e ligar arquivos relacionados era usado um simples c digo Bush vislumbrava sistemas de compress o de dados fotogr ficos transmiss o de voz cart es de mem ria eletromagn tica e o uso da televis o para promover a comunica o entre os diversos usu rios do Memex O sistema Memex nunca foi implementado usando as tecnologias que Bush vislumbrava mas a id ia de uma esta o de trabalho de hiperm dia interativa foi um pensamento razo vel nos anos 40 inspirando importantes contribui es Outro nome importante na hist ria do hipertexto foi Engelbart respons vel pelo nascimento de muitas inova es na hiperm dia que se tornaram padr o em todos os sistemas de hiperm dia que temos hoje Engelb
100. antity of clicks function generateQuery return CREATE TEMPORARY TABLE Additions SELECT url count addition FROM Logs WHERE datetime gt this gt interval gt getStart AND datetime lt this gt interval gt getEnd GROUP BY url 72 lt PHP class PheromoneUpdaterTrigger 209 var pheromoneUpdater var configuration var conection var queryLastUpdate var queryAdditionCalculator var intervals array function setConection amp p this gt conection amp p function setQueryAdditionCalculator amp p this gt queryAdditionCalculator amp p function shiftinterval list value each this gt intervals return value function setUrl function PheromoneUpdaterTrigger builder new BuilderWithCache builder gt buildDecoratorPheromoneUpdate Trigger this this gt configuration gt setIniFile antweb ini this gt configuration gt load function setLastUpdate amp p this gt queryLastUpdate amp p function setConfiguration amp p this gt configuration amp p function setPheromoneUpdater amp p this gt pheromoneUpdater amp p function getLastUpdate if result this gt queryLastUpdate gt execute return mysql_result result 0 last function update this gt pheromoneUpdater gt update this gt
101. apesar da superioridade do Modelo 2 comparado ao 1 no que diz respeito a condu o do usu rio o modelo 1 ainda importante para os estudos entre as diferen as na navega o do usu rio e a peregrina o da formiga V11 5 Recomenda es e trabalhos futuros As possibilidades de trabalhos futuros poss veis de se realizar com o AntWeb s o imensas n o sendo poss vel listar todas nesta se o No entanto citamos algumas j vislumbradas durante nosso trabalho Para a obten o de outras ideias sugerimos a leitura completa deste documento pois acreditamos que o leitor poder formar suas pr prias ideias de como o AntWeb pode ser melhorado Dentre as possibilidades de trabalhos futuros podemos citar A aplica o do modelo 2 em sistemas adaptativos para sites reais na Internet Fazer um estudo para saber de que forma popularidades anteriores de uma p gina podem influenciar na relev ncia de uma p gina Sabemos hoje que a popularidade recente de uma p gina influencia na sua relev ncia para o usu rio como mostra 47 mas ainda n o sabemos o quanto as popularidades anteriores podem influenciar a relev ncia Se confirmado que as popularidades anteriores s o uteis para a determina o da relev ncia estaremos comprovando uma nova fun o para o ferom nio 116 A exposic o da implementac o do modelo 1 por um periodo maior de tempo e a sua divulgac o na Internet de forma que haja um n mero de acessos significativo
102. apora o mais um par metro do sistema que determina a evapora o ocorrida entre os instantes t e t n e possui a restri o O lt p lt 1 Atij AT k 1 Equa o 5 Onde AT a quantidade de ferom nio depositada pela k sima formiga entre os instantes te t n que por sua vez dada por 23 7 FLI ak esima formiga usou a aresta i j ie jie 0 em outro caso Equac o 6 Onde Q uma constante geralmente igual a 1 e L o comprimento do trajeto percorrido pela k sima formiga Assim conclu mos a descri o da aplica o da meta heur stica da formiga para o problema do caixeiro viajante 1 1 5 2 Balanceamento de cargas em redes de telecomunica es O balanceamento de cargas em redes de telecomunica es um problema de atribui o quadr tica para o qual foi desenvolvido uma aplica o usando a meta heur stica da formiga segundo Schoonderwoerd 42 Quando determinadas centrais telef nicas atingem um n vel cr tico de utiliza o tornam se incapazes de originar novas chamadas e nesse contexto o balanceamento de carga entre diversas centrais de uma rede mostra se fundamental para um bom desempenho da mesma Chamadas entre dois pontos s o geralmente roteadas por esta es de comuta o intermedi rias ou nodos em uma rede de grandes propor es h v rias rotas poss veis para cada chamada Um bom sistema de balanceamento de carga procura distribuir o fluxo de chamadas atrav s do sistema
103. armazenarmos a tupla lt url ferom nio gt para a transi o a tupla seria lt url1 url2 ferom nio gt e para o link seria a tupla da transi o com mais uma chave para identificar o link dentro da p gina Conforme vimos os dados teriam uma manuten o mais f cil na hip tese do ferom nio associado p gina pois no caso de altera es feitas na estrutura do site o nico caso de se ter que atualizar as taxas de ferom nio seria se alguma p gina fosse inclu da ou exclu da Neste caso as taxas de ferom nio a serem manipuladas seriam apenas das p ginas em que a inclus o ou a exclus o foi feita Na hip tese do ferom nio associado transi o teriam que ser manipuladas todas as taxa das p ginas vizinhas s p ginas inclu das ou exclu das Na hip tese do 68 ferom nio associado aos links o n mero de taxas a ser manipulada seria maior ainda no caso de haver mais de um link entre duas p ginas Na possibilidade de haver inclus o ou exclus o de links s haveria necessidade de manipular taxas de ferom nio se o ferom nio estiver associado transi o ou link Se o ferom nio estiver associado p gina n o haveria necessidade alguma de manipular taxas de ferom nio em fun o disto As taxas associadas aos links seriam mais vantajosas somente quanto quest o da efici ncia na representa o da estrutura do site pois nos outros dois tipos de representa es haveria perda de informa es relativa a quanti
104. art foi um pioneiro em automa o de escrit rio Em 1968 ele produziu o NLS oN Line System no qual incorporou uma variedade de caracter sticas como mouse m ltiplas janelas e correio eletr nico Tamb m em 1968 Kay construiu um modelo de papel o de um sistema port til de hiperm dia que ele chamou de Dynabook O prot tipo original foi desenhado com tela plana interface gr fica e capacidade de manipular grandes quantidades de texto O Dynabook tinha como interface uma linguagem de programa o de escritaleitura de f cil uso chamada de Paintbrush no qual crian as poderiam usar para criar figuras animadas e poderia incorporar links via linhas telef nicas sem fio com acesso a fontes de informa es hiperm dia O Dynabook seria produzido em um custo baixo de forma que ele poderia estar dispon vel para cada crian a na escola Ainda hoje o Dynabook n o foi implementado com os conceitos originais Nielsen concluiu que o hipertexto tem uma surpreendente e rica hist ria comparada com a maioria dos fen menos na industria de computadores pessoais O hipertexto foi concebido em 1945 nascido em nos anos 60 lentamente alimentado nos anos 70 e finalmente entrou no mundo nos anos 80 com um crescimento r pido depois de 1985 Durante 1989 o hipertexto se tornou um campo estabelecido com o 32 surgimento do primeiro jornal cientifico especializado hypermedia publicado por Taylor Graham e muitas conferencias bem suc
105. atura Nos dois modelos a percep o da formiga em rela o ao ferom nio est representada pela percep o do usu rio em rela o ao link Uma das grandes 71 vantagens do modelo 1 que o usu rio n o precisa entender necessariamente o sistema de formiga O importante que o link destacado chame sua aten o aumentando a probabilidade de ser escolhido Os links ser o destacados em tempo real medida que os usu rios usam o link O sistema contabilizar os acionamentos dos links de cada p gina pelos usu rios e a partir destas informa es atualizar a quantidade de ferom nio associada a cada link Finalmente usando as taxas de ferom nio atualizadas destacar sistematicamente os links O princ pio usado para aumentar a probabilidade do usu rio usar o link com mais ferom nio que estando o link destacado ele ser mais facilmente visto e consequentemente quanto mais o link visto pelos usu rios mais ele ser usado IV 6 1 A representa o do ferom nio no modelo 1 No modelo 1 associado somente uma taxa de ferom nio para cada p gina Nesta abordagem a indica o para v rias p ginas destino est fundida em um mesmo valor Esta taxa compartilhada por todos os usu rios que farejam a p gina em um determinado momento independente de seus objetivos Esta forma mais compat vel com o sistema das formigas reais uma vez que elas s podem perceber um tipo de cheiro em um determinado
106. av s dos links pre existentes no site e sim criar um novo link de acesso na home page para levar o usu rio diretamente p gina destino Este m todo classificado em hiperm dia adaptativa como condu o local pois ocupa se em levar o usu rio ao destino em um nico passo 18 Ap s a primeira concep o chegou se a conclus o que para desenvolver um sistema como o descrito no exemplo n o seria necess rio o modelo do ferom nio Bastaria calcular o n mero de acessos feitos recentemente para cada p gina do site e inserir um banner na home page para a p gina que tivesse a maior n mero de acessos recentes Esse m todo teria o mesmo resultado da aplica o do m todo do ferom nio mas com a vantagem de ser mais simples e direto A nica desvantagem em rela o ao uso do ferom nio neste caso seria a flexibilidade de permitir que popularidades anteriores influenciassem no ferom nio atual de forma continuada e controlada mas isso tinha um efeito n o vis vel influ ncia na relev ncia da p gina para o usu rio Assim a utilidade do uso do ferom nio nesta concep o iria depender de um estudo que determinasse criteriosamente quanto popularidades anteriores de uma p gina influenciam na relev ncia da p gina buscada pelo usu rio no momento e consideramos que existia uma grande probabilidade de que esta relev ncia fosse nula Desta forma a primeira concep o do AntWeb adaptativo foi abandonada Se isto fosse realmente compr
107. b sites surgiu a partir da necessidade de medir a efici ncia da estrutura de web sites ap s a adi o de links sugerida por um sistema de Web Mining que implementava o algoritmo de Srikant 44 O trabalho de Srikant consistia em um algoritmo que descobria localiza es esperadas pelos visitantes do site para suas p ginas alvo usando informa es contidas no log do servidor web Seu algoritmo baseava se na presun o de que quando o usu rio toma determinado caminho para sua p gina alvo e descobre que ele tomou um caminho errado ele usa o bot o voltar do seu browser para retomar sua busca pelo caminho correto Por exemplo considere o web site da Figura 17 Suponhamos que depois de examinarmos o log do servidor web descobrimos que uma quantidade significativa de usu rios faz o caminho 1A 2A 3B 2A 1A 2C 9 para chegar at a p gina alvo 9 Podemos interpretar isto da seguinte forma Eles iniciam na raiz e esperam encontrar a p gina 9 sob 2A v o at 2A e depois para 3B Constatado que 9 n o est sob 3B voltaram todo o caminho at a raiz e finalmente encontra 9 sob 2C Assim podemos presumir que a localiza o esperada pelo usu rio para sua p gina alvo 9 era 3B e ao inv s de 2C Figura 17 Trajeto executado por usu rios para encontrar a p gina 9 39 Assim com base nestas informag es o webmaster poderia fazer alterac es na estrutura do Web site para que este reflita melhor a expectativa dos us
108. bela hash a partir da tabela de links do sistema O motivo de usar uma tabela hash ao inv s de acessar diretamente a tabela de links aumentar a velocidade de acesso Tendo criado a tabela hash o algoritmo particiona a tabela de log duas vezes O primeiro processo de particionamento feito de forma que cada partic o corresponda aos logs de determinado visitante Assim teremos neste primeiro particionamento o n mero de partic es igual ao n mero de visitantes dentro da tabela de log Em seguida particionamos novamente cada parti o gerada no primeiro particionamento da seguinte forma Os logs de cada parti o est o ordenados pela sequ ncia de acesso do visitante Determinamos quais logs correspondem s p ginas alvo do visitante Dividimos a parti o de forma que cada log de p gina alvo corresponda ao final de uma nova parti o Desta forma se o visitante acessou N p ginas alvos existiram N parti es correspondentes a este visitante Em outras palavras o n mero total de parti es da tabela de logs ser o n mero de p ginas objetivo cadastradas no log pois cada p gina alvo ter sua parti o correspondente Depois de realizarmos os dois particionamentos teremos parti es que representam a sequ ncia de p ginas que o visitante acessou antes de encontrar sua p gina alvo Cada uma destas parti es corresponde a um registro da tabela de backtracks a ser preenchido O leitor deve estar se pergunta
109. bmining como em 44 que tentam resolver este problema atrav s da minerac o do log e da colocac o de links extras nas p ginas em que os usu rios costumam 104 errar mais O objetivo deste experimento n o provar que o modelo 2 diminui os erros de trajet ria como mencionamos na descric o dos experimentos do modelo 1 mas sim provar due mesmo em uma situa o em que existem muitos erros de trajet ria o modelo 2 capaz de aprender a estrutura do site com efici ncia Nesta simula o mostramos que a heur stica robusta mesmo quando um grande n mero de usu rio toma o caminho errado inicialmente para sua p gina objetivo A Figura 45 mostra um exemplo de um site apresentado em 25 Neste exemplo um visitante a cada 5 segundos come a a navegar no site iniciando da home page Observe que 70 dos usu rios tomam o caminho correto e 30 o caminho errado se considerarmos que eles tem como p gina objetivo a p gina 9 Como os browsers hoje em dia possuem sistema de cache que faz com que as p ginas que j foram acessadas anteriormente sejam guardadas em disco para o caso do usu rio acess las novamente fizemos esta simula o levando isso em considera o A Tabela 12 mostra a simula o de usu rios navegando em nosso site Nesta tabela as linhas representam as navega es correspondentes a cada formiga e as colunas os intervalos a cada 5 segundos Os n meros mostrados antes de cada trajeto s o valores aleat rios que v o
110. da p gina ent o o modelo 2 passa a fazer o que presumiamos que o modelo 1 faria ou seja levar o usu rios as p ginas mais populares pelo caminho mais curto Alem do modelo 2 fazer o que o modelo 1 prometia fazer no aspecto de auxiliar a navegac o do usu rio ele pode ser usando n o s com a heur stica da popularidade mas com qualquer outra heur stica Os experimentos do modelo 2 seguiram os mesmos formatos dos experimentos em 25 Eles foram feitos atrav s de simula es com formigas andando em estruturas de sites fict cios Nas simula es descritas a seguir foram considerados os seguintes valores para a atualiza o do ferom nio Coeficiente de evapora o p 0 3 Coeficiente que diz o quanto a dist ncia de uma p gina ao destino deve afetar o decremento do ferom nio o 1 As constantes de controle a 1 e B 0 V1 2 1 A diminuic o de erros na trajet ria do usu rio Um dos problemas encontrados na navega o de sites n o bem estruturados o grande n mero de p ginas acessadas por sess o Isso ocorre por que muitas vezes o usu rio toma uma trajet ria errada na hora de procurar sua p gina Em sites com estrutura em forma de rvore os usu rios muitas vezes clicam em um link achando que este link vai lev lo at a sua p gina Ao perceber que ele tomou o caminho errado ele usa o bot o back do Browser para voltar at o ponto em que ele errou para poder tomar o caminho correto Existem trabalhos de We
111. dade de links que existem entre duas p ginas Mas para o AntWeb esta informa o n o tem relev ncia uma vez que o objetivo apenas levar o usu rio at a p gina destino n o importando qual dos links entre duas p ginas o usu rio deva usar IV 4 Compara o entre o AntWeb adaptativo e outros sistemas A primeira diferen a importante entre o AntWeb adaptativo e os demais sistemas formiga tradicionais vide se o 11 1 5 est no fato em que as formigas artificiais n o s o componentes de software No AntWeb as formigas s o os usu rios da Internet Dessa forma n o poss vel fazer com que as formigas andem de forma aleat ria com probabilidade proporcional s taxas de ferom nio no caminho como acontece no AntWeb para avalia o de estruturas e nos demais sistemas formiga No AntWeb adaptativo o usu rio escolhe o caminho a pegar baseando se no seu interesse e o ferom nio apenas um influenciador na sua escolha Outra diferen a a forma como as formigas s o influenciadas Dependendo da t cnica de navega o adaptativa escolhida o usu rio influenciado de forma discreta e n o continua como acontece com outros sistemas formiga A forma como armazenado o ferom nio outra diferen a importante No AntWeb adaptativo o ferom nio armazenado nas p ginas e n o nos links como ocorre com o AntWeb para avalia o A Internet na perspectiva do AntWeb seria como na Figura 30 em que o ferom nio representado
112. de 0 5 ficando com 0 44 de ferom nio Assim usando a Equac o 19 obtemos os valores Pia 2a 0 39 pia ze 0 61 Desta forma o caminho menor prevaleceu mostrando a efici ncia do modelo na indica o de caminhos curtos V1 2 3 Indica o de mais de uma pagina destino Esta caracter sca do modelo 2 foi colocada prova porque o modelo 2 o 108 primeiro sistema inspirado no comportamento da formiga que considera mais de um destino na conduc o da formiga A Figura 47 mostra a estrutura de um site com 3 p ginas destino Neste exemplo as 3 p ginas destino recebem a mesma quantidade de visitas ou seja cada p gina tem 33 dos acessos dos usu rios 0 33 0 33 Figura 47 Estrutura com mais de uma p gina destino A Tabela 16 mostra a simulac o com formigas e a Tabela 17 mostra a quantidade de ferom nio que foi acrescentado pelas formigas nas p ginas em rela o ao tempo Como neste caso existe mais de um destino em considera o usamos uma nota o diferente para evitar ambiguidade A nota o usada nas c lulas da Tabela 17 representa Atq onde At o acr scimo de ferom nio feito naquele instante e d o destino correspondente Tabela 16 Simula o com mais de um destino Time 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 t 112 13 4 5 6 7 8 9 10 1 12 13 14 15 16 A 1 t 0 96 2B 3 A 2 t 0 19 2A 3A 1 A 3
113. de formigas desde nodos congestionados para seus vizinhos impedindo assim que as tabelas que conduzem a nodos congestionados sejam atualizadas e permitindo que as probabilidades de escolhas alternativas cres am mais rapidamente Uma vez que as formigas envelhecem enquanto esperam em nodos congestionados elas t m menos influ ncia sobre as tabelas de ferom nio ao sa rem 1 1 5 2 4 Roteamento de chamadas As chamadas operam independentemente das formigas Para determinar a rota para uma chamada de um nodo particular para um destino a maior probabilidade na tabela de ferom nio para esse destino escolhida O vizinho correspondente a essa probabilidade ser o pr ximo nodo na rota para o destino A rota v lida se o destino alcan ado e a chamada ent o colocada na rede a 28 menos que algum dos nodos da rota esteja congestionado Nesse caso a tentativa de chamada falha Dessa forma chamadas e formigas interagem dinamicamente umas com as outras Chamadas influenciam na carga dos nodos que por sua vez influencia nas formigas atraves do mecanismo de retardo Formigas influenciam nas rotas representadas pelas tabelas de ferom nio que determinam por sua vez o roteamento de novas chamadas Acabamos de expor duas aplica es inspiradas no sistema formiga o TSP e o balanceamento de cargas em redes de telecomunica es Passaremos a expor outros fundamentos para o nosso trabalho como World Wide Web Web as tecnologias
114. de hipertexto e hiperm dia e algumas considera es de hiperm dia adaptativa atrav s de m todos e t cnicas de navega o adaptativa 11 2 Uma vis o geral de World Wide Web A World Wide Web ou simplesmente Web o mundo de informa es em larga escala acess veis via Internet Uma biblioteca on line de conhecimentos humanos tamb m referida como W3 ou WWW A Web usa a tecnologia de hipertexto para permitir o acesso s informa es em multim dia localizadas em sistemas de computadores espalhados pelo mundo formando um sistema de hiperm dia distribu da A Web une t cnicas de informa es em rede e hipertexto para tornar poss vel um poderoso sistema global de informa es A Web um dos recursos mais usados dispon veis na Internet Na vis o do usu rio a Web consiste de documentos e links A Web a grande respons vel pelo grande uso da tecnologia de hipertexto O protocolo HTTP Hypertext Transport Protocol usado para permitir a integra o de programas como os browsers com servidores remotos de informa o A Web surgiu atrav s de um projeto iniciado por Tim Bearners Lee e Robert Caillian nos laborat rios CERN na Genebra http www cern ch em 1991 Originalmente o projeto tinha como objetivo prover uma infraestrutura para a alta comunidade de f sica em energia da Europa para que eles pudessem compartilhar informa es Uma vez que os f sicos estavam localizados em v rias organiza es e usando uma va
115. e 150 echo lt META HTTP EQUIV Refresh Content 0 URL this gt url gt get gt unset this gt sender unset this gt url unset this gt adaptabilityChecker this gt log gt execute unset this gt log this gt conection gt close unset this gt conection function setPageLoader amp p this gt pageLoader amp p function setDbCreator amp p this gt bDCreator amp p function setTest amp t this gt test amp t function setConection amp c this gt conection amp c function setHandlerParser amp p this gt handlerParser amp p function setSenderNonHtml amp p gt this gt senderNonHtml amp p function setSender amp s this gt sender amp s function setLog amp l this gt log amp l function setUrl amp u this gt url amp u function setConfiguration amp c this gt configuration amp c lt PHP class Miscellaneous function testimplode original aaa aaa aaa aaa if original implode explode original echo funcionou function cleanArray a reset a 151 152 while element each a list key value element if value and value return key value return return function glue url url if lis arrav uri return false scheme uri
116. e cada partic o termine com uma p gina destino do usu rio 4 Para cada partic o criada do passo 3 atualize o ferom nio das p ginas usando a Equa o 17 e a Equa o 18 3A 3B 5 6 9 10 KY KY P gina 9 a p gina destino 2 Figura 35 Estrutura de um site fict cio Por exemplo a Figura 35 a estrutura de um site fict cio Considerando que o browser do usu rio possui um sistema de cache e o 1 se um visitante fizer a seguinte trajet ria para chegar at sua p gina destino neste site 1A 2A 3A 2C 9 Os acr scimos de ferom nio que este visitante far nas p ginas ser o os seguintes 1 5 de ferom nio em 1A 1 4 de ferom nio em 2A 1 3 de ferom nio em 3A 1 2 de ferom nio em 2C 84 1 1 de ferom nio em 9 Note que o valor do acr amp scimo vai aumentando cada vez que o usu rio chega mais perto do seu objetivo E como se o visitante estivesse sentindo o cheiro da sua p gina destino e quanto mais perto ele se encontra de sua p gina mais o cheiro fica forte IV 7 6 O processo de adapta o da apresenta o da p gina O AntWeb adaptativo prop em que as formigas s o influenciadas a seguir caminhos que cont m quantidade significativa de ferom nio atrav s de t cnicas de navega o adaptativa Estas t cnicas consistem em destacar links que desejamos que o usu rio use ocultar links que desejamos que ele n o use adicionar informa es aos links e outras mais Este o algoritmo gen
117. e de ferom nio com uma probabilidade maior No caso do AntWeb as formigas s o os usu rios da Web o que nos deixa em d vida se devemos considerar o usu rio da Web uma formiga artificial uma vez que eles s o seres humanos Mas independente disto n s sabemos que ao menos o ambiente que o usu rio da Web se encontra se encaixa mais na defini o de ambiente que Marco Dorigo definiu para suas formigas artificiais do que o ambiente das formigas naturais Os estados discretos das formigas de Dorigo s o como as p ginas da Web que os usu rios navegam onde as transi es s o os links existentes entre as p ginas A nica diferen a a inexist ncia do ferom nio das formigas artificiais Assim para fazer com que o ambiente dos usu rios da Web se torne totalmente compat vel com o ambiente das formigas artificiais preciso implementar mecanismos na Web que permitam que os usu rios percebam o ferom nio existente no ambiente e ao mesmo tempo permitam que ele deposite seu pr prio ferom nio no ambiente Para a solu o do problema de como os usu rios da Web depositariam o ferom nio no ambiente usando os recursos existentes na Web atual duas solu es foram encontradas o uso do arquivo log do servidor web e o uso de scripts que funcionam do lado do servidor Server Side Script Language SSSL O log um arquivo utilizado pelos servidores web para registrar o 65 hist rico de acessos feitos as p ginas que est o nele hospedadas
118. e seguir a rota 1A 2A fixada como 0 3 Paa 2c como 0 7 Os valores 0 3 e 0 7 foram obtidos de resultados do processo de WebMining Se a vari vel aleat ria do visitante A i t for menor ou igual a 0 3 ent o o visitante tomar o caminho 2A caso contr rio tomar o caminho 2C A Tabela 4 mostra a simula o com 12 visitantes 46 Um visitante gerado a cada 5 segundos 1A 0 3 0 7 2A 2B C sd A N 3A 3B 5 6 9 10 KA KY 9 a p gina objetivo 2 Figura 22 A estrutura de um website simples Tabela 4 Simula o com um modelo simples A t 5 sec Caminho do visitante Tempo 5 10 15 20 25 30 35 40 45 50 55 60 t 1 2 3 4 5 6 7 8 9 10 11 12 A 14 0 974 2C A 2 t 0 182 2A 3A 2A 3B 27 1A 2C A 3 t 0 917 2C E A 4 t 0 175 2A 3B Fi 3A 2A 1A 2C A S t 0 435 2C A 6 0 778 2C A 7 t 0 571 2C AB 0 210 2A 3A 2A 3B A 9 t 0 791 2C A 10 t 0 298 2A 3B ACD 0 322 2C A 12 t 0 655 11 2 3 Modelo de simula o AntWeb O experimento anterior foi feito sem a aplicac o do modelo AntWeb ou seja foi feito apenas considerando a situac o normal de qualquer website Agora explicaremos como o modelo de simulac o AntWeb e em seguida faremos a mesma simulac o usando o modelo No modelo AntWeb os visitantes ou seja as formigas caminham pelo site da mesma forma como na situac o anterior A diferenca que
119. e somente conter links direcionados ao pr prio AntWeb com uma anota o que informa qual o endere o na Internet o link original direcionava Assim quando o usu rio clica em algum link na p gina fornecida pelo AntWeb o browser do usu rio 70 retorna uma requisi o ao servidor AntWeb e este por sua vez contabiliza o uso daquele link atualiza a taxa de ferom nio no Banco de Dados e recome a o ciclo novamente obtendo a p gina original corresponde ao link que o usu rio usou Este ciclo continua at que o usu rio saia do sistema Ant Web p gina modificada Visitante us link quant de feromonio no link Figura 31 Modelo funcional Ant Web adaptativo IV 6 Modelo 1 do AntWeb adaptativo O modelo 1 como apresentado na se o IV 1 que trata da concep o do AntWeb adaptativo o modelo que procura trazer para a Web a meta heur stica da formiga da forma mais fiel poss vel ao comportamento das formigas naturais sem se preocupar com as otimiza es existentes na literatura dos sistemas formigas artificiais Este modelo teve como prop sito principal o estudo para descoberta de diferen as e semelhan as entre o comportamento do usu rio durante a navega o na Web e o comportamento das formigas naturais O desenvolvimento e a experimenta o deste modelo foi essencial para a obten o das conclus es necess rias para o desenvolvimento do modelo 2 que j cont m otimiza es propostas na liter
120. eb inteligente atrav s de interfaces adaptativas para web J foi comprovada a aplicabilidade proposta atrav s de publica es tal como 25 que marcou o in cio da pesquisa sobre o AntWeb al m dos trabalhos 57 e 58 No futuro esperamos o surgimento de outros trabalhos relacionados ao AntWeb visando o estudo e a aplicabilidade do sistema 1 3 Metodologia e realiza o Com rela o aos aspectos da apresenta o deste trabalho escrito foram seguidas prioritariamente as diretrizes do instituto de Ci ncias Exatas da Universidade de Bras lia Por m nas situa es n o especificadas ou incompletas foram usadas as diretrizes contidas em 59 Tamb m foram usados na prepara o desta disserta o livros de metodologia cient fica tais como 52 11 e 8 A tarefa de levantar os conceitos necess rios contextualiza o do AntWeb foi feita fazendo se uso da literatura referente aos respectivos temas A parte referente a meta heur stica Ant Colony Optimization ACO 31 centralizou se em descrever o sistema formiga de forma geral n o se preocupando em focar em uma aplica o espec fica do sistema Para escrever sobre o sistema de meta heur stica ACO desenvolvido por Marco Dorigo foram usadas principalmente as obras publicadas do pr prio desenvolvedor da t cnica Os conceitos sobre Web hipertexto e hiperm dia foram retirados de 6 Para os conceitos e teorias referentes aos sistemas de hiperm dia adaptativa foi us
121. eb que uma rea n o trivial comparada com s reas que normalmente s o aplicadas a meta heur stica da formiga Em virtude disto o AntWeb encarou problemas que tamb m n o s o usuais neste ramo da Ci ncia da Computa o O AntWeb teve que levar em considera o por exemplo o problema de existir p ginas na Web que tinham a mesma relev ncia para o usu rio Outra diferen a not vel neste novo contexto de aplica o o fato das formiga serem pessoas ao inv s de componentes de softwares como em todas as aplica es da meta heur stica da formiga existentes na literatura Em consequ ncia disto o AntWeb trouxe inova es para esta rea O AntWeb foi o primeiro sistema inspirado no comportamento da formiga levar em considera o a condu o da formiga multiplos destinos A adapta o do sistema as caracter sticas da navega o do usu rio da Web fez surgir uma nova metodologia que permitia a meta heur stica aprender com efici ncia o menor caminho sem o uso da avaliac o implicita da soluc o que normalmente existe em todas as reas que se costuma aplicar a meta heuristica da formiga O uso das t cnicas de hipermidia adaptativa mostrou uma nova maneira de influenciar a formiga alem do uso de numeros aleat rios como nas demais aplicac es do sistema formiga Em rela o a rea de Web Inteligente o AntWeb trouxe um novo sistema de navega o adaptativa que solucionou de forma consistente o problema de determinar
122. ebsite With model 2 simulations had been done to show of the optimized form that AntWeb could assist web users The main objective of these simulations is to test the research work developed with the AntWeb Keywords Ant System Web Mining Adaptive Hypermedia and Web Intelligence xiv CAP TULO INTRODU O 1 Problema A formiga um inseto social que trabalha em prol da col nia Suas caracter sticas f sicas n o lhe permitem ter uma vis o global do seu ambiente uma vez que possuem recursos de vis o curta o que as torna praticamente cegas Mas mesmo com essa limita o ela precisa encontrar seu alimento para sobreviver Esta uma situa o muito parecida com os usu rios quando buscam informa es nos sites da Internet Eles se encontram num imenso ciberespa o sem saber onde est o e por vezes nem por onde iniciar seu processo de busca pelas informa es que procuram Da mesma forma que a formiga se encontra em um gigantesco mundo sem indicativos o usu rio da Internet se encontra em uma gigantesca teia de p ginas interligadas por links Ambos tem uma vis o limitada do seu ambiente tornado bastante rdua sua tarefa de navega o Para auxiliar o usu rio nesta tarefa foram desenvolvidos mecanismos de busca que para tipos de procura muito especificas s o mecanismos razo veis mas estes mesmos mecanismos est o se tornando cada vez mais ineficientes medida que o ciberespa o cresce Quem nunca se deparou com u
123. ecar a desenvolver o modelo 1 com servidores PHP gratuitos na Web como o coolfreepages www coolfreepages com e o portland www portland co uk Descobrir um servidor gratuito na Web que n o tivesse os privilegios de sistema necess rios para a hospedagem do AntWeb desabilitados e que n o tivesse problemas de quedas frequentes n o foi tarefa f cil Para encontrar estes servidores foram usadas informa es obtidas do grupo de discurc es chamado PHP www grupos com br e de um ndice de sites no site www superphp com br Apesar desses servidores gratu tos terem sido essenciais para o desenvolvimento do AntWeb os problemas causados por eles atrasaram substancialmente o projeto de implementa o Para descobrir um servidor que tivesse os requisitos m nimos para desenvolver o AntWeb foram testados todos os servidores listados em www superphp com br Muitas vezes come ava se a trabalhar com um determinado servidor e o servidor era desativado nos obrigando a reiniciar uma nova busca de servidores gratu tos Mas no final quando a implementa o j estava no seu per odo final conseguimos hospedagem no servidor web do laborat rio de inform tica do curso da gradua o em Ci ncia da Computa o da Universidade de Bras lia Foi com essa hospedagem que foi poss vel dispor o AntWeb na Web por um per odo pequeno de tempo o que nos permitiu fazer nossos experimentos com o modelo 1 VII 4 Conclus o sobre o experimento Em rela o ao
124. ecayPheromone gt setConfiguration this gt configuration queryInsertUpdate gt setConfiguration this gt configuration trigger gt setConfiguration this gt configuration trigger gt setPheromoneUpdater pheromoneUpdater trigger gt setLastUpdate queryLastUpdate trigger gt setQueryAdditionCalculator queryAdditionCalculator function buildDecoratorLinksSelector linksArrayMaker new LinksArravMaker linksFilter new LinksFilter linksSelector new CacheLinksSelector querySelectLinks new QuerySelectLinks decoratorBuilder new DecoratorBuilder decoratorBuilder gt setNext linksSelector decoratorBuilder gt setNext linksArrayMaker decoratorBuilder gt setNext linksFilter decoratorBuilder gt setNext this gt htmIParser linksSelector gt setQuerySelectLinks querySelectLinks this gt linksSelector amp linksSelector if lisset this conection or isset this gt configuration exit core not built querySelectLinks gt setConection this gt conection querySelectLinks gt setConfiguration this gt configuration function buildDecoratorPageAdapter amp antWeb dissolver new Dissolver linksGuider new LinksGuider 159 linksHighlighter new LinksHighlighter sender new Sender unWrapper new Unwrapper decoratorBuilder new DecoratorBuilder if lisset this gt configuration exit erro core n
125. edidas 11 3 2 Classes de Links Pelo fato do sistema AntWeb ser um sistema de Navega o Adaptativa tendo como objetivo conduc o do usu rio atraves dos links conv m aqui citarmos os principais tipos de links encontrados nas hipermidias do ponto de vista do usu rio que o AntWeb deve levar em considerac o no processo de conduc o do usu rio S o eles Links locais n o contextuais Links contextuais ou Hipertexto Verdadeiro e Links do browser Os Links locais n o contextuais s o links independentes do conte do do nodo em que se encontram e geralmente s o apresentados como conjunto de bot es uma lista ou um menu pop up Tais links s o f ceis de manipular e podem ser classificados ocultos ou anotados Os Links contextuais ou Hipertexto verdadeiro s o os links vinculados ao contexto tais como os representados por certas palavras ou frases em um texto ou por zonas especialmente delimitadas de uma imagem Estes links podem ser anotados mas n o podem ser classificados nem totalmente ocultos Links do browser s o os links providos pelo navegador como o bot o voltar p gina inicial etc Estes links permitem atalhar em qualquer tempo o curso da navega o oferecida pelo sistema Eles est o em geral fora do controle do sistema mas seu uso n o pode deixar de ser considerado Os tipos de link especialmente os dois primeiros tipos devem ser levados em considera o ao escolher o tipo de t cnica de adapta
126. efone_cargo area_administrativa _financeira htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo area_tecnica area_tecnica htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo fabrica_software htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo recursos_humanos recursos_humanos htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo gerencia_comercial htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo area_administrativa _financeira htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo recursos_humanos recursos_humanos htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo recursos_humanos recrutamento_selecao htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo recursos_humanos treinamento htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo recursos_humanos departamento_pessoal htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo recursos_humanos medicina_trabalho htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo area_tecnica area_tecnica htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo area_tecnica atendimento htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_cargo area_tecnica consultoria htm
127. eles 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 O modelo heur stico bem como sua implementa o atrav s do AntWeb possui vantagens n o expl citas como a simplicidade do algoritmo a flexibilidade de n o precisar que o usu rio informe qualquer coisa e de n o depender da iniciativa do usu rio para que o sistema funcione A proposta apresentada possui um modelo extens vel que pode ser combinado sem grandes dificuldades com outros modelos podendo ser adaptado para diferentes situa es O sistema tamb m pode ser aprimorado de diversas formas para incorporar recursos de adaptabilidade mais espec ficos a diversos objetivos de sistemas de hiperm dia adaptativos 1 2 Objetivo e motiva o do trabalho O objetivo deste trabalho o estudo da aplica o da meta heur stica da formiga na navega o da Internet ou seja o desenvolvimento do AntWeb adaptativo baseado na met fora do comportamento das formigas possibilitando a implementa o de sistemas que procurem orientar o usu rio na navega o da Internet A Internet teve uma explos o r pida na sua utiliza o e possui atualmente acesso a diversas informa es de todas as naturezas em seus trilh es de sites dispon veis no mundo inteiro A Internet pode se
128. em rela o sua navega o na hiperm dia O m todo usado no AntWeb classificado na HA como Condu o Global CG pois o sistema procura conduzir o usu rio pelo caminho mais curto at seu objetivo no hiperespa o Na CG o objetivo do usu rio se encontra em um ou mais nodos e o sistema deve conduzir o usu rio na dire o deles oferecendo a cada passo o link apropriado Al m do m todo Condu o Global existe o m todo Condu o Local CL o m todo Suporte Orienta o Local OL e o m todo Suporte Orienta o Global OG A Conducao Local tem objetivo semelhante ao da CG por m um alcance muito menor ocupando se de um nico passo ao inv s de todo um caminho A conduc o deve ser reformulada a cada passo e tenta apresentar ao usu rio os links mais relevantes O m todo Suporte Orientac o Local consiste em auxiliar o usu rio a entender seu posicionamento no hiperespaco local E normalmente implementado por meio de informac o adicional sobre os nodos que podem ser acessados a partir do nodo corrente O m todo Suporte Orienta o Global tem como objetivo auxiliar o usu rio a entender a estrutura de todo o hiperespa o que constitui o dom nio de navega o do sistema Em sistemas n o adaptativos isto oferecido por meio de marcos visuais e mapas globais que auxiliam o usu rio a localizar sua posi o 1 4 3 1 T cnicas de Navega o Adaptativa Segundo 18 as t cnicas de navega o adaptativa s
129. encentes ao trajeto e diminuindo se por normalizac o as probabilidades associadas aos demais links 7 p p 1 se necess rio 11 2 5 Simula o usando o modelo AntWeb A seguir faremos a mesma simula o no site da Figura 22 s que desta 49 vez usando o modelo AntWeb Os resultados podem ser vistos na Tabela 5 Note que houve um aumento substancial na quantidade de visitantes que atingiram a p gina objetivo o que mostra que o modelo AntWeb torna a estrutura do website mais eficiente Tabela 5 Simulacao usando o modelo AntWeb At 5sec Tempo Caminho do visitante 5 10 15 20 25 30 35 40 45 50 55 60 T 1 2 3 4 5 6 7 8 9 10 11 12 0 974 2C 0 182 2A 0 917 2C 0 175 2A 0 435 2C 0 571 2C 0 210 2A 0 791 2C it 0 298 2A it 0 322 2C it 0 778 20 t t t st 0 655 11 2 6 Aspectos da implementa o O programa foi implementado na linguagem Java usando o banco de dados relacional Microsoft Access como base de dados O c digo fonte contou com aproximadamente 1538 linhas de c digo e o banco de dados com apenas tr s tabelas A linguagem Java foi escolhida por ser uma linguagem orientada a objeto e por facilitar a separa o dos elementos dos sistemas em classes O banco de dados no contexto do simulador serviu para armazenar a estrutura do WebSite Foi projetado de forma que p
130. entes relagao_clientes htm http intranet administrativo_financeiro produtos fornecedores_computadores_politec htm http intranet administrativo_financeiro produtos fornecedores_softwares_politec htm http intranet administrativo_financeiro produtos fornecedores_servicos_politec htm http intranet treinamento menu_treinamento htm http intranet treinamento aviso_inscrigao_curso htm http intranet treinamento cursos banco_instrutores htm http intranet treinamento relacao_livros htm http intranet treinamento cursos relacao_cursos htm http intranet projetos menu_fabrica_projetos htm http bsbserv004 cnap menu_cnap menu htm http bsbserv004 cnap menu_cnap requisitos doc 134 http bsbserv004 cnap menu_cnap apresentacao_02 htm http bsbserv004 cnap menu_cnap plano_de_estruturacao doc http bsbserv004 cnap menu cnap plano de acao emergencial doc http bsbserv004 cnap menu cnap paes especificacao para automacao banco recursos humanos talentos doc http bsbserv004 cnap menu cnap paes especificacao para automacao area comercial doc http bsbserv004 cnap menu cnap paes especificacao para automa o fabricas de projeto e software doc http bsbserv004 cnap menu cnap paes especificacao para automacao faturamento doc http bsbserv004 cnap menu cnap paes especificacao para automacao informacoes gerenciais doc http bsbserv004 cnap menu cnap paes especificacao para aut
131. enu_cnm fase07_agosto htm http bsbserv004 cnm menu_cnm fase09_agosto htm http bsbserv004 cnm menu_cnm fase02_agosto htm http bsbserv004 cnm menu_cnm fase04_agosto htm http bsbserv004 cnm menu_cnm fase06_agosto htm http bsbserv004 cnm menu_cnm fase08_agosto htm http bsbserv004 cnm menu_cnm introducao_agosto htm http bsbserv004 cnm menu cnm matriz de responsabilidades htm http bsbserv004 cnm menu cnm tecnicas e metodos recomendados agosto htm http bsbserv004 cnm menu cnm quest es mais frequentes agosto htm http osbserv004 cnm menu_cnm glosario_agosto htm http osbserv004 cnm menu_cnm bibliografia_agosto htm http bsbserv004 cnm menu_cnm formulario htm mailto cnm bsb politec com br http bsbserv004 cnm menu cnm palestra da semana metologica htm http intranet normas internas nbr iso 9000 pago1 htm http intranet normas internas nbr iso 9001 pago1 htm http intranet normas internas nbr iso 9004 pago1 htm http intranet normas internas iso 9000 menu comite apoio htm http intranet normas_internas politica_seguranca htm http bsbserv007 cyberdocs http intranet normas_internas aquisicao_equipamentos recomendacoes_tecnicas_servidor htm http intranet normas_internas aquisicao_equipamentos recomendacoes_tecnicas_estacao_trabalho htm 133 http intranet normas_internas aquisicao_equipamentos recomendacoes_tecnicas_rede htm ht
132. er stica citadas fossem comprovadas dever se ia disponibilizar a implementa o do modelo 1 na Web Os logs gerados nas navega es realizadas com o AntWeb teriam que passar por um processo de webmining e os resultados teriam que ser comparados com os resultados do processo de webming dos logs de navega es antes da implata o do AntWeb Se nestas compara es fosse comprovado uma diminui o de tempo em que o usu rio se conectou ao site um n mero menor de p ginas consultadas por sess o e outras caracter sticas das citadas acima seriam comprovados os benef cios do modelo 1 na navega o do usu rio 98 No entanto os experimentos realizados com o modelo 1 foram implantados junto ao site do departamento de Ci ncia da Computac o da Universidade de Brasilia CIC da seguinte forma O AntWeb foi colocado disponivel aos usu rios da Internet por um curto espaco de tempo entre os dias 4 e 10 de marco de 2003 e os poucos acessos que ocorreram neste periodo foram feitos por pessoas que tinham como objetivo satisfazer curiosidades a respeito de caracteristicas do sistema Por exemplo a forma como eram adaptadas as p ginas e a resposta do sistema ao ferom nio que o usu rio tinha acabado de deixar Os usu rios escolhiam p ginas arbitr rias para fazer seus testes de forma que n o poss vel considerar essas navega es como leg timas para fazer a avalia o do sistema da forma pretendida Ent o nossos experimentos foram limit
133. eran ended 18 11 1 5 Aplica es inspiradas no sistema formiga eenen 19 1 2 Uma vis o geral de World Wide Web aan 28 IL 3 Hipertexio 6 Hipermidia una 29 11 3 1 Um breve hist rico de hipertexto nennen onnneenen neen ennnee nerven eenn 30 13 2 Classes de Links a an ae 32 ILA Hiperm dia Adaptatie rn eu 32 4 1 Modelo do USUAAO ennen le 33 11 4 2 Ciclo cl ssico de adapta o nnn nnee nen eeen enneee nennen eenn 34 1 4 3 Navega o Adaptaliva essa set ta a Ik In 35 Capitulo III AntWeb para avalia o de estruturas de Web 38 iv IIl 1 Implementa o do Algoritmo de WebMining de Srikant 39 1 1 1 O processo de filtragem de informa es do arquivo de log 40 1 1 2 Os processos que envolvem a tabela de backtracks 41 IIl 2 Modelo AntWeb para avalia o de estruturas nn 44 1 2 1 Processo de mensura o de WebSites seen 45 II1 2 2 Simula o com um modelo simples nanne Re Re nerven eenn 45 1 2 3 Modelo de simula o AntWeb nnee eenen eneen eenn 46 I11 2 4 Algoritmo do AntWeb para avalia o de estruturas en 48 II1 2 5 Simula o usando o modelo AntWeb RA nn eenn 48 IIl 2 6 Aspectos da implementa o nnen nnn ee vennen ennen 49 NES Besultados OBUAOE annet teen ea 53 1 3 1 Situa o 1 Apenas 1 caminho de 5 links para o objetivo
134. essing trim this gt dataProcessing return value function getElement this gt undolsTag return this gt dataProcessing function undolsTag if isset this gt is Tag this gt undoType if this gt isTag this gt dataProcessing lt this gt dataProcessing gt unset this gt isTag function undoType if isset this gt type this gt undoName if this gt getType END this gt dataProcessing this gt dataProcessing unset this gt type 183 function undoName if isset this gt name this gt undoAtributes this gt dataProcessing this gt getName this gt dataProcessing unset this gt name function undoAtributes if isset this gt atributes this gt dataProcessing reset this gt atributes while list name value each this atributes this gt dataProcessing name value this gt dataProcessing trim this gt dataProcessing unset this gt atributes function test this gt setElement lt asdf if this gt isTag echo var_dump this this gt setElement lt asdf gt if this gt getType START9echo this gt getT ype if this gt getName ASDF echo this gt getName this gt setElement lt asdf gt if this gt getType endjecho this gt getType gt lt
135. etos projetos projeto_intranet projeto_seguranca htm http intranet projetos projetos projeto_intranet projeto_estagio_atual htm http bsbserv004 gestaoprojetos default htm http bsbserv004 gestaoprojetos abertura psq_registro_projeto asp http bsbserv004 gestaoprojetos perfil_profissional psq_tecnico asp http bsbserv004 gestaoprojetos capacidade_produtiva psq_capacidade_produtiva asp http intranet recursos_tecnologicos menu_recursos_tecnologicos htm 280 http intranet menus menu_relacao_equipamentos htm 153 http intranet recursos_tecnologicos relacao_equipamentos gerencia_filial relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos adm_financeiro relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos area_tecnica relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos fabrica_software relacao_maquinas htm http intranet recursos tecnologicos relacao equipamentos recursos humanos relacao maquinas htm http intranet recursos_tecnologicos relacao_equipamentos gerencia_comercial relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos adm_financeiro relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos recursos_humanos relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos recrutamento_selecao relacao_maquinas htm http intranet recursos_tecnolo
136. eturn lt exit erro sending tag do car parent getOut if lisset car or car lt this gt next gt giveBack car return return return car while car gt return return gt lt PHP class ElementExtractor extends Decorator var sendingNonTag var sendingTag var currentState function setNextToStates 174 this gt sendingNonTag gt setNext this gt next this gt sendingTag gt setNext this gt next function setExtractingNonTag amp p this gt sendingNonTag amp p function setExtractingTag amp p this gt sendingTag amp p function setCurrentState amp p this gt currentState amp p function getOut first parent getOut this gt next gt giveBack first if lisset this gt currentState if first lt this gt setCurrentState this gt sendingTag this gt setCurrentState this gt sendingNonTag elseif this gt currentState gt getDescription this gt sendingNonTag gt getDescription 175 this gt setCurrentState this gt sending Tag elseif this gt currentState gt getDescription this gt sendingTag gt getDescription if first lt this gt setCurrentState this gt sendingNonTag return this gt currentState gt getOut gt lt PHP class Wrapper extends Decorator function
137. f element gt isTag if element gt getType START if element gt getName A if isset this gt links element gt getAtribute HREF return true return false function amp getOut if lisset this gt links this gt links this gt linksSelector gt getOut unset this gt linksSelector 197 element amp Decorator getOut if lisset element return element out array array_push out element if this gt hasToHighlight element while element amp Decorator getOut array push out element if element gt isTag if element gt getType END if element gt getName A imagem this gt configuration gt data indicator_picture array_push out new HtmlElementParser lt img src imagem gt break return out gt lt PHP class Interval var start var end function getStart return this gt start function getEnd return this gt end function Interval s e this gt start s this gt end e lt PHP class PheromoneUpdater extends Decorator var intervalSetter var queriesPheromoneUpdater var pheromoneUpdaterTrigger var intervals array function shiftinterval list value each this gt intervals return value function pushinterval p array_push this gt intervals p 198 199 f
138. ferom nio e de adapta o da p gina O Cap tulo VI descreve os experimentos realizados por meio das simula es com estudos de casos envolvendo o segundo modelo do AntWeb adaptativo e as analises de resultados dos experimentos feitos E finalmente o Cap tulo VII apresenta a conclus o do trabalho com sugest es de trabalho futuro No anexo A descrevemos os algoritimos usados na implementa o do m todo de webmining de Srikant No anexo B listamos a estrutura do website da Politec Inform tica LTDA usada no experimento do AntWeb para avalia o de WebSites O anexo C cont m o c digo fonte da implementa o do modelo 1 do AntWeb adaptativo CAP TULO Il FUNDAMENTOS O objetivo deste cap tulo descrever as t cnicas e os conceitos que foram usados para a formaliza o e serviram como fundamento para o AntWeb ou seja a meta heur stica da formiga que a ess ncia do AntWeb as t cnicas de hiperm dia adaptativa que permitiram a jun o da meta heur stica da formiga com a navega o na Internet e outros conceitos relativos a Web como a tecnologia de hipertexto e hiperm dia ll 1 A meta heur stica da formiga e suas bases biol gicas A meta heur stica ACO desenvolvida por Marco Dorigo foi inspirada no comportamento das formigas reais para encontrar o caminho para seu alimento e otimizar sua trajet ria entre o formigueiro e a fonte de alimento 33 30 Foi proposta por Marco Dorigo em 1991 como uma abordagem de
139. gicos relacao_equipamentos area_treinamento relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos departamento_pessoal relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos medicina_trabalho relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos area_tecnica relacao_maquinas htm 135 http intranet recursos_tecnologicos relacao_equipamentos fabrica_projetos relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos atendimento_usuario relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos area_suporte relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos linha_digitalizacao relacao_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos fabrica_software relacao_maquinas htm http intranet menus menu_relacao_equipamentos_quadro_resumo htm 154 http intranet recursos_tecnologicos relacao_equipamentos gerencia_filial quadro_resumo_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos adm_financeiro quadro_resumo_maquinas htm http intranet recursos_tecnologicos relacao_equipamentos area_tecnica quadro_resumo_maquinas htm http intranet recursos tecnologicos relacao equipamentos fabrica software quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos recursos humanos quadro resumo maquinas
140. his gt configuration gt data deufaut page this gt url urldecode this gt url url parse_url this gt url if lisset url scheme this gt url http this gt url this gt processExcetion this gt url this gt putSlash function becomePageNotFound this gt setUrl this gt configuration gt data page_not_found this gt handle gt lt PHP class QueryCreateLogs extends Query function generateQuery return CREATE TABLE IF NOT EXISTS Logs dateTime DATETIME NOT NULL ip CHAR 15 NOT NULL gt lt PHP 169 url CHAR 255 BINARY NOT NULL PRIMARY KEY dateTime ip url host CHAR 255 BINARY maxLinksToShow TINYINT UNSIGNED numberLinks INT UNSIGNED threshold DOUBLE UNSIGNED suggestioni CHAR 255 BINARY pheromone1 DOUBLE UNSIGNED suggestion2 CHAR 255 BINARY pheromone2 DOUBLE UNSIGNED suggestion3 CHAR 255 BINARY pheromone3 DOUBLE UNSIGNED isAdaptable TINYINT class QueryCreateUpdates extends Query function generateQuery return CREATE TABLE IF NOT EXISTS Updates lastEnd DATETIME NOT NULL PRIMARY KEY lastEnd lastStart DATETIME dateTime DATETIME decayCoefficient DOUBLE UNSIGNED function CHAR 100 quantity BIGINT UNSIGNED iterationTime INT UNSIGNED 170 gt lt PHP class QueryCreateUrls extends Query
141. htm http intranet recursos tecnologicos relacao equipamentos gerencia comercial quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos adm financeiro quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos recursos humanos quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos recrutamento selecao quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos area treinamento quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos departamento pessoal quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos medicina trabalho quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos area tecnica quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos fabrica projetos quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos atendimento usuario quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos area suporte quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos linha digitalizacao quadro resumo maquinas htm http intranet recursos tecnologicos relacao equipamentos fabrica software quadro resumo maquinas htm http intranet menus menu relacao equipamentos quadro total htm 155 htt
142. htm http intranet recursos_humanos quadro_pessoal gerencia_filial_pessoal htm http intranet recursos_humanos quadro_pessoal gerencia_comercial htm http intranet recursos_humanos quadro_pessoal administrativo_financeiro htm http intranet recursos_humanos quadro_pessoal recursos_humanos recursos_humanos htm http intranet recursos_humanos quadro_pessoal recursos_humanos recrutamento_selecao htm http intranet recursos_humanos quadro_pessoal recursos_humanos treinamento htm http intranet recursos_humanos quadro_pessoal recursos_humanos departamento_pessoal htm http intranet recursos_humanos quadro_pessoal recursos_humanos medicina_trabalho htm http intranet recursos_humanos quadro_pessoal area_tecnica area_tecnica htm http intranet recursos_humanos quadro_pessoal area_tecnica fabrica_projetos htm http intranet recursos_humanos quadro_pessoal area_tecnica atendimento_usuario htm http intranet recursos_humanos quadro_pessoal area_tecnica suporte htm http intranet recursos humanos quadro pessoal area tecnica linha producao htm http intranet recursos humanos quadro pessoal fabrica software htm http intranet beneficios menu_beneficio htm http intranet beneficios projeto_viver_convenios_seguro_vida htm http intranet beneficios ppr_manual htm http intranet beneficios ppr manual 2000 htm http intranet beneficios ppr manual 1999 htm mailto ppr bsb politec co
143. html http bsbserv006 mrtg 10 61 254 1_3 html http www internettrafficreport com http intranet tabela_precos menu_tabela_precos htm http intranet tabela_precos tabela_referencial_precos_componentes htm http intranet tabela_precos tabela_referencial_precos_estacoes htm http intranet tabela precos tabela referencial precos impressoras htm http intranet tabela precos tabela referencial precos notebooks htm http intranet tabela precos tabela referencial precos scanner htm http intranet tabela precos tabela referencial precos servidores htm http intranet tabela_precos preco_software htm http www politec com br iexplorer curriculos curriculos_intranet htm http suporte mailto webmaster bsb politec com br http osbserv007 cyberdocs http intranet a_politec menu_a_politec htm http intranet a_politec apresentacao htm http intranet a_politec estrutura_organizacional estrutura_organizacional_politec htm http intranet a_politec matriz_filiais_endereco htm http intranet a_politec clientes relagao_clientes htm http intranet a_politec parceiros parceiros htm http www pcdocs com http www fulcrum com http www microsoft com brasil http www optika com http www eastmansoftware com http www maximal com http www staffware com http www kofax com http intranet a_politec produtos_servicos servicos servico
144. inks que v o decidir qual caminho o usu rio ir seguir para chegar p gina 9 s o os links que levam as p ginas 2A e 2C Nesta simula o 106 conforme salientado na Tabela 13 a p gina 2A recebeu 5 atualizac es de ferom nio de 0 2 ficando com 0 17 de ferom nio no final da itera o enquanto a pagina 2C recebeu 12 atualiza es de 0 5 ficando com 0 49 de ferom nio Usando a Equa o 19 obtemos os valores pia 2a 0 26 e piaac 0 74 ou Seja mesmo com usu rio seguindo caminhos errados a heur stica apontou a p gina 2C como melhor p gina para chegar ao destino 9 VI 2 2 A indica o de caminhos mais curtos Esta a principal hip tese que levou ao desenvolvimento do modelo 2 Considere a seguinte situa o mostrada na Figura 46 Existem dois caminhos para a p gina D no site sendo um caminho menor do que o outro 1A 0 5 0 5 2A 2B outras p ginas 3A 3B A Page D is the objective D Figura 46 Site com caminhos de tamanhos diferentes Neste exemplo 50 dos usu rios utilizam o menor caminho enquanto os outros 50 usam o maior Assim o AntWeb dever indicar o menor caminho com o passar do tempo Tabela 14 Simula es com caminhos de tamanhos diferentes Time 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 T 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 A 1 t 10 62 1A 2B A 2 t 0 86 TA 2B A 3 t 046 1A
145. intervals this gt pheromoneUpdater gt intervals this gt conection gt close gt lt PHP class QueryCreateUpdatesAux extends Query function generateQuery return create table UpdatesAux select max lastEnd lastEnd min lastStart lastStart max dateTime date Time 211 decayCoefficient function sum quantitv quantity iterationTime from Updates group by decayCoefficient function iterationTime order by lastEnd gt lt PHP class QueryDeleteUpdates extends Query function generateQuery return DELETE FROM Updates gt lt PHP class QuerylnsertUpdates extends Query function generateQuery return insert Updates select from UpdatesAux gt lt PHP class QueryDropUpdatesAux extends Query function generateQuery return drop table UpdatesAux gt 212 INDICE ANALITICO A Verdadeiro Links do browser ambiente 9 aplicag es do algoritmo formiga 19 Aspectos do comportamento da formiga real para encontrar o alimento 9 auto catalitico 9 10 C caminho 9 12 caminho alternativo 9 car ter coletivo 9 car ter descentralizado da atividade 9 Ciclo cl ssico de adaptac o 34 Classes de Links 32 Classificac o Adaptativa 36 col nia 7 9 E estigmergia 8 etologia 8 evaporac o de ferom nio 8 F ferom nio 7 8 9 17 18 formigas reais 7 H Hipermidia 29 H
146. ipermidia Adaptativa 33 L Links contextuais ou Hipertexto Links locais n o contextuais M meta heuristica modelagem de usuario Modelo do Usu rio m ltiplos agentes N natureza f sica da informa o Navega o O O experimento da ponte bin ria O modelo probabilistico o problema do caixeiro viajante Ocultac o Adaptativa Orientac o Direta otimiza o de problemas combinat rios P Par metros que permitem ajustar a formula aos dados experimentais ponte bin ria ponto central de intelig ncia problema do caixeiro viajante problemas dificeis de otimizac o S Simulag o com o obst culo 213 32 32 32 34 33 35 10 11 36 36 12 10 18 18 12 214 Suporte Orienta o Global 35 trilha 12 Suporte Orienta o Local 35 trilha de ferom nio 15 T throughput 39 215 BIBLIOGRAFIA A Colorni M Dorigo V Maniezzo e M Trubian Ant system for job shop scheduling Belgian Journal of Operations Research Statistics and Computer Science JORBEL 1994 34 39 53 B Bulinheimer e C Strauss Tourenplanung mit dem Ant System Forschungsberichte des Instituts f r Betriebswirtschaftslehre der UniversitEt Wien No 6 1996 B Bullnheimer R F Hartl e C Strauss A New Rank Based Version of the Ant System A Computational Study Central European Journal for Operations Research and Economics 7 1 1999 25 38 B Bullnheimer R F Hartl e C Strauss A
147. ir o de exemplo para o leitor entender melhor como a meta heur stica da formiga pode 21 ser usada de forma mais concreta 1 1 5 1 Problema do Caixeiro viajante O problema do caixeiro viajante um problema cl ssico da ci ncia da computa o e foi utilizado como teste para algoritmos formiga 27 O TSP pode ser definido da seguinte forma sejam n cidades todas interligadas formando um grafo fortemente conexo o objetivo encontrar o caminho mais curto que visite todas as cidades passando somente uma vez em cada uma delas A complexidade desse tipo de problema cresce exponencialmente com o n mero de cidades tratando se de um problema NP completo e consequentemente n o se conhece um algoritmo que forne a a solu o tima em tempo polinomial 17 Para problemas dessa esp cie abordagens heur sticas fornecem solu es satisfat rias O problema computacionalmente modelado por um grafo completo Cada n do grafo representa uma cidade e cada aresta o caminho entre duas cidades O comprimento de cada aresta representa a dist ncia entre as cidades A extens o de um trajeto ciclo dada pela soma dos comprimentos das arestas percorridas Al m do comprimento cada aresta possui tamb m uma determinada quantidade de ferom nio associada a esta Um total de m formigas move se entre as cidades em busca da solu o do problema ou seja do caminho mais curto Para garantir que uma formiga n o visite duas vezes a mesma
148. istas a elimina o de bugs E finalmente preciso fazer com que a implementa o do modelo 1 evolua e incorpore nova ideias Como todo sistema o AntWeb nunca vai ficar pronto de forma definitiva Em rela o ao Modelo 2 ele precisa ser implementado para que possa ser experimentado em situa es reais e para isso o c digo fonte da implementa o do modelo 1 pode ser util pelas classes definidas atrav s de orienta o a objetos VII 3 As dificuldades durante a pesquisa Pesquisar sobre como utilizar a meta heur stica da formiga na Web teve as dificuldades naturais que toda pesquisa tem mas tamb m teve suas dificuldades excepcionais e inesperadas A maioria destas dificuldades se relaciona ao desenvolvimento do projeto de implementa o Obter o c digo HTML de p ginas que n o t nhamos como saber previamente sua estrutura processar e retornar ao usu rio Web foi uma tarefa n o trivial N o havia ferramenta alguma dispon vel para esse pr posito Dessa forma 114 fomos obrigados a improvisar utilizando a linguagem PHP que apesar de n o ter sido feita para esses prop sitos uma linguagem poderosa e preencheu ainda que de forma forcada esta lacuna Muitas func es de baixo nivel foram desenvolvidas como por exemplo um parser HTML No periodo do desenvolvimento do sistema o departamento de Ci ncia da Computac o n o tinha um servidor web com a linguagem PHP disponivel para os alunos Fomos obrigados a com
149. iza es como a Equa o 4 Ao mesmo tempo mant m a caracteristica do sistema formiga como a evaporac o e adic o de ferom nio Em outras f rmulas o ferom nio com passar do tempo tende a crescer infinitamente No modelo 1 cada usu rio deixa a quantidade 1 de ferom nio quando passa por uma p gina Assim neste modelo a taxa de ferom nio de uma p gina ser o n mero m dio de acessos feitos a essa p gina em um periodo de tempo IV 6 3 Formas de destacar um link Neste trabalho quando um link possui relativamente uma significante quantidade de ferom nio a probabilidade de o usu rio clicar neste link dever ser aumentada usando a forma de apresentac o do link na p gina Por exemplo o link 73 poder ficar em uma fonte maior em relac o aos links anteriores poder aparecer uma figura ao lado do link ou qualquer outra forma de se destacar Seja qual a forma escolhida esta dever ter como requisito aumentar a probabilidade do usu rio usar o link Existem infinitas maneiras de se fazer isso sendo impossivel enumerar todas aqui A forma como o link vai ser destacado ficar como escolha do WebDesigner n o sendo o objetivo do AntWeb determina la No entanto salientamos que a abordagem escolhida dever ser analisada levando se em considera o fatores como agress o ao projeto visual inicial da p gina Precis o da sugest o ao usu rio Grau de atratividade para que o usu rio use o link e O conhecime
150. le ponto que ajudar a pr xima formiga a tomar o melhor caminho Isso funciona de forma circular resultando na melhora constante da solu o O efeito auto catal tico combinado com a avalia o impl cita da solu o o que produz o efeito desejado nos sistemas que utilizam o comportamento da formiga como inspira o 29 Uma caracter stica interessante do modo como a formiga acha o menor caminho que o sistema totalmente adapt vel a modifica es no ambiente Se por alguma raz o um determinado caminho que at ent o era o melhor deixar de s lo como por exemplo aparecer um obst culo naquele caminho o sistema de coopera o entre as formigas vai encontrar um outro caminho alternativo Outra observa o a ser feita que a intensidade de ferom nio funciona como uma meta heur stica ou seja quanto maior a quantidade de ferom nio naquela trilha melhor ser a trilha que permite formiga ter localmente informa es sobre o que fazer depois Note tamb m o car ter coletivo do modo como as formigas conseguem descobrir o melhor caminho A descoberta da solu o s poss vel se toda a col nia agir conjuntamente A atividade de uma nica formiga isolada n o possui intelig ncia suficiente para determinar o melhor caminho mas a atividade de toda uma col nia possui essa intelig ncia Observe tamb m o car ter descentralizado da atividade A intelig ncia esta distribu da uniformemente em todas as formigas N o exi
151. lema em quest o As formigas cooperam entre si para resolver problemas dif ceis de otimiza o como o problema do caixeiro viajante e a atribui o quadr tica 19 As formigas navegam por estados discretos de um determinado contexto Atraves de transic es entre estados vizinhos ela busca pela melhor soluc o do problema que geralmente o menor n mero de transic es possiveis para se chegar a um estado especifico partindo de outro No problema do caixeiro viajante por exemplo os estados discretos s o as cidades por onde o caixeiro passa e as transic es s o as ligac es entre as cidades Tal como as formigas reais as formigas artificiais ter o acesso a informa es apenas localmente As formigas artificiais s o similares as formigas reais em muitos aspectos por m s o enriquecidas com certas capacidades que n o s o encontradas nas formigas reais como As formigas artificiais vivem em um mundo discreto e seus movimentos s o transi es de um estado discreto a outro As formigas artificiais possuem um estado interno privado que contem a mem ria de a es passadas As formigas podem depositar uma quantidade de ferom nio que proporcional a qualidade da solu o encontrada A atualiza o do ferom nio n o necessariamente dependente do comportamento da formiga Por exemplo o ferom nio pode ser atualizado somente quando a formiga encontra alguma solu o diferente das formigas reais que atualizam o fero
152. lugar Neste modelo a taxa de ferom nio representada pela letra t e a p gina representada pela letra p da seguinte forma Tp IV 6 2 Atualiza o do ferom nio No modelo 1 a atualiza o de ferom nio ocorre em per odos uniformes cuja a dura o um par metro configur vel do sistema Nesta atualiza o s o feitas simultaneamente a evapora o e o aumento na taxa de ferom nio A atualiza o ocorre mesmo nas p ginas por onde n o passaram nenhum usu rio pois neste caso ocorre somente a evapora o do ferom nio A f rmula a ser usada no modelo 1 para atualiza o do ferom nio a seguinte T t l p 7 t 10 4p AT Equac o 12 72 onde v t Taxa de ferom nio depositado no link na p ginas ino tempo t p Taxa de evaporac o do ferom nio que ocorre em uma unidade de tempo AT Total de ferom nio a ser depositado na p gina i no intervalo correspondente Em nosso caso o numero de usu rios que usaram o link no durante o intervalo Esta formula equivalente a fazer uma m dia aritm tica ponderada entre o ferom nio adicionado com peso 2 2p e o ferom nio j existente no link com peso 2p como demostrado a seguir r t 1 p t t 1 P AT 2 A PAD PAT 2 T t 2 2p t 2970 2 T t Esta formula foi escolhida por fazer com que a taxa de ferom nio no link tenda a se estabilizar para a quantidade que esta sendo adicionada diferente outras equa es de atual
153. m nio a medida em que caminham Para aprimorar de maneira geral a efici ncia do sistema pode ser acrescida na formiga capacidades extras como retrocesso vis o de estados vizinhos dentre outros 11 1 5 Aplica es inspiradas no sistema formiga A seguir ser o apresentadas tabelas que listam as principais aplica es do algoritmo formiga 26 A Tabela 1 lista as aplica es de ACO para problemas est ticos de otimiza o combinatorial ou seja problemas no qual as caracter sticas n o mudam no decorrer do processo da procura da solu o Um exemplo cl ssico deste tipo de problema o TSP Tabela 1 Aplica es de ACO para problemas est ticos Problema Autor Ano Refer ncias Nome do Algoritmo Caixeiro viajante Dorigo Maniezzo amp Colorni 1991 33 30 32 AS 20 Gambardella amp Dorigo 1995 19 Ant Q Dorigo amp Gambardella 1996 27 28 21 ACS amp ACS 3 opt St tzle amp Hoos 1997 50 48 MMAS Bullnheimer Hartl amp Strauss 1997 3 ASrank Atribui o Maniezzo Colorni amp Dorigo 1994 55 AS QAP Quadr tica Gambardella Taillard amp Dorigo 1997 23 24 HAS QAP St tzle amp Hoos 1998 49 MMAS QAP Maniezzo amp Colorni 1998 54 AS QAP Maniezzo 1998 56 ANTS QAP Job shop Colorni Dorigo amp Maniezzo 1994 1 AS JSP scheduling Roteamento de Bullnheimer Hartl amp Strauss 1996 2 4 5 AS VRP ve culos Gambardella Tailard amp Agazzi 1999 22 HAS
154. m br http intranet beneficios projeto_viver_convenios_medico_hospitalar htm http intranet beneficios projeto_viver_convenios_odontologica htm http intranet beneficios projeto_viver_convenios_farmacia htm http intranet beneficios programa_incentivos_posgraduacao htm http intranet beneficios projeto_viver_convenios_imobiliaria htm http intranet beneficios projeto_viver_convenios_transporte htm http intranet beneficios projeto_viver_convenios_lazer htm http intranet beneficios projeto_viver_convenios_educacao htm http intranet beneficios projeto_viver_convenios_tickt htm mailto luciana bsb politec com br http intranet eventos calendario_eventos htm http intranet eventos outsourcing_resultados menu_outsourcing_resultados htm http intranet eventos outsourcing_resultados politec ppt http intranet eventos outsourcing_resultados outsourcing zip http intranet normas_internas menu_normas_internas htm http osbserv004 cnm menu_cnap menu_cnap htm http bsbserv004 cnm menu_cnap Apresenta ao_II htm http bsbserv004 cnm menu_cnap requisitos_II htm http bsbserv004 cnap menu cnap Plano 20de 20Estrutura o DOC 132 http bsbserv004 cnap menu cnap Plano 20de 20A o 20Emergencial DOC http bsbserv004 cnm menu_cnap Banco 20de 20Recursos 20Humanos htm http bsbserv004 cnm menu_cnap Area 20Comercial htm http bsbserv004 cnm menu_cnap Fabrica 20de 20
155. m link nesta solicita o o AntWeb grava tamb m no Log a URL dos links destacados e quantidade ferom nio que estava em cada um deles S o os dados contidos na tabela Log que servem de base para o c lculo do acr scimo de ferom nio nos links Ao projetarmos esta tabela procuramos colocar o m ximo de dados poss vel nela pois esta tabela pode ser usada no futuro para webmining Pheromone tabela respons vel por guardar as quantidades de ferom nio de cada p gina Se uma p gina n o possuir um registro correspondente a sua URL nesta tabela significa que a quantidade de ferom nio relacionado a p gina igual a zero Updates tabela respons vel por armazenar os dados correspondes s atualiza es de ferom nio feitas na tabela Pheromone Nesta tabela s o armazenadas a data e a hora em que foi feito a atualiza o e os valores dos par metros usados no processo de atualiza o como coeficiente de evapora o e tempo de itera o A fun o principal desta tabela registrar as altera es de par metros durante o ciclo de vida do sistema V 3 Os dois m dulos do Antweb O AntWeb foi desenvolvido em dois m dulos O m dulo de atualiza o do ferom nio arquivo index php e o m dulo para adapta o de p ginas arquivo pheromoneupdater php Os m dulos funcionam de forma independente para que o 92 m dulo de adaptac o de p gina d amp uma resposta mais r pida ao usu rio V 3 1 M dulo de atualizac o do ferom nio
156. m os caminhos mais curtos gastam menos tempo fazendo o percurso entre o ninho e a fonte de alimento do que as formigas que usam o caminho mais longo consequentemente a frequ ncia de formigas que passam pelos caminhos mais curtos maior do que a frequ ncia de formigas que passam pelos caminhos mais longos o que faz com que os caminhos mais curtos recebam mais atualiza o de ferom nio Esse efeito chamado por Dorigo 29 de avalia o impl cita da solu o Devido evapora o de ferom nio os caminhos mais longos desaparecer o ficando apenas os caminhos mais curtos Observe que as formigas inconscientemente comunicam se entre si indiretamente usando o ferom nio que elas deixam no ch o Essa forma de comunica o indireta entre os insetos chamada pela etologia de estigmergia 38 O que caracteriza o estigmergia de outras formas de comunica o 29 A natureza f sica da informa o corresponde a modifica es no ambiente A informag o somente amp acessivel localmente 11 1 1 Aspectos do comportamento da formiga real O procedimento das formigas para encontrar o caminho mais curto entre o ninho e a fonte de alimento auto catal tico ou seja um processo que se alimenta de seu pr prio impulso para se desenvolver Quando a formiga toma o melhor caminho baseado na quantidade de ferom nio contido na trilha correspondente ela est ao mesmo tempo contribuindo para melhorar a precis o da informa o naque
157. ma lista de 1000 links ao digitar algum t pico em algum site de procura Para auxiliar neste cen rio este trabalho prop e uma heur stica inspirada no comportamento das formigas que serve para guiar o usu rio da Internet durante a navega o Apesar das formigas possu rem as limita es de vis o j citadas elas conseguem achar com muita efici ncia a fonte de alimento al m de determinar o menor caminho entre o ninho e esta A formiga quando caminha deixa uma subst ncia chamada ferom nio no ch o As formigas ao procurarem o caminho que devem seguir optam por aquele em que o grau de ferom nio est mais forte Com o passar do tempo o ferom nio das trilhas em desuso evapora ficando apenas as trilhas que s o mais interessantes para a col nia Este um processo de trabalho em equipe em prol da col nia como um todo Uma s formiga com suas limita es de vis o n o seria capaz de achar o caminho para o alimento com a mesma efici ncia de um trabalho em grupo das formigas da col nia Diferente das formigas os usu rios da Internet n o possuem nenhum tipo de comunica o grupal durante o processo de navega o Cada um conta somente consigo mesmo para alcan ar seu objetivo A id ia deste trabalho contribuir para a mudan a deste quadro propondo um sistema baseado no ferom nio para que os usu rios da Internet realizem um trabalho coletivo em prol de toda comunidade estabelecendo um canal de comunica o indireta entre
158. mente o algoritmo cria a lista P e a inicializa como na primeira abordagem Em seguida percorre todos os registros da parti o ponderando as p ginas em P com o beneficio correspondente A vari vel m representa o n mero de atributos preenchidos de LocalizacaoEsperadai a N Como n s definimos um n mero de atributos suficientemente grande prevendo uma quantidade m xima de localiza es esperadas quando o visitante n o visitar uma quantidade suficiente para preencher todos os atributos que certamente ser o a maioria dos casos existir o atributos no registro em quest o que estar o em branco e estes estar o sempre direita dos atributos preenchidos n o havendo necessidade ent o de percorre los O algoritmo ent o percorre todos os registros e para cada registros todos os atributos de LocalizacaoEsperadai a m ponderando cada p gina na lista P correspondente ao valor do atributo em quest o Ap s percorrer todos os registros e obter as pondera es de cada localiza o esperada come a a segunda etapa que determinar a localiza o esperara recomendada O algoritmo ap s inferir os pesos de todas as p ginas em P somente considera localiza o esperada a p gina com maior peso Para inferir a pr xima localiza o esperada recomendada o algoritmo apaga todas as localiza es esperadas correspondentes a localiza o esperada que acabamos de encontrar da parti o e as localiza es esperada posteriores a ela no
159. modelo 1 observamos que ele cumpriu seu principal objetivo de permitir o estudo entre as diferen as entre o comportamento da formiga real e a navega o do usu rio na Internet Apesar de n o ter sido poss vel dispor a implementa o do modelo 1 na Web e obter dados de navega o de forma satisfat ria pudemos concluir que a avalia o impl cita da solu o n o ocorre na navega o do usu rio usando o modelo 1 fazendo navega es fict cias 115 No papel de ajudar o usu rio na navega o o modelo 1 do AntWeb adaptativo foi inutilizado pela sua incapacidade de indicar o menor caminho Apesar de que mesmo sem a avalia o impl cita da solu o seja poss vel que o modelo 1 traga benef cios estes mesmos benef cios podem ser alcan ados sem a meta heur stica da formiga simplesmente indicando se os links para as p ginas vizinhas mais populares Apesar disto o modelo 1 foi fundamental para a constru o do modelo 2 que se mostrou eficiente no papel de otimizar a rota do usu rio Diferente do modelo 1 o modelo 2 mostrou se eficiente na condu o do usu rio pelo menor caminho at s p ginas destino nos experimentos realizados Mesmo em situa es com caracter sticas que prejudicam seu processo de aprendizagem da estrutura do site como no caso em que os usu rio tomam trajet rias erradas para suas p ginas destino e o cache de p ginas do browser do usu rio esteja habilitado o modelo 2 cumpriu seu objetivo Mas
160. mos que o Ant Web adaptativo torne esse mundo virtual que surgiu um mundo melhor para as pessoas viverem tornando menos rdua a tarefa de encontrar o que se quer na Web Esperamos tamb m que os usu rios que utilizarem o AntWeb tomem consci ncia de que n o est o sozinhos neste mundo virtual que existem pessoas que como ele procuram sua fonte de alimento para se alimentarem de conhecimento de divers o de tudo que a Internet pode oferecer VIL 1 Satisfa o dos objetivos Como foi exposto no Cap tulo o principal objetivo deste trabalho o estudo da aplica o da meta heur stica da formiga na navega o da Internet ou seja o desenvolvimento do AntWeb adaptativo baseado na met fora do comportamento das formigas possibilitando a implementa o de sistemas que procure orientar o usu rio na navega o da Internet Assim acreditamos que atingimos os objetivos propostos ao passo que 112 houve um desenvolvimento consider vel no que diz respeito a adaptac o da meta heuristica da formiga para a navegac o na Internet Foram realizados estudos para determinar diferencas entre a peregrinac o da formiga real e a navegac o na Internet atrav s da implementa o do modelo 1 tamb m foi desenvolvido um modelo matem tico adaptado do Ant System que permite conduzir os usu rios pela Web o qual chamamos de modelo 2 Foram feitos estudos de caso para an lise do modelo 2 Em suma o AntWeb adaptativo foi desenvolvido e agora
161. mostra como amp calculado o acr scimo de ferom nio feito separadamente por cada formiga 81 l dik T gt An p a por CO b 0 seig T p Equa o 17 Onde T X p o conjunto de p ginas visitadas pela formiga k na itera o p para chegar a p gina d nI p a dist ncia da pagina i at a p gina dem T p e o um par metro que determina o quanto a dist ncia entre e d vai influenciar no decremento do ferom nio normalmente igual a 1 Por exemplo se T p P1 P2 P3 ent o Atp p 0 336 Atpo 0 50 e ATpa PH 6 A adi o de ferom nio em cada p gina feita de acordo com o esquema abaixo d Ti p l p t p p Arf p Equac o 18 Onde p 0 1 o coeficiente de evapora o Semelhante ao modelo 1 essa f rmula equivalente a uma m dia continuada fazendo com que o ferom nio dos links tendam a uma estabiliza o IV 7 3 Extens o do modelo para mais de um destino No modelo 2 quando o usu rio est procurando sua p gina usando o AntWeb como se ele estivesse seguindo o cheiro de sua p gina e seguindo os links na qual o cheiro de sua p gina fosse exalado de forma mais acentuada No modelo b sico quando se est guiando o usu rio para apenas um destino como se somente uma p gina pudesse exalar seu cheiro ficando todas as outras inodoras Assim ficando somente a p gina que o usu rio deseja encontrar exalando cheiro basta o usu rio seguir o cheiro que
162. mpo o ferom nio vai sendo adicionado nos dois caminhos de forma proporcionalmente igual Como a formiga escolhe um caminho devido a grande quantidade de ferom nio toda migra o da formiga se concentrar cada vez mais em apenas um caminho apesar de que neste experimento os dois caminhos sejam de tamanhos iguais Ap s uma breve oscila o nos primeiros minutos as formigas passaram a convergir para o caminho mais alto Este experimento mostra tamb m que a probabilidade da formiga escolher seu caminho proporcional a quantidade de ferom nio Segundo 26 o modelo probabil stico mais compat vel com as observa es experimentais o seguinte U k U k L k P m Equac o 1 12 P m 1 Pu m Equac o 2 Onde Pi m Probabilidade da formiga m escolher a parte de baixo da ponte Pu m Probabilidade da formiga m escolher a parte de cima da ponte Lm N mero de formigas que usaram a parte de baixo depois de m formigas usarem a ponte Um N mero de formigas que usaram a parte de cima depois de m formigas usarem a ponte keh Par metros que permitem ajustar a formula aos dados experimentais Neste modelo assumida que a quantidade de ferom nio em um caminho proporcional a quantidade de formiga que o utilizou Isto porque n o houve tempo suficiente no experimento para que acontecesse uma evapora o efetiva de ferom nio 1 1 3 Simula o com o obst culo Esta simula o
163. n improved ant system algorithm for the vehicle routing problem Technical Report POM 10 97 Institute of Management Science Yniversity of Vienna Accepted for publication in the Annals of Operations Research 1997 B Bullnheimer R F Hartl e C Strauss Applying the ant system to the vehicle routing problem In I H Osman S VoB S Martello and C Roucairol editors Meta Heuristics Advances and Trends in Local Search Paradigms for Optimization Kluwer Academics 1998 109 120 C G Ralha A framework for dynamic structuring of information PhD Dissetation School of Computing University of Leeds 1996 D Costa e A Hertz Ants can colour graphs Journal of the Operational Research Society 48 1997 295 305 D G Carmo Neto Metodologia Cient fica para Principiantes 3 ed Salvador BA American World University Press 1996 216 9 D Subramanian P Druschel e J Chen Ants and reinforcement learning A case study in routing in dynamic networks In Proceedings of IJCAI 97 International Joint Conference on Artificial Intelligence Morgan Kaufmann 1997 832 838 10 E Bonabeau F Henaux S Gu rin D Snyers P Kuntz e G Th raulaz Routing in telecommunication networks with Smart ant like agents telecommunication applications In Proceeding of IATA 98 Second Int Workshop on Intelligent Agents for Telecommunication Applications Lectures Notes in Al Springer Verlag 1437 1998 11 E
164. namorados a p gina mais popular do site seja a p gina que os usu rios usam para comprar flores Assim neste per odo os usu rios que est o procura de flores enfrentam o problema de encontrar a p gina que vende flores na rede de hiperm dia do site Desta forma imaginou se um sistema adaptativo que criasse automaticamente um banner na home page do site para levar o usu rio mais r pido a p gina mais popular no nosso exemplo do supermercado a p gina que vende flores Um sistema como este em nosso exemplo seria til para a maioria dos visitantes que est o acessando o site naquele per odo presumindo se claro que a maioria est procura de flores como se os usu rios anteriores tivessem deixado uma trilha de ferom nio nas p ginas que visitaram e as p ginas mais populares tivessem ficado com mais ferom nio do que as outras O banner na home page representaria o ferom nio atraindo os novos visitantes Continuando nosso racioc nio no exemplo do site de um supermercado imagine que passado o per odo do dia dos namorados a p gina de flores deixaria de ser a mais visitada Ent o como j n o h mais tantas atualiza es de ferom nio na p gina de flores o ferom nio deixado pelas visitas anteriores evaporaria fazendo com que o sistema retirasse automaticamente o banner para a p gina de flores que est na home page 62 Observe que nesta primeira concep o ainda n o havia a id ia de conduzir o usu rio atr
165. nanceira htm http intranet recursos_humanos pessoal endereco_telefones recursos_humanos recursos_humanos htm http intranet recursos_humanos pessoal endereco_telefones recursos_humanos recrutamento_selecao htm http intranet recursos_humanos pessoal endereco_telefones recursos_humanos treinamento htm http intranet recursos_humanos pessoal endereco_telefones recursos_humanos departamento_pessoal htm 131 http intranet recursos_humanos pessoal endereco_telefones recursos_humanos medicina_trabalho htm http intranet recursos_humanos pessoal endereco_telefones coordenador_contrato area_tecnica area_tecnica htm http intranet recursos_humanos pessoal endereco_telefones coordenador_contrato area_tecnica atendimento_usuario htm http intranet recursos_humanos pessoal endereco_telefones coordenador_contrato area_tecnica consultoria htm http intranet recursos_humanos pessoal endereco_telefones coordenador_contrato area_tecnica desenvolvimento htm http intranet recursos_humanos pessoal endereco_telefones coordenador_contrato area_tecnica linha_producao htm http intranet recursos_humanos pessoal endereco_telefones coordenador_contrato area_tecnica suporte htm http intranet recursos_humanos pessoal endereco_telefones fabrica_software fabrica_software htm http intranet recursos_humanos pessoal endereco_telefones coordenador_contrato coordenador_contrato htm http intranet menus menu_quadro_pessoal
166. ndo neste momento Como o algoritmo sabe quando uma p gina alvo ou n o se a tabela de log n o informa o tempo que o visitante gastou visitando a p gina Depois de determinarmos o valor threshold para calcularmos a quantidade de tempo que o visitante gastou visitando uma p gina usamos o seguinte m todo 1 Obtemos a hora de acesso da p gina na qual queremos descobrir o tempo de acesso 2 Obtemos a hora de acesso da p gina seguinte p gina na qual queremos descobrir o tempo de acesso 121 3 Subtraimos os dois hor rios e obtemos o tempo gasto Portanto o tempo gasto em um acesso P dado pela relac o Tempo P DataHora Pi 1 DataHora P Equac o 20 Seja a fun o TempoVisita a fun o que retornar o tempo que o visitante gastou visitando a p gina correspondente ao registro corrente da Tabela de Log Esta fun o ser invocada no momento em que estiver sendo executado o segundo particionamento Portanto o programa que estar montando a parti o provavelmente estar acessando fisicamente a tabela de log e provavelmente tamb m esta tabela estar ordenada pela sequ ncia de visita Assim esta fun o poder ser definida da seguinte forma considerando a abordagem orientada a objetos usada pela maioria das linguagens atuais TempoVisita Inicio Tempol TabelaLog Hora Valor abelaLog Pr ximo Tempo2 TabelaLog Hora Valor TabelaLog Anterior Retorne Tempo2 Tem
167. ninho ela deposita no ch o o ferom nio marcando assim o caminho de ida e volta usado por ela As formigas possuem a capacidade de farejar o ferom nio permitindo que elas percebam o ferom nio deixado por outras formigas Por instinto a formiga tende sempre a andar na direc o em que o ferom nio esta apontando fazendo com que elas sigam os rastros depositados anteriormente no ch o Enquanto caminham as formigas depositam mais ferom nio no caminho utilizado reforcando ainda mais o rastro que est sendo seguido Assim formam se as trilhas de ferom nio que ser o usadas por todas as formigas para indica o do caminho entre a fonte de alimento e o ninho As formigas podem formar mais de um caminho entre a fonte de alimento e o ninho O processo o seguinte aleatoriamente as formigas se desviam um pouco do caminho original e como toda formiga deixa ferom nio no ch o ela cria uma nova trilha de ferom nio formando caminhos alternativos aos caminhos originais Dessa forma v o aumentando as op es de trajetos que a formiga pode seguir para chegar ao seu objetivo Quando h mais de uma trilha a seguir a formiga tende a escolher a trilha que tem a maior concentra o de ferom nio O ferom nio com o passar do tempo se evapora diminuindo a taxa de ferom nio nas trilhas Quando uma trilha de ferom nio n o utilizada a tend ncia que essa trilha desapare a permanecendo apenas as trilhas ativas Obviamente as formigas que utiliza
168. no tempo 2 Na Figura 11 a formiga 1v j alcan ou a trilha original que estava do outro lado do obst culo enquanto a formiga 1i esta passando para o outro lado do obst culo Nesse momento tamb m aparecem as formiga 2i e 2v nos pontos que n s fixamos na trilha original 17 Figura 11 Estado da simulac o no tempo 3 Na Figura 12 as formiga 2i e 2v tem que escolher qual caminho seguir Para a formiga 2i a probabilidade de escolher um caminho ou outro continuam sendo de 50 cada um mas para a formiga 2v a probabilidade de escolher o caminho de baixo que o mais eficiente tornou se maior devido ao ferom nio depositado no caminho de baixo Dessa forma podemos ver que a tend ncia a quantidade de ferom nio no caminho de baixo se tornar cada vez maior Figura 12 Estado da simulac o no tempo 4 A Figura 13 mostra trilha de ferom nio que tende a se formar com o 18 passar do tempo Esta trilha mostra o caminho que as formigas seguir o tal como LE Figura 13 Trilha de ferom nio formada na simula o ilustrado na Figura 14 FE Se Me AE Spa Me FE SA VE Se AL VE Se He Figura 14 As formigas seguem a trilha de ferom nio formada 11 1 4 A vers o artificial da Formiga Na vers o artificial da formiga proposta por Marco Dorigo 29 as formigas s o componentes de software e as taxas de ferom nio s o valores continuos associados a arestas de um grafo que representa o ambiente para o prob
169. ntinue usando o AntWeb Sender respons vel por enviar via Internet o c digo HTML da p gina adaptada para o browser do usu rio que a solicitou Log respons vel por fazer o registro de log na tabela logs correspondente ao processo de adapta o As classes Decorator e DecoratorEnd fazem parte da defini o do pattern Decorator As demais classes s o as mesmas apresentadas na descri o do m dulo de atualiza o de ferom nio 96 CAPITULO VI EXPERIMENTOS Neste capitulo s o apresentados os experimentos feitos com o modelo 1 e o modelo 2 do AntWeb adaptativo Os experimentos envolvendo o modelo 1 foram feitos usando a implementac o descrita no Capitulo V O modelo 2 n o foi implementado e seus experimentos foram feitos usando tabelas com dados de navega o fict cia VI 1 Experimentos com o modelo 1 O modelo 1 simples e de f cil entendimento para a maioria das pessoas Estabelecemos alguns par metros de navega o do usu rio usando o AntWeb a saber Condu o dos usu rios s p ginas mais populares Isto uma consequ ncia bvia uma vez que no modelo 1 o ferom nio nada mais do que a m dia continuada da quantidade de acessos ocorridos nos intervalos estabelecidos pelo par metro iteration time do sistema Por exemplo no caso dos experimentos descritos abaixo este par metro igual a 30 segundos Ent o a quantidade de ferom nio que vai prevalecer para uma determinada p gina ser a m dia entre a
170. nto dos usu rios que utilizaram o site Dependendo da abordagem escolhida o algoritmo para atualiza o da p gina tamb m mudar A seguir apresentaremos a analise de tr s abordagens b sicas para o destaque dos links Essas abordagens podem ser combinadas dependendo do problema em quest o Em nossa implementa o foi utilizado a abordagem do m nimo significativo por ser mais elaborada 74 IV 6 3 1 Abordagem do valor do ferom nio Esta uma lista hier rquica de ke loj x File Edit View Go Communicator Help yo AAS ASA ER ab Bookmarks A Location ET What s Related linki 1 5 de feromonio link2 2 1 de feromonio link3 0 0 de feromonio link4 4 0 de feromonio EP JER 9E HO Figura 32 abordagem do valor do ferom nio Nesta abordagem ser informado o n mero exato de ferom nio contido no link junto com o texto do link Esta t cnica classificada na hiperm dia adaptativa como Anota o 18 Esta abordagem tem como desvantagem o fato do usu rio ter que saber o que o ferom nio mas apesar disto mesmo que ele n o saiba o que o ferom nio ele vai ter uma orienta o num rica precisa apesar de n o ter o conhecimento do significado real dos valores O algoritmo para esta abordagem est resumido a seguir Obtenha dados para calcular ferom nio Atualize as taxas de ferom nio Para cada p gina Fa a In cio Modifique cada link para que mostre a quantidade
171. nyers e P Kuntz Adaptative agent driven routing and load balancing in communication networks Technical Report RR 98001 IASC Department Intelligence Artificielle et Sciences Cognitives ENST Bretagne Accepted for publication in the Journal of Complex Systems 1998 35 M S Chen J S Park and P S Yu Data mining for path traversal patterns in a web environment In Proc of the 16th International Conference on Distributed Computing Systems 1996 385 392 36 M V P Dib W M Teles e V M de Andrade Mining weblogs para melhorar a organiza o de websites Semin rio apresentado na Universidade de Brasilia 2001 37 P Brusilovski Methods e Techniques of Adaptive Hypermedia User Modeling and User Adapted Interaction n 2 3 Special issue on adaptive hypertext and hypermedia 6 1996 87 129 38 P P Grass La reconstruction du nid et les coordinations inter individuelles chez Bellicositermes natalensis et Cubitermes sp La theorie de la stigmerge Essai d interpretation des termites constructeurs In Ins Soc 6 1959 41 83 39 R E Horn Mapping Hipertext the lexington Institute 1989 40 R Michel and M Middendorf An island model based ant system with lookahead for the shortest superseguence problem In A E Eiben T Back 220 M Schoenauer and H P Schwefel editors Proceedings of PPSN V Fifth International Conference on Parallel Problem Solving from Nature Springer Verlag 199
172. o Bencontrouobj amp tempoDownload int iMpercorreul BtempoVisita int ListaRetrocessos Bo EIS from AntWeb m oveFormiga Ds PvoltaF ormiga Bet ink WPListaRetrocessos Ehpad h PP ush ostraCaminhoFormiga addLink PP op gecalculaProbabilidadel ER PMeromonioDepositado iRgetProxima getNumPagVisit PegetFeromonio PegetNumLinks PatualizaFeromonio Figura 24 Diagrama de classes de entidade TelaCadastro from AntWeb WTelaCadastrol E binitl FM enuFileExit_actionPerformed processWindowEvent PidbTextField5_focusGained idbTextField1_focusGained idbTable1_foc us Gained Principal from AntWeb GWP rincipall main TelaParametros from AntWeb WTela Parametros Tela Principal from AntWeb Ms etControladorColonia MTelaP rincipal Miinit PaditemMenu 7 PactionP erformed MbtE xecutar_actionP erformed GWmostraResultados impaResultados escolheArquivoSaida Pm ontaLista ComboBox1 actionPerformed ControladorColonia from AntWeb tempo int amp ControladorColonia MsetTelaP rincipal MexecutaSimulacao MoravaResultados Pipad rpad mostraCaminhoColonia Ms etArquivoS aida actionPerformed Parametros from AntWeb alfa double beta double Bro double GWP arametros
173. o P ginas ndices s o p ginas que servem apenas para levar o usu rio at a uma p gina Neste caso a p gina identificada como uma p gina destino atrav s da verifica o do tipo de p gina Threshold Em sites que n o poss vel a identifica o de p ginas de acordo com o primeiro m todo feito a verifica o do tempo em que o a formiga permaneceu na p gina Se o tempo for acima de um threshold a p gina considerada a p gina destino do usu rio Aqui considerado tamb m a possibilidade do usu rio ter por exemplo ficado longe do seu computador e alguma p gina que na verdade n o p gina destino ter sido eleita p gina destino Assim devem ser considerados dois threshold em que a p gina para ser eleita p gina 83 destino deve ter o tempo acima do threshold 1 e deve ficar abaixo do threshold 2 IV 7 5 O algoritmo para atualizac o do ferom nio A atualizac o do ferom nio ser feita usando se uma tabela de log que funcione de forma similar ao arquivo log que se encontra no servidor web 44 ou o pr prio arquivo de log O algoritmo amp o seguinte 1 Particione o log por visitante Ordene o log por ID do usu rio ou Particione o log por hashing com o ID do usu rio e ordene cada partic o separadamente Varra a tabela extraindo seg ncias de p ginas para cada ID visitante 2 Ordene cada partic o pela hora em que cada p gina foi acessada 3 Para cada visitante particione de forma qu
174. o a ser usada Os links do browser devem ser levados em considera o principalmente na analise do log de acesso obtido do servidor web uma vez que informa es de navega o podem ser distorcidas devido aos recursos do browser do usu rio Por exemplo as a es de retrocesso uso do bot o voltar n o aparecem no log devido ao cache de p ginas que a maioria dos browsers possuem 1 4 Hipermidia Adaptativa A hipermidia Adaptativa foi a soluc o encontrada para unir a meta heuristica da formiga com a navegac o na Internet e fazer com que o usuario fosse 33 atraido pelo ferom nio na abordagem do AntWeb adaptativo Para a melhor escolha das t cnicas de HA disponiveis e o melhor uso destas durante a implementac o foi feito uma pesquisa na literatura Esta se o a compila o das principais informa es a respeito de tema extra das da literatura relevantes ao AntWeb Hiperm dia Adaptativa segundo Brusilovsky 37 a rea de ci ncia da computa o que se ocupa do estudo e desenvolvimento de sistemas arquiteturas m todos e t cnicas capazes de promover a adapta o de hiperdocumentos e hiperm dia em geral s expectativas necessidades prefer ncias e desejos de seus usu rios O AntWeb usa t cnicas inerentes aos sistemas de HA do tipo navega o adaptativa usando as para direcionar a navega o do usu rio no hiperespa o Al m dos sistemas do tipo navega o adaptativa existem tamb m os sistema do ti
175. o criado linksGuider gt setConfiguration this gt configuration linksHighlighter gt setConfiguration this gt configuration decoratorBuilder gt setNext sender decoratorBuilder gt setNext unWrapper decoratorBuilder gt setNext linksGuider decoratorBuilder gt setNext dissolver decoratorBuilder gt setNext linksHighlighter decoratorBuilder gt setNext this gt htmIParser antWeb gt setSender sender this gt buildDecoratorLinksSelector linksHighlighter gt setLinksSelector this gt linksSelector function buildLog amp antWeb queryInsertLog new QuervinsertLog if lisset this gt linksSelector exit Links selector not built queryInsertLog gt setLinksSelector this gt linksSelector if lisset this conection or lisset this gt configuration or lisset this gt url exit core not built gt 160 querylnsertLog gt setConection this gt conection queryInsertLog gt setConfiguration this gt configuration queryInsertLog gt setUrl this gt url querylnsertLog gt setAdaptabilityChecker this gt adaptabilityChecker antW eb gt setLog querylnsertLog function buildAntWeb amp antWeb lt PHP class QueryExecuter function pushQuery amp p this gt buildCore antWeb this gt buildDBCreator antWeb this gt buildHimlParser antW eb this gt buildDecoratorPageAdapter antW eb
176. o de corte para as localizac es esperadas A func o colocar em R somente as localizac es recomendas que possuirem peso maior ou igual a S O peso amp uma heuristica de quanto recomendada esta localizac o para esta p gina Quanto maior o peso mais recomendada amp a localizac o Finalmente o algoritmo mostra as localizac es recomendadas Este algoritmo teria uma saida como esta p gina 1 p gina 2 peso 3 7 p gina 3 peso 2 5 p gina 4 peso 2 p gina 5 p gina 6 peso 3 p gina 7 peso 2 3 Onde p gina 1 e p gina 5 seriam p ginas de conte do e as p ginas de 2 3 4 6 e 7 as p ginas indice que deveriam ter algum link para as p ginas 1 e 5 respectivamente As tr s abordagens de algoritmos para a func o Achelocalizac esRecomendas R ser o descritas a seguir Abordagem somente o primeiro Este algoritmo considera apenas os valores de atributo Localiza oEsperada1 para inferir qual a melhor localiza o da pagina em quest o 124 SomentePrimeiro S R Inicio Crie lista P com a estrutura P gina Peso Coloque em P todas as p ginas indice de Tabela de P ginas e com Quantidade 0 Para i de 1 at n Fa a onde n o n mero de p ginas em P Inicio Conte quantas vezes P i aparece no atributo Localizac esEsperadasl na partic o P i Peso Quantidade obtida acima Inclua P em R Fim Ordene R por pelo valor de Peso Fim Esta a abordagem mais simples de todas Este m todo
177. o de destacar os links ao inv s de simplesmente mostra o ferom nio 76 IV 6 3 3 Abordagem do m nimo significativo MY Esta uma lista hier rquica de t 5 x File Edit View Go Communicator Help CERNE Ed Bookmarks A Location GE What s Related af D JER TAE Figura 34 Abordagem do minimo significativo Esta a abordagem mais elaborada de todas e foi a abordagem usada no projeto WebWatcher 47 Nesta abordagem o link s ser destacado se a quantidade de ferom nio associada a ele estiver acima de um m nimo significativo Em outras palavras o link s ser destacado se possuir uma quantidade significativa de ferom nio independente da sua posi o no ranking dos links com maior ferom nio Assim se um link pouco usado e n o tem a quantidade m nima de ferom nio ele nunca destacado mesmo que seja o link mais usado da p gina Por outro lado se a p gina estiver sendo muito frequentada uma quantidade enorme de links ter o que ser destacados Para evitar este problema uma quantidade m nima de links a ser destacado ser estabelecida em cada p gina que no nosso caso s o tr s O algoritmo listado a seguir 77 Obtenha dados para calcular ferom nio Atualize as taxas de ferom nio Para cada p gina Fa a In cio Pegue os 3 links com a maior taxa de ferom nio Para cada um desses links Fa a Inicio Se taxa de ferom nio gt minimo significativo
178. o durante o tempo de simula o O ndice que indicava o quanto a estrutura do WebSite era boa o throughput era o n mero de visitantes que alcan aram sua p gina alvo por unidade 45 de tempo relacionadas ao total de visitantes Durante a simulac o medida que iam caminhando entre os links as formigas depositavam ferom nio neles O simulador conseguia o efeito auto catalitico fazendo com que a probabilidade da formiga escolher um determinado link em uma p gina fosse maior quando este link possuisse bastante ferom nio o que fazia com que o total de formigas que chegasse na sua p gina objetivo aumentasse 11 2 1 Processo de mensurac o de WebSites O processo consistia em duas etapas 1 A execuc o do software que implementou o trabalho do Skirant Nesta etapa eram obtidas as taxas de ferom nio iniciais que era a probabilidade do usu rio escolher determinado link considerando determinada p gina objetivo 2 A execuc o do simulador propriamente dito Depois de feita as devidas modificag es sugeridas pelo algoritmo de Skirant o simulador era usado para avaliar a efici ncia da modificag o que era feita atrav s do throughput 11 2 2 Simula o com um modelo simples Neste experimento 25 o tempo inicial de simula o igual a zero e o intervalo de gera o de visitantes igual a 5 segundos Cada vez em que gerado um visitante tamb m gerada uma vari vel aleat ria A probabilidade PA 24 para o visitant
179. oi um banner colocado na p gina inicial do Site do banco Este banner funcionou como um ferom nio atraindo a formiga O banner levou o visitante diretamente a p gina que ele queria que similar ao que acontece quando a formiga descobre o menor caminho entre a fonte de alimento e o ninho Existem muitos trabalhos no sentido de melhorar a estrutura de websites 35 e 44 mas eles possu am a limita o de n o fornecerem um par metro de avalia o das modifica es Este AntWeb para avalia o de estruturas Web preencheu esta lacuna vazia Para isto o modelo simulava a visita o do website baseado no comportamento da formiga Um conceito muito importante neste modelo o throughput ou seja o n mero de visitantes que alcan aram suas p ginas objetivo por unidade de tempo relativa ao n mero total de visitantes O throughput era o indice que indicava a efici ncia da organiza o do website At o momento o modelo considerava apenas o visitante que tinha como objetivo uma p gina Para provar a efici ncia do modelo foi constru do um simulador O simulador tendo a estrutura do WebSite j montada em seu banco de dados criaria formigas virtuais que seriam equivalentes aos visitantes do WebSite que navegariam pela estrutura do WebSite escolhendo os links a ser seguidos de forma aleat ria No final da simula o o programa apresenta o total de formigas que foram criadas e o total de formigas que conseguiram chegar at a p gina alv
180. omacao tecnologia doc http bsbserv004 cnap menu cnap paes especificacao para automacao controle de despesas doc http bsbserv004 cnap menu cnap gerencia de projetos doc http bsbserv004 cnap menu cnap avaliacao tecnica proposta doc http bsbserv004 cnap menu cnap proposta tecnica comercial exemplo doc http bsbserv004 cnap menu cnap relatorio de acompanhamento de projeto htm http bsbserv004 cnap menu cnap documento de gestao 01 xIs http bsbserv004 cnap menu cnap documento de gest o 02 xIs http bsbserv004 cnap menu cnap documento de gest o 03 xls http bsbserv004 cnap menu cnap 7 de junho htm http bsbserv004 cnap menu cnap relatorio 11 07 2000 doc http bsbserv004 gestaoprojetos http bsbserv004 gestaoprojetos abertura psq_registro_projeto asp http bsbserv004 gestaoprojetos perfil_profissional psq_tecnico asp http bsbserv004 gestaoprojetos capacidade_produtiva psq_capacidade_produtiva asp http intranet projetos linha digitalizacao acompanhamento linha produ o htm http intranet projetos pessoal projeto milenio menu projeto milenio htm http intranet projetos pessoal projeto governet menu projeto governet htm http intranet projetos projetos projeto intranet menu projeto intranet htm http intranet projetos projetos projeto_intranet projeto_apresentacao htm http intranet projetos projetos projeto_intranet projeto_intranet htm http intranet proj
181. ormigas podem ser lan adas de qualquer nodo da rede simulando o in cio de uma chamada Cada formiga tem um nodo de 26 destino aleat rio Formigas movem se de nodo para nodo selecionando o pr ximo nodo para mover de acordo com as probabilidades nas tabelas de ferom nio para seu nodo destino Chegando a um nodo elas atualizam as probabilidades na tabela de ferom nio correspondentes a seu nodo de origem isto amp formigas depositam o tipo de ferom nio associado ao nodo de onde elas partiram Elas alteram a tabela para aumentar a probabilidade que aponta para o nodo anterior Quando as formigas alcancam seu nodo destino elas morrem Tomemos como exemplo uma formiga na rede da Figura 15 que amp lancada no nodo 3 com destino ao nodo 2 e acaba de mover se do nodo 4 para o nodo 1 Nesse exemplo a formiga toma uma rota ineficiente somente para fins de ilustra o Essa formiga primeiro vai alterar a tabela do nodo 1 correspondente ao nodo 3 seu nodo de origem aumentando a probabilidade de sele o do nodo 4 ela vai ent o selecionar seu pr ximo nodo aleatoriamente de acordo com as probabilidades na tabela correspondente ao seu nodo de destino nodo 2 Essa forma de atualiza o direcional de probabilidades difere da maneira como as formigas depositam ferom nio por m funcionalmente equivalente Schoonderwoerd 42 afirma que usar probabilidades ao inv s de quantidades absolutas de ferom nio ajuda a entender melhor o comport
182. ovado s haveria sentido em usar a meta heur stica da formiga na Internet se esta aplica o tivesse como objetivo encurtar o caminho do usu rio at a p gina destino sendo este o objetivo prim rio do sistema desenvolvido por Marco Dorigo 29 Esta aplica o s seria cab vel em um m todo de condu o global que tivesse como objetivo conduzir o usu rio pela estrutura existente do site sem a cria o de novos links Ent o com base nesta nova concep o foi desenvolvido o primeiro modelo do AntWeb adaptativo que chamamos de modelo 1 Esta nova concep o da mesma forma que a primeira ainda se baseia na id ia que assumiremos como ponto fundamental do nosso estudo que a maioria dos usu rios da Web procuram as mesmas p ginas em determinados contextos A principal diferen a entre as duas concep es trata da incorpora o do requisito de levar o usu rio at a p gina destino por um caminho otimizado usando a 63 estrutura original do site ou seja sem a adic o de links na estrutura ja existente Isso teria a vantagem de n o tornar a estrutura do site mais complexa do que ja n o colaborando para causar uma sobrecarga cognitiva no usu rio com o aumento de opc es a escolher O modelo 1 procura reproduzir com a maior fidelidade possivel o mesmo sistema de coopera o das formigas naturais n o se preocupando em incorporar os recursos de otimiza o usados pelas formigas artificiais de Marco Dorigo Como este
183. p intranet recursos tecnologicos relacao equipamentos gerencia filial quadro total maquinas htm 310 http intranet recursos tecnologicos relacao equipamentos adm financeiro quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos area tecnica quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos fabrica software quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos recursos humanos quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos gerencia filial quadro geral m quinas htm 308 http intranet recursos tecnologicos relacao equipamentos gerencia comercial quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos adm financeiro quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos recursos humanos quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos recrutamento selecao guadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos area treinamento quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos departamento pessoal quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos medicina trabalho quadro total maquinas htm http intranet recursos tecnologicos relacao equipamentos area tecnica quadro total maquinas htm
184. pela letra t A cada pagina ser associado um valor num rico correspondente a quantidade de ferom nio existente nela 69 T Figura 30 A associac o do ferom nio no AntWeb adaptativo Em relac o aos demais sistemas de hipermidia adaptativa a principal diferenca que o AntWeb n o possui guase nenhuma representac o do modelo de usu rio No AntWeb existe uma representac o de ambiente que s o os caminhos com ferom nio O nico aspecto do usu rio que o AntWeb leva em considerac o sua experi ncia no uso do sistema uma vez que isso necess rio para a manuten o das taxas de ferom nio IV 5 Esquema do AntWeb adaptativo na Web A Figura 31 mostra como funcionaria o AntWeb adaptativo na Internet Quando o usu rio for usar o sistema adaptativo ele acessar o servidor AntWeb e fornecer o endere o inicial de onde ele quer come ar sua navega o Depois o sistema busca na Internet o c digo HTML da p gina correspondente ao endere o fornecido Obtido o c digo este modificado de forma que os links que cont m uma quantidade razo vel de ferom nio apare am destacados para o usu rio Para isto o sistema faz uso das informa es contidas no Banco de Dados que s o as quantidades de ferom nio contidas nos links da p gina em quest o Em seguida o sistema AntWeb fornece ao usu rio a p gina correspondente ao endere o fornecido com os links modificados sistematicamente A p gina fornecida pelo AntWeb na verdad
185. po apresenta o adaptativa que tem como objetivo adaptar o conte do das p ginas Aqui discutiremos apenas os t picos de HA relacionados navega o adaptativa deixando de lado a apresenta o adaptativa 11 4 1 Modelo do Usuario Apesar do AntWeb possuir quase nenhuma modelagem de usu rio o modelo de usu rio um conceito muito importante quando se trata de Hiperm dia Adaptativa O AntWeb n o personaliza o hipertexto pelo menos nestas pesquisas iniciais mostrando uma hiperm dia s para todos os usu rios A id ia b sica da modelagem de usu rio representar o usu rio por atributos que correspondem a suas caracter sticas Segundo 18 existem pelo menos seis caracter sticas associadas a um usu rio que podem ser levadas em considera o seus conhecimentos seus objetivos sua hist ria sua experi ncia suas prefer ncias e sua velocidade no aprendizado A nica caracter stica do usu rio que o AntWeb leva em considera o a experi ncia que a caracter stica que diz respeito s a es que o usu rio executou 34 durante o uso do sistema de HA em quest o ou seja a experi ncia do usu rio com o sistema de HA O AntWeb usa as trajet rias que o usu rio executou durante a navegac o do hipertexto para determinar as quantidades de ferom nio a serem adicionadas 11 4 2 Ciclo cl ssico de adaptac o Goleta Dados sobre o Usu rio Processa Modelagem do
186. pol Fim Inicialmente a fun o obt m o valor hora do registro atual Em seguida vai para o pr ximo registro da tabela e obt m o segundo valor hora A fun o reposiciona o ponteiro da tabela no registro anterior de forma a deixar a tabela com a mesma configura o que a fun o a encontrou E finalmente retorna a subtra o dos dois tempos obtidos Voltamos ent o ao processo de cria o da tabela de localiza es esperada Depois de criar as parti es o algoritmo percorre cada uma delas a procura de localiza es esperada medida que encontra as localiza es esperadas o algoritmo as armazena sequencialmente na lista B Ao terminar de percorrer a parti o o algoritmo verifica se existe algum backtrack em B Caso exista ele inseri o seguinte registro na tabela de localiza es esperada P gina Objetivo A p gina do ltimo log da parti o Localiza esEsperadas1 B 1 ou seja o primeiro item da lista 122 Localizac esEsperadasN BIN o item N da lista B Localiza oAtual A pen ltima p gina da parti o que corresponde localiza o atual do link que leva at a p gina alvo Note que se o n mero de localiza es esperadas encontradas exceder ao n mero de atributos definidos o algoritmo falhar Assim conv m definir antes de criar a estrutura da tabela de backtracks um n mero m ximo estimado de backtracks que o visitante pode realizar antes de encontrar sua p gina alvo A
187. por que os protocolos atuais da Web n o possuem mecanismos de armazenamento e acesso de informa es direto p gina A associa o poderia ser feita atrav s do uso de uma tabela com informa es para identificar a p gina na Internet e o valor de ferom nio associado a p gina pelo uso de um sistema de banco de dados Outro problema tratado est relacionado a quest o de como fazer com que o usu rio seja atra do pelo ferom nio Infelizmente apesar de todo o avan o que a multim dia e a hiperm dia alcan aram sendo hoje poss vel interagir com o usu rio atrav s de imagens e sons ainda n o poss vel fazer com que as p ginas da Web interajam com os usu rios atrav s de odores Portanto tivemos que encontrar uma maneira alternativa de informar ou influenciar o usu rio a seguir os caminhos com maior quantidade de ferom nio A solu o encontrada foi atrav s do uso de t cnicas j consolidadas de hiperm dia adaptativa Estas t cnicas se mostraram suficientemente eficientes para os nossos prop sitos e consistem em 66 destacar os links mudar a ordem de apresentac o de links na p gina ou adicionar uma informac o extra ao link de forma a aumentar a probabilidade de escolha de determinado links pelo usu rio Atraves da aplicac o das soluc es aqui expostas verificamos que temos recursos suficientes para incorporar a meta heuristica da formiga a Web restando apenas o desenvolvimento de m todos inteligentes para utilizar
188. query this gt conection gt get echo lt br gt n echo query return return gt lt PHP 147 148 class AdaptabilityChecker var url function setUrl amp p this gt url amp p function isAdaptable url this gt url gt get if url http www cic unb br grad disciplinas disciplinas html return false return true 73 lt PHP class AntWeb var bDCreator var adaptabilityChecker var configuration var conection var handlerParser var log var pageLoader var sender var senderNonHtmi var test var url function AntWeb Surl 149 builder new BuilderWithCache builder gt buildAntWeb this unset builder this gt run url function setAdaptabilityChecker amp p this gt adaptabilityChecker amp p function run url this gt configuration gt setIniFile antweb ini this gt configuration gt load unset this gt configuration this gt bDCreator gt execute unset this gt dDCreator this gt url gt setUrl url this gt url gt handle if this gt pageLoader gt openFile this gt url gt becomePageNotFound if this gt pageLoader gt openFile exit Arquivo de pagina n o encontrada n o existe unset this gt pageLoader if this gt adaptability Checker gt isAdaptable this gt sender gt sendWholePage els
189. queryDropAdditions queriesPheromoneUpdater gt pushQuery queryCreateUpdatesAux queriesPheromoneUpdater gt pushQuery queryDeleteUpdates queriesPheromoneUpdater gt pushQuery queryInsertUpdates queriesPheromoneUpdater gt pushQuery queryDropUpdatesAux SquervinsertUpdate gt setQueryAdditionCalculator queryAdditionCalculator this gt buildCore trigger queryAddAdditions gt setConection this gt conection queryAdditionCalculator gt setConection this gt conection queryCreateUrlsAux gt setConection this gt conection queryDecayPheromone gt setConection this gt conection queryDeleteUrls gt setConection this gt conection queryDropAdditions gt setConection this gt conection queryDropUrlsAux gt setConection this gt conection queryFirstLog gt setConection this gt conection querylnsertUpdate gt setConection this gt conection querylnsertUrls gt setConection this gt conection queryLastUpdate gt setConection this gt conection queryCreateUpdatesAux gt setConection this gt conection queryDeleteUpdates gt setConection this gt conection querylnsertUpdates gt setConection this gt conection queryDropUpdatesAux gt setConection this gt conection intervalMaker gt setConfiguration this gt configuration 158 lastUpdateExtractor gt setConfiguration this gt configuration queryAddAdditions gt setConfiguration this gt configuration queryD
190. r na p gina correspondente ao endereco http www cic unb br O arquivo pheromoneupdater php a p gina respons vel pelas atualiza es de ferom nio contidos no banco de dados uma p gina que deve ficar aberto em um host qualquer da Web em per odo permanente Esta p gina possui um mecanismo especial que faz que com ela mesma se auto atualize no browser a cada 5 segundo Em cada atualiza o desta p gina ela verifica se necess rio fazer uma atualiza o de ferom nio no banco de dados e a realiza O arquivo classes php cont m as classes que s o usadas em comum pelas duas p ginas citadas anteriormente A classe mais relevente deste arquivo no que diz respeito instala o e configura o do AntWeb a classe DBAccess nesta classe que est o gravadas as informa es referentes ao acesso ao banco de dados como senha e nome de usu rio No m todo setConfiguration deve se configurar a URL do servidor de banco de dados na Web mvsqlhost o nome do usu rio username a senha password e o nome da base de dados databasename Ap s informadas estas informa es bastar executar o AntWeb pela primeira vez que ele automaticamente criar todas as tabelas e far todas as configura es necess rias no banco de dados O arquivo antweb ini o arquivo em que s o configurados todos os outros par metros Para editar esses par metros basta abrir o arquivo em um editor de texto qualquer Os par metros configuraveis ne
191. r gt setNext elementExtractor decoratorBuilder gt setNext returnKeeper decoratorBuilder gt setNext stringDecomposer decoratorBuilder gt setNext pageLoader elementExtractor gt setExtractingNonTag extractingNonTag elementExtractor gt setExtractingTag extractingTag elementExtractor gt setNextToStates if lisset this gt url exit erro core n o criado pageLoader gt setUrl this gt url internalUrlsProcessor gt setUrl this gt url antWeb gt setPageLoader amp pageLoader this gt htmlParser amp cache function buildDBCreator amp antWeb dBCreator new QueryExecuter queryCreateLogs new QueryCreateLogs queryCreateUpdates new QueryCreateUpdates queryCreateUrls new QueryCreateUris if lisset this gt conection exit erro Core n o criado queryCreateLogs gt setConection this gt conection queryCreateUpdates gt setConection this gt conection queryCreateUrls gt setConection this gt conection 155 dBCreator gt pushQuery queryCreateLogs dBCreator gt pushQuery queryCreateUpdates dBCreator gt pushQuery queryCreateUrls antWeb gt setDBCreator dBCreator function buildAdaptabilityChecker amp antWeb adaptabilityChecker new AdaptabilityChecker adaptabilityChecker gt setUrl this gt url antW eb gt setAdaptabilityChecker adaptabilityChecker this gt adaptabili
192. r vista como um gigantesco mar de informa es que pode ser utilizada de diversas formas No entanto a Internet ainda possui muitos problemas sem solu o como o problema de navega o Diversos fatores podem ser apontados para que este problema persista O fato que as estruturas dos sites n o auxiliam o usu rio a encontrar sua p gina alvo Os textos dos links s o imprecisos ou seja os links que levam o usu rio a sua p gina alvo est o em p ginas ndice diferentes das quais o usu rio espera como citado por 44 Estes s o alguns dos problemas que levam o usu rio a usar uma sequ ncia de liga es passaremos a utilizar a palavra links de agora em diante mais longa do que a necess ria ou at mesmo desistir da procura antes de encontrar a sua p gina alvo prejudicando sua navega o Neste contexto surge uma clara demanda por m todos que visem melhorar este cen rio do ponto de vista da navega o Um sistema como o AntWeb contribui no sentido que indica caminhos para que o usu rio chegue at seu objetivo e otimize sua navega o fazendo com que ele use apenas a quantidade necess ria de links para se deslocar dentro do hipertexto at sua p gina alvo O AntWeb est relacionado com diversas reas da Ci ncia da Computa o e t picos de pesquisa como a meta heur stica da formiga que lhe d fundamento a hiperm dia adaptativa Web inteligente webmining agentes inteligentes de navega o itera o homem w
193. ra VE zo lado de algum link Isto significa que este link poder levar voc mais r pido ao que voc est procurando Clique aqui para come ar Siga a SE eboa sorte contato gt Figura 36 P gina em que o usu rio inicia sua navega o Na Figura 37 o link docentes destacado com a formiga significa que interceptamos uma trilha de ferom nio Ao clicarmos neste link destacado estaremos seguindo a trilha de ferom nio deixado por outros usu rios No nosso exemplo o usu rio aceita a sugest o do AntWeb e clica no link indicado aparecendo assim a p gina do corpo docentes do CIC que mostrado na Figura 38 Note que na barra de endere o mostrado na figura ainda est o endere o http antweb linf unb br mas com o par metro mudado para url http www cic unb br docentes docentes html que corresponde a p gina que estamos acessando agora 87 a Departamento de Ci ncia da Computa o CIC Microsoft Internet Explorer E i loj xi File Edit View Favorites Tools Help E Back gt O A A Qsearch Ggravortes D SO E Address http antweb linf unb br url http fwww cic unb br Universidade de Bras lia Xi Insti e Ci nci Go Links Departamento DE CI NCIA DA COMPUTA O Curso de Gradua o wi 2 Mestrado em Inform tica Mestrado em Ci ncia da gt i Pesquisa Extens o Li es de Computa o Debates sobre Seguran a Concurso
194. rama de classes contendo as principais classes do m dulo de adaptac o de paginas Este m dulo amp executado a cada vez que o usuario faz uma solicitac o ao AntWeb e amp respons vel por apresentar a pagina com os links destacados se necess rio No projeto deste m dulo foi usando o design pattern decorator 60 que permite como que a pagina seja adaptada com se estivesse passando por uma linha de montagem de uma fabrica A descric o das principais classes apresentado a seguir Url responsavel por tratar a URL da pagina que vai ser adaptada PageLoader respons vel por obter da Internet o c digo HTML da p gina 95 que vai ser adaptada TagExtractor respons vel por extrair do c digo HTML as tag InternalLinksProcessor respons vel por fazer com que os caminhos relativos dos links da p gina se tornem absolutos PheromoneSetter respons vel por obter a taxa de ferom nio de todos os links da p gina LinksSelector respons vel por selecionar os links que ser o destacados baseando na taxa de ferom nio de cada um e nos par metros obtidos de Configuration LinksHighlighter respons vel por destacar os links selecionados em LinksSelector na p gina que est sendo adaptada LinksGuider altera todas as URLs dos links da p gina de forma que eles apontem para o AntWeb e contenham um par metro informando qual p gina o link apontava antes Este processo essencial para que o usu rio ao clicar em algum link na p gina co
195. riedade de sistemas de computadores e aplica es de software 29 distintos o projeto WWW tinha com requisito ter uma plataforma que fosse port vel compativel atodos sendo desenvolvido usando a arquitetura cliente servidor AWeb foi projetada para ser integr vel com futuras tecnologias como novas redes protocolos tipos de objetos e formatos de dados O projeto WWW introduziu v rias pr ticas comuns para estar de acordo com a abordagem de comunica o cliente e servidor Dentre elas o protocolo HTTP a linguagem HTML Hypertext Markup Language que uma generaliza o da linguagem SGML Standard Generalized Markup Language sendo a linguagem nativa para documentos na Web Tamb m o conceito de URL Uniform Resource Locator que o sistema padr o para a identifica o de objetos na Web A Web somente foi poss vel de ser desenvolvida pela utiliza o da tecnologia de hipertexto e hiperm dia o qual passaremos a expor 1 3 Hipertexto e Hipermidia Um sistema de hipertexto ou um hiperdocumento pode ser definido como um sistema que apresenta informa es como uma rede interconectada de n s ou nodos a qual os leitores tem liberdade para navegar livremente de forma n o linear A palavra hipertexto a fus o dos termos espa o hiperb lico e texto sugerindo a id ia de um texto multidimensional e n o linear em que o leitor pode acessa lo de forma n o sequencial O hipertexto pode ser definido como uma rede de nodos
196. role individuais 11 1 5 2 1 A modelagem do problema Uma aplica o foi escrita por Schoonderwoerd 42 para simular padr es de tr fego em um modelo de rede de telecomunica es baseado em comuta o switching Tal rede representada por um grafo n o direcionado Cada nodo do grafo corresponde a uma esta o de comuta o as arestas entre os n s correspondem aos canais de comunica o Um dado nodo geralmente estar conectado somente a um subconjunto de outros nodos da rede geralmente sua vizinhan a geogr fica arestas s o intrinsecamente bidirecionais O modelo de rede usado um grafo com n nodos cada qual com v rios atributos Um identificador do nodo Uma capacidade ou seja o n mero de chamadas simult neas que o nodo pode gerenciar Uma tabela de roteamento com n 1 entradas uma para cada um dos demais nodos da rede Cada entrada informa qual nodo o pr ximo nodo na rota ao destino considerado probabilidade de ser o nodo terminal fonte ou destino de uma chamada A capacidade ociosa o percentual da capacidade que ainda est dispon vel no nodo As arestas entre os nodos possuem capacidade infinita de modo que a dist ncia geogr fica entre os nodos ligados n o seja levada em conta A capacidade dos nodos ser portanto o nico gargalo da rede 11 1 5 2 2 Ger ncia de redes com controle baseado em formigas Esta se o mostra como algoritmos formiga podem ser aplicados a rede
197. rowser Caso isto n o fosse feito os 99 acessos repetidos as p ginas feitos a partir de um mesmo host n o seriam registrados no log do sistema e consequentemente n o seriam considerados no processo de atualizac o de ferom nio Decidimos testar a hip tese mais importante do modelo 1 que o prevalecimento dos caminhos mais curtos Acreditamos que os outros benef cios listados acima tamb m seriam alcan ados se ao inv s de usarmos o ferom nio apenas indicassemos os links mais populares A nica coisa que essa abordagem mais simpl ria n o poderia fazer e que o modelo 1 poderia indicar rotas mais curtas Para comprovarmos isto atrav s de experimentos executamos navega es no site do CIC at determinada p gina usando o sistema implementado Foi escolhida a p gina do professor Li Weigang pelo fato de existirem dois caminhos de tamanhos diferentes para chegar at ela a partir da p gina inicial do departamento de ci ncia da computa o A Figura 43 mostra uma estrutura parcial do site do CIC focalizando os dois caminhos existentes entre as duas p ginas Nesta situa o quando o usu rio estiver procura da p gina objetivo ele ter que decidir qual link seguir na hora em que ele estiver na p gina inicial O link para a p gina do corpo docente do departamento conduz o usu rio a um caminho com um custo de dois links enquanto o link para a p gina da p s gradua o conduz o usu rio para um caminho com tr s links
198. rtida para sua navegac o sendo que a partir dele pode se chegar a outras p ginas clicando os links disponiveis Ao clicar no link indicado o usu rio visualizar a mesma p gina que ele visualizaria se tivesse digitado a URL no campo adresss do seu browser mas com a diferenca que o s link s que presumidamente possuem maior probabilidade de levar ao objetivo em menos tempo foi destacado como mostrado na Figura 37 Observe a barra de endereco do browser no alto da Figura 37 O leitor poder perceber que na verdade o nosso usu rio n o est acessando a p gina http www cic unb br e sim a p gina http antweb linf unb br url http www cic unb br ou seja ele est acessando a pagina http antweb linf unb br com o par metro url http www cic unb br 86 a Departamento de Ci ncia da Computag o CIC Microsoft Internet Explorer Arquivo Editar Exibir Favoritos Ferramentas Ajuda QNS ASE HE Enderego je http antweb linf unb br metapages cic htm he el Links Universidade de Bras lia Instituto de Ci ncias Exatas Departamento de Ci ncia da Computa o RET da EE tees td A T i tie Ex Ola este um projeto experimental desenvolvido no departamento de Ci ncia da Computa o que visa trazer para internet o mesmo m todo usada pelas formigas para encontrar alimento Quando voc estiver navegando em nosso site usando o AntWeb poder aparecer a figu
199. s 25 de telecomunicac es atrav s do uso de tabelas de ferom nio no lugar das tabelas de roteamento como passaremos a expor 1 1 5 2 2 1 Tabelas de ferom nio Substituem se as tabelas de roteamento nos nodos da rede por tabelas de probabilidades que podem ser chamadas tamb m de tabelas de ferom nio uma vez que a intensidade de ferom nio representada por essas probabilidades Cada nodo possui uma tabela de ferom nio para cada poss vel destino na rede e cada tabela possui uma entrada para cada vizinho Por exemplo um nodo com quatro vizinhos em uma rede de 30 nodos tem 29 tabelas de ferom nio com quatro entradas cada Poderia se dizer que uma rede com n nodos teria n diferentes tipos de ferom nio As entradas nas tabelas s o as probabilidades que influenciam a escolha do pr ximo nodo pelas formigas em seu trajeto rumo ao destino A Figura 15 mostra uma poss vel configura o de rede e a Tabela 3 uma tabela de ferom nio assumindo se o nodo 1 como origem segundo trabalho de 42 Por exemplo formigas viajando do nodo 1 para o nodo 3 t m probabilidade 0 49 de escolher o nodo 2 como seu pr ximo nodo e 0 51 de escolher o nodo 4 Aqui o dep sito de ferom nio representado por atualiza o de probabilidades Figura 15 Modelo de rede Tabela 3 Tabela de probabilidade Pr ximo nodo Nodo destino 2 4 2 0 95 0 05 3 0 49 0 51 4 0 05 0 95 A cada instante da simula o f
200. s E a tabela em que est o registrados todos os arquivos HTML que representam as p ginas do nosso site em estudo Esta tabela fornecida pelo administrador Web do site Ela servir para fazer a filtragem dos logs contidos no arquivo de log No arquivo de log est o registrados os acessos a todos os arquivos do site inclusive arquivos que n o s o de interesse do sistema webmining A fun o desta tabela informar ao sistema quais arquivos devem ser filtrados do arquivo de Log Tabela de logs Para facilitar a manipula o dos dados contidos no log do servidor n s utilizaremos uma tabela intermedi ria que conter os dados filtrados do log do servidor Esta tabela conter todos os logs filtrados do Arquivo de log pelo 41 processo de filtragem de dados A tabela formada pelos seguintes atributos Idvisitante E a chave que identifica o visitante do Site Normalmente o endereco IP que o visitante possuia na sec o em que acessava o site P gina A URL da p gina que o visitante visitou Ex http www politec com br produtos impressao htm DataHora A data e hora em que o visitante acessou a p gina Este atributo servir para determinar a ordem de visita das p ginas que o visitante acessou no site Este dado ser importante no processo de criac o da Tabela de localizac es esperada descrita na pr xima sec o Toda essas informac es existem tamb m no arquivo de log sendo apenas transferidas para esta tabela para uma forma
201. s gt atributes a this gt atributes a null function setAtribute name value if lisset this gt atributes if this gt getName return false this gt load this gt atributes name value function load if lisset this gt atributes if this gt getName return false this gt atributes array while this gt dataProcessing this gt atributes this gt shiftAtributeName this gt shiftAtributeValue unset this gt dataProcessing 181 function shiftAtributeName this gt dataProcessing explode this gt dataProcessing namesstrtoupper array_shift this gt dataProcessing this gt dataProcessing implode this gt dataProcessing this gt dataProcessing trim this gt dataProcessing return trim name function shiftAtributeValue if this gt dataProcessing return null delimitator this gt dataProcessing 0 if delimitator or delimitator this gt dataProcessing explode delimitator this gt dataProcessing array_shift this gt dataProcessing value array_shift this gt dataProcessing this gt dataProcessing implode delimitator this gt dataProcessing else this gt dataProcessing explode this gt dataProcessing value array shift this gt dataProcessing this gt dataProcessing implode this gt dataProcessing 182 this gt dataProc
202. s ajudaria numa an lise posterior dos dados obtidos Poderiamos ent o estudar caracteristicas comuns e distintas relacionadas com a peregrinac o das formigas naturais e a navegac o dos humanos na Internet Neste sentido poderiamos estabelecer valores para os par metros do sistema de forma mais precisa bem como criar m todos objetivos para a determinac o dos mesmos A aplicacao de t cnicas de Intelig ncia Artificial como o raciocinio baseado em casos para a infer ncia das p ginas que s o interessantes para o usu rio para ser usado no goodnees do modelo 2 do AntWeb adaptativo A utiliza o conjunta do AntWeb adaptativo com outras abordagens inteligentes na Web para estrutura o da informa o que auxiliem na navega o do usu rio por exemplo 6 realiza o de estudos com o objetivo de descobrir viabilidades de incorpora o do AntWeb adaptativo em outras heur stica de navega o adaptativa Incorporar de forma mais significativa a modelagem de usu rio no AntWeb adaptativo de forma que o AntWeb possa se adaptar s preferencias e as caracter sticas de cada usu rio A realiza o de estudos com o objetivo de incorporar o ferom nio ao protocolo HTTP fazendo assim com que a resposta do sistema ao usu rio seja mais imediata Estas foram algumas sugest es elaboradas durante nosso trabalho no entanto n o tivemos a pretens o de completude pois sabemos que muitas outras podem surgir no momento em que o lei
203. s neste O 40 sistema foi dividido em tr s processos distintos O processo de filtragem de informa es do arquivo de log O processo de preenchimento da tabela de Backtracks O processo de extra o de informa es da tabela de Backtracks Os tr s processos s o dependentes entre si de forma que cada um depende da sa da do processo anterior Assim eles devem ser realizados na sequ ncia informada pois cada um depende do anterior Cada um dos tr s processos descrito abaixo 11 1 1 O processo de filtragem de informa es do arquivo de log o processo que seleciona os logs do Arquivo de Log e os transfere para tabela de log Este processo manipula tr s objetos Arquivo de log O arquivo de log um arquivo do tipo texto que o servidor web usa para registrar os acessos s p ginas e elementos feitos pelos usu rios que navegam pelo servidor A cada acesso feito no servidor este acrescenta uma linha no arquivo de log como no exemplo abaixo 10 61 3 47 POLITEC BSB edvans Y 1 22 01 9 23 03 1 www xdrive com 80 844 792 826 http http www xdrive com images tech login button_login gif Inet 200 8392706 Nele ficam registrados os acessos externos feitos a arquivos que fazem parte do site Esses arquivos podem ser figuras p ginas HTML etc E o objeto base para a realizac o do webmining E deste arquivo que vamos minerar todas informac es para reestruturac o do site Tabela de p gina
204. s_politec htm http intranet a_politec produtos_servicos servicos recuperacao_textual1 htm http intranet a_politec produtos_servicos servicos cold1 htm http intranet a_politec produtos_servicos servicos ged1 htm http intranet a_politec produtos_servicos servicos ocr_icr1 htm http intranet a politec produtos servicos servicos workflowi htm http intranet a politec produtos servicos servicos intranet interneti htm http intranet a_politec produtos_servicos servicos base_conhecimento1 htm http intranet a_politec produtos_servicos servicos resultados htm http intranet a_politec produtos_servicos servicos fabrica htm http intranet a politec portifolio portifolio htm http intranet a politec premios politec premios politec htm http intranet a politec subsidiarias htm http intranet a politec certificacao relacao CDIA htm 137 http intranet a politec certificacao relacao Microsoft htm http intranet a_politec certificacao relacao_Novell htm 138 ANEXO C C DIGO FONTE DA IMPLEMENTA O DO ANTWEB lt PHP class DecoratorEnd function unsetNexts function amp getOut echo Esta operacao nao foi implementada gt lt PHP class FlushCloser extends Decorator var open true var nome function FlushCloser n null this gt nome n function amp getOut if this gt open this gt open false return Decora
205. see ee ee ee nn 54 FIGURA 27 SITUA O COM UM CAMINHO DE 4 LINKS PARA O OBJETIVO san nennen enn 56 FIGURA 28 SITUA O 3 COM UM CAMINHO COM DOIS LINKS PARA O OBJETIVO 58 FIGURA 29 INDICA O DIFERENCIADA PARA CAMINHOS EQUIVALENTES aan see ee ee ee ee 67 FIGURA 30 A ASSOCIA O DO FEROM NIO NO ANTWEB ADAPTATIVO aen ee see ee ee ee ee 69 FIGURA 31 MODELO FUNCIONAL ANT WEB ADAPTATIVO iese ses sees see ee ee ee ee sun see ee ee ee ee 70 FIGURA 32 ABORDAGEM DO VALOR DO FEROM NIO annen see ee ee see ee ee ee ee ee ee ee ee ee 74 FIGURA 33 ABORDAGEM DO DESTAQUE PROPORCIONAL ese sesse ee ee ee ee ee ee ee ee ee ee ee ee 75 FIGURA 34 ABORDAGEM DO M NIMO SIGNIFICATIVO sesse es esse ese ee ee ee ee ee ee ee ee ee ee ee ee 76 FIGURA 35 ESTRUTURA DE UM SITE FICT CIO ees ese ees ees see ee see ee ee ee ee ee ee ee ee ee Re ee nanna 83 FIGURA 36 P GINA EM OUE O USU RIO INICIA SUA NAVEGA O eere oenen ee ee ee ee ee ee ee 86 FIGURA 37 HOME PAGE DO CIC COM O ANTWEB aaneen ee ee eed ee ees ees ee eed ee ee ee ee ee ee ee 87 FIGURA 38 P GINA DE CORPO DOCENTE annae ese ee ee ee ee ee ae ee ee Re ee RA ee ee Re ee ee ee 88 FIGURA 39 ACESSO A PAGINA SEM O ANTWEB ees ee see ee ees ee ee ee ee ee dee ee ee ee ee ee ee ee ee ee ee 88 FIGURA 40 ACESSO A P GINA COM O ANTWEB unsure ee ee ee ee ee ee ee Re ee ee ee ee ee 89 FIGURA 41 DIAGRAMA DE CLASSES SIM
206. servir para o leitor entender melhor como a formiga pode se adaptar a altera es no ambiente e como o caminho mais curto tende a ficar com mais ferom nio Imagine a seguinte situa o em que as formigas est o indo e voltando entre o ninho e a fonte de alimento como mostra a Figura 3 HE Se HE VE AG ME VE Se AF MG HE DE DE HE TE DE HEDE DE HEDE DE HEDE DE GR Figura 3 Formigas caminhado entre o ninho e a fonte de alimento Nesta situa o j existe uma trilha formada indicando o menor caminho entre o ninho e a fonte de alimento Ao se colocar um obst culo no caminho das formigas como mostrado na Figura 4 as formigas inicialmente se dividem na escolha do caminho para desviar o obst culo como mostrado na Figura 5 Mas 13 depois de algum tempo um n mero cada vez maior de formigas comecam a escolher o caminho mais curto como mostrado na Figura 6 IE Me AE VE Ma HE BE Me AE BE Me AE IE a HE IESE HE BES ME HE De AE Figura 4 Um obst culo na trilha de formigas ae sk si _ d Se FE Se pe IE VE AE FE SA AE IE Sa ME IE Sa DE AE Se HE AE BE HE SA IL Fu Fr Se HERE DE MEE at WM AL Figura 5 As formigas se dividem na escolha do caminho a seguir 14 AE SA IE Figura 6 O caminho mais curto acaba prevalecendo A Figura 7 mostra as dist ncias consideradas para fazer a simulac o Dois pontos da trilha original s o fixados de forma eqiidistante do obst culo a 1 cm cada um A di
207. sistema de coopera o entre as formigas naturais ainda pesquisado pela biologia com respeito a descoberta de outras fun es tinha se a expectativa de que este modelo pudesse melhorar a navega o do usu rio at mesmo em aspectos n o estudados O m nimo que se esperava desta nova concep o que o aparecimento de trilhas otimizadas de ferom nio na Web pudesse levar os usu rios s p ginas que de alguma forma seriam interessantes A comprova o destas expectativas s seria poss vel com a incorpora o deste sistema na Web e a compara o das navega es feitas na Web com e sem o AntWeb adaptativo Ent o partiu se para a implementa o e testes do modelo 1 utilizando se o site do departamento de Ci ncia da Computa o da Universidade de Bras lia Os experimentos realizados foram fundamentais para notarmos diferen as essenciais entre a navega o t pica do usu rio da Internet e a peregrina o das formigas em busca de alimento derrubando hip teses falsas Estas diferen as limitavam a aplica o do sistema original de coopera o das formigas naturais na Web sugerindo modifica es no modelo 1 para que este pudesse ter uma utilidade maior no processo de navega o na Web Com base nas conclus es obtidas dos experimentos feitos com o modelo 1 foi desenvolvido um novo modelo mais flex vel e complexo que foi chamado de modelo 2 A principal diferen a do modelo 2 em rela o ao modelo 1 foi a separa o da fun
208. st embaixo de outra 44 Neste sentido com a conduc o do usu rio As p ginas seria possivel a diminuic o substancial de trajet rias erradas Diminuir o n mero de p ginas consultadas por sess o Um n mero alto de p ginas consultadas por sess o em um site significa que os usu rios est o perdidos e est o encontrando suas p ginas atrav s de m todos de tentativa e erro Se o usu rio seguisse a orientac o do AntWeb nas primeiras tentativas e o usu rio chegasse a p gina desejada seria diminuido o n mero de p ginas consultadas Diminui o do uso do bot o de busca Quando o uso do bot o de busca de um site est muito alto significa que o usu rio tem pouca confian a na estrutura do site j que ele acha que vai encontrar o que ele procura mais r pido desse modo do que usando os links Se o AntWeb realmente trouxer benef cios na navega o mais usu rios v o tentar achar o que procuram atrav s dos links Diminu o do tempo que o usu rio permanece conectado ao site Esta caracter stica est relacionada a todas as anteriores uma vez que a navega o atrav s de rotas otimizadas e diminui se o n mero de p ginas consultadas por sess o resultando numa diminui o de tempo em que o usu rio permanece navegando sem encontrar o que procura Esses itens s o verific veis atrav s do processo de webmining e s o muitas vezes usados como indicativos para avaliar a usabilidade de sites Dessa forma para que as caract
209. st ncia da ponta do obst culo que esta na parte de baixo da trilha original 1 cm e a dist ncia da ponta do obst culo que esta na parte de cima da trilha original 2 cm E claro que nesta situac o o menor caminho para desviar do obst culo o caminho de baixo Nesta simulac o estamos considerando que as formigas caminham a uma velocidade de 1 cm por segundo IE Figura 7 Dist ncias entre os pontos para fazer a simulac o No tempo 0 a primeira formiga indo o dual chamamos de 1i e a primeira formiga voltando da fonte de alimento o qual chamamos de 1v aparecem nos 15 respectivos pontos que estabelecemos sobre a trilha de ferom nio como mostra a Figura 8 Figura 8 Estado da simula o no tempo 0 Figura 9 Estado da simula o no tempo 1 Passado 1 segundo as duas formigas chegam at o obst culo como mostrado na Figura 9 nesse momento que as duas formigas tem que decidir qual caminho seguir dentre as duas alternativas poss veis Para justificar a probabilidade real da formiga escolher qualquer um dos caminhos que de 50 cada um vamos considerar que cada uma das duas formigas escolheram caminhos diferentes como 16 mostrado na Figura 10 que mostra a situac o no tempo 2 Nesta situacao a formiga 1i ainda n o conseguiu atravessar o obst culo enquanto que a formiga 1v j esta passando de um lado para o outro do obst culo lv Figura 10 Estado da simula o
210. stam dois usu rios a procura da p gina 1 sendo que um usu rio est na p gina 1A e outro na p gina 1B Se o ferom nio estiver associado transi o ou ao link seria o ferom nio dos links lt 1A 2A gt e lt 1B 2A gt que informariam a efici ncia do caminho respectivamente para cada usu rio para chegar at a p gina 1 sendo que a situa o dos dois usu rios 67 equivalente pois s o necess rios tr s clicks para se chegar p gina 1 Mas como nesta hip tese s o duas taxas diferentes existiria a possibilidade de terem valores diferentes Se associarmos o ferom nio s p ginas seria a taxa de ferom nio da pagina 2A que decidira o rumo dos dois usu rios ou seja os dois usu rios compartilhariam da mesma taxa de ferom nio e assim n o haveria a possibilidade de terem valores diferentes para indicar caminhos equivalentes pelo menos nesta situa o 1A 1B 2A 3A Figura 29 Indica o diferenciada para caminhos equivalentes Outra desvantagem de associar o ferom nio ao link que o n mero de links em um site geralmente maior do que o n mero de p ginas consequentemente o n mero de acessos necess rios para treinar as taxas de ferom nio seria maior do que na hip tese do ferom nio associado p gina Tamb m a tabela usada para armazenar o ferom nio seria mais complexa para representar o link ou transi o do que a p gina Na hip tese do ferom nio estar associado p gina basta
211. ste arquivo s o os seguintes application address URL para o arquivo index php na Web decay coefficient coeficiente de evapora o representado por um n mero real entre Oe 1 deufaut page p gina que o arquivo index php se transformar caso n o seja informado nenhuma URL no par metro URL em sua evoca o iteration time quantidade de tempo em segundos que deve ocorrer entre uma atualiza o e outra das taxas de ferom nio indicator picture URL da figura da formiga que servir para destacar os links max links to show n mero m ximo de links a destacar por p gina page not found p gina que a p gina index php dever se transformar 91 caso a URL informada no par metro url n o exista threshold quantidade minima de ferom nio correspondente a um link para que este seja destacado Para o bom funcionamento do sistema todos os par metros acima listados dever o ser configurados V 2 Banco de dados do AntWeb O banco de dados do AntWeb amp constituido por quatro tabelas a saber Log tabela respons vel por guardar os dados de acesso feitos no AntWeb Cada vez que um usu rio faz uma solicitag o ao AntWeb amp incluido um registro nesta tabela correspondente a solicita o S o gravados nesta tabela ID do usu rio URL da p gina solicitada data e a hora que foi feita a solicita o e valor do par metro n mero m ximo de links a destacar usado para adaptar a p gina Se o AntWeb sugeriu algu
212. ste nenhuma hierarquia entre elas nenhum ponto central de intelig ncia existe apenas um conjunto de indiv duos fazendo a mesma coisa Da provavelmente vem o principal trunfo desse sistema natural que chamou a aten o dos cientistas da Computa o a capacidade de executar isso em paralelo 10 11 1 2 O experimento da ponte bin ria 15cm Upper Branch Lower Branch Figura 1 Experimento da ponte bin ria Em 29 encontramos o experimento da ponte bin ria uma ponte que possui dois caminhos entre o formigueiro e a fonte de alimento sendo que os dois caminhos tem tamanhos iguais O objetivo deste experimento descobrir de que forma aquele fen meno auto catal tico da atividade de encontrar o melhor caminho acontece Quando as formigas come am a caminhar sobre a ponte no in cio do experimento as formigas se dividem em partes iguais em cada ramo da ponte para ir e voltar Com o passar do tempo ap s uma breve oscila o esta raz o vai ficando cada vez mais diferenciada tornando o caminho mais alto mais usado pela formiga como mostrado na Figura 2 11 e Passages upper branch Passages lower branch 100 75 50 25 0 5 10 15 20 25 30 Time minutes Figura 2 Gr fico de uso dos dois caminhos pela formiga A Figura 2 de 29 mostra como variou a quantidade de formigas que usaram os dois caminhos Inicialmente n o existe ferom nio algum e com o passar do te
213. stema e representa o coeficiente de decremento da trilha de ferom nio 11 2 4 Algoritmo do AntWeb para avalia o de estruturas O algoritmo usado por AntWeb amp delineado a seguir 1 Aplica se minerac o de dados no log de acessos ao servidor web para conseguir a probabilidade inicial de escolher a p gina j quando se est na p gina i Iterac o p 0 2 Dentro de uma itera o o sistema lan a uma formiga k na homepage raiz do site s a cada instante t com uma p gina de destino d aleatoriamente escolhida neste trabalho n s ainda nos limitaremos a uma s p gina destino 3 Cada formiga k seleciona a pr xima p gina usando a informa o armazenada na tabela de roteamento A rota selecionada seguindo um esquema rand mico proporcional probabilidade de cada p gina vizinha 4 O identificador de cada p gina i visitada e o tempo decorrido desde o lan amento da formiga at chegar a sua j sima p gina s o armazenados em uma pilha de mem ria levada pela formiga k 5 Quando a formiga k alcan a a p gina de destino d ela morre esse trabalho assumimos que o visitante p ra na p gina de destino A formiga deposita uma quantidade de ferom nio Ar t em cada link que ela visitou em seu trajeto T p Equa o 10 6 O sistema atualiza o ferom nio nos links ao longo do trajeto da formiga k A tabela de roteamento amp alterada incrementando se as probabilidades associadas com links pert
214. stro ele incrementar o valor peso da p gina em P correspondente a p gina armazena no atributo analisado com o valor da rela o descrita na Equa o 21 htt 129 ANEXOB ESTRUTURA DO WEB SITE DA POLITEC p intranet 77 http intranet recursos_humanos menu_recursos_humanos htm http intranet menus menu_pessoal_telefones_nome htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_nome conselho_diretor_assessoria htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_nome diretoria_superintendente_assessoria htm http intranet recursos_humanos pessoal_telefones pessoal_telefone_nome gerencia_operacional htm http intranet recursos humanos pessoal telefones pessoal telefone nome area adm financeiro htm http intranet recursos humanos pessoal telefones pessoal telefone nome area tecnica area tecnica htm http intranet recursos humanos pessoal telefones pessoal telefone nome fabrica software htm http intranet recursos humanos pessoal telefones pessoal telefone nome recursos humanos area rh htm http intranet recursos humanos pessoal telefones pessoal telefone nome gerencia comercial htm http intranet recursos humanos pessoal telefones pessoal telefone nome area adm financeiro htm http intranet recursos humanos pessoal telefones pessoal telefone nome recursos humanos area rh htm http intranet recursos humanos pessoal telefones pessoal telefone
215. t this gt interval gt getStart dateTime date Y m d His decayCoefficient this gt configuration gt data decay_coefficient function this gt additionCalculator gt getFunction interationTime this gt configuration gt data iteration_time return INSERT INTO Updates lastEnd lastStart dateTime decayCoefficient function iterationTime quantity gt lt PHP class QueryFirstLog extends Query VALUES end start dateTime decayCoefficient function interationTime 1 function generateQuery return select min dateTime last from Logs 202 gt lt PHP class QueryDropUrlsAux extends Query function generateQuery return DROP TABLE UrlsAux gt lt PHP class QueryDropAdditions extends Query function generateQuery return DROP TABLE Additions gt lt PHP class QueryDeleteUrls extends Query function generateQuery return DELETE FROM Urls WHERE pheromone lt 0 00000000000000000000000000000000000001 gt 203 lt PHP class QueryDecayPheromone extends Query var configuration function setConfiguration amp p this gt configuration amp p function generateQuery return UPDATE Urls SET pheromone pheromone 1 this gt configuration gt data decay_coefficient gt lt PHP class QueryCreateUrlsAux e
216. t no processo de navega o Esta orienta o viria sob a forma de adapta es din micas nos sites como por exemplo o destacamento de links Por isso o adjetivo adaptativo O AntWeb adaptativo envolve estudos como descobrir a melhor forma de promover a adapta o como incorporar a nova metodologia na Internet atual e principalmente o desenvolvimento de uma heur stica que informe ao usu rio o melhor caminho a seguir A express o meta heur stica significa uma heur stica que serve para fazer outras heur sticas a partir dela Assim usando a meta heur stica da formiga desenvolvemos uma nova heur stica que foi chamada de AntWeb Ao atingir um est gio em que n s j t nhamos um modelo concreto de como a meta heur stica da formiga poderia ser aplicada navega o na Internet este modelo foi implementado como um servi o no web server e foi colocado a disposi o dos usu rios da Internet por um determinado per odo Podemos dizer tamb m que o AntWeb um sistema pois a sua proposta permite a forma o de um cen rio em que partes coordenadas entre si concorram para um determinado resultado baseando se em um conjunto de princ pios Neste contexto as partes coordenadas s o os usu rios da Web que fazem um trabalho em conjunto para encontrarem suas p ginas alvo No est gio atual em que a Web se encontra infelizmente ainda n o existe nenhuma coordena o entre essas partes justificando o desenvolvimento do sistema AntWeb
217. tabela usada para realiza o das estat sticas que informaram ao Administrador Web as mudan as na estrutura do site Esta a tabela que ser usada pelo pr ximo processo formada pelos seguintes atributos P ginaAlvo a p gina que o visitante procurava O sistema reconhece essa p gina atrav s do valor threshold Localiza esEsperadas1 at Localiza esEsperadasN S o as p ginas que o visitante supostamente esperava encontrar um link levando a sua p gina alvo Estas p ginas s o inferidas atrav s das a es de backtrack ou seja quando o visitante usa o mecanismo de voltar a p gina anterior do seu browser Na tabela haver um n mero N de atributos de Localiza o Esperada pois o visitante durante a navega o pode ter acessado N p ginas esperando que em alguma delas existisse link para sua p gina alvo Quando o n mero de Localiza es Esperadas inferior a N os atributos restantes ter o valor nulo Localiza o Atual Localiza o atual do link que levou o visitante a sua p gina alvo A tabela de backtracks o objetivo deste processo Ele depende do processo descrito anteriormente pois a mat ria prima que ele usa para cria o da tabela de localiza es esperada a tabela de logs 43 preencher tabela de backtracks partic o de isi consulta da visitante e backtr ck pag obj existencia do link tabela de logs tabela de links tabela de backtracks Figura 20 Processo
218. tac o mais apropriada O processo de filtragem um processo mais simples dos tr s e consiste apenas em selecionar dados do arquivo de log baseando se na tabela de p ginas O objetivo deste processo filtrar apenas os logs necess rios ao sistema e armazena los na tabela de log O algoritmo detalhado deste processo descrito no Anexo A log consulta da existencia da pagina log filtrado ln arquivo log tabela de paginas tabela de logs Figura 19 Processo de filtragem do arquivo de log 11 1 2 Os processos que envolvem a tabela de backtracks O primeiro processo feito com a tabela de backtrack o seu preenchimento usando a tabela de logs preenchida no processo anterior este processo que descobrir as localiza es esperadas de cada p gina alvo Este processo utiliza tr s objetos Tabela de logs Esta tabela preenchida pelo processo anterior e que 42 a base para a montagem da tabela de localizac o esperada Tabela de links Para se descobrir se o visitante passou de uma p gina para outra atrav s do bot o voltar do navegador ou atrav s de algum link contido na pagina esta tabela fundamental Nela est o cadastrados os links entre as p ginas no site Esta tabela deve ser fornecida pelo Administrador Web do site Possui os seguintes atributos P ginaPai Possui a URL da p gina que cont m o link P gina Possui a URL da p gina que esta sendo apontada pelo o link Tabela de backtracks Esta a
219. tor getOut return null 139 gt lt PHP class Decorator extends DecoratorEnd var next function setNext amp p this gt next amp p function amp getOut if lisset this gt next exit erro return this gt next gt getOut gt lt PHP class Cache extends Decorator var cache array var state passing context function getOut if this gt state passing context return parent getOut if lisset return 140 this gt state pass cache reset this gt cache return null else array_push this gt cache return return return elseif this gt state pass cache list return each this gt cache if return reset this cache return return gt lt PHP class DecoratorBuilder var last function setNext amp current if isset this gt last this gt last gt setNext current 141 this gt last amp current 73 lt PHP class Dissolver extends Decorator var buffer function amp getOut if lisset this gt buffer this gt buffer amp Decorator getOut if lisset this gt buffer return this gt buffer if is_array this gt buffer if element each this gt buffer reset this gt buffer unset this gt buffer return this gt getOut list return element else
220. tor terminar de l los sendo que uma caracter stica marcante da Web a velocidade com que a mesma se desenvolve seja na rea cient fica acad mica seja na vida cotidiana das pessoas VII 6 Publica es referentes a este trabalho Weigang L M V P Dib W M Teles V M de Andrade A C M Alves de Melo J T Cariolano Using ants behavior based simulation model AntWeb to improve website organization in Proc SPIE s Aerospace Defense Sensing and Controls Symposium Data Mining Vol 4730 pp 229 241 Orlando USA 2002 117 W M Teles L Weigang C G Ralha AntWeb The Adaptive Web Server Based on the Ants Behavior WI International Conference on Web Intelligence IEEE WIC Halifax Canada 2003 W M Teles L Weigang C G Ralha Uma heuristica para guiar os usu rios da Internet baseada no comportamento da formiga ENIA Encontro Nacional de Inteligencia Artificial SBC Brazil 2003 118 ANEXO A ALGORITMOS DA IMPLEMENTAC O DE WEBMINING Todos estes algoritmos foram utilizados na implementac o do algoritimo de Webmining de Srikant descrito no Cap tulo Ill Processo de filtragem O processo de filtragem o processo mais simples dos tr s e consiste apenas em selecionar dados do arquivo de log baseando se na tabela de p ginas O objetivo deste processo filtrar apenas os logs necess rios ao sistema e armazen los na tabela de log O algoritmo detalhado usado na implementa o
221. tp intranet normas_internas procedimentos procedimento_atendimento_usuario htm http intranet normas_internas procedimentos procedimento_fabrica_projetos htm http intranet normas_internas medicina_trabalho procedimento htm http intranet normas_internas cipa menucipa htm http intranet normas_internas tabagismo menu_tabagismo htm http intranet normas_internas tabagismo resolucao htm http intranet normas_internas tabagismo ata_12_janeiro_2000 htm http intranet normas_internas tabagismo ata_02_fevereiro_2000 htm http intranet normas_internas ler lerexec_1 htm http intranet administrativo_financeiro menu_adm_financeiro htm http sispoli http intranet coordenacao_contratos menu_coordenacoes_contrato htm http intranet coordenacao_contratos relagao_contratos htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_ABDE htm http intranet coordenacao_contratos pessoal contratos relagao_contrato_ANATEL htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_ASBACE htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_BancoBrasillell htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_BrasilSeg htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_Caixal htm http intranet coordenacao_contratos pessoal contratos relacao_contrato_Caixall htm http intranet coordenacao
222. tyChecker amp adaptabilityChecker function buildCore amp antWeb conection new mySalConection configuration new Configuration dBAccess new DBAccess url new Url conection gt setConfiguration configuration url gt setConfiguration configuration configuration gt setDBAccess dBAccess this gt conection amp conection this gt configuration amp configuration this gt url amp url antWeb gt setConection conection antWeb gt setConfiguration configuration antWeb gt setUrl url function buildDecoratorPheromoneUpdateTrigger amp trigger additionCalculator new QueryAdditionsCalculatorQClicks decoratorBuilder new DecoratorBuilder dissolver new Dissolver 156 flushCloser new FlushCloser intervalMaker new IntervalMakerCache intervalSetter new IntervalSetter lastUpdateExtractor new LastUpdateExtractor pheromoneUpdater new PheromoneUpdater queriesPheromoneUpdater new QueryExecuter queryAddAdditions new QueryAddAdditions queryAdditionCalculator new QueryAdditionsCalculatorQClicks queryCreateUpdatesAux new QueryCreateUpdatesAux queryCreateUrlsAux new QueryCreateUrlsAux queryDecayPheromone new QueryDecayPheromone queryDeleteUpdates new QueryDeleteUpdates queryDeleteUrls new QueryDeleteUrls queryDropAdditions new QueryDropAdditions queryDropUpdatesAux new
223. u rios do site como por exemplo a inserg o de um link na p gina 3B para a p gina 9 conforme mostrado na Figura 18 1A A 3 a AS KIN un Figura 18 Nova estrutura do site ap s a inserc o de um novo link Outra contribuig o deste trabalho de Srikant foi o m todo usado para inferir a s p gina s alvo s nas rotas que os usu rios realizaram no Web Site que tinha como base o tempo que o usu rio permanecia na pagina Apesar das suas contribuic es seu trabalho deixou quest es pendentes como por exemplo um m todo para avaliar a efici ncia da nova estrutura em relac o a antiga Foi visando preencher esta lacuna que o AntWeb para avaliac o de estruturas surgiu O AntWeb fornecia uma medida de efici ncia chamada throughput calculada a partir de informac es obtidas do processo de Webmining e de simulag es de visitantes caminhando na estrutura do site usando o algoritmo AntSystem de Marco Dorigo 31 A seguir descreveremos a implementac o do algoritmo de Srikant o modelo AntWeb para avalia o de estruturas e os experimentos realizados envolvendo o AntWeb 11 1 Implementa o do Algoritmo de WebMining de Srikant O algoritmo de Srikant foi implementado em linguagem Java e banco de dados Access na f brica de softwares da empresa Politec O software desenvolvido foi usado para extrair informa es do log do servidor web em que estava hospedado o site da empresa com objetivo de detectar problemas eventuais existente
224. udesse guardar a estrutura de mais de um WebSite ao mesmo tempo O banco de dados foi constitu do das seguintes tabelas Tabela WebSite Agrupa em websites as p ginas armazenadas no banco Indica tamb m qual a homepage e p gina destino de cada website Tabela p gina Representa as p ginas do website Guarda o tempo de 50 download e de visita de cada p gina Por tratar se de um modelo relacional e n o orientado ao objeto n o guarda refer ncias aos links que cada pagina possui no modelo relacional os links fazem refer ncia tanto p gina pai quanto p gina filho Tabela link uma tabela de relacionamentos pois relaciona as p ginas entre si Armazena o ferom nio presente nos links A Figura 23 mostra os relacionamentos entre as tabelas usando o pr prio IDE do Microsoft Access Relacionamentos L JDIX descricao tempodownload tempovisita website codigo feromonio Figura 23 Relacionamentos entre as tabelas do BD O sistema foi desenvolvido usando o paradigma orientado a objeto Aqui mostramos apenas os principais diagramas do sistemas A Figura 24 mostra o diagrama focalizando as classes de neg cio e persist ncia e a Figura 25 mostra o diagrama focalizando as classes de interface Os diagramas seguem a linguagem UML que hoje a linguagem padr o para descri o de sistemas orientados a objeto 12 Nos diagramas mostrados cada ret ngulo representa uma classe Os ret ngulos possuem tr s
225. unction setPheromoneUpdaterTrigger amp p this gt pheromoneUpdaterTrigger amp p function setIntervalSetter amp i this gt intervalSetter amp i function setQueriesPheromoneUpdater amp p this gt queriesPheromoneUpdater amp p function update while interval Decorator getOut this sintervalSetter ssetinterval interval this gt queriesPheromoneUpdater gt execute this gt pushlnterval interval gt lt PHP class QueryLastUpdate extends Query function generateQuery return select max lastEnd last from Updates gt 200 lt PHP class QuervinsertUris extends Query gt var interval function setInterval amp i this gt interval amp i function generateQuery return INSERT Urls url pheromone SELECT Logs url O FROM Logs WHERE datetime gt this gt interval gt getStart AND datetime lt this gt interval gt getEnd lt PHP class QueryInsertUpdate extends Query var configuration var additionCalculator var interval function setlnterval amp p this gt interval amp p function setQueryAdditionCalculator amp a this gt additionCalculator amp a 201 function setConfiguration amp c this gt configuration amp c function generateQuery end this gt interval gt getEnd star
226. unset this gt type unset this gt name unset this gt atributes this gt dataProcessing s 177 178 function isTag if lisset this gt isTag nontag strip_tags this gt dataProcessing lastcar substr this gt dataProcessing 1 if nontag and lastcar gt and this gt dataProcessing gt this gt is Tag true this gt dataProcessing trim this gt dataProcessing lt gt this gt dataProcessing trim this gt dataProcessing else this gt is Tag false return this gt is Tag function getType if lisset this gt type if this gt isTag l return false if Sthis sdataProcessing 0 179 this gt type END else this gt type START this gt dataProcessing ltrim this gt dataProcessing this gt dataProcessing trim this gt dataProcessing return this gt type function getName if lisset this gt name if this gt getType return false this gt dataProcessing explode this gt dataProcessing this gt name trim strtoupper array shift this gt dataProcessing this gt dataProcessing implode this dataProcessing this gt dataProcessing trim this gt dataProcessing return this gt name function getAtribute a if lisset this gt atributes if this gt getName 180 return false this gt load return isset thi
227. ur lio Carvalho pela sua boa vontade em ajudar nos momentos dif ceis Aos meus colegas do Departamento de Ci ncias da Computa o por terem sido mais do que colegas Ao Jean administrador da rede do departamento de Ci ncia da Computa o pelo apoio t cnico dado hospedagem da implementa o do modelo 1 do AntWeb Aos professores do Departamento de Ci ncias da Computac o da Universidade de Brasilia pelos ensinamentos Aos meus amigos da Internet pelo companherimo virtual SUMARIO Adradeeimentos RE teel u a a a e E iii UMAG RE EE GE ER EE De GE RE CR Eg Oe ie ERP iv Lista de S mbolos Siglas e Abreviag es nnen nn vii Eistadefigliras sn etat ix Eistadeitabelas ren ti as ee varende ER DE DE A eunuch EE EE Dee Xi Lista de SYUACOBS EE tener EE ut xii RESUMO e o xili Abstract ee RR N xiv Capitulo l Introdu o aaa en A ap ia 1 ls Problems nes A d 1 1 2 Objetivo e motiva o do trabalho nennen se 2 I 3 Metodologia e Gali ZAC AG anne 3 1 4 A contribui o do AntWeb no contexto de outros trabalhos neee 4 I 5 Organiza o do trabalho u senken 5 Cap tulo Il Fundamentos qu srad GR ES RE Ga ek ee ee 7 Il 1 A meta heur stica da formiga e suas bases biol gicas nnn 7 1 1 1 Aspectos do comportamento da formiga real nn resne 9 1 1 2 O experimento da ponte bin ria a 10 11 3 3 Simula o com o OBSTACUIO mrt ae 12 Il 14 A versag artificial da Formida ervarener aie nenen
228. ura do Web site da politec nnn ee EE KERE Ee RR RE RE EER Ee 129 Anexo C C digo fonte da implementa o do AntWeb 138 ndice Analitieo sie EG Ge de ee ee ee Ge Ge GE eea eneen geenen enen 213 Bibliografia 215 Vi LISTA DE SIMBOLOS SIGLAS E ABREVIACOES AA Apresentac o Adaptativa ACO Ant Colony Optimization Otimizac o por col nia de formigas AO Adaptative Occultation Ocultac o Adaptativa AW AntWeb BD Banco de Dados CA Classificac o Adaptativa CF Classifica o de Fragmentos CG Condu o Global CIC Departamento de Ci ncia da Computa o da Universidade de Bras lia CL Condu o Local EA Explica o Adicional EC Explica o Comparativa ER Explica o Requerida EV Explica o Variante FR Frames FV Fragmento Variante HA Hiperm dia Adaptativa HTML Hypertext Mark Language linguagem de marca o de texto HTTP Hypertext Transport Protocol protocolo de transporte de hipertexto IP Internet Protocol protocolo da Internet JSP Java Server Pages MA Mapas Adaptativos MU Modelo de Usu rio OD Orienta o Direta OG Suporte Orienta o Global OL Suporte Orienta o Local PHP Personal Home Page Linguagem de programa o do tipo SSSL PV P gina Variante SQL Standard Query Language ST Stretch text SSSL Server Side Script Language Linguagem Script do Lado do Servidor TC Texto Condicional
229. xtends Query function generateQuery return CREATE TEMPORARY TABLE UrlsAux SELECT FROM Urls gt lt PHP class QueryAddAdditions extends Query var configuration function setConfiguration amp p 204 this gt configuration amp p function generateQuery return REPLACE Urls SELECT UrlsAux url UrlsAux pheromone Additions addition this gt configuration gt data decay coefficient pheromone gt FROM UrlsAux INNER JOIN Additions ON UrlsAux url Additions url lt PHP class LastUpdateExtractor var configuration var queryLastUpdate var queryFirstLog function setQueryLastUpdate amp p this gt queryLastUpdate amp p function setQueryFirstLog amp p this gt queryFirstLog amp p function setConfiguration amp p this gt configuration amp p function get if resultado this gt queryLastUpdate gt execute 205 if return mysal result resultado 0 last return return else if resultado this gt queryFirstLog gt execute if Gdate mysql result resultado 0 last timest strtotime date this gt configuration gt data iteration_time return date Y m d H i s timest return null gt lt PHP class IntervalSetter extends QueryExecuter function execute return null function setInterval amp i for j 0 j lt

Download Pdf Manuals

Related Search

Related Contents

Peavey AMD 1220 User's Manual  1024 ESA - 1024A ESA    PhotoniQ Multi-Channel Data Acquisition Systems  1 User manual for the 3-D macro lens model 2002 General  Merge Patient User Guide    Agricultural Spray Products  Kenmore 721.88512 Microwave Oven User Manual  Sony TA-F5000 User's Manual  

Copyright © All rights reserved. Failed to retrieve file