• Refine Query
  • Source
  • Publication year
  • to
  • Language
  • 38
  • 7
  • 6
  • 6
  • 6
  • 6
  • 1
  • Tagged with
  • 40
  • 40
  • 18
  • 17
  • 12
  • 11
  • 10
  • 10
  • 10
  • 9
  • 8
  • 7
  • 7
  • 7
  • 7
  • About
  • The Global ETD Search service is a free service for researchers to find electronic theses and dissertations. This service is provided by the Networked Digital Library of Theses and Dissertations.
    Our metadata is collected from universities around the world. If you manage a university/consortium/country archive and want to be added, details can be found on the NDLTD website.
1

Ferramentas integradas de acesso remoto para apoiar o auto-estudo e a competição em jogos heurísticos

Barbieri, Henrique Teske 27 April 2010 (has links)
No description available.
2

Otimização de problemas multimodais usando meta-heurísticas evolutivas /

Uzinski, Henrique. January 2014 (has links)
Orientador: Rubén Augusto Romero Lázaro / Banca: Marina Lavorato de Oliveira / Banca: Marcelo Escobar de Oliveira / Resumo: Neste trabalho é proposta a resolução de problemas multimodais usando duas diferentes meta-heurísticas: Algoritmo Genético de Chu-Beasley modificado e o Algoritmo Genético de Chaves Aleatórias Viciadas (BRKGA), com foco principal nos resultados obtidos por esta última. É feita especificamente a implementação das meta-heurísticas e comparação dos resultados obtidos por estas diferentes técnicas. Uma característica muito importante do BRKGA é a estruturação que permite separar o algoritmo em duas parcelas claramente diferenciadas, uma parcela que depende exclusivamente das características do BRKGA e, portanto, independente do problema que se pretende resolver e outra parcela que depende exclusivamente das características especificas do problema que pretendemos resolver. Essa característica geral do BRKGA permite que ele seja facilmente aplicado a uma grande variedade de problemas, já que a primeira parcela pode ser integralmente aproveitada na resolução de um novo problema. Por outro lado, o Algoritmo Genético de Chu-Beasley (AGCB) é caracterizado pela substituição de um único indivíduo no ciclo geracional e pelo controle máximo de diversidade, mas isto não é suficiente para resolução de problemas complexos e multimodais, sendo assim, é apresentado o AGCB modificado, onde o critério de diversidade é estendido, a população inicial e o descendente gerado no ciclo geracional passa por uma melhoria local. Essas características tornam-o competitivo justificando a comparação com o BRKGA / Abstract: In this work it is proposed the resolution of multimodal problems using two different meta- heuristics: Chu-Beasley's Genetic Algorithm and Biased Random Key Genetic Algorithm (BRKGA), focusing mainly on the results obtained by the latter. Specifically the imple- mentation and comparison of results obtained by these different techniques is made. There are several metaheuristics, each with its own specific characteristics which have advan- tages and disadvantages for the resolution of certain problems and in several ways in the implementation and results. A very important feature of the BRKGA is the structure that allows to separate the algorithm into two clearly different parts, one part that depends exclusively on the characteristics of BRKGA and therefore independent of the problem to be solved and another part that depends exclusively on the specific characteristics of the problem we intend to solve. This general feature of the BRKGA allows it to be readily applied to a variety of problems, because the first component part can be fully utilized to solve a new problem. On the other hand, Chu-Beasley's Genetic Algorithm (AGCB) is characterized by the replacement of a single individual in the generation cycle and by maximum control of diversity, but this is not enough to solve complex and multimodal problems, therefore it is presented the modified AGCB, where the diversity criterion is extended, the initial population and the descendant generated in the generational cycle passes through a local improvement. These features make it competitive, justifying the comparison with BRKGA / Mestre
3

Aplicação de meta-heurísticas na resolução do problema de balanceamento e designação de trabalhadores com deficiência em linha de produção /

