Learnable Evolutionary Multi-Objective Combinatorial Optimization via Sequence-to-Sequence Model

• URL: http://arxiv.org/abs/2412.06140v1
• Date: Mon, 09 Dec 2024 01:46:58 GMT
• Title: Learnable Evolutionary Multi-Objective Combinatorial Optimization via Sequence-to-Sequence Model
• Authors: Jiaxiang Huang, Licheng Jiao,
• Abstract summary: SeqMO is a learnable multi-objective optimization method that integrates sequence-to-sequence models with evolutionary algorithms. Our approach divides approximate solution sets based on objective values' distance to the Pareto front, and establishes mapping relationships between solutions by minimizing objective vector angles in the target space. Experiments on the multi-objective travel salesman problem and the multi-objective assignment problem verify the effectiveness of the algorithm.
• Score: 43.53359509358102
• License:
• Abstract: Recent advances in learnable evolutionary algorithms have demonstrated the importance of leveraging population distribution information and historical evolutionary trajectories. While significant progress has been made in continuous optimization domains, combinatorial optimization problems remain challenging due to their discrete nature and complex solution spaces. To address this gap, we propose SeqMO, a novel learnable multi-objective combinatorial optimization method that integrates sequence-to-sequence models with evolutionary algorithms. Our approach divides approximate Pareto solution sets based on their objective values' distance to the Pareto front, and establishes mapping relationships between solutions by minimizing objective vector angles in the target space. This mapping creates structured training data for pointer networks, which learns to predict promising solution trajectories in the discrete search space. The trained model then guides the evolutionary process by generating new candidate solutions while maintaining population diversity. Experiments on the multi-objective travel salesman problem and the multi-objective quadratic assignment problem verify the effectiveness of the algorithm. Our code is available at: \href{https://github.com/jiaxianghuang/SeqMO}{https://github.com/jiaxianghuang/SeqMO}.

Related papers

• Multi-Agent Path Finding in Continuous Spaces with Projected Diffusion Models [57.45019514036948]
  Multi-Agent Path Finding (MAPF) is a fundamental problem in robotics. This work proposes a novel approach that integrates constrained optimization with diffusion models for MAPF in continuous spaces.
  arXiv  Detail & Related papers  (2024-12-23T21:27:19Z)
• DiffSG: A Generative Solver for Network Optimization with Diffusion Model [75.27274046562806]
  Diffusion generative models can consider a broader range of solutions and exhibit stronger generalization by learning parameters. We propose a new framework, which leverages intrinsic distribution learning of diffusion generative models to learn high-quality solutions.
  arXiv  Detail & Related papers  (2024-08-13T07:56:21Z)
• Large Language Model-Aided Evolutionary Search for Constrained Multiobjective Optimization [15.476478159958416]
  We employ a large language model (LLM) to enhance evolutionary search for solving constrained multi-objective optimization problems. Our aim is to speed up the convergence of the evolutionary population.
  arXiv  Detail & Related papers  (2024-05-09T13:44:04Z)
• Rank-Based Learning and Local Model Based Evolutionary Algorithm for High-Dimensional Expensive Multi-Objective Problems [1.0499611180329806]
  The proposed algorithm consists of three parts: rank-based learning, hyper-volume-based non-dominated search, and local search in the relatively sparse objective space. The experimental results of benchmark problems and a real-world application on geothermal reservoir heat extraction optimization demonstrate that the proposed algorithm shows superior performance.
  arXiv  Detail & Related papers  (2023-04-19T06:25:04Z)
• 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)
• An Online Prediction Approach Based on Incremental Support Vector Machine for Dynamic Multiobjective Optimization [19.336520152294213]
  We propose a novel prediction algorithm based on incremental support vector machine (ISVM) We treat the solving of dynamic multiobjective optimization problems (DMOPs) as an online learning process. The proposed algorithm can effectively tackle dynamic multiobjective optimization problems.
  arXiv  Detail & Related papers  (2021-02-24T08:51:23Z)
• AdaLead: A simple and robust adaptive greedy search algorithm for sequence design [55.41644538483948]
  We develop an easy-to-directed, scalable, and robust evolutionary greedy algorithm (AdaLead) AdaLead is a remarkably strong benchmark that out-competes more complex state of the art approaches in a variety of biologically motivated sequence design challenges.
  arXiv  Detail & Related papers  (2020-10-05T16:40:38Z)
• Adaptive Sampling of Pareto Frontiers with Binary Constraints Using Regression and Classification [0.0]
  We present a novel adaptive optimization algorithm for black-box multi-objective optimization problems with binary constraints. Our method is based on probabilistic regression and classification models, which act as a surrogate for the optimization goals. We also present a novel ellipsoid truncation method to speed up the expected hypervolume calculation.
  arXiv  Detail & Related papers  (2020-08-27T09:15:02Z)
• EOS: a Parallel, Self-Adaptive, Multi-Population Evolutionary Algorithm for Constrained Global Optimization [68.8204255655161]
  EOS is a global optimization algorithm for constrained and unconstrained problems of real-valued variables. It implements a number of improvements to the well-known Differential Evolution (DE) algorithm. Results prove that EOSis capable of achieving increased performance compared to state-of-the-art single-population self-adaptive DE algorithms.
  arXiv  Detail & Related papers  (2020-07-09T10:19:22Z)
• 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.