# Hierarchical Swarm Model: A New Approach to  Optimization

Authors: Hanning Chen; Yunlong Zhu; Kunyuan Hu; Xiaoxian He
Journal: Discrete Dynamics in Nature and Society
 (2010)

---

## Abstract

This paper presents a novel optimization model called hierarchical swarm optimization (HSO), which simulates the natural hierarchical complex system from where more complex intelligence can emerge for complex problems solving. This proposed model is intended to suggest ways that the performance of HSO-based algorithms on complex optimization problems can be significantly improved. This performance improvement is obtained by constructing the HSO hierarchies, which means that an agent in a higher level swarm can be composed of swarms of other agents from lower level and different swarms of different levels evolve on different spatiotemporal scale. A novel optimization algorithm (namedPS2O), based on the HSO model, is instantiated and tested to illustrate the ideas of HSO model clearly. Experiments were conducted on a set of 17 benchmark optimization problems including both continuous and discrete cases. The results demonstrate remarkable performance of the PS2O algorithm on all chosen benchmark functions when compared to several successful swarm intelligence and evolutionary algorithms.


---

## Body

## 1. Introduction

Swarm intelligence (SI), which is inspired by the “swarm behaviors” of social animals [1], is an innovative artificial intelligence technique for solving hard optimization problems. In SI system, there are many simple individuals who can interact locally with one another and with their environments. Although such systems are decentralized, local interactions between individuals lead to the emergence of global behaviors or global properties. For instance, flock of birds and school of fish emerge spatial self-organized patterns through social foraging [2]. Similar phenomena can also be observed in colonies of single-cell bacteria, social insects like ants and bees, as well as multicellular vertebrates, which all display collective intelligence [3].As a problem-solving technique, many algorithmic methods of SI were designed to deal with practical problems. In 1991, Dorigo proposed ant colony optimization (ACO) [4, 5] based on foraging behaviors of ant colonies. ACO has been successfully used to solve discrete optimization problems, like traveling salesman problems (TSP) [6]. After that, another SI algorithm, namely, particle swarm optimization (PSO), was proposed by Kennedy and Eberhart [7], which gleaned ideas from the social behavior of bird flocking and fish schooling [8–10]. PSO is primarily concerned with continuous optimization problems. In 2001, Passino proposed a technique known as bacterial foraging optimization (BFO) that inspired by the pattern exhibited by bacterial foraging behaviors [11]. Other swarm optimization methods have been developed like artificial immune systems (AIS) [12], which are based on the metaphor of the immune system as a collective intelligence process [13]. Recently, Karaboga has described a bee swarm algorithm called artificial bee colony (ABC) algorithm [14], and Basturk and Karaboga compared the performance of ABC algorithm with the performance of genetic algorithm (GA) in [15]. These SI paradigms have already come to be widely used in many areas [8, 16–22].In current artificial SI systems, however, researchers only take into account the collective behaviors of one level of individuals, and ignored the hierarchical nature [23] of the real world systems and animal society. In fact, for most social insects and animals, their organizational structures are not flat. They can form complex hierarchical (or multilevel) system structures by self-organization and division of labor features [24]. In other words, in a hierarchical system, a swarm of lower level individuals can be the infrastructure of a single individual at the higher level [25, 26]. Here the term “swarm” is used in a general sense to refer to any collection of interacting agents. In most of natural hierarchically complex systems, swarms of lower level agents interact with each other to constitute more complex high-level swarms’ constituent agents, repeatedly, until very complex structures with greatly enhanced macroscopical intelligence emerge. Such phenomenon is so common in the natural world, this guides us to design a multilevel algorithmic model to mimic hierarchical emergence of nature society.First, this paper extends the traditional SI framework from flat (one level) to hierarchical (multiple level) by proposing a novel optimization model called hierarchical swarm optimization (HSO). In HSO model, collective behaviors of multiple levels are taken into account to solve complex problems. Then some initial insights into this method are provided by designing a two-level HSO algorithm (named PS2O) based on canonical PSO model. Four versions of PS2O are realized according to different structures of cooperation and interaction types in each level. In order to evaluate the performance of PS2O, extensive studies based on a set of 17 benchmark functions (including both continuous and discrete cases) have been carried out. For comparison purposes, we also implemented the genetic algorithm (GA), covariance matrix adaptation evolution strategy (CMA-ES), artificial bee colony algorithm (ABC), and four state-of-the-art PSO variants on these functions. The experimental results are encouraging; the PS2O algorithm achieved remarkable search performance in terms of accuracy, robustness, and convergence speed on all benchmark functions.The rest of the paper is organized as follows. Section2 describes the proposed hierarchical swarm optimization model. In Section 3, a novel HSO-based optimization algorithm, namely, PS2O, is given. Section 4 tests the algorithm on the benchmarks and illustrates the results. Finally, Section 5 outlines the conclusions.


## 2. Hierarchical Swarm Optimization

### 2.1. From Flat Swarm to Hierarchical Swarm

In [3], Bonabeau et al. define swarm intelligence as “the emergent collective intelligence of groups of simple agents”. In such a perspective, the artificial SI systems, which are designed for complex problem solving, maintain a swarm made up of many isomorphic and relatively simple individuals that often share the same states and behaviors set. In such a swarm, all individuals have absolutely equal status in the whole life cycle. The interaction relations between these individuals are symmetrical and operate on the same spatiotemporal scale. One individual can be substituted by another one, while the function of the swarm remains steady. That is, the architecture and functionality of classical SI are flat (Figure 1(a)).Two types of systems.
(a)
Flat structure(b)
Hierarchical structureHowever, swarm intelligence only explains partial mechanisms of collective behavior of biology. The natural cases could be more complex: except for individual tasks, these units lie at a hierarchical level between an individual ant and the colony as a whole, and thus constitute what might be called “intermediate-level parts” [27]. Now consider two basic types of systems: hierarchical and nonhierarchical (flat). Flat systems can be regarded as a group of undifferentiated particles, such as traditional SI systems. Hierarchical swarm systems must have a structure requiring a minimum of two hierarchical levels (Figure 1(b)). In Figure 1(b), a particle is the minimum unit of the system, while an agent constitutes the intermediate hierarchical level, which is composed of a number of particles. In this perspective, it is evident that the complexity of the individual “agents” of SI systems is dramatically simplified to particles, which are the minimum unit of the systems. Hence, the hierarchical nature of swarm [23] is ignored in the traditional artificial SI systems, such as PSO and ACO.Hierarchy is common in the real world. For examples, immune system antibodies continuously self-organize and evolve while being a part of the many “organism agents” of a bird, and that a bird is in turn an agent in the formation of a flock of birds, and the flock of birds is in turn an agent that is part of a particular ecosystem niche [28]. Genes, the elementary biochemical coding units are complicated macromolecular strings, as are the metabolic units, the proteins. Neurons, the basic elements of cognitive networks, themselves are cells. In any of these examples, it is evident that the interactions of the agents lead to a coherent structure at a higher level [29]. That is, the emergent characteristics of a particular lower level system frequently form an individual agent at a higher level of the hierarchical system. This aspect has been emphasized by many researchers on artificial intelligence and complex systems [23, 25, 29–32].Hence, this paper strives to extend the traditional SI framework from flat to hierarchical, and propose the hierarchical swarm optimization model. By incorporating these new degrees of complexity, HSO-based optimization algorithm can accommodate a considerable potential for solving more complex problems.


### 2.2. HSO Model Description

