TL;DR
This paper introduces a novel "negative control" approach for genetic algorithms (GAs) that uses machine learning to learn from past evolutionary "errors." By identifying and avoiding detrimental operations, this ML-based control significantly improves GA performance on several challenging problems, particularly by controlling mutation.
What Problem Does This Paper Address?
Genetic algorithms (GAs) rely on a delicate balance between exploration (searching new areas of the solution space) and exploitation (refining promising solutions). Controlling this balance, often through adjusting operator rates (like mutation and crossover), is crucial for efficient evolution. However, traditional methods for control are often ad-hoc or rely on brute-force parameter tuning. This paper addresses the challenge of developing a more intelligent, adaptive control mechanism for GAs that can learn from the evolutionary process itself to prevent repeating past mistakes. The authors propose using machine learning to extract "rules" from evolutionary history, enabling the GA to avoid operations that have previously led to poor outcomes.
Methods
The core of the paper is the development of a Knowledge-Controlled Evolution framework. This involves:
- Inductive Learning: The authors employ inductive learning to extract rules from examples of evolutionary events (crossovers and mutations). These examples are generated by a "reference population" and classified as "good" (leading to improved fitness), "bad" (leading to decreased fitness), or "inactive" (no change in fitness).
- Rule Extraction: The induction process aims to find rules that generalize these examples, essentially creating a knowledge base of what operations are detrimental or beneficial in specific contexts.
- ML-Based Control: These learned rules are then used to guide the evolution. The paper proposes two main control strategies:
- Classical Control: Rejects "bad" events, aiming to limit disruptiveness.
- Modern Control: Rejects "inactive" events, aiming to increase population diversity.
- Hybrid Evolution: The authors propose interleaving "darwinian" (uncontrolled) periods with periods of classical or modern ML-based control, adapting the control strategy based on the perceived "age" of the evolutionary process (beginning, middle, or end). This update mechanism is performed periodically (every M generations) to prevent rules from becoming outdated or misleading.
Datasets
The paper evaluates its proposed ML-based control on three standard GA benchmark problems:
- The Royal Road problem: Designed to study the combination of features adapted to GA search.
- A GA-deceptive problem: A concatenated version of elementary deceptive problems, known to be challenging for GAs.
- The multiple knapsack problem: A combinatorial optimization problem with constraints.
The authors do not introduce new benchmark datasets but rather use established ones to compare their method against existing GA approaches.
Key Insights and Ideas
- "Negative Control" is Safer: The authors argue that controlling evolution by learning what not to do (inhibitions based on past errors) is inherently safer and less prone to misleading the search than trying to prescribe what to do.
- Mutation Control is Surprisingly Effective: Despite crossover typically having a higher rate and being considered more disruptive, controlling mutation through ML-based rules yielded significantly better results than controlling crossover on several problems. This suggests that mutation plays a critical role in maintaining diversity and preventing premature convergence, especially in the later stages of evolution.
- ML as an Evolutionary Memory: The ML-based rules act as an explicit "memory" of the evolutionary process, allowing the GA to avoid repeating detrimental patterns.
- Adaptive Control Strategy: The hybrid approach of interleaving darwinian and ML-controlled periods, and periodically updating the rules, allows the control to adapt to the changing landscape of the evolutionary search.
Key Results
- Significant Performance Gains: ML-based control, particularly when applied to mutations (M-M and M-MX schemes), consistently and significantly improved the percentage of success on the Royal Road and GA-deceptive problems compared to standard GAs and other GA-based control methods.
- Royal Road: ML-control achieved up to 100% success rate with selective pressure 1.2, outperforming other methods.
- GA-Deceptive Problem: ML-control also showed substantial improvements, reaching 100% success with selective pressure 1.2.
- Knapsack Problem: ML-based control of mutations (M-M) led to reaching better solutions sooner, as visualized in the dynamics of evolution plots.
- Crossover Control Disastrous: Conversely, ML-based control built from crossover examples proved detrimental on the Royal Road and GA-deceptive problems.
Limitations and Future Work
- Control Disabled or Misleading: The approach can fail if induction cannot find significant rules (e.g., due to a non-representative reference population) or if the learned rules are misleading, potentially leading to a deceptive control.
- Computational Cost: The acquisition of examples and the induction process add computational overhead.
- Future Work:
- Flexible Control Strategy: Allowing evolution to optimize the control strategy itself (e.g., deciding whether to apply classical, modern, or darwinian control on an individual basis).
- Evolutionary Programming: Experimenting with ML-control within evolutionary programming frameworks.
- Real-Valued Search Spaces: Extending the approach to handle real-valued representations, which may introduce new challenges.
- Understanding Mutation vs. Crossover: Further investigating why mutation control was more effective than crossover control.
Summary updated