Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/920100

OpenURL Link
Title
A population-based approach to finding the matchset of a learning classifier system efficiently
Author/Creator
Mellor, Drew;  Nicklin, Steven P.
Institution
The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
Description
Profiling of the learning classifier system XCS [11] has revealed that its execution time tends to be dominated by rule matching [8], it is therefore important for rule matching to be efficient. To date, the fastest speedups for matching have been achieved by exploiting parallelism [8], but efficient sequential approaches, such as bitset and “specificity” matching [2], can be utilised if there is no platform support for the vector instruction sets that [8] employs. Previous sequential approaches have focussed on improving the efficiency of matching individual rules; in this paper, we introduce a population-based approach that partially matches many rules simultaneously. This is achieved by maintaining the rule-base in a rooted 3-ary tree over which a backtracking depthfirst search is run to find the matchset. We found that the method generally outperformed standard and specificity matching on raw matching and on several benchmarking tasks. While the bitset approach attained the best speedups on the benchmarking tasks, we give an analysis that shows that it can be the least efficient of the approaches on long rule conditions. A limitation of the new method is that it is inefficient when the proportion of “don’t care” symbols in the rule conditions is very large, which could perhaps be remedied by combining the method with the specificity technique.
Relation
11th Annual Conference on Genetic and Evolutionary Computation, 2009 (GECCO'09). Proceedings of the 11th Annual Conference on Genetic and Evolutionary Computation (Montreal, Canada 8-12 July, 2009) p. 1267-1274
Publisher Link
http://dx.doi.org/10.1145/1569901.1570071
Date
2009
Publisher
ACM
Keyword(s)
learning classifier systems;  LCS;  XCS;  efficient matching
Resource Type
conference paper
Identifier
http://hdl.handle.net/1959.13/920100
Identifier
ISBN:9781605583259
Reviewed
Reviewed
8 Visitors 10 Hits 0 Downloads
Save/E-mail Citation
Citation Format
E-mail Address
Subject
"A population-based approach to finding the matchset of a learning classifier system efficiently"
 
OR