1 Introduction

Computational intelligence is a set of nature-inspired algorithms that can be applied to solve problems in complex and dynamical environments (Engelbrecht 2007). Some examples of computational intelligence paradigms include: artificial neural networks, fuzzy systems, evolutionary computation, and swarm intelligence. Swarm intelligence is a concept in which actors communicate with each other locally and also act locally on the environment. The interactions between these individuals (the swarm) lead to the emergence of solutions to hard problems. Many computational techniques motivated by this behavior constitute what we call computational swarm intelligence—a set of bio-inspired algorithms based on populations of simple reactive agents. Among the best known swarm techniques are: particle swarm optimization (PSO) (Kennedy and Eberhart 1995), ant colony optimization (ACO) (Dorigo and DiCaro 1999), artificial bee colony (ABC) (Karaboga 2005), and fish school search (FSS) (Bastos-Filho et al. 2008).

PSO was proposed by Kennedy and Eberhart, and inspired by the social behavior of flocks of birds when searching for food (Kennedy and Eberhart 1995). The technique has been widely used to solve optimization problems in hyper-dimensional search spaces with continuous variables. The main idea behind the technique refers to a population of simple reactive agents (particles) that explore the search space by seeking the best solutions. Each particle has a position representing a candidate solution for the problem and stores the best position it has visited. This stored information is used by the particles to update their position and to navigate within the search space. Although different equations may be used to update the particles (Engelbrecht 2007), they all modify the particles’ position based mainly on their own history and on their neighbors information. Therefore, the way the information exchange happens between the particles plays an important role in the swarm behavior during the search (Mendes et al. 2004).

The ability of PSO to use different swarm topologies is an example of the importance of the communication between particles on the swarm search behavior. This structure defines the particles that can exchange information with each other (i.e. the particle’s neighborhood) and its characteristics have a high impact on the convergence speed and the quality of the solution obtained by the algorithm (Bratton and Kennedy 2007; Kennedy and Mendes 2002). Less connected topologies slow down the information flow given that the information is transmitted indirectly through intermediary particles (Kennedy and Mendes 2002). Conversely, highly connected topologies decrease the average distance between individuals. Consequently, they lead the whole swarm to move quickly towards the first local optimum found by any of the particles. Indeed, these different behaviors motivated the use of dynamic self-adjustable topologies to manage the information flow during the execution of the PSO algorithm (Suganthan 1999; Peram et al. 2003; Janson and Middendorf 2005; Mendes et al. 2004; Wang and Xiang 2008; Oliveira et al. 2013).

Although some researchers used the swarm topology to analyze the swarm behavior, this structure is only a static representation of the boundaries of the particles' communication (Kennedy and Mendes 2002; Mendes et al. 2004). Moreover, these analyses regarding the impact of the topology on the swarm performance are generally performed using measures that cannot provide a comprehensive information about the swarm behavior. In general, researchers use measures that do not assess the flow of information within the swarm; they just evaluate simple measures, such as the average distance between particles, and the evolution of the fitness of the particles along the iterations. In fact, as we look further into the literature we conclude that there are no measures to appropriately assess the communication process within swarms.

