PaperlayerView exact revision on arXiv

Source-linked AI summary

Deep Reinforcement Learning for Multi-objective Optimization

Kaiwen Li, Tao Zhang, Rui Wang

arXiv:1906.02386v2cs.NEmath.OC

TL;DR

The paper addresses the inefficiency and limited adaptability of iteration-based methods for multi-objective optimization. It proposes DRL-MOA, a decomposition-based DRL framework whose trained neural networks directly produce Pareto solutions, and reports strong generalization, fast solving, and competitive solution quality on MOTSP.

  • Problem

    Iteration-based evolutionary algorithms and heuristics often require long searches and must be rerun or revised when multi-objective problem instances change.

  • Method

    DRL-MOA decomposes a multi-objective problem into scalar subproblems, models each with a neural network, and collaboratively trains them using neighborhood-based parameter transfer and DRL.

  • Results

    On MOTSP instances, DRL-MOA significantly outperforms NSGA-II, MOEA/D, and MOGLS in solution convergence, spread performance, and computing time.

  • Takeaways & Limitations

    Once trained, DRL-MOA generalizes to newly encountered MOTSP problems without retraining and obtains Pareto solutions through a simple forward propagation without iterative searching.

Abstract

from arXiv · show

This study proposes an end-to-end framework for solving multi-objective optimization problems (MOPs) using Deep Reinforcement Learning (DRL), that we call DRL-MOA. The idea of decomposition is adopted to decompose the MOP into a set of scalar optimization subproblems. Then each subproblem is modelled as a neural network. Model parameters of all the subproblems are optimized collaboratively according to a neighborhood-based parameter-transfer strategy and the DRL training algorithm. Pareto optimal solutions can be directly obtained through the trained neural network models. In specific, the multi-objective travelling salesman problem (MOTSP) is solved in this work using the DRL-MOA method by modelling the subproblem as a Pointer Network. Extensive experiments have been conducted to study the DRL-MOA and various benchmark methods are compared with it. It is found that, once the trained model is available, it can scale to newly encountered problems with no need of re-training the model. The solutions can be directly obtained by a simple forward calculation of the neural network; thereby, no iteration is required and the MOP can be always solved in a reasonable time. The proposed method provides a new way of solving the MOP by means of DRL. It has shown a set of new characteristics, e.g., strong generalization ability and fast solving speed in comparison with the existing methods for multi-objective optimizations. Experimental results show the effectiveness and competitiveness of the proposed method in terms of model performance and running time.

I. INTRODUCTION

The paper motivates DRL for multi-objective optimization by addressing the iteration, re-solving, and task-specific limitations of classical methods. It proposes DRL-MOA and evaluates it on MOTSP, reporting generalization, speed, convergence, and diversity advantages.

  • Problem setting: MOTSP requires minimizing multiple conflicting travel-cost objectives over a cyclic tour and is harder than single-objective TSP.Approximate algorithms are therefore commonly used in practice.
  • Motivation: Classical evolutionary and handcrafted methods may require many iterations, repeated optimization after instance changes, and task-specific redesign.These limitations become more pronounced for large-dimensional problems and newly encountered instances.
  • Motivation: DRL is presented as a way to learn decision-making and optimization procedures without manually engineered evolution strategies or heuristics.The paper positions DRL as learning how to solve optimization problems automatically.
  • Proposed direction: DRL-MOA solves MOPs end to end by producing solutions through forward propagation of a trained network, including for previously unseen problems.The trained model is described as a black-box heuristic or meta-algorithm with learned heuristics.
  • Reported findings: The proposed method is reported to outperform classical methods on large-scale MOTSPs in convergence and diversity while requiring much less running time.The comparisons include evolutionary and specialized methods such as NSGA-II, MOEA/D, and MOGLS.

II. THE DEEP REINFORCEMENT LEARNING-BASED MULTI-OBJECTIVE OPTIMIZATION ALGORITHM (DRL-MOA)

DRL-MOA decomposes a multi-objective problem into scalar subproblems, models each with a neural network, and trains them collaboratively through neighborhood-based parameter transfer. The resulting models approximate the Pareto front and can produce solutions directly by forward propagation.

  • General framework: DRL-MOA decomposes an MOP into scalar optimization subproblems and models each subproblem as a neural network.The framework uses DRL to solve the subproblems collaboratively.
  • Decomposition strategy: Weighted Sum converts the original MOP into N scalar subproblems using a set of uniformly spread weight vectors.The Pareto front is formed from solutions obtained across the subproblems.
  • Parameter transfer: Neighboring subproblems can have close optimal solutions because their weight vectors are adjacent, enabling knowledge transfer between network models.The strategy uses a solved neighboring model to assist training of the next subproblem.
  • Parameter transfer: Network parameters are transferred sequentially from one subproblem to the next, reducing the training burden across the N subproblems.The paper states that without this strategy, training would require a tremendous amount of time.
  • Inference: After training, the Pareto front can be directly approximated from the obtained models through forward propagation without population updating or iterative searching.The framework is also described as modular, allowing the subproblem model to be replaced for other optimization problems.

