Orientador : Prof. Dr. José Carlos Korelo / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Sociais Aplicadas, Programa de Pós-Graduação em Administração. Defesa: Curitiba, 26/02/2016 / Inclui referências : f.131-134 / Área de concentração : Estratégia de marketing / Resumo: Esta dissertação verifica a influência da indisponibilidade do produto, da determinação da preferência prévia e do momento do pagamento na manutenção da implementação. Com base na literatura de metas de consumo, processo decisório e heurísticas de compra (mind-sets de deliberação e implementação), objetiva-se investigar a propensão dos consumidores em progredirem para a compra de itens subsequentes na condição de indisponibilidade do produto primário. Nesse sentido, o efeito da moderação da preferência previamente estipulada é mensurado. Ainda, por meio da moderação da condição de contorno da heurística de compra, o estudo analisa o momento em que o pagamento é realizado na interrupção das aquisições sequenciais. Três experimentos foram realizados, através dos quais as hipóteses propostas nesta pesquisa foram testadas. O primeiro (n =109) foi um fator único com duas condições (primeira compra: disponibilidade vs. indisponibilidade do produto driver) entre grupos. Os resultados mostram que, com a ausência do item primário, os consumidores possuem maior probabilidade de comprar o produto alvo. O segundo estudo (n = 243), analisa o efeito da moderação da preferência prévia do tipo 2 (disponibilidade vs. indisponibilidade do item driver) por 2 (preferência estipulada vs. não estipulada previamente) full factorial design, between subjects design. Os resultados das relações principais não replicaram o Estudo 1 para o grupo estoque nem para a moderação. Porém, é demonstrada a predominância da preferência prévia influenciando a propensão dos consumidores adquirirem o produto target. Em conjunto, os Estudos 1 e 2 comprovam que há maior probabilidade de compra do item target quando considerada a indisponibilidade do produto inicial por meio da busca de uma meta superior de compra. Ainda, o Estudo 2 demonstra o aumento da intenção de compras sequenciais, quando analisada a preferência estipulada em um conjunto de opções. Para o teste da condição de ruptura da implementação, o Estudo 3 (n = 56), do tipo 2 (disponibilidade vs. indisponibilidade do item driver) por 2 (pagamento único final vs. parcelado por compra) factorial design, between subjects, demonstra a tendência da ruptura das compras sequenciais com a moderação do pagamento parcelado, fazendo com que os consumidores retornem ao processo de deliberação com o início de um novo episódio de consumo. Esta pesquisa contribui com a literatura demonstrando maior probabilidade dos consumidores continuarem realizando as aquisições com a indisponibilidade do item inicial, por meio do efeito da preferência prévia estipulada e do momento da efetivação do pagamento com a continuidade das heurísticas de compra. Pesquisas futuras podem replicar os achados explorando o efeito da atratividade na intenção de compra e a interação das variáveis propostas. Destaca-se a possibilidade de validação do pagamento parcelado como forma de ruptura das heurísticas de compra e a consequente ruptura da implementação. Palavras-chave: Mind-set de implementação, preferência prévia estipulada, momento do pagamento, compras sequenciais. / Abstract: This dissertation verifies the influence of the unavailability of the product, the determination of prior preference and the time of payment in the maintenance of implementation. Based on the literature of consumption goals, decision-making process, and heuristics of buying process (deliberation and implementation mind-sets), aims to investigate the propensity of consumers to progress to the purchase of subsequent items in the condition of unavailability of the primary product. In this direction, the effect of moderating the preference previously stipulated is measured. Still, through the moderation of the boundary condition of purchase heuristics, the study analyzes the time of payment is made in the interruption of sequential acquisitions. Three experiments were conducted, by which the cases provided for in this study were tested. The first (n = 109) was a single factor with two conditions (first purchase: availability vs. unavailability of driver product) between groups. The results show that in the absence of the primary items, consumers are more likely to buy the target product. The second study (n = 243), analyzes the effect of moderating the previous preference type 2 (availability vs. unavailability of driver product) by 2 (preferably: stipulated vs. not stipulated) full factorial design, between subjects design. The results of the main relations not replicate Study 1 for the stock or moderation. However, it is demonstrated the predominance of the previous preference influencing the propensity of consumers to purchase the target product. Studies 1 and 2 show that consumers are more likely to purchase the target item when considering the unavailability of the initial product through the pursuit a higher purchase goal. Further, Study 2 demonstrates the increased intention to sequential purchases when analyzed the preference stipulated in a set of options. To test the implementation rupture condition, Study 3 (n = 56), type 2 (availability unavailability vs. driver item) by 2 (Single vs. final payment by installments purchase) factorial design, between subjects, demonstrates the tendency of the rupture the sequential purchases with the moderation of payment in installments, making consumers return to the deliberation process with the onset of a new episode of consumption. This research contributes to the literature demonstrating higher likelihood consumers to continue making purchases with the unavailability of the original item, through the effect of stipulated prior preference, and the time of the payment with the continuation of purchases. Further research may apply the findings to explore the effect of attractiveness on purchase intent and the interaction of variables proposed. We highlight the possibility of validation of payment in installments as a way to rupture the purchase of heuristics and the consequent disruption of implementation. Keywords: Implementation Mind-set, prior stipulated preference, the time of encashment, sequential purchases.

