[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.

[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] 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

[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.