Esse trabalho de investigação visa a realização de uma análise sistemática, integrada e iterativa da utilização de algoritmos heurísticos aplicados aos problemas de estimativa de parâmetros e detecção multiusuário, sob o ponto de vista do compromisso desempenho × complexidade. O sistema considera topologias do tipo CDMA com exploração de diversidade multidimensional, ou seja, que utilizam uma ou mais técnicas de diversidade, considerando a diversidade de código, tempo, frequência e espaço, entre outras, sujeitos a desvanecimentos multipercurso. A solução integrada para os problemas de estimativa de parâmetros e detecção multiusuário consiste no uso recorrente de técnicas heurísticas. Além disso, estabelece-se uma análise comparada e sistêmica de convergência e de complexidade computacional da técnica de detecção proposta com alguns outros métodos, heurísticos ou determinísticos, relatados na literatura, considerando como métrica de desempenho o número de operações computacionais que cada estratégia requer para a detecção simultânea da informação de todos os usuários ativos no sistema. Por fim, e mais importante, considera-se como a principal contribuição deste trabalho a sistematização da utilização dos algoritmos heurísticos no processo de otimização dos problemas já citados, caracterização de limiares de desempenho e análise de complexidade destas técnicas, trazendo à comunidade científica parâmetros suficientes que devem ser respeitados na configuração dos algoritmos para garantia de resultados satisfatórios quando da utilização destes métodos em problemas de detecção multiusuário com diversidade multidimensional e estimativa de parâmetros. / This work will perform a systematic, integrated and iterative research of heuristic algorithms applied to parameter estimation and multiuser detection problems, considering the performance × complexity tradeoff. The CDMA systems with multidimensional diversity exploitation, i.e., with one or more diversity techniques, code diversity, frequency, time and space, among other, in multipath fading channel scenarios are considered. The integrated solution for parameter estimation and multiuser detection problem uses heuristic techniques in recurrent form. In addition, we intend to establish a systemic and comparative analysis of convergence and computational complexity of the proposal detection technique with some other methods, heuristic or deterministic, reported in the literature, considering the number of computational operations that each strategy requires for simultaneous detection from all active users as a performance metrics. Finally, and most importantly, this work systematizes the heuristic algorithms approach in the optimization problems process already mentioned, considering the thresholds for performance and complexity of these techniques, bringing the scientific community enough configuration parameters that must be respected in the setup algorithms step to guarantee satisfactory results when using these methods to multiuser detection with multidimensional diversity and parameter estimation problems.

Esse trabalho de investigação visa a realização de uma análise sistemática, integrada e iterativa da utilização de algoritmos heurísticos aplicados aos problemas de estimativa de parâmetros e detecção multiusuário, sob o ponto de vista do compromisso desempenho × complexidade. O sistema considera topologias do tipo CDMA com exploração de diversidade multidimensional, ou seja, que utilizam uma ou mais técnicas de diversidade, considerando a diversidade de código, tempo, frequência e espaço, entre outras, sujeitos a desvanecimentos multipercurso. A solução integrada para os problemas de estimativa de parâmetros e detecção multiusuário consiste no uso recorrente de técnicas heurísticas. Além disso, estabelece-se uma análise comparada e sistêmica de convergência e de complexidade computacional da técnica de detecção proposta com alguns outros métodos, heurísticos ou determinísticos, relatados na literatura, considerando como métrica de desempenho o número de operações computacionais que cada estratégia requer para a detecção simultânea da informação de todos os usuários ativos no sistema. Por fim, e mais importante, considera-se como a principal contribuição deste trabalho a sistematização da utilização dos algoritmos heurísticos no processo de otimização dos problemas já citados, caracterização de limiares de desempenho e análise de complexidade destas técnicas, trazendo à comunidade científica parâmetros suficientes que devem ser respeitados na configuração dos algoritmos para garantia de resultados satisfatórios quando da utilização destes métodos em problemas de detecção multiusuário com diversidade multidimensional e estimativa de parâmetros. / This work will perform a systematic, integrated and iterative research of heuristic algorithms applied to parameter estimation and multiuser detection problems, considering the performance × complexity tradeoff. The CDMA systems with multidimensional diversity exploitation, i.e., with one or more diversity techniques, code diversity, frequency, time and space, among other, in multipath fading channel scenarios are considered. The integrated solution for parameter estimation and multiuser detection problem uses heuristic techniques in recurrent form. In addition, we intend to establish a systemic and comparative analysis of convergence and computational complexity of the proposal detection technique with some other methods, heuristic or deterministic, reported in the literature, considering the number of computational operations that each strategy requires for simultaneous detection from all active users as a performance metrics. Finally, and most importantly, this work systematizes the heuristic algorithms approach in the optimization problems process already mentioned, considering the thresholds for performance and complexity of these techniques, bringing the scientific community enough configuration parameters that must be respected in the setup algorithms step to guarantee satisfactory results when using these methods to multiuser detection with multidimensional diversity and parameter estimation problems.