Orientadora : Profª. Drª. Adriana Sbicca Fernandes / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Sociais Aplicadas, Programa de Pós-Graduação em Desenvolvimento Econômico. Defesa: Curitiba, 27/03/2017 / Inclui referências / Resumo: A economia evolucionária é uma abordagem bem estabelecida nas Ciências Econômicas que apresentou várias teorias para explicar os mais diversos fenômenos econômicos. No entanto, o lado da demanda em suas teorias é relativamente pouco desenvolvido. Com o objetivo avançar teoricamente as discussões sobre o lado da demanda na economia evolucionária, esta pesquisa investiga o comportamento do consumo a partir de uma perspectiva econômica evolucionária. Hipóteses típicas da economia evolucionária que podem embasar uma teoria do consumidor evolucionária são identificadas. Com o intuito de superar algumas dificuldades na modelagem de modelos de consumo evolucionário, é introduzida uma abordagem na literatura da psicologia que poderia contribuir para o avanço das teorias da economia evolutiva no consumo: o programa de pesquisa em heurísticas rápidas e frugais (Gigerenzer e Selten, 2001). Nessa abordagem, inspirada pelo conceito racionalidade limitada de Herbert Simon, mecanismos cognitivos chamados "heurísticas" desempenham um papel importante na explicação da tomada de decisão humana. Depois de analisar as investigações da economia evolucionária sobre o comportamento do consumidor e a abordagem de heurísticas rápidas e frugais, desenvolvemos um modelo baseado em agentes que apresenta os principais pressupostos identificados nessas abordagens. Propomos uma estrutura de modelo baseada em Valente (2012) para analisar uma evolução de um mercado de bens semiduráveis com agentes que utilizam diferentes estratégias de decisão (i.e., heurísticas) que podem mudar dependendo da estrutura do ambiente em cada fase do desenvolvimento desse mercado. Tendo desenvolvido o modelo adequado, as implicações da inclusão de três heurísticas (Take-the-best, Tallying e Imitate-the-majority) na estrutura de mercado e dinâmica são investigadas através de uma série de simulações computacionais. Com base nessas simulações, é possível dizer que os diferentes processos de decisão heurística afetam: a dinâmica da evolução do mercado, o desempenho das empresas medido pelas vendas e conseqüentemente a concentração do mercado. Esta dissertação contribui para a compreensão das microfundações do lado da demanda da economia evolucionária. Concluise que as heurísticas simples usadas pelos consumidores para decidir qual produto eles vão comprar pode melhorar a compreensão dos economistas evolucionários em relação aos microfundamentos que determinam a demanda e subjazem fenômenos como inovação, dependência do caminho, aprendizagem do consumidor e formação de rotinas. Palavras-chave: Economia evolucionária. Teoria do consumidor. Racionalidade limitada. Programa de pesquisa em heurísticas rápidas e frugais. Modelos baseados em agentes. Estruturas de mercado. / Abstract: Evolutionary economics is as well established approach in economics that has presented various theories to explain the most diverse economic phenomena. Nevertheless, we argue in this dissertation that the demand side of the theory is underdeveloped. In order to provide insights into demand side theorizing in evolutionary economics, this research investigates the consumption behavior in an evolutionary economics perspective. I identify typical assumptions in evolutionary economics in which a consumer theory may be built. In order to overcome some difficulties in modeling evolutionary consumption models, I introduce an approach in the psychological literature that could contribute to advance the evolutionary economics theories in consumption: the fast-and-frugal heuristics program (Gigerenzer and Selten, 2001). In this approach, which was inspired by Herbert Simon's bounded rationality, the cognitive mechanisms called heuristics play a major role in explaining human decision-making. After reviewing the evolutionary economics investigations into consumer behavior and the fast-and-frugal heuristics approach, I develop an agent based model featuring the main assumptions identified in each of these approaches. I propose a model framework - based on Valente (2012) - to analyze a semi-durable market evolution with agents using different decision strategies (i.e., heuristics) that can change depending on the structure of the environment in each stage of the market development. Having developed an appropriate model, I investigate the implications of the inclusion of three heuristics (Take-the-best, Tallying and Imitate-the-majority) in the market structure and dynamics through a series of computer simulations. Based on these simulations, I confirm that the different heuristics decision process affect the dynamics of the market evolution, the firms' performance measured by sales and consequently the market concentration. This dissertation contributes to the understanding of the microfoundations of the demand side of evolutionary economics. I conclude that simple heuristics strategies used by the consumers to decide which product they will purchase may enhance the comprehension of evolutionary economists of the demand-side drives that underlie phenomena like innovation, path dependency, consumer learning, and routine formation. Key-words: Evolutionary economics. Consumer theory. Bounded rationality. Fast-and-frugal heuristics research program. Agent-based models. Market structure.

