[pt] Nesta tese são propostos modelos e algoritmos aproximados para o Problema da Árvore Geradora de Custo Mínimo com Restrição de Diâmetro (AGMD). Este problema modela tipicamente aplicações em projetos de redes de computadores onde todos os vértices devem comunicar-se entre si a um custo mínimo, garantindo um certo nível de serviço. Os modelos propostos por Achuthan e Caccetta para o AGMD são reforçados através da introdução de restrições válidas. Uma relaxação lagrangeana é proposta para o modelo de multifluxo básico de Gouveia e Magnanti. Essa relaxação é utilizada para o desenvolvimento de heurísticas lagrangeanas. Adaptações são realizadas nas heurísticas construtivas propostas por Deo e Abdalla, e por Raidl e Julstrom. São propostas ainda quatro estratégias de busca local, uma heurística do tipo GRASP e outra híbrida. São obtidos limites superiores a menos de 2% do ótimo para as classes de instâncias usadas nos trabalhos de Gouveia e Magnanti, e de Santos, Lucena e Ribeiro. Além disto, obteve-se os melhores resultados conhecidos até o presente momento para 11 instâncias de grafos completos usadas por Raidl, Julstrom e Gruber. / [en] In this work, models and approximation algorithms to solve the Diameter Constrained Minimum Spanning Tree Problem (AGMD) are proposed. This problem typically models network design applications where all vertices must communicate with each other at a minimum cost, while meeting a given quality requirement. The formulations proposed by Achuthan and Caccetta are strengthened with valid inequalities. A lagrangean relaxation is proposed for the multicommodity flow model developed by Gouveia and Magnanti. Adaptations are made in the constructive heuristics proposed by Deo and Abdalla and by Raidl and Julstrom. Four local search procedures, a GRASP algorithm and a hybrid heuristic are proposed. Upper bounds within 2% of the optimal solution values are obtained for the two classes of instances used by Gouveia and Magnanti and by Santos, Lucena and Ribeiro. Moreover, stronger upper bounds are reported for 11 instances in complete graphs used by Raidl, Julstrom and Gruber

Made available in DSpace on 2016-04-29T14:22:48Z (GMT). No. of bitstreams: 1 Fabricio Mario Maia Fava.pdf: 17540766 bytes, checksum: dbdc481a71a11cbb7c042f4b6f5eee16 (MD5) Previous issue date: 2010-09-13 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / Evaluating the quality of interaction with digital games has been a hard task. This is due mainly to the unawareness of proper tools and criteria or to its inappropriate application. The usability methods, for instance, are often used for the analysis of applications aiming productivity. Nevertheless, they are not established regarding the evaluation of interaction with videogames, which are developed to help players to have fun. Another tool adopted to measure the quality of interaction with other digital games is the playability. However, the unawareness of its evaluation criteria makes this method even less explored. So, we propose on this work to discuss the relations between playability and usability in digital games, trying to identify characteristics and concerns in every technique regarding design and evaluation of videogames. To cover up such questions, we weaved dialogues with game researchers as Jesper Juul, Katie Salen and Erick Zimmerman; scholars of topics related to fun and entertainment, as Nicole Lazzaro, Donald Norman and Mihaly Csikszentmihalyi; besides researchers in the field of playability, as Carlo Fabricattore and Aki Jarvinen; and of the usability, like Katherine Isbister, Noah Schaffer and Sauli Laitinen. The knowledge of the topics discussed by these authors led us to adopt the application of usability and playability heuristics as research methodology, with the first person shooting games for computers as gender and study platform. Through this approach it was possible tot identify the observation needs concerning kinds of interaction problems before choosing the evaluation method (playability and usability) that will be used. By doing so, the measurement of the interaction quality will be more accurate and will contribute to the project of games able to keep players emotionally evolved. Considering the few literature about playability and usability in digital games, it is expected that this work help professionals and researchers in the designing and evaluating processes of videogames / Avaliar a qualidade da interação com os jogos digitais tem sido uma tarefa complexa. Isso se deve principalmente ao desconhecimento de ferramentas e critérios adequados ou à sua aplicação de forma inapropriada. Os métodos de usabilidade, por exemplo, são bastante utilizados para a análise de aplicações com Rns de produtividade. No entanto, não estão estabelecidos quanto à avaliação da interação com os videogames, que são desenvolvidos pensando em ajudar os jogadores a terem diversão. Outra ferramenta adotada para mensurar a qualidade da interação com os jogos digitais é a jogabilidade. Todavia, o desconhecimento de seus critérios de avaliação torna esse método ainda pouco explorado. Nesse sentido, propomos com este trabalho discutir as relações entre jogabilidade e usabilidade em jogos digitais, buscando identificar as características e preocupações de cada técnica no que diz respeito ao design e avaliação de videogames. Para dar conta dessas questões, traçamos diálogos com pesquisadores de jogos como Jesper Juul, Katie Salen e Erick Zimmerman; estudiosos das questões relacionadas à diversão e ao entretenimento, como Nicole Lazzaro, Donald Norman e Mihaly Csikszentmihalyi; além de pesquisadores do campo da jogabilidade, como Carlo Fabricattore e Aki Jarvinen; e da usabilidade, como Katherine Isbister, Noah Schaffer e Sauli Laitinen. O conhecimento das questões discutidas por esses autores nos conduziu a adotar a aplicação de heuristicas de jogabilidade e usabilidade como metodologia de pesquisa, tendo os jogos de tiro em primeira pessoa para computador como gênero e plataforma de estudo. Com essa abordagem, foi possivel identificar a necessidade da observação dos tipos de problemas de interação antes da escolha do método de avaliação (jogabilidade e usabilidade) que será utilizado. Dessa forma, a mensuração da qualidade da interação será mais precisa e contribuirá no projeto de jogos capazes de manter os jogadores envolvidos emocionalmente. Considerando a pouca literatura pertinente à jogabilidade e usabilidade nos jogos digitais, espera-se que esse trabalho auxilie profissionais e pesquisadores no processo de design e avaliação de videogames

