Lossless fitness inheritance in genetic algorithms for decision trees

2006/11/30 by Dimitris Kalles, Kalles, Dimitris, Athanassios Papagelis +1 · 2 citations
Computer Science · #Artificial Intelligence (cs.AI) #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #Evolutionary Algorithms and Applications #FOS: Computer and information sciences #Metaheuristic Optimization Algorithms Research #Neural and Evolutionary Computing (cs.NE) #cs.AI #cs.DS #cs.NE

paper · pdf · doi:10.48550/arxiv.cs/0611166

Contains 23 pages, 6 figures, 12 tables. Text last updated as of March 6, 2009. Submitted to a journal

openalex publication_date 2006/11/30 · arxiv created 2009/03/10 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

When genetic algorithms are used to evolve decision trees, key tree quality parameters can be recursively computed and re-used across generations of partially similar decision trees. Simply storing instance indices at leaves is enough for fitness to be piecewise computed in a lossless fashion. We show the derivation of the (substantial) expected speed-up on two bounding case problems and trace the attractive property of lossless fitness inheritance to the divide-and-conquer nature of decision trees. The theoretical results are supported by experimental evidence.

Cited by

• Governance by Evidence: Regulated Predictors in Decision-Tree Models
• Improving Decision Trees through the Lens of Parameterized Local Search

Related

• Genetic Adversarial Training of Decision Trees
• Sharpness-Aware Minimization in Genetic Programming
• On the Workings of Genetic Algorithms: The Genoclique Fixing Hypothesis
• Fitness-based Adaptive Control of Parameters in Genetic Programming: Adaptive Value Setting of Mutation Rate and Flood Mechanisms
• Evolutionary algorithms for constructing an ensemble of decision trees