HSO model accommodates a hierarchical multiagent system, in which an agent can itself be a swarm of other agents.(1)
HSO is composed of a number of levels. Each level is a multiagent system composed of several swarms of agents.(2)
Each swarm of leveln-1 agents is aggregated into a level-n agent.(3)
Level-n behavior emerges from the organization of level 1 to n.HSO naturally admits of a description in terms of higher level and lower level, where the lower level is nested within the higher level. Any agent at any level is both a component of a given swarm in its own level and a subsystem decomposable into a swarm of other agents at its adjacent lower level of HSO (shown as in Figure2). Note that the agents in the lowest level are the particles that are the minimum unit, which are indecomposable of this hierarchical system. HSO is a heterogeneous system that each swarm in each level is evolved in its own population and adapts to the environment through the application of any SI method at hand. The interaction topology of HSO can also be heterogeneous hierarchical structures. Namely, the evolution rules and the interaction topology of distinct swarms can be different, and these different SI paradigms hierarchically construct the HSO model and lead to the hierarchical emergence of intelligence. In mathematical terms, the HSO model can be defined as in Table 1.Table 1
The structure of HSO model.
HSO=(A,N,P,T,O,S)A:agentsthatexistatvarioushierarchicallevels.N:thenumberoflevels.P:thepopulationsofeachswarmineachlevel.T:thehierarchicalinteractiontopologyofHSO.O:theobjectiveoptimizationgoals.S:SwarmorEvolutionaryoptimizationstrategiesusedforeachswarmtosearchtheobjectiveO.Figure 2
Hierarchical swarm optimization model using a multiagent system in nested hierarchies.Figure3 lists a general description of HSO containing four main functional blocks. In the first block of Figure 3, we show that under the external environment pressure (defined by the object function), each agent in the HSO model evolves and adapts as a consequence of internal and external hierarchical interactions. Both in higher level and lower level, the swarms can be manipulated by different SI algorithms (shown as in blocks 2 and 3 of Figure 3). In principle, any SI algorithms (such as PSO, ACO, BFO, and ABC) can be used by any swarm at any level, and we have first hand experience constructing HSO paradigms using PSO and BFO [33–35]. Interactions that occur within one level (each entity of the interaction is operating on the same spatiotemporal scale) are called symmetrical relations.Figure 3
The main functional blocks of the HSO model.On the other hand, asymmetrical relationships occuring between different levels are called “constraints” [32]. The forth block formed the constraint that higher level affects elements from lower level. When an agent of higher level transmits the information to its constituent swarms of other agents of lower level, the effect can be the according evolutional actions of this agent’s swarm of constituent agents.


## 2.1. From Flat Swarm to Hierarchical Swarm

In [3], Bonabeau et al. define swarm intelligence as “the emergent collective intelligence of groups of simple agents”. In such a perspective, the artificial SI systems, which are designed for complex problem solving, maintain a swarm made up of many isomorphic and relatively simple individuals that often share the same states and behaviors set. In such a swarm, all individuals have absolutely equal status in the whole life cycle. The interaction relations between these individuals are symmetrical and operate on the same spatiotemporal scale. One individual can be substituted by another one, while the function of the swarm remains steady. That is, the architecture and functionality of classical SI are flat (Figure 1(a)).Two types of systems.
(a)
Flat structure(b)
Hierarchical structureHowever, swarm intelligence only explains partial mechanisms of collective behavior of biology. The natural cases could be more complex: except for individual tasks, these units lie at a hierarchical level between an individual ant and the colony as a whole, and thus constitute what might be called “intermediate-level parts” [27]. Now consider two basic types of systems: hierarchical and nonhierarchical (flat). Flat systems can be regarded as a group of undifferentiated particles, such as traditional SI systems. Hierarchical swarm systems must have a structure requiring a minimum of two hierarchical levels (Figure 1(b)). In Figure 1(b), a particle is the minimum unit of the system, while an agent constitutes the intermediate hierarchical level, which is composed of a number of particles. In this perspective, it is evident that the complexity of the individual “agents” of SI systems is dramatically simplified to particles, which are the minimum unit of the systems. Hence, the hierarchical nature of swarm [23] is ignored in the traditional artificial SI systems, such as PSO and ACO.Hierarchy is common in the real world. For examples, immune system antibodies continuously self-organize and evolve while being a part of the many “organism agents” of a bird, and that a bird is in turn an agent in the formation of a flock of birds, and the flock of birds is in turn an agent that is part of a particular ecosystem niche [28]. Genes, the elementary biochemical coding units are complicated macromolecular strings, as are the metabolic units, the proteins. Neurons, the basic elements of cognitive networks, themselves are cells. In any of these examples, it is evident that the interactions of the agents lead to a coherent structure at a higher level [29]. That is, the emergent characteristics of a particular lower level system frequently form an individual agent at a higher level of the hierarchical system. This aspect has been emphasized by many researchers on artificial intelligence and complex systems [23, 25, 29–32].Hence, this paper strives to extend the traditional SI framework from flat to hierarchical, and propose the hierarchical swarm optimization model. By incorporating these new degrees of complexity, HSO-based optimization algorithm can accommodate a considerable potential for solving more complex problems.


## 2.2. HSO Model Description

HSO model accommodates a hierarchical multiagent system, in which an agent can itself be a swarm of other agents.(1)
HSO is composed of a number of levels. Each level is a multiagent system composed of several swarms of agents.(2)
Each swarm of leveln-1 agents is aggregated into a level-n agent.(3)
Level-n behavior emerges from the organization of level 1 to n.HSO naturally admits of a description in terms of higher level and lower level, where the lower level is nested within the higher level. Any agent at any level is both a component of a given swarm in its own level and a subsystem decomposable into a swarm of other agents at its adjacent lower level of HSO (shown as in Figure2). Note that the agents in the lowest level are the particles that are the minimum unit, which are indecomposable of this hierarchical system. HSO is a heterogeneous system that each swarm in each level is evolved in its own population and adapts to the environment through the application of any SI method at hand. The interaction topology of HSO can also be heterogeneous hierarchical structures. Namely, the evolution rules and the interaction topology of distinct swarms can be different, and these different SI paradigms hierarchically construct the HSO model and lead to the hierarchical emergence of intelligence. In mathematical terms, the HSO model can be defined as in Table 1.Table 1
The structure of HSO model.
HSO=(A,N,P,T,O,S)A:agentsthatexistatvarioushierarchicallevels.N:thenumberoflevels.P:thepopulationsofeachswarmineachlevel.T:thehierarchicalinteractiontopologyofHSO.O:theobjectiveoptimizationgoals.S:SwarmorEvolutionaryoptimizationstrategiesusedforeachswarmtosearchtheobjectiveO.Figure 2
Hierarchical swarm optimization model using a multiagent system in nested hierarchies.Figure3 lists a general description of HSO containing four main functional blocks. In the first block of Figure 3, we show that under the external environment pressure (defined by the object function), each agent in the HSO model evolves and adapts as a consequence of internal and external hierarchical interactions. Both in higher level and lower level, the swarms can be manipulated by different SI algorithms (shown as in blocks 2 and 3 of Figure 3). In principle, any SI algorithms (such as PSO, ACO, BFO, and ABC) can be used by any swarm at any level, and we have first hand experience constructing HSO paradigms using PSO and BFO [33–35]. Interactions that occur within one level (each entity of the interaction is operating on the same spatiotemporal scale) are called symmetrical relations.Figure 3
The main functional blocks of the HSO model.On the other hand, asymmetrical relationships occuring between different levels are called “constraints” [32]. The forth block formed the constraint that higher level affects elements from lower level. When an agent of higher level transmits the information to its constituent swarms of other agents of lower level, the effect can be the according evolutional actions of this agent’s swarm of constituent agents.


## 3. Case Study: The PS2O Algorithm

In this section, we implement a simple two-level HSO algorithm, which employs PSO method in each swarm of each level, and hence named it PS2O. Here the agents (particles) in the lower level (level-1) are analogous to individuals in a biological population (species) and the agents in the higher level (level-2) are analogous to species. As the hierarchical interactions that occur in the real ecosystems, from the macro view, dissimilar species establish symbiotic relationships to improve their survivability in level-1 of PS2O (i.e., interspecies cooperation); from the micro view, species’ members (the particles) cooperatively interact with each other in level-2 of PS2O (i.e., intraspecies cooperation).


### 3.1. Levels Detail of PS2O

Here the basic goals are to find the minimum off(x⃗),x⃗∈RD. We create an ecosystem in level-1 that contains a species set Ω={S1,S2,…,SM}, and each specieskpossesses a member set, Sk={X1k,X2k,…,XNk}, in level-2. The ith member of the kth species is characterized by the vector Xik=(Xik1,Xik2,…,XikD). In each generation t, the evolution process of each level is detailed as follow.


#### 3.1.1. Level 1