Orientador : Prof. Dr. Silvia Regina Vergilio / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 23/02/2017 / Inclui referências : f. 90-98 / Área de concentração: Ciência da Computação / Resumo: Determinar um conjunto de casos de teste que possua alta probabilidade de revelar defeitos em um software é um dos principais objetivos da área de teste de software. Dentre os vários critérios propostos na literatura destaca-se a Análise de Mutantes, uma abordagem promissora devido a sua capacidade em revelar defeitos, embora possua um custo computacional relativamente alto. Com o intuito de reduzir o custo da Análise de Mutantes, estudos empregam a utilização de mutação de ordem superior (Higher Order Mutants, HOMs). O uso de HOMs tem se destacado por reduzir o número de mutantes equivalentes, reduzir o esforço do teste e simular defeitos próximos dos defeitos reais. Entretanto, a geração dos melhores HOMs é uma tarefa complexa, devido ao grande número de mutantes que podem existir e a outros fatores que influenciam a geração, tais como a eficácia dos HOMs gerados. Trabalhos têm aplicado com sucesso técnicas da área da Engenharia de Software baseada em busca por meio da utilização de técnicas de otimização para solucionar esse problema. Entretanto, há ainda a necessidade de possuir um conhecimento sobre o comportamento do problema, de modo a determinar a melhor estratégia a ser utilizada, como projetar e configurar os algoritmos, escolhendo os diferentes operadores de busca e definindo seus parâmetros, para assim melhorar o direcionamento da busca. Neste sentido, o uso de hiper-heurística possibilita uma abordagem mais flexível para automatizar estas tarefas. Além disso, o uso de uma hiper-heurística de seleção de diferentes estratégias existentes para geração de HOMs pode ser útil para reduzir o esforço do testador. Diante disso, este trabalho propõe uma abordagem multi-objetivo que utiliza o conceito de hiper-heurística para gerar conjuntos de HOMs, denominada Hyper-Heuristic for Generation of Higher Order Mutants (HG4HOM). O objetivo é selecionar a menor quantidade de HOMs, os mais difíceis de serem mortos e assim melhorar a eficácia do teste, além de também possibilitar que ao matar um HOM seus FOMs (First Order Mutants) constituintes também possam ser mortos. Para isso, a abordagem é implementada e avaliada com dois algoritmos multi-objetivos: NSGA-II e SPEA2, e três métodos de seleção: Choice-Function (CF), Fitness-Rate-Rank based Multi-Armed Bandit (FRR-MAB) e a seleção aleatória (Random). O algoritmo SPEA2 utilizando o conceito de hiper-heurística juntamente com o método de seleção CF obteve os melhores resultados. Quando comparado com as estratégias tradicionais, a abordagem obteve resultados próximos em relação ao escore de mutação e valor equivalente ao melhor em relação ao tamanho do conjunto de casos de teste adequado. A abordagem obteve as soluções com melhores valores de Euclidean Distance considerando os objetivos relacionados a encontrar a menor quantidade de HOMs, os mais difíceis de serem mortos e capazes de substituírem seus FOMs constituintes. Palavras-chave: Teste de Software, Análise de Mutantes, Mutação de Ordem Superior, Algoritmos Evolutivos Multi-Objetivos, Hiper-Heurística. / Abstract: One of the main testing goals is to determine test sets with a high probability of revealing faults. Mutant Analysis is a promising criterion due to its ability to reveal faults, although with a high computational cost. In order to decrease the mutation testing cost, studies employ the use of Higher Order Mutants (HOMs). The use of HOMs can contribute to decrease the number of equivalent mutants, decrease the test effort and simulate faults close to the real ones. However, the generation of the best HOMs is a complex task, due to the large number of mutants that may exist, and to other factors that influence the generation, such as the efficacy of the generated HOMs. To solve such a problem, some works have successfully applied Search-based Software Engineering techniques through the use of optimization techniques. However, it is still needed to have knowledge about the problem behavior, to determine the best strategy to be applied, and to know how to design and configure the algorithms by choosing the different search operators and defining their parameters in order to improve the search. In this sense, the use of hyper-heuristics allows a more flexible approach to automating these tasks. Also, the use of a hyper-heuristic for selection of different existing strategies to generate HOMs can be useful to reduce the tester's effort. Considering all these facts, this work proposes a multi-objective approach, called Hyper-Heuristic for Generation of Higher Order Mutants (HG4HOM), which uses the hyper-heuristic concept to generate sets of HOMs. The goal is to select a small number of HOMs which are difficult to kill, and that contribute to improve the test efficacy, that is, it is desired the test cases that kill the selects HOMs are also capable of killing their corresponding FOMs (First Order Mutants). The approach is implemented and evaluated with two multi-objective algorithms: NSGA-II and SPEA2, and three selection methods: Choice-Function (CF), Fitness-Rate-Rank based Multi-Armed Bandit (FRR-MAB ), and random selection (Random). The SPEA2 algorithm using the hyper-heuristic concept together with the CF selection method obtained the best results. In comparison with respect to the traditional strategies, the approach achieved similar results related to the mutation score and statically equivalent values to the best strategy considering the size of the adequate test case sets. The approach obtained the best results when considering the Euclidean Distance values of the solutions with respect to the goals proposed. Keywords: Software Testing, Mutation Analysis, Higher Order Mutation, Multi-objective Evolutionary Algorithms, Hyper-heuristic.