B. Modelling the subproblem of MOTSP

For MOTSP, DRL-MOA decomposes the problem into subproblems and models each one with a modified Pointer Network trained by Actor-Critic reinforcement learning.

  • MOTSP modelling: MOTSP is decomposed into subproblems that are solved collaboratively within the DRL-MOA framework.Each decomposed subproblem is handled using deep reinforcement learning.
  • MOTSP modelling: Each MOTSP subproblem is modelled with a modified Pointer Network and trained using the Actor-Critic algorithm.The model outputs a permutation of the cities as the tour representation.

1) Formulation of MOTSP:

MOTSP seeks a cyclic tour of n cities that minimizes M cost functions simultaneously, extending the TSP setting to multiple objectives.

  • An MOTSP requires finding a cyclic permutation ρ of n cities while minimizing M different travel cost functions simultaneously.
  • Each objective assigns a travel cost to the transition from city ρ(i) to city ρ(i+1), such as length, safety, or tourist attractiveness.

2) The model:

The model maps city attributes to a city permutation using a modified Pointer Network with convolutional encoding, recurrent decoding, and attention-based next-city selection.

  • The modified Pointer Network maps input city attributes X to an output permutation Y={ρ1,···,ρn}.
  • For bi-objective Euclidean TSPs, each city contributes coordinates for two objectives, producing a four-dimensional input with 4 × n values.
  • Encoder: The encoder uses a 1-D convolutional embedding rather than an RNN because city-input order is not meaningful, with hidden dimension dh=128.
  • Decoder and attention: The decoder uses a GRU to summarize previously selected cities, and attention combines its hidden state with encoded city representations to select the next city.
  • Decoder and attention: At each step, attention scores candidate cities, softmax produces their selection probabilities, and training samples from this distribution instead of always choosing greedily.

3) Training method:

DRL-MOA decomposes the MOP into scalar subproblems, trains their neural networks collaboratively with neighborhood parameter transfer and Actor-Critic learning, and then outputs solutions by forward propagation.

  • DRL-MOA decomposes the MOP into scalar subproblems whose neural-network models are collaboratively optimized through neighborhood-based parameter transfer.
  • Training uses actor and critic networks: the Pointer Network selects actions, while the critic estimates expected reward for a problem state.
  • MOTSP instances are generated unsupervised from feature distributions, and sampled tours provide rewards for updating the actor and critic networks.
  • The trained models directly output Pareto optimal solutions through forward propagation, with approximate MOTSP complexity O(Nndh^2).N denotes the number of subproblems; encoder and decoder forward calculations are reported as fast enough to obtain solutions within reasonable time.

III. EXPERIMENTAL SETUPS

The study evaluates DRL-MOA on bi-objective TSPs using a GPU implementation and compares it with algorithms run on CPU-based software platforms.

  • DRL-MOA is tested on bi-objective TSPs using a single GTX 2080Ti GPU, with publicly available Python code.
  • Compared MOEAs are run through the PlatEMO MATLAB platform, while MOGLS is implemented in Python3.
  • All compared algorithms run on an Intel 16-Core i7-9800X CPU with 64GB memory.

A. Test Instances

The study tests Euclidean and Mixed MOTSP instances with different input structures, using models trained on 40-city instances to approximate Pareto fronts for larger problems. Training is unsupervised and uses generated instances, while evaluation includes standard and randomly generated test problems.

  • Euclidean instances use two coordinate sets, producing a four-dimensional input for two distance-based objectives.
  • Mixed instances use two-dimensional city coordinates and one-dimensional altitude values, producing a three-dimensional input.The objectives minimize travel distance and altitude variance.
  • Training requires only model inputs and reward functions, without optimal tours as labels.Euclidean and Mixed instances are generated from a uniform distribution over [0, 1].
  • Euclidean experiments use kroAB100, kroAB150, and kroAB200, while Mixed experiments use randomly generated instances from 40 to 200 cities.
  • The model is trained on 40-city MOTSP instances and applied to 40-, 70-, 100-, 150-, and 200-city test instances.
  • The experimental comparison evaluates DRL-MOA against NSGA-II and MOEA/D using population size and subproblem count 100, with competitor iteration limits of 500 to 4000.The Tchebycheff approach is used for MOEA/D, and only nondominated final solutions are retained.

