No Problema da Cadeia de Caracteres mais Próxima (PCCP), deseja-se encontrar uma sequência de caracteres que se aproxime ao máximo, segundo uma métrica, de todas as sequências de um dado conjunto, no qual as cadeias de caracteres possuem a mesma dimensão. Neste trabalho, a ideia principal é encontrar uma heurística cujo resultado seja uma sequência centro que se assemelhe, ao máximo, a um conjunto de cadeias dado. O objetivo é minimizar a distância máxima desta cadeia de caracteres às demais cadeias do conjunto.

Com os experimentos realizados para o desenvolvimento deste projeto, podemos concluir que os algoritmos IGS e BRKGA para o problema da Cadeia de Caracteres Mais Próxima demonstram ser eficientes na resolução do problema em questão.

A heurística BRKGA consiste em um Algoritmo Genético Baseado em Chaves Aleatórias para a resolução de problemas de otimização combinatória. Nesse Algorítmo não existe mutação das cadeias de caracteres, pois a cada geração, um número fixo de cromossos mutantes é inserido na população.

Já a heurística IGS parte de uma solução inicial para um problema de otimização combinatória, para, em seguida, fazer buscas locais e melhorar diversas vezes a solução inicial encontrada através de um determinado número de iterações.

Em relação a heurística IGS-PCCP, observamos que os experimentos realizados com perturbação de 40% obteve os melhores resultados, enquanto os de 3% obteve os piores. Já a heurística BRKGA-PCCP apresentou os melhores resultados com população de 1000 indivíduos e os piores com população de 100 indivíduos.

Concluiu-se que a heurística BRKGA-PCCP se mostrou mais eficiente, obtendo valores próximos do ótimo em um tempo de processamento reduzido.