Level-1 agents are clustered intoMswarms, each of which possesses Nagents. Each swarm constitutes an agent of level-2. Each swarm of level-1 evolves within its own separate population via separate PSO algorithm. That is, there are M parallel PSO paradigms evolving separately in level-1. This process addresses the cooperation between individuals of the same species: within the species k, one or more members in the neighborhood of Xik contribute their experiments to Xik, and Xik also share its knowledge with its neighbors. Then Xik accelerate towards its personal best position and the best position found by its species members in neighborhood:(3.1)αikt+1=c1r1(pbestikt-Xikt)+c2r2(sbestkt-Xikt),
where αik is the social acceleration vector of Xik, pbestik is the personal best position found so far by Xik, sbestk is the best position found so far by its neighbors within species k, c1 are individual learning rate, c2 are social learning rate, and r1,r2∈ℜd are two random vectors uniformly distributed in [0,1].


#### 3.1.2. Level 2

All level-2 agents aggregate into a single swarm. This swarm of distinct symbiotic species coevolves via the social only version of the PSO [36] as the cognitive processes have already taken care of by the level-1 swarms. From the coevolution perspective, the species k accelerates towards the best position that the symbiotic partners of species k have found:(3.2)βkt+1=c3r3(cbestt-Skt),
where βk is the symbiotic acceleration vector of Sk, cbest is the best position found so far by the symbiotic partners of the kth species, c3 is the “symbiotic learning rate”, and r3∈ℜd is a uniform random sequence in the range [0,1].


#### 3.1.3. Constraints

When speciesk in level-2 accelerates towards the best position, cbest, found by its more successful symbiotic partners, the according evolutional action of this agent’s swarm of constituent agents from level-1 is that all the members of species k accelerate to cbest too(3.3)βikt+1=c3r3(cbestt-Xikt),
where βik is the symbiotic acceleration vector of Xik.Then the velocityVikand position Xikof each member of species k are updated according to (3.4)Vikt+1=χ(Vikt+αikt+1+βikt+1),Xikt+1=Xikt+Vikt+1,
where χ  is known as the constriction coefficient [37].


### 3.2. Hierarchical Interaction Topologies

Systems of interacting agents—like many natural and social systems—are typically depicted by scientists as the graphs or networks, in which Individuals can be connected to one another according to a great number of schemes [38]. In PSO, since the original particle swarm model is a simulation of the social environment, a neighborhood that structured as the interaction topological graph is defined for an individual particle as the subset of particles it is able to communicate with. Four classical interaction topologies have been shown as in Figure 4.Four interaction topologies for PSO: (a) fully-connected, (b) ring, (c) star, (d) grid.
(a)(b)(c)(d)Most particle swarm implementations use one of two simple interaction topologies. The first, namely, the fully-connected topology (see Figure4(a)), conceptually connects all members of the population to one another. The effect of this topology is that each particle is influenced by the very best performance of any member of the entire population. This means faster convergence, which implies a higher risk to converge to a local minimum. Experiments show that the fully-connected topology is faster than the other neighborhoods, but it meets the optimal fewer times than any other one. The second, called ring topology (see Figure 4(b)), creates a neighborhood for each individual comprising itself and its two nearest neighbors in the population. The ring neighborhood is more robust if the maximum number of iterations was increased but much slower. However, experiments show that the ring neighborhood cannot meet the required precision for many complex problems. That is, it promotes the exploration, but unfortunately fails to provide the exploitation.In our model, the interaction of agents occurred in a two-level hierarchical topology. By employing two simple topologies—the ring and the fully-connected topologies—for swarms in different levels, four hierarchically nested interaction topologies have been obtained. Shown as in Figure5, each hierarchical topology is comprised of 4 warms in level-2 and each swarm possesses 4 agents from level-1. The first two topologies have a homogeneous hierarchical structure (employ the ring or fully-connected topology in both levels) and the other two have the heterogeneous hierarchical structures (employ the ring and fully-connected topologies in different levels, resp.). Four variant versions of the PS2O algorithms are studied, respectively, in this paper according to these four interaction topologies.(i)
PS2O-S: in level-1, agents interact with each other in each swarm. In level-2, each agent is influenced by the performance of all the other agents. That is, swarms of both levels are configured into the fully-connected topology (Figure 5(a)).(ii)
PS2O-R: in level-1, agents interact with 2 immediate agents in its neighborhood. In level-2, each agent is influenced by the performance of its two symbiotic partners only. That is, both levels are configured into the ring topology (Figure 5(b)).(iii)
PS2O-SR: In level-1, agents interact with each other in each swarm. In level-2, each agent is influenced by the performance of its two symbiotic partners only. That is, the level-2 is configured into the fully-connected topology while the each swarm of level-1 is configured into the ring topology (Figure 5(c)).(iv)
PS2O-RS: In level-1, each agent interacts with 2 immediate agents in its neighborhood. In level-2, each agent is influenced by the performance of all the other agents. That is, each swarm of the level-1 is configured into the ring topology while the level-2 is configured into the fully-connected topology (Figure 5(d)).Four hierarchical interaction topologies for PS2O.
(a)(b)(c)(d)


### 3.3. Matrix Representation

A multidimensional array representation of the PS2O algorithm is proposed in this section. The PS2O randomly initializes a number of M species with each possesses a number of N members to represent the biological community in the natural ecosystems. Then the positions X, velocities V, and personal best locations Pof the biological community are all specified as the three-dimensional (3D) matrixes (showed as in Figures 6(a)–6(c)), where the first matrix dimension—Species number—is the number of species in level-2, the second matrix dimension—Swarm size—is the number of agents of each swarm in level-1, and the third matrix dimension—Dimension—is the number of dimensions of the object problem.Matrix representation of the PS2O algorithm.
(a)(b)(c)(d)In PS2O model, in order to update the velocity and position matrixes, every agent in level-1 must accelerate to three factors: the previous best position of the agent itself (this factor is called “personal best”), the previous best position of other members in its neighborhood (we named this factor “species best”), and the previous best position found by other species (agents from level-2) that have the cooperative symbiotic relation to the species that this agent belongs to (we named this factor “community best”). The species best is represented by a 2D matrix S, which showed as in Figure 6(d) left, and the community best is referred to as a 1D matrix C, which showed as in Figure 6(d) right.X,V,P,S, and C matrixes together record all of the update information required by the PS2O algorithm. These 3D matrixes are elegantly updated in successive iteration to numerically model the hierarchical emergence. The velocity and position matrixes must be updated element by element in each generation as.(3.5)Vijkt+1=χ(Vijkt+φ1r1(Pijkt-Xijkt)+φ2r2(Sjkt-Xijkt)︸lower level  evolution+φ3r3(Cjt-Xijkt)︸higher level  evolution),Xijkt+1=Xijkt+Vijkt+1
to obtain the intended behaviors. Note that these equations are exactly described in the previous section: the term φ1r1(Pijkt-Xijkt) associates with each individual’s own cognition, the term φ2r2(Sjkt-Xijkt) associates with cooperative coevolution within each swarm in level-1, and the term φ3r3(Cjt-Xijkt) associates with the symbiotic coevolution between dissimilar species in level-2.The main difference between PS2O and PSO is the matrix implementation and the modified velocity updating equation, that is, the complexity of this new HSO algorithm is similar to the original PSO. The flowchart of the PS2O algorithm is presented in Figure 7, and according variables used in PS2O are summarized in Table 2.Table 2
Parameters of the PS2O.
MThe number of agents (species) in level-2NPopulation size of each species in level-1kSpecies’ ID counter from 1 toMiIndividual’s ID counter from 1 toNjDimension counter from 1 toDtGeneration counter from 1 tomax-genXijkTheith individual’s (of the kth species) jh dimension’s position valueVijkTheith individual’s (of the kth species) jh dimension’s velocity valuePijkThejth dimension value of the ith individual’s (of the kth species) personal best positionSjkThejth dimension position value of the best position found by the kth level-2 speciesCjThejth dimension value of the community best positionχThe constriction coefficientc1The learning rates for individual cognitionc2The learning rates for intraspecies cooperationc3The learning rates for interspecies coevolutionFigure 7
Flowchart of the PS2O algorithm.


## 3.1. Levels Detail of PS2O

Here the basic goals are to find the minimum off(x⃗),x⃗∈RD. We create an ecosystem in level-1 that contains a species set Ω={S1,S2,…,SM}, and each specieskpossesses a member set, Sk={X1k,X2k,…,XNk}, in level-2. The ith member of the kth species is characterized by the vector Xik=(Xik1,Xik2,…,XikD). In each generation t, the evolution process of each level is detailed as follow.