[pt] Esta tese define os problemas das p-medianas conectadas e o de localização de facilidades não-capacitadas conectadas. Possíveis aplicações incluem problemas de planejamento regional e o projeto de redes de telecomunicações ou de transporte. Para o primeiro problema, duas formulações de programação linear inteira são apresentadas e comparadas. Um destes modelos é adaptado para o segundo problema. Para o problema das p-medianas conectadas, algoritmos aproximados são desenvolvidos. Uma estratégia de busca local híbrida é proposta. Para acelerar as iterações do algoritmo de busca local, idéias como circularidade, melhoria iterativa e o descarte de vizinhos são incorporadas. Heurísticas GRASP e VNS são desenvolvidas incluindo a utilização de um filtro com o objetivo de diminuir os tempos de processamento e do procedimento de reconexão por caminhos com o objetivo de melhorar a qualidade das soluções encontradas. Diversos testes são realizados comparando-se esses algoritmos. Os resultados mostraram a necessidade de se executar um passo adicional de pós-otimização às heurísticas GRASP e VNS propostas. / [en] In this work, the connected p-median and the connected facility location problems are defined. Applications arise in regional planning, design of telecommunications and transportation networks. For the first problem, two integer linear programming formulations are proposed. Adaptations are made in one of these formulations and are used to model the second problem. Approximation algorithms to solve the connected p-median problem are developed. A hybrid local search strategy is proposed. In order to speed up the local search iterations, ideas as circularity, first- improving strategy and discard neighbors are incorporated. A GRASP algorithm and a VNS heuristic are also proposed. A filter is used to reduce the computational time required and a path-relinking is applied to improve the results found. Computational experiments to compare the algorithms are reported. To improve these results, it is applied a post-optimization step to the GRASP and VNS heuristics.

[pt] Uma filogenia é uma árvore que relaciona unidades taxonômicas, baseada na similaridade de seus conjuntos de características. O problema da filogenia consiste em encontrar uma filogenia com o número mínimo de passos evolutivos. O principal objetivo deste trabalho é desenvolver heurísticas híbridas para este problema. Duas estratégias são propostas. A primeira combina a metaheurística GRASP baseada em uma nova estrutura de vizinhança (k-SPR) proposta neste trabalho com um procedimento VND de busca local. A segunda estratégia híbrida combina algoritmos genéticos com uma estratégia de cruzamento inovadora, a qual é uma extensão da técnica de intensificação denominada reconexão por caminhos que foi originalmente aplicada no contexto de outras metaheurísticas, tais como busca tabu e GRASP. Os experimentos computacionais realizados sobre instâncias geradas aleatoriamente e instâncias da literatura científica mostram que os novos algoritmos são bastante robustos e que superaram os outros algoritmos existentes na literatura em termos de qualidade de solução e tempos computacionais obtidos. / [en] A phylogeny is a tree that relates taxonomic units, based on their similarities over a set of characters. The phylogeny problem consists in finding a phylogeny with the minimum number of evolutionary steps. The main goal of this work is to develop hybrid heuristics for this problem. Two strategies are proposed. The first combines the GRASP metaheuristic using a new neighborhood structure (k-SPR) proposed in this work with a VND local search procedure. The second hybrid strategy combines genetic algorithms with an innovative optimized crossover strategy which is an extension of the path-relinking intensification technique originally applied in the context of other metaheuristics such as tabu search and GRASP. Computational results on randomly generated and benchmark instances are reported, showing that the new heuristics are quite robust and outperform the others algorithms in the literature in terms of solution quality and computational time.

