Natural computing is a field of study that involves the use of natural systems, such as biological organisms or processes, to solve complex computational problems. Slime mold is one such natural system that has gained attention in recent years for its ability to solve optimization and decision-making problems in a novel and efficient way.
Slime mold is a simple organism that belongs to the group of protists, and it has the unique ability to move and grow towards food sources in a way that appears intelligent, despite lacking a central nervous system. Researchers have studied the behavior of slime mold and have found that it can solve a range of problems, from finding the shortest path between two points to optimizing transportation networks and even designing efficient computer algorithms.
The Physarum Optimization Algorithm is a computational model that simulates the behavior of slime mold to solve optimization problems. It is based on the observation that slime mold will spread out and grow towards food sources in the most efficient way possible, following the shortest path to connect different parts of its body. The algorithm works by representing a problem as a network and simulating the growth and propagation of slime mold agents along the network. The concentration of slime at each node indicates the optimal path between two points on the network.
While this piqued your curiosity regarding how an organism can lay paths to solving human problems, I believe what is necessary to grab here is the understanding of natural computing and how slime mold can be used as a model organism for solving complex problems. I do believe this in itself sets the stage for understanding the basic principles of the Physarum Optimization Algorithm and its potential applications.
To illustrate the Physarum Optimization Algorithm, I will use a straightforward example in this post, such as "finding the shortest path between two points on a network." As I alluded to previously, I would have to demonstrate how the algorithm works by spreading/propagating plasmodium agents throughout the network to replicate the activity of slime mold and demonstrating how the concentration of slime at each node shows the shortest path between two points. The algorithm works by simulating the behavior of slime mold to find the optimal path between two points.
Let’s take a look how Physarum Optimization Algorithm work:
We start by initializing the network and placing plasmodium agents at each node.
We then simulate the behavior of the agents by moving them along the network, based on a set of rules that mimic the behavior of slime mold. For example, the agents might move towards areas of high nutrient concentration (i.e., where other agents have traveled before) and avoid areas of low concentration.
As the agents move along the network, they leave behind a trail of slime that indicates the concentration of slime mold at each node.
We will then use the concentration of slime at each node to determine the shortest path between two nodes on the network. The path with the highest concentration of slime represents the optimal path between the two nodes.
By propagating plasmodium agents along the network and simulating the behavior of slime mold, we can find the optimal path between two nodes on the network. The concentration of slime at each node indicates the shortest path between the two points. This method is not only efficient but also provides a biologically-inspired approach to optimization and decision-making problems.
There are several areas slime molds can be used in decision-making. Some of the use cases is to use of the Physarum Optimization Algorithm to solve optimization problems in engineering and design. By representing the design problem as a network and simulating the behavior of slime mold, the algorithm can find the optimal configuration of components or materials to minimize cost or maximize performance.
One of the many advantages of the Physarum optimization algorithm is its ability to solve logistics problems efficiently, leading to cost reduction for logistics players. The Physarum Optimization Research Group conducted a comprehensive review on the optimization applications of Physarum polycephalum, a type of slime mold that has been used as a model organism for natural computing and optimization (Chu et al., 2021). In their review published in Swarm and Evolutionary Computation, the authors provide an overview of how Physarum polycephalum has been utilized to solve various optimization problems, including routing problems in communication networks, clustering problems in data mining, and optimization problems in engineering and design. The potential of Physarum polycephalum for future applications in areas such as robotics and swarm intelligence is also highlighted. This review serves as a valuable resource for researchers and practitioners interested in the use of slime mold-inspired algorithms for optimization and decision-making problems.
Now, let’s jump on it using python to exemplify slime molds actions as listed earlier.
First, we will import dependencies to carry out this Physarum Optimization Algorithm:
# Import dependencies
import numpy as np
import scipy.sparse as sparse
import networkx as nx
from queue import PriorityQueue
Next, we will initialize graph through networkx
and add edges to it:
# Initialize the network
G = nx.Graph()
G.add_edges_from([(0,1), (1,2), (2,3), (3,0)])
This initializes an undirected graph G
and adds edges between four nodes (0,1)
, (1,2)
, (2,3)
, and (3,0)
.
Then, we can initialize the parameter, such as plasmodium agents, rate of slime evaporation (this is a natural attitude of slime molds), concentration of slime at each node, etc:
# Initialize the parameters
N = 100 # number of plasmodium agents. For test purposes, you can lower this number to 10 or thereabout
evaporation_rate = 0.1 # rate of slime evaporation
slime_concentration = sparse.csr_matrix((1, len(G.nodes))) # concentration of slime at each node
plasmodium = np.zeros((len(G.nodes)))
These lines/block initialize the parameters used in the simulation. N
is the number of plasmodium agents that will be simulated, evaporation_rate
is the rate at which the slime will evaporate, and slime_concentration
is a sparse matrix that represents the concentration of slime at each node.
Once we have initialized the parameters, I believe we can we can randomly generate the start node and the end node for the plasmodium agent to propagate between:
start_node = np.random.choice(list(G.nodes))
end_node = np.random.choice(list(G.nodes))
This is as a result of wanting the plasmodium agent to propagate between start_node and end_node. Another possibility is to generate a static start_node and end_node, however, it will make our code less robust. So it is better we have randomness just to see the beauty of slime mode based algorithm.
Now let’s propagate the plasmodium:
queue = PriorityQueue()
queue.put((-plasmodium[start_node], start_node))
while not queue.empty():
current_node = queue.get()[1]
if current_node == end_node:
break
neighbors = list(G.neighbors(current_node))
if len(neighbors) == 0:
break
for neighbor in neighbors:
next_concentration = plasmodium[current_node] / len(neighbors)
if next_concentration > slime_concentration[0, neighbor]:
slime_concentration[0, neighbor] = next_concentration
queue.put((-next_concentration, neighbor))
plasmodium[neighbor] += plasmodium[current_node] / len(neighbors)
# Update the slime concentration at each node
slime_concentration *= (1 - evaporation_rate)
This block propagate the plasmodium agent along the graph using a priority queue data structure. The queue is initialized with the start node and its corresponding plasmodium value. In the while loop, the current node is retrieved from the queue, and if it matches the end node, the loop is broken. The neighbors of the current node are retrieved and if there are no neighbors, the loop is broken. For each neighbor, the next slime concentration is calculated based on the current plasmodium concentration and the number of neighbors. If the next concentration is greater than the current slime concentration at the neighbor node, then the slime concentration is updated, and the neighbor is added to the queue with the next concentration value. The plasmodium concentration at the neighbor is also updated based on the current concentration and the number of neighbors.
Under the same while..loop, we then updates the slime concentration at each node by multiplying it with the evaporation rate.
At this point, we have done a great job with propagation. Knowing how slime molds work, it is certain you can never get O(1) time complexity in this algorithm. But you can make it better by having an optimized algorithmic complexities for this Physarum (Slime) Optimization Algorithm. You may have to look at the videos in the references to understand leads with slime molds and start thinking how better you will rewrite this code.
We can now apply the method created thus far to determine the shortest path between two nodes depending on the concentration of slime, as we can do so by including the excerpt below:
path = [start_node]
while path[-1] != end_node:
neighbors = list(G.neighbors(path[-1]))
next_node = neighbors[np.argmax(slime_concentration[0, neighbors])]
path.append(next_node)
These block finds the shortest path between the start node and the end node based on the slime concentration at each node. The current node is initialized with the start node, and while the current node is not equal to the end node, the neighbors of the current node are retrieved, and the next node is selected based on the maximum slime concentration among the neighbors. The next node is then added to the path, and the loop continues until the end node is reached.
We can now output the shortest path using the print()
function:
# Print the shortest path
print(path)
By output of the print statement, in the code we have written, for the first simulation, I got [2, 1, 0]
. Don’t forget there is randomness in the start and end node, so we will always get differing outputs and that is indeed peculiar to slime molds. If we assume the start node is 0
and the end node is 3
. The path
list is initialized with the start node, and we continue to append the neighbor with the highest concentration of slime until we reach the end node.
In this case, the shortest path between node 0
and node 3
based on the slime concentration is [0, 1, 2, 3]
. However, the actual path found by the algorithm in this specific run of the simulation happened to be [2, 1, 0]
. This is due to the randomness involved in the simulation - the plasmodium agent starts from a random node, and the algorithm selects random end nodes for each run.
Overall, this code generates a network and initializes plasmodium agents to propagate along the network, updating the slime concentration at each node based on the agent's movement. The shortest path between two randomly generated nodes is then calculated based on the slime concentration at each node.
This algorithm can be useful in modeling the movement of agents or particles in a network and finding the most efficient path between two points based on some criteria. You can find the complete repository on my github (https://github.com/AfolabiOlaoluwa/physarum_optimization_algorithm).
After exploring the Python code that exemplifies how the slime mold algorithm works, we can conclude that natural computing and biological-inspired algorithms are powerful tools for solving complex optimization problems. Slime molds, despite lacking a centralized nervous system, are able to solve complex decision-making problems by adapting their growth patterns in response to environmental stimuli. By understanding how slime molds work, we can develop new algorithms and computational models that mimic the behavior of these organisms and apply them to a wide range of real-world problems, such as urban planning, logistics, and transportation.
Moreover, the study of natural systems can also inspire us to develop more sustainable and efficient approaches to problem-solving. Slime molds, for example, are able to solve optimization problems with minimal resources and energy consumption, making them a potential source of inspiration for the development of more energy-efficient and eco-friendly computing technologies.
In conclusion, the study of natural computing and biological-inspired algorithms not only allows us to solve complex problems more efficiently, but it also provides us with a new perspective on how to approach problem-solving in a more sustainable and nature-inspired way.
Reference:
Wired. "Mycologist Explains How a Slime Mold Can Solve Mazes." Online video clip. YouTube. YouTube, 5 April 2018. https://www.youtube.com/watch?v=7YWbY7kWesI.
Biographic. (2016, June 7). Lens of Time: Slime Lapse. https://www.biographic.com/lens-of-time-slime-lapse/. .
Chu, D., Ma, W., Yang, Z., Li, J., Deng, Y., & Cheong, K. H. (2021). A comprehensive review on the optimization applications of Physarum polycephalum. Swarm and Evolutionary Computation, 64, 100937. doi: 10.1016/j.swevo.2021.100937.
L. Liu, Y. Song, H. Zhang, H. Ma, and A. V. Vasilakos, "Physarum Optimization: A Biology-Inspired Algorithm for the Steiner Tree Problem in Networks," in IEEE Transactions on Computers, vol. 64, no. 3, pp. 818-832, March 2015, doi: 10.1109/TC.2013.229.
A Hagberg, D Schult, P Swart, Exploring Network Structure, Dynamics, and Function using NetworkX in Proceedings of the 7th Python in Science conference (SciPy 2008), G Varoquaux, T Vaught, J Millman (Eds.), pp. 11-15.