Solving Optimization Problems through Fully Convolutional Networks: an Application to the Travelling Salesman Problem
arXiv:1910.12243 · doi:10.1186/s11671-018-2831-8
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 paper, 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 10 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 a 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.
25pages,7figures,research article
References in corpus (20)
- Very Deep Convolutional Networks for Large-Scale Image Recognition
- Sequence to Sequence Learning with Neural Networks
- Improving neural networks by preventing co-adaptation of feature detectors
- Thermal transport measurements of individual multiwalled nanotubes
- Unusually High Thermal Conductivity of Carbon Nanotubes
- End to End Learning for Self-Driving Cars
- Thermal conduction in classical low-dimensional lattices
- Optimized Tersoff and Brenner empirical potential parameters for lattice dynamics and phonon thermal transport in carbon nanotubes and graphene
- From Point Defects in Graphene to Two-Dimensional Amorphous Carbon
- Thermal conductivity of graphene flakes: Comparison with bulk graphite
- Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
- Thermal conductivity decomposition in two-dimensional materials: Application to graphene
- Tensile Strains Give Rise to Strong Size Effects for Thermal Conductivities of Silicene, Germanene and Stanene
- Novel Two-dimensional Carbon Allotrope with Strong Electronic Anisotropy
- Octagraphene as a Versatile Carbon Atomic Sheet for Novel Nanotubes, Unconventional Fullerenes and Hydrogen Storage
- A Two-Dimensional Carbon Semiconductor
- Equivalence of the equilibrium and the nonequilibrium molecular dynamics methods for thermal conductivity calculations: From bulk to nanowire silicon
- Fixed-Parameter Algorithms for Rectilinear Steiner tree and Rectilinear Traveling Salesman Problem in the plane
- Long-term Planning by Short-term Prediction
- Thermal conductivity of graphene kirigami: ultralow and strain robustness