Submitted by Automa??o e Estat?stica (sst@bczm.ufrn.br) on 2017-04-17T22:16:50Z No. of bitstreams: 1 NielsenCasteloDamascenoDantas_TESE.pdf: 581150 bytes, checksum: 9543323aa1568bdc35f349c906b0c64b (MD5) / Approved for entry into archive by Arlan Eloi Leite Silva (eloihistoriador@yahoo.com.br) on 2017-04-19T21:06:11Z (GMT) No. of bitstreams: 1 NielsenCasteloDamascenoDantas_TESE.pdf: 581150 bytes, checksum: 9543323aa1568bdc35f349c906b0c64b (MD5) / Made available in DSpace on 2017-04-19T21:06:11Z (GMT). No. of bitstreams: 1 NielsenCasteloDamascenoDantas_TESE.pdf: 581150 bytes, checksum: 9543323aa1568bdc35f349c906b0c64b (MD5) Previous issue date: 2016-10-05 / O k-means ? um algoritmo benchmark bastante utilizado na ?rea de minera??o de dados.Ele pertence ? grande categoria de heur?sticas com base em etapas delocaliza??o-aloca??o que, alternadamente, localiza centros de cluster e atribu?pontos de dados a eles at? que nenhuma melhoria seja poss?vel. Tais heur?sticass?o conhecidas por sofrer de um fen?meno chamado de degenera??o, em que,alguns dos clusters ficam vazios, e, portanto, fora de uso. Nesta tese, prop?e-sevarias compara??es e uma s?rie de estrat?gias para contornar solu??esdegeneradas durante a execu??o de k-means. Os experimentos computacionaisdemonstram que essas estrat?gias s?o eficientes e levam a melhoressolu??es de agrupamento na grande maioria dos casos testados.

Submitted by Isaac Francisco de Souza Dias (isaac.souzadias@ufpe.br) on 2016-05-20T17:36:32Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO WalquirFernandes.pdf: 962005 bytes, checksum: 355a53e7ec6f6ea739aedc953d9d9d07 (MD5) / Made available in DSpace on 2016-05-20T17:36:32Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) DISSERTAÇÃO WalquirFernandes.pdf: 962005 bytes, checksum: 355a53e7ec6f6ea739aedc953d9d9d07 (MD5) Previous issue date: 2014-01-30 / As avaliações de usabilidade tornaram-se necessárias no desenvolvimento de artefatos digitais. Esse trabalho visou analisar se o principio tradicional de usabilidade se apresenta adequado quando confrontado com as novas heurísticas de usabilidade aplicadas aos equipamentos médicos de diagnóstico por imagem. Foi realizada uma análise crítica das heurísticas de usabilidade atuais, confrontada com as Heurísticas de Nielsen. O resultado foi a elaboração de 10 heurísticas multiplas, resultante da análise de 4 grupos de heurísticas: -Principios do Design Interativo (Tognazzini) -Schneiderman “8 regras de ouro do Design de Interface”. -Principios de Design, segundo Tufte -Heurísticas de Nielsen. Um estudo de caso comparativo foi realizado entre o conjunto de heurísticas múltiplas e as heurísticas de Nielsen, com intuito de atingir o objetivo da pesquisa. / The evaluations of usability have become necessary in the development of digital artifacts. This study aimed to examine whether the traditional principle of usability itself suitable when confronted with new usability heuristics applied to medical diagnostic imaging equipment. A critical analysis of current usability heuristics, compared with the heuristics of Nielsen was performed. The result was the elaboration of 10 multiple heuristics, resulting from the analysis of 4 groups of heuristics: -Principles of Interactive Design (Tognazzini) -Schneiderman "8 Golden Rules of Interface Design". -Principles of Design, according to Tufte -Nielsen heuristics A comparative case study was conducted among the set of multiple heuristics and Nielsen heuristics, in order to achieve the research objective.

