In adaptive evolution, a system is iteratively modified in order to optimize a given fitness function. This biologically inspired technique is commonly used to search for solutions in large, complex spaces. In this project, we investigate the adaptive evolution of hypergraph rewriting systems. Our goal is to discover rewrite rules that evolve a hypergraph for a finite number of iterations and then halt. As an extension, we explore the adaptive evolution of hypergraph multiway systems, aiming to identify rules that produce halting multiway graphs with the maximal possible number of nodes.
Introduction
Introduction
The adaptive evolution of a system is an iterative process in which the system gets slightly adjusted at each timestep. If the adjustment improves the system according to a certain measurement, the new version is kept and we continue evolving from there. If it performs worse, we discard the adjustment and try a different one. These small adjustments are called mutations. The performance of the system is measured using a so-called fitness function.
In previous work, Stephen Wolfram used adaptive evolution on cellular automata (CAs) to find CA rules that generate systems with a finite lifetime. He obtained very interesting results, helping explain how biological evolution and neural networks might work. Similarly, he applied adaptive evolution to Turing Machines.
In this post, we examine the adaptive evolution of string rewriting systems, hypergraph rewriting systems, and finally hypergraph multiway systems. All these systems consist of an initial state and a rule that is applied iteratively, either indefinitely or until the rule can no longer be applied. The number of times a rule can be applied is the system’s lifetime. The main idea is the following: in each step of the evolution process, we mutate the current rule, build the rewriting system based on a fixed initial state, and compute the fitness of the rule based on properties of the resulting system. For all three kinds of rewriting systems, the core process is the same. The main differences lie in how we define the mutation and fitness functions.
The adaptive evolution of string and hypergraph rewriting systems has previously been briefly explored by Willem Nielsen in the context of developmental biology. We build on his work.
In previous work, Stephen Wolfram used adaptive evolution on cellular automata (CAs) to find CA rules that generate systems with a finite lifetime. He obtained very interesting results, helping explain how biological evolution and neural networks might work. Similarly, he applied adaptive evolution to Turing Machines.
In this post, we examine the adaptive evolution of string rewriting systems, hypergraph rewriting systems, and finally hypergraph multiway systems. All these systems consist of an initial state and a rule that is applied iteratively, either indefinitely or until the rule can no longer be applied. The number of times a rule can be applied is the system’s lifetime. The main idea is the following: in each step of the evolution process, we mutate the current rule, build the rewriting system based on a fixed initial state, and compute the fitness of the rule based on properties of the resulting system. For all three kinds of rewriting systems, the core process is the same. The main differences lie in how we define the mutation and fitness functions.
The adaptive evolution of string and hypergraph rewriting systems has previously been briefly explored by Willem Nielsen in the context of developmental biology. We build on his work.
Global Functions
Global Functions
mutateOneOption
mutateOneOption
mutateIterationOneOption
mutateIterationOneOption
mutateStringRule
mutateStringRule
fitnessStringLifeTime
fitnessStringLifeTime
mutateHypergraphRule
mutateHypergraphRule
fitnessHypergraphNodeNum
fitnessHypergraphNodeNum
fitnessHypergraphLifeTime
fitnessHypergraphLifeTime
fitnessMultiway
fitnessMultiway
String rewrite system visualization
String rewrite system visualization
Adaptive Evolution of String Rewriting Systems
Adaptive Evolution of String Rewriting Systems
We began our journey with string rewriting systems. These are simpler and faster to work with than hypergraph rewriting systems, making them a good starting point for understanding and implementing adaptive evolution step by step. Our approach is similar to the one used by Willem Nielsen, with a few optimization tweaks.
The goal is to find rewriting rules that generate a system with finite lifetime.
Mutation Function
Mutation Function
An example of a string rewriting rule is the following, which will substitute every A to AB, and every BA to C:
An example string rewriting rule
Out[]=
{AAB,BAC}
In a default string rewriting system, the subrules of a rewrite rule are applied in the order in which they appear in the list. Consider the following rule applied to the initial state A:
An example of a string rewriting rule in which application order matters
In[]:=
exampleOrder={"A"->"B","B"->"A","A"->"C"}SubstitutionSystem[exampleOrder,"A",10]
The first two subrules of the rewrite rule will continuously be applied, but the third rule will never be used.
There are many ways to mutate a string rewrite rule. For example, one can substitute a character with a different one, or add or remove characters within a subrule. In our approach, we follow Willem Nielsen’s method of mutating rules by adding or removing subrules from the rule list. This strategy offers a rich space of possible mutations while preserving subrules that have previously contributed to a high fitness of the system. To ensure new subrules are actually used, we add them to the beginning of the rule list. If they’re added at the end, they won’t have any effect if there are earlier subrules with the same left-hand side. In such cases, the rule can grow very long during evolution without meaningfully changing the system’s behavior. By inserting new subrules at the front, we reduce redundancy and keep rules shorter.
The characters of our string rewriting systems are the first four letters of the alphabet.
The characters of our string rewriting systems are the first four letters of the alphabet.
As an example, we show some possible mutations of the rule {A → AB, BA → C}.
Three examples mutating the rule {A → AB, BA → C}
Out[]=
{BAA,AAB,BAC} |
{BC,AAB,BAC} |
{AAB} |
Fitness Function
Fitness Function
Our goal is to find rules that evolve the system for a substantial amount of time, and then halt, i.e., create rules with a long but finite lifetime. To capture this behavior, we define the fitness of a string rewriting rule as the number of steps (or lifetime) the the system evolves before halting, given a pre-defined initial state. It is often not possible to determine whether a rewrite system will halt, or run forever. To deal with this, we introduce a boundary n, called the maximal lifetime. If a rewriting system evolves for more than n steps, we assume that it will not halt and assign it a fitness of zero.
Under this definition, the optimal rule is one that evolves for exactly n steps before halting, maximizing its lifetime without exceeding the boundary.
The fitness vs life time curve for our fitness function
Out[]=
To calculate the lifetime of a string rewriting rule, the entire rewriting process must be executed. However, if the rule causes the string to grow, the string can become very long, making the computation increasingly slow. To address this, we also impose a limit on the maximum string length allowed during evolution. If this length is exceeded at any point, the process is stopped early and the rule is assigned a fitness of zero.
As an example we calculate the fitness function of the following rule, which converges after three steps.
An example rule
Out[]=
{ABC,CD,BD}
The fitness of this rule for initial state “A”
Out[]=
4
The rewriting system of this rule
Out[]=
A |
BC |
DD |
DD |
DD |
DD |
As a small technical detail: in our implementation, the fitness is equal to the system’s lifetime plus one. This is due to how the FixedPoint function works in Mathematica; it includes the initial state as the first element in the evolution list, and repeats the final state twice at the end.
Results
Results
Running the adaptive evolution process for 5000 iterations with a maxFitness of 100 resulted in a rewriting rules with fitness up to 99. A beauty error that we made was not using random seeds in any of the methods. Every run will thus give a different result.
Evolve a string rewriting rule for 5000 iterations and show the result
Out[]=
rule{DDAD,DCBD,DAC,BCAA,AAC,BBBD,BDBA,CCAA,BACA,ACBB,CBAC,DAC,AD},fitness98
To easily see the structure of the string rewriting system, we assign a color to each letter.
Visualize the string rewriting system.
Out[]=
Random String Rewrite System | Rule 99 String Rewrite System |
Adaptive Evolution of Hypergraphs
Adaptive Evolution of Hypergraphs
Next, we experiment with the adaptive evolution of hypergraphs. The setup is very similar to that of string rewriting systems. The only major differences lie in the mutation function and the fitness function. In this section, we explore two different fitness functions, each optimizing for a different metric.
As initial rules, we began with simple→ hypergraph rules, which consist of a single node and self-loops. Next, we wondered what would happen if we used rules from the Registry of Notable Universe Models as starting points and evolved to have a finite lifetime.
As initial rules, we began with simple
2
3
5
3
Mutation Function
Mutation Function
Hypergraph rewrite rules are expressed as tuples of node numbers.
An example hypergraph rewrite rule and its plot
Out[]=
{{1,1,1},{1,2,3}}{{2,2,2},{1,2,3}} |
As with string rewrite rules, there are many possible ways to mutate a hypergraph rewrite rule. For example, one could add or delete tuples from either the left- or right-hand side, modify the nodes within one of the tuples, substitute whole edges, or substitute one or more nodes. However, some of these mutations can cause the rule to grow very large, which significantly slows down the evolution process. To avoid this, we use a simpler mutation strategy: we randomly change a single node in the rule, replacing it with either an existing node or a new one. This keeps the overall size of the rule constant and helps maintain performance. An important implementation detail is that after each mutation, the rule is transformed back into its canonical form. Without this step, node numbers tend to grow unnecessarily, which increases the chance of introducing nodes that haven’t yet appeared in the system, leading to unintended complexity.
We show an example of three different mutations of the above rule.
Three examples of mutating the rule {{1, 1, 1}, {1, 2, 3}} {{2, 2, 2 }, {1, 2, 3}}
Out[]=
Fitness Functions
Fitness Functions
For the adaptive evolution of hypergraphs, we implemented two different fitness functions. The first fitness function counts the number of nodes in the final state of the hypergraph system, only if the system reaches a fixed point. If it doesn’t halt, the fitness is zero. The second fitness function measures the lifetime of a rule: the number of successful rewrite steps before the system halts. As with string rewriting systems, we introduce a cutoff: if the number of rewrites exceeds a certain limit, we assume the system doesn’t halt and assign a fitness of zero.
Just as very long strings can slow down string rewriting systems, hypergraph rewriting becomes increasingly slow when the number of nodes or edges grows large. To manage this, we also set generous upper bounds on the number of nodes and edges. According to our fitness definition, the best a rule can do is evolve into a final state that reaches (but doesn’t exceed) these size boundaries.
As an example, calculate the two different fitness functions of the following finite hypergraph rewriting system.
Just as very long strings can slow down string rewriting systems, hypergraph rewriting becomes increasingly slow when the number of nodes or edges grows large. To manage this, we also set generous upper bounds on the number of nodes and edges. According to our fitness definition, the best a rule can do is evolve into a final state that reaches (but doesn’t exceed) these size boundaries.
As an example, calculate the two different fitness functions of the following finite hypergraph rewriting system.
An example hypergraph rewriting rule and the rewrite system it creates
Out[]=
{{1,1,2},{3,4,5}}{{6,4,3},{4,1,7},{2,8,1}} |
Calculate the node fitness function of the rule above
Calculate the life time fitness function of the rule above
Mutate the initial rule for 500 steps, with a cutoff of 100 vertices
Using this evolution process, we were able to evolve a rule with fitness of 99 (and thus 99 nodes in its final state). We show this rule below.
The rule we evolved with fitness of 99, and its rewriting process
For completeness, we also show its causal graph.
The causal graph of the above rule
Using Rules from the Registry of Notable Universe Models as Initial Rules
Using Rules from the Registry of Notable Universe Models as Initial Rules
Next, we wanted to see what kinds of rules would emerge when using rules from the Registry of Notable Universe Models as starting points. In particular, we were interested in what would happen if we evolved these already interesting rules into ones with a long, but finite, lifetime. This is why we switched to using the lifetime-based fitness function from this point onward.
wm1167
wm1167
Rule 1167 and its final state after 200 iterations
We used the following code to evolve rule 1167 over 500 evolutionary iterations, with a maximum allowed lifetime of 100 for each candidate rule.
Evolve rule 1167 for 500 iterations
After repeating the experiment three times, we found rules with fitness values of 32, 31, and 24, respectively. These are unfiltered result, we didn’t do any cherry picking. Below, we show plots of the rules and their corresponding final states.
Rules found after 500 iterations
Wondering whether we could achieve a higher fitness, we ran the evolution process for 1000 iterations.
Evolve rule 1167 for 1000 iterations
Rules found after 500 iterations
In the hope of evolving these already high-fitness rules into ones with even higher fitness, we ran the evolution process on the last two rules for an additional 1000 iterations, during which the rules no longer changed.
Below are our results, showing the evolved rules, their fitness (lifetime), and plots of their final states. We also show a plot of how the fitness of each of the rules changed during the evolution process.
Below are our results, showing the evolved rules, their fitness (lifetime), and plots of their final states. We also show a plot of how the fitness of each of the rules changed during the evolution process.
Fitness, rewrite rule and final state plot of the evolved rules
Fitness per iteration of each of the evolved rules
We will now show the evolution process of my two personal favorites, which are the rules with fitness 32 and fitness 50.
Fitness 32
Show the rewriting process of the found rule with fitness 32
Show the rewriting process of the found rule with fitness 50
Different rewrite orders
It would be very interesting to take one of the evolved rules and generate its full multiway system to check whether all branches terminate. However, creating a multiway system for such a long-lived rule requires significant computational resources and time due to combinatorial explosion. To get a sense of how these rules behave under different rewriting orders, we selected the rule with fitness 50 and generated its final state plot for twenty different random rewriting orders. All of them terminated within 1000 iterations. This is of course just a random selection and we cannot know for sure whether every branch of the multiway system would halt or not. Below, we show the final state plot for five different rewriting orders.
Final state plot, causal graph, termination reason and lifetime of the fitness 50 rule applied using five different random rewriting orders
wm1268
wm1268
Rule 1268 and its final state after 200 iterations
We ran the evolution two times, with the same parameters as before for 1000 iterations, and evolved the following two rules.
Two rules we evolved starting from rule 1268 after 1000 iterations
It’s remarkable that running the evolution process twice can result in significantly different fitness outcomes.
Adaptive Evolution of Hypergraph Multiway Systems
Adaptive Evolution of Hypergraph Multiway Systems
Finally, we arrive at the last stage of our journey: the adaptive evolution of hypergraph multiway systems. As before, we define a fitness function and a mutation function, and then present some results. Since hypergraph multiway systems are computationally intensive, we focus on smaller examples here and leave the exploration of larger systems for future work.
Fitness Function
Fitness Function
As a fitness function for hypergraph multiway systems, we count the number of nodes in the full multiway system. Since paths in a multiway system can grow combinatorially with each generation, computation becomes expensive very quickly: four generations may take seconds, five may take minutes, and six can take hours, depending heavily on the rule and the number of branching paths. To ensure the system doesn’t get stuck, we set a maximum allowed computation time for constructing one multiway system. If building the multiway system exceeds this time limit, the rule is considered “too big,” assigned a fitness of zero, and we move on.
We show an example of a multiway system and its fitness.
We show an example of a multiway system and its fitness.
An example multiway system which halts after three generations
The fitness of this multiway system
Mutation function
Mutation function
To mutate the hypergraph multiway system, we use the same mutation strategy as in the adaptive evolution of hypergraphs, changing one random node in the rule.
Results
Results
Without using too much compute, we obtained some promising results. Running the system with a maximum lifetime of 5 for each branch of the multiway system, a 5-second time limit for generating the multiway graph, and only 50 iterations of the evolution process, we were able to evolve multiway systems with up to 12 nodes. For a maximum lifetime of 6, a 10-second time limit and 100 iterations, we found rules that created hypergraph multiway systems with a fitness up to 18. Starting with a rule consisting of only self-loops didn’t produce good results, typically yielding a fitness of 0 or at most 2. More iterations might improve this, but we were curious whether better results could be achieved more quickly by starting from a more sophisticated rule. For that reason, we used rule 1167 from the Registry of Notable Universes as the initial rule. This appeared to help, as we evolved multiway systems with fitness scores as high as 18.
It’s worth noting that the obtained fitness can vary significantly between runs. One run might result in a fitness of only 2, while another may reach 12. This variability is likely due to the low number of iterations and possibly the time cutoff, though we can’t make strong claims about this yet.
Below, we show five multiway systems that we evolved.
The following rules were found using a lifetime of 6, a 10 second time limit per multiway system and 100 iterations of the evolution process.
It’s worth noting that the obtained fitness can vary significantly between runs. One run might result in a fitness of only 2, while another may reach 12. This variability is likely due to the low number of iterations and possibly the time cutoff, though we can’t make strong claims about this yet.
Below, we show five multiway systems that we evolved.
The following rules were found using a lifetime of 6, a 10 second time limit per multiway system and 100 iterations of the evolution process.
Run the evolution process with maximum lifetime 6, 10 second time limit, and 100 iterations
Lastly, we show some of our previously found rules for which we used a smaller lifetime, time limit and number of iterations.
Show some interesting results we previously found with a lifetime of 5, a 5 second time limit, and 50 iterations
Concluding Remarks
Concluding Remarks
Using initial rules from the Registry of Notable Universes, we found several hypergraph rewriting rules that evolve the hypergraph for 24 to 54 steps before halting. We were also able to create small, halting multi-way hypergraph systems with up to 18 multi-way system nodes.
There is much more exploration to be done—especially with different initial states, fitness functions, and mutation strategies. One interesting direction is to explore a broader range of rules from the Registry of Notable Universes and investigate potential relationships between the structure of the initial rule and the properties of its evolved descendants. It would also be valuable to run adaptive evolution with larger parameters to construct bigger and more complex hypergraph multi-way systems.
Overall, our experiments suggest that adaptive evolution is a fruitful and flexible method for discovering structured, finite behaviors in a variety of rewriting systems.
There is much more exploration to be done—especially with different initial states, fitness functions, and mutation strategies. One interesting direction is to explore a broader range of rules from the Registry of Notable Universes and investigate potential relationships between the structure of the initial rule and the properties of its evolved descendants. It would also be valuable to run adaptive evolution with larger parameters to construct bigger and more complex hypergraph multi-way systems.
Overall, our experiments suggest that adaptive evolution is a fruitful and flexible method for discovering structured, finite behaviors in a variety of rewriting systems.
Acknowledgments
Acknowledgments
I would like to thank my mentor, Dugan Hammock, for his help, ideas, and endless encouragement throughout this process, and for believing in me. Thank you to Bowen Ping for helping me with the layout of all of my graphics and for the productive work sessions. Eric Parfitt, thank you for your interest in my project and for the input you gave whenever I felt stuck. I’m also grateful to Willem Nielsen for the research I could build on, and for taking the time to answer all my questions. A special thank you to Stephen Wolfram for providing the project idea. Lastly, I want to thank all the friends I made during this journey for the shared working sessions, thought-provoking conversations, and constant support.
References
References
1
.Willem Nielsen (2025), “Hypergraph Rewriting and Computational Formalizations in Biology”, https://amoeba.wolfram.com/index.php/s/RFajdxPCb3SRnRY?dir=undefined&openfile=36774140 .
2
.Stephen Wolfram (2024), “Foundations of Biological Evolution: More Results & More Surprises,” Stephen Wolfram Writings. writings.stephenwolfram.com/2024/12/foundations-of-biological-evolution-more-results-more-surprises.
3
.Stephen Wolfram (2024), “Why Does Biological Evolution Work? A Minimal Model for Biological Evolution and Other Adaptive Processes,” Stephen Wolfram Writings. writings.stephenwolfram.com/2024/05/why-does-biological-evolution-work-a-minimal-model-for-biological-evolution-and-other-adaptive-processes.
4
.Cite This Notebook
Cite This Notebook
Adaptive Evolution of Hypergraph Rewriting Systems
by Anneline Daggelinckx
Wolfram Community, STAFF PICKS, July 9, 2025
https://community.wolfram.com/groups/-/m/t/3497465
by Anneline Daggelinckx
Wolfram Community, STAFF PICKS, July 9, 2025
https://community.wolfram.com/groups/-/m/t/3497465