Título: Resolução de Problemas de Conversão Irreversível por Meio de Algoritmos Genéticos
Autores: Amaral, Alain A. T.; Wanner, Elizabeth F.; Santos, Vinícius F. dos
Resumo: Diferentes tipos de processos utilizam-se de grafos em sua modelagem matemática. Processos que simulam a disseminação de uma característica dentro de um conjunto de vértices de um grafo, de modo que um vértice detentor de tal característica a possuirá para sempre e passará a ser considerado um disseminador para os demais itens do conjunto são conhecidos como processos de conversão irreversível. Estes processos são ditos convergentes se, dado um conjunto de vértices inicialmente possuidores da característica para determinada simulação, todos os itens do conjunto passarem a possuir a característica após um certo período de tempo. Uma vez que encontrar o número mínimo de vértices de um grafo, que necessitam possuir a característica no inicio do processo, para que um processo de conversão irreversível seja convergente é considerado um problema NP-difícil, encontrar uma solução adequada para o problema em tempo hábil através de métodos determinísticos pode ser uma tarefa inviável para grafos com grande número de vértices. Portanto, este trabalho analisa a capacidade de resolução de tal problema por meio de algoritmos genéticos. Resultados preliminares indicam que a abordagem usada é capaz de resolver o problema de conversão irreversível de forma satisfatória.
Palavras-chave: Grafos; Algoritmos Genéticos; Processos de Conversão Irreversível; Conjuntos Convergentes; Otimização; Disseminação de Característica
Páginas: 6
Código DOI: 10.21528/CBIC2015-083
Artigo em pdf: cbic2015_submission_83.pdf
Arquivo BibTeX: cbic2015_submission_83.bib