A. Results on Mixed type bi-objective TSP

Across Mixed and Euclidean bi-objective MOTSPs, DRL-MOA generalizes from 40-city training instances to substantially larger problems. It maintains strong convergence and diversity while requiring less computation than iterative MOEAs, especially as problem size increases.

  • Mixed instances: DRL-MOA efficiently scales from 40-city training instances to Mixed bi-objective TSPs with 70, 100, 150, and 200 cities.The reported evaluation uses Pareto fronts and Hypervolume values from five runs.
  • Mixed instances: 4000 iterations require 130.2 seconds for MOEA/D and 28.3 seconds for NSGA-II, compared with 2.7 seconds for DRL-MOA.
  • Mixed instances: As the number of cities increases, NSGA-II and MOEA/D struggle to converge while DRL-MOA retains better convergence.
  • Mixed instances: For 150- and 200-city Mixed instances, DRL-MOA performs better than both competitors in convergence and diversity despite their 4000 iterations.
  • Euclidean instances: On the 150- and 200-city Euclidean instances, DRL-MOA significantly outperforms NSGA-II and MOEA/D in both convergence and diversity.This gap remains after NSGA-II and MOEA/D run for 4000 iterations.
  • Euclidean instances: On Euclidean instances, DRL-MOA achieves the best Hypervolume on all tested instances and substantially lower running time than the compared MOEAs.The Euclidean evaluation covers 40-, 70-, 100-, 150-, and 200-city problems.
  • Euclidean instances: DRL-MOA also significantly outperforms the competitors on a 500-city Euclidean instance trained from 40-city data.

C. Extension to MOTSPs with More Objectives

The study extends DRL-MOA beyond bi-objective problems and compares it with local-search-based MOTSP methods. Results support strong performance on higher-objective instances, while local search can further improve DRL-generated solutions.

  • More objectives: The model trained on 40-city instances is evaluated on 3- and 5-objective TSPs with 100 and 200 cities.The higher-objective instances combine two two-dimensional inputs with one or three one-dimensional inputs.
  • More objectives: DRL-MOA significantly outperforms classical MOEAs on the tested 3-objective 100- and 200-city instances.The 200-city instance shows clearer superiority while the competitors struggle to converge.
  • More objectives: The experiments report Hypervolume values for both 3- and 5-objective TSP instances based on five runs.
  • Local-search comparison: The comparison with local-search methods uses improved MOGLS variants alongside DRL-MOA and DRL-MOA+LS.
  • Local-search comparison: The study explicitly does not aim to outperform specialized non-learned MOTSP algorithms, instead emphasizing solving speed and generalization.
  • Local-search comparison: A single 2-opt post-processing step further improves DRL-MOA solutions while costing several seconds in total.

E. Effectiveness of parameter-transfer strategy

Experiments show that the neighborhood-based parameter-transfer strategy is important for effective DRL-MOA training. Removing it produces poor performance even when training is extended substantially.

  • Without parameter transfer, the model trained on 120,000 20-city instances for five epochs performs dramatically poorly.
  • Training four times longer without parameter transfer still produces poor performance.The extended experiment uses 240,000 instances for 10 epochs.
  • The experiments therefore identify parameter transfer as an effective and efficient component of the training strategy.

F. The impact of training on different number of cities

Training on 40-city instances produces better-performing models than training on 20-city instances, while DRL-MOA is reported to generalize across problem sizes without retraining. The method is also reported to provide fast solving and promising solution quality, although solution distribution remains an open issue.

  • Training-size comparison: Two models trained on 20- and 40-city Euclidean bi-objective TSP instances are used to approximate Pareto fronts for 40-, 100-, and 200-city problems.
  • Training-size comparison: Models trained on 20-city instances perform apparently worse than models trained on 40-city instances, with fewer non-dominated solutions and more crowded regions.The authors attribute this deterioration partly to making twice as many city-selection decisions during training on 40-city instances.
  • Open issues: DRL-MOA solutions are not all non-dominated and are not evenly distributed along the provided search directions.The authors identify these properties as issues requiring further study.
  • Generalization and efficiency: Once trained, DRL-MOA can scale to newly encountered problems without retraining, and its performance is less affected by increasing city counts than existing methods.
  • Generalization and efficiency: Pareto optimal solutions can be obtained within a reasonable time while maintaining solution quality, providing a balance between solving speed and quality.The method obtains solutions through direct model computation rather than population updating or iterative searching.
Loading 1906.02386v2…