Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem

• URL: http://arxiv.org/abs/2006.15968v1
• Date: Mon, 29 Jun 2020 12:15:35 GMT
• Title: Deep Learning as a Competitive Feature-Free Approach for Automated Algorithm Selection on the Traveling Salesperson Problem
• Authors: Moritz Seiler and Janina Pohl and Jakob Bossek and Pascal Kerschke and Heike Trautmann
• Abstract summary: We focus on the well-known Euclidean Traveling Salesperson Problem (TSP) We evolve instances with 1,000 nodes where the solvers show strongly different performance profiles. We show that a feature-free deep neural network based approach solely based on visual representation of the instances already matches classical AS model results.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this work we focus on the well-known Euclidean Traveling Salesperson Problem (TSP) and two highly competitive inexact heuristic TSP solvers, EAX and LKH, in the context of per-instance algorithm selection (AS). We evolve instances with 1,000 nodes where the solvers show strongly different performance profiles. These instances serve as a basis for an exploratory study on the identification of well-discriminating problem characteristics (features). Our results in a nutshell: we show that even though (1) promising features exist, (2) these are in line with previous results from the literature, and (3) models trained with these features are more accurate than models adopting sophisticated feature selection methods, the advantage is not close to the virtual best solver in terms of penalized average runtime and so is the performance gain over the single best solver. However, we show that a feature-free deep neural network based approach solely based on visual representation of the instances already matches classical AS model results and thus shows huge potential for future studies.

Related papers

• Machine learning meets the CHSH scenario [0.0]
  We focus on assessing the usefulness and effectiveness of the machine learning (ML) approach. We consider a wide selection of approaches, ranging from simple data science models to dense neural networks. We conclude that while it is relatively easy to achieve good performance on average, it is hard to train a model that performs well on the "hard" cases.
  arXiv  Detail & Related papers  (2024-07-19T15:16:31Z)
• Skill-Based Few-Shot Selection for In-Context Learning [123.26522773708683]
  Skill-KNN is a skill-based few-shot selection method for in-context learning. It does not require training or fine-tuning of any models, making it suitable for frequently expanding or changing example banks. Experimental results across five cross-domain semantic parsing datasets and six backbone models show that Skill-KNN significantly outperforms existing methods.
  arXiv  Detail & Related papers  (2023-05-23T16:28:29Z)
• Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks [4.084365114504618]
  This paper revisits the algorithm selection problem for Euclidean Traveling Salesman Problem (TSP) We propose a novel Graph Neural Network (GNN), called GINES. GINES takes the coordinates of cities and distances between cities as input. It is better than the traditional handcrafted feature-based approach on one dataset.
  arXiv  Detail & Related papers  (2023-02-08T13:14:20Z)
• RF+clust for Leave-One-Problem-Out Performance Prediction [0.9281671380673306]
  We study leave-one-problem-out (LOPO) performance prediction. We analyze whether standard random forest (RF) model predictions can be improved by calibrating them with a weighted average of performance values.
  arXiv  Detail & Related papers  (2023-01-23T16:14:59Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  Permutation flow shop scheduling (PFSS) is widely used in manufacturing systems. We propose to train the model via expert-driven imitation learning, which accelerates convergence more stably and accurately. Our model's network parameters are reduced to only 37% of theirs, and the solution gap of our model towards the expert solutions decreases from 6.8% to 1.3% on average.
  arXiv  Detail & Related papers  (2022-10-31T09:46:26Z)
• AdAUC: End-to-end Adversarial AUC Optimization Against Long-tail Problems [102.95119281306893]
  We present an early trial to explore adversarial training methods to optimize AUC. We reformulate the AUC optimization problem as a saddle point problem, where the objective becomes an instance-wise function. Our analysis differs from the existing studies since the algorithm is asked to generate adversarial examples by calculating the gradient of a min-max problem.
  arXiv  Detail & Related papers  (2022-06-24T09:13:39Z)
• Automated Algorithm Selection: from Feature-Based to Feature-Free Approaches [0.5801044612920815]
  We propose a novel technique for algorithm-selection, applicable to optimisation in which there is implicit sequential information encapsulated in the data. We train two types of recurrent neural networks to predict a packing in online bin-packing, selecting from four well-known domains.
  arXiv  Detail & Related papers  (2022-03-24T23:59:50Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  Pairwise learning refers to learning tasks where the loss function depends on a pair instances. Online descent (OGD) is a popular approach to handle streaming data in pairwise learning. In this paper, we propose simple and online descent to methods for pairwise learning.
  arXiv  Detail & Related papers  (2021-11-23T18:10:48Z)
• Efficient Person Search: An Anchor-Free Approach [86.45858994806471]
  Person search aims to simultaneously localize and identify a query person from realistic, uncropped images. To achieve this goal, state-of-the-art models typically add a re-id branch upon two-stage detectors like Faster R-CNN. In this work, we present an anchor-free approach to efficiently tackling this challenging task, by introducing the following dedicated designs.
  arXiv  Detail & Related papers  (2021-09-01T07:01:33Z)
• Gone Fishing: Neural Active Learning with Fisher Embeddings [55.08537975896764]
  There is an increasing need for active learning algorithms that are compatible with deep neural networks. This article introduces BAIT, a practical representation of tractable, and high-performing active learning algorithm for neural networks.
  arXiv  Detail & Related papers  (2021-06-17T17:26:31Z)
• Towards Explainable Exploratory Landscape Analysis: Extreme Feature Selection for Classifying BBOB Functions [4.932130498861987]
  We show that a surprisingly small number of features -- often less than four -- can suffice to achieve a 98% accuracy. We show that the classification accuracy transfers to settings in which several instances are involved in training and testing.
  arXiv  Detail & Related papers  (2021-02-01T10:04:28Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.