Towards Geometry-Aware Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization

• URL: http://arxiv.org/abs/2405.08604v2
• Date: Fri, 24 May 2024 03:36:10 GMT
• Title: Towards Geometry-Aware Pareto Set Learning for Neural Multi-Objective Combinatorial Optimization
• Authors: Yongfan Lu, Zixiang Di, Bingdong Li, Shengcai Liu, Hong Qian, Peng Yang, Ke Tang, Aimin Zhou,
• Abstract summary: Multi-objective diversity optimization (MOCO) problems are prevalent in various real-world applications. Most existing neural MOCO methods rely on problem to transform an MOCO problem into a series of singe-objective diversity enhancement (SOCO) problems. These methods often approximate partial regions of the front because of ambiguous and time-consuming precise hypervolume calculation.
• Score: 19.631213689157995
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Multi-objective combinatorial optimization (MOCO) problems are prevalent in various real-world applications. Most existing neural MOCO methods rely on problem decomposition to transform an MOCO problem into a series of singe-objective combinatorial optimization (SOCO) problems. However, these methods often approximate partial regions of the Pareto front and spend excessive time on diversity enhancement because of ambiguous decomposition and time-consuming precise hypervolume calculation. To address these limitations, we design a Geometry-Aware Pareto set Learning algorithm named GAPL, which provides a novel geometric perspective for neural MOCO via a Pareto attention model based on hypervolume expectation maximization. In addition, we propose a hypervolume residual update strategy to enable the Pareto attention model to capture both local and non-local information of the Pareto set/front. We also design a novel inference approach to further improve quality of the solution set and speed up hypervolume calculation. Experimental results on three classic MOCO problems demonstrate that our GAPL outperforms several state-of-the-art baselines via superior decomposition and efficient diversity enhancement.

Related papers

• Towards Efficient Pareto Set Approximation via Mixture of Experts Based Model Fusion [53.33473557562837]
  Solving multi-objective optimization problems for large deep neural networks is a challenging task due to the complexity of the loss landscape and the expensive computational cost. We propose a practical and scalable approach to solve this problem via mixture of experts (MoE) based model fusion. By ensembling the weights of specialized single-task models, the MoE module can effectively capture the trade-offs between multiple objectives.
  arXiv  Detail & Related papers  (2024-06-14T07:16:18Z)
• Expensive Multi-Objective Bayesian Optimization Based on Diffusion Models [17.19004913553654]
  Multi-objective Bayesian optimization (MOBO) has shown promising performance on various expensive multi-objective optimization problems (EMOPs) We propose a novel Composite Diffusion Model based Pareto Set Learning algorithm, namely CDM-PSL, for expensive MOBO. Our proposed algorithm attains superior performance compared with various state-of-the-art MOBO algorithms.
  arXiv  Detail & Related papers  (2024-05-14T14:55:57Z)
• UCB-driven Utility Function Search for Multi-objective Reinforcement Learning [75.11267478778295]
  In Multi-objective Reinforcement Learning (MORL) agents are tasked with optimising decision-making behaviours. We focus on the case of linear utility functions parameterised by weight vectors w. We introduce a method based on Upper Confidence Bound to efficiently search for the most promising weight vectors during different stages of the learning process.
  arXiv  Detail & Related papers  (2024-05-01T09:34:42Z)
• Neural Multi-Objective Combinatorial Optimization with Diversity Enhancement [33.28756549307025]
  We propose a novel neural with diversity enhancement (NHDE) for multi-objective optimization (MOCO) problems. We show that our NHDE is able to generate a Pareto front with higher diversity, thereby achieving superior overall performance. Our NHDE is generic and can be applied to different neural methods for MOCO.
  arXiv  Detail & Related papers  (2023-10-22T08:50:57Z)
• A Pareto-optimal compositional energy-based model for sampling and optimization of protein sequences [55.25331349436895]
  Deep generative models have emerged as a popular machine learning-based approach for inverse problems in the life sciences. These problems often require sampling new designs that satisfy multiple properties of interest in addition to learning the data distribution.
  arXiv  Detail & Related papers  (2022-10-19T19:04:45Z)
• Pareto Set Learning for Neural Multi-objective Combinatorial Optimization [6.091096843566857]
  Multiobjective optimization (MOCO) problems can be found in many real-world applications. We develop a learning-based approach to approximate the whole Pareto set for a given MOCO problem without further search procedure. Our proposed method significantly outperforms some other methods on the multiobjective traveling salesman problem, multiconditioned vehicle routing problem and multi knapsack problem in terms of solution quality, speed, and model efficiency.
  arXiv  Detail & Related papers  (2022-03-29T09:26:22Z)
• Efficient Model-Based Multi-Agent Mean-Field Reinforcement Learning [89.31889875864599]
  We propose an efficient model-based reinforcement learning algorithm for learning in multi-agent systems. Our main theoretical contributions are the first general regret bounds for model-based reinforcement learning for MFC. We provide a practical parametrization of the core optimization problem.
  arXiv  Detail & Related papers  (2021-07-08T18:01:02Z)
• Reinforcement Learning for Adaptive Mesh Refinement [63.7867809197671]
  We propose a novel formulation of AMR as a Markov decision process and apply deep reinforcement learning to train refinement policies directly from simulation. The model sizes of these policy architectures are independent of the mesh size and hence scale to arbitrarily large and complex simulations.
  arXiv  Detail & Related papers  (2021-03-01T22:55:48Z)
• Application of Compromising Evolution in Multi-objective Image Error Concealment [0.0]
  The Compromising Evolution Method is proposed to modify the Simple Genetic Algorithm by utilizing the notion of compromise. The simulation results show the power of the proposed method solving multi-objective optimizations in a case study of image error concealment.
  arXiv  Detail & Related papers  (2020-11-11T15:22:23Z)
• Uncrowded Hypervolume-based Multi-objective Optimization with Gene-pool Optimal Mixing [0.0]
  Hypervolume-based MO optimization has shown promising results to overcome this. Sofomore framework overcomes this by solving multiple interleaved single-objective dynamic problems. We construct a hybrid approach that combines MO-GOMEA with UHV-GOMEA and outperforms both.
  arXiv  Detail & Related papers  (2020-04-10T15:14:54Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
  arXiv  Detail & Related papers  (2020-02-17T20:21: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.