Orientadora : Profa. Dra. Aurora Trinidad Ramirez Pozo / Coorientador : Prof. Dr. Roberto Santana / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 13/03/2017 / Inclui referências : f. 54-60 / Resumo: Proteínas são estruturas, compostas por aminoácidos, que exercem um papel importante na natureza. Estas estruturas são formadas a partir de um processo de dobramento, no qual uma sequência de aminoácidos inicialmente desdobrada irá adotar uma conformação/estrutura espacial única/nativa. Entretanto, o processo de dobramento ainda não é completamente compreendido e é considerado um dos maiores desafios das áreas de biologia, química, medicina e bioinformática. Este desafio é conhecido como o problema de dobramento de proteínas (PDP) e trata da predição de estruturas de proteínas. O PDP pode ser visto como um problema de minimização, pois é afirmado que a estrutura nativa de uma proteína é aquela que minimiza sua energia global livre. Dessa maneira, diversas estudos aplicam estratégias heurísticas para explorar modelos simplificados, tais como o modelo Hidrofóbico-Polar HP. Embora simplificado, HP possui um complexo espaço de busca e uma grande variabilidade de características entre as instâncias. Por conta de tal complexidade surge a demanda de estratégias que possuam mecanismos robustos para explorar de maneira adequada o espaço de busca. É nesse contexto que hiper-heurísticas se apresentam como boas opções para explorar o espaço de busca de problemas complexos. Nesta dissertação, são apresentadas duas abordagens para resolver o PDP. A primeira descreve uma abordagem biobjetiva explorando algoritmos evolucionários multi objetivos tradicionais. A segunda consiste no projeto automático de heurísticas de alto nível utilizando uma técnica de programação genética chamada evolução gramatical, a qual utiliza uma gramática para produzir programas de computador. As estratégias propostas foram aplicadas sobre um conjunto de benchmark com diferentes sequências de aminoácidos. Os resultados foram comparados com outros trabalhos que utilizam o mesmo conjunto de benchmark. Alguns resultados obtidos se mostraram promissores dessa maneira motivando novos estudos que desenvolvam estratégias adaptativas para o PDP. Palavras-chave: PDP, hiper heurísticas, evolução gramatical, otimização multi objetiva. / Abstract: Proteins are structures composed by amino acids that plays a important role in nature. These structures are built by a process called protein folding, where a sequence of amino-acids initially unfolded will obtain your native structure. However, the protein folding process is not entire understood and it is considered one of the most challenging problem from biology, chemistry, medicine and bio-informatics. This problem is knows as the protein folding problem (PFP) and handles the prediction of protein structures. The PFP is a minimization problem, because the proteins native structures are the one within minimum energy. Thus, many heuristics strategies make use of simplified models, such as the HP model, to find the proteins native structures within the HP model. Although simplified, the HP model has a complex search space and a great variability of characteristics between the instances. Thus, raises the demand of strategies with robust mechanisms to explore the search space properly. In this context, adaptive strategies fits well as good alternative to explore the fitness landscape from complex problems. In this dissertation, two approaches are presented to solve the PDP. The first one describes a bi objective approach applying traditional multi objective evolutionary algorithms. The second approach consists the automated design of high level heuristics using a genetic programming technique called grammatical evolution, which uses a grammar to produce computer programs. Both approaches proposed have been applied on a benchmark set with different amino acids sequences. The results have been compared with previous studies that used the same benchmark. In some cases the results obtained are promising which motivates the development of new adaptive strategies to solve the PFP. Keywords: PFP, hyper heuristics, grammatical evolution , multi objective optimization.

