Memetic Teaching–Learning-Based Optimization algorithms for large graph coloring problems

Dokeroglu T., Sevinc E.

Engineering Applications of Artificial Intelligence, vol.102, 2021 (SCI-Expanded) identifier

  • Publication Type: Article / Article
  • Volume: 102
  • Publication Date: 2021
  • Doi Number: 10.1016/j.engappai.2021.104282
  • Journal Name: Engineering Applications of Artificial Intelligence
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus, Academic Search Premier, Aerospace Database, Applied Science & Technology Source, Communication Abstracts, Computer & Applied Sciences, INSPEC, Metadex, Civil Engineering Abstracts
  • Keywords: Graph coloring, Memetic, Optimization, Parallel, TabuCol, TLBO
  • TED University Affiliated: No


The Graph Coloring Problem (GCP) can be simply defined as partitioning the vertices of a graph into independent sets while minimizing the number of colors used. So far, many approaches have been implemented to solve the GCP. However, researchers are still trying to solve this important NP-Hard problem much faster and with better results for large graphs. The Teaching-Learning-Based Optimization (TLBO) metaheuristic is a recent approach that has attracted the attention of many researchers due to its algorithm-specific parameterless concept and high performance. In this study, we propose a new memetic TLBO algorithm (TLBO-Color) combined with a robust tabu search algorithm to solve the GCP. A scalable parallel version of TLBO-Color is also developed for painting 43 benchmark DIMACS graphs with thousands of vertices and millions of edges. The optimization times of the TLBO-Color algorithm are very practical and the best results (for 33 of the graphs) or solutions with a few more colors are reported. On average, there are only 1.77% more colors compared to the best solutions. The obtained results confirm that the proposed algorithm is competitive with the state-of-the-art algorithms in the literature.