Please use this identifier to cite or link to this item: http://hdl.handle.net/1959.13/920100
- A population-based approach to finding the matchset of a learning classifier system efficiently
Nicklin, Steven P.
- The University of Newcastle. Faculty of Engineering & Built Environment, School of Electrical Engineering and Computer Science
- Profiling of the learning classifier system XCS  has revealed that its execution time tends to be dominated by rule matching , it is therefore important for rule matching to be efficient. To date, the fastest speedups for matching have been achieved by exploiting parallelism , but efficient sequential approaches, such as bitset and “specificity” matching , can be utilised if there is no platform support for the vector instruction sets that  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.
- 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
learning classifier systems;
- Resource Type
- conference paper