Na presente tese é resolvida a equação de difusão de nêutrons estacionária, bem como problemas de cinética, em geometria unidimensional cartesiana multi-região considerando o modelo de multigrupos de energia. Um dos objetivos e inovação neste trabalho é a obtenção de uma solução aproximada com estimativa de erro, controle de precisão e na forma de uma expressão analítica. Com esse tipo de solução não há a necessidade de recorrer a esquemas de interpolação, geralmente necessários em caso de discretizações do domínio. O fluxo de nêutrons é expandido em uma série de Taylor cujos coeficientes são encontrados utilizando a equação diferencial e as condições de contorno e interface. O domínio é dividido em várias células, cujo tamanho e o grau do polinômio são ajustáveis de acordo com a precisão requerida. Para resolver o problema de autovalor é utilizado o método da potência. A metodologia é aplicada em um benchmark que consiste na solução da equação de difusão como condição inicial e na solução de problemas de cinética para diferentes transientes. Os resultados são comparados com sucesso com resultados da literatura. A convergência da série é garantida pela aplicação de um raciocínio baseado no critério de Lipschitz para funções contínuas. Cabe ressaltar que a solução obtida, em conjunto com a análise da convergência, mostra a solidez e a precisão dessa metodologia. / In the present dissertation the one-dimensional neutron diffusion equation for stationary and kinetic problems in a multi-layer slab has been solved considering the multi-group energy model. One of the objectives and innovation in this work is to obtain an approximate solution with error estimation, accuracy control and in the form of an analytical expression. With this solution there is no need for interpolation schemes, which are usually needed in case of discretization of the domain. The neutron flux is expanded in a Taylor series whose coefficients are found using the differential equation and the boundary and interface conditions. The domain is divided into several layers, whose size and the polynomial order can be adjusted according to the required accuracy. To solve the eigenvalue problem the conventional power method has been used. The methodology is applied in a benchmark problem consisting of the solution of the diffusion equation as an initial condition and solving kinetic problems for different transients. The results are compared successfully with the ones in the literature. The convergence of the series is guaranteed by applying a criterion based on the Lipschitz criterion for continuous functions. Note that the solution obtained, together with the convergence analysis, shows the robustness and accuracy of this methodology.

