techreport.bib

@techreport{TR-IC-PFG-23-61,
    number = {IC-PFG-23-61},
    author = {Leonardo de Sousa Rodrigues
        and Tiago de Paula Alves
        and Gabriel Siqueira
        and Zanoni Dias},
    title = {{Heurísticas para Partição Comum Mínima de Strings}},
    year = {2023},
    month = {December},
    institution = {Instituto de Computação, Universidade Estadual de Campinas},
    note = {In Portuguese, 18 pages.
    \par\selectlanguage{brazil}\textbf{Resumo}
        O problema de Partição Comum Mínima de Strings (MCSP) é utilizado na
        comparação de strings com aplicações em biologia computacional. Boas
        heurísticas têm grande valor para esse problema, já que ele foi provado
        ser NP-Difícil. Além de apresentar implementações para heurísticas
        conhecidas da literatura, desenvolvemos uma representação por grafo
        eficiente para instâncias do MCSP, reduzindo-o a um problema de
        permutação e permitindo a aplicação de algoritmos de otimização para
        buscar soluções. O \textit{Particle Swarm Optimization} (PSO) foi
        adaptado para esta representação e foi capaz de não só melhorar
        significativamente o resultado das outras heurísticas utilizadas,
        mas também encontrar boas soluções de forma independente, mostrando-se
        uma meta-heurística promissora, principalmente para instâncias com
        poucas repetições de caracteres. Esse trabalho sugere a utilização da
        representação por grafo com outros métodos de otimização para o MCSP.
    }
}