Orientador : Aurora Trinidad Ramirez Pozo / Coorientador : Roberto Santana Hermida / Tese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 06/03/2017 / Inclui referências : f. 161-72 / Área de concentração : Computer Science / Resumo: Problemas multi-objetivo (MOPs) são caracterizados por terem duas ou mais funções objetivo a serem otimizadas simultaneamente. Nestes problemas, a meta é encontrar um conjunto de soluções não-dominadas geralmente chamado conjunto ótimo de Pareto cuja imagem no espaço de objetivos é chamada frente de Pareto. MOPs que apresentam mais de três funções objetivo a serem otimizadas são conhecidos como problemas com muitos objetivos (MaOPs) e vários estudos indicam que a capacidade de busca de algoritmos baseados em Pareto é severamente deteriorada nesses problemas. O desenvolvimento de otimizadores bio-inspirados para enfrentar MOPs e MaOPs é uma área que vem ganhando atenção na comunidade, no entanto, existem muitas oportunidades para inovar. O algoritmo de enxames de partículas multi-objetivo (MOPSO) é um dos algoritmos bio-inspirados adequados para ser modificado e melhorado, principalmente devido à sua simplicidade, flexibilidade e bons resultados. Para melhorar a capacidade de busca de MOPSOs, seguimos duas linhas de pesquisa diferentes: A primeira foca em métodos de líder e arquivamento. Trabalhos anteriores apontaram que esses componentes podem influenciar no desempenho do algoritmo, porém a seleção desses componentes pode ser dependente do problema. Uma alternativa para selecioná-los dinamicamente é empregando hiper-heurísticas. Ao combinar hiper-heurísticas e MOPSO, desenvolvemos um novo framework chamado H-MOPSO. A segunda linha de pesquisa também é baseada em trabalhos anteriores do grupo que focam em múltiplos enxames. Isso é feito selecionando como base o framework multi-enxame iterado (I-Multi), cujo procedimento de busca pode ser dividido em busca de diversidade e busca com múltiplos enxames, e a última usa agrupamento para dividir um enxame em vários sub-enxames. Para melhorar o desempenho do I-Multi, exploramos duas possibilidades: a primeira foi investigar o efeito de diferentes características do mecanismo de agrupamento do I-Multi. A segunda foi investigar alternativas para melhorar a convergência de cada sub-enxame, como hibridizá-lo com um algoritmo de estimativa de distribuição (EDA). Este trabalho com EDA aumentou nosso interesse nesta abordagem, portanto seguimos outra linha de pesquisa, investigando alternativas para criar versões multi-objetivo de um dos EDAs mais poderosos da literatura, chamado estratégia de evolução baseada na adaptação da matriz de covariância (CMA-ES). Para validar o nosso trabalho, vários estudos empíricos foram conduzidos para investigar a capacidade de busca das abordagens propostas. Em todos os estudos, nossos algoritmos investigados alcançaram resultados competitivos ou melhores do que algoritmos bem estabelecidos da literatura. Palavras-chave: multi-objetivo, algoritmo de estimativa de distribuição, otimização por enxame de partículas, multiplos enxames, híper-heuristicas. / Abstract: Multi-Objective Problems (MOPs) are characterized by having two or more objective functions to be simultaneously optimized. In these problems, the goal is to find a set of non-dominated solutions usually called Pareto optimal set whose image in the objective space is called Pareto front. MOPs presenting more than three objective functions to be optimized are known as Many-Objective Problems (MaOPs) and several studies indicate that the search ability of Pareto-based algorithms is severely deteriorated in such problems. The development of bio-inspired optimizers to tackle MOPs and MaOPs is a field that has been gaining attention in the community, however there are many opportunities to innovate. Multi-objective Particle Swarm Optimization (MOPSO) is one of the bio-inspired algorithms suitable to be modified and improved, mostly due to its simplicity, flexibility and good results. To enhance the search ability of MOPSOs, we followed two different research lines: The first focus on leader and archiving methods. Previous works have pointed that these components can influence the algorithm performance, however the selection of these components can be problem-dependent. An alternative to dynamically select them is by employing hyper-heuristics. By combining hyper-heuristics and MOPSO, we developed a new framework called H-MOPSO. The second research line, is also based on previous works of the group that focus on multi-swarm. This is done by selecting as base framework the iterated multi swarm (I-Multi) algorithm, whose search procedure can be divided into diversity and multi-swarm searches, and the latter employs clustering to split a swarm into several sub-swarms. In order to improve the performance of I-Multi, we explored two possibilities: the first was to further investigate the effect of different characteristics of the clustering mechanism of I-Multi. The second was to investigate alternatives to improve the convergence of each sub-swarm, like hybridizing it to an Estimation of Distribution Algorithm (EDA). This work on EDA increased our interest in this approach, hence we followed another research line by investigating alternatives to create multi-objective versions of one of the most powerful EDAs from the literature, the Covariance Matrix Adaptation Evolution Strategy (CMA-ES). In order to validate our work, several empirical studies were conducted to investigate the search ability of the approaches proposed. In all studies, our investigated algorithms have reached competitive or better results than well established algorithms from the literature. Keywords: multi-objective, estimation of distribution algorithms, particle swarm optimization, multi-swarm, hyper-heuristics.