Decision-related activities, such as bottom-up and top-down policy development, analysis, and planning, stand to benefit from the development and application of computer-based models that are capable of representing spatiotemporal social human behavior in local contexts. This is especially the case with our efforts to understand and search for ways to mitigate the context-specific effects of climate change, in which case such models need to include interacting social and ecological components. The development and application of such models has been significantly hindered by the challenges in designing artificial agents whose behavior is grounded in both empirical evidence and theory and in testing the ability of artificial agents to represent the behavior of real-world decision-makers. This dissertation advances our ability to develop such models by overcoming these challenges through the creation of: (a) three new frameworks, (b) two new methods, and (c) two new open-source modeling tools. The three new frameworks include: (a) the SOSIEL framework, which provides a theoretically-grounded blueprint for the development of a new generation of cognitive, multi-agent, and knowledge-based models that consist of agents empowered with cognitive architectures; (b) a new framework for analyzing the bounded rationality of decision-makers, which offers insight into and facilitates the analysis of the relationship between a decision situation and a decision-maker's decision; and (c) a new framework for analyzing the doubly-bounded rationality (DBR) of artificial agents, which does the same for the relationship between a decision situation and an artificial agent's decision. The two new methods include: (a) the SOSIEL method for acquiring and operationalizing decision-making knowledge, which advances our ability to acquire, process, and represent decision-making knowledge for cognitive, multi-agent, and knowledge-based models; and (b) the DBR method for testing the ability of artificial agents to represent human decision-making. The two open-source modeling tools include: (a) the SOSIEL platform, which is a cognitive, multi-agent, and knowledge-based platform for simulating human decision-making; and (b) an application of the platform as the SOSIEL Human Extension (SHE) to an existing forest-climate change model, called LANDIS-II, allowing for the analysis of co-evolutionary human-forest-climate interactions. To provide a context for examples and also guidelines for knowledge acquisition, the dissertation includes a case study of social-ecological interactions in an area of the Ukrainian Carpathians where LANDIS-II with SHE are currently being applied. As a result, this dissertation advances science by: (a) providing a theoretical foundation for and demonstrating the implementation of a next generation of models that are cognitive, multi-agent, and knowledge-based; and (b) providing a new perspective for understanding, analyzing, and testing the ability of artificial agents to represent human decision-making that is rooted in psychology.

Thesis (Ph.D.)--Mississippi State University. Department of Industrial and Systems Engineering. / Title from title screen. Includes bibliographical references.

Random graph processes are most often used to investigate theoretical questions about random graphs. A randomised algorithm can be defined specifically for the purpose of finding some structure in a graph, such as a matching, a colouring or a particular kind of sub graph. Properties of the related random graph process then suggest properties, or bounds on properties, of the structure. In this thesis, we use a random graph process to analyse a particular load balancing algorithm from theoretical computer science. By doing so, we demonstrate that random graph processes may also be used to analyse other algorithms and systems of a random nature, from areas such as computer science, telecommunications and other areas of engineering and mathematics. Moreover, this approach can lead to theoretical results on the performance of algorithms that are difficult to obtain by other methods. In the course of our analysis we are also led to some results of the first kind, relating to the structure of the random graph. / The particular algorithm that we analyse is a randomised algorithm for an off-line load balancing problem with two choices. The load balancing algorithm, in an initial stage, mirrors an algorithm which finds the k-core of a graph. This latter algorithm and the related random graph process have been previously analysed by Pittel, Spencer and Wormald, using a differential equation method, to determine the thresholds for the existence of a k-core in a random graph. We modify their approach by using a random pseudograph model due to Bollobas and Frieze, and Chvatal, in place of the uniform random graph. This makes the analysis somewhat simpler, and leads to a shortened derivation of the thresholds and other properties of k-cores.(For complete abstract open document)