[pt] Sistemas de software estão evoluindo frequentemente devido a diversas requisições de mudanças. A medida que o software evolui, seu tamanho e complexidade aumentam, e consequentemente, sua arquitetura tende a se degradar. Sintomas de degradação arquitetural são por muitas vezes uma consequência direta da inserção progressiva de anomalias de código. Uma anomalia de código é uma estrutura da implementação recorrente que possivelmente indica problemas mais severos no projeto arquitetural. Anomalia de código é considerada crítica quando ela está relacionada problemas estruturais na arquitetura do software. Sua criticidade origina-se da sua influência negativa em uma ampla gama de requisitos não-funcionais. Por exemplo, a presença e anomalias e código críticas dificulta a manutenibilidade e software., ex. uma grande refatoração pode ser necessária para remover um problema arquitetural. Diversas abordagens tem sido propostas para a detecção de anomalias em sistemas de software, mas nenhuma delas suporta eficientemente a priorização e classificação de anomalias de código críticas de acordo com seu impacto na arquitetura. O presente trabalho investiga como a priorização e classificação dessas anomalias críticas de código pode se melhorado com o uso de blueprints arquiteturais. Blueprints arquiteturais são providos pelo arquiteto de software desde estágios iniciais de desenvolvimento do sistema. Blueprints são modelos de projeto informais normalmente definidos para capturar e comunicar as principais decisões de projeto arquitetural. Embora blueprints normalmente sejam incompletos e inconsistentes com respeito a implementação do sistema, eles podem contribuir para o processo de priorização e classificação de anomalias de código críticas. Com o intuito de alcançar nossos objetivos de pesquisa, um conjunto de estudos empíricos foram realizados. O trabalho também propõe e avalia um conjunto de heurísticas para auxiliar desenvolvedores na priorização e classificação de anomalias de código em 3 sistemas de software. Os resultados mostraram uma acurácia média de mais de 60 porcento na priorização e classificação de anomalias de código associadas com problemas arquiteturais nesses sistemas. / [en] Software systems are often evolving due to many changing requirements. As the software evolves, it grows in size and complexity, and consequently, its architecture design tends to degrade. Architecture degradation symptoms are often a direct consequence of the progressive insertion of code anomalies in the software implementation. A code anomaly is a recurring implementation structure that possibly indicates deeper architectural design problems. Code anomaly is considered critical when it is related with a structural problem in the software architecture. Its criticality stems from its negative influence on a wide range of non-functional requirements. For instance, the presence of critical code anomalies hinders software aintainability, i.e. these critical anomalies require wide refactoring in order to remove an architectural problem. Symptoms of architecture degradation have often to be observed in the source code due to the lack of an explicit, formal representation of the software architecture in a project. Many approaches are proposed for detecting code anomalies in software systems, but none of them efficiently support the prioritization and ranking of critical code anomalies according to their architecture impact. Our work investigates how the prioritization and ranking of such critical code anomalies could be improved by using blueprints. Architecture blueprints are usually provided by software architects since the early stages of the system development. Blueprints are informal design models usually defined to capture and communicate key architectural design decisions. Even though blueprints are often incomplete and inconsistent with respect to the underlying implementation, we aim to study if their use can contribute to improve the processes of prioritizing and ranking critical code anomalies. Aiming to address these research goals, a set of empirical studies has been performed. We also proposed and evaluated a set ofheuristics to support developers when prioritizing and ranking code anomalies in 3 software systems. The results showed an average accuracy higher than 60 percent when prioritizing and ranking code anomalies associated with architectural problems in these systems.

[pt] A indústria de transporte marítimo é essencial para o comércio internacional. No entanto, no despertar da crise financeira de 2008, essa indústria foi severamente atingida. Nessas ocasiões, empresas de transporte só são capazes de obter lucro se suas frotas forem roteadas de forma eficaz. Neste trabalho, nós estudamos uma classe de problemas de roteamento de navios relacionados ao Pickup and Delivery Problem with Time Windows. Para resolver esses problemas, nós introduzimos um método heurístico e um exato. O método heurístico é uma meta-heurística híbrida com uma vizinhança larga baseada em set partitioning, enquanto o método exato é um algoritmo de branch-and-price. Nós conduzimos experimentos em um conjunto de instâncias baseadas em rotas de navios reais. Os resultados obtidos mostram que nossos algoritmos superam as metodologias estado da arte. Em seguida, nós adaptamos o conjunto de instâncias para modelar um problema de roteamento de navios no qual a velocidade em cada segmento de rota é uma variável de decisão, e o consumo de combustível por unidade de tempo é uma função convexa da velocidade e carga do navio. A fim de resolver esse novo problema de roteamento de navios com otimização de velocidade, nós estendemos nossa meta-heurística para encontrar decisões de velocidade ótimas em toda avaliação de solução vizinha de uma busca local. Nossos experimentos demonstram que essa abordagem pode ser altamente rentável, e que requer apenas um aumento moderado de recursos computacionais. / [en] The shipping industry is essential for international trade. However, in the wake of the 2008 financial crisis, this industry was severely hit. In these times, transportation companies can only obtain profit if their fleet is routed effectively. In this work, we study a class of ship routing problems related to the Pickup and Delivery Problem with Time Windows. To solve these problems, we introduce a heuristic and an exact method. The heuristic method is a hybrid metaheuristic with a set-partitioning-based large neighborhood, while the exact method is a branch-and-price algorithm. We conduct experiments on a benchmark suite based on real-life shipping segments. The results obtained show that our algorithms largely outperform the state-of-the-art methodologies. Next, we adapt the benchmark suite to model a ship routing problem where the speed on each sailing leg is a decision variable, and fuel consumption per time unit is a convex function of the ship speed and payload. To solve this new ship routing problem with speed optimization, we extend our metaheuristic to find optimal speed decisions on every local search move evaluation. Our computational experiments demonstrate that such approach can be highly profitable, with only a moderate increase in computational effort.

