Euler Who? The Original Optimizers: Heterocephalus glaber and Their Algorithmic Society

Keywords: Naked mole rat, graph theory, optimization, eusocial, mating, algorithm

Abstract

Owing to its eusocial organization, the naked mole rat emerges as a model species exemplifying principle of biological optimization. The design solutions associated with this behavior seamlessly translate into algorithmic capabilities: the positive feedback of workers achieving appropriate fitness to become breeders; the fittest breeders mating with the queen; the negative feedback of breeders getting demoted in the caste to become workers; the queen optimizing for the best possible breeder to mate with; and the cooperation and competition to determine rank in the colony which creates multiple interactions between males. These eusocial dynamics extend beyond their biological roots to address complex mathematical challenges. This paper examines the development and application of the naked mole rat Algorithm as a graph-theory-inspired optimization tool, rooted in these cooperative behaviors. It further explores the algorithm’s performance in unimodal, multimodal and fixed functions highlighting its versatility and effectiveness. Furthermore, compared with other nature-inspired algorithms, the naked mole Rat Algorithm offers unique strengths in achieving decentralized, scalable, and efficient solutions. Thus, through the lens of the naked mole rat algorithm and its efficiency in finding optimal solutions in a timely manner, this paper concludes that the representation of the eusocial caste system as an algorithm captures both the abilities and limitations of the colony's mate optimization capabilities.

Introduction

The naked mole rat (Heterocephalus glaber) inhabits complex, extensive underground tunnel systems in the arid regions of East Africa. These tunnels serve multiple functions beyond just travel pathways; they are carefully constructed to optimize temperature control, predator defense, and resource management (Sherman, Jarvis, & Alexander, 1991). Moreover, the naked mole rat is among the few vertebrates that exhibit eusociality, a complex social organization usually found among some insects like bees and ants (Jarvis, 1981). It exhibits a highly structured and rigid social hierarchy that supports its eusocial system, and this distinguishes it as one of the few mammals to show this level of social complexity. This form of social structure is characterized by a division of labor into reproductive and non-reproductive groups, the cooperative care of offspring, and a clear hierarchy that includes a dominant breeding pair (Salgotra & Singh, 2019).

In the case of the naked mole rat, the colony is typically led by a single breeding female, known as the queen (Salgotra & Singh, 2019). She is the only female in the colony that breeds and produces offspring, and she maintains her dominance through aggressive behaviors towards other females, effectively suppressing their reproductive capabilities (Hart et al., 2022). Beneath the queen are a few selected breeding males, who are allowed to mate with her. In naked mole rat colonies, most members are non-reproductive workers that are divided into castes based on their roles and tasks like foraging for food, defending the colony, supporting the tunnels, and caring for the queen's offspring (Sherman, Jarvis, & Alexander, 1991).

The structure of the colony serves as a good model for studying cooperative and adaptive behaviors in living systems (Spinks et al., 2000). These complex social structures are supported by an efficient and adaptive caste system that can transition workers to breeders when necessary. The differentiation and specialization within these roles are crucial for the colony’s survival, since they ensure efficient resource utilization, defense against predators, and overall stability (Clarke & Faulkes, 1997). The dynamic transition of roles within the colony where non-reproductive workers can become breeders occurs when the queen dies or when there is a shift in the colony’s needs. Conversely, reproductive roles can be relinquished to ensure optimal task allocation and resource management within the colony (Spinks et al., 2000).

The queen's role can be seen as a strategy to maximize the colony's reproductive output, while the workers' non-reproductive status minimizes internal conflict over breeding opportunities. The transition between roles in the naked mole rat colony is a key aspect of its social behavior and adaptability. When the queen dies and the colony faces internal pressures, non-reproductive females can transition to become new breeders, illustrating a flexibility in the naked mole rat’s rigid social order. As mentioned previously, this transition is accompanied by intensive competition among females, with the emergence of a new queen marked by shifts in aggressive behavior and social dominance (Hart et al., 2022). This competition and aggression over breeding rights is minimized due to the presence of the structured social hierarchy. On the other hand, most males are non-aggressive towards breeding opportunities as the queen selectively mates with a few males who are capable of reproduction (Clarke & Faulkes, 1997). This system of defined roles and controlled reproduction explains how conflict is minimized and how colony harmony is maintained.