Silva, Renato Teixeira da. January 2012 (has links)
Orientador: Galeno José de Sena / Banca: Marcos Antonio Pereira / Banca: Anibal Tavares de Azevedo / Resumo: A Organização Internacional do Trabalho estima que existem cerca de 650 milhões de pessoas com deficiência em idade produtiva. No entanto, esta parcela da população possui altos índices de desemprego devido a várias barreiras. Uma alternativa para facilitar a inclusão dessas pessoas é a criação de Centros de Trabalho para pessoas com Deficiência (CTD's) onde as pessoas com deficiência tenham a oportunidade de experimentar um ambiente de trabalho real antes de irem para um emprego "normal". Neste tipo de ambiente, onde é impossível ao gestor prever quais trabalhadores estarão disponíveis a cada dia devido às altas taxas de absenteísmo, há a necessidade de se definir uma organização mais produtiva diariamente. Neste contexto se torna oportuna a utilização do Problema de Balanceamento de Linha e Designação de Trabalhadores (em inglês ALWABP), onde se busca minimizar o tempo de ciclo a partir de um dado número de trabalhadores, alocando tarefas às estações de trabalho e trabalhadores às estações, tendo em vista que alguns trabalhadores podem ser muito lentos para executar certas tarefas ou até incapazes, devido a alguma deficiência que eles apresentam, e muito eficientes na execução de outras. O objetivo geral desta dissertação consiste em empregar diferentes meta-heurísticas para resolver o ALWABP, comparando com os melhores resultados das instâncias encontradas na literatura. Dentre várias meta-heurísticas disponíveis na literatura foram utilizados o Harmony Search (HS), o Adaptive Large Neighborhood Search (ALNS) e o Clustering Search (CS) utilizando o HS e o ALNS como heurísticas geradoras de soluções. Cada uma das quatro implementações foram testadas em 320 instâncias propostas na literatura divididas em quatro famílias. Os experimentos computacionais mostraram bons resultados... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: The International Labour Organization estimates that there are approximately 650 million disabled people in working age. However, this population presents high rates of unemployment due to numerous barriers. An alternative to facilitate the inclusion of these people is the establishment of Centers for Working People with Disabilities where people with disabilities have the opportunity to experience a real work environment before going to a "normal" job. In this type of environment, where it is impossible to predict which workers will be available each day due to high rates of absence in this population, there is a need to define a more productive organization on a daily basis. In this context it becomes appropriate to use the Assembly Line Worker Assignment and Balancing Problem (ALWABP), which seeks to minimize the cycle time for a given number of workers, assigning tasks to workstations and workers to stations, considering that some workers may be too slow to perform certain tasks, or even unable due to some deficiency they present, and very efficient in performing others. The aim of this dissertation is to employ different meta-heuristics to solve the ALWABP, comparing with the best results of instances found in the literature. Among several meta-heuristics available in the literature were used Harmony Search (HS), Adaptive Large Neighborhood Search (ALNS) and Clustering Search (CS) using the HS and ALNS as heuristics for the generation of solutions. Each of the four implementations has been tested in 320 instances proposed in the literature, classified into four families. The computational experiments showed good results, and in some instances obtaining better solution values best known. Conclusions regarding... (Complete abstract click electronic access below) / Mestre
4

Otimização de problemas multimodais usando meta-heurísticas evolutivas

Uzinski, Henrique [UNESP] 24 October 2014 (has links) (PDF)
Made available in DSpace on 2015-03-03T11:52:33Z (GMT). No. of bitstreams: 0 Previous issue date: 2014-10-24Bitstream added on 2015-03-03T12:06:30Z : No. of bitstreams: 1 000808114.pdf: 869921 bytes, checksum: d49e859927277a17ca43ba9e2d635677 (MD5) / Neste trabalho é proposta a resolução de problemas multimodais usando duas diferentes meta-heurísticas: Algoritmo Genético de Chu-Beasley modificado e o Algoritmo Genético de Chaves Aleatórias Viciadas (BRKGA), com foco principal nos resultados obtidos por esta última. É feita especificamente a implementação das meta-heurísticas e comparação dos resultados obtidos por estas diferentes técnicas. Uma característica muito importante do BRKGA é a estruturação que permite separar o algoritmo em duas parcelas claramente diferenciadas, uma parcela que depende exclusivamente das características do BRKGA e, portanto, independente do problema que se pretende resolver e outra parcela que depende exclusivamente das características especificas do problema que pretendemos resolver. Essa característica geral do BRKGA permite que ele seja facilmente aplicado a uma grande variedade de problemas, já que a primeira parcela pode ser integralmente aproveitada na resolução de um novo problema. Por outro lado, o Algoritmo Genético de Chu-Beasley (AGCB) é caracterizado pela substituição de um único indivíduo no ciclo geracional e pelo controle máximo de diversidade, mas isto não é suficiente para resolução de problemas complexos e multimodais, sendo assim, é apresentado o AGCB modificado, onde o critério de diversidade é estendido, a população inicial e o descendente gerado no ciclo geracional passa por uma melhoria local. Essas características tornam-o competitivo justificando a comparação com o BRKGA / In this work it is proposed the resolution of multimodal problems using two different meta- heuristics: Chu-Beasley’s Genetic Algorithm and Biased Random Key Genetic Algorithm (BRKGA), focusing mainly on the results obtained by the latter. Specifically the imple- mentation and comparison of results obtained by these different techniques is made. There are several metaheuristics, each with its own specific characteristics which have advan- tages and disadvantages for the resolution of certain problems and in several ways in the implementation and results. A very important feature of the BRKGA is the structure that allows to separate the algorithm into two clearly different parts, one part that depends exclusively on the characteristics of BRKGA and therefore independent of the problem to be solved and another part that depends exclusively on the specific characteristics of the problem we intend to solve. This general feature of the BRKGA allows it to be readily applied to a variety of problems, because the first component part can be fully utilized to solve a new problem. On the other hand, Chu-Beasley’s Genetic Algorithm (AGCB) is characterized by the replacement of a single individual in the generation cycle and by maximum control of diversity, but this is not enough to solve complex and multimodal problems, therefore it is presented the modified AGCB, where the diversity criterion is extended, the initial population and the descendant generated in the generational cycle passes through a local improvement. These features make it competitive, justifying the comparison with BRKGA
5

Aplicação de meta-heurísticas na resolução do problema de balanceamento e designação de trabalhadores com deficiência em linha de produção

Silva, Renato Teixeira da [UNESP] 26 October 2012 (has links) (PDF)
Made available in DSpace on 2014-06-11T19:26:18Z (GMT). No. of bitstreams: 0 Previous issue date: 2012-10-26Bitstream added on 2014-06-13T19:33:57Z : No. of bitstreams: 1 silva_rt_me_guara.pdf: 445223 bytes, checksum: f6563e16194940a8f4f8abc7c03ac033 (MD5) / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES) / A Organização Internacional do Trabalho estima que existem cerca de 650 milhões de pessoas com deficiência em idade produtiva. No entanto, esta parcela da população possui altos índices de desemprego devido a várias barreiras. Uma alternativa para facilitar a inclusão dessas pessoas é a criação de Centros de Trabalho para pessoas com Deficiência (CTD`s) onde as pessoas com deficiência tenham a oportunidade de experimentar um ambiente de trabalho real antes de irem para um emprego “normal”. Neste tipo de ambiente, onde é impossível ao gestor prever quais trabalhadores estarão disponíveis a cada dia devido às altas taxas de absenteísmo, há a necessidade de se definir uma organização mais produtiva diariamente. Neste contexto se torna oportuna a utilização do Problema de Balanceamento de Linha e Designação de Trabalhadores (em inglês ALWABP), onde se busca minimizar o tempo de ciclo a partir de um dado número de trabalhadores, alocando tarefas às estações de trabalho e trabalhadores às estações, tendo em vista que alguns trabalhadores podem ser muito lentos para executar certas tarefas ou até incapazes, devido a alguma deficiência que eles apresentam, e muito eficientes na execução de outras. O objetivo geral desta dissertação consiste em empregar diferentes meta-heurísticas para resolver o ALWABP, comparando com os melhores resultados das instâncias encontradas na literatura. Dentre várias meta-heurísticas disponíveis na literatura foram utilizados o Harmony Search (HS), o Adaptive Large Neighborhood Search (ALNS) e o Clustering Search (CS) utilizando o HS e o ALNS como heurísticas geradoras de soluções. Cada uma das quatro implementações foram testadas em 320 instâncias propostas na literatura divididas em quatro famílias. Os experimentos computacionais mostraram bons resultados... / The International Labour Organization estimates that there are approximately 650 million disabled people in working age. However, this population presents high rates of unemployment due to numerous barriers. An alternative to facilitate the inclusion of these people is the establishment of Centers for Working People with Disabilities where people with disabilities have the opportunity to experience a real work environment before going to a “normal” job. In this type of environment, where it is impossible to predict which workers will be available each day due to high rates of absence in this population, there is a need to define a more productive organization on a daily basis. In this context it becomes appropriate to use the Assembly Line Worker Assignment and Balancing Problem (ALWABP), which seeks to minimize the cycle time for a given number of workers, assigning tasks to workstations and workers to stations, considering that some workers may be too slow to perform certain tasks, or even unable due to some deficiency they present, and very efficient in performing others. The aim of this dissertation is to employ different meta-heuristics to solve the ALWABP, comparing with the best results of instances found in the literature. Among several meta-heuristics available in the literature were used Harmony Search (HS), Adaptive Large Neighborhood Search (ALNS) and Clustering Search (CS) using the HS and ALNS as heuristics for the generation of solutions. Each of the four implementations has been tested in 320 instances proposed in the literature, classified into four families. The computational experiments showed good results, and in some instances obtaining better solution values best known. Conclusions regarding... (Complete abstract click electronic access below)
6

Algoritmos de nuvem de partículas e a otimização com muitos objetivos

Castro Junior, Olacir Rodrigues 26 March 2013 (has links)
Resumo: Problemas de otimização multiobjetivo (MOPs) sao problemas que possuem mais de uma função objetivo a ser minimizada ou maximizada. Entre as abordagens mais utilizadas atualmente para resolve-los destaca-se o uso de metaheurísticas populacionais. Esta popularidade se deve principalmente à natureza destas de lidar simultaneamente com diversas soluções (populacao) em uma única execucao. Um algoritmo muito utilizado para lidar com MOPs e chamado otimizacao por nuvem de partículas multiobjetivo (MOPSO), esta e uma abordagem derivada da otimizaçao por nuvem de partículas (PSO), que e uma metaheurística inspirada no comportamento de conjuntos de aves. Devido ao bom desempenho apresentado pelos MOPSOs ao resolver MOPs, esta abordagem vem sendo estendida para a resolucao de problemas de otimizaçao com muitos objetivos (MaOPs). Estes problemas sao caracterizados por apresentarem mais de tres funçoes objetivo e uma alta complexidade causada principalmente porque a proporçao de soluções não dominadas em uma populacao aumenta rapidamente com o número de objetivos, o que diminui a pressao de selecõo em direçao a fronteira de Pareto. Alem disso, o numero de pontos necessúrios para representar a fronteira aumenta exponencialmente de acordo com o numero de objetivos dificultando a obtençao de solucoes diversas o suficiente para cobri-la totalmente. Este trabalho apresenta algumas tecnicas aplicadas para melhorar o desempenho do MOPSO ao resolver MaOPs e tornú-lo menos sensível ao aumento no número de objetivos. Primeiramente estudaram-se duas tecnicas de controle da úrea de dominância das solucoes para aumentar a pressao de seleçõo, normalmente reduzida pelo aumento no numero de objetivos. Outra tecnica estudada foi a alteracao do metodo de selecao de líderes do MOPSO com a realizaçao de um estudo empírico usando seis metodos e os melhores foram destacados. Foi estudada tambem a influencia sofrida por esses metodos devido a alteracao na técnica de controle da área de dominância, e as melhores combinações foram identificadas através de estudos empíricos. Por último um novo MOPSO e proposto usando o conceito de pontos de referencia distribuindo melhor as soluções obtidas e com isso melhorando a convergencia a fronteira real. Estudos empíricos tambem foram realizados para comparar a nova abordagem a abordagem classica. A partir dos trabalhos realizados aqui tres artigos foram publicados, sendo o primeiro um estudo sobre os metodos de selecao de líderes, o segundo propondo um novo MOPSO que usa uma tecnica de controle da area de dominancia, e o terceiro que avalia a influencia das tecnicas de controle da area de dominância no desempenho dos metodos de selecõo de líder e identifica as melhores combinacoes entre tecnica de controle da area de dominância e metodo de seleçao de líder. Em geral todos os estudos realizados apresentaram melhorias de desempenho em relacao ao algoritmo original utilizado, especialmente no contexto de muitos objetivos.
7

Grafo de conflitos : construção e aplicações em problemas de programação inteira.

Brito, Samuel Souza January 2015 (has links)
Programa de Pós-Graduação em Ciência da Computação. Departamento de Ciência da Computação, Instituto de Ciências Exatas e Biológicas, Universidade Federal de Ouro Preto. / Submitted by Oliveira Flávia (flavia@sisbin.ufop.br) on 2015-05-20T18:18:24Z No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) / Approved for entry into archive by Gracilene Carvalho (gracilene@sisbin.ufop.br) on 2015-05-20T19:03:59Z (GMT) No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) / Made available in DSpace on 2015-05-20T19:03:59Z (GMT). No. of bitstreams: 2 license_rdf: 22741 bytes, checksum: 6d485fa57a2ebb95a6dd0efb0da258db (MD5) DISSERTAÇÃO_GrafoConflitosConstrução.pdf: 1083492 bytes, checksum: 9d93fcc467dfc82a2db43315dfc47e7d (MD5) Previous issue date: 2015 / Este trabalho explora a informação estrutural de relações entre variáveis binárias em problemas de Programação Inteira por meio de grafos de conflitos. Tal estrutura possui um papel fundamental na construção de métodos exatos e heurísticos de resolução. Nesse sentido, o presente trabalho propõe e desenvolve técnicas baseadas na análise de grafos de conflitos para obtenção de soluções factíveis e limites duais fortes para problemas de Programação Inteira. Foram desenvolvidas otimizações nas técnicas de detecção de conflitos, que permitiram a construção rápida de grafos densos mediante a análise de restrições. A obtenção de limites duais fortes para programas inteiros é realizada por uma rotina desenvolvida para geração de desigualdades válidas. Essa rotina é responsável por gerar cortes de clique e ciclo ímpar e inseri-los na relaxação linear, reforçando os limites duais e acelerando a convergência para a solução ótima. Para obter soluções factíveis para programas binários foi desenvolvido um resolvedor heurístico, que utiliza as relações lógicas entre variáveis para construir uma solução inicial e melhorá-la por meio de uma busca local. A busca local executa uma cadeia de movimentos a cada iteração, que permite corrigir a infactibilidade de uma solução ou, até mesmo, saltar de uma solução factível para outra. Considerando a produção de limites duais fortes, os resultados obtidos pela rotina de geração de desigualdades desenvolvida mostraram uma convergência mais rápida em relação à rotina de separação de cortes do resolvedor COINOR Branch-and-Cut. Em relação à obtenção de factibilidade, o resolvedor heurístico foi apto a gerar soluções para um número significativo de problemas de Programação Inteira Binária, considerando tempos restritos de execução. _________________________________________________________________________________ / ABSTRACT: This work explores the structural information of relations between binary variables in Integer Programming problems using conflict graphs. Such structure has a fundamental role in the construction of exact and heuristic solving methods. In this sense, the present work proposes and develops techniques based on the analysis of conflict graphs to obtain feasible solutions and strong dual bounds for Integer Programming problems. Optimizations were developed in the conflict detection techniques that allowed the fast construction of dense graphs through the constraints analysis. The obtaining of strong dual bounds for integer programs is performed by a routine developed for the generation of valid inequalities. This routine is responsible for generating clique and odd hole cuts and insert them into the linear relaxation, strengthening the dual bounds and accelerating the convergence to the optimal solution. To obtain feasible solutions for binary programs it was developed a heuristic solver, which uses the logical relations between variables to build an initial solution and improve it through a local search. Local search performs chains of movements at each iteration, which allows to fix infeasibilities of a solution or even jump from a feasible solution to another. Considering the production of strong dual bounds, the results obtained by the developed routine for generating inequalities showed a faster convergence compared with the cut separation routine of COIN-OR Branch-and-Cut solver. Regarding the production of feasible solutions, the heuristic solver was able to generate solutions to a significant number of Integer Binary Programming problems considering restricted runtimes.
8

Método heurístico para criação de linhas de trabalho em problemas de escalonamento de pessoal /

Méllo, Fábio Gavião Avelino de. January 2014 (has links)
Orientador: Edson Luiz França Senne / Banca: Galeno José de Sena / Banca: José Roberto Dale Luche / Banca: Anibal Tavares de Azevedo / Banca: Kelly Cristina Poldi / Resumo : A presente pesquisa trata do desenvolvimento de um método de solução do problema de construção de linhas de trabalho para a área de escalonamento de pessoal. Foram investigados diversos artigos da área de programação de pessoal com o objetivo de escolher precisamente o tema da pesquisa. Este tema escolhido foi o da construção de linhas de trabalho para empresas de ônibus interurbanos no Brasil. De posse do tema escolhido, foram analisados os métodos usados para formular e resolver o problema. Como resultado foi decidido o uso de uma formulação de cobertura de conjuntos não unicusto para representar o problema em estudo e o uso de um método heurístico para resolver o mesmo. Esta heurística divide a solução do problema em duas fases. A primeira é a fase construtiva, em que o espaço de solução é montado e linhas de trabalho são investigadas e aquelas viáveis são agrupadas formando um conjunto de linhas viáveis e qualificadas. A segunda é a fase de otimização ou de busca local em que um algoritmo evolutivo, baseado em algoritmo genético, irá procurar a melhor solução dentro desse subconjunto de linhas viáveis e qualificadas obtidas na primeira fase. Estes dois procedimentos se repetem até que um critério de parada seja atingido. Testes computacionais foram realizados no sentido de demonstrar a eficácia e eficiência do método proposto. Em seguida, o problema da programação de dias de expediente e de folga, neste trabalho denominado problema de padrões de folga, é formulado e resolvido. Algumas propostas para integrar a solução do problema de criação de linhas de trabalho à do problema de padrões de folga são apresentadas e discutidas / Abstract: This thesis deals with the development of a method for solving the problem of construction of lines of work for the application area of personnel scheduling. Several articles were analyzed in order to matching precisely the subject of the research. An in-depth review of the processes used for formulating and solving such a kind of problem in the literature was conducted. As a result, it was decided to formulating the problem as a non unicost set covering problem and to use a heuristic method to solve it. The proposed heuristic is a twofold algorithm. The first is the construction phase, in which the solution space is scanned and working lines are investigated and those feasible are grouped together forming a set of feasible and qualified lines. The second phase is the optimization or local search in which an evolutionary algorithm based on genetic algorithm will search for the best solution within this set of feasible and qualified lines obtained in the first phase. These two phases are repeated until a stop criterion is reached. Computational tests were performed to demonstrate the effectiveness and efficiency of the proposed method. Then, the tour scheduling problem is addressed in the context of finding shifts of work-days and days-off scheduling. Its resolved by deterministic techniques. Some methods are then discussed on how to integrating both of the solutions of the lines of work and the tour scheduling problems / Doutor
9

Meta-heurísticas e hiper-heurísticas aplicadas ao problema de dobramento de proteínas

Fontoura, Vidal Daniel da January 2017 (has links)
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.
10

Uma abordagem baseada em hiper-heurística e otimização multi-objetivo para o teste de mutação de ordem superior

Lima, Jackson Antonio do Prado January 2017 (has links)
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.

Page generated in 0.1561 seconds