Genetic algorithms are an evolutionary technique that use crossover and mutation operators to solve optimization problems using a survival of the fittest idea. They have been used successfully in a variety of different problems, including the traveling salesman problem. In the traveling salesman problem we wish to find a tour of all nodes in a weighted graph so that the total weight is minimized. The traveling salesman problem is NP-hard but has many real world applications so a good solution would be useful. Many different crossover and mutation operators have been devised for the traveling salesman problem and each give different results. We compare these results and find that operators that use heuristic information or a matrix representation of the graph give the best results.

No description available.

No desenvolvimento de software, a qualidade do produto está diretamente relacionada à qualidade do processo de desenvolvimento. Diante disso, atividades de Verificação, Validação & Teste (VV&T) realizadas por meio de métodos, técnicas e ferramentas são de extrema necessidade para o aumento da produtividade, qualidade e diminuição de custos no desenvolvimento de software. Do mesmo modo, técnicas e critérios contribuem para a produtividade das atividades de teste. Um ponto crucial para o teste de software é sua automatização, tornando as atividades mais confiáveis e diminuindo significativamente os custos de desenvolvimento. Na automatização dos testes, os oráculos são essenciais, representando um mecanismo (programa, processo ou dados) que indica se a saída obtida para um caso de teste está correta. Este trabalho de mestrado utiliza a ideia de mutação para criar implementações alternativas de oráculos de teste e, assim, avaliar a sua qualidade. O teste de mutação se refere à criação de versões do sistema em desenvolvimento com pequenas alterações sintáticas de código. A mutação possui alta eficácia na detecção de defeitos e é bastante flexível na sua aplicação, podendo ser utilizada em diversos tipos de artefatos. Adicionalmente, este trabalho propõe operadores de mutação específicos para oráculos, implementa uma ferramenta de apoio à utilização desses operadores para oráculos e também descreve um estudo empírico dos operadores, destacando benefícios e desafios associados ao seu uso. / In software development, product quality is directly related to the quality of the development process. Therefore, activities of Verification, Validation & Testing (VV&T) performed by methods, techniques and tools are urgently required to increase productivity, quality and cost reduction in software development. Similarly, testing technique and criteria contribute to the productivity of test activities. A crucial point for the software testing automation is making the most reliable activities and significantly reducing development costs. Regarding software testing automation, test oracles are essential, representing an mechanism (program, process or data) to indicate whether the actual output for a given test case is correct. This masters thesis aims to explore concepts of mutation testing to create alternative implementations of the oracle procedure and thus assess their quality. Mutation testing refers to the creation of system development versions with minor syntactic code changes. It has high efficiency on defects detecting and it is very flexible in its application and it is being used in various types of artifacts. This work also proposes specific mutation operators for oracles, implements an useful support tool for using these oracle mutation operators and conducts an empirical study of operators, highlighting benefits and challenges associated with their use.

No desenvolvimento de software, a qualidade do produto está diretamente relacionada à qualidade do processo de desenvolvimento. Diante disso, atividades de Verificação, Validação & Teste (VV&T) realizadas por meio de métodos, técnicas e ferramentas são de extrema necessidade para o aumento da produtividade, qualidade e diminuição de custos no desenvolvimento de software. Do mesmo modo, técnicas e critérios contribuem para a produtividade das atividades de teste. Um ponto crucial para o teste de software é sua automatização, tornando as atividades mais confiáveis e diminuindo significativamente os custos de desenvolvimento. Na automatização dos testes, os oráculos são essenciais, representando um mecanismo (programa, processo ou dados) que indica se a saída obtida para um caso de teste está correta. Este trabalho de mestrado utiliza a ideia de mutação para criar implementações alternativas de oráculos de teste e, assim, avaliar a sua qualidade. O teste de mutação se refere à criação de versões do sistema em desenvolvimento com pequenas alterações sintáticas de código. A mutação possui alta eficácia na detecção de defeitos e é bastante flexível na sua aplicação, podendo ser utilizada em diversos tipos de artefatos. Adicionalmente, este trabalho propõe operadores de mutação específicos para oráculos, implementa uma ferramenta de apoio à utilização desses operadores para oráculos e também descreve um estudo empírico dos operadores, destacando benefícios e desafios associados ao seu uso. / In software development, product quality is directly related to the quality of the development process. Therefore, activities of Verification, Validation & Testing (VV&T) performed by methods, techniques and tools are urgently required to increase productivity, quality and cost reduction in software development. Similarly, testing technique and criteria contribute to the productivity of test activities. A crucial point for the software testing automation is making the most reliable activities and significantly reducing development costs. Regarding software testing automation, test oracles are essential, representing an mechanism (program, process or data) to indicate whether the actual output for a given test case is correct. This masters thesis aims to explore concepts of mutation testing to create alternative implementations of the oracle procedure and thus assess their quality. Mutation testing refers to the creation of system development versions with minor syntactic code changes. It has high efficiency on defects detecting and it is very flexible in its application and it is being used in various types of artifacts. This work also proposes specific mutation operators for oracles, implements an useful support tool for using these oracle mutation operators and conducts an empirical study of operators, highlighting benefits and challenges associated with their use.