Abstract
This paper introduces Memetic Networks (MNAs), a novel class of multi-agent optimization algorithms where information exchange is governed by an explicit, controllable network topology. By investigating the emergence of "hubs"—highly connected agents—we demonstrate that the structural properties of agent interactions significantly influence the global performance of the system. Our results show that MNAs are competitive with traditional population-based methods and that tuning network parameters allows for a precise balance between exploration and exploitation.
Introduction
In Multi-Agent Systems (MAS), research typically emphasizes individual agent logic. However, the collective performance of these systems is often a function of how agents are interconnected. While population-based optimization techniques like Genetic Algorithms (GAs) rely on interaction, their communication structures are frequently implicit or static. This paper addresses the lack of frameworks that allow for the explicit control and measurement of network properties, such as degree distribution and hub influence, in solving complex optimization problems.
Methodology: The Memetic Network Algorithm (MNA)
The proposed Memetic Network Algorithm (MNA) is inspired by Richard Dawkins' concept of "memes"—units of cultural information that propagate through a population. An MNA is defined by three fundamental rules:
- Connection Rule: This governs how the network topology evolves. By employing a "connect to those better than me" strategy, the system naturally induces a scale-free network through preferential attachment.
- Aggregation Rule: This defines how agents synthesize information from their neighbors. A "majority vote" mechanism is used where an agent updates its solution bit-string based on the most frequent bits among its incoming connections.
- Appropriation Rule: This represents local innovation or search. Stochastic bit flips (noise) are introduced to prevent premature convergence and encourage continued exploration.
A critical parameter, $M$, is introduced to limit the maximum in-degree of any single agent, thereby controlling the influence of hubs within the network.
Experimental Setup
The MNA was evaluated against four standard benchmark functions:
- $f1$ (Sphere): Unimodal and separable.
- $f2$ (Rosenbrock’s Valley): Unimodal but non-separable.
- $f3$ (Rastrigin): Multimodal and separable.
- $f4$ (Ackley): Multimodal and non-separable.
These functions represent a spectrum of difficulty, from simple gradients to complex landscapes with numerous local optima.
Results and Discussion
The MNA demonstrated performance comparable to, and occasionally exceeding, standard Genetic Algorithms and Simulated Annealing across the test suite.
As shown in the convergence plots, while MNAs may exhibit slower initial convergence compared to GAs, they often achieve superior final solutions. The research highlights a "Hub Paradox": in unimodal problems ($f1, f2$), large hubs facilitate rapid information spread and faster convergence. Conversely, in multimodal problems ($f3, f4$), excessive hub influence can lead to premature convergence on local optima, as the population follows a single dominant agent before the search space is adequately explored.
The influence of the hub constraint $M$ is further explored in Figure 6. For function $f2$, we observe that increasing $M$ initially leads to significant performance gains, though the system remains sensitive to the specific value chosen. For multimodal functions, the authors identified a "sweet spot" for $M$ where information spreads effectively without sacrificing the diversity needed to escape local optima.
Conclusion
Memetic Networks provide a robust framework for analyzing the impact of interaction topologies on multi-agent performance. By treating network structure as a primary design variable, researchers can tune the exploitation-exploration trade-off more effectively. Future work will focus on scaling MNAs to higher-dimensional problems and exploring alternative topologies such as small-world or hierarchical networks.
Summary updated