Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia Elétrica. / Made available in DSpace on 2013-07-15T23:42:02Z (GMT). No. of bitstreams: 0

Made available in DSpace on 2019-03-30T00:01:20Z (GMT). No. of bitstreams: 0 Previous issue date: 2017-09-22 / Some software systems must respond to thousands or millions of concurrent requests. These systems must be properly tested to ensure that they can function correctly under the expected load. Performance degradation and consequent system failures usually arise in stressed conditions. Stress testing subjects the program to heavy loads. Stress tests di¿er from other kinds of testing in that the system is executed on its breakpoints, forcing the application or the supporting infrastructure to fail. The search for the longest execution time is seen as a discontinuous, nonlinear, optimization problem, with the input domain of the system under test as a search space. In this context, search-based testing is viewed as a promising approach to verify timing constraints. Search-based software testing is the application of metaheuristic search techniques to generate software tests. The test adequacy criterion is transformed into a ¿tness function and a set of solutions in the search space is evaluated with respect to the ¿tness functionusingametaheuristic. Search-basedstresstestinginvolves¿ndingthebest-andworst-case executiontimestoascertainwhethertimingconstraintsareful¿lled. ServiceLevelAgreements (SLAs) are documents that specify realistic performance guarantees as well as penalties for non-compliance. SLAsaremadebetweenprovidersandcustomersthatincludeservicequality, resourcescapability,scalability,obligations,andconsequencesincaseofviolations. Satisfying SLAisofgreatimportanceandachallengingissue. Themainmotivationofthisthesisisto¿nd theadequateresponsetimeofSLAsusingStressTesting. Thisthesisaddressesthreeapproaches insearch-basedstresstests. First,HybridmetaheuristicusesTabuSearch,SimulatedAnnealing, andGeneticAlgorithmsinacollaborativemanner. Second,anapproachcalledHybridQusesa reinforcementlearningtechniquetooptimizethechoiceofneighboringsolutionstoexplore,reducingthetimeneededtoobtainthescenarioswiththelongestresponsetimeintheapplication. The best solutions found by HybridQ were on average 5.98% better that achieved by the Hybrid approach without Q-learning. Third, the thesis investigates the use of the multi-objective NSGA-II,SPEA2,PAESandMOEA/Dalgorithms. MOEA/Dmetaheuristicsobtainedthebest hypervolume value when compared with other approaches. The collaborative approach using MOEA/D and HybridQ improves the hypervolume values obtained and found more relevant workloadsthanthepreviousexperiments. AtoolnamedIAdapter,aJMeterpluginforperformingsearch-basedstresstests,wasdevelopedandusedtoconductalltheexperiments. Keywords: Search-based Testing, Stress Testing, Multi-objective metaheuristics, Hybrid metaheuristics,ReinforcementLearning. / Alguns sistemas de software devem responder a milhares ou milhões de requisições simultâneos. Tais sistemas devem ser devidamente testados para garantir que eles possam funcionar corretamente sob uma carga esperada. Normalmente, a degradação do desempenho e consequentes falhas do sistema geralmente ocorrem em condições de estresse. No teste de estresse o sistema é submetido a cargas de trabalho acima dos resquistos não funcionais estabelecidos. Os testes de estresse diferem de outros tipos de testes em que o sistema é executado em seus pontos de interrupção, forçando o aplicativo ou a infra-estrutura de suporte a falhar. Testes de estresse podem ser vistos como um problema de otimização descontínuo, não-linear, comodomínio de entrada do sistema em test ecomo espaço de busca. Neste contexto,ostestes baseados em busca (search-based tests) são vistos como uma abordagem promissora para veri¿car as restrições de tempo. O teste de software baseado em busca é a aplicação de técnicas de pesquisa metaheurística para gerar testes de software. O critério de adequação do teste é transformado em uma função objetivo e um conjunto de soluções no espaço de busca é avaliado em relação à função objetivo usando uma metaheurística. Otestedeestressebaseadoembusca envolve encontrar os tempos de execução melhores e piores para veri¿car se as restrições de tempo são cumpridas. Os acordos de nível de serviço (SLA) são documentos que especi¿cam garantias de desempenho realistas, bem como penalidades por incumprimento. Os SLAs são feitos entre provedores e clientes que incluem qualidade do serviço, capacidade de recursos, escalabilidade, obrigações e consequencias em caso de violação. Satisfazer o SLA é de grande importância e um problema desa¿ador. A principal motivação desta tese é encontrar o tempo de resposta adequado dos SLAs usando teste de estresse. Esta tese apresenta três abordagens em testes de estresse baseados em busca. Primeiro, a metaheurística híbrida usa Tabu Search, Simulated Annealing e Algoritmos Genéticos de forma colaborativa. Em segundo lugar, uma abordagem chamada HybridQ usa uma técnica de aprendizado de reforço para otimizar a escolha de soluções vizinhas para explorar, reduzindo o tempo necessário para obter os cenários com o tempo de resposta mais longo na aplicação. As melhores soluções encontradas pelo HybridQ foram em média 5,98 % melhores que alcançadas pela abordagem híbrida sem Qlearning. Em terceiro lugar, a tese investiga o uso dos algoritmos multi-objetivos NSGA-II, SPEA2, PAES e MOEA/D. A metaheurística MOEA/D obteve o melhor valor de hipervolume quando comparada com outras abordagens. A abordagem colaborativa usand oMOEA/DeHybridQ melhora os valores de hipervolume obtidos e encontrou workloads mais relevantes do que as experiências anteriores. Uma ferramenta chamada IAdapter, um plugin JMeter para realizar testes de esforço baseados em busca, foi desenvolvida e usada para realizar todas as experiências. Palavras-chave: Search-basedTesting,StressTesting,Multi-objective metaheuristics,Hybridmetaheuristics,ReinforcementLearning

