GAIA - CBR for Cellular Automata configuration

About CBR for Cellular Automata configuration

The modeling of complex systems constitutes a highly valuable tool for solving problems of very diverse nature, and cellular automata are capable of simulating their evolution in a visual and relatively simple way. Automata evolve according to a set of rules, and it is in finding the optimal rules where different artificial intelligence techniques can be of great help. In recent years, evolutionary strategies have proven to be an efficient method for solving this type of problem, due to their ability to find robust solutions in relatively large search spaces.

This work is based on both elements: evolutionary strategies and cellular automata, with the aim of discovering self-organization patterns and emergent computation arising solely from local interactions between automaton cells; that is, the goal is to achieve global coordination from strictly local information. The fusion of both techniques is used to build a Case-Based Reasoning (CBR) engine capable of solving problems in the context of artificial morphogenesis. Experimental results show that the CBR engine reduces the number of generations required by up to 80%, while maintaining competitive fitness scores.

Main Contributions

Implementation of a (μ + λ) Evolutionary Strategy: An adaptive mutation strategy is proposed to optimize local transition rules, successfully overcoming epistasis and premature convergence commonly present in classical GAs.
Design of a 2D Evaluation Framework: An advanced framework for artificial morphogenesis is introduced by combining structural metrics (multichannel RGB SSIM), spatial metrics (weighted Jaccard index), and statistical dependency metrics (Mutual Information).
Development of a CBR Engine: A CBR architecture is presented that automates system parameterization through topological retrieval and transfer learning of cellular automata rules, demonstrating up to an 80% reduction in computational cost.
Systematic Evaluation: Validation on 1D benchmarks (Density Classification Problem, French Flag Problem, Drosophila embryogenesis), and 2D flag generation problems.

All the code associated with this project is available on this GitHub repository: GitHub/sergiio8/TFG_CS

Optimization Framework

Problem Definition: Rule Evolution

The core challenge is to discover the transition rules that determine a specific behavior of the cellular automaton. These rules are encoded as an array (a lookup table), where each index represents a specific neighborhood configuration, and its value corresponds to the next state of the central cell.

These arrays serve as the chromosomes in our evolutionary strategy, where the goal is to optimize the gene sequence to achieve specific morphogenetic patterns.

Figure: Mapping of neighborhood configurations to the lookup table array (the chromosome).

The system integrates cellular automata with an evolutionary strategy capable of exploring intractable rule spaces.

Cellular Automaton Modeling

We use CellPyLib to configure neighborhoods and boundaries.

Neighborhoods: Visualization of neighboring cells (von Neumann/Moore).
Boundary Conditions: Configuration of behavior at the limits (periodic, fixed, or mixed).

Figure: von Neumann and Moore neighborhoods.

Figure: Periodic boundary conditions in 2 dimensions.

Evolutionary Strategy (μ + λ)

We employ the (μ + λ) strategy with adaptive mutation to avoid premature convergence and epistasis.

Figure: Diagram of the (μ+λ) strategy.

Adaptive Mutation m(f)

Equation: Dynamic adjustment of the number of mutated genes according to fitness (exploration vs exploitation).

Evaluation Metrics (Fitness Function)

In 2D scenarios, accuracy is insufficient. Therefore, we employ a convex combination of metrics to guide morphogenesis:

SSIM: Evaluates global structure and visual contrast.

Jaccard Index: Measures pixel-by-pixel positional accuracy.

Mutual Information: Captures statistical dependency between images.

Fitness formula: fitness = α·SSIM + β·Jaccard + γ·MI (where α+β+γ=1)

CBR System

To automate system parameterization, a CBR architecture has been implemented that provides the framework with a "memory" based on prior experience. Instead of treating each artificial morphogenesis problem independently, the system reuses previous parameterizations and successful transition rules.

1. Similarity Evaluation

We designed a similarity function for the Retrieve phase that combines four critical descriptors:

Topological Similarity: Evaluation of stripes, edges, and connected components.
Mutual Information (MI): Captures statistical dependency, robust against shifts.
Color Histograms: Comparison of state density (percentage of each color).
Rotational Invariance: The engine is capable of identifying equivalent cases through 90° rotations, allowing successful rules to be reused in different orientations.

2. Rule Transfer Learning

Once the most similar case has been retrieved, the engine applies Transfer Learning techniques to accelerate optimization:

Knowledge Injection: The best rules found in similar problems are leveraged and directly injected into the initial population of the evolutionary algorithm.
Evolutionary Acceleration: The combined injection of rules (5% clones and 5% mutated) acts as a starting point, drastically improving the algorithm's convergence toward high-fitness solutions.

Case Studies 1D

The validation of the framework began with three one-dimensional problems of varying complexity:

Density Classification Problem

A classical benchmark where the ability to reach a uniform state from random configurations is analyzed. The rule found by our algorithm was compared with the handcrafted Gacs-Kurdymov-Levin (GKL) rule, obtaining competitive results and strong generalization capability.

French Flag Problem

A fundamental low-level morphogenesis problem. The (μ + λ) strategy proved superior to the classical algorithm, achieving fitness scores above 90% and overcoming premature convergence thanks to adaptive mutations.

Drosophila Embryogenesis

Simulation of the even-skipped gene pattern in seven stripes. The system successfully inferred the local genomic rule governing cellular differentiation from the macroscopic phenotype, resolving the conflict caused by initial noise.

Density Classification Problem automaton

French Flag Problem automaton

Drosophila embryogenesis automaton

Fitness evolution with a classical genetic algorithm

Fitness evolution with the (μ+λ) strategy

Experiments 1D & 2D

The transition to two-dimensional environments increases topological complexity, requiring an evaluation framework based on structural (SSIM), spatial (Jaccard), and statistical (Mutual Information) metrics.

Hungary Flag

We addressed the formation of a horizontal stripe pattern from initial noise, achieving fitness scores above 75%.

Japan Flag

We tackled the morphogenesis of a central circle from an initial seed. This case revealed emergent behavior: the automaton learns to "wait" (initial oscillations) depending on the total number of timesteps so that the circle does not overflow the canvas dimensions, achieving fitness scores above 80%.

Video: Evolution of the automaton toward the Hungary flag.

Video: Formation of the Japan flag pattern.

CBR Evaluation

The CBR engine was evaluated against a collection of 12 problems. Below, we present the analysis of 6 successful cases illustrating the system's ability to reuse experience and accelerate convergence through transfer learning.

Performance Analysis

The evaluation focused on measuring how the injection of seed rules obtained through topological retrieval and transfer learning affects the evolutionary lifecycle. The selected cases (Poland, Italy, Benin, Switzerland, Bangladesh, Colombia) represent diverse morphogenetic challenges where the CBR engine demonstrated superior efficiency both in fitness and number of generations compared to random resolution and expert heuristics. Savings of up to 80% in the number of generations were achieved in the Colombia case.