ePrints

Blind optimisation problem instance classification via enhanced universal similarity metric

Lookup NU author(s): Professor Natalio Krasnogor

Downloads

Full text for this publication is not currently held within this repository. Alternative links are provided below where available.

Abstract

The ultimate aim of Memetic Computing is the fully autonomous solution to complex optimisation problems. For a while now, the Memetic algorithms literature has been moving in the direction of ever increasing generalisation of optimisers initiated by seminal papers such as Krasnogor and Smith (IEEE Trans 9(5): 474-488, 2005; Workshops Proceedings of the 2000 International Genetic and Evolutionary Computation Conference (GECCO2000), 2000), Krasnogor and Gustafson (Advances in nature-inspired computation: the PPSN VII Workshops 16(52), 2002) and followed by related and more recent work such as Ong and Keane (IEEE Trans Evol Comput 8(2): 99-110, 2004), Ong et al. (IEEE Comp Int Mag 5(2): 24-31, 2010), Burke et al. (Hyper-heuristics: an emerging direction in modern search technology, 2003). In this recent trend to ever greater generalisation and applicability, the research has focused on selecting (or even evolving), the right search operator(s) to use when tackling a given instance of a fixed problem type (e. g. Euclidean 2D TSP) within a range of optimisation frameworks (Krasnogor, Handbook of natural computation, Springer, Berlin/Heidelberg, 2009). This paper is the first step up the generalisation ladder, where one assumes that the optimiser is given (perhaps by other solvers who do not necessarily know how to deal with a given problem instance) a problem instance to tackle and it must autonomously and without human intervention pre-select which is the likely family class of problems the instance belongs to. In order to do that we propose an Automatic Problem Classifier System able to identify automatically which kind of instance or problem the system is dealing with. We test an innovative approach to the Universal Similarity Metric, as a variant of the normalised compression distance (NCD), to classify different problem instances. This version is based on the management of compression dictionaries. The results obtained are encouraging as we achieve a 96% average classification success with the studied dataset.

Publication metadata

Author(s): Contreras I, Arnaldo I, Krasnogor N, Hidalgo JI

Publication type: Article

Publication status: Published

Journal: Memetic Computing

Year: 2014

Volume: 6

Issue: 4

Pages: 263-276

Print publication date: 01/12/2014

Online publication date: 08/11/2014

Acceptance date: 13/10/2014

ISSN (print): 1865-9284

ISSN (electronic): 1865-9292

Publisher: Springer

URL: http://dx.doi.org/10.1007/s12293-014-0145-7

DOI: 10.1007/s12293-014-0145-7

Altmetrics

Actions

Share