Feature-Based Diversity Optimization for Problem Instance Classification | Zendy

Wanru Gao | Zendy; Samadhi Nallaperuma | Zendy; Frank Neumann | Zendy

AI Assistant Blog Pricing

Home ZAIA Blog

Open Access

Feature-Based Diversity Optimization for Problem Instance Classification

Author(s) -

Wanru Gao,

Samadhi Nallaperuma,

Frank Neumann

Publication year - 2020

Publication title -

evolutionary computation

Language(s) - English

Resource type - Journals

SCImago Journal Rank - 0.732

H-Index - 82

eISSN - 1530-9304

pISSN - 1063-6560

DOI - 10.1162/evco_a_00274

Subject(s) - heuristic , set (abstract data type) , feature (linguistics) , simple (philosophy) , construct (python library) , computer science , local search (optimization) , evolutionary algorithm , artificial intelligence , travelling salesman problem , mathematics , mathematical optimization , algorithm , philosophy , linguistics , epistemology , programming language

Understanding the behaviour of heuristic search methods is a challenge. This even holds for simple local search methods such as 2-OPT for the Travelling Salesperson Problem (TSP). In this article, 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.

The content you want is available to Zendy users.

Already have an account? Click here to sign in.

Having issues? You can contact us here

Accelerating Research