Computed prediction in binary multistep problems

Computed prediction was originally devised to tackle problems defined over real-valued domains. Recent experiments on Boolean functions showed that the concept of computed prediction extends beyond real values and it can also be applied to solve more typical classifier system benchmarks such as Boolean multiplexer and parity functions. So far however, no result has been presented for other well known classifier system benchmarks, i.e., binary multistep problems such as the woods environments. In this paper, we apply XCS with computed prediction to woods environments and show that computed prediction can also tackle this class of problems. Our results demonstrate that (i) XCS with computed prediction converges to optimality faster than XCS, (ii) it solves problems that may be too difficult for XCS and (iii) it evolves solutions that are more compact than those evolved by XCS.