On learning kDNF/sub n//sup s/ Boolean formulas
A. Hernandez-Aquirre, Bill P. Buckles, Carlos A. Coello Coello · 2002
The number of samples needed to learn an instance of the representation class kDNF/sub n//sup s/ of Boolean formulas is predicted using some tolerance parameters by the PAC framework. When the learning machine is a simple genetic algorithm, the initial population is an issue. Using PAC-learning we derive the population size that has at least one individual at a given Hamming distance from the optimum. Then we show that the GA evolves solutions from initial populations rather far (Hamming distance) from the optimum.