Another interesting aspect of the naked mole rat’s social behavior is related to their communication system. The naked mole rat exhibits a complex vocal repertoire, in which distinct vocalizes are used for different purposes, including social bonding, recognition of colony members, and alerting others to threats (Barker et al., 2021). Each colony has its own dialect that helps the colony members to distinguish its members from others. This shows that they can recognize and protect themselves against external threats. This communication system not only supports efficient coordination but also helps maintain the rigid social hierarchy, as interactions with the queen and higher-ranking members are often marked by specific behaviors and vocal cues. Communication extends beyond just vocalizations since the naked mole rat depends on other aspects, such as tactile cues and scent marking with their intricate tunnel systems to convey information related to territory boundaries, food availability, and reproductive status (Brett, 1991).

The naked mole rat also has remarkable physiological adaptations that support their lifestyle and contribute to its colony’s resilience. It has a highly efficient metabolism that allows it to thrive in hypoxic environments (Park et al., 2017). This metabolic adaptation ensures that all members, regardless of their caste, can perform their tasks even under conditions such as limited oxygen availability. These physiological traits contribute to the longevity and stability of the colony, reinforcing the strict division of labor and ensuring that the queen’s reproductive output is maximized. This combination of behavioral, communicative, and physiological adaptations allows naked mole rat colonies to function as highly organized and efficient units that can adapt to a wide range of environmental and social pressures.

The cooperative and adaptive behaviors of the naked mole rat, including efficient task allocation, role transitions, and environmental responsiveness, makes it an excellent model for the development of computational algorithms due to its ability to optimize complex systems and adapt to changing conditions. These behaviors lend themselves to the creation of optimization algorithms inspired by natural processes (Salgotra & Singh, 2019).

Graph Theory

Preface 

Before exploring the intricacies of graph theory and the significance of this field of mathematics, it is important to understand its historical context. In 1735, Leonhard Euler sought to solve the Königsberg bridge problem. This problem posed a deceptively simple question: Is it possible to walk through the city of Königsberg, crossing each of its seven bridges exactly once? (Editors of www.encyclopediabritannica, 2024).

Fig. 1. The map of Königsberg and its 7 bridges. The challenge was as follows: visitors would attempt to explore the city of Königsberg whilst only crossing each of the 7 bridges once.

Euler's proved this feat was impossible with a rudimentary form of graph theory, in which he represented each landmass as a node and each bridge as an edge and set mathematical constraints according to this challenge. This elegant solution to the optimization problem that stumped mathematicians for many years thus laid the foundation for a novel field of mathematics. As this field evolved, it became integral to various disciplines, including computer science, biology, and social network analysis. These algorithms are often inspired by biological processes, which have the intrinsic ability to solve complex optimization challenges. These nature-inspired algorithms rely on principles of cooperation, adaptation, and efficiency, in which they mimic phenomena like foraging, flocking behavior, and genetic evolution. However, to fully appreciate the elegance and utility of these algorithms, the jargon surrounding this field of mathematics must be explored.

Basic Graph Theory Terminology 

Graph theory is defined as the branch of mathematics and computer science that studies the relationships between objects connected by edges. The objects can be seen as individual entities or points on a graph and are represented by vertices or nodes. The connections between nodes are called edges or links. These edges can be used to show the relationships between different nodes, as seen in Figure 2 below (Diestel, 2018).

Fig. 2. Pictorial representation of vertices and edges to start the reader’s intuition on graph theory. The vertices are represented by the circled letters and the edges are represented by the lines connecting these circles (Rote, 2023).

Directed versus undirected graphs are another important concept to understand. In an undirected graph, edges have no direction, which means that the connections between nodes are bidirectional. In contrast, a directed graph features edges with a defined direction, called arcs, which represent one-way connections. These graphs are crucial for modeling directional processes like resource flow or information transfer. The distinction is illustrated in Figure 3 below (Diestel, 2018).