Orientadora : Profª. Drª. Andréa Weber / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 27/08/2015 / Inclui referências : f. 75-81 / Resumo: Diagnóstico em nível de sistema e uma sub-área de tolerância a falhas. O objetivo de um algoritmo de diagnostico em nível de sistema e reportar, para todas as unidades sem-falha de um sistema distribuído, o estado das demais unidades do sistema. A di- agnosticabilidade do sistema depende de algumas propriedades topologicas do grafo de diagnostico. Nesse contexto, um assinalamento de testes e um conjunto de testes mótuos entre as n unidades de um sistema. Um sistema com n unidades e dito t-diagnosticavel se o numero de unidades falhas nao ultrapassar t e satisfizer as seguintes condicões: (i) n > 2t + 1; e (ii) cada unidade for testada por, no mínimo, t outras unidades. Um sistema t-diagnosticóvel e definido como ótimo se n = 2t + 1. Considera-se o problema da definicao de um assinalamento de testes para a identificaçao de nós com falha em uma Rede de Sensores Sem Fio - RSSF. Dado um conjunto de 2t +1 sensores, a abordagem Optimal Design Testing Assignment - ODTA [36] gera um assinalamento de testes ótimo do ponto de vista da diagnosticabilidade do sistema. Entretanto, o problema da escolha em termos da distancia dos 2t +1 sensores que farao parte do assinalamento de testes tem características de um problema computacionalmente intratavel. Devido a ausencia de tal prova, apresenta-se o aprimoramento da heurística do ODTA para a escolha deste conjunto de sensores. Por meio da heurística Set of Sensors Chosen by Centroid and Radius - SSCCR apresentada, e possível selecionar em tempo polinomial tal conjunto nao somente otimo em termos de número de sensores, mas com uma considerável melhora dos resultados em termos de distancia geográfica entre os sensores. Por fim, apresenta-se a comparacõo das duas heurísticas abordadas com a solucõo ítima obtida pela formulacao do problema em programacao linear inteira, na qual pode-se confirmar que a heurística SSCCR apresenta melhor desempenho em relacao a heurística ODTA na escolha do conjunto de sensores com relacao a distancia entre eles e ate mesmo, em algumas situacoes, pode proporcionar o alcance de valores íotimos e consequentemente obter a reduçcõao do consumo de energia na execucao do diagnostico de falhas. / Abstract: System-level diagnosis is a subset of fault tolerance. The goal of a system-level diagnosis algorithm is to report the state of the units of a distributed system to all fault-free units of the system. The diagnosability of the system depends on some topological properties of the diagnostic graph. In this context, a test assignment is a set of mutual tests between n units of a system. A system with n units is called t-diagnosable if the number of faulty units does not exceed t and it satisfies the following conditions: (i) n > 2t +1; and (ii) each unit is tested at least by t other units. A t-diagnosable system is said to be optimal if n = 2t +1. Consider the problem of defining a test assignment to identify faults in a wireless sensor network (WSN). Given a set of 2t +1 sensors, the approach Optimal Design Testing Assignment - ODTA [36] generates an optimal test assignment for the diagnosability of the system. However, the problem of the choice of 2t + 1 sensors that will take part of the testing assignment has characteristics of a computationally intractable problem. Due to the absence of such proof, the improvement of ODTA heuristics is presented. According to the heuristic Set of Sensors Chosen by Centroid and Radius - SSCCR it is possible to select that set in polynomial time, optimal not only in terms of number of sensors, but with a considerable improvement of results in terms of geographical distance between the sensors. Finally, a comparison of the two heuristics with the optimal solution obtained by the problem formulated in integer linear programming is presented, which confirms that the heuristic SSCCR has better performance compared with ODTA heuristic, and in many cases achieves optimal values, and consequently achieve the reduction of energy consumption in the implementation of fault diagnosis.

