Please use this identifier to cite or link to this item: https://hdl.handle.net/2440/129398
Citations
Scopus Web of Science® Altmetric
?
?
Type: Journal article
Title: Feature-based diversity optimization for problem instance classification
Author: Gao, W.
Nallaperuma, S.
Neumann, F.
Citation: Evolutionary Computation, 2021; 29(1):107-128
Publisher: Massachusetts Institute of Technology Press (MIT Press)
Issue Date: 2021
ISSN: 1063-6560
1530-9304
Statement of
Responsibility: 
Wanru Gao, Samadhi Nallaperuma and Frank Neumann
Abstract: Understanding the behaviour of heuristic search methods is a challenge. This even holds for simple local search methods such as 2-OPT for the Traveling Salesperson problem. In this paper, we present a general framework that is able to construct a diverse set of instances which are hard or easy for a given search heuristic. Such a diverse set is obtained by using an evolutionary algorithm for constructing hard or easy instances which are diverse with respect to different features of the underlying problem. Examining the constructed instance sets, we show that many combinations of two or three features give a good classification of the TSP instances in terms of whether they are hard to be solved by 2-OPT.
Keywords: Classification
Combinatorial optimization
Evolving Instances
Feature selection
Travelling Salesman Problem
Rights: © 2020 Massachusetts Institute of Technology
DOI: 10.1162/evco_a_00274
Grant ID: http://purl.org/au-research/grants/arc/DP140103400
http://purl.org/au-research/grants/arc/DP190103894
Appears in Collections:Aurora harvest 4
Computer Science publications

Files in This Item:
There are no files associated with this item.


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.