A Distribution Evolutionary Algorithm for the Graph Coloring Problem

• URL: http://arxiv.org/abs/2203.15162v3
• Date: Tue, 2 May 2023 13:50:15 GMT
• Title: A Distribution Evolutionary Algorithm for the Graph Coloring Problem
• Authors: Yongjian Xu and Huabin Cheng and Ning Xu and Yu Chen and Chengwang Xie
• Abstract summary: A distribution evolutionary algorithm based on a population of probability model (DEA-PPM) is developed to address the problem of graph coloring. DEA-PPM employs a distribution population based on a novel probability model, and an exploration strategy is introduced to search the distribution space. Numerical results demonstrate that the DEA-PPM of small population size is competitive to the state-of-the-art metaheuristics.
• Score: 9.258122432690556
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Graph coloring is a challenging combinatorial optimization problem with a wide range of applications. In this paper, a distribution evolutionary algorithm based on a population of probability model (DEA-PPM) is developed to address it efficiently. Unlike existing estimation of distribution algorithms where a probability model is updated by generated solutions, DEA-PPM employs a distribution population based on a novel probability model, and an orthogonal exploration strategy is introduced to search the distribution space with the assistance of an refinement strategy. By sampling the distribution population, efficient search in the solution space is realized based on a tabu search process. Meanwhile, DEA-PPM introduces an iterative vertex removal strategy to improve the efficiency of $k$-coloring, and an inherited initialization strategy is implemented to address the chromatic problem well. The cooperative evolution of the distribution population and the solution population leads to a good balance between exploration and exploitation. Numerical results demonstrate that the DEA-PPM of small population size is competitive to the state-of-the-art metaheuristics.utes to its competitiveness to the state-of-the-art metaheuristics.

Related papers

• Distributed Markov Chain Monte Carlo Sampling based on the Alternating Direction Method of Multipliers [143.6249073384419]
  In this paper, we propose a distributed sampling scheme based on the alternating direction method of multipliers. We provide both theoretical guarantees of our algorithm's convergence and experimental evidence of its superiority to the state-of-the-art. In simulation, we deploy our algorithm on linear and logistic regression tasks and illustrate its fast convergence compared to existing gradient-based methods.
  arXiv  Detail & Related papers  (2024-01-29T02:08:40Z)
• Ensemble-Based Annealed Importance Sampling [12.59962335240209]
  We propose an ensemble-based version of Annealed Importance Sampling (AIS) We take advantage of the interaction within the ensemble to encourage the exploration of undiscovered modes. We discuss how the proposed algorithm can be implemented and derive a partial differential equation governing the evolution of the ensemble.
  arXiv  Detail & Related papers  (2024-01-28T12:47:39Z)
• Strategic Distribution Shift of Interacting Agents via Coupled Gradient Flows [6.064702468344376]
  We propose a novel framework for analyzing the dynamics of distribution shift in real-world systems. We show that our approach captures well-documented forms of distribution shifts like polarization and disparate impacts that simpler models cannot capture.
  arXiv  Detail & Related papers  (2023-07-03T17:18:50Z)
• Provably Efficient UCB-type Algorithms For Learning Predictive State Representations [55.00359893021461]
  The sequential decision-making problem is statistically learnable if it admits a low-rank structure modeled by predictive state representations (PSRs) This paper proposes the first known UCB-type approach for PSRs, featuring a novel bonus term that upper bounds the total variation distance between the estimated and true models. In contrast to existing approaches for PSRs, our UCB-type algorithms enjoy computational tractability, last-iterate guaranteed near-optimal policy, and guaranteed model accuracy.
  arXiv  Detail & Related papers  (2023-07-01T18:35:21Z)
• Scalable Multiple Patterning Layout Decomposition Implemented by a Distribution Evolutionary Algorithm [11.366935475887239]
  We model the layout decomposition of MPL as a generalized graph coloring problem. DEA-PPM can strike a balance between decomposition results and running time.
  arXiv  Detail & Related papers  (2023-04-09T10:23:30Z)
• End-to-End Pareto Set Prediction with Graph Neural Networks for Multi-objective Facility Location [10.130342722193204]
  Facility location problems (FLPs) are a typical class of NP-hard optimization problems, which are widely seen in the supply chain and logistics. In this paper, we consider the multi-objective facility location problem (MO-FLP) that simultaneously minimizes the overall cost and maximizes the system reliability. Two graph neural networks are constructed to learn the implicit graph representation on nodes and edges.
  arXiv  Detail & Related papers  (2022-10-27T07:15:55Z)
• Distributed Evolution Strategies for Black-box Stochastic Optimization [42.90600124972943]
  This work concerns the evolutionary approaches to distributed black-box optimization. Each worker can individually solve an approximation of the problem with algorithms. We propose two alternative simulation schemes which significantly improve robustness of problems.
  arXiv  Detail & Related papers  (2022-04-09T11:18:41Z)
• Score-based Generative Modeling of Graphs via the System of Stochastic Differential Equations [57.15855198512551]
  We propose a novel score-based generative model for graphs with a continuous-time framework. We show that our method is able to generate molecules that lie close to the training distribution yet do not violate the chemical valency rule.
  arXiv  Detail & Related papers  (2022-02-05T08:21:04Z)
• Implicit Distributional Reinforcement Learning [61.166030238490634]
  implicit distributional actor-critic (IDAC) built on two deep generator networks (DGNs) Semi-implicit actor (SIA) powered by a flexible policy distribution. We observe IDAC outperforms state-of-the-art algorithms on representative OpenAI Gym environments.
  arXiv  Detail & Related papers  (2020-07-13T02:52:18Z)
• MineReduce: an approach based on data mining for problem size reduction [58.720142291102135]
  This paper presents an approach named MineReduce, which uses mined patterns to perform problem size reduction. We present an application of MineReduce to improve a for the heterogeneous fleet vehicle routing problem.
  arXiv  Detail & Related papers  (2020-05-15T08:49:50Z)
• Decentralized MCTS via Learned Teammate Models [89.24858306636816]
  We present a trainable online decentralized planning algorithm based on decentralized Monte Carlo Tree Search. We show that deep learning and convolutional neural networks can be employed to produce accurate policy approximators.
  arXiv  Detail & Related papers  (2020-03-19T13:10:20Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.