### 3.1.1. Level 1

Level-1 agents are clustered intoMswarms, each of which possesses Nagents. Each swarm constitutes an agent of level-2. Each swarm of level-1 evolves within its own separate population via separate PSO algorithm. That is, there are M parallel PSO paradigms evolving separately in level-1. This process addresses the cooperation between individuals of the same species: within the species k, one or more members in the neighborhood of Xik contribute their experiments to Xik, and Xik also share its knowledge with its neighbors. Then Xik accelerate towards its personal best position and the best position found by its species members in neighborhood:(3.1)αikt+1=c1r1(pbestikt-Xikt)+c2r2(sbestkt-Xikt),
where αik is the social acceleration vector of Xik, pbestik is the personal best position found so far by Xik, sbestk is the best position found so far by its neighbors within species k, c1 are individual learning rate, c2 are social learning rate, and r1,r2∈ℜd are two random vectors uniformly distributed in [0,1].


### 3.1.2. Level 2

All level-2 agents aggregate into a single swarm. This swarm of distinct symbiotic species coevolves via the social only version of the PSO [36] as the cognitive processes have already taken care of by the level-1 swarms. From the coevolution perspective, the species k accelerates towards the best position that the symbiotic partners of species k have found:(3.2)βkt+1=c3r3(cbestt-Skt),
where βk is the symbiotic acceleration vector of Sk, cbest is the best position found so far by the symbiotic partners of the kth species, c3 is the “symbiotic learning rate”, and r3∈ℜd is a uniform random sequence in the range [0,1].


### 3.1.3. Constraints

When speciesk in level-2 accelerates towards the best position, cbest, found by its more successful symbiotic partners, the according evolutional action of this agent’s swarm of constituent agents from level-1 is that all the members of species k accelerate to cbest too(3.3)βikt+1=c3r3(cbestt-Xikt),
where βik is the symbiotic acceleration vector of Xik.Then the velocityVikand position Xikof each member of species k are updated according to (3.4)Vikt+1=χ(Vikt+αikt+1+βikt+1),Xikt+1=Xikt+Vikt+1,
where χ  is known as the constriction coefficient [37].


## 3.1.1. Level 1

Level-1 agents are clustered intoMswarms, each of which possesses Nagents. Each swarm constitutes an agent of level-2. Each swarm of level-1 evolves within its own separate population via separate PSO algorithm. That is, there are M parallel PSO paradigms evolving separately in level-1. This process addresses the cooperation between individuals of the same species: within the species k, one or more members in the neighborhood of Xik contribute their experiments to Xik, and Xik also share its knowledge with its neighbors. Then Xik accelerate towards its personal best position and the best position found by its species members in neighborhood:(3.1)αikt+1=c1r1(pbestikt-Xikt)+c2r2(sbestkt-Xikt),
where αik is the social acceleration vector of Xik, pbestik is the personal best position found so far by Xik, sbestk is the best position found so far by its neighbors within species k, c1 are individual learning rate, c2 are social learning rate, and r1,r2∈ℜd are two random vectors uniformly distributed in [0,1].


## 3.1.2. Level 2

All level-2 agents aggregate into a single swarm. This swarm of distinct symbiotic species coevolves via the social only version of the PSO [36] as the cognitive processes have already taken care of by the level-1 swarms. From the coevolution perspective, the species k accelerates towards the best position that the symbiotic partners of species k have found:(3.2)βkt+1=c3r3(cbestt-Skt),
where βk is the symbiotic acceleration vector of Sk, cbest is the best position found so far by the symbiotic partners of the kth species, c3 is the “symbiotic learning rate”, and r3∈ℜd is a uniform random sequence in the range [0,1].


## 3.1.3. Constraints

When speciesk in level-2 accelerates towards the best position, cbest, found by its more successful symbiotic partners, the according evolutional action of this agent’s swarm of constituent agents from level-1 is that all the members of species k accelerate to cbest too(3.3)βikt+1=c3r3(cbestt-Xikt),
where βik is the symbiotic acceleration vector of Xik.Then the velocityVikand position Xikof each member of species k are updated according to (3.4)Vikt+1=χ(Vikt+αikt+1+βikt+1),Xikt+1=Xikt+Vikt+1,
where χ  is known as the constriction coefficient [37].


## 3.2. Hierarchical Interaction Topologies

Systems of interacting agents—like many natural and social systems—are typically depicted by scientists as the graphs or networks, in which Individuals can be connected to one another according to a great number of schemes [38]. In PSO, since the original particle swarm model is a simulation of the social environment, a neighborhood that structured as the interaction topological graph is defined for an individual particle as the subset of particles it is able to communicate with. Four classical interaction topologies have been shown as in Figure 4.Four interaction topologies for PSO: (a) fully-connected, (b) ring, (c) star, (d) grid.
(a)(b)(c)(d)Most particle swarm implementations use one of two simple interaction topologies. The first, namely, the fully-connected topology (see Figure4(a)), conceptually connects all members of the population to one another. The effect of this topology is that each particle is influenced by the very best performance of any member of the entire population. This means faster convergence, which implies a higher risk to converge to a local minimum. Experiments show that the fully-connected topology is faster than the other neighborhoods, but it meets the optimal fewer times than any other one. The second, called ring topology (see Figure 4(b)), creates a neighborhood for each individual comprising itself and its two nearest neighbors in the population. The ring neighborhood is more robust if the maximum number of iterations was increased but much slower. However, experiments show that the ring neighborhood cannot meet the required precision for many complex problems. That is, it promotes the exploration, but unfortunately fails to provide the exploitation.In our model, the interaction of agents occurred in a two-level hierarchical topology. By employing two simple topologies—the ring and the fully-connected topologies—for swarms in different levels, four hierarchically nested interaction topologies have been obtained. Shown as in Figure5, each hierarchical topology is comprised of 4 warms in level-2 and each swarm possesses 4 agents from level-1. The first two topologies have a homogeneous hierarchical structure (employ the ring or fully-connected topology in both levels) and the other two have the heterogeneous hierarchical structures (employ the ring and fully-connected topologies in different levels, resp.). Four variant versions of the PS2O algorithms are studied, respectively, in this paper according to these four interaction topologies.(i)
PS2O-S: in level-1, agents interact with each other in each swarm. In level-2, each agent is influenced by the performance of all the other agents. That is, swarms of both levels are configured into the fully-connected topology (Figure 5(a)).(ii)
PS2O-R: in level-1, agents interact with 2 immediate agents in its neighborhood. In level-2, each agent is influenced by the performance of its two symbiotic partners only. That is, both levels are configured into the ring topology (Figure 5(b)).(iii)
PS2O-SR: In level-1, agents interact with each other in each swarm. In level-2, each agent is influenced by the performance of its two symbiotic partners only. That is, the level-2 is configured into the fully-connected topology while the each swarm of level-1 is configured into the ring topology (Figure 5(c)).(iv)
PS2O-RS: In level-1, each agent interacts with 2 immediate agents in its neighborhood. In level-2, each agent is influenced by the performance of all the other agents. That is, each swarm of the level-1 is configured into the ring topology while the level-2 is configured into the fully-connected topology (Figure 5(d)).Four hierarchical interaction topologies for PS2O.
(a)(b)(c)(d)


## 3.3. Matrix Representation

