Solving Optimization Problems Through Fully Convolutional Networks: An Application to the Traveling Salesman Problem
Authors:
- 11 February 2020
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Systems, Man, and Cybernetics: Systems
- Vol. 51 (12) , 7475-7485
Abstract
In the new wave of artificial intelligence, deep learning is impacting various industries. As a closely related area, optimization algorithms greatly contribute to the development of deep learning. But the reverse applications are still insufficient. Is there any efficient way to solve certain optimization problem through deep learning? The key is to convert the optimization to a representation suitable for deep learning. In this article, a traveling salesman problem (TSP) is studied. Considering that deep learning is good at image processing, an image representation method is proposed to transfer a TSP to an image. Based on samples of a ten city TSP, a fully convolutional network (FCN) is used to learn the mapping from a feasible region to an optimal solution. The training process is analyzed and interpreted through stages. A visualization method is presented to show how an FCN can understand the training task of a TSP. Once the training is completed, no significant effort is required to solve a new TSP and the prediction is obtained on the scale of milliseconds. The results show good performance in finding the global optimal solution. Moreover, the developed FCN model has been demonstrated on TSP’s with different city numbers, proving excellent generalization performance.Keywords
All Related Versions
Funding Information
- NSFC-Zhejiang Joint Fund (U1509209)
- National Key Research and Development Program of China (2016YFC1301703)
This publication has 8 references indexed in Scilit:
- Fixed-parameter algorithms for rectilinear Steiner tree and rectilinear traveling salesman problem in the planeEuropean Journal of Operational Research, 2018
- Correction to: Deep Learning for Drug Design: an Artificial Intelligence Paradigm for Drug Discovery in the Big Data EraThe AAPS Journal, 2018
- Extended formulations and branch-and-cut algorithms for the Black-and-White Traveling Salesman ProblemEuropean Journal of Operational Research, 2017
- Deep Residual Learning for Image Recognition2016
- Fully Convolutional Networks for Semantic SegmentationIEEE Transactions on Pattern Analysis and Machine Intelligence, 2016
- Deep learningNature, 2015
- A Survey on Transfer LearningIEEE Transactions on Knowledge and Data Engineering, 2009
- “Neural” computation of decisions in optimization problemsBiological Cybernetics, 1985