1. Universidade Federal da Bahia
  2. Instituto de Computação (IC)
  3. Programa de Pós-Graduação em Ciência da Computação (PGCOMP)
  4. Dissertação (PGCOMP)
Use este identificador para citar ou linkar para este item: https://repositorio.ufba.br/handle/ri/39322
Registro completo de metadados
Campo DCValorIdioma
dc.creatorSilva, Mateus Carvalho-
dc.date.accessioned2024-04-26T21:51:54Z-
dc.date.available2024-04-26-
dc.date.available2024-04-26T21:51:54Z-
dc.date.issued2023-12-13-
dc.identifier.citationSILVA, Mateus Carvalho da. Application of biased random-key genetic algorithm and formulations for the Grundy coloring problem and the connected Grundy coloring problem. 2023. 49 f. Dissertação (Mestrado em Ciência da Computação) Instituto de Computação, Universidade Federal da Bahia, Salvador, BA, 2023.pt_BR
dc.identifier.urihttps://repositorio.ufba.br/handle/ri/39322-
dc.description.abstractDado um grafo G, seu número de Grundy Γ(G) define o comportamento de pior caso para a conhecida e amplamente utilizada heurística de coloração gulosa first-fit. Mais especificamente, Γ(G) é o maior k para o qual uma k-coloração pode ser obtida com a heurística first-fit. O número de Grundy conexo Γc(G) fornece o comportamento do pior caso para a heurística de coloração first-fit conexa, ou seja, aquela em que cada vértice a ser colorido, exceto o primeiro, é adicionado adjacente a um vértice já colorido. Ambos os problemas são NP-difíceis. Nesta dissertação, apresentamos abordagens heurísticas e exatas para o problema da coloração de Grundy e o problema de coloração de Grundy conexo, que são problemas de otimização consistindo na obtenção do número de Grundy e do número de Grundy conexo, respectivamente. Nesse estudo é proposto o uso do algoritmo genético de chaves aleatórias viesado (Biased random-key genetic algorithm - BRKGA) e do uso de formulações de programação inteira usando uma abordagem mais tradicional (padrão) e uma por representativos. Também é proposto um novo limite superior combinatório que é válido para ambos os problemas e um algoritmo usando programação dinâmica para o seu cálculo. Os experimentos computacionais mostram que o novo limite superior pode melhorar o limite para vários casos em relação a um limite combinatório bem estabelecido disponível na literatura. Os resultados também evidenciam que a formulação por representativos tem um desempenho geral superior que a formulação padrão, alcançando melhores resultados para as instâncias mais densas, enquanto esta última tem melhor desempenho para as mais esparsas para o problema dos números de Grundy. Contudo mostramos que este tipo de formulações com programação inteira são computacionalmente impraticáveis para a versão conexa. Além disso, o BRKGA pode encontrar soluções de alta qualidade para ambos os problemas e pode ser usado com confiança em grandes instâncias onde as formulações falham para o problema da coloração de Grundypt_BR
dc.description.sponsorshipCoordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES).pt_BR
dc.languageengpt_BR
dc.publisherUniversidade Federal da Bahiapt_BR
dc.rightsAcesso Abertopt_BR
dc.subjectOtimização combinatóriapt_BR
dc.subjectColoração de grafospt_BR
dc.subjectNúmero de Grundypt_BR
dc.subjectBRKGApt_BR
dc.subjectAnálise de pior casopt_BR
dc.subject.otherCombinatorial optimizationpt_BR
dc.subject.otherGraph coloringpt_BR
dc.subject.otherGrundy numberpt_BR
dc.subject.otherBRKGApt_BR
dc.subject.otherWorst-case analysispt_BR
dc.titleApplication of biased random-key genetic algorithm and formulations for the Grundy coloring problem and the connected Grundy coloring problempt_BR
dc.title.alternativeAplicação do algoritmo genético de chaves aleatórias viesado e formulações para o problema da coloração de Grundy e o problema da coloração conexa de Grundypt_BR
dc.typeDissertaçãopt_BR
dc.publisher.programPrograma de Pós-Graduação em Ciência da Computação (PGCOMP) pt_BR
dc.publisher.initialsUFBApt_BR
dc.publisher.countryBrasilpt_BR
dc.subject.cnpqCNPQ::CIENCIAS EXATAS E DA TERRA::CIENCIA DA COMPUTACAOpt_BR
dc.contributor.advisor1Melo, Rafael Augusto de-
dc.contributor.advisor1Latteshttp://lattes.cnpq.br/4117373032501782pt_BR
dc.contributor.advisor-co1Santos, Márcio Costa-
dc.contributor.advisor-co1Latteshttp://lattes.cnpq.br/4258661430014987pt_BR
dc.contributor.referee1Melo, Rafael Augusto-
dc.contributor.referee1Latteshttp://lattes.cnpq.br/4117373032501782pt_BR
dc.contributor.referee2Silva, Pedro Henrique Gonzáles-
dc.contributor.referee3Durão, Frederico Araújo-
dc.contributor.referee3Latteshttp://lattes.cnpq.br/6271096128174325pt_BR
dc.contributor.referee4Resende, Maurício Guilherme de Carvalho-
dc.contributor.referee4Latteshttp://lattes.cnpq.br/6235837317096398pt_BR
dc.creator.Latteshttp://lattes.cnpq.br/8638009209427420pt_BR
dc.description.resumoGiven a graph G, its Grundy number Γ(G) defines the worst-case behavior for the wellknown and widely used first-fit greedy coloring heuristic. Specifically, Γ(G) is the largest k for which a k-coloring can be obtained with the first-fit heuristic. The connected Grundy number Γc(G) gives the worst-case behavior for the connected first-fit coloring heuristic, that is, one in which each vertex to be colored, except the first, is added adjacent to an already colored vertex. Both problems are NP-hard. In this master’s thesis, we present heuristic and exact approaches to the Grundy coloring problem and the connected Grundy coloring problem, which are optimization problems consisting of obtaining the Grundy number and the connected Grundy number, respectively. This study proposes the use of a algorithm Biased Random-Key Genetic Algorithm (BRKGA) and the use of integer programming formulations using a more traditional (standard) approach and a representative one. A new combinatorial upper bound is also proposed that is valid for both problems and an algorithm using dynamic programming for its calculation. The computational experiments show that the new upper bound can improve over a well-established combinatorial bound available in the literature for several instances. The results also evidence that the formulation by representatives has an overall superior performance than the standard formulation, achieving better results for the denser instances, while the latter performs better for the sparser ones to the Grundy coloring problem. However, we show that these types of integer programming formulations are computationally impractical for the connected version. Furthermore, the BRKGA can find high-quality solutions for both problems and can be used with confidence in large instances where the formulations fail for the Grundy coloring problem.pt_BR
dc.publisher.departmentInstituto de Computação - ICpt_BR
dc.type.degreeMestrado Acadêmicopt_BR
Aparece nas coleções:Dissertação (PGCOMP)

Arquivos associados a este item:
Arquivo Descrição TamanhoFormato 
MSC_Mateus_Carvalho_da_Silva.pdfDissertação de Mestrado de Mateus Carvalho da Silva.1,21 MBAdobe PDFVisualizar/Abrir
Mostrar registro simples do item Visualizar estatísticas


Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.