A multidimensional array representation of the PS2O algorithm is proposed in this section. The PS2O randomly initializes a number of M species with each possesses a number of N members to represent the biological community in the natural ecosystems. Then the positions X, velocities V, and personal best locations Pof the biological community are all specified as the three-dimensional (3D) matrixes (showed as in Figures 6(a)–6(c)), where the first matrix dimension—Species number—is the number of species in level-2, the second matrix dimension—Swarm size—is the number of agents of each swarm in level-1, and the third matrix dimension—Dimension—is the number of dimensions of the object problem.Matrix representation of the PS2O algorithm.
(a)(b)(c)(d)In PS2O model, in order to update the velocity and position matrixes, every agent in level-1 must accelerate to three factors: the previous best position of the agent itself (this factor is called “personal best”), the previous best position of other members in its neighborhood (we named this factor “species best”), and the previous best position found by other species (agents from level-2) that have the cooperative symbiotic relation to the species that this agent belongs to (we named this factor “community best”). The species best is represented by a 2D matrix S, which showed as in Figure 6(d) left, and the community best is referred to as a 1D matrix C, which showed as in Figure 6(d) right.X,V,P,S, and C matrixes together record all of the update information required by the PS2O algorithm. These 3D matrixes are elegantly updated in successive iteration to numerically model the hierarchical emergence. The velocity and position matrixes must be updated element by element in each generation as.(3.5)Vijkt+1=χ(Vijkt+φ1r1(Pijkt-Xijkt)+φ2r2(Sjkt-Xijkt)︸lower level  evolution+φ3r3(Cjt-Xijkt)︸higher level  evolution),Xijkt+1=Xijkt+Vijkt+1
to obtain the intended behaviors. Note that these equations are exactly described in the previous section: the term φ1r1(Pijkt-Xijkt) associates with each individual’s own cognition, the term φ2r2(Sjkt-Xijkt) associates with cooperative coevolution within each swarm in level-1, and the term φ3r3(Cjt-Xijkt) associates with the symbiotic coevolution between dissimilar species in level-2.The main difference between PS2O and PSO is the matrix implementation and the modified velocity updating equation, that is, the complexity of this new HSO algorithm is similar to the original PSO. The flowchart of the PS2O algorithm is presented in Figure 7, and according variables used in PS2O are summarized in Table 2.Table 2
Parameters of the PS2O.
MThe number of agents (species) in level-2NPopulation size of each species in level-1kSpecies’ ID counter from 1 toMiIndividual’s ID counter from 1 toNjDimension counter from 1 toDtGeneration counter from 1 tomax-genXijkTheith individual’s (of the kth species) jh dimension’s position valueVijkTheith individual’s (of the kth species) jh dimension’s velocity valuePijkThejth dimension value of the ith individual’s (of the kth species) personal best positionSjkThejth dimension position value of the best position found by the kth level-2 speciesCjThejth dimension value of the community best positionχThe constriction coefficientc1The learning rates for individual cognitionc2The learning rates for intraspecies cooperationc3The learning rates for interspecies coevolutionFigure 7
Flowchart of the PS2O algorithm.


## 4. Experimental Result and Discussion

In experimental studies, according to the no free lunch (NFL) theorem [39], a set of 17 benchmark functions (with continuous and discrete characters), which are listed in the appendix, was employed to fully evaluate the performance of the PS2O algorithm without a biased conclusion towards some chosen problems.


### 4.1. Experimental Setting

Experiments were conducted with four variations of PS2O (PS2Os) according to the four hierarchical interaction topologies. To fully evaluate the performance of the proposed PS2O, seven successful EA and SI algorithms were used for comparisons:(i)
canonical PSO with constriction factor (PSO) [37],(ii)
fully informed particle swarm (FIPS) [40],(iii)
unified particle swarm (UPSO) [41],(iv)
fitness-Distance-Ratio-based PSO (FDR-PSO) [42],(v)
standard genetic algorithm (GA) [43],(vi)
covariance matrix adaptation evolution strategy (CMA-ES) [44],(vii)
artificial bee colony algorithm (ABC) [15].Among these optimization tools, GA is the classical search technique that enables the fittest candidate among discrete strings to survive and reproduce based on random information search and exchange imitating the natural biological selection; the underlying idea of CMA-ES is to gather information about successful search steps, and to use that information to modify the covariance matrix of the mutation distribution in a goal-directed, derandomized fashion; ABC is a recently developed SI paradigm simulating foraging behavior of bees; UPSO combined the global version and local version PSO together to construct a unified particle swarm optimizer; FIPS used all the neighbors’ knowledge of the particle to update the velocity; when updating each velocity dimension, the FDR-PSO selects one other particlenbest, which has a higher fitness value and is nearer to the particle being updated.In all experiments in this section, the values of the common parameters used in each algorithm such as population size and total generation number were chosen to be the same. Population size was 150 and the maximum evaluation number was 10000 for continuous functions and 1000 for discrete functions.According to Clerc’s method [37], when constriction factor is implemented as in the canonical PSO algorithm, χ is calculated from the values of the acceleration coefficients (i.e., the learning rate) c1 andc2; importantly, it is the sum of these two coefficients that determines what χ to use. This fact implies that the particle’s velocity can be adjusted by any number of terms, as long as the acceleration coefficients sum to an appropriate value. Thus, the constriction factor χ in velocity formula of PS2O can be calculated by(4.1)χ=2|2-ϕ-ϕ2-4ϕ|,
where ϕ=c1+c2+c3,ϕ>4. Then the algorithm will behave properly, at least as far as its convergence and explosion characteristics, whether all of ϕ is allocated to one term, or it is divided into thirds, fourths, and so forth. Hence, for each PS2O, except  when different interaction topologies are used, the parameters were set to the values c1=c2=c3=1.3667(i.e., ϕ=c1+c2+c3≈4.1>4) and then χ= 0.729, which is calculated by (4.1).All the control parameters for the other algorithms were set to be default of their original literatures. In continuous optimization experiment, for CMA-ES, initialization conditions are the same as in [44], and the number of offspring candidate solutions generated per time step is λ=4μ; for ABC, the limit parameter is set to be SN×D, where Dis the dimension of the problem and SN is the number of employed bees; for canonical PSO and UPSO, the learning rates c1 and c2 were both 2.05 and the constriction factor χ= 0.729; for FIPS, the constriction factor χ equals to 0.729 and the U-ring topology that achieved highest success rate is used; for FDR-PSO, the inertia weight ω started at 0.9 and ended at 0.5 and a setting of c1=c2=2.0was adopted.Since there are no literatures using CMA-ES, ABC, UPSO, FIPS, and FDR-PSO for discrete optimization so far, discrete optimization experiment just compares PS2Os with the binary version of canonical PSO and standard GA in discrete cases. For GA, single-point crossover operation with the rate of 0.8 was employed and mutation rate was set to be 0.01. For discrete PSO, the parameters were set to the values c1=c2=2 and χ= 1. For PS2O variants, the parameters were set to the values c1=c2=c3=2 and χ= 1. The sigmoid function S was used as the transfer function to discrete the position X of PSO and PS2O variants [45]. Then the velocity update equation remains unchanged, while the position update equation is defined by the following equation (4.2) for discrete problems:(4.2)if(rand()<S(Vijkt+1)),Xijkt+1=1,elseXijkt+1=0.The number of agents (species) in level-2 (i.e., swarm numberM of the level-2 swarm) needs be tuned. Six benchmark functions—Sphere 10D, Rosenbrock 10D, Rastrigrin 10D, Goldberg 120D, Bipolar 60D, and Discrete multimodal problem 100D—are used to investigate the impact of this parameter. Experiments were executed with PS2O-R on Sphere, PS2O-SR on Rosenbrock, PS2O-S on Rastrigrin, PS2O-R on Goldberg, PS2O-RS on Bipolar, and PS2O-S on Discrete multimodal problem by changing the number of swarms and fixing each swarm size N at 10.  The average test results obtained from 30 runs are plot in Figure 8. For continuous problems, the performance measurement is the average best-so-far fitness value; while for discrete cases, the performance measurement is the mean iteration to the function minimum 0.  From Figure 8, we can observe that the performance of PS2Os is sensitive to the number of agents in level-2. When M increased, we obtained faster convergence velocity and better results on all test functions. However, it can be observed that the performance improvement is not evident when M>15 for most test functions. Thus, in our experiments, the parameter M of PS2Os is set at 15 for all test functions (i.e., each swarm of level-2 possesses N=100/10=10 agents of level 1).PS2O’s results on six test functions with different swarm numberM.
(a)(b)(c)(d)(e)(f)The experiment runs 30 times, respectively, for each algorithm on each benchmark function. The numbers of generations for the 10 continuous benchmark functions were set to be 10000 and for the 7 discrete functions were 1000, respectively.


### 4.2. Continuous Unimodal Functions