Na presente tese é resolvida a equação de difusão de nêutrons estacionária, bem como problemas de cinética, em geometria unidimensional cartesiana multi-região considerando o modelo de multigrupos de energia. Um dos objetivos e inovação neste trabalho é a obtenção de uma solução aproximada com estimativa de erro, controle de precisão e na forma de uma expressão analítica. Com esse tipo de solução não há a necessidade de recorrer a esquemas de interpolação, geralmente necessários em caso de discretizações do domínio. O fluxo de nêutrons é expandido em uma série de Taylor cujos coeficientes são encontrados utilizando a equação diferencial e as condições de contorno e interface. O domínio é dividido em várias células, cujo tamanho e o grau do polinômio são ajustáveis de acordo com a precisão requerida. Para resolver o problema de autovalor é utilizado o método da potência. A metodologia é aplicada em um benchmark que consiste na solução da equação de difusão como condição inicial e na solução de problemas de cinética para diferentes transientes. Os resultados são comparados com sucesso com resultados da literatura. A convergência da série é garantida pela aplicação de um raciocínio baseado no critério de Lipschitz para funções contínuas. Cabe ressaltar que a solução obtida, em conjunto com a análise da convergência, mostra a solidez e a precisão dessa metodologia. / In the present dissertation the one-dimensional neutron diffusion equation for stationary and kinetic problems in a multi-layer slab has been solved considering the multi-group energy model. One of the objectives and innovation in this work is to obtain an approximate solution with error estimation, accuracy control and in the form of an analytical expression. With this solution there is no need for interpolation schemes, which are usually needed in case of discretization of the domain. The neutron flux is expanded in a Taylor series whose coefficients are found using the differential equation and the boundary and interface conditions. The domain is divided into several layers, whose size and the polynomial order can be adjusted according to the required accuracy. To solve the eigenvalue problem the conventional power method has been used. The methodology is applied in a benchmark problem consisting of the solution of the diffusion equation as an initial condition and solving kinetic problems for different transients. The results are compared successfully with the ones in the literature. The convergence of the series is guaranteed by applying a criterion based on the Lipschitz criterion for continuous functions. Note that the solution obtained, together with the convergence analysis, shows the robustness and accuracy of this methodology.

In the last decades there has been a lot of interest in computational models and metaheuristics algorithms capable to solve combinatorial optimization problems. The recent trend is to define these algorithms taking inspiration by the observation of natural systems. In this thesis the Ant Colony System (ACS) is presented which has been inspired by the observation of real ant colonies. ACS is initially proposed to solve the symmetric and asymmetric travelling salesman problems where it is shown to be competitive with other metaheuristics. Although this is an interesting and promising result, it was immediately clear that ACS, as well as other metaheuristics, in many cases cannot compete with specialized local search methods. An interesting trend is therefore to couple metaheuristics with a local optimizer, giving birth to so-called hybrid methods. Along this line, the thesis investigates MACS-VRPTW (Multiple ACS for the Vehicle Routing Problem with Time Windows) and HAS-SOP: Hybrid Ant System for the Sequential Ordering Problem (SOP). In the second part the thesis introduces some modifications of the original ACS algorithm. These modifications are able to speed up the method and to make it more competitive in case of large problem instances. The resulting framework, called Enhanced Ant Colony System is tested for the SOP. Finally the thesis presents the application of ACS to solve real-life vehicle routing problems where additional constraints and stochastic information are included. / Doctorat en Sciences de l'ingénieur / info:eu-repo/semantics/nonPublished

