Aplicação de metaheurísticas na solução do problema da cadeia de caracteres mais próxima.

APLICAÇÃO DE METAHEURÍSTICAS NA SOLUÇÃO DO PROBLEMA DA CADEIA DE CARACTERES MAIS PRÓXIMA.
Jeanderson C. de Souza and Sérgio R. de Souza
Centro Federal de Educação Tecnológica de Minas Gerais, Av. Amazonas, 7675 - Nova GameleiraCEP 30510-000 - Belo Horizonte, MG, Brasil, http:// www.portais.atrio.scire.coppe.ufrj.br/ cefet-mg-ppgmmc/

Keywords: Combinatorial Optimization, CSP, Strings, Hamming. Abstract. This paper presents a study of the Closest String Problem (CSP). The problem is to find a string that is the closest of a group of pre-set string (instance), in other words, minimize the Hamming distance between an initial solution (string) in relation to all strings of the group simultaneously through successive modifications of this. This distance is calculated as the sum of one unit for each difference found, character by character, between the current solution and each of the strings of the given set (instance). Minimize the Hamming distance is a combinatorial optimization problem, in the literature classified as NP-hard. This article shows and discusses the results obtained by a hybrid metaheuristic, based on Greedy Randomized Adaptive Search Procedure (GRASP), in the construction phase, with a Genetic Algorithm (GA) applied to instances that represent DNA sequences of 300, 400, 500 , 600, 700 and 800 characters in groups of 10, 15, 20, 25 and 30 strings. The results show the efficiency of heuristic methods, especially in relation to the execution time when compared to exact methods.

Palavras chave: Otimização Combinatória, PCCP, Cadeias de Caracteres, Hamming. Resumo. O presente trabalho traz um estudo do Problema da Cadeias de Caractere Mais Próxima (PCCP), em inglês Closest String Problem (CSP). O problema consiste em encontrar uma cadeia de caracteres que se aproxime ao máximo de um grupo de cadeias pré estabelecidas (instância), ou seja, minimizar a distância de Hamming entre uma cadeia inicial em relação a todas as outras do grupo, simultaneamente,