[pt] Clusterização desempenha um papel importante em data mining, sendo útil em muitas áreas que lidam com a análise exploratória de dados, tais como recuperação de informações, extração de documentos e segmentação de imagens. Embora sejam essenciais em aplicações de data mining, a maioria dos algoritmos de clusterização são métodos ad-hoc. Eles carecem de garantias na qualidade da solução, que em muitos casos está relacionada a uma convergência prematura para um mínimo local no espaço de busca. Neste trabalho, abordamos o problema de clusterização a partir da perspectiva de otimização, onde propomos um algoritmo genético híbrido para resolver o problema Minimum Sum-of-Squares Clustering (MSSC, em inglês). A meta-heurística proposta é capaz de escapar de mínimos locais e gerar soluções quase ótimas para o problema MSSC. Os resultados mostram que o método proposto superou os resultados atuais da literatura – em termos de qualidade da solução – para quase todos os conjuntos de instâncias considerados para o problema MSSC. / [en] Clustering plays an important role in data mining, being useful in many fields that deal with exploratory data analysis, such as information retrieval, document extraction, and image segmentation. Although they are essential in data mining applications, most clustering algorithms are adhoc methods. They have a lack of guarantee on the solution quality, which in many cases is related to a premature convergence to a local minimum of the search space. In this research, we address the problem of data clustering from an optimization perspective, where we propose a hybrid genetic algorithm to solve the Minimum Sum-of-Squares Clustering (MSSC) problem. This meta-heuristic is capable of escaping from local minima and generating near-optimal solutions to the MSSC problem. Results show that the proposed method outperformed the best current literature results - in terms of solution quality - for almost all considered sets of benchmark instances for the MSSC objective.

[pt] Esta dissertação de mestrado analisa um problema de programação de máquinas em série com datas de entrega e ganhos cumulativos sob incerteza. Em particular, este trabalho considera situações reais na quais os tempos de processamento e datas de liberação são estocásticos. O objetivo principal deste trabalho é a resolução deste problema de programação de máquinas em série em um ambiente estocástico buscando analisar a relação entre diferentes niveis de incerteza e o benefício esperado. Visando atingir este objetivo, primeiramente uma heurística é proposta utilizando-se da técnica de biased-randomization para a versão determinística do problema. Então, esta heurística é extendida para uma metaheurística a partir do encapsulamento dentro da estrutura de um variable neighborhood descend. Finalmente, a metaheurística é extendida para uma simheurística a partir da incorporação da simulação de Monte Carlo. De acordo com os experimentos computacionais, o nível de incerteza tem um impacto direto nas soluções geradas pela simheurística. Além disso, análise de risco foram desenvolvidas utilizando as conhecidas métricas de risco: value at risk e conditional value at risk. / [en] This master s thesis analyzes the Permutation Flow-shop Scheduling Problem with Delivery Dates and Cumulative Payoffs under uncertainty conditions. In particular, the work considers the realistic situation in which processing times and release dates are stochastics. The main goal is to solve this Permutation Flow-shop problem in the stochastic environment and analyze the relationship between different levels of uncertainty and the expected payoff. In order to achieve this goal, first a biased-randomized heuristic is proposed for the deterministic version of the problem. Then, this heuristic is extended into a metaheuristic by encapsulating it into a variable neighborhood descent framework. Finally, the metaheuristic is extended into a simheuristic by incorporating Monte Carlo simulation. According to the computational experiments, the level of uncertainty has a direct impact on the solutions provided by the simheuristic. Moreover, a risk analysis is performed using two well-known metrics: the value at risk and the conditional value at risk.