Orientadora: Profª. Drª. Deise M. Bertholdi Costa / Co-orientador: Prof. Dr. Luiz Fernando Nunes / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Tecnologia, Programa de Pós-Graduaçao em Métodos Numéricos em Engenharia. Defesa: Curitiba, 25/11/2011 / Inclui bibliografias / Resumo: O transporte, em geral, representa nos dias atuais, o maior percentual de custos do na atividade logística. Por isso, muitas empresas estão repensando seus processos para redução dos mesmos. A otimização da distribuição de produtos é um problema estudado há muito tempo por pesquisadores da área de matemática, pesquisa operacional e da computação. Este tipo de problema é dado como um típico problema de otimização combinatória. O Problema do Caixeiro Viajante (PCV) é um clássico deste tipo de problema. Assim, como o Problema de Roteamento de Veículos (PRV), o qual busca o menor caminho dentre N lugares de destino. Na literatura podem ser encontrados trabalhos e abordagens propostos, que utilizam formulações exatas, algoritmos heurísticos e metaheurísticos. O objetivo deste trabalho foi realizar um estudo de caso que envolvesse um número significativo de pontos visitados por algum tipo de veículo, visando analisar e comparar, em termos de desempenho computacional e qualidade das soluções obtidas, as Heurísticas de Construção e Melhoria de Rota e das Metaheurísticas Ant System, Simulated Annealing e Algoritmos Genéticos para o PCV. Também foi aplicado o algoritmo 2- opt para melhoria das rotas geradas. As técnicas foram aplicadas tendo em vista que a otimização das visitas e distribuição dos produtos pode reduzir custos e principalmente os atrasos nas entregas. Para implementação foram utilizados dados reais de uma distribuidora de produtos para uma determinada região da cidade de Curitiba (PR), Brasil. Através do aplicativo online, Google Earth foram obtidas as coordenadas geográficas dos pontos de visitação, que foram então convertidas para coordenadas cartesianas, para a utilização nos algoritmos. Os resultados obtidos foram comparados com as rotas reais praticadas na época por um dos representantes da referida distribuidora. / Abstract: Transport, in general, on average absorbs the highest percentage of costs than any other logistics activity, so many companies are rethinking their processes to reduce them. The optimization of the distribution of products is a problem that is studied for a long time by researchers in mathematics, operational research and computing. This type of problem is given as a typical combinatorial optimization problem. The Traveling Salesman Problem (TSP) is a classic of this, as well as the Vehicle Routing Problem (VRP), where it briefly conceptualizes in finding the shortest path from N places of destination. In the literature there are many jobs and proposed approaches, and some of these heuristics and metaheuristics will be studied and analyzed. The objective of this work was to perform a case study involving a significant number of points visited by some kind of vehicle in order to analyze and compare in terms of computational performance and quality of the solutions obtained, the Construction and Improvement Heuristics and Route Ant System metaheuristics, Simulated Annealing and Genetic Algorithms for the TSP, and has also applied the 2-opt algorithm for improving the routes generated, with a view that the optimization of the visits and distribuition product will reduce costs and above all, the delivery delays. We used real data from a distributor of products in a specific region of Curitiba (PR), Brazil. Using Google Earth has picked the geographical coordinates of points of visitation, which were converted to Cartesian coordinates, for application of the algorithms used. The results were compared with the true routes that are being used by a particular representative of that distributor.

