| |
| Acadêmico(a): Fernando dos Santos |
| Título: Implementação Distribuída do Algoritmo Adopt |
| |
| Conclusão: |
| O framework dynDCSP, devido a sua arquitetura em camadas, mostrou-se bastante flex´ivel a altera¸c˜oes. A comprova¸c˜ao disto est´a no fato de que, para adicionar ao framework a capacidade de resolver COPs, bastaram poucas refatora¸c˜oes nas classes existentes e a inclus˜ao de algumas novas classes. Outro ponto positivo do framework ´e a utiliza¸c˜ao de express˜oes l´ogicas e aritm´eticas para especificar restri¸c˜oes e fun¸c˜oes de custo pois, por serem especificadas de maneira an´aloga as express˜oes utilizadas no universo matem´atico, sua compreens˜ao ´e r´apida e a utiliza¸c˜ao facilitada. A utiliza¸c˜ao da infraestrutura de comunica¸c˜ao SACI torna transparente ao desenvolvedor o processo de comunica¸c˜ao entre os agentes, realizando esta tarefa com sucesso. Em fun¸c˜ao da implementa¸c˜ao ser feita na linguagem Java, o requisito de portabilidade ´e seguramente atendido. A implementa¸c˜ao do algoritmo Adopt foi realizada com sucesso. Testes realizados a partir de estudo de caso com problema de colora¸c˜ao de grafo corroboraram uma implementa¸c˜ao correta e efetivamente funcional, j´a que apresentou as mesmas solu¸c˜oes da implementa¸c˜ao de Modi (2003a) (o autor do algoritmo). Pesquisa realizada em Pearce (2005) (um reposit´orio de implementa¸c˜oes do algoritmo Adopt) mostrou que a implementa¸c˜ao do algoritmo Adopt realizada neste trabalho ´e a primeira a operar em um ambiente distribu´ido formado por v´arios hosts. A respeito da capacidade do algoritmo Adopt resolver DCOP, algumas considera¸c˜oes merecem ser feitas. Conforme Modi et al. (2003d) afirmam, o algoritmo Adopt garante solu¸c˜ao ´otima em situa¸c˜oes onde o grafo de restri¸c˜oes ´e esparso, ou seja, onde o grau de cada v´ertice ´e pequeno. Nestas situa¸c˜oes o funcionamento do algoritmo Adopt ´e muito bom, convergindo rapidamente para uma solu¸c˜ao. Esta caracter´istica ´e comprovada com o estudo de caso do problema de colora¸c˜ao de grafo apresentado neste trabalho, composto por oito v´ertices sendo o maior grau igual a quatro havendo oito v´ertices. Neste estudo de caso, o tempo utilizado pela implementa¸c˜ao do algoritmo Adopt deste trabalho ´e menor que o utilizado pela implementa¸c˜ao de Modi (2003a), al´em da quantidade de mensagens enviadas, sendo bastante superior na implementa¸c˜ao de Modi (2003a) pois a mesma n˜ao otimiza o envio de mensagens. J´a para problemas onde o grafo de restri¸c˜oes ´e mais denso, o desempenho do algoritmo Adopt n˜ao ´e satisfat´orio. Modi (2003b) observa que, no pior caso (o de um grafo completo), o desempenho do algoritmo Adopt ´e exponencial ao n´umero de vari´aveis, isto porque os COP fazem parte do conjunto de problemas NP-completos. Este fato foi verificado no estudo de caso do problema de modelagem molecular. Sendo o problema de modelagem molecular definido como um somat´orio de energias de intera¸c˜oes onde a solu¸c˜ao ´e encontrada ao minimizar este somat´orio, a abordagem utilizada neste trabalho, de definir cada intera¸c˜ao entre os ´atomos como uma vari´avel do COP e as fun¸c˜oes de custo como as equa¸c˜oes que definem cada uma destas intera¸c˜oes, tornou o grafo de restri¸c˜oes do problema muito denso, o que inviabilizou a sua resolu¸c˜ao atrav´es do algoritmo Adopt devido ao tempo que seria necess´ario para resolvˆe-lo. |
| |
|
