A deep learning guided memetic framework for graph coloring problems
Given an undirected graph $G=(V,E)$ with a set of vertices $V$ and a set of edges $E$, a graph coloring problem involves finding a partition of the vertices into different independent sets. In this paper we present a new framework that combines a deep neural network with the best tools of classical metaheuristics for graph coloring. The proposed method is evaluated on two popular graph coloring problems (vertex coloring and weighted coloring). Computational experiments on well-known benchmark graphs show that the proposed approach is able to obtain highly competitive results for both problems. A study of the contribution of deep learning in the method highlights that it is possible to learn relevant patterns useful to obtain better solutions to graph coloring problems.
Code (0)
등록된 구현이 없습니다.
Tasks
Deep LearningSimilar Papers 제목 키워드 기반
Variations on Memetic Algorithms for Graph Coloring Problems
Graph vertex coloring with a given number of colors is a well-known and much-studied NP-complete problem.The most effective methods to solve this problem are proved to be hybrid algorithms such as memetic algorithms or q…
DiversityPopulation-based Gradient Descent Weight Learning for Graph Coloring Problems
Graph coloring involves assigning colors to the vertices of a graph such that two vertices linked by an edge receive different colors. Graph coloring problems are general models that are very useful to formulate many rel…
Randomized Memetic Artificial Bee Colony Algorithm
Artificial Bee Colony (ABC) optimization algorithm is one of the recent population based probabilistic approach developed for global optimization. ABC is simple and has been showed significant improvement over other Natu…
global-optimizationJCOL: A Java package for solving the graph coloring problem
The graph coloring problem aims at assigning colors to the nodes of a graph such that no two connected nodes have the same color. The graph coloring problem is NP-complete and one of the harder problems to solve. Here we…
Embedding models through the lens of Stable Coloring
Embedding-based approaches find the semantic meaning of tokens in structured data such as natural language, graphs, and even images. To a great degree, these approaches have developed independently in different domains. …
Denoising