Orientador: Alice Maria Bastos Hubinger Tokarnia / Dissertação (mestrado) - Universidade Estadual de Campinas,Faculdade de Engenharia Elétrica e de Computação / Made available in DSpace on 2018-08-21T13:10:12Z (GMT). No. of bitstreams: 1 Pepe_PedroCarlosFazolino_M.pdf: 4573450 bytes, checksum: d2aa117fafd3213b052c1164eaabed1f (MD5) Previous issue date: 2012 / Resumo: Este trabalho apresenta quatro algoritmos de escalonamento dinâmico de Tensão e Frequência (DVFS) em sistemas multiprocessador baseado em caminhos de execução. Nossos alvos são aplicações multimídia executadas em sistemas embarcados, com especificação de qualidade por taxa mínima de entradas (QoS) processadas. Uma fração mínima de entradas, geralmente quadros de dados, precisa ser completamente processada no tempo máximo de resposta especificado. O objetivo dos algoritmos é atuar em quatro cenários que correspondem a sistemas com diferentes possibilidades de escalonamento dinâmico de tensão e frequência e diferentes capacidades de monitoramento da qualidade de serviço. No primeiro cenário, todos os pacotes de dados de entrada recebidos devem ser processados dentro do tempo máximo especificado e o nível de tensão/frequência pode ser ajustado no início da execução da aplicação, sendo o mesmo para todos os processadores. Este cenário é referência para comparação de resultados para os outros cenários. Para o segundo cenário, o nível de tensão/frequência pode ser definido individualmente para um processador, no início da execução de cada tarefa, e dados de entrada de classes específicas podem ser descartados. O terceiro cenário possibilita, além do descarte de classes específicas de dados de entrada, o ajuste do nível de tensão/frequência de cada tarefa de acordo com a classe de dados de entrada a ser processada. O algoritmo desenvolvido para o quarto cenário trata dinamicamente de alterações na distribuição probabilística das classes de entrada, calculando novos níveis de tensão/frequência para as tarefas e classes de entrada de modo que a especificação de qualidade continue a ser satisfeita, de forma eficiente. Para uma aplicação de cancelamento de eco acústico, executada em 4 processadores, com taxa mínima de processamento igual a 50%, o algoritmo de escalonamento de tensão e frequência, no cenário 3, conseguiu reduzir o consumo de energia em cerca de 71%, comparado ao cenário 1. No cenário 4, simulamos para esta aplicação uma modificação simultânea de 10 pontos percentuais na distribuição das classes de entrada em 3 tarefas causando aumentos do número de descartes. O algoritmo proposto para o cenário 4 manteve a qualidade mínima com um aumento de apenas 6% no consumo de energia, quando comparado ao consumo de energia da configuração inicial definida para o cenário 3 / Abstract: This work presents four execution-path based Dynamic Voltage/Frequency Scaling (DVFS) algorithms for multiprocessor systems. The targets are embedded systems multimedia applications, with minimum input data completion rate specification (QoS). A minimum fraction of input data, usually data frames, should be processed within the specified deadline. These algorithms aim to operate in four scenarios corresponding to systems with different possibilities of dynamic voltage and frequency scheduling and different QoS monitoring capabilities. In the first scenario, all received data frames should be treated within the deadline and the voltage/frequency operational level can be adjusted at the beginning of the application execution, and must be the same for all processors. This scenario is a reference for comparison of results obtained for the other scenarios. For the second scenario, the voltage/frequency operational level can be set individually for each processor at the beginning of each task execution, and input data frames of specific input classes can be discarded. The third scenario allows, besides discarding specific classes of input data, it is possible to adjust the operation level for each task, according to the class of the input data to be treated. The algorithm for the fourth scenario operates online, computing new voltage/frequency levels and making new decisions about class discarding to cope with changes in probability distribution of input classes. Its goal is to maintain the specified quality with low energy consumption. In an application of acoustic echo cancellation running on a system with 4 processors, with a rate of inputs completely processed specified as 50%, the algorithm for scenario 3 achieved a reduction in consumption close to 71%, comparing to the results for scenario 1. During simulation, this application has been subjected to simultaneous changes of 10% in the input class distributions of three discarding tasks, reducing system quality. The algorithm for scenario 4, maintained the minimum quality with just 6% increase in power consumption, when compared to the consumption of the initial configuration for scenario 3 / Mestrado / Engenharia de Computação / Mestre em Engenharia Elétrica

This thesis focuses on a description of the split delivery vehicle routing problem (SDVRP), in which the restriction that each customer has to be visited exactly once is not assumed, contrary to the classical vehicle routing problem, and split deliveries are allowed. Considering the fact that the split delivery vehicle routing problem in NP-hard, a number of heuristic algorithms proposed in the literature are presented. Computational experiments are reported and the results show that the largest benefits of split deliveries are obtained in case of instances with fairly specific characteristics and also several drawbacks of implemented Tabu Search algorithm (SPLITABU) are point out.