PERICINI, Matheus Henrique Machado. Utilização de metaheurísticas para balanceamento de carga em ambientes MapReduce. 2017. 71 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2017. / Submitted by Jonatas Martins (jonatasmartins@lia.ufc.br) on 2017-10-19T17:17:01Z No. of bitstreams: 1 2017_dis_mhmpericini.pdf: 2342022 bytes, checksum: 8bfd2d1fee199d87109de3ba41cb73df (MD5) / Approved for entry into archive by Jairo Viana (jairo@ufc.br) on 2017-10-30T17:13:30Z (GMT) No. of bitstreams: 1 2017_dis_mhmpericini.pdf: 2342022 bytes, checksum: 8bfd2d1fee199d87109de3ba41cb73df (MD5) / Made available in DSpace on 2017-10-30T17:13:30Z (GMT). No. of bitstreams: 1 2017_dis_mhmpericini.pdf: 2342022 bytes, checksum: 8bfd2d1fee199d87109de3ba41cb73df (MD5) Previous issue date: 2017 / With the increase in the number of data obtained by large companies, it was necessary to elaborate new strategies for the processing of this data in order to maintain the relevance of the information that they contain. One of the strategies that has been widely used is based on a programming model, called MapReduce, which uses division and conquest to process the data in a cluster of machines. Hadoop is one of the most consolidated implementations of the MapReduce model. But even such a strategy is subject to improvement. In it, the runtime depends on all the machines causing any overloaded machine to generate a delay in the delivery of the result. This overhead is caused by a problem commonly called Data Skew which consists of an unequal division of data, either by the size of the data or by the way it is divided. In order to solve this problem, we have proposed the MALiBU, an improvement of the execution strategy of Hadoop, which partitions the data between the machines using a meta-heuristic among them Simulated Annealing, Local Beam Search or Stochastic Beam Search. Experimental results showed improvements in the performance of Hadoop when using metaheuristics to distribute the data among the processing elements of the model, as well as among the three meta-heuristics evaluated, which has the best results. / Com o aumento do número de dados obtidos por grandes empresas, foi necessário elaborar novas estratégias para o processamento desses dados de modo a manter sua relevância e aproveitar suas informações. Uma das estratégias que tem sido amplamente utilizada tem como base um modelo de programação, chamado MapReduce, que utiliza divisão e conquista para processar os dados em um cluster de máquinas. O Hadoop é uma das implementações mais consolidadas do modelo de MapReduce. Mas mesmo tal estratégia é passível de melhorias. Nela o tempo de execução é dependente de todas as máquinas fazendo com que qualquer máquina sobrecarregada gere um atraso na entrega do resultado. Essa sobrecarga é causada por um problema chamado comumente de Data Skew que consiste em uma divisão desigual dos dados causado pelo tamanho dos dados, o modo como eles são divididos, ou o processamento desigual dos dados. Visando resolver esse problema, propusemos o MALiBU, uma melhoria da estratégia de execução do MapReduce que particiona os dados entre as máquinas usando uma meta-heurística dentre elas Simulated Annealing, Local Beam Search ou Stochastic Beam Search. Resultados experimentais mostraram melhorias no desempenho do MapReduce quando se faz uso de meta-heurística para distribuir os dados entre as máquinas, bem como mostraram, dentre as três meta-heurísticas avaliadas, qual delas melhor balanceia a carga.