Unimodal problems have been adopted to assess the convergence rates of optimization algorithms. We test the four PS2O variants on a set of unimodal functions (f1–f5) in comparison with CMA-ES, ABC, PSO, FIPS, UPSO, and FDR-PSO algorithms. Table 3 lists the experimental results (i.e., the mean and standard deviations of the function values found in 30 runs) for each algorithm on f1–f5. Figure 9 shows the search progress of the average values found by the eight algorithms over 30 runs for f1–f5.Table 3
Performance of all algorithms on benchmark functionsf1–f5. In bold are the best results.
Func.PS2O-SPS2O-RPS2O-SRPS2O-RSPSOFIPSUPSOFDR-PSOCMA-ESABCMean006.24e-30502.42e-1141.73e-0293.71e-1832.47e-16905.52e-016f1Std00003.39e-1142.29e-0290008.47e-017Rank11417865110Mean1.32e-0011.04e-0142.55e-0163.71e-0266.61e+0002.25e+0012.09e+0002.79e-0017.91e-0298.80e-002f2Std7.27e-0019.71e-0151.70e-0161.09e-0254.02e-0011.27e+0007.69e-0011.02e+0001.77e-0297.98e-002Rank64329108715Mean1.04e-0902.19e-0471.42e-0512.50e-0923.51e-0181.38e+0006.12e-0134.25e-0143.95e-2351.16e+001f3Std5.01e-0906.82e-0474.28e-0511.02e-0917.88e-0181.00e+0006.06e-0132.32e-01304.57e+000Rank35426108719Mean0008.23e-3204.54e-1855.03e-06508.64e-2809.48e-0067.75e-006f4Std000002.38e-064001.27e-0058.50e-006Rank11157816109Mean001.38e-0021.14e-0014.84e-0021.38e-00203.50e-0039.28e-0325.68e-016f5Std003.58e-0022.80e-0018.04e-0024.50e-00201.89e-0026.57e-0338.19e-017Rank11710981645Aver. Rank242.43.849.58.84.86.23.47.6Final Rank11451096738The median convergence results of 30D unimodal continuous functions. (a) Sphere function. (b) Rosenbrock’s function. (c) Quadric function. (d) Sum of different powers. (e) Sin function.
(a)(b)(c)(d)(e)From Table3 and Figure 9, the four PS2O variants converged much faster to significantly better results than all other algorithms. The PS2O-RS, which has the heterogeneous hierarchical structures, is the fastest one for finding good results within relatively few generations. All PS2O variants were able to consistently find the minimum to functions f1, f4, and f5 within 10000 generations.From the comparisons between PS2O and other algorithms, we can see that, statistically, PS2O has significantly better performance on continuous unimodal functions f1–f5. From the rank values presented in Table 2, the search performance of the algorithms tested here is ordered as PS2O-S > PS2O-R > CMA-ES > PS2O-SR> PS2O-RS> UPSO > FDR-PSO > ABC > FIPS > PSO.


### 4.3. Continuous Multimodal Functions

The first four multimodal functionsf6–f9 are regarded as the most difficult functions to optimize since the number of local minima increases exponentially as the function dimension increases. According to the results reported in [22], the methods CL-PSO, PSO, CMA-ES, G3-PCX, DE, and the algorithms used for comparison all failed to find the minimum of the six composition function designed by Liang. Since these mentioned methods have demonstrated their excellent performance on standard benchmark functions, the six composition functions are very complex. In this paper, we only test PS2O on the first composition function f10 and the test on the other five composition functions will be studied in the future works. The mean and standard deviations of the function values found in 30 runs for each algorithm on each function are listed in Table 4. Figure 10 shows the search progress of the average values found by the ten algorithms over 30 runs for functions f6–f10.Table 4
Performance of all algorithms on benchmark functionsf6–f10. In bold are the best results.
Func.PS2O-SPS2O-RPS2O-SRPS2O-RSPSOFIPSUPSOFDR-PSOCMA-ESABCMean7.11e-0154.74e-0154.97e-0158.32e-0026.16e-0152.04e-0143.55e-0152.74e-0141.96e+0014.79e-014f6Std01.70e-0151.77e-0153.17e-0021.80e-0151.08e-0143.16e-0151.03e-0144.30e-0016.09e-015Rank13495627108Mean4.47e+0013.25e+0013.61e+0014.61e+0012.78e+0014.13e+0014.96e+0012.60e+0017.56e+0001.64e-013f7Std1.20e+0018.41e+0008.96e+0001.11e+0015.46e+0002.34e+0019.80e+0008.32e+0002.15e+0006.25e-014Rank95684710321Mean8.37e-003009.26e-0031.83e-0021.56e-0033.47e-0031.79e-00201.03e-015f8Std1.09e-002001.07e-0022.66e-0023.78e-0034.78e-0031.82e-00201.17e-015Rank71181056914Mean1.17e+000001.22e+0001.35e+0002.01e-0024.42e+0001.58e-0012.15e+0000f9Std7.68e-001008.64e-0011.16e+0005.58e-0022.60e+0004.56e-0012.98e+0000Rank61178410591Mean0004.00e+0015.00e+0013.37e+0018.00e+0011.00e+0021.30e+0023.83e-002f10Std0008.94e+0001.82e+0022.58e+0014.42e+0014.42e+0011.63e+0021.21e-001Rank11167589104Aver. Rank4.82.22.67.66.85.47.26.66.43.6Final Rank41210859763The median convergence results of 30D multimodal continuous functions. (a) Ackley’s function. (b) Rastrigin’s function. (c) Griewank’s function. (d) Weierstrass function. (e) Composition function 1.
(a)(b)(c)(d)(e)From Table4 and Figure 10, it is clear to see that for most of the tested continuous benchmark functions, all PS2O algorithms except PS2O-RS markedly outperformed the other algorithms. For example, PS2O-R and PS2O-SR found the global minimum every time of run on function f8–f10, and PS2O-R can also consistently found the minimum of f10 within relatively fewer generations, while the other algorithms generated poorer results on them. On functions f6 and f7, the four PS2O algorithms yielded similar results to the other four algorithms. From the rank values presented in Table 4, the search performance of the algorithms tested here is ordered as PS2O-R > PS2O-SR> ABC > PS2O-S > FIPS CMA-ES > FDR-PSO > PSO > UPSO > PS2O-RS.It should be mentioned that PS2O were the only ones able to consistently find the minimum to the composition function f1 that reported in the literatures so far.


### 4.4. Discrete Functions

In binary optimization, it is very easy to design some algorithms that are extremely good on some benchmarks (and extremely bad on some others) [46]. In order to fully evaluate the performance of PS2O on discrete problems, we have employed a carefully chosen set of discrete benchmark functions f11–f17. The results obtained by the GA, PSO, and four PS2O algorithms on each discrete benchmark function are listed in Table 5, including the mean number of iterations required to reach the minimum, mean, and standard deviations of the function values found in 30 runs. Figure 11 shows the search progress of the average values found by the five algorithms over 30 runs for functions f11–f17.Table 5
Performance of all algorithms on benchmark functionsf11–f17. In bold are the best results.
Func.PS2O-SPS2O-RPS2O-SRPS2O-RSPSOGAf11Mean001.67e-00202.14e+0001.26e-001Std005.31e-00202.60e-0011.41e-001Iter.142433528∞∞Rank124365f12Mean003.33e-00203.19e+0002.64e-001Std001.18e-00103.81e-0011.06e-001Iter.31069493328∞∞Rank214365f13Mean00003.96e+0000Std00001.33e+0000Iter.13482426275∞335Rank215364f14Mean4.00e-00306.70e-00302.94e-0012.38e-001Std1.98e-00202.54e-00201.33e-0028.05e-002Iter.871367538398∞∞Rank413265f15Mean000001.36e-001Std000001.30e-001Iter.1789147107356∞Rank124356f16Mean00002.00e-0031.80e-001Std00001.41e-0022.44e-001Iter.203272187151∞∞Rank342156Mean000007.44e-002f17Std000001.83e-002Iter.3951395561∞Rank131456Aver. Rank223.292.715.575.14Final Rank114365The median results of discrete functions. (a) Goldberg’s order-3. (b) Bipolar order-6. (c) Mulenbein’s order-5. (d) Clerc’s Zebra-3. The median convergence results of discrete functions. (e) Clerc’s order-3 problem 1. (f) Clerc’s order-3 problem 2. (g) Discrete multimodal problem.
(a)(b)(c)(d)(e)(f)(g)From the results, we can observe that PS2O obtain an obviously remarkable performance. It can be seen from Figure 11 that all PS2O variants converged greatly faster and to significantly better results than the other two algorithms for all discrete cases. From the rank values presented in Table 5, the search performance of the algorithms tested here is ordered as PS2O-R > PS2O-S > PS2O-RS> PS2O-SR> GA > PSO. It is worth mentioning that the PS2O-R and PS2O-RS were able to consistently find the minimum to all discrete benchmark functions.