Fig. 3. Pictorial representation of directed versus undirected graphs. Notice that directed graphs have arrows which indicate the direction of flow whereas undirected graphs do not have any directionality in their edges (Editors of https://cs226fa21.github.io/notes/26-graph/step05.html, 2024).

Another similar concept can be seen in the difference between weighted and unweighted graphs. Unweighted graphs are graphs in which all edges are treated as equal, without any preference or cost associated with a specific edge. Weighted graphs are graphs where each edge has an associated numerical value or weight: the weight represents costs, distances, or other metrics. The weight placed on a certain connection is important for modeling real-world scenarios like transportation networks or communication systems, as it specifies the relative favorability or efficiency of certain routes over others (Diestel, 2018). The concepts of weight and directionality can be combined to represent complex systems, as seen in figure 4 below.

Fig. 4. This graph shows the difference between weighted and unweighted graph while also building on the previous concepts on directionality. On the left, notice the numerical values, or weights, placed on each edge. On the right, notice that the edges do not have a specific weight associated with them, which means that any edge can be taken without a bias (Editors of https://afteracademy.com, 2020).

Characteristics of a Graph

Now that the basic kinds of graphs have been established, there are certain characteristics used to describe graphs, which are important to develop a sense of intuition with graph theory. The degree of a node is described as the number of edges that are connected to a specific node. A node with a large degree has many connections to other nodes. For example, in Figure 2, node B has a degree of 3 since it has three incident edges.

The path is the sequence of nodes where each consecutive pair is connected by an edge. To put this concept into context, the Königsberg bridge problem is set to find a path connecting all 7 nodes where each node is passed once. Additionally, a cycle is a specific type of path that starts and ends at the same node without repeating any edges or vertices. Thus, all cycles are paths, but not all paths are cycles. The difference between a path and a cycle can be understood through a simple analogy: walking your dog to your friend's house represents a path, as it has a clear start and endpoint, whereas walking your dog around the block represents a cycle, as it begins and ends at the same point (Diestel, 2018).

The final term to understand is the distinction between connected and disconnected graphs, in which connected graphs have paths connecting all nodes whereas disconnected graphs do not possess this characteristic. This difference can be seen in Figure 5 below (Diestel, 2018).

Fig. 5. The difference between connected and undirected graphs. Notice the difference in connected nodes between these two graphs. On the left, notice the connected graph where all the vertices are connected by edges. On the right, notice the disconnected graph where the right-most vertex is not connected to the rest of the graph by an edge (Rote, 2023).

Optimization in Graph Structures 

It is very easy to get lost in the graph theory jargon and lose sight of the big picture. It is important to remember the goal of an algorithm, which is to solve an allotted problem. Now that a basic understanding of the framework of this theory was established, the more interesting aspects that this field of mathematics unlocks can be explored.

Optimization solutions find the most efficient solution to a problem, such as the shortest path between two nodes, by leveraging the structural relationships and characteristics of the specific graph. Just like in calculus, the best overall solution is referred to as a global optimum (maximum or minimum), as seen in figure 6. Accordingly, the local optimum refers to a solution that is better than its immediate neighbors but may not be the best overall solution.

Fig. 6. This graph shows the difference between a local maximum and global maximum in a 3-dimensional function. This representation can be extended to a local optimum versus a global maximum (Luo, 2022).

However, algorithms are not without limitations and often face challenges. One such challenge is premature convergence, in which the algorithm quickly settles on a suboptimal solution. These suboptimal solutions can cause the algorithm to stagnate and cease its progression, as it gets stuck oscillating around a suboptimal solution space. Thus, these challenges highlight the importance of balance in an algorithm: it must maintain sufficient exploration, which is the algorithm's active search for new areas of the solution space, while ensuring effective exploitation, in which the algorithm refines already-known optimal solutions (Gentile et al., 2021).

Dynamic interactions help algorithms explore solutions effectively and adapt to complex problems. These interactions involve repulsion and attraction, which allow an algorithm to balance its exploration and exploitation. Attraction draws solutions closer for refinement, while repulsion spreads them apart to explore diverse regions to ultimately prevent premature convergence. Fluctuations, which are random variations or disturbances, introduce a sense of randomness to the algorithm. This randomness allows algorithms to escape local optima by enabling the exploration of alternative solutions. Multiple interactions, which refer to the simultaneous influence of various factors, create a dynamic landscape in an algorithm. This landscape creates adaptability and enables algorithms to respond to a problem's complexity while it adapts its search strategy (Gentile et al., 2021).

Nature-inspired algorithms mimic biological processes to maintain diversity, escape local optima, and dynamically adjust parameters. These changes to the structure of a typical algorithm led to more robust optimization strategies. One advantage of these algorithms is their initialization techniques, in which they ensure diverse starting points and introduce random perturbations to further enhance their ability to achieve global optimization (Gentile et al., 2021). Through nature's inspiration, these algorithms achieve solutions that closely emulate the efficiency found in natural systems.

Swarm-inspired Algorithms: a Bridge to the Naked Mole Rat Algorithm

Swarm-inspired algorithms are a subset of nature-inspired optimization techniques that model the collective behavior of decentralized systems. These algorithms excel at solving complex optimization problems by mimicking self-organization and cooperative behavior found in biological phenomena such as ant foraging and bird flocking.

Central to swarm algorithms is the concept of fitness values, which measure the quality of a solution. Fitness is an important concept that guides the balance between exploration and exploitation in SWARM algorithms. Successful algorithms can dynamically adapt this balance, as they leverage the collective intelligence of agents to escape local optima and converge on the global optimum.

By incorporating mechanisms such as repulsion, attraction and fluctuations, Swarm algorithms are particularly well-suited to addressing challenges like premature convergence and stagnation, which often arise in traditional optimization methods (Gupta, 2021).

The Naked Mole Rat Algorithm

The Algorithmic Behavior of the Naked Mole Tat Colony

The naked mole rat colony exhibits self-organization and division of labor, which is characteristic of a swarm inspired algorithm. Self-organization can be subdivided into positive and negative feedback, fluctuations, and multiple interactions. In the context of eusocial behavior, positive feedback is the increase in probability of males mating with the queen. The magnitude of the probability increases as workers become breeders and eventually mating with the queen. Negative feedback is the decrease in probability of males mating with the queen. If a breeder is not fit to breed, he is demoted to the worker caste: this fall in the hierarchy can be recognized as negative feedback. Fluctuations in the colony are demonstrated by both the randomness of the male with the highest initial probability of mating and the choice of the queen in the colony. Multiple interactions are displayed by the cooperation among the colony. As a result of the cooperation, the naked mole rat colony displays a complex division of labor. By having members of the colony perform specialized tasks, all tasks can be simultaneously performed, which is more beneficial than unspecialized members performing tasks sequentially. This drastically improves the efficiency of the colony (Salgotra and Singh,2019).

Fig. 7. The naked mole rat caste system. This figure demonstrates the movements within the caste system to find the most optimal mate for the queen. This system can be modeled as an algorithm to solve optimization problems (Salgotra and Singh,2019).

The Colony Modeled as an Algorithm

In 2019, Solgota and Singh proposed a naked mole rat algorithm that focuses specifically on the mating patterns of the naked mole rat colony, built upon four rules inspired by these mating patterns. The proposed algorithm uses a colony with a population of 50. This creates a connected graph with 50 different vertices. A female queen divides the population among breeders and workers, with no overlap between the roles of breeders and workers. It should be noted that the queen is identified as the vertex with the highest degree. The edges connecting workers to the queen are assigned higher weights than those connecting breeders to the queen to reflect their differing probabilities of interaction. In this algorithm, edge weight directly influences the likelihood of traversing a solution, with higher weights decreasing the probability of a path being taken. The colony structure is dynamic: the best-performing workers are promoted to breeders, while underperforming breeders are demoted to workers, which leads to continuous updates in edge weights as the algorithm progresses. Ultimately, the top-performing breeders are selected to mate with the queen: this makes the graph unidirectional, with all edges converging toward the queen. This iterative process mimics optimization, as the algorithm seeks to identify the "best breeder," or the optimal solution to the problem it addresses.

The algorithm begins by analyzing the male population and dividing members into the worker caste and breeder caste. The fitness of the breeders and workers is continuously reassessed, and the weights of the different edges are continuously updated. The worker’s fitness is constantly artificially improving, to increase the probability that they will become a breeder. In terms of the graph, the edge weights between workers and the queen are artificially improved to increase the likelihood of workers being promoted to breeders. On the other hand, the breeders’ fitness is determined by their probability of mating with the queen. If a breeder's probability falls below a certain threshold, they are demoted to the worker caste: this threshold dictates whether a vertex is associated with workers or breeders and evolves throughout the algorithm. The fittest workers then replace demoted breeders to maintain a dynamic cycle of reassessment and optimization (Salgotra and Singh, 2019).

The Phases of the Algorithm

The algorithm contains three distinct phases: initialization, worker, and breeder. In initialization, the population of the naked mole rats is uniformly distributed, and each member is defined as a vector (1,2…n). The number of dimensions of the vector is determined by the number of variables or parameters present in the problem. The initialization of each naked mole rat can be described by the following equation.

The variables can be defined by the following: i ϵ [1,2,…n], j ϵ [1,2,…n] where NMR_i,j is the i^th solution in the j^th dimension, NMR_min,j and NMR_max,j are the lower and upper bounds of the problem and U(0,1) is a random number responsible for the fluctuations within the algorithm. Upon initialization, the objective function is evaluated, and its initial fitness is calculated. Breeders and workers are identified depending on an individual’s relative fitness. The breeder with the best fitness is recognized as the best initial solution.

The next phase, referred to as the worker phase, can then begin. In this phase, the workers’ fitness gradually improves as a factor of the workers’ experience, as well as new local information. If the experience and local information can provide the members with better fitness, the old solution is discarded and the new solution is integrated. This mechanism is determined by the following equation:

The variables can be defined by the following: w^t_i is the i^th worker in the t^th interaction whereas w_i^t+1 is the new solution. Furthermore, w^t_j and w^t_k are two random solutions chosen from the pool of workers, and λ is a uniform distribution from [0,1].

Finally, the breeder phase determines the final and most optimal solution. The breeders update themselves in a similar fashion. However, in conjunction with fitness, the breeders are sorted on their breeding probability with respect to the best solution. Breeding probability is determined by a random number in [0,1]. If the fitness of the breeder is too low, they will be pushed back down to the worker caste. These mechanisms are determined by the following equation.

The variables can be defined by the following: b_i^t is the breeder i in the t^th iteration; λ is a factor that controls mating frequency, which helps define the new breeder b_i^t+1. Initially, the breeding probability (bp) is set at 0.5. If U (0,1) is greater than the bp, the breeder phase is performed. The algorithm will cycle through these phases in multiple iterations until the best solution is found.

Thus, the naked mole rat Algorithm leverages graph theory concepts to represent the colony as a directed graph where vertices signify individuals, and weighted edges reflect dynamic relationships. This algorithm then employs mathematical equations to model fluctuations in edge weights, which simulate optimization and hierarchical changes within the colony (Salgotra and Singh, 2019).

Performance of the Algorithm

Algorithm performance is generally evaluated by its ability to find optimal solutions efficiently and consistently across various test scenarios. To test the performance of the naked mole rat algorithm, Salgota and Singh used a twofold approach. The researchers evaluated the algorithm's performance on test problems by comparing its results to those of standard algorithms and conducting a rank-sum test to identify statistically significant differences. The standard algorithms the researchers used were the differential evolution algorithm, the firefly algorithm, the flower pollination algorithm, and the bat algorithm. They used a variety of test problems ranging from unimodal, multimodal, and fixed dimension functions. The unimodal functions have no local solution and only contain a single global solution. Unimodal functions are helpful to determine convergence rate, since there is no risk of the algorithm stagnating at a local minimum. The multimodal functions had many local minima, which allows the researchers to determine the algorithm’s ability to avoid local minima and show the algorithm’s balance between exploration and exploitation. The fixed dimension functions maintain a consistent number of dimensions, which tests the algorithms consistency in finding optimal solutions.

To evaluate the naked mole rat algorithm's rate of convergence, nine unimodal functions were tested: one of which was the Tablet function, which can be seen below.

The naked mole rat algorithm performed very well, with a final fitness value of 2.22 x 10^-9. Furthermore, it converged to its solution much faster than the other algorithms, as seen in Figure 8.

Fig. 8. Results from the Tablet function test of the naked mole rat (NMR), differential evolution (DE), firefly (FA), flower pollination (FPA), and the bat (BA) algorithms. A lower fitness value signifies a more optimal solution. As illustrated by the graph, the NMR algorithm demonstrated faster convergence toward the optimal solution compared to the other algorithms, highlighting its superior optimization efficiency. Of the eight other unimodal tests done, the naked mole rat algorithm showed the fastest convergence rate in seven: it should be noted that it was outperformed by all the other algorithms in only one of the functions tested. Thus, these results demonstrate that the naked mole rat algorithm possesses a great convergence rate in optimization problems.

In terms of multimodal tests, one of the functions tested was the Ackley function, seen in the equation below.

The simulation of the algorithm applied to the Ackley function showed that the naked mole rat algorithm was the only one to find an optimal solution, as seen in figures 9 and 10. The fitness value, in which lower values denote more optimal solution, was only 3.76x10^-12, whereas the next best algorithm, being the firefly algorithm, was 2.82x10^-2. Of the twelve multimodal functions tested, the naked mole rat algorithm achieved the best performance in nine and demonstrated comparable results in the remaining three. This outstanding performance in the multimodal tests shows that the naked mole rat algorithm’s ability to effectively avoid local minimum.

Table 1. Results of the Ackley function test of the naked mole rat (NMR), differential evolution (DE), firefly (FA), flower pollination (FPA), and bat (BA) algorithms. Best, worst and mean signify the associated fitness values, in which a lower fitness value identifying a more optimal solution.

Fig. 9. Results of the naked mole rat (NMR), differential evolution (DE), firefly (FA), flower pollination (FPA), and the bat (BA) algorithms solving the Ackley function. It can be seen thet the naked mole rat algorithm found the most opitimal solution in much less iterations than the other algorithms.

The researchers further evaluated the algorithms using five distinct fixed-dimension tests. These tests assess an algorithm's ability to consistently achieve the same optimal solution, with a lower standard deviation indicating superior performance. Among the fixed-dimension functions tested was the Six Hump Camel function, where the naked mole rat algorithm exhibited the best performance, where it achieved the lowest standard deviation of 0.0201, as shown in Figure 11.

Table 2. Results of the Six Hump Camel function test of the naked mole rat (NMR), differential evolution (DE), firefly (FA), flower pollination (FPA), and bat (BA) algorithms. Here, the lowest standard deviation represents the best performance.

Nevertheless, the naked mole rat algorithm was outperformed in three of the fixed dimension functions while showing comparable results in one. These results demonstrate that the naked mole rat algorithm may have limitations in finding consistent optimization solutions to the same function (Salgotra and Singh, 2019).

Discussion

Multiple determinants of the algorithm's performance were found using a multitude of tests: these tests included unimodal, multimodal, and fixed dimension functions. Compared to standard algorithms, the naked mole rat algorithm performed very well in the unimodal and multimodal functions but was outperformed in the fixed dimension functions. High performance in unimodal and multimodal functions showed that the algorithm can find optimal solutions while avoiding local optima. However, its inadequate performance in fixed dimension functions showed that it is limited in its ability to repeatedly find the same optimal solution. In other words, this algorithm does not excel in its exploitation. These abilities and limitations of the naked mole rat algorithm are consistent with the behavior of the naked mole rat colony. The algorithm's ability to consistently identify an optimal solution mirrors the naked mole rat colony's capacity to select the most suitable breeder for the queen. Its effective avoidance of local optima is reflected by the colony’s dynamic adjustment of hierarchy within the caste system. Finally, the limitation in finding the same solution is also consistent with the eusocial caste system of the colony. The colony does not seek to find the single fittest breeder; rather, it prioritizes identifying a breeder that is sufficiently fit to breed with the queen in a timely manner.

Conclusion

This paper explores the naked mole rat algorithm as a representation for the eusocial behavior of the naked mole rat colonies, specifically in their ability to identify a highly suitable mate for the queen. It mimics the process of workers competing to become breeders and subsequently competing to mate with the queen. By mimicking this process, the algorithm finds the “best suiting male” to find an optimal solution to the problem. The naked mole rat algorithm was shown to be very effective at finding optimal solutions compared to other nature inspired algorithms. Thus, it can be concluded that the eusocial behavior of this species is a design solution to effectively find a suitable mate for the queen. These design solutions include the hierarchical shifts of males depending on their fitness, and the queen's choice for the best possible breeder to mate with.

The naked mole rat algorithm provides a deeper understanding of the behavior and purpose of the naked mole rat's social hierarchy. Thus, by developing nature-inspired algorithms, we uncover the intricate connections between complex mathematics and biology to showcase how evolutionary pressures drive the pursuit of optimal solutions.