Made available in DSpace on 2014-06-12T15:53:30Z (GMT). No. of bitstreams: 2 arquivo1920_1.pdf: 3817805 bytes, checksum: 7b50528318a4bbf365ddf3fc6ad1ca73 (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2009 / Conselho Nacional de Desenvolvimento Científico e Tecnológico / Os algoritmos de busca meta-heurística vêm sendo pesquisados em inúmeros domínios, inclusive na resolução de restrições. Devido à sua capacidade de atuação em problemas que a solução é desconhecida, são utilizados em diversas situações. Os algoritmos evolutivos são uma família dos algoritmos de busca, que simulam o comportamento da natureza. Os problemas de satisfação de restrição (CSP) são compostos por um conjunto de conjunções de variáveis, caracterizando uma restrição. Valores são associados às variáveis, os quais devem satisfazer a restrição, caso contrário, são considerados inválidos. Problemas de resolução de restrição estão associados a diversos contextos, desde problemas de alocação de recursos a design de circuitos integrados. Algoritmos de busca meta-heurística vêm sendo utilizados para a solução de CSP, resolvendo o problema da limitação dos provadores de teoremas, que necessitam modelar uma teoria para serem capazes de encontrar uma solução. Neste trabalho, investigamos o uso do algoritmo de busca meta heurística em um tipo de teste de software (execução concólica) que é tratado como um problema de CSP. A execução concólica se baseia no teste simbólico, o qual extrai as decisões internas de um programa que formam uma restrição, também conhecidas como Path Condition (PC). Estas restrições são formadas a partir das variáveis de entrada, portanto, a solução de uma restrição determina as entradas necessárias para percorrer um determinado caminho no software. As técnicas clássicas utilizam provadores de teoremas, os quais são limitados a teoria suportada, e métodos de randomização, que geram valores aleatórios para as variáveis, reduzindo a complexidade da restrição. A presente dissertação teve como objetivo criar e analisar o desempenho de solucionadores baseados em algoritmos de busca meta-heurística, sendo comparados às técnicas clássicas utilizadas neste contexto. Os resultados mostraram que o uso de heurísticas de busca pode permitir a criação de novas técnicas de resolução de restrição, no contexto de teste simbólico

Made available in DSpace on 2014-06-12T16:00:01Z (GMT). No. of bitstreams: 2 arquivo5815_1.pdf: 5568534 bytes, checksum: c4f94d52da70aa2e4b63d53050048c4a (MD5) license.txt: 1748 bytes, checksum: 8a4605be74aa9ea9d79846c1fba20a33 (MD5) Previous issue date: 2011 / Faculdade de Amparo à Ciência e Tecnologia do Estado de Pernambuco / Máquinas de Vetores Suporte (SVM) é uma poderosa técnica de Aprendizagem de Máquina (AM) fundamentada na teoria do aprendizado estatístico utilizada para problemas de classificação, reconhecimento de padrões, dentre outros. Em função de seu forte embasamento teórico e sua excelente capacidade de generalização, considerada superior diante de muitos algoritmos de aprendizagem, SVM tem atraído o interesse da comunidade de Aprendizagem de Máquina. Nesse contexto, apesar de possuir uma performance eficaz para maioria dos problemas de classificação e regressão, SVM é sensível a seleção adequada dos parâmetros, permitindo a aplicação de muitas estratégias para seleção e otimização do processo para esse tipo de problema, sendo normalmente realizado empiricamente ou através de experimentos por tentativa e erro. No entanto, existe um número significativo de combinações de parâmetros que podem ser utilizados, de forma que a utilização de um processo exaustivo como este se torna inviável, o qual é tratado como um problema de busca. Neste trabalho foi proposto um sistema híbrido para otimização da seleção do parâmetro de regularização do SVM e o parâmetro (gamma) do Kernel RBF utilizando os algoritmos de busca meta-heurísticas Subida da Encosta e Otimização por Enxame de Partículas. O processo de busca foi aplicado em uma grade de busca composta por 38 problemas de benchmark, contendo o valor de desempenho da combinação de 399 parâmetros distintos executados no SVM. As principais contribuições deste trabalho são os resultados da investigação dos algoritmos para o problema de seleção de parâmetros do SVM, comparando-o com a busca aleatória, bem como a realização de experimentos com versões otimizadas dos algoritmos, obtendo resultados mais satisfatórios. Por fim, este trabalho contribui também com a constatação da viabilidade dos algoritmos para o problema com um número fixo de iterações a fim de reduzir o número de execução de muitos parâmetros no SVM

O propósito deste trabalho foi o de elaborar uma metodologia de projeto de embarcações pesqueiras como alternativa ao processo clássico baseado na seqüência da \"Espiral de Projetos\". A metodologia proposta faz uso de um algoritmo de otimização que tem como finalidade automatizar cada uma das etapas e aperfeiçoar o resultado final mediante a busca, dentro do espaço de soluções viáveis (chamadas de soluções satisfatórias), da solução \"ótima\", ou seja, a melhor solução para uma determinada condição. Devido ao fato de cada zona de pesca ter suas características particulares no que diz respeito a condições ambientais (altura das ondas e força do vento), arte de pesca desenvolvida na região e normas impostas pela Autoridade Marítima, foi feita, em particular, uma aplicação ao caso da pesca no litoral peruano, pois foram consideradas no desenvolvimento do trabalho peculiaridades e dados que estão presentes nesta região. Neste sentido, desenvolveu-se um programa automatizado e otimizado baseado em uma seqüência de cálculos que permite projetar, a partir dos requisitos do armador, as características de uma embarcação pesqueira que cumpre um conjunto de restrições impostas e que atende ao objetivo desejado, ou seja, a embarcação que represente, através dessas características, a melhor solução possível para uma função de mérito ou função objetivo imposta. Desta forma, utilizando a técnica da parametrização de embarcações semelhantes, assim como métodos conhecidos para cálculo de características e atributos associados a navios pesqueiros, e também um algoritmo matemático de busca, demonstrou-se que é possível projetar uma embarcação pesqueira, do tipo de cerco, a partir dos requisitos do armador, com bons resultados, em períodos curtos de tempo e dentro das margens esperadas em etapas preliminares de projeto. / The purpose of this work was to develop a methodology for a fishing vessel design as alternative to the classic process based on the sequence of the \"Design Spiral.\" The proposed methodology use an optimization algorithm that aims to automate each one of the stages of the design and to improve the final result by the search, among the space of viable solutions (calls of satisfactory solutions), of the optimal solution, in other words, to find the best solution for a determined condition. Due to different characteristics of each fishing area such as: environmental conditions (height of the waves and wind intensity), the fishing gear used in the region and the rules established by the local Maritime Authority, this tool contemplates specific applications to fishing in the Peruvian coasts. Therefore, the development of this tool considered the corresponding data available for the region and the particularities unique to this fishing ground. In this context, an automated and optimized program was created based on a sequence of calculations, allowing to project, under the owner\'s requirements, fitting the characteristics of a fishing vessel that contemplates the imposed restrictions while achieving the overall objective. In other words, the resulting vessel will achieve, through these characteristics, the best possible solution in terms of functionality and desired requirements. Therefore, using the parametric technique of similar vessels, as well as known methods for the calculation of characteristics and associated attributes for fishing vessels and the use of a search mathematical algorithm, it was demonstrated that it is possible to design a fishing vessel of the seiner type, from the requirements of the owner, with good results, in few periods of time and within expected rates in preliminary stages of the project.

O propósito deste trabalho foi o de elaborar uma metodologia de projeto de embarcações pesqueiras como alternativa ao processo clássico baseado na seqüência da \"Espiral de Projetos\". A metodologia proposta faz uso de um algoritmo de otimização que tem como finalidade automatizar cada uma das etapas e aperfeiçoar o resultado final mediante a busca, dentro do espaço de soluções viáveis (chamadas de soluções satisfatórias), da solução \"ótima\", ou seja, a melhor solução para uma determinada condição. Devido ao fato de cada zona de pesca ter suas características particulares no que diz respeito a condições ambientais (altura das ondas e força do vento), arte de pesca desenvolvida na região e normas impostas pela Autoridade Marítima, foi feita, em particular, uma aplicação ao caso da pesca no litoral peruano, pois foram consideradas no desenvolvimento do trabalho peculiaridades e dados que estão presentes nesta região. Neste sentido, desenvolveu-se um programa automatizado e otimizado baseado em uma seqüência de cálculos que permite projetar, a partir dos requisitos do armador, as características de uma embarcação pesqueira que cumpre um conjunto de restrições impostas e que atende ao objetivo desejado, ou seja, a embarcação que represente, através dessas características, a melhor solução possível para uma função de mérito ou função objetivo imposta. Desta forma, utilizando a técnica da parametrização de embarcações semelhantes, assim como métodos conhecidos para cálculo de características e atributos associados a navios pesqueiros, e também um algoritmo matemático de busca, demonstrou-se que é possível projetar uma embarcação pesqueira, do tipo de cerco, a partir dos requisitos do armador, com bons resultados, em períodos curtos de tempo e dentro das margens esperadas em etapas preliminares de projeto. / The purpose of this work was to develop a methodology for a fishing vessel design as alternative to the classic process based on the sequence of the \"Design Spiral.\" The proposed methodology use an optimization algorithm that aims to automate each one of the stages of the design and to improve the final result by the search, among the space of viable solutions (calls of satisfactory solutions), of the optimal solution, in other words, to find the best solution for a determined condition. Due to different characteristics of each fishing area such as: environmental conditions (height of the waves and wind intensity), the fishing gear used in the region and the rules established by the local Maritime Authority, this tool contemplates specific applications to fishing in the Peruvian coasts. Therefore, the development of this tool considered the corresponding data available for the region and the particularities unique to this fishing ground. In this context, an automated and optimized program was created based on a sequence of calculations, allowing to project, under the owner\'s requirements, fitting the characteristics of a fishing vessel that contemplates the imposed restrictions while achieving the overall objective. In other words, the resulting vessel will achieve, through these characteristics, the best possible solution in terms of functionality and desired requirements. Therefore, using the parametric technique of similar vessels, as well as known methods for the calculation of characteristics and associated attributes for fishing vessels and the use of a search mathematical algorithm, it was demonstrated that it is possible to design a fishing vessel of the seiner type, from the requirements of the owner, with good results, in few periods of time and within expected rates in preliminary stages of the project.

Spanning tree optimization problems are related to many practical applications. Several of these problems are NP-Hard, which limits the utility of exact methods and can require alternative approaches, like metaheuristics. A common issue for many metaheuristics is the data structure used to represent and manipulate the solutions. A data structure with efficient operations can expand the usefulness of a method by allowing larger instances to be solved in a reasonable amount of time. We propose the 2LETT data structure and uses it to represent spanning trees in two metaheuristics: mutation-based evolutionary algorithms and local search algorithms. The main operation of 2LETT is the exchange of one edge in the represented tree by another one, and it has O(√n) time, where n is the number of vertices in the tree. We conducent qualitative and quantitative evaluations for 2LETT and other structures in the literature. For the main operation of edge exchange in evolutionary algorithms, the computational experiments show that 2LETT has the best performance for trees with more than 10,000 vertices. For local search algorithms, 2LETT is the best option to deal with large trees with large diameters. / Os problemas de otimização de árvores geradoras estão relacionados a muitas aplicações práticas. Vários desses problemas são NP-difícies, o que limita a utilidade de métodos exatos e pode exigir abordagens alternativas, como metaheurísticas. Um questão relevante para muitas metaheurísticas é a estrutura de dados usada para representar e manipular as soluções. Uma estrutura de dados com operações eficientes pode aumentar a utilidade de um método, permitindo que instâncias maiores sejam resolvidas em um período de tempo razoável. Propomos a estrutura de dados 2LETT e a usamos para representar árvores geradoras em duas metaheurísticas: algoritmos evolutivos baseados em mutações e algoritmos de busca local. A operação principal da 2LETT é a troca de uma aresta na árvore representada por outra aresta. Esta operação tem tempo de O(√n), onde n é o número de vértices na árvore. Conduzimos avaliações qualitativas e quantitativas para 2LETT e outras estruturas na literatura. Para a principal operação de troca de arestas em algoritmos evolutivos, os experimentos computacionais mostram que a 2LETT possui o melhor desempenho para árvores com mais de 10.000 vértices. Para algoritmos de busca local, o 2LETT é a melhor opção para lidar com árvores grandes com grandes diâmetros.

A segmentação de imagens consiste em dividir uma imagem em regiões ou objetos que a compõem, como, por exemplo, para isolar os pixels de um objeto alvo de uma dada aplicação. Em segmentação de imagens médicas, o objeto de interesse comumente apresenta transições em suas bordas predominantemente do tipo claro para escuro ou escuro para claro. Métodos tradicionais por região, como a conexidade fuzzy relativa (RFC - Relative Fuzzy Connectedness), não distinguem bem entre essas bordas similares com orientações opostas. A especificação da polaridade de contorno pode ajudar a amenizar esse problema, o que requer uma formulação matemática em grafos dirigidos. Uma discussão sobre como incorporar essa propriedade no arcabouço do RFC é apresentada neste trabalho. Uma prova teórica da otimalidade do novo algoritmo, chamado conexidade fuzzy relativa com orientação (ORFC - Oriented Relative Fuzzy Connectedness), em termos de uma função de energia em grafos dirigidos sujeita as restrições de sementes é apresentada, bem como a sua apli- cação em poderosos métodos híbridos de segmentação. O método híbrido proposto ORFC &Graph Cut preserva a robustez do ORFC em relação à escolha de sementes, evitando o problema do viés de encolhimento do método de Corte em Grafo (GC - Graph Cut), e mantém o forte controle do GC no delineamento de contornos de bordas irregulares da imagem. Os métodos propostos são avaliados usando imagens médicas de ressonáncia magnética (RM) e tomografia computadorizada (TC) do cérebro humano e de estudos torácicos. / Image segmentation consists of dividing an image into its composing regions or objects, for example, to isolate the pixels of a target object of a given application. In segmentation of medical images, the object of interest commonly presents transitions at its border predominantly from bright to dark or dark to bright. Traditional region-based methods of image segmentation, such as Relative Fuzzy Connectedness (RFC), do not distinguish well between similar boundaries with opposite orientations. The specification of the boundary polarity can help to alleviate this problem but this requires a mathematical formulation on directed graphs. A discussion on how to incorporate this property in the RFC framework is presented in this work. A theoretical proof of the optimality of the new algorithm, called Oriented Relative Fuzzy Connectedness (ORFC), in terms of an energy function on directed graphs subject to seed constraints is presented, and its application in powerful hybrid segmentation methods. The hybrid method proposed ORFC&Graph Cut preserves the robustness of ORFC respect to the seed choice, avoiding the shrinking problem of Graph Cut (GC), and keeps the strong control of the GC in the contour delination of irregular image boundaries. The proposed methods are evaluated using magnetic resonance medical imaging (MR) and computed tomography (CT) of the human brain and thoracic studies.

With a digital game industry in constant ascendant and a more demanding consumer, designers and programmers have faced even bigger challenges to create realistic games. In this way, people are working a lot in the NPCs (Non Player Characters) intelligence. In this research, it was emphasized the use of planning to control the Artificial Intelligence of the NPCs. The work documented here was guided by the verification of two hypotheses: the viability of using a planner based on the A* algorithm and on a knowledge representation model similar to STRIPS system in strategic games, and the possibility of using this planner in a Multiagent System approach based on an auction system used to identify agents more appropriated to fulfill a goal. The term strategic games was chosen to avoid misunderstandings about the traditional RTS games. The planner and the Multiagent System have been implemented and several tests were made. The results were satisfactory and the hypotheses proved. / Com a indústria de jogos eletrônicos em constante crescimento e com um consumidor cada vez mais exigente, designers e programadores enfrentam, cada vez, maiores desafios para criar jogos realísticos. Nesse sentido, um tópico que vem sendo trabalhado bastante é a inteligência dos NPCs (Non Player Characters). Neste trabalho foi enfatizado o uso de técnicas de planejamento para controlar a Inteligência Artificial dos NPCs. A pesquisa documentada nesta dissertação foi guiada pela verificação de duas hipóteses: a viabilidade de utilização de um planejador baseado no algoritmo A* e em um modelo de representação de conhecimentos semelhante a do sistema STRIPS em jogos de estratégia; a possibilidade de uso desse planejador e de uma abordagem multiagente baseada em um sistema de leilões onde este último teria como função identificar o agente mais apto para cumprir uma determinada meta. O termo jogos de estratégia foi usado para não gerar confusão com relação aos jogos RTS tradicionais. O planejador e o sistema multiagente foram implementados e ínumeros testes realizados. Os resultados foram satisfatórios e as hipóteses comprovadas. / Mestre em Ciência da Computação

A segmentação de imagens consiste em dividir uma imagem em regiões ou objetos que a compõem, como, por exemplo, para isolar os pixels de um objeto alvo de uma dada aplicação. Em segmentação de imagens médicas, o objeto de interesse comumente apresenta transições em suas bordas predominantemente do tipo claro para escuro ou escuro para claro. Métodos tradicionais por região, como a conexidade fuzzy relativa (RFC - Relative Fuzzy Connectedness), não distinguem bem entre essas bordas similares com orientações opostas. A especificação da polaridade de contorno pode ajudar a amenizar esse problema, o que requer uma formulação matemática em grafos dirigidos. Uma discussão sobre como incorporar essa propriedade no arcabouço do RFC é apresentada neste trabalho. Uma prova teórica da otimalidade do novo algoritmo, chamado conexidade fuzzy relativa com orientação (ORFC - Oriented Relative Fuzzy Connectedness), em termos de uma função de energia em grafos dirigidos sujeita as restrições de sementes é apresentada, bem como a sua apli- cação em poderosos métodos híbridos de segmentação. O método híbrido proposto ORFC &Graph Cut preserva a robustez do ORFC em relação à escolha de sementes, evitando o problema do viés de encolhimento do método de Corte em Grafo (GC - Graph Cut), e mantém o forte controle do GC no delineamento de contornos de bordas irregulares da imagem. Os métodos propostos são avaliados usando imagens médicas de ressonáncia magnética (RM) e tomografia computadorizada (TC) do cérebro humano e de estudos torácicos. / Image segmentation consists of dividing an image into its composing regions or objects, for example, to isolate the pixels of a target object of a given application. In segmentation of medical images, the object of interest commonly presents transitions at its border predominantly from bright to dark or dark to bright. Traditional region-based methods of image segmentation, such as Relative Fuzzy Connectedness (RFC), do not distinguish well between similar boundaries with opposite orientations. The specification of the boundary polarity can help to alleviate this problem but this requires a mathematical formulation on directed graphs. A discussion on how to incorporate this property in the RFC framework is presented in this work. A theoretical proof of the optimality of the new algorithm, called Oriented Relative Fuzzy Connectedness (ORFC), in terms of an energy function on directed graphs subject to seed constraints is presented, and its application in powerful hybrid segmentation methods. The hybrid method proposed ORFC&Graph Cut preserves the robustness of ORFC respect to the seed choice, avoiding the shrinking problem of Graph Cut (GC), and keeps the strong control of the GC in the contour delination of irregular image boundaries. The proposed methods are evaluated using magnetic resonance medical imaging (MR) and computed tomography (CT) of the human brain and thoracic studies.

Nos últimos anos a Web obteve um crescimento exponencial, se tornando o maior repositório de informações já criado pelo homem e representando uma fonte nova e relevante de informações potencialmente úteis para diversas áreas, inclusive a área nuclear. Entretanto, devido as suas características e, principalmente, devido ao seu grande volume de dados, emerge um problema desafiador relacionado à utilização das suas informações: a busca e recuperação informações relevantes e úteis. Este problema é tratado por algoritmos de busca e recuperação de informação que trabalham na Web, denominados rastreadores web. Neste trabalho é apresentada a pesquisa e desenvolvimento de um algoritmo rastreador que efetua buscas e recupera páginas na Web com conteúdo textual relacionado ao domínio nuclear e seus temas, de forma autônoma e massiva. Este algoritmo foi projetado sob o modelo de um sistema especialista, possuindo, desta forma, uma base de conhecimento que contem tópicos nucleares e palavras-chave que os definem e um mecanismo de inferência constituído por uma rede neural artificial perceptron multicamadas que efetua a estimação da relevância das páginas na Web para um determinado tópico nuclear, no decorrer do processo de busca, utilizando a base de conhecimento. Deste modo, o algoritmo é capaz de, autonomamente, buscar páginas na Web seguindo os hiperlinks que as interconectam e recuperar aquelas que são mais relevantes para o tópico nuclear selecionado, emulando a habilidade que um especialista nuclear tem de navegar na Web e verificar informações nucleares. Resultados experimentais preliminares apresentam uma precisão de recuperação de 80% para o tópico área nuclear em geral e 72% para o tópico de energia nuclear, indicando que o algoritmo proposto é efetivo e eficiente na busca e recuperação de informações relevantes para o domínio nuclear. / Over the last years the Web has obtained an exponential growth, becoming the largest information repository ever created and representing a new and valuable source of potentially useful information for several topics and also for nuclear-related themes. However, due to the Web characteristics and, mainly, because of its huge data volume, finding and retrieving relevant and useful information are non-trivial tasks. This challenge is addressed by web search and retrieval algorithms called web crawlers. This work presents the research and development of a crawler algorithm able to search and retrieve webpages with nuclear-related textual content, in autonomous and massive fashion. This algorithm was designed under the expert systems model, having, this way, a knowledge base that contains a list of nuclear topics and keywords that define them and an inference engine composed of a multi-layer perceptron artificial neural network that performs webpages relevance estimates to some knowledge base nuclear topic while searching the Web. Thus, the algorithm is able to autonomously search the Web by following the hyperlinks that interconnect the webpages and retrieving those that are more relevant to some predefined nuclear topic, emulating the ability a nuclear expert has to browse the Web and evaluate nuclear information. Preliminary experimental results show a retrieval precision of 80% for the nuclear general domain topic and 72% for the nuclear power topic, indicating that the proposed algorithm is effective and efficient to search the Web and to retrieve nuclear-related information.

Submitted by William Justo Figueiro (williamjf) on 2015-07-21T22:37:51Z No. of bitstreams: 1 63c.pdf: 2699232 bytes, checksum: 1ae2013ef31101508f9fef3997d71790 (MD5) / Made available in DSpace on 2015-07-21T22:37:51Z (GMT). No. of bitstreams: 1 63c.pdf: 2699232 bytes, checksum: 1ae2013ef31101508f9fef3997d71790 (MD5) Previous issue date: 2013 / SIMTUR - Sistema Inteligente De Monitoramento de Tráfego Urbano / O crescente aumento do uso de automóveis e de motocicletas tem provocado uma contínua degradação no trânsito urbano das grandes metrópoles. Este cenário é agravado pelas deficiências nos atuais sistemas de transporte público, geradas, em parte, pela falta de informação ao usuário. O presente trabalho apresenta um modelo computacional para um sistema de informação ao usuário de transporte público. Ao contrário de outros trabalhos baseados no algoritmo clássico Dijkstra, a abordagem apresentada faz uso do algoritmo A* para resolução do problema de caminhos mínimos, presente neste contexto, a fim de reduzir o tempo de resposta de maneira que o modelo possa ser utilizado em um sistema real de informação ao usuário. O modelo proposto considera múltiplos critérios de decisão, como a distância total percorrida e o número de transbordos. Um estudo de caso foi realizado utilizando dados reais do transporte público da cidade Porto Alegre com o objetivo de avaliar o modelo computacional desenvolvido. Os resultados gerados foram comparados com aqueles obtidos através do emprego do algoritmo Dijkstra e indicam que a combinação do algoritmo A* com técnicas de aceleração permite reduzir, significativamente, a complexidade de espaço, o tempo de processamento e o número de transbordos. / The increasing use of automobiles and motorcycles has caused a continuous degradation in the traffic of large cities. This scenario gets worse due to shortcomings in the current public transportation, which is entailed, in a certain way, by the lack of information provided to the user. This study shows a computing model for a public transportation user information system. Unlike other studies based on the classical Dijkstra’s algorithm, the approach makes use of the algorithm A* to solve a shortest path problem to reduce the response time so that the model can be used in an real-time web information system. The proposed model takes into account multiple criteria of decision, such as total distance traveled and number of transfers and it was evaluated with data from Porto Alegre’s public transportation. The results were compared to those ones obtained by the use of Dijkstra’s algorithm and indicate that the combination of algorithm A* with acceleration techniques allows reducing significantly the space complexity, processing time and the number of transfers.