## 4.1. Experimental Setting

Experiments were conducted with four variations of PS2O (PS2Os) according to the four hierarchical interaction topologies. To fully evaluate the performance of the proposed PS2O, seven successful EA and SI algorithms were used for comparisons:(i)
canonical PSO with constriction factor (PSO) [37],(ii)
fully informed particle swarm (FIPS) [40],(iii)
unified particle swarm (UPSO) [41],(iv)
fitness-Distance-Ratio-based PSO (FDR-PSO) [42],(v)
standard genetic algorithm (GA) [43],(vi)
covariance matrix adaptation evolution strategy (CMA-ES) [44],(vii)
artificial bee colony algorithm (ABC) [15].Among these optimization tools, GA is the classical search technique that enables the fittest candidate among discrete strings to survive and reproduce based on random information search and exchange imitating the natural biological selection; the underlying idea of CMA-ES is to gather information about successful search steps, and to use that information to modify the covariance matrix of the mutation distribution in a goal-directed, derandomized fashion; ABC is a recently developed SI paradigm simulating foraging behavior of bees; UPSO combined the global version and local version PSO together to construct a unified particle swarm optimizer; FIPS used all the neighbors’ knowledge of the particle to update the velocity; when updating each velocity dimension, the FDR-PSO selects one other particlenbest, which has a higher fitness value and is nearer to the particle being updated.In all experiments in this section, the values of the common parameters used in each algorithm such as population size and total generation number were chosen to be the same. Population size was 150 and the maximum evaluation number was 10000 for continuous functions and 1000 for discrete functions.According to Clerc’s method [37], when constriction factor is implemented as in the canonical PSO algorithm, χ is calculated from the values of the acceleration coefficients (i.e., the learning rate) c1 andc2; importantly, it is the sum of these two coefficients that determines what χ to use. This fact implies that the particle’s velocity can be adjusted by any number of terms, as long as the acceleration coefficients sum to an appropriate value. Thus, the constriction factor χ in velocity formula of PS2O can be calculated by(4.1)χ=2|2-ϕ-ϕ2-4ϕ|,
where ϕ=c1+c2+c3,ϕ>4. Then the algorithm will behave properly, at least as far as its convergence and explosion characteristics, whether all of ϕ is allocated to one term, or it is divided into thirds, fourths, and so forth. Hence, for each PS2O, except  when different interaction topologies are used, the parameters were set to the values c1=c2=c3=1.3667(i.e., ϕ=c1+c2+c3≈4.1>4) and then χ= 0.729, which is calculated by (4.1).All the control parameters for the other algorithms were set to be default of their original literatures. In continuous optimization experiment, for CMA-ES, initialization conditions are the same as in [44], and the number of offspring candidate solutions generated per time step is λ=4μ; for ABC, the limit parameter is set to be SN×D, where Dis the dimension of the problem and SN is the number of employed bees; for canonical PSO and UPSO, the learning rates c1 and c2 were both 2.05 and the constriction factor χ= 0.729; for FIPS, the constriction factor χ equals to 0.729 and the U-ring topology that achieved highest success rate is used; for FDR-PSO, the inertia weight ω started at 0.9 and ended at 0.5 and a setting of c1=c2=2.0was adopted.Since there are no literatures using CMA-ES, ABC, UPSO, FIPS, and FDR-PSO for discrete optimization so far, discrete optimization experiment just compares PS2Os with the binary version of canonical PSO and standard GA in discrete cases. For GA, single-point crossover operation with the rate of 0.8 was employed and mutation rate was set to be 0.01. For discrete PSO, the parameters were set to the values c1=c2=2 and χ= 1. For PS2O variants, the parameters were set to the values c1=c2=c3=2 and χ= 1. The sigmoid function S was used as the transfer function to discrete the position X of PSO and PS2O variants [45]. Then the velocity update equation remains unchanged, while the position update equation is defined by the following equation (4.2) for discrete problems:(4.2)if(rand()<S(Vijkt+1)),Xijkt+1=1,elseXijkt+1=0.The number of agents (species) in level-2 (i.e., swarm numberM of the level-2 swarm) needs be tuned. Six benchmark functions—Sphere 10D, Rosenbrock 10D, Rastrigrin 10D, Goldberg 120D, Bipolar 60D, and Discrete multimodal problem 100D—are used to investigate the impact of this parameter. Experiments were executed with PS2O-R on Sphere, PS2O-SR on Rosenbrock, PS2O-S on Rastrigrin, PS2O-R on Goldberg, PS2O-RS on Bipolar, and PS2O-S on Discrete multimodal problem by changing the number of swarms and fixing each swarm size N at 10.  The average test results obtained from 30 runs are plot in Figure 8. For continuous problems, the performance measurement is the average best-so-far fitness value; while for discrete cases, the performance measurement is the mean iteration to the function minimum 0.  From Figure 8, we can observe that the performance of PS2Os is sensitive to the number of agents in level-2. When M increased, we obtained faster convergence velocity and better results on all test functions. However, it can be observed that the performance improvement is not evident when M>15 for most test functions. Thus, in our experiments, the parameter M of PS2Os is set at 15 for all test functions (i.e., each swarm of level-2 possesses N=100/10=10 agents of level 1).PS2O’s results on six test functions with different swarm numberM.
(a)(b)(c)(d)(e)(f)The experiment runs 30 times, respectively, for each algorithm on each benchmark function. The numbers of generations for the 10 continuous benchmark functions were set to be 10000 and for the 7 discrete functions were 1000, respectively.


## 4.2. Continuous Unimodal Functions

Unimodal problems have been adopted to assess the convergence rates of optimization algorithms. We test the four PS2O variants on a set of unimodal functions (f1–f5) in comparison with CMA-ES, ABC, PSO, FIPS, UPSO, and FDR-PSO algorithms. Table 3 lists the experimental results (i.e., the mean and standard deviations of the function values found in 30 runs) for each algorithm on f1–f5. Figure 9 shows the search progress of the average values found by the eight algorithms over 30 runs for f1–f5.Table 3
Performance of all algorithms on benchmark functionsf1–f5. In bold are the best results.
Func.PS2O-SPS2O-RPS2O-SRPS2O-RSPSOFIPSUPSOFDR-PSOCMA-ESABCMean006.24e-30502.42e-1141.73e-0293.71e-1832.47e-16905.52e-016f1Std00003.39e-1142.29e-0290008.47e-017Rank11417865110Mean1.32e-0011.04e-0142.55e-0163.71e-0266.61e+0002.25e+0012.09e+0002.79e-0017.91e-0298.80e-002f2Std7.27e-0019.71e-0151.70e-0161.09e-0254.02e-0011.27e+0007.69e-0011.02e+0001.77e-0297.98e-002Rank64329108715Mean1.04e-0902.19e-0471.42e-0512.50e-0923.51e-0181.38e+0006.12e-0134.25e-0143.95e-2351.16e+001f3Std5.01e-0906.82e-0474.28e-0511.02e-0917.88e-0181.00e+0006.06e-0132.32e-01304.57e+000Rank35426108719Mean0008.23e-3204.54e-1855.03e-06508.64e-2809.48e-0067.75e-006f4Std000002.38e-064001.27e-0058.50e-006Rank11157816109Mean001.38e-0021.14e-0014.84e-0021.38e-00203.50e-0039.28e-0325.68e-016f5Std003.58e-0022.80e-0018.04e-0024.50e-00201.89e-0026.57e-0338.19e-017Rank11710981645Aver. Rank242.43.849.58.84.86.23.47.6Final Rank11451096738The median convergence results of 30D unimodal continuous functions. (a) Sphere function. (b) Rosenbrock’s function. (c) Quadric function. (d) Sum of different powers. (e) Sin function.
(a)(b)(c)(d)(e)From Table3 and Figure 9, the four PS2O variants converged much faster to significantly better results than all other algorithms. The PS2O-RS, which has the heterogeneous hierarchical structures, is the fastest one for finding good results within relatively few generations. All PS2O variants were able to consistently find the minimum to functions f1, f4, and f5 within 10000 generations.From the comparisons between PS2O and other algorithms, we can see that, statistically, PS2O has significantly better performance on continuous unimodal functions f1–f5. From the rank values presented in Table 2, the search performance of the algorithms tested here is ordered as PS2O-S > PS2O-R > CMA-ES > PS2O-SR> PS2O-RS> UPSO > FDR-PSO > ABC > FIPS > PSO.