Orientadora : Profª. Ph.D. Aurora Pozo / Dissertação (mestrado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 29/02/2016 / Inclui referências : f. 81-87 / Resumo: O algoritmo de Otimização por Enxame de Partículas (PSO) e uma meta-heurística inspirada no comportamento de bandos de aves a procura de alimento. Os bons resultados obtidos por esta técnica na otimização de problemas mono-objetivo incentivaram o estudo de variações para problemas multi- objetivo (MOPSO), que também alcançaram bons resultados. Para a adaptação do PSO para problemas multi-objetivo algumas modificações foram necessárias, tais como o uso de um operador para seleção de líder e a aplicação de um operador de arquivamento. Entretanto, a qualidade do algoritmo diminui conforme o aumento do numero de objetivos. Encontrar, dentre os diferentes operadores de selecao de líder e de arquivamento, propostos na literatura, os mais apropriado para determinada instância de um problema permite amenizar esta perda de qualidade. Porem esta tarefa não é uma tarefa trivial. Em trabalhos anteriores o uso de hiper-heurística para a seleção de uma combinação apropriada destes operadores e proposta. Hiper-heurísticas são técnicas para a seleção, ou geração, de heurísticas para problemas de busca. Estas técnicas visam a seleção, ou geração, de uma heurística apropriada para determinada instancia de um problema ou estágio da busca. Neste trabalho foi abordada a hipótese de que, o uso de métodos de seleção mais avançados poderiam melhorar desempenho do MOPSO baseado em Hiper-heurística (H-MOPSO). Para investigar esta hipótese quatro métodos de seleção foram avaliados e comparados a um algoritmo multi-objetivo estado da arte. Nos resultados apresentados o H-MOPSO obteve melhores resultados na maioria dos problemas. / Abstract: Multi-objective Particle Swarm Optimization (MOPSO) is a promising meta-heuristic to solve Many-Objective Problems (MaOPs), however, its performance decreases as the number of objective functions increases. Selecting a good combination of leader and archiving methods helps the algorithm to deal with the challenges caused by this increase in the number of objectives, but finding the most appropriate combination for a given problem is a hard task. To deal with this issue, previous works proposed the use of a simple hyper-heuristic to select dynamically a good combination of leader and archiving methods and achieved promising results. In this work, we hypothesize that by using more advanced heuristic selection methods we could further improve the performance of the algorithm. To investigate this hypothesis we conducted experimental studies comparing four heuristic selection methods. After selecting the best performing variant from this study, we conducted a second empirical study to compare this variant to a state-of-the- art optimizer, where the resulting algorithm outperformed it in most of the problems investigated.

Made available in DSpace on 2016-09-27T13:40:08Z (GMT). No. of bitstreams: 0 Previous issue date: 2015-02-26. Added 1 bitstream(s) on 2016-09-27T13:45:21Z : No. of bitstreams: 1 000868828.pdf: 1398254 bytes, checksum: b44031133d83ed0f7078fb32d0787427 (MD5) / Neste trabalho, propõe-se um algoritmo baseado na meta-heurística busca tabu para o problema de restauração de redes de distribuição de energia elétrica radiais com geração distribuída, considerando como sistema de codificação uma estrutura denominada representação nó-profundidade (RNP). O problema é modelado como não linear inteiro misto e considera os principais objetivos da restauração de redes de distribuição: minimizar número de consumidores sem fornecimento de energia elétrica e o número de chaveamentos. Propõe-se, também, uma sequência lógica de chaveamentos que garante os aspectos operacionais. O algoritmo desenvolvido foi implementado em linguagem de programação C++ e testado em sistemas de distribuição de 136 e 7052 barras / This work proposes a methodology based in the meta-heuristic tabu search to distribution power system restoration considering distributed generators installed on the system, using the encoding system node depth representation. The problem is established as a mixed-integer nonlinear programming taking into account the mainly goals: to minimize both the number of consumers without supply and the number of switching. This work also proposes a logic sequence of switching operations, taking care of operational issues. The proposed algorithm was implemented in C++ programming language and tested in a 136 and a 7052 bus distribution systems

[pt] O Team Orienteering Problem é um problema de roteamento de veículos sobre um grafo com durações associadas aos arcos e prêmios atribuídos à visitação de cada vértice. Neste problema, considera-se que as visitas são realizadas por uma frota com um número fixo de veículos idênticos e que existe uma duração total máxima para as rotas serem finalizadas. Cada vértice pode ser visitado no máximo uma vez, não havendo obrigatoriedade de se visitar todos os vértices, devido à restrição que limita o tempo m´aximo de duração das rotas. O objetivo do problema é maximizar o prêmio total ganho por todas as rotas. Neste trabalho, foram propostas duas abordagens: uma exata e uma heurística. Na abordagem exata, foi desenvolvida uma formulação baseada em arcos e uma formulação estendida na qual cada arco tem um índice extra. Esse índice representa o tempo de partida de um veículo ao percorrer o arco. Através de transformações sobre a formulação estendida, foi obtida uma formulação, cuja relaxação, problema mestre restrito, foi resolvida pela técnica de geração de colunas. O subproblema de geração de colunas foi resolvido por programação dinâmica em tempo pseudo-polinomial. Este algoritmo gera rotas não elementares, que são rotas nas quais subciclos são permitidos. Com o objetivo de eliminar os subciclos das rotas não elementares, uma nova classe de desigualdades denominada min cut foi proposta. Aplicando-se um algoritmo Branch-Cut-and-Price (BCP) foram obtidos alguns novos limites superiores. A abordagem exata obteve resultados competitivos quando comparada ao melhor algoritmo exato já proposto para esse problema. Na abordagem heurística, além de uma vizinhança k-opt, foi explorada também uma busca elipsoidal que adiciona um corte à formulação do algoritmo Branch-Cut-and-Price. Esse novo corte reduz o espa¸co de busca a uma vizinhança em torno de um conjunto de soluções conhecidas. Essa busca é utilizada como um operador de crossover executado em todas as iterações de um algoritmo evolutivo. Essa abordagem converge em um tempo computacional razoável e encontra soluções ótimas ou próximas da ótima para algumas instâncias da literatura. / [en] Team Orienteering Problem is a vehicle routing problem on a graph with durations associated to the arcs and profits assigned to visiting the vertices. In this problem, a fleet with a fixed number of identical vehicles performs the visitations and there is a limited total duration for the routes to be ended up. Each vertex can be visited at most once and the solution does not have the obligation to visit all vertices, due to the constraint that limits the maximum duration of routes. The goal of the problem is to maximize the total profit gathered by all routes. In this work, two approaches have been proposed: an exact and a heuristic one. In the exact approach, we have developed an arc based formulation and an extended formulation where each arc has an extra index. This index represents the departure time of a vehicle using an arc. Through transformations on the extended formulation, we have obtained a formulation, whose relaxation - the restricted master problem - is solved using the column generation technique. A dynamic programming algorithm solves the column generation subproblem in pseudo-polynomial time. This algorithm generates non-elementary routes that allow subcycles. In order to cut off the subcycles, a new class of inequalities called min cut has been proposed.We have applied a Branch-Cut-and-Price (BCP) algorithm. This allowed finding some new upper bounds. The exact approach has achieved competitive results compared to the best exact algorithm has already proposed to this problem. In the heuristic approach, besides a kopt neighborhood, we have also exploited an ellipsoidal search that adds a new cut constraint to the formulation of Branch-Cut-and-Price algorithm. This new cut reduces the space search to a neighborhood around a known set of solutions. This search is used as a crossover operator that runs all iterations of a evolutive algorithm. This approach converges in a reasonable computational time and finds optimal or near optimal solutions for some instances in the literature.