Multi-Objective Neural Evolutionary Algorithm for Combinatorial Optimization Problems

Yinan Shao, Jerry Chun Wei Lin, Gautam Srivastava, Dongdong Guo, Hongchun Zhang, Hu Yi, Alireza Jolfaei

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

Abstract

There has been a recent surge of success in optimizing deep reinforcement learning (DRL) models with neural evolutionary algorithms. This type of method is inspired by biological evolution and uses different genetic operations to evolve neural networks. Previous neural evolutionary algorithms mainly focused on single-objective optimization problems (SOPs). In this article, we present an end-to-end multi-objective neural evolutionary algorithm based on decomposition and dominance (MONEADD) for combinatorial optimization problems. The proposed MONEADD is an end-to-end algorithm that utilizes genetic operations and rewards signals to evolve neural networks for different combinatorial optimization problems without further engineering. To accelerate convergence, a set of nondominated neural networks is maintained based on the notion of dominance and decomposition in each generation. In inference time, the trained model can be directly utilized to solve similar problems efficiently, while the conventional heuristic methods need to learn from scratch for every given test problem. To further enhance the model performance in inference time, three multi-objective search strategies are introduced in this work. Our experimental results clearly show that the proposed MONEADD has a competitive and robust performance on a bi-objective of the classic travel salesman problem (TSP), as well as Knapsack problem up to 200 instances. We also empirically show that the designed MONEADD has good scalability when distributed on multiple graphics processing units (GPUs).

Original languageEnglish
Number of pages11
JournalIEEE Transactions on Neural Networks and Learning Systems
Early online date2 Sep 2021
DOIs
Publication statusE-pub ahead of print - 2 Sep 2021
Externally publishedYes

Keywords

  • Attention mechanism
  • deep reinforcement learning (DRL)
  • Evolutionary computation
  • Genetics
  • Heuristic algorithms
  • multi-objective learning
  • neural combinatorial optimization
  • neural evolutionary algorithm.
  • Neural networks
  • Optimization
  • Search problems
  • Urban areas

Fingerprint

Dive into the research topics of 'Multi-Objective Neural Evolutionary Algorithm for Combinatorial Optimization Problems'. Together they form a unique fingerprint.

Cite this