The study of generalization in XCS has been mainly focused on single-step binary problems for which the optimal (accurate, maximally general) solution is known. In contrast, binary multistep problems have primarily been studied in terms of performance. However, while there is an intuitive notion of generalization in multistep environments, the optimal solutions for even the simplest multistep problems are still unknown. This paper presents an approach to compute the optimal solutions for single-step and multistep binary problems starting from their tabular solution. We first illustrate the approach using Boolean functions for which the optimal solutions are known. Then, we apply it to compute, for the first time, the optimal solutions for the Woods problems that have been used as a testbed to study XCS behavior in multistep problems. The solutions confirm early intuitions on simple environments and shed new light on more complex problems. We compare the optimal solutions our approach computes with the condensed populations that XCS can evolve, showing that XCS consistently evolves a number of minimal solutions that increases with the number of learning problems. Finally, we extend our approach to compute the minimal representation of evolving classifier populations and compare the size of the evolved populations before and after condensation with their minimized counterparts.

Computing Optimal Populations for Binary Problems Using Logic Minimization

Lanzi, Pier Luca
2026-01-01

Abstract

The study of generalization in XCS has been mainly focused on single-step binary problems for which the optimal (accurate, maximally general) solution is known. In contrast, binary multistep problems have primarily been studied in terms of performance. However, while there is an intuitive notion of generalization in multistep environments, the optimal solutions for even the simplest multistep problems are still unknown. This paper presents an approach to compute the optimal solutions for single-step and multistep binary problems starting from their tabular solution. We first illustrate the approach using Boolean functions for which the optimal solutions are known. Then, we apply it to compute, for the first time, the optimal solutions for the Woods problems that have been used as a testbed to study XCS behavior in multistep problems. The solutions confirm early intuitions on simple environments and shed new light on more complex problems. We compare the optimal solutions our approach computes with the condensed populations that XCS can evolve, showing that XCS consistently evolves a number of minimal solutions that increases with the number of learning problems. Finally, we extend our approach to compute the minimal representation of evolving classifier populations and compare the size of the evolved populations before and after condensation with their minimized counterparts.
2026
File in questo prodotto:
File Dimensione Formato  
ECJ-2025-002R1.pdf

Accesso riservato

: Pre-Print (o Pre-Refereeing)
Dimensione 579.56 kB
Formato Adobe PDF
579.56 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11311/1332545
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
  • OpenAlex 0
social impact