Training deep learning models for solving the Travelling Salesman Problem (TSP) directly on large instances is computationally challenging. An approach to tackle large-scale TSPs is through identifying elements in the...
详细信息
ISBN:
(纸本)9783030770044;9783030770037
Training deep learning models for solving the Travelling Salesman Problem (TSP) directly on large instances is computationally challenging. An approach to tackle large-scale TSPs is through identifying elements in the model or training procedure that promotes out-of-distribution (OoD) generalization, i.e., generalization to samples larger than those seen in training. The state-of-the-art TSP solvers based on Graph neural Networks (GNNs) follow different strategies to represent the TSP instances as input graphs. In this paper, we conduct experiments comparing different graph representations finding features that lead to a better OoD generalization.
Critical Adaptive Distributed Embedded Systems (CADES) must carry out a set of funcionalities while fulfilling their associated real-time and dependability requirements. Moreover, they must be able to reconfigure them...
详细信息
ISBN:
(纸本)9781728129891
Critical Adaptive Distributed Embedded Systems (CADES) must carry out a set of funcionalities while fulfilling their associated real-time and dependability requirements. Moreover, they must be able to reconfigure themselves in a bounded time as the operational context changes. Finding a proper configuration can be non-trivial and time-consuming. Several studies have proposed Deep Reinforcement Learning (DRL) approaches to solve combinatorialoptimization problems. In this paper, we explore the application of such approaches to CADES by solving a simple tasks allocation problem using DRL and comparing the results with three popular heuristics. The results show that DRL beats two of them and gets very close to the third, while requiring significantly less time to generate a solution.
Recent studies have revealed that neural combinatorial optimization (NCO) has advantages over conventional algorithms in many combinatorialoptimization problems such as routing, but it is less efficient for more comp...
详细信息
Recent studies have revealed that neural combinatorial optimization (NCO) has advantages over conventional algorithms in many combinatorialoptimization problems such as routing, but it is less efficient for more complicated optimization tasks such as packing which involves mutually conditioned action spaces. In this paper, we propose a Recurrent Conditional Query Learning (RCQL) method to solve both 2D and 3D packing problems. We first embed states by a recurrent encoder, and then adopt attention with conditional queries from previous actions. The conditional query mechanism fills the information gap between learning steps, which shapes the problem as a Markov decision process. Benefiting from the recurrence, a single RCQL model is capable of handling different sizes of packing problems. Experiment results show that RCQL can effectively learn strong heuristics for offline and online strip packing problems (SPPs), outperforming a wide range of baselines in space utilization ratio. RCQL reduces the average bin gap ratio by 1.83% in offline 2D 40-box cases and 7.84% in 3D cases compared with state-of-the-art methods. Meanwhile, our method also achieves 5.64% higher space utilization ratio for SPPs with 1000 items than the state of the art. (C) 2021 Elsevier B.V. All rights reserved.
We introduce the first neuraloptimization framework to solve a classical instance of the tiling problem. Namely, we seek a non-periodic tiling of an arbitrary 2D shape using one or more types of tiles-the tiles maxim...
详细信息
We introduce the first neuraloptimization framework to solve a classical instance of the tiling problem. Namely, we seek a non-periodic tiling of an arbitrary 2D shape using one or more types of tiles-the tiles maximally fill the shape's interior without overlaps or holes. To start, we reformulate tiling as a graph problem by modeling candidate tile locations in the target shape as graph nodes and connectivity between tile locations as edges. Further, we build a graph convolutional neural network, coined TilinGNN, to progressively propagate and aggregate features over graph edges and predict tile placements. TilinGNN is trained by maximizing the tiling coverage on target shapes, while avoiding overlaps and holes between the tiles. Importantly, our network is self-supervised, as we articulate these criteria as loss terms defined on the network outputs, without the need of ground-truth tiling solutions. After training, the runtime of TilinGNN is roughly linear to the number of candidate tile locations, significantly outperforming traditional combinatorial search. We conducted various experiments on a variety of shapes to showcase the speed and versatility of TilinGNN. We also present comparisons to alternative methods and manual solutions, robustness analysis, and ablation studies to demonstrate the quality of our approach.
neural combinatorial optimization (NCO) is a promising learning-based approach to solving complex combinatorialoptimization problems such as the traveling salesman problem (TSP), the vehicle routing problem (VRP), an...
详细信息
neural combinatorial optimization (NCO) is a promising learning-based approach to solving complex combinatorialoptimization problems such as the traveling salesman problem (TSP), the vehicle routing problem (VRP), and the orienteering problem (OP). However, how to efficiently train a powerful NCO solver for routing problems remains a crucial challenge. The widely used reinforcement learning method suffers from sparse rewards and low data efficiency, while the supervised learning approach requires a large number of high-quality solutions (i.e., labels) that could be costly to obtain. In this work, we find that simple data augmentation operations can drastically reduce the number of required high-quality solutions for supervised learning. Moreover, simple boosting strategies that leverage the property of multiple optima can significantly improve training efficiency. With only a small set of \(50,000\) labeled instances, supervised learning can achieve a competitive in-distribution performance with the widely-used reinforcement learning counterpart. Furthermore, we also investigate the generalization ability for larger out-of-distribution problems. We believe the findings from this work may lead to a rethinking of the value of data-efficient supervised learning for NCO solver training.
暂无评论