Submitted by JÚLIO HEBER SILVA (julioheber@yahoo.com.br) on 2017-09-13T17:19:44Z No. of bitstreams: 2 Dissertação - Vinícius Paulo Lopes de Oliveira - 2017.pdf: 2066886 bytes, checksum: c610d8e21e23795d1cea6eeca17b5e5e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2017-09-19T13:58:48Z (GMT) No. of bitstreams: 2 Dissertação - Vinícius Paulo Lopes de Oliveira - 2017.pdf: 2066886 bytes, checksum: c610d8e21e23795d1cea6eeca17b5e5e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) / Made available in DSpace on 2017-09-19T13:58:48Z (GMT). No. of bitstreams: 2 Dissertação - Vinícius Paulo Lopes de Oliveira - 2017.pdf: 2066886 bytes, checksum: c610d8e21e23795d1cea6eeca17b5e5e (MD5) license_rdf: 0 bytes, checksum: d41d8cd98f00b204e9800998ecf8427e (MD5) Previous issue date: 2017-08-14 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / Maintenance and software repair are responsible for most of the cost of a software in the course of its life. Software repair through genetic evolution may repair errors and improve software, reducing its high cost. GenProg is a technique that uses this approach and through patches evolution it is capable to fix errors in large and small softwares. A patch composed by low-granularity operations compromise the manipulation of these operations. These operations consist of three subspaces: operation, location of application of the operation and what the operation will apply at the location of the fault (operator, fault and fix, respectively). The recombination and mutation operators applied to a low granulation representation limits the ability of the technique to navigate in search space efficiently. It is proposed the reformulation of the representation, in order to allow greater search capability. Theoretical analysis of the representation showed that the new representation has a greater locality than the original one. Through experimentation, validation and genotypic analysis it is shown that the proposed changes have led to a better performance with respect to the original operators and parameters in terms of efficiency, in the first experiments the operator UnifSingle with memorization was 48.88% more effective than the Original operator and then the operator OPSingle_V2 was 26% more effective than the operator UnifSingle with memorization. Some characteristics of these cross-operators were observed through a genotype distance analysis and their influence on the automatic software reapair problem. The proposed mutation operator shown superior results if compared to original. Combination between operator UniSingle with memorization showed the best efficacy among all combinations of operators and parameters (28.29% superior to the best result of the original GenProg). / Manutenção e reparo de software é responsável pela maior parte do custo de um software no decorrer de sua vida. O reparo de software por meio de evolução genética pode reparar erros e/ou melhorar softwares, diminuindo seu alto custo. GenProg é uma técnica em desenvolvimento que utiliza esta abordagem e por meio de evolução de patches é capaz de reparar erros em grandes e pequenos softwares. Um patch é composto por operações de edições de baixa granularidade o que compromete a separação e edição dessas operações. Essas operações são formadas por três subespaços: operação, local da aplicação da operação e o que a operação irá aplicar no local da falha (operator, fault, fix, respectivamente). Os operadores de recombinação e mutação aplicados às representações de baixa granularidade limita a habilidade da técnica de navegar no espaço de busca de forma eficiente. É proposto neste estudo, a reformulação da representação, do operador de cruzamento e mutação a fim de permitir uma maior capacidade de busca. Análises teóricas da representação demonstraram que a nova representação possui localidade maior que a original. Por meio de experimentações, validações e análises genotípicas é mostrado que as mudanças propostas levaram a uma melhoria em relação aos operadores e parâmetros originais em termos de eficácia, sendo que nos experimentos iniciais o operador UnifSingle com memorização apresentou eficácia 45,88% superior ao melhor caso do operador Original e em seguida o operador posteriormente proposto OPSingle_V2 apresentou eficácia 26% superior ao UnifSingle com memorização. Foram observadas algumas características desses operadores de cruzamento por meio de uma análise por distância genotípica e suas influências no problema de reparo automatizado de software. O operador de mutação proposto apresentou resultados superiores ao operador de mutação original e combinado com operador UnifSingle com memorização, apresentou a melhor eficácia entre todas as combinações de operadores e parâmetros.

Submitted by Nadir Basilio (nadirsb@uninove.br) on 2016-06-01T14:43:08Z No. of bitstreams: 1 Valdemar Modolo Junior.pdf: 2802590 bytes, checksum: f3956818acd10efc3244abc007294827 (MD5) / Made available in DSpace on 2016-06-01T14:43:08Z (GMT). No. of bitstreams: 1 Valdemar Modolo Junior.pdf: 2802590 bytes, checksum: f3956818acd10efc3244abc007294827 (MD5) Previous issue date: 2015-06-10 / Among the optimization methods, the Genetic Algorithm (GA) has been producing good results in problems with high order of complexity, such as, for example, the production scheduling problem in job shop environment. The production sequencing problems must be translated into a mathematical representation, so that the AG can act. In this process we came up a problematic, the choice between different ways to represent the solution as some representations have limitations, how to present not feasible and / or redundant solutions. Therefore the aim of this study is to conduct a comparative study between different representations of the solution in the AG in production sequencing problems in job shop environments. Two representations of the solution were analyzed, the priority lists based and based on order of operations and compared with a binary representation, in the context of sequencing problem set defined by Lawrence (1984). The results were evaluated according to the total processing time (makespan), the computational cost and the proportion of generated feasible solutions. It was noticed that the representation of the solution based on order of operations, which produced 100% of feasible solutions, was the one that showed the best results although no convergence to the best known solution to every problem. / Dentre os métodos de otimização, o Algoritmo Genético (AG) vem produzindo bons resultados em problemas com ordem de complexidade elevada, como é o caso, por exemplo, do problema de sequenciamento da produção em ambiente job shop. Os problemas de sequenciamento da produção devem ser traduzidos para uma representação matemática, para que o AG possa atuar. Neste processo surgi uma problemática, a escolha entre as diferentes formas de se representar a solução visto que algumas representações apresentam limitações, como apresentar soluções não factíveis e/ou redundantes. Portanto o objetivo deste trabalho é realizar um estudo comparativo entre diferentes representações da solução no AG em problemas de sequenciamento da produção em ambientes job shop. Duas representações da solução foram analisadas, a baseada em listas de prioridades e a baseada em ordem de operações e comparada com uma representação binária, no contexto do conjunto de problemas de sequenciamento definidos por Lawrence (1984). Os resultados foram avaliados em função do tempo total de processamento (makespan), do custo computacional e da proporção de soluções factíveis geradas. Percebeu-se que, a representação da solução baseada em ordem de operações, a qual produziu 100% de soluções factíveis, foi a que mostrou os melhores resultados apesar de não apresentar convergência para a melhor solução conhecida em todos os problemas.