Current Slide

Genetic Algorithms (GA)

• Genetic Algorithm: based on an analogy to biological evolution
• An initial population is created consisting of randomly generated rules
• Each rule is represented by a string of bits
• E.g., if A1 and ¬A2 then C2 can be encoded as 100
• If an attribute has k > 2 values, k bits can be used
• Based on the notion of survival of the fittest, a new population is formed to consist of the fittest rules and their offspring
• The fitness of a rule is represented by its classification accuracy on a set of training examples
• Offspring are generated by crossover and mutation
• The process continues until a population P evolves when each rule in P satisfies a prespecified threshold
• Slow but easily parallelizable