Memetic Networks: Analyzing the Effects of Network Properties in Multi-Agent Performance

Ricardo M. Araújo, Luís C. LambAAAI 2008

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:

  1. 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.
  2. 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.
  3. 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.

Convergence of MNA compared to GA, RS, and SA across four benchmark functions.

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.

Impact of the hub constraint M on the best solution found after 30 rounds for function f2.

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

BibTeX
@inproceedings{araujo2008memetic,
  author = {Ricardo M. Araújo and Luís C. Lamb},
  title = {{Memetic Networks: Analyzing the Effects of Network Properties in Multi-Agent Performance}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2008},
}
Figure