Blind optimisation problem instance classification via enhanced universal similarity metric
Blind optimisation problem instance classification via enhanced universal similarity metric
复制标题
DOI：
10.1007/s12293-014-0145-7
复制
发表时间：
2014-12-01
影响因子：
4.7
通讯作者：
Ignacio Hidalgo, J.
中科院分区：
文献类型：
--
作者：
Contreras, Ivan;Arnaldo, Ignacio;Ignacio Hidalgo, J.
模因计算的最终目标是完全自主地解决复杂的优化问题。一段时间以来，模因算法文献一直在朝着不断增加的优化器推广的方向发展，这些优化器是由Krasnogor和Smith等开创性论文发起的（IEEE Trans 9（5）：474-488，2005; 2000年国际遗传与进化计算会议论文集（GECCO 2000），2000），Krasnogor和Gustafson（Advances in nature-inspired computation：the PPSN VII Workshops 16（52），2002），随后是Ong和Keane等相关和最近的工作，（IEEE Trans Evol Comput 8（2）：99-110，2004）、Ong等人（IEEE Comp Int Mag 5（2）：24-31，2010）、Burke等人（Hyper-Evolistics：an emerging direction in modern search technology，2003）。在最近的趋势越来越普遍和适用性，研究集中在选择（甚至发展），正确的搜索操作符时使用的一个给定的实例，一个固定的问题类型（例如，搜索）。G. Euclidean 2D TSP）在一系列优化框架（Krasnogor，Handbook of natural computation，Springer，柏林/海德堡，2009）内的计算。本文是第一步的概括阶梯，其中一个假设，优化器是（也许是由其他解决者谁不一定知道如何处理一个给定的问题实例）的问题实例来解决，它必须自主，没有人为干预预选这是可能的家庭类的问题的实例属于。为了做到这一点，我们提出了一个自动问题分类系统，能够自动识别哪种情况或系统正在处理的问题。我们测试了一种创新的方法，通用相似性度量，作为一个变种的归一化压缩距离（NCD），分类不同的问题实例。这个版本是基于压缩字典的管理。所获得的结果是令人鼓舞的，因为我们实现了96%的平均分类成功与研究的数据集。
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.