## 4.3. Continuous Multimodal Functions

The first four multimodal functionsf6–f9 are regarded as the most difficult functions to optimize since the number of local minima increases exponentially as the function dimension increases. According to the results reported in [22], the methods CL-PSO, PSO, CMA-ES, G3-PCX, DE, and the algorithms used for comparison all failed to find the minimum of the six composition function designed by Liang. Since these mentioned methods have demonstrated their excellent performance on standard benchmark functions, the six composition functions are very complex. In this paper, we only test PS2O on the first composition function f10 and the test on the other five composition functions will be studied in the future works. The mean and standard deviations of the function values found in 30 runs for each algorithm on each function are listed in Table 4. Figure 10 shows the search progress of the average values found by the ten algorithms over 30 runs for functions f6–f10.Table 4
Performance of all algorithms on benchmark functionsf6–f10. In bold are the best results.
Func.PS2O-SPS2O-RPS2O-SRPS2O-RSPSOFIPSUPSOFDR-PSOCMA-ESABCMean7.11e-0154.74e-0154.97e-0158.32e-0026.16e-0152.04e-0143.55e-0152.74e-0141.96e+0014.79e-014f6Std01.70e-0151.77e-0153.17e-0021.80e-0151.08e-0143.16e-0151.03e-0144.30e-0016.09e-015Rank13495627108Mean4.47e+0013.25e+0013.61e+0014.61e+0012.78e+0014.13e+0014.96e+0012.60e+0017.56e+0001.64e-013f7Std1.20e+0018.41e+0008.96e+0001.11e+0015.46e+0002.34e+0019.80e+0008.32e+0002.15e+0006.25e-014Rank95684710321Mean8.37e-003009.26e-0031.83e-0021.56e-0033.47e-0031.79e-00201.03e-015f8Std1.09e-002001.07e-0022.66e-0023.78e-0034.78e-0031.82e-00201.17e-015Rank71181056914Mean1.17e+000001.22e+0001.35e+0002.01e-0024.42e+0001.58e-0012.15e+0000f9Std7.68e-001008.64e-0011.16e+0005.58e-0022.60e+0004.56e-0012.98e+0000Rank61178410591Mean0004.00e+0015.00e+0013.37e+0018.00e+0011.00e+0021.30e+0023.83e-002f10Std0008.94e+0001.82e+0022.58e+0014.42e+0014.42e+0011.63e+0021.21e-001Rank11167589104Aver. Rank4.82.22.67.66.85.47.26.66.43.6Final Rank41210859763The median convergence results of 30D multimodal continuous functions. (a) Ackley’s function. (b) Rastrigin’s function. (c) Griewank’s function. (d) Weierstrass function. (e) Composition function 1.
(a)(b)(c)(d)(e)From Table4 and Figure 10, it is clear to see that for most of the tested continuous benchmark functions, all PS2O algorithms except PS2O-RS markedly outperformed the other algorithms. For example, PS2O-R and PS2O-SR found the global minimum every time of run on function f8–f10, and PS2O-R can also consistently found the minimum of f10 within relatively fewer generations, while the other algorithms generated poorer results on them. On functions f6 and f7, the four PS2O algorithms yielded similar results to the other four algorithms. From the rank values presented in Table 4, the search performance of the algorithms tested here is ordered as PS2O-R > PS2O-SR> ABC > PS2O-S > FIPS CMA-ES > FDR-PSO > PSO > UPSO > PS2O-RS.It should be mentioned that PS2O were the only ones able to consistently find the minimum to the composition function f1 that reported in the literatures so far.


## 4.4. Discrete Functions

In binary optimization, it is very easy to design some algorithms that are extremely good on some benchmarks (and extremely bad on some others) [46]. In order to fully evaluate the performance of PS2O on discrete problems, we have employed a carefully chosen set of discrete benchmark functions f11–f17. The results obtained by the GA, PSO, and four PS2O algorithms on each discrete benchmark function are listed in Table 5, including the mean number of iterations required to reach the minimum, mean, and standard deviations of the function values found in 30 runs. Figure 11 shows the search progress of the average values found by the five algorithms over 30 runs for functions f11–f17.Table 5
Performance of all algorithms on benchmark functionsf11–f17. In bold are the best results.
Func.PS2O-SPS2O-RPS2O-SRPS2O-RSPSOGAf11Mean001.67e-00202.14e+0001.26e-001Std005.31e-00202.60e-0011.41e-001Iter.142433528∞∞Rank124365f12Mean003.33e-00203.19e+0002.64e-001Std001.18e-00103.81e-0011.06e-001Iter.31069493328∞∞Rank214365f13Mean00003.96e+0000Std00001.33e+0000Iter.13482426275∞335Rank215364f14Mean4.00e-00306.70e-00302.94e-0012.38e-001Std1.98e-00202.54e-00201.33e-0028.05e-002Iter.871367538398∞∞Rank413265f15Mean000001.36e-001Std000001.30e-001Iter.1789147107356∞Rank124356f16Mean00002.00e-0031.80e-001Std00001.41e-0022.44e-001Iter.203272187151∞∞Rank342156Mean000007.44e-002f17Std000001.83e-002Iter.3951395561∞Rank131456Aver. Rank223.292.715.575.14Final Rank114365The median results of discrete functions. (a) Goldberg’s order-3. (b) Bipolar order-6. (c) Mulenbein’s order-5. (d) Clerc’s Zebra-3. The median convergence results of discrete functions. (e) Clerc’s order-3 problem 1. (f) Clerc’s order-3 problem 2. (g) Discrete multimodal problem.
(a)(b)(c)(d)(e)(f)(g)From the results, we can observe that PS2O obtain an obviously remarkable performance. It can be seen from Figure 11 that all PS2O variants converged greatly faster and to significantly better results than the other two algorithms for all discrete cases. From the rank values presented in Table 5, the search performance of the algorithms tested here is ordered as PS2O-R > PS2O-S > PS2O-RS> PS2O-SR> GA > PSO. It is worth mentioning that the PS2O-R and PS2O-RS were able to consistently find the minimum to all discrete benchmark functions.


## 5. Conclusion

This paper first describes the hierarchical swarm intelligence phenomenon: the emergence of high-level intelligence aggregates properties from low-level. This mechanism is so common in nature, and provides initial evidence of the potential problem solving capabilities. Furthermore, this paper presents the hierarchical swarm optimization (HSO) model that simulates the hierarchical swarm intelligence for function optimization. HSO is an artificial hierarchical complex system, in which agents are composed of swarms of other agents in nested hierarchies. That is, HSO is configured into several levels and each level is composed of a number of independent swarms. Note that any traditional SI methods or evolutionary algorithms can be used to manipulate any swarm of any level in HSO. HSO can be considered as not only an extension of the traditional SI model to design novel optimization algorithms, but also an open framework to hybrid traditional SI or EA algorithms to tackle hard optimization problems.HSO model has a considerable potential in optimization domain. This paper provides some initial insights into this potential by designing a two-level HSO algorithm, namely PS2O, which employs PSO method in each swarm of each level. This algorithm is conceptually simple, has low complexity, and is easy to implement. A set of 17 benchmark functions (including continuous and discrete cases) have been used to test four PS2O variants in comparison with GA, CMA-ES, ABC, canonical PSO, FIPS, UPSO, and FDR-PSO. The simulation results show that, for all the test functions, the PS2Os reach remarkably better performance in terms of accuracy, convergence rate, and robustness than the other classical powerful algorithms.It should be mentioned that the PS2Os were the only ones that are able to consistently find the minimum of Sphere, Sum of different powers, Griewank, Weierstrass, Composition function 1 and all discrete test problems. Future research will address designing more robust and efficient HSO algorithms by integrating other SI algorithms to HSO and applying them to solve complex optimization problems. We should note that the two-level HSO algorithm is conceptually simple and easy to implement. However, in our future work, HSO algorithms with more hierarchical levels could be studied and tested on some complex benchmark functions and real-world problems.



---

*Source: 379649-2010-05-18.xml*