La planificación, programación y control de la producción se encargan de diseñar, coordinar y administrar todas las operaciones que se hallan presentes en la explotación de los sistemas productivos. En las últimas décadas muchos problemas de optimización multi-objetivo han surgido en este ámbito y fueron tratados con éxito con técnicas de resolución basadas en metaheurísticas, en general, y con algoritmos evolutivos, en particular. Dichas técnicas, sin descartar otras, constituyen potentes herramientas para tratar adecuadamente estos problemas en el marco de las operaciones productivas y logísticas. La complejidad que se presenta en estos problemas se debe a los criterios de eficiencia que se imponen a los distintos sistemas productivos. Este estudio se extiende al desarrollo y análisis de un procedimiento, enmarcado en la estructura particular de un algoritmo evolutivo para resolver el problema de secuenciación de trabajos (JSSP, Job-Shop Scheduling Problem). Además, se explora la vecindad de las distintas soluciones dentro de la misma evolución, lo que mejora significativamente los resultados. El algoritmo propuesto utiliza una codificación basada en asignación de secuencias para poder establecer permutaciones con repeticiones. Esta representación, muy sencilla y compacta, distingue a este estudio de otros. Luego de finalizar el procedimiento, se adiciona una etapa de simulación a modo de examinar las soluciones obtenidas en la etapa resolutiva. Se realiza un análisis comparativo con otros algoritmos para constatar la eficiencia del procedimiento. Finalmente, se presenta una aplicación de la técnica en varias empresas, lo que permitió contrastar los resultados obtenidos con la realidad. / The study of planning, programming and controlling production processes yields methods of design, coordination and management of the operations involved in productive systems. In the last decades several multi-objective optimization problems have arisen in those studies and have been solved successfully with techniques based on meta-heuristics, in general, and evolutionary algorithms in particular. These techniques, notwithstanding the existence of other useful tools, provide the adequate means for treating those optimization problems in the realm of logistics and operations analysis. The complexity of the problems stems from the efficiency criteria imposed over the solution candidates. This work extends those tools to the development and analysis of an evolutionary procedure aimed to solving the Job-Shop Scheduling Problem (JSSP). We explore ways of improving solutions in the vicinity of already found candidates. The algorithm generates sequences that allow permutations with repetition. This representation, simple enough, distinguishes this study from others. After running the procedure, a comparison with other algorithms is presented, based on simulations. Finally, the algorithm is applied to analyze real-world applications.

Made available in DSpace on 2019-03-29T23:32:55Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-08-30 / The aim of this study is to establish a parallel between four bioinspired metaheuristic algorithms (namely, Genetic Algorithm, Differential Evolution, Particle Swarm Optimization, and Harmony Search), testing them with continuous optimization benchmark functions and assessing them based on data collected about the quality of the solutions they generate and based on the way they explore the search space. Novel techniques are proposed to collect data about the modus operandi of the algorithms using Voronoi Diagrams and through a division of the search space in bi-dimensional regions using Self-Organizing Maps. The use of these maps as a Visual Data Mining tool aims to process the resulting data and identify the available clusters. We wish to understand the influence of parameter calibration on the search behavior of the metaheuristic algorithms, as well as their sensitivity to dimension changes of the optimization functions they are solving. Furthermore, behavior profiles can be established and patterns can be defined, allowing us to analyze in detail the similarities/dissimilarities between the algorithms. All metaheuristics were implemented step-by-step to allow us to understand their inner workings, peculiarities, and also facilitate the tracking of their search behavior along their execution on the optimization problems. Keywords: Bioinspired Metaheuristics. Information Visualization. Visual Data Mining. Self-Organizing Maps. Kohonen Maps. Voronoi Diagrams. / Este trabalho tem por finalidade traçar um paralelo entre quatro algoritmos bio-inspirados de cunho meta-heurístico (a saber: Algoritmo Genético, Evolução Diferencial, Otimização por Enxame de Partículas e Busca Harmônica), testando-os em funções de benchmark de otimização contínua e avaliando-os com base em dados coletados sobre a qualidade das soluções geradas e sobre o modo de exploração do espaço de busca. São propostas aqui técnicas de coleta de informações sobre o modus operandi dos algoritmos que envolvem Diagramas de Voronoi e divisão do espaço de busca em regiões bidimensionais utilizando Mapas Auto-organizáveis. O uso desses mapas como ferramenta de Mineração Visual de Dados tem como objetivo avaliar os dados gerados e identificar os agrupamentos que foram formados. Procuramos entender a influência da alteração dos valores dos parâmetros das meta-heurísticas no seu comportamento ao longo do tempo, bem como a sua sensibilidade às mudanças de dimensão das funções de otimização que estão solucionando. Dessa forma, almeja-se traçar perfis de comportamento e definir a posteriori um padrão para possibilitar a análise mais detalhada das similaridades/dissimilaridades entre as abordagens. Todos os algoritmos utilizados foram implementados passo-a-passo a fim de entender as suas particularidades, esclarecer melhor seus mecanismos internos e facilitar o rastreamento do comportamento dos mesmos no ato da resolução dos problemas. Palavras-chave: Meta-heurísticas Bioinspiradas. Visualização da Informação. Mineração Visual de Dados. Mapas Auto-Organizáveis. Mapas de Kohonen. Diagramas de Voronoi.

Nesta dissertação convergem algumas linhas de investigação na área das meta-heurísticas que, recentemente, têm vindo a ser objecto de particular atenção: a flexibilização, ou seja, a introdução de mecanismos de modificação de componentes e estratégias elementares, o desenvolvimento de abordagens orientadas por objectos, e a adaptação a contextos multiobjectivo. Esta convergência justifica-se pelo facto de as abordagens orientadas por objectos promoverem naturalmente a flexibilização, e pela constatação da inexistência, até ao momento, de abordagens orientadas por objectos para a área das metaheurísticas multiobjectivo. Foi feita uma análise e sistematização do domínio e, em particular, das metaheurísticas multiobjectivo, com ênfase na perspectiva da flexibilização. Esta sistematização fundamenta a proposta de um template para pesquisa local multiobjectivo, e de um conjunto de estratégias genéricas de flexibilização.

El problema de corte y empaquetado en dos dimensiones, es un problema NP- difícil perteneciente a la familia de problemas de la optimización combinatoria. El problema combinatorio estriba en la gran cantidad de patrones de corte que puede construirse a partir de un número determinado de requerimientos y un conjunto de objetos los cuales deben ser cortados para satisfacer estos. Este problema es muy importante debido a la gran cantidad de aplicaciones que tiene en la industria. En este trabajo presentamos un estudio de los diferentes métodos que resuelven el problema, clasificándolos por métodos exactos, heurísticas y meta heurísticas. También presentamos conceptos, modelos del problema y las relaciones con otros problemas combinatorios. / Two dimensional cutting and packing problems is NP-hard, it belong to the family of problems of the optimization combinatory. This problem is based in the great amount of cut patterns that can be constructed from a determined number of requirements and a set of objects which must be cut to satisfy these. This problem is very important because it presents enormous applicability in the industry. In this work we presented a study of the different methods that solve the problem, classifying them by exact methods, heuristic and meta heuristic. Also we presented concepts, models and the relations with other combinatory problems.

Made available in DSpace on 2016-08-29T15:36:59Z (GMT). No. of bitstreams: 1 tese_5351_.pdf: 1690430 bytes, checksum: fc8ed930b6e3cdee37d30a437bf819b8 (MD5) Previous issue date: 2012-03-01 / COSTA, Marcos Fávero. Aplicação de meta-heurísticas no escalonamento de motoristas para o transporte de madeira. 2012. Dissertação (Mestrado em Ciências Florestais) Universidade Federal do Espírito Santo, Alegre-ES. Orientador: Prof. Dr. Nilton Cesar Fiedler. Coorientador: Prof. Dr. Geraldo Regis Mauri. O transporte de cargas do setor florestal brasileiro é realizado em sua maior parte pelo modal rodoviário. Sua complexidade exibe a importância de diagnosticar o desenvolvimento da atividade para que se possa, por meio da pesquisa operacional, empregar de forma mais eficiente seus recursos disponíveis sem que haja perda de produtividade. Atualmente, o problema de escalonamento de motoristas é considerado um dos principais entraves à otimização em empresas de transporte, pois apresenta uma grande quantidade de restrições físicas e técnicas. Esta pesquisa teve como objetivo solucionar um problema real de escalonamento de motoristas no transporte de madeira de uma empresa florestal por meio de cinco meta-heurísticas (Algoritmo Genético AG, Algoritmo Memético AM, Clustering Search CS, Greedy Randomized Adaptive Search GRASP e Simulated Annealing SA), comparar os métodos entre si e entre a situação corrente na empresa, e propor uma nova escala de serviços. Para validação da abordagem proposta, foi utilizada uma entrada de dados gerada a partir da pesquisa qualitativa e de estudos de tempos e movimentos. Os resultados indicam que todos os métodos foram eficientes para resolver o problema sobressaindo-se o CS como melhor, seguido do SA, GRASP, AM e AG. O CS conseguiu atender aos objetivos com uma redução em 1/3 do quadro de 150 motoristas além de eliminar médias diárias de horas extras e excedentes que eram de 01h03min e 00h51min, respectivamente. Palavras-chave: transporte florestal, meta-heurísticas, escalonamento de motoristas, logística de transporte, produção florestal.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Computação, Florianópolis, 2011 / Made available in DSpace on 2012-10-25T15:06:52Z (GMT). No. of bitstreams: 1 292866.pdf: 11944502 bytes, checksum: af23b7398a934a57e26ae19c7d723aeb (MD5) / Otimização por Colônia de Formigas (Ant Colony Optimization - ACO) é uma meta-heurística de otimização baseada no comportamento das formigas na busca por alimento. Esta meta-heurística foi originalmente desenvolvida para encontrar boas soluções em problemas de otimização combinatória discretos. Em domínios contínuos, a discretização do intervalo tem sido praticada para o uso de técnicas baseadas em ACO. Extensões do ACO para trabalhar diretamente com domínios contínuos têm surgido, entretanto as propostas mais similares à ideia clássica não usam a informação heurística chamada visibilidade, geralmente presente em algoritmos de ACO discreto. Neste trabalho é realizada uma revisão da ideia central do ACO mostrando a importância da visibilidade em domínios discretos e estendendo sua implementação em algoritmos ACO com domínio contínuo. Resultados de experimentos mostram a melhora na velocidade de convergência com o uso da heurística de visibilidade.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia Civil, Florianópolis, 2015. / Made available in DSpace on 2016-10-19T13:08:12Z (GMT). No. of bitstreams: 1 338188.pdf: 3091652 bytes, checksum: c043e2c0726edfda841374506edc4107 (MD5) Previous issue date: 2015 / Um operador baseado na maximização da rigidez é implementado como objetivo de melhorar a convergência de algoritmos metaheurísticos na otimização simultânea dimensional, de forma e topológica de treliças com variáveis mistas. O problema estudado apresenta não-convexidade, o que justifica o uso de algoritmos heurísticos na sua solução. O operador faz uso da informação do gradiente do trabalho em relação às variáveis de forma, as únicas contínuas, para buscar uma estrutura mais rígida. O gradiente do trabalho é significativamente menos custoso de ser obtido computacionalmente do que o gradiente da função objetivo e por isso é empregado no presente trabalho. A busca unidimensional é realizada minimizando-se o trabalho e o peso simultaneamente. O algoritmo de competição imperialista ICA, um algoritmo metaheurístico de população, é usado para testar o novo operador. Três problemas clássicos de topologia inicial são estudados com e sem o operador e os resultados obtidos são comparados com a literatura. O operador se mostrou eficiente dependendo do problema estudado sendo especialmente eficaz quando restrições de deslocamento máximo se encontram ativas.<br> / Abstract : A operator based on the maximization of stiffness is implemented withthe objective of improving the convergence of metaheuristic algorithmson the simultaneous optimization of dimensions, shape and topology oftrusses with mixed variables. The use of metaheuristics is justified by thenonconvexity of the problem. The proposed operator uses the gradient ofthe work by the shape variables - the ones treated as continuous on thepresent work - to search for a stiffer structure. The use of the gradientof the work is justified for its low cost to evaluate. The unidimensionalsearch on the direction of the work gradient is realized through theminimization of a combined function of the penalized weight and thework absorbed by the truss. The ICA, a population based metaheuristic,is employed to test the new operator. Three ground structure benchmarkproblems are analysed with and without the operator and the resultsare compared. The proposed operator proved to be efFicient dependingon the studied problem, specially when the stiffness of the structure ismore important for its performance.