PPGCC - Programa de Pós-graduação em Ciência da Computação

URI permanente desta comunidadehttp://www.hml.repositorio.ufop.br/handle/123456789/596

Navegar

Agora exibindo 1 - 20 de 151

Música evolutiva : uma abordagem computacional para composição algorítmica.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2011) Freitas, Alan Robert Resende de; Guimarães, Frederico Gadelha
Este trabalho descreve uma abordagem para composição algorítmica baseada em algoritmos genéticos. São desenvolvidos dois módulos principais, que são os geradores melódico e harmônico. Um dos maiores problemas quando se usa algoritmos genéticos para evoluir melodias é criar uma medida esteticamente consciente de fitness. Neste trabalho, descreve-se uma nova abordagem com uma medida mínima de fitness na qual um conjunto de boas melodias é retornado no fim do processo. Logo depois, uma abordagem multiobjetivo é usada para harmonização da melodia. O algoritmo evolucionário multiobjetivo define mudanças de acordes com diferentes graus de simplicidade e dis- sonância. Experimentos foram feitos e comparados a julgamento humano dos resultados. As descobertas sugerem ser possível desenvolver funções de fitness que refletem intenções humanas para música.
Detecção de outliers multivariados em redes de sensores.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Valadares, Fabricio Geraldo; Pereira Junior, Álvaro Rodrigues
Esse trabalho apresenta uma análise, via detecção de outliers, sobre os dados multivariados proveniente de uma rede de sensores. Inicialmente, caracterizamos o problema de detecção de outliers nestas redes. Em seguida, realizamos, via simulação, uma comparação entre três métodos gerais para a identificação dos outliers, Minimum Volume Ellipsoid (MVE), Minimum Covariance Determinant (MCD) e Max-Eigen Difference (MED), considerando cenários específicos de uma rede de sensores. Os dados utilizados na simulação foram gerados a partir de uma base de dados reais proveniente da medição de poluentes no ar. Essa geração nos permitiu representar o cenário de uma rede de sensores. O fenômeno avaliado segue um comportamento Normal, e utilizamos outras duas distribuições, Skew-Normal e T-Student, para representar a imprecisão inerente do processo de sensoriamento, que nem sempre consegue representar satisfatoriamente o ambiente monitorado. Adicionalmente, representamos a presença de ruídos nos dados (outliers pontuais), inseridos com base em uma distribuição de Bernoulli. Essa distribuição foi utilizada para selecionar quais amostras seriam substituídas por ruídos. A avaliação da representatividade dos dados após a remoção dos outliers é realizada por intermédio de um ferramental estatístico formado pelos seguintes testes, valor absoluto do erro relativo, ANOVA, medidas de tendência central e a contagem de outliers. Todas as simulações foram realizadas no software estatístico R. Os resultados das avaliações demonstraram que os erros encontrados podem ser tolerados por grande parte das aplicações em redes de sensores, quando aplicados os métodos MVE e MCD. O método MED não conseguiu identificar todos os outliers, logo, sua aplicação não traz benefícios às aplicações consideradas.
Identificação de atributos relevantes em sequências de protease e transcriptase reversa do vírus HIV para a predição da resposta de pacientes ao tratamento com drogas antirretrovirais.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Oliveira, Samuel Evangelista Lima de; Merschmann, Luiz Henrique de Campos
O vírus da Imunode ciência Humana é um retrovirus que ataca principalmente o sistema imunológico humano, reduzindo progressivamente a sua e cácia. Combinações de drogas antirretrovirais são utilizadas no tratamento da infecção por HIV, contudo, as altas taxas de mutação nesse vírus podem desencadear fenótipos virais resistentes a alguns antirretrovirais e, consequentemente, causar falhas no tratamento. Alguns trabalhos propostos na literatura utilizam técnicas de mineração de dados para predizer a resposta de um paciente à terapia antirretroviral que está sendo utilizada. Contudo ainda há poucos estudos que avaliem a in uência que diferentes tipos de atributos na tarefa de predição da resposta de pacientes às drogas antirretrovirais. Neste trabalho é apresentado um estudo comparativo sobre a utilização de diferentes atributos na predição da resposta de pacientes recém infectados pelo HIV-1 ao tratamento com antirretrovirais. Foram utilizados diferentes conjuntos de atributos para o treinamento de quatro modelos de classi cação. A partir desses conjuntos de atributos foram realizadas três etapas de testes que envolveram a avaliação do impacto do desbalanceamento das bases no resultado dos modelos de classi cação, a análise da importância de cada grupo de atributos e, por m, uma etapa de seleção de atributos. A partir da avaliação do impacto do desbalanceamento nas bases de dados pode-se observar que uma etapa de balanceamento ajudou na obtenção de resultados mais equilibrados entre as duas classes do problema de classi cação em questão. Por sua vez a análise da importância dos diferentes grupos de atributos demonstrou que os melhores resultados de predição foram obtidos para os atributos que representam os níveis de resistência dos pacientes às drogas antirretrovirais. Por m, as bases de dados obtidas após uma fase de seleção de atributos apresentaram melhores resultados de predição quando compostas por um conjunto variado de atributos. Nesta etapa dos testes foi possível observar novamente a importância dos atributos de nível de resistência, bem como a importância de um atributo que representa o tamanho de uma determinada proteína do HIV.
GENILS-TS-CL-PR : um algoritmo heurístico para resolução do problema de roteamento de veículos com coleta e entrega simultânea.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Silva, Thaís Cotta Barbosa da; Souza, Marcone Jamilson Freitas
Este trabalho tem seu foco no Problema de Roteamento de Veículos com Coleta e Entrega Simultânea (PRVCES). Dada a dificuldade de solução deste problema, é proposto um algoritmo heurístico nomeado GENILS-TS-CL-PR, que combina os procedimentos heurísticos Inserção Mais Barata, Inserção Mais Barata Múltiplas Rotas, GENIUS, Iterated Local Search (ILS), Variable Neighborhood Descent (VND), Busca Tabu (TS, do inglês Tabu Search) e Reconexão por Caminhos (PR, do inglês Path Relinking). Os três primeiros procedimentos visam a obtenção de uma solução inicial, enquanto os procedimentos VND e TS são usados como métodos de busca local para o ILS. A Busca Tabu somente é acionada após certo número de iterações sem sucesso do VND. As buscas locais fazem uso de uma Lista de Candidatos de forma a evitar o uso de movimentos desnecessários e, assim, reduzir o espaço de busca. O algoritmo proposto foi testado em problemas-teste disponíveis na literatura e se mostrou capaz de gerar soluções de alta qualidade, sendo o algoritmo sequencial mais eficiente da literatura com relação à capacidade de encontrar melhores soluções e com pouca variabilidade.
Representação e computação de cubos de dados completos ou parciais em clusters de computadores de baixo custo.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Moreira, Angélica Aparecida; Lima, Joubert de Castro
A abordagem PnP (Pipe ’n Prune) é considerada uma das abordagens mais promissoras da literatura para computação de cubos em arquiteturas de computadores com memória distribuída. Infelizmente, a abordagem PnP gera uma enorme quantidade de dados redundantes. No geral, a PnP não considera a uniformidade nos dados, denominada skew. Não considerar o skew no particionamento da carga de trabalho impõe máxima redundância de dados, mesmo com dados uniformes. Diante deste cenário, foi desenvolvida a abordagem P2CDM (acrônimo de Parallel Cube Computation with Distributed Memory), que possui comunicação minimizada e gera redundância de dados sob demanda, dependendo do grau de uniformidade dos dados. Neste sentido, a abordagem P2CDM permite a computação de cubos completos a partir de um certo grau de uniformidade nos dados e cubos parciais quando o grau de uniformidade nos dados ultrapassar um limite predefinido. Os experimentos demonstram que as abordagens PnP e P2CDM possuem acelerações similares, porém a abordagem P2CDM ´e 20-25% mais rápida e consome 30-40% menos memória em cada nó do cluster, quando comparada com a abordagem PnP.
Reconciliação de chaves através de um canal público usando acelerômetros.
(2012) Castro, Pedro Henrique Nascimento; Oliveira, Ricardo Augusto Rabelo; Graaf, Jeroen Antonius Maria Van de; Oliveira, Ricardo Augusto Rabelo; Graaf, Jeroen Antonius Maria Van de; Lima, Joubert de Castro; Carneiro, Tiago Garcia de Senna; Santos, Haroldo Gambini
A maioria dos sistemas criptográficos se baseiam em chaves para alcançar a segurança desejada. Essas chaves podem ser obtidas a partir de fontes de dados aleatórias. Quanto maior a aleatoriedade, maior é a sua entropia e, consequentemente, a segurança da chave. Uma possível fonte de entropia seriam os dados de um acelerômetro, que é um instrumento de medição da aceleração de um dispositivo nas três dimensões. Desta forma, é possível criar uma conexão segura entre estes dispositivos a partir da similari- dade de movimento dos mesmos. A leitura destes equipamentos não é muito precisa e, além disso, pode sofrer perturbações do meio. Assim, pode-se utilizar os protocolos de reconciliação de chaves para gerar uma chave comum entre os dispositivos, sem compro- meter a segurança. Este trabalho aplica esses protocolos aos dados dos acelerômetros para prover uma chave criptográfica segura.
BeShort : um algoritmo para encurtamento de URLs.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Freitas, Pedro Paulo Simões; Souza, Fabrício Benevenuto de
Microblogs como o Twitter são sistemas sociais voltados unicamente para a postagem de mensagens com no m aximo 140 caracteres. Com o grande uso de mensagens curtas na Web o uso de encurtadores de URLs est a se tornando cada vez mais comum. Sistemas encurtadores traduzem uma URL com dezenas de caracteres em uma nova URL, tipicamente com poucos caracteres e redirecionam requisi ções da URL encurtada para a URL longa original. Apesar de extremamente e ciente, esses servi cos podem introduzir atrasos para seus usu arios e têm sido amplamente utilizada para ofuscar spam, phishing e malware. Esse trabalho apresenta o BeShort, um algoritmo para encurtamento de URLs capaz de evitar tais problemas. Nossa abordagem consiste em substituir partes frequentes ocorridos (ex. "www" e "http:") por caracteres UTF-8, normalmente nãoo utilizados em URLs. Para testar nossa abordagem, utilizamos uma base contendo 50 milhões de URLs de dois servi ços encurtadores de URL bastante populares. Nossos resultados mostram que o BeShort consegue taxas de encurtamento tão e cientes quanto as taxas praticadas pelas arquiteturas atuais.
Classificação automática de arritmias : um novo método usando classificação hierárquica.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Luz, Eduardo José da Silva; Gomes, David Menotti
De acordo com a organização Mundial de Saúde (OMS), doenças cardíacas são a principal causa de morte no planeta. Todavia, a maioria das doenças cardíacas podem ser diagnosticas e tratadas com antecedência, com o auxílio de exames preventivos. O exame mais utilizado para diagnóstico de doenças cardíacas é chamado Eletrocardiograma (ECG) que podem identicar as arritmias. As arritmias podem se encaixar em duas categorias, arritmias formadas por um único batimento cardíaco irregular ou como um conjunto irregular de batimentos. As arritmias podem ser raras e inofensivas, mas também podem levar à morte rapidamente. Mais efetivo será seu tratamento, quando detectadas o quanto antes. Este trabalho apresenta duas contribuições principais: Primeiro, foi elaborada uma revisão da literatura dos métodos destinados à classificação de arritmias em sinais de ECG e segundo, foi proposto um novo método para classificação de arritmias usando classificação hierárquica. Como contribuições secundárias, investigaram-se novas características para representação do batimento cardíaco baseadas em uma representação 2D do sinal de ECG, o Vectorcardiograma (VCG), e redes complexas. Além disso, investigou-se o uso de uma abordagem wrapper para seleção de características com análise de sensibilidade neste contexto. Os resultados obtidos por este novo método usando classificação hierárquica são comparáveis aos resultados reportados por métodos estado-da-arte. As novas características propostas se mostraram eficientes para discriminação da classe SVEB, que é uma das classes minoritárias. A Classificação Hierárquica se mostrou promissora para o problema de classificação de arritmias e a técnica deve ser explorada por pesquisas futuras.
SIGHabitar - Uma abordagem baseada em Inteligência de negócios para o desenvolvimento de sistemas de informação territorial : o cadastro técnico multifinalitário do município de Ouro Preto, MG.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Silva, João Tácio Corrêa da; Carneiro, Tiago Garcia de Senna
As técnicas para o desenvolvimento de sistemas de informação para a gestão dos territórios municipais têm evoluído rapidamente. A crescente demanda por análises completas e atualizadas para apoiar a tomada de decisão e o planejamento municipal levou à especialização do cadastro imobiliário, cujos fatos relacionam-se com questões imobiliárias, jurídicas e fiscais, em um Cadastro Técnico Multifinalitário (CTM). O CTM busca representar vários outros aspectos do município, como saúde, segurança, educação e meio ambiente. Os Sistemas de Informação Territoriais (SIT) passaram a incorporar métodos e tecnologias de Sistema de Informação Geográfica (GIS) para representar a forma e localização geográficas dos fatos. O armazenamento e análise de um grande volume de dados espaciais e temporais levou a pesquisas por ferramentas que pudessem realizá-los com segurança e eficiência. No entanto, são raras as experiências relatadas na literatura que exploram o uso de técnicas de Inteligência de Negócios (Business Intelligence - BI) para a construção de SITs. Apesar de há anos existirem tecnologias livres para construir SITs, em todo o mundo, pouquíssimos municípios dispõe de um. Este fato justifica-se pela falta de pessoas especializadas para construí-los e mantê-los, de exemplos bem documentados para ser copiado e da garantia de retorno do investimento no sistema. Diante deste cenário, este trabalho procura desenvolver, avaliar e documentar uma abordagem que permita o desenvolvimento de um SIT que seja flexível o suficiente para absorver mudanças no território e nas questões a serem analisadas, sem que elas demandem grandes alterações nos esquemas dos bancos de dados e nas ferramentas para integração e análise. Para isso, métodos e ferramentas de BI foram emprega para implementar o CTM de um município de médio porte como um armazém de dados espaço-temporal (Spatio-Temporal Data Warehouse - STDW). Ferramentas ETL (Extract Transform and Load) foram utilizadas para a integração dos dados e ferramentas OLAP (On Line Analytical Processing) foram utilizadas para análise. Os resultados mostraram que, em dois meses, 92,5% dos 3.037 imóveis registrados na área de estudo foram corretamente georreferenciados e associados a informações de sistemas legados. Estima-se que a maior parte dos investimentos no SIT seja recuperada após o primeiro ano de uso para cobranças de taxas por serviços e de impostos imobiliários.
Reconhecimento de face invariante a iluminação baseado em uma abordagem supervisionada.
(2012) Carneiro, Larissa Natália das Virgens; Cámara Chávez, Guillermo
A crescente relevância dada aos estudos e pesquisas de sistemas automáticos de reconhecimento/identificação de faces capazes de identificar indivíduos nas mais diversas situações é devido às várias possibilidades de aplicações, tais como sistemas de segurança bancários, eleitorais e busca por pessoas desaparecidas. Outro fator é a questão da tarefa de reconhecimento não ser trivial devido aos componentes variantes como envelhecimento, uso de óculos, chapéu, maquiagem, variação de aparência e a variação de iluminação. Esta última é um dos maiores desafios dos sistemas de reconhecimento, pois pode ocultar quase todas as características da face. Assim, o presente trabalho propõe um sistema de reconhecimento de faces invariante à iluminação. O mesmo utiliza como pré-processamento das imagens as técnicas Local Contrast Enhancement (LCE) ou normalização da iluminação no domínio Discrete Consine Transform (DCT), na segunda fase é utilizado o DCT para extração de características e na terceira o Discrimination Power Analysis (DPA) é usado para redução de dimensionalidade. O reconhecimento é feito com o Support Vector Machine (SVM) e os experimentos são realizados em duas etapas. Na primeira são utilizadas as bases de dados Pie e Yale B e o modelo proposto é avaliado quanto ao quesito de variação de iluminação. Na segunda fase são utilizadas as bases JAFFE, AT&T, UMIST e Georgia e o modelo é avaliado quanto à robustez em relação a variação de expressão, rotação e fundo. O método proposto apresenta melhor desempenho e melhores resultados para as variações existentes nas bases testadas.
IDEAL-TRAFFIC : a framework for building monitoring systems for intelligent transportation systems.
(2012) Silva, Saul Emanuel Delabrida; Pereira Junior, Álvaro Rodrigues; Oliveira, Ricardo Augusto Rabelo
The evolution and dissemination of network communication technology and the advanced status of embedded devices encourage the creation of solutions for monitoring cities in various environments. Intelligent Transportation Systems (ITS) is an area that makes use of these technologies, so that end-users can benefit from applications that deliver information in real time. On the other hand, administrating these applications is not a trivial task. Components may fail and invalidate an application. Usually, traffic application's architecture is centralized, fact that increases the cost of maintenance and reduces the flexibility of resources reuse. There are features required on ITS such as adaptability, scalability, heterogeneity, interoperability, openness, accessibility, and flexibility. It was not found on the literature any related work that aims to cover all these features, although some of them are requisites for ITS developed for use in North America and Europe. In this work we present IDEAL-TRAFFIC: a framework based on SOA architecture for building monitoring applications, with the ability to manage the state of the applications. IDEAL-TRAFFIC provides a simple interface that enables system administrators create applications and make them available to end-users. A self-adaptation process is included in the IDEAL-TRAFFIC framework in order to ensure fault tolerance. For the implementation of these features, rules of the application need to be considered and might depend upon the minimum of human intervention, since the framework can use third part systems or legacy systems to retrieve relevant data to continue running an application. In this thesis we have applied the IDEAL-TRAFFIC to two use cases to illustrate its use for ITS. In the first use case, we demonstrate the use of the framework in static nodes. In the second use case, we show how the framework may be integrated with vehicular networks. Three experiments have been launched. In all executions we reproduced the first use case over embedded devices. In order to demonstrate the framework accordance with the main ITS requirements, we illustrate the creation of services using XML SOA files, the communication among devices, the integration of the framework with a legacy system, and the scalability of the system. In all experiments we have obtained the expected results. This fact shows that the IDEAL-TRAFFIC is in accordance with the main ITS requirements. In the experiments launched, it was proved that the use of XML is an effective and efficient alternative, to create applications using services available by several nodes on the network. The proposed process reduces the time of creation of applications.
Algoritmos heurísticos híbridos para o problema de sequenciamento em máquinas paralelas não-relacionadas com tempos de preparação dependentes da sequência.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Haddad, Matheus Nohra; Souza, Marcone Jamilson Freitas
Este trabalho aborda o problema de sequenciamento em máquinas paralelas não- relacionadas com tempos de preparação dependentes da sequência, dó inglês Unre- lated Parallel Machine Scheduling Problem with Sequence Dependent Setup Times, ou apenas UPMSPST. Neste problema há um conjunto de tarefas e máquinas e a cada tarefa está associado um tempo de processamento, que é diferente para cada máquina. Dadas duas tarefas, também existe um tempo de preparação dependente da sequência de lase da máquina utilizada. O objetivo considerado neste problema é minimizar o tempo máximo de conclusão do sequenciamento, o chamado makes pan. OUPMSPST é muito encontrado no âmbito industrial e pertence à classe NP- difícil. Visando a sua resolução, são propostos três algoritmos heurísticos híbridos. O primeiro, nomeado VP, combina os procedimentos heurísticos Iterated Local Search (ILS), Variable Neighborhood Descent (VND)e Path Relinking(PR). O segundo, nomeado GIVP, difere do primeiro pelo fato de gerar a solução inicial pela fase de construção Greedy Randomized AdaptiveS earch Procedure(GRASP), e não por um procedimento guloso. O terceiro algoritmo, nomeado GIVMP, diferedos outros em três estratégias: a fase PR utiliza a estratégia mix edrelinking ao invés de backward relinking, as vizinhanças que formam o VND são usada sem ordem aleatória a cada chamada e não em ordem previamente de nida; por m,o GIVMP inclui um módulo de busca local feita pelo resolvedor CPLEX12.1 de programação matemática. Este resolvedor é aplicado apenas à máquina gargalo do problema e utiliza um modelo de programação inteira mista base a dono problemado Caixeiro Viajante Assimétrico. Para explorar o espaço de soluções são utilizados movimentos de inserção e troca de tarefas entre máquinas. Para testar os algoritmos foram utilizados dois conjuntos de problemas-teste da literatura. Inicialmente eles foram comparados entre si em um conjunto reduzido de instâncias ,tendo- severi cado a superioridade do algoritmo GIVMP. Em seguida, este algoritmo foi compara do com outros seis da literatura, sendo dois no primeiro conjunto de problemas- teste e outros quatro no Segundo. No primeiro conjunto veri cou-se a superiorida de absoluta do GIVMP sobre os dois algoritmos genéticos da literatura, tendo-se encontra do desvios percentuais relativos médios menores e novas melhores soluções.No segundo conjunto de problemas-teste vericou-se que o GIVMP tem desempenho inferior a um dos algoritmos, mas superior em relação aos outros três. Observa-se,no entanto,que neste segundo conjunto de problemas, não foram disponibilizados os desvios percentuais relativos médios dos algoritmos, mas apenas os desvios dos melhores valores encontrados,impedindo uma comparação de robustez dos algoritmos.
Técnicas de programação inteira para o problema de escalonamento de enfermeiras.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2012) Gomes, Rafael Antonio Marques; Santos, Haroldo Gambini
Esta dissertação apresenta t écnicas de Programação Inteira (PI) para o problema da Competi ção Internacional de Escalonamento de Enfermeiras (INRC). A partir de uma formula ção compacta e monol tica onde a atual geração dos resolvedores executam de maneira nãoo satisfat oria, melhores estrat egias de gera c~ao de cortes e heur sticas primais s~ao propostas e avaliadas. Um grande n úmero de experimentos computacionais com estas t écnicas produziram os seguintes resultados: a otimalidade da grande maioria das instâncias foi provada, as melhores soluções conhecidas foram melhoradas em at e 15% e fortes limitantes duais foram obtidos. No esp rito da reprodu ção cient ífica, todo o c ódigo foi implementado utilizando a Infra-Estrutura Computacional para Pesquisa Operacional (COIN-OR).
GeoCube : representação, computação, e visualização de cubos espaciais.
(2012) Rocha, Tárik de Melo e Silva; Lima, Joubert de Castro; Carneiro, Tiago Garcia de Senna; Lisboa Filho, Jugurta; Pereira Junior, Álvaro Rodrigues; Santos, Haroldo Gambini
A tecnologia SOLAP (Spatial On-Line Analytical Processing) oferece a junção das funcionalidades OLAP (Online Analytical Processing ) e SIG (Sistema de Informação Geográfica) e abre caminho para uma nova categoria de aplicações que fornecem suporte a manipulação, processamento e navegação em dados espaço-temporais organizados hierarquicamente. Os dados em um sistema OLAP são armazenados como cubos e estes são organizados segundo o conceito de dimensões, medidas e hierarquias. A materialização de um cubo de dados possui ordem de complexidade exponencial em relação ao consumo de memória e tempo de execução. Quando associamos informações espaciais ao cubo, a demanda de memória e processamento aumenta, tornando mais difícil a tarefa de oferecer respostas rápidas ao usuário. Atualmente, poucos trabalhos foram publicados na representação, computação e consulta de cubos espaço-temporais completos. As técnicas apresentadas como materialização seletiva, materialização baseada em aproximações e estruturas para indexação de regiões não oferecem soluções para computação de cubos completos e muitas vezes não podem ser aplicadas para uma grande variedade de funções de agregação espaciais. Arquiteturas de computadores baseadas em endereçamento compartilhado também não são utilizadas nos trabalhos correlatos. Nos trabalhos correlatos as hierarquias são especificadas manualmente por especialistas do domínio e muitas vezes as soluções limitam a quantidade e a variedade de medidas espaciais e não espaciais no cubo. Diante de tal cenário, é proposta uma abordagem para representação, computação e vi consulta de cubos espaço-temporais completos ou parciais, chamada GeoCube. A abordagem GeoCube pode ser executada em máquinas com múltiplos núcleos de processamento. Múltiplas funções de agregação espacial e estatística podem ser combinadas. Também é proposta uma abordagem para formação automática de hierarquias através de regras de vizinhança entre seus objetos espaciais. As regras de vizinhança podem ser definidas pelo usuário e executadas pelo GeoCube. O GeoCube já possui vizinhança nxn, onde n>1. Testes comparativos com um sistema implementado usando PostGIS e vistas materializadas mostram que a GeoCube consegue computar cubos de dados espaciais em até 1/6 do tempo gasto pela tecnologia PostGis em uma máquina com 8 núcleos de processamento.
s-WIM : a scalable web information mining tool.
(2012) Melo, Felipe Santiago Martins Coimbra de; Pereira Junior, Álvaro Rodrigues; Pereira Junior, Álvaro Rodrigues; Lima, Joubert de Castro; Souza, Fabrício Benevenuto de; Ziviani, Nivio
Mineração Web pode ser vista como o processo de encontrar padrões na Web por meio de técnicas de mineração de dados. Mineração Web é uma tarefa computacionalmente intensiva, e a maioria dos softwares de mineração são desenvolvidos isoladamente, o que torna escalabilidade e reusabilidade difı́cil para outras tarefas de mineração. Mineração Web é um processo iterativo onde prototipagem tem um papel essencial para experimentar com diferentes alternativas, bem como para incorporar o conhecimento adquirido em iterações anteriores do processo. Web Information Mining (WIM) constitui um modelo para prototipagem rápida em mineração Web. A principal motivação para o desenvolvimento do WIM foi o fato de que seu modelo conceitual provê seus usuários com um nı́vel de abstração apropriado para prototipagem e experimentação durante a tarefa de mineração. WIM é composto de um modelo de dados e de uma álgebra. O modelo de dados WIM é uma visão relacional dos dados Web. Os três tipos de dados existentes na Web, chamados de conteúdo, de estrutura e dados de uso, são representados por relações. Os principais componentes de entrada do modelo de dados WIM são as páginas Web, a estrutura de hiper- links que interliga as páginas Web, e os históricos (logs) de consultas obtidos de máquinas de busca da Web. A programação WIM é baseada em fluxos de dados (dataflows), onde sequências de operações são aplicadas às relações. As operações são definidas pela álgebra WIM, que contém operadores para manipulação de dados e para mineração de dados. WIM materializa uma linguagem de programação declarativa provida por sua álgebra. O objetivo do presente trabalho é o desenho de software e o desenvolvimento do Scalable Web Information Mining (s-WIM), a partir do modelo de dados e da álgebra apresentados pelo WIM. Para dotar os operadores com a escalabilidade desejada – e consequentemente os programas gerados por eles – o s-WIM foi desenvolvido sobre as plataformas Apache Hadoop e Apache HBase, que provêem escalabilidade linear tanto no armazenamento quanto no processamento de dados, a partir da adição de hardware. A principal motivação para o desenvolvimento do s-WIM é a falta de ferramentas livres que ofereçam tanto o nı́vel de abstração provido pela álgebra WIM quanto a escalabilidade necessária à operação sobre grandes bases de dados. Além disso, o nı́vel de abstração provido pela álgebra do WIM permite que usuários sem conhecimentos avançados em linguagens de programação como Java ou C++ também possam utilizá-lo. O desenho e a arquitetura do s-WIM sobre o Hadoop e o HBase são apresentados nesse trabalho, bem como detalhes de implementação dos operadores mais complexos. São também apresentados diversos experimentos e seus resultados, que comprovam a escalabilidade do s-WIM e consequentemente, seu suporte à mineração de grandes volumes de dados.
Um algoritmo de estimação de distribuição para otimização multiobjetivo baseado em colônia de abelhas e clusters.
(2013) Novais, Fabiano Tomás; Guimarães, Frederico Gadelha
Neste trabalho, propõem-se um novo algoritmo híbrido denominado Multiobjective Optimization Estimation of Distribution Algorithm Based on Bee Colonies and Clusters (MOEDABC) para resolução de problemas de otimização multiobjetivo de larga escala no domínio contínuo. Este algoritmo é inspirado na organização de uma colônia de abelhas e baseia-se nos algoritmos de estimação de distribuição. Como forma de gerar melhores soluções utiliza-se também técnicas de clusterização com a finalidade de aumentar a convergência local das soluções na fronteira Pareto. O algoritmo é baseado em quatro tipos de abelhas: as campistas, as observadoras, as nutrizes e as escoteiras, onde cada uma utiliza uma forma diferente de gerar as novas soluções. Combinando diferentes técnicas como clusterização, estimação de distribuição e algoritmos genéticos possibilitou-se um melhor aprendizado por meio de modelos probabilísticos baseados em distribuições Gaussianas e de Cauchy, obtendo assim soluções de maior qualidade. Em busca de obter maior flexibilidade do algoritmo na resolução de problemas foi introduzido um feromônio de controle responsável por controlar a proporção de cada tipo de abelhas na colônia. Comparado com outros algoritmos os resultados obtidos demonstram que o algoritmo proposto apresenta uma maior velocidade de convergência e uma melhor distribuição das soluções na fronteira Pareto conforme os indicadores utilizados.
Proposta e avaliação de um sistema automático para identificação de veículos.
(2013) Oliveira Neto, Vantuil José de; Menotti, David; Menotti, David; Cámara Chávez, Guillermo; Bianchi, Andrea Gomes Campos; Facon, Jacques; Guimarães, Silvio Jamil Ferzoli; Santos, Haroldo Gambini
Sistemas automáticos de identificação de veículos têm como objetivo a identificação de automóveis por meio de suas placas. A maioria dos trabalhos relatados na literatura científica utilizam imagens únicas de um veículo, em geral capturadas sob condições de iluminação e distância controladas, utilizando em muitos casos um gatilho que informa ao sistema qual o momento em que a imagem deve ser processada pelo sistema. Nosso sistema parte de uma abordagem diferente: a localização e o rastreamento dos veículos ao longo da cena. Com esta abordagem o uso do gatilho é dispensado, a área para localização da placa é diminuída devido ao rastreamento do veículo e a quantidade de quadros disponíveis para um mesmo veículo é aumentada. Construímos uma base de vídeos com 1061 veículos divididos em 23 vídeos diferentes, capturados em quatro pontos distintos no acesso principal da nossa universidade. O sistema foi desenvolvido utilizando C++ e OpenCv, e constituído de 6 módulos: localização de movimento, rastreamento de veículos, seleção do melhor frame, localização da placa, segmentação dos caracteres e reconhecimento; cada um dos módulos foi construído independentemente, permitindo assim que trabalhos futuros alterem apenas um destes módulos, dando mais flexibilidade a trabalhos futuros. O sistema funciona em tempo real, processando o vídeo em menos tempo do que o tempo total do vídeo. Em nossa base, o sistema foi capaz de identificar perfeitamente apenas 27,7% dos veículos, no entanto de reconhecer 54,7% dos caracteres rotulados. Em pontos de referência mais adequados, atingimos 65,8% e 65,03% de reconhecimento de caracteres, com 71,11% e 70,30% de identificação de veículos com quatro ou mais dígitos da placa corretamente reconhecidos. Embora o sistema não apresente resultados promissores nos vídeos avaliados, ele abre espaço para que diferentes métodos e abordagens encapsulados em módulos do sistema possam ser facilmente avaliados.
Algoritmos multiobjetivos para o problema de sequenciamento de tarefas em uma máquina com tempo de preparação dependente da sequência e da família.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2013) Rego, Marcelo Ferreira; Souza, Marcone Jamilson Freitas
Este trabalho trata do Problema de Sequenciamento de Tarefas em Uma Máquina com Tempo de Preparação Dependente da Sequência e da Família. Nesse problema, um conjunto de tarefas devem ser processadas por uma máquina, sendo que antes da execução de cada tarefa é necessário um tempo para preparar a máquina, o qual é de nido de acordo com a sequência e a família da tarefa. Desta forma, o tempo de preparação da máquina é requerido, apenas, para executar duas tarefas consecutivas que pertencem a famílias diferentes. Consideram-se os objetivos de minimizar o makespan e o atraso total ponderado. Para resolvê-lo, foram analisados sete algoritmos de otimização multiobjetivo. O primeiro é o Multi-objective Variable Neighborhood Search (MOVNS), que é um método de otimização multiobjetivo baseado na metaheur ística Variable Neighborhood Search (VNS). O segundo e o terceiro são duas variantes do MOVNS encontradas na literatura, denominadas MOVNS_Ottoni e MOVNS_Arroyo, que consistem em adicionar um procedimento de intensi cação no MOVNS. O quarto é o Pareto Iterated Local Search (PILS), que é um algoritmo multiobjetivo de busca local com características semelhantes à metaheurística Iterated Local Search (ILS). O quinto é uma variante do PILS proposta neste trabalho, denominada PILS1, em que um novo procedimento de perturbação é desenvolvido. O sexto e o sétimo são o Nondominated Sorting Genetic Algorithm II (NSGA-II) e o Strength Pareto Evolutionary Algorithm 2 (SPEA2), os quais são métodos de otimização baseados no processo de evolução natural para problemas multiobjetivos. Entre os sete algoritmos, cinco são de busca local: MOVNS, MOVNS_Ottoni, MOVNS_Arroyo, PILS e PILS1, e outros dois são de busca populacional: NSGA-II e SPEA2. Esses algoritmos foram comparados em relação às métricas de cardinalidade, distância média, distância máxima, diferença de hipervolume e epsilon. Os resultados computacionais realizados em instâncias-teste geradas aleatoriamente mostraram que o algoritmo PILS1 é estatisticamente superior a todos os outros algoritmos em relação às métricas cardinalidade, distância média, diferença de hipervolume e métrica epsilon, em termos de resultados médios. O PILS1 conseguiu também o melhor resultado médio para a métrica distância máxima; entretanto, a partir da análise estatística não foi possível a rmar que a diferença observada entre ele o NSGA-II era signi cativa.
Métodos de busca heurística para problemas de programação de horários modelados em XHSTT.
(Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto., 2013) Fonseca, George Henrique Godim da; Santos, Haroldo Gambini
O Problema da Programação de Horários Escolares é alvo de diversas pesquisas em Pesquisa Operacional e Inteligência Artificial devido a sua dificuldade de resolução e import^ancia prática. Uma solução para esse problema consiste basicamente na alocação de aulas a horários e na alocação dos recursos para essas aulas. Essa alocação deve atender a várias restrições especificadas a priori. O presente trabalho considera a solução do problema proposto pela Third Interntional Timetabling Competition (ITC2011), a qual inclui um amplo conjunto de inst^ancias originadas de diversas instituições educacionais ao redor do mundo. O presente trabalho prop~oe diversas técnicas de busca local para solucionar o problema. O formato de especificação de inst^ancias considerado foi o XHSTT, permitindo que qualquer inst^ancia especificada no referido formato possa ser manipulada pelos algoritmos propostos. Uma característica estrutural importante da nossa abordagem é o uso da plataforma KHE para gerar soluções iniciais, combinada com uma abordagem de busca multi-vizinhança. Os resultados obtidos incluem o desenvolvimento do algoritmo vencedor da competição. Fomos ainda capazes de encontrar soluções factíveis para treze de dezoito inst^ancias e melhorar quinze de dezesseis melhores soluções conhecidas
Metaheurísticas Busca Tabu para o problema de rodízio de tripulações de ônibus urbanos.
(2013) Andrade, Suelaine Débora Gonçalves de; Silva, Gustavo Peixoto
O Problema de Rodízio das Tripulações (PRT) do sistema de transporte público consiste em atribuir a cada tripulação uma sequência de jornadas para os dias do horizonte de planejamento. Como as jornadas diárias tem durações diferentes, as sequências das jornadas podem resultar em um acúmulo de horas extras ou de horas ociosas. Assim o objetivo do PRT é minimizar as horas extras da escala, compensando-as com ociosidades entre jornadas.Este é o princípio do banco de horas permitido pela legislação, desde que sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema foi resolvido utilizando diferentes implementações do Algoritmo de Busca Tabu. Primeiramente é feita a geração da solução inicial através de uma heurística gulosa. A solução gerada é viável, no entanto os custos são altos. Depois são utilizadas as jornadas criadas e com base em trocas viáveis tenta diminuir o custo de cada rodízio com diferentes versões implementadas de Busca Tabu. Foram implementadas quatro versões: a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra um vizinho melhor; a segunda, denominada BTMV, em que a busca local é efetuada sobre toda a vizinhança; a terceira, BTPV, que utiliza um critério de porcentagem variável para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza critérios de intensificação e diversificação para a Busca Tabu. Ao montar um rodízio, devem ser consideradas as folgas das tripulações ao longo do período. Neste trabalho foi desenvolvido um modelo em dois cenários distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados aos obtidos no trabalho de Prates e Silva (2012) através da metaheurística VNS. Os resultados mostram que as implementações do modelo desenvolvido se aproveitam das características de cada etapa, gerando soluções mais econômicas.cada tripulação uma sequência de jornadas para os dias do horizonte de planejamento. Como as jornadas diárias tem durações diferentes, as sequências das jornadas podem resultar em um acúmulo de horas extras ou de horas ociosas. Assim o objetivo do PRT é minimizar as horas extras da escala, compensando-as com ociosidades entre jornadas. Este é o princípio do banco de horas permitido pela legislação, desde que sejam respeitadas as restrições operacionais e leis trabalhistas. Neste trabalho o problema foi resolvido utilizando diferentes implementações do Algoritmo de Busca Tabu. Primeiramente é feita a geração da solução inicial através de uma heurística gulosa. A solução gerada é viável, no entanto os custos são altos. Depois são utilizadas as jornadas criadas e com base em trocas viáveis tenta diminuir o custo de cada rodízio com diferentes versões implementadas de Busca Tabu. Foram implementadas quatro versões: a primeira versão, BTMP, que possui menor tempo da busca local para quando encontra um vizinho melhor; a segunda, denominada BTMV, em que a busca local é efetuada sobre toda a vizinhança; a terceira, BTPV, que utiliza um critério de porcentagem variável para a busca pelo melhor vizinho e a quarta versão BTID, que utiliza critérios de intensificação e diversificação para a Busca Tabu. Ao montar um rodízio, devem ser consideradas as folgas das tripulações ao longo do período. Neste trabalho foi desenvolvido um modelo em dois cenários distintos: um que não considera a atribuição das folgas e outro que realiza esta atribuição. Posteriormente os resultados foram comparados aos obtidos no trabalho de Prates e Silva (2012) através da metaheurística VNS. Os resultados mostram que as implementações do modelo desenvolvido se aproveitam das características de cada etapa, gerando soluções mais econômicas.