Furthermore, despite the communication between particles being a fundamental aspect of the swarm behavior, many researchers focus solely on the final result of these particles' interactions. For example, many studies have used the particles' properties (e.g. the position of a particle, the velocity of a particle, etc.) to assess the swarm behavior (Zhan et al. 2009; Zhang et al. 2011; Pontes et al. 2011; Zhou and Shi 2011). Although these approaches perform well with their proposed analyses, they are actually analyzing the final results (particles' properties) of the particles' interactions. For example, the average distance between particles (the density) in the search space can be used to infer if the swarm has stagnated in a certain area. However, all particles being in the same place is the result of a lack of diversity in the particles' communication. This approach also loses important information about the swarm behavior. For instance, the particles that attracted all the other particles to a region cannot be distinguished by just evaluating the density of particles in this specific region of the search space. Nevertheless, the particles that have attracted many other particles to this region present a higher influence and can be seen as hubs; hence it might be the case that one can help the entire swarm to escape from a local minimum by just working on these particular hub-particles. In addition to these afore mentioned aspects, one may notice that the approach based on the particles’ properties may be cumbersome because these properties are dependent on the dimension of the problem addressed by the swarm. For example, in a swarm that is optimizing a function in 1,000 dimensions, any particle’s property is also defined in 1,000 dimensions, and calculations using these properties (e.g. Euclidean distance to calculate the swarm barycenter) will be inconvenient.

We propose the analysis of the particles’ communication as a way to assess the swarm execution behavior because we believe it to be the core mechanism driving the behavior the swarm. First, to have this analysis, we need to capture the information flows within the swarm, thus we define the swarm influence graph, that is a graph (or network) representing the information exchange between particles in the swarm. Second, we analyze this network to understand the information flow; we propose the analysis of the influence graph by looking at the number of components present and its general structural characteristics. We simulated the PSO algorithm with three different communication topologies and we showed that each topology leads to different communication signatures. Also, we showed that, in the case of a dynamic topology, this signature is related to the stagnation of the swarm.

The paper is organized as follows: we review the particle swarm optimization and some network science concepts in Sect. 2. In Sect. 3 we define the swarm influence graph and describe the measures to analyze it. In Sect. 4, the simulation setup and results are presented. Finally, we present our conclusions and suggest some future work in Sect. 5.

2 Background

In this section, we provide a brief explanation of the topics related to our proposal. In Sect. 2.1, PSO is defined focusing on the topologies used by the swarm. Some definitions from network science are given in Sect. 2.2, along with network concepts that are used in this paper.

2.1 Particle swarm optimization

PSO is a stochastic, bio-inspired, population-based global optimization technique (Eberhart and Kennedy 1995; Kennedy and Eberhart 1995). In PSO, each particle \(i\) has a position \({{x}}_i(t)\) at iteration \(t\) within the search space and each position represents a possible solution for a \(d\)-dimensional optimization problem. The particles move through the problem’s search space seeking for the best solutions. Each particle updates its position according to the current velocity \({\mathbf {v}}_{i}(t)\), the best position \({\mathbf{p}}_{i}(t)\) found by itself, and the best position \({\mathbf {n}}_{i}(t)\) found in its neighborhood during the search so far. The velocity \({\mathbf {v}}_i(t)\) and the position \({\mathbf {x}}_i(t)\) of every particle is updated iteratively by applying Eqs. (1) and (2), respectively.

$$\begin{aligned} {\mathbf {v}}_{i}(t+1) = {\mathbf {v}}_i(t) + {\mathbf {r}}_1 c_1 [{\mathbf {p}}_{i}(t)-{\mathbf {x}}_i(t)] \nonumber \\ + \; {\mathbf {r}}_2 c_2 [{\mathbf {n}}_{i}(t)-{\mathbf {x}}_i(t)], \end{aligned}$$
(1)
$$\begin{aligned} {\mathbf {x}}_{i}(t+1) = {\mathbf {x}}_{i}(t) + {\mathbf {v}}_{i}(t+1), \end{aligned}$$
(2)

where \({\mathbf {r}}_1\) and \({\mathbf {r}}_2\) are vectors containing random numbers generated from a uniform probability density function within the interval [0,1] at each iteration, for all particles, and for every dimension. The learning factors \(c_{1}\) and \(c_{2}\) are the cognitive and the social acceleration constants. They are non-negative constants and weigh the contribution of the cognitive and social components, i.e. the second and the third terms of Eq. (1).

This basic set of particles’ update equations can lead the swarm to what is called an explosion state. This behavior arises because these equations allow the particles to increase their velocities indefinitely (i.e. they “explode”). Some approaches have been proposed to overcome this issue (Eberhart et al. 1996; Shi and Eberhart 1998; Clerc and Kennedy 2002). Bratton and Kennedy (2007) developed an approach in which the velocities are constricted by a constant \(\chi\), referred as the constriction factor (Clerc and Kennedy 2002). They determined a relation based on this factor that avoids the explosion state, defined according to Eq. (3). \(\varphi\) is the sum of the acceleration coefficients \(c_{1}\) and \(c_{2}\).

$$\begin{aligned} \chi = \frac{2}{\vert 2 - \varphi - \sqrt{\varphi ^2 - 4\varphi }\vert }, \;\;\;\;\; \varphi = c_{1} + c_{2}. \end{aligned}$$
(3)

This factor was introduced to adjust the influence of the previous particle velocities to the optimization process. The final update equation (using \(\chi\)) for the particle’s position is defined as:

$$\begin{aligned} {\mathbf {v}}_{i}(t+1) = \chi \cdot \bigg \{{\mathbf {v}}_i(t) + {\mathbf {r}}_1 c_1 [{\mathbf {p}}_{i}(t)-{\mathbf {x}}_i(t)] \nonumber \\ + \; {\mathbf {r}}_2 c_2 [{\mathbf {n}}_{i}(t)-{\mathbf {x}}_i(t)]\bigg \}. \end{aligned}$$
(4)

The constriction factor \(\chi\) also helps to regulate the exploitation–exploration balance of the swarm (Clerc and Kennedy 2002; Bratton and Kennedy 2007). This balance is related to the swarm behavior during the swarm search. The exploration mode is the ability of individuals to broadly explore a region in the search space, while exploitation happens when the search is focused on a specific area of the search space (Kennedy and Eberhart 2001).

2.1.1 Particle swarm optimization topologies

The swarm topology defines the boundaries of the particles' communication. The particles only share information with others in the neighborhood defined by the swarm topology. Thus, the flow of information within the swarm during the search is impacted by the topology used by the swarm. Kennedy and Mendes (2002) showed how the topology structure influences the flow of information among the particles (Kennedy and Mendes 2002). They demonstrated that the presence of intermediary individuals slows down the information flow. Conversely, the information moves faster if more pairs of individuals are directly connected. Thus, when the average distance between nodes is too short, the population tends to move quickly towards the best solution found in earlier iterations. This behavior implies a faster convergence to the global optimum in simple unimodal problems. However, this fast convergence might force the swarm to prematurely reach a local optimum and loose diversity, specially in multimodal problems (Bratton and Kennedy 2007). In such cases, communication topologies with lower number of connections may reach better results, because the information spreads slowly and the swarm explores different regions of the search space.

Fig. 1
figure 1

The swarm topology defines the boundaries of the particles' communication. In each network topology, the nodes are the particles and the links represent the possibility of information exchange

Full size image

Figure 1 depicts some well-known communication topologies used in swarms (Bratton and Kennedy 2007). The global topology was the first topology proposed for the PSO (Kennedy and Eberhart 1995). In this topology, shown in Fig. 1a, all the particles of the swarm are neighbors of each other, leading to a social memory shared by the entire swarm. On the other hand, in local topologies the particles do not share the same neighborhood (Bratton and Kennedy 2007). Consequently, the social memory is not the same for all the particles and is topology dependent. The most used local topology is the ring topology (Bratton and Kennedy 2007), in which each particle has only two neighbors, as depicted in Fig. 1b. This structure helps to avoid a premature attraction of all particles to a single location of the search space given that the information spreads slowly; this characteristic comes with the caveat of a slow convergence time (Bratton and Kennedy 2007).

These two topologies lead to extreme opposite behaviors in the swarm, therefore many efforts have been made to propose approaches that have fast convergence while avoiding local minima, such as the ones depicted in Fig. 1c and d (Kennedy and Mendes 2002; Mendes et al. 2003; Bratton and Kennedy 2007). However, all these proposed structures are usually more appropriate to certain problems (e.g. global topology for unimodal problems) (Kennedy and Mendes 2002). The main reason for this problem dependency is that these topologies are based on arbitrary structures, normally static, and consequently they lead to a non-robust search behavior.

To achieve more robustness, some dynamic topologies were proposed (Suganthan 1999; Peram et al. 2003; Mendes et al. 2004; Janson and Middendorf 2005; Wang and Xiang 2008; Godoy and Von Zuben 2009; Mo et al. 2010; Oliveira et al. 2013). The structures of these topologies are not static, they change during the search process generally based on specific rules. Oliveira et al. (2013) proposed an approach that (self-)adapts the communication scheme based on the swarm state. This dynamic topology tries to change the information flow within the swarm when the particles are stagnating in the search space. The structure modification is based on the preferential attachment mechanism present on the Barabási-Albert model (Barabasi and Albert 1999; Albert and Barabasi 2002). Each particle attempts to create a connection with new particles using a roulette wheel based on the particles’ fitness. We call this topology as the dynamic topology henceforth in this paper.

The self-adaptation in the dynamic topology is based on the state of the swarm. The topology changes when the swarm is stagnating, thus a way to assess the swarm state is needed. To do that, each particle has a new attribute, called \(P_k\) failures, to determine if the particle \(k\) is improving its fitness during the search process. Therefore, if the fitness of the particle \(k\) does not improve after its iterative position update, \(P_k\) failures  is incremented, otherwise \(P_k\) failures  is set to zero. The particle is considered stagnated if \(P_k\) failures  reaches a preset threshold, a parameter of the algorithm.

In the beginning of the algorithm execution, all the particles are connected based on a structure that allows exploration of the search space. The rationale of this initial scheme is that it is desirable for the swarm to explore the search space in the initial stage of the algorithm run, then in the final steps an exploitation behavior is preferable (Bratton and Kennedy 2007). At each iteration, each particle updates its \(P_k\) failures  and when the value reaches the preset threshold of failures, the particle \(k\) searches for better particles to be connected with, as well as to stop being connected to its current neighbors. This selection of new neighbors is based on a roulette wheel with a linear fitness-based ranking. More details about the dynamic topology can be found in Oliveira et al. (2013).

2.2 Network science concepts

The analysis made in this paper is a network-based approach to capture the information flow within the swarm and is conducted by modeling the particles’ interactions as networks/graphs. A graph \(G\) consists of a pair \([V(G), E(G)]\), where \(V(G)\) is a set of vertices labelled \(1,2,\ldots ,n\) and \(E(G)\) is a set of edges (i.e. pairs of adjacent vertices). Any graph \(G\) can be represented by its adjacency matrix \(A(G)\), in which its elements are defined as:

$$\begin{aligned} A_{ij} = \left\{ \begin{array}{ll} 1, &{} \quad \text {if} \ \text {vertex}\,\,i \text {\, and\,vertex}\,\,j \text{\,are\,adjacent},\\ 0, &{} \quad \text {otherwise}. \end{array} \right. \end{aligned}$$
(5)

The spectrum of \(G\) consists of the \(n\) eigenvalues of \(A(G)\), denoted as \(\lambda _{1},\lambda _{2},\ldots ,\lambda _{n}\) where \(\lambda _{1}\ge \lambda _{2}\ge \cdots \ge \lambda _{n}\). The spectral density of a graph can be defined as the density of these eigenvalues and can be stated as a probability density function as follows:

$$\begin{aligned} \rho (\lambda ) = \dfrac{1}{n} \sum _{j = 1}^{n} \delta (\lambda - \lambda _{j}), \end{aligned}$$
(6)

where \(n\) is the number of eigenvalues and \(\delta\) is the Dirac function.

Many characteristics of the graph can be assessed by analyzing the graph spectrum (Cvetković et al. 2010). Actually, the spectrum is considered a fingerprint of the networks that can be used to characterize them (Dorogovtsev et al. 2003). Farkas et al. (2001) showed that topological features of some kinds of graphs (uncorrelated random networks, the small-world networks, and the scale-free networks) can be identified by its graph spectral density (Farkas et al. 2001). They also proposed some practical tools for the identification of the basic types of random graphs and for classification of real-world networks. These tools are based on the extremal eigenvalues of the adjacency matrix. Farkas et al. (2001) showed that these eigenvalues contain useful information about the structure of the graph. Depending on the periodicity of this structure, the principal eigenvalue is detached from the rest of the spectrum. Thus, they proposed a quantity named \(R\), defined as:

$$\begin{aligned} R = \dfrac{\lambda _{1} - \lambda _{2}}{\lambda _{2} - \lambda _{n}}, \end{aligned}$$
(7)

that measures the distance of the first eigenvalue from the main part of \(\rho (\lambda )\).

The \(R\) value can be used to distinguish between some graph structure features: (1) periodical or almost periodical; (2) uncorrelated and non-periodical; and (3) strongly correlated non-periodical. For example, a regular graph has a structure that is periodical, conversely a random graph is non-periodical. However, when the probability in a random graph is not constant and depends on the nodes involved, the result is a correlated structure. In large systems, \(R\) value of the sparse uncorrelated random graph converges to a constant, while \(R\) value in the scale-free model decays as a power law function of the number of the nodes.

The Laplacian matrix \(L(G)\) of a simple graph \(G\) is the matrix \(D(G) - A(G)\), where \(D(G)\) is the degree matrix of graph \(G\). Some properties of a graph can be inferred using the Laplacian matrix, its eigenvalues \(v_{1}(G) \ge v_{2}(G) \ge \cdots \ge v_{n}(G)\) relate to many of these properties. For instance, the multiplicity of \(0\) as an eigenvalue of \(L\) is equal to the number of components in \(G\) (Cvetković et al. 2010). Thus, the second-smallest eigenvalue of \(L\) is equal to zero if and only if \(G\) is a non-connected graph. This eigenvalue is called the algebraic connectivity (or Fiedler value) of \(G\) and its magnitude reflects how well the graph is connected.

3 Assessing particle swarm optimizers

In this section, a structure called the swarm influence graph is defined to capture the flows of information within the swarm. Moreover, some measures are described to analyze these flows by analyzing this proposed structure. In Sect. 3.1 the afore mentioned structure is defined and the measures are presented in Sect. 3.2.

3.1 The swarm influence graph

Although the swarm communication topology defines which particles can communicate with one another, the topology only bounds the particles' communication range. Actually, the information flow changes at each iteration when the particles share information with their best neighbors. That is, at iteration \(t\), each particle \(i\) only gets information from its best neighbor \(n_{i}(t)\). Thus, a network of information exchanges between particles in a given iteration can be used to assess the information flow within the swarm. Therefore, we define the influence graph as the representation of this network. The elements of the swarm influence graph \(I'_t\) at iteration \(t\) are defined as follows:

$$\begin{aligned} I'_{t_{ij}} = \left\{ \begin{array}{ll} 1, &{} \quad \text {if} \quad {\it n_{i}}({\it t}) = {\it j},\\ 0, &{} \quad \text {otherwise}. \end{array} \right. \end{aligned}$$
(8)

where \(n_{i}(t)\) is the neighbor of particle \(i\) at iteration \(t\).

Fig. 2
figure 2

Examples of the swarm influence graph over the topology for the three communication topologies. These examples suggest that the swarm topology impacts the structure of the influence graph

Full size image

One can observe that the influence graph \(I'_i\) is a directed graph by definition. The direction of the edges is the actual direction of the information exchange between particles. The simplified influence graph \(I_t\) is defined by removing the edge direction. The elements of this graph at iteration \(t\) are described as follows:

$$\begin{aligned} I_{t_{ij}} = \left\{ \begin{array}{ll} 1, &{} \quad {\text {if }}\ n_{i}(t) = j \quad {\text {or}} \quad n_{j}(t) = i,\\ 0, &{} \quad \text {otherwise}. \end{array} \right. \end{aligned}$$
(9)

In other words, the simplified influence graph is the network of the particles that shared information between them at a given iteration. Figure 2 depicts examples of simplified influence graphs (in bold) over three different swarm topologies. These examples suggest that the swarm topology impacts the structure of the influence graph. For example, in the case of the ring and dynamic topologies, there are some sub-graphs, whereas the global topology presents only a focal point in the influence graph. One must notice that the existence of two particles in the same component does not imply they share information, actually they only do if they are directed connected, otherwise they only share common particles that are indirectly exchanging information.

The swarm influence graph is a forest, that is a graph in which each connected component is a tree. The components in the influence graph are related to the information flows within the swarm. Therefore, the number of components as well as their structure is associated with the swarm behavior, and the analyses in this paper are made on these two aspects.

The simplified influence graph is the one used to analyze the swarm information flow in this paper because the analysis of the structure of a undirected graph is simpler than a directed one (e.g. the eigenvalues of the adjacency matrix of a directed graph may be not real). Although the direction is removed from the edges in the simplified graph, there is still implicit information about the influence of the nodes. This is the case because of the tree structure of the influence graph and the fact that every particle must retrieve information from other particle, once the PSO version being analyzed is a selfless model, that is, the particles always use the neighbors’ information to evaluate \({\mathbf {n}}_i(t)\) (Kennedy 1997). For example, Fig. 3 is a small tree that depicts a possibly influence graph of three particles, namely \(a\), \(b\), and \(c\).

Fig. 3
figure 3

The structure of the simplified influence graph still provides information about the swarm behavior. In this example, a simplified influence graph of three particles is derived from one of the graphs in Fig. 4

Full size image

The graph in Fig. 3 can be the result of the direction removal process of the follow structures depicted in Fig. 4. One must notice that the structures in Fig. 4b and c can be seen as the same, the difference between them is just the labels, thus they are treated as the same. Furthermore, once this is a selfless model and a particle must retrieve information from its neighborhood, the structure in Fig. 4a may also be understood in the same way as the other ones. Therefore, when the labels are disregarded, these structures are the same, as depicted in Fig. 5.

Fig. 4
figure 4

The possible directed influence graphs of the structure in Fig. 3. Due to the tree structure of the influence graph and the fact that every particle must retrieve information from other particle, all of them can be seen as the same

Full size image
Fig. 5
figure 5

The origin of the structure in Fig. 3 when the labels are disregarded. There is no loss of information when the directions are removed from these trees

Full size image

Such understanding of the swarm influence graph can be also easily obtained in a tree of two particles, a case in which there is only one possible configuration: both particles sending and receiving information. Thus, there is no loss of information when the directions are removed from these small-sized trees. On the other hand, bigger trees are more complicated to analyze and indeed there is loss of information. However, the structure of these trees still contains informative aspects of the swarm communication. For example, a particle with degree \(k\) in a tree of the influence graph transmits information to at least \(k - 1\) other particles (and at most to \(k\) particles). Thus, the higher is the degree of a particle, the higher is the impact of this particle on the others. Therefore, although the influence graph is simplified, the analysis of its structure still provides information about the influential role of the particles involved, as well as the information flow.

3.2 Analyzing the swarm influence graph

In this paper, the swarm influence graph is analyzed by its number of components and its structure. In Sect. 3.2.1, the use of the number of zero-valued eigenvalues of the Laplacian matrix is discussed as a way to count the number of information flows. To analyze the structure of these flows, the density spectrum is used and discussed in Sect. 3.2.2. Once the analysis of the spectrum may be cumbersome, the \(R\) value is used to assess the information flow and is also discussed in Sect. 3.2.2.

3.2.1 The number of zero-valued eigenvalues in the Laplacian matrix

The components in the swarm influence graph (i.e. the sub-graphs in the case of undirected graphs) are groups of particles that shared information with the same particles; in such a manner that if two particles are not in the same component, they have different sources of information to calculate their velocities. Thus, these components can be seen as different flows of information in the swarm. The number of these flows within the particles is related to the swarm diversity. For instance, a swarm with few information flows does not have different sources of information regarding different regions of the search space. In this case, the swarm may contain low diversity, which drives all the particles towards the same place in the search space. Conversely, a swarm with many different information flows explores the search space as a whole because there are many sources of information. These two distinct search behaviors with different number of information flows also relate to the exploration–exploitation balance in the swarm. When the particles are exploring broadly a region in the search space (i.e. exploration search mode), there are different information flows in the swarm. On the other hand, when the search is focused in an area (i.e. exploitation search mode), the swarm diversity is low.

The multiplicity of “\(0\)” as an eigenvalue of the Laplacian matrix of the swarm influence graph is equal to the number of components in this graph. Thus, to count the number of information flow in the swarm, we analyze the influence graph with this measure.

3.2.2 The density spectrum and \(R\) value

The analysis of the structure of the information flow within the swarm may elucidate aspects of the swarm behavior. For instance, although particles in the swarm can share information with the same particles, there is the possibility of a particle being more influential than others in the same flow. This is the case, for example, when particles transmitting information to many others are present in the flow. This is highly related to the diversity of the swarm since the existence of impactful particles may lead the other particles to the same region of the search space. Thus, the way information navigates within the swarm is described by the structure of the information flow, that impacts the swarm behavior. Therefore, the analysis of the structure of the swarm influence graph may explain these intricate behaviors of the particles during the search process.

The spectra of eigenvalues of the graph adjacency matrix is considered a fingerprint of the networks that can be used to characterize them (Dorogovtsev et al. 2003). Thus, we use the density spectrum of the swarm influence graph to find the fingerprints of the swarm search behaviors. That is, this analysis can show a signature of the type of the search being performed by the swarm. Still, this analysis may be cumbersome because the density spectrum analysis we perform is mainly a plot analysis. In general, the spectral density can be mainly used to assess the behavior of algorithms or to diagnose the influence of a parameter in the algorithm performance.

Considering this, we also deployed the \(R\) value since it can also be used as a way to understand the characteristics of the network. Besides, the \(R\) value is a single indicator and can be used to control the operation of the algorithm. It is worthy to mention that the \(R\) value can be used together with other measures, such as the evolution of the fitness or the density of particles in a certain region of the search space.

Fig. 6
figure 6

Number of zero eigenvalues of the swarm influence matrix for dynamic, ring, and global topologies for two different benchmark functions

Full size image
Fig. 7
figure 7

Density spectrum of the swarm influence graph for a the ring topology and b the global topology (right)

Full size image
Fig. 8
figure 8

The performances of two independent runs of the PSO algorithm with the dynamic topology optimizing F6 function

Full size image

4 Simulation setup and results

4.1 PSO setup

To assess the proposed methodology, we used the PSO algorithm to optimize two well-known multimodal benchmark functions, named F6 function and F8 function, that were proposed in 2010 as large-scale optimization problems (Tang et al. 2010). The F6 function is a single-group shifted and \(m\)-rotated Ackley’s function and F8 function is a single-group shifted and \(m\)-dimensional Rosenbrock’s function. The former is a multimodal function and the latter is also a multimodal function very dependent on the initial values. We selected these two different functions to have insights of the swarm behavior in two distinct scenarios.

In all experiments, we used 1,000 dimensions and \(m\) equal to 50. We used 200 particles in all simulations. For each simulation trial, we used 300,000 fitness function evaluations. We performed simulations for the global, local, and dynamic topologies. In the case of the dynamic topology, the threshold of failures for the particles was set to \(P_k\) failures  = \(50\). The particles were updated according to Eq. (4) with \(c_{1} = 2.05\) and \(c_{2} = 2.05\) as indicated in Clerc and Kennedy (2002), which guarantees no explosion state.

4.2 The number of information flows

The evolution of the number of information flows within the swarm during the execution of the PSO optimizing the F6 function is shown in Fig. 6a. It shows the behavior of this quantity as a function of the number of iterations for the three considered topologies.

The influence graph in the global topology is an one-component star-like graph and keeps its structure during the whole execution of the algorithm; the number of zero eigenvalues is constant and equal to one. Although the value is equal to one in this case, it does not mean that the influence graph is the same along the entire process. The best particle of the swarm can change along the iterations which causes the center of the star-like topology to change.

Although the ring topology is static, the influence graph can present different sub-graphs. One can observe that the number of information flows varies through the iterations, but presents a high average value of \(40\) along the entire process.

In the dynamic topology, the algorithm starts with \(10\) information flows and diminishes in average to \(5\) information flows along the algorithm execution. One must observe that the dynamic topology presents a balanced behavior between the two static approaches.

Figure 6b depicts the same analysis on the F8 function. One can observe that the curves are similar to the ones shown in Fig. 6a. This similarity can also be seen with all benchmark functions in Tang et al. (2010).

4.3 Analyzing the structure of the information flows with the density spectrum

To analyze the eigenvalue spectra of the swarm influence graph, we divided the analysis in two parts: static topologies and the dynamic topology. First, we try to capture the structural characteristics of the static topologies. Thereafter, we try to analyze the performance of the algorithm by its structural characteristics when the swarm has a dynamic topology.

The static topology analysis is given in Sect. 4.3.1 and analysis of the dynamic topology is shown in Sect. 4.3.2.

4.3.1 Static topologies

The spectral density has the capacity to represent the frequency of the eigenvalues. Therefore, it is interesting to evaluate the characteristics of the topologies as a function of the number of iterations to examine the swarm behavior through iterations.

As the ring and global topologies present a well-known behavior in terms of connectivity and convergence, we first evaluated the evolution of the spectral density of the influence graph as a function of the number of iterations for these two topologies.

Fig. 9
figure 9

The density spectrum of the swarm influence graph from different iterations of the two runs with performances depicted in Fig. 8. The curve for Run #2 is flattened out more quickly than the curve from Run #1

Full size image

The behavior of the spectral density of the influence graph along the iterations of the PSO when using a Global topology is depicted in Fig. 7b. The snapshots of the spectral density are from iterations 100, 400, 800 and 1,200. One can observe that the Global topology presents a perfect unimodal shape. Moreover, the shape does not vary along iterations.

Figure 7a depicts the curve of the spectral density along the iteration for the PSO with local topology. The shape is bimodal, unlike the density spectrum shape of the swarm with a Global topology. Nevertheless, the curve also does not change along the iterations.

Fig. 10
figure 10

The performances of two independent runs of the PSO algorithm with the dynamic topology optimizing F8 function

Full size image
Fig. 11
figure 11

Density spectrum of the swarm influence graph from different iterations of the two algorithm executions with performance shown in Fig. 10. Again, the curve for Run #2 is flattened out faster than the curve from Run #1

Full size image

4.3.2 Dynamic topology

To analyze the information flow of the swarm and to assess the performance of the proposed approach by means of the information disseminated in the swarm, we use two different runs of the PSO algorithm. These different runs optimize one of benchmark functions used before (F6 function), but one of these runs gets stagnated along the iterations and the other has success.

Figure 8 shows two different trials of the PSO with the dynamic topology (Run #1 and Run #2) optimizing F6 function. As seen in the figure, the results of these two independent runs are quite different. In Run #1, the algorithm converged, while in the Run #2 the algorithm got stuck in a local minimum. Figure 9 shows evolution of the spectral density of the influence graph for these two runs for the iterations \(50\) to \(450\) with increments of \(50\). In Run #2, the curve is flattened out more quickly than the curve from Run #1. Moreover, in both cases, the structure in the first iterations is similar to the one when the swarm has the global topology. However, one can observe that both cases present side lobes, which represents a combination of local and global behaviors.

Two runs of the PSO with the dynamic topology optimizing F8 function are shown in Fig. 10. The fitness values for these two independent runs are different just at the end of the algorithm execution. The fitness is slightly better for Run #1 when compared to Run #2.

Figure 11 shows the evolution of the spectral density of the influence graph for these two runs for the iterations from \(50\) to 1,000, with increments of \(50\). Again, in Run #2, the curve is flattened out a little more quickly than the curve from Run #1. This might explain the difference in the final fitness. However, one must observe that the difference in the shape of the curve is not so evident as in the former case (F6 function).

Hence, although interesting, from our results alone, we still cannot define a rigid rule between the flattening rate of the spectral density and the stagnation level of the swarm. However, the information provided by the evolution of the spectral density may be used to assess the influence of a parameter in the swarm performance.

Fig. 12
figure 12

\(R\) value of the swarm influence graph along the iterations when the swarm has dynamic, ring, and global topologies. the dynamic topology leads to a balanced behavior between ring and global topologies

Full size image

4.4 Using the \(R\) value

Two analysis of the swarm influence graph with the \(R\) value were made. First, we compare the structure features through iterations of the information flow of the PSO using different topologies. Thereafter, we analyze the performance of the algorithm by its structural characteristics when the swarm has a dynamic topology.

Fig. 13
figure 13

Comparison of the \(R\) value and cumulative \(R\) value of the influence graph of the swarm with dynamic topology. We show the non-cumulative only for the F6 function because the result for the F6 function is similarly confusing and not used in any analysis. The evolution of the cumulative \(R\) value for runs #1 and #2 diverges at a certain iteration

Full size image

4.4.1 Static and dynamic topologies

Figure 12 presents the behavior of \(R\) value of the influence graph as a function of the number of iterations for the three topologies considered in this paper. A low \(R\) value means that \(\lambda _1\) is not detached from the rest of the spectrum and it can be seen as a consequence of a periodical structure Farkas et al. (2001).

Because of the star-like behavior of influence graph for the global topology, its \(R\) value is constant and presents the value \(1\), since the extremal eigenvalues \(\lambda _1\) and \(\lambda _N\) are opposites, and \(\lambda _2 = 0\).

Both the ring and the dynamic topologies present small \(R\) values, as they produce influence graphs that display very periodical structures. Again, the dynamic topology presented a balanced behavior.

4.4.2 Dynamic topology

Figures 8 and 10, described in Sect. 4.3.2, depict runs of the PSO algorithm with different performances. Here, we try to learn more about those runs by means of the information disseminated in the swarm using the \(R\) value defined earlier.

Figure 13a depicts the evolution of the \(R\) value through the iterations of the PSO when optimizing the F6 function.

As the plot is confusing to understand, we use the cumulative \(R\) value, defined as follows:

$$\begin{aligned} R_{\mathrm{cum}_i} = {1 \over i}\sum _{j = 1}^{i}{R_j}, \end{aligned}$$
(10)

where \(R_i\) is the \(R\) value at iteration \(i\).

The evolution of the cumulative \(R\) value through iterations of the swarm influence graph of the PSO when optimizing the F6 function using the dynamic topology is shown in Fig. 13b. As it is possible to see, the behaviors of the curves are very different. In the first iterations, the plots are similar, but at approximately iteration \(400\), the plots diverge. One can observe that the cumulative \(R\) value is higher for Run #2 and presents a value that is more similar to the one presented by a global topology, which represents a higher chance to get trapped in a local minima.

Figure 13c shows the behavior of the cumulative \(R\) value through iterations of the swarm influence graph of the PSO when optimizing the F8 function. Again, the worst run (Run #2) presented higher values for the cumulative \(R\) value.

5 Conclusions and future work

We proposed the analysis of the swarm behavior in PSO based on the particles' interactions. We defined a network of these interacti ons named the swarm influence graph and we assessed the swarm behavior by analyzing this graph. The novelty of our approach is that we analyze the fundamental aspect of the swarm intelligence: the particles communication. Due to this characteristic, our proposal allows richer analyses regarding the information flows within the swarm than the usual approaches. Moreover, the particles' properties (e.g. the position of a particle, the velocity of a particle, etc) are not needed on this swarm analysis, thus our approach is not dependent of the problem dimension.

In this paper, we proposed the analysis of the swarm influence graph to assess the information flow to find the fingerprints of the swarm search behavior. The analyses made on the influence graph consider its number of components and its structure. More specifically, we used: the number of zero-valued eigenvalues in the Laplacian matrix to count the number of components in the graph; the spectral density to characterize the network; and the \(R\) value to numerically characterize the network. The first can be used to assess the number of information flows within the swarm. The second provides a signature of the information flows, which can provide insights on the type of search performed by the swarm in the last iteration. The third one also returns information about the network structure, but is a single value that could be used to control the operation of the algorithm.

We showed that our approach can assess the different search behaviors of the swarm when different topologies are used. Each topology used by the swarm does have different signatures in the swarm influence graph that leads the swarm to behave in distinct manners. We showed that the swarm with the dynamic topology has a behavior that is between the two most used static approaches, the ring and global topologies. Moreover, regarding the dynamic topology, the simulation results showed that the measures can be used to indicate a possible stagnation process within the swarm. Again, this can be used to trigger operators, for example, to generate diversity in the swarm.

Although we have presented results using measures from the network science field applied to the PSO algorithm, the main idea presented in this paper is not technique-dependent. We believe this is a first attempt to show that this measures can be used to assess the performance and to assist the design of swarm intelligence algorithms. In fact, the analysis of the communication within the swarm can be done with other swarm intelligence approaches (e.g. FSS, ACO, etc.). In ACO, the analysis could be performed in the pheromone graph. In the FSS, the idea could be adapted to assess the memory matrix introduced in the dFSS approach.

As future works, we intend to use these measures to design high performance dynamic topologies for PSOs by assessing the information flow within the swarm. We also aim to develop variations of the swarm influence graph to recognize different aspects of the swarm communication. Furthermore, we want to perform analysis on the swarm performance of different swarm intelligence approaches as indicated above.