Small Worlds and Mega

Small Worlds and Mega-Minds: Effects of Neighborhood Topology

on Particle Swarm Performance

James Kennedy

Bureau of Labor Statistics,

USA

Kennedy-Jim@

Abstract This study manipulated the neighborhood

topologies of particle swarms optimizing four test

functions. Several social network structures were

tested, with “small-world” randomization of a speci-

fied number of links. Sociometric structure and the

small-world manipulation interacted with function

to produce a significant effect on performance.

1

Introduction

The particle swarm algorithm is a method for opti-

mizing hard numerical functions bad on a metaphor

of human social interaction (Eberhart, Simpson, and

Dobbins, 1996; Kennedy, 1997). Individuals repre-

nted as multidimensional points interact with one

another and converge on optimal regions the prob-

of

lem space. While originally developed as a simulation

of social behavior, the algorithm has become accepted

as a computational intelligence technique related to

evolutionary algorithms (Angeline, 1998; Eberhart,

Simpson, and Dobbins, 1996).

Human interpersonal interaction, which has been

theorized to contribute to cognitive process (e.g.,

Brothers, 1997; Levine, Resnick, and Higgins, 1993),

occurs

in

the context of a social structure, often de-

picted by social scientists as a network of connections

between pairs of individuals. Rearch since the late

1940’s (e.g., Bavelas, 1950) has shown that communi-

cation within a group, and ultimately the group’s per-

formance, is affected by the structure of the social net-

work. Particle rearch has examined veral

swarm

simple social structures, in particular the interaction of

individuals with their immediate adjacent neighbors

and fully connected interaction of all individuals in the

population, but has not riously examined effects of

various “social structures” on optimization.

2

Small Worlds, Mega-Minds

In the 1960’s, Milgram (1967) conducted an ex-

periment to learn how interconnected people in the

United States are. Individuals picked at random from

the populations of Midwestern cities were given a

two

folder containing the name of someone in Cambridge,

Massachutts. The individuals were told to nd the

folder to someone they knew, who they thought might

be likely to know the person Cambridge; the person

in

who received the folder then was to do the same, nd

it to someone they knew, and on. The question was,

so

how many links are required to connect two people

lected at random? The surprising answer was that a

median of only five connections were required to get

the folder from a random person in Nebraska to a target

in Massachutts.

Granovetter (1973) theorized that “weak ties” are

important in determining the optimality of social

structures. According to his much-cited paper, infor-

mation traveling through distant acquaintances is very

important, largely becau it provides information that

a clique or ingroup might not posss. Strong ties or

connections between pairs of individuals are likely to

be found within cohesive groups, where interaction is

frequent and norms are established and accepted, while

weak ties form bridges between strongly-connected

clusters. The weak ties then create paths between indi-

viduals who are not directly linked, allowing the spread

of innovation through a population.

Recently, Watts and Strogetz (1998) examined the

effects of changing a small number of randomly-

chon edges in a regular ring lattice. They demon-

strated that changing fewer than

1

percent of edges in a

network where every individual is connected to its

K

nearest neighbors (the “lbest” topology ud in many

particle swarm studies) resulted in a structure that fea-

tured high clustering, as found in a regular lattice, but

with a greatly reduced average distance between nodes.

Clustering is defined by the average number of neigh-

bors that any two connected nodes have in common. In

a ring lattice, clustering is high, but the average dis-

tance between nodes is also high. Randomizing a

small proportion of connections maintains a high level

of

envi orderly network should propitiate the spread of

information throughout a population. For a particle

swarm population, a manipulation affecting the topo-

logical distance between individuals might affect the

rate and degree to which population members are at-

tracted toward a particular solution.

In support of this hypothesis, Hutchins

(1995)

simulated a group of individuals reprented as parallel

constraint satisfaction networks. Selected nodes of

each network were connected to the corresponding

nodes of neighboring networks, and the were allowed

to influence one another through the connections. The

networks were optimized through the usual technique

of asynchronous updating (Hopfield,

1984),

allowing

however for inputs from other nets. Hutchins found

that the groups of networks converged on optima when

there were a moderate number of connections among

them, but converged on poor solutions when the cogni-

tive structures were highly connected. He concluded

that such mega-minds were especially susceptible to where

confirmation bias, which is a tendency to ek confir-

mation for hypothes rather than using the proper

logical method of falsifying. Networks that were

highly connected in a “mass mental telepathy” (p.

252)

quickly succumbed to the attraction of very poor local

optima. Thus there appeared to be an optimal level of

connectivity among individuals for optimizing the net-

works.

Latane’s social impact theory (Latank,

1981;

Nowak, Szamrej, and Latad, asrts that the

1990)

probability that someone will adopt an attitude or belief

is a function of the Strength, Immediacy, and Number

of others who endor the attitude (immediacy is the

reciprocal of distance, while strength is a social attrib-

ute like status or persuasiveness). Social impact theory

though is prented in terms of univariate social influ-

ence, that is, attitudes and beliefs are considered one at

a time, independent of one another. Most interesting

particle swarm problems are multivariate, for instance,

optimizing the pattern of weights in a neural network,

as it has long been presumed that cognitive variables

should be optimized in relation to one another, i.e.,

cognitions should be consistent with one another

(Abelson et

al.,

1968).

The individual will arch the

nodes connected to it in the social network

-

its neigh-

to determine which single member of the borhood

-

neighborhood has achieved the best performance

so

far. Thus the sociometric topology of the particle

swarm population determines the breadth of influences

on the individual, and how many neighbors the indi-

how small vidual has in common with its neighbors

-

its world is.

In sum, we have reason to hypothesize that highly

connected particle swarm societies might not be as

good at finding optima in a problem space, compared

to moderately connected social networks. It has been

shown (e.g., Kennedy, that isolated particle

1997)

swarm individuals perform very poorly: the interac-

tions between particles make the algorithm

work.

What might be the best social structure for particles?

The prent study begins to investigate this question.

3 Particle

The Swarm

The particle swarm algorithm is bad on the meta-

phor of individuals refining their knowledge by inter-

acting with one another. particle is a moving point

A

in a hyperspace. Besides its position and velocity

Zi

?;,

each particle stores the best position in the arch

space it has found thus far in a vector

jji

.

The velocity

of

the particle is adjusted stochastically toward its pre-

vious best position, and the best position found by any

member of its neighborhood:

V’i 91

+ +

V’i

(jj;

-

ii)

+

v)Z

(jjg

-

?i)

pI

and are random numbers defined by

vZ

their upper limit (usually The index g is the index

2.0).

of

the particle in the neighborhood with the best per-

formance far, that is the best vector found by

so

so

pg

any member of the neighborhood.

Once has been calculated, the particle’s position

Gi

Zi

is adjusted:

2; ii

f-

+

The algorithm is often compared to the family of

evolutionary algorithms, as a stochastic population-

bad arch of a problem space. Particle swarm dif-

fers

from an

evolutionary methods in important way,

however: it does not implement lection of the fittest.

Instead, individuals persist over time, and adapt by

changing.

Particles have historically been studied in two gen-

eral types overlapping neighborhoods, called gbest

of

and lbest (Eberhart, Simpson, and Dobbins,

1996).

In

the gbest neighborhood every individual is attracted to

the best solution found by any member of the entire

population. This structure then is equivalent to a fully

connected social network; every individual is able to

compare the performances of every other member

of

the population, imitating the very best. the lbest

In

network each individual affected by the best per-

is

formance of its

K immediate neighbors in the topologi-

cal population a regular ring lattice. In the usual

-

ca,

K=2, the individual affected by only its imme-

is

diately adjacent neighbors.

The choice of social structures ud has been thus

far a matter of individual artistry, with some lore and

little data to help the rearcher choo a strategy. The

lore suggests that

gbest populations tend to converge

more rapidly than

lbest populations, when they con-

verge, but are also more susceptible to convergence on

local optima.

vi

1932

Authorized licend u limited to: SUN YAT-SEN UNIVERSITY. Downloaded on January 19, 2010 at 22:42 from IEEE Xplore. Restrictions apply.

4

Neighborhood Types

In the trials reported below, populations of indi-

20

viduals were configured into the configurations,

:

shown in Figure

1

0

Circles (hest): each individual is connected to

its immediate neighbors only

K

0

Wheels: one individual is connected to all oth-

ers, and they are connected to only that one

Stars (gbest): every individual is connected to

every other individual, and

Random edges: for particles, random

N N

symmetrical connections are assigned between

pairs of individuals.

In the Circle topology, which is a regular ring lat-

tice as studied by Watts and Strogetz (1998), parts of

the population that are distant from one another are

also independent of one another. Thus one gment of

the population might converge on a local optimum,

while another gment converges on a different opti-

mum or keeps arching. Influence spreads from

neighbor to neighbor in this topology, until, if an opti-

mum really is the best found by any part of the popula-

tion, it will eventually pull all the particles in. Small-

world reassignments of connections have the effect of

shortening the distances between neighborhoods, and

one would expect the population to converge faster

-

perhaps too fast when the shortcuts are implemented.

-

The Wheel topology effectively isolates individuals

from one another, as all information has to be commu-

nicated through the focal individual. This focal indi-

vidual compares performances of all individuals in the

neighborhood, and adjusts its trajectory toward the

very best. If adjustments result in improvement in the

focal individual’s performance, then that improvement

is communicated out to the rest of the population.

Thus the focal individual rves as a kind of buffer or

filter, slowing the speed

of

transmission of good

solu-

tions through the population. (It should be noted that

the Wheel is a common configuration for many busi-

ness and government organizations.)

Small-world shortcuts in the Wheel may have two

effects. One is to create mini-neighborhoods, where

peripheral individuals are influenced by individuals

who are in direct contact with the focal or hub individ-

ual. Thus incread communication can result from

implementing shortcuts, and we might again expect

faster convergence the collaborating subpopulation.

in

The buffering effect of the focal particle though should

prevent overly rapid convergence on local optima. It is

also possible to create islands, or disconnected groups Two kinds of control groups were run.

of individuals, which may collaborate among them-

lves to optimize the function. This would introduce a

diminishing

of

communication, as the isolated indi-

viduals would not have access to information about the

best region found by the population; nor would the rest

of the population benefit from their success.

The Star or Gbest topology links every individual

with every other, that the social source influence

so

of

is in fact the best-performing member of the popula-

tion. Finally, the Random topology simply assigns

connections at random between pairs of particles.

Populations were tested on a t of well-studied test

functions covering a range of problem types. Circles

were defined with and Circles and Wheels were

K=2,

studied with veral degrees of small-world shortcuts;

shortcuts are meaningless in either Random

or

fully

connected Star networks.

The trials implemented a modified particle swarm

version using a constriction coefficient propod by

Maurice Clerc (Clerc and Kennedy, 1999, under re-

view). This version is simple to implement and has the

advantage that the population converges without re-

limit to velocities. constant coeffi- quiring a

A

cient is calculated using the upper limit of

p p,

=

+

p2

:

v,

x=l--+ 1

9

JFG

2

The particle swarm formula is then modified:

V’i ~l(jj

+ +

x(V’j

- -

ii)+

~z(Ijg

gill

This modification, ud with values of has

p

>

4.0

,

been shown to result in excellent optimization of test

functions. Since it has desirable convergence proper-

ties and removes the necessity of imposing the arbi-

trary velocity limit, it was ud in the prent imple-

mentations.

5

Method

The particle swarm program was modified to allow

control over sociometry. Standard test functions were

taken from the literature evolutionary computation,

of

including De Jong’s fl sphere function, Griewank,

Rastrigin, and Ronbrock functions.

All

functions

were implemented in 30 dimensions. Each function

was run with wheel and circle sociometries, with 1,

0,

2, 3,4, and random small-world shortcuts. Thus the

5

experiment had three independent variables: function

(4

levels: Func), basic neighborhood topology (2 lev-

els: Ntype), and shortcuts levels: Nmoved). The de-

(6

pendent variable ud was population-best performance

on the test function after 1,000 iterations. Each

FuncxNtypexNmoved condition of the experiment was

run twenty times.

A randomly

connected group was run for each function, as was a

gbest or fully-connected topology. Becau the

groups were not orthogonal to the experimental design,

they were analyzed parately.

1933

Authorized licend u limited to: SUN YAT-SEN UNIVERSITY. Downloaded on January 19, 2010 at 22:42 from IEEE Xplore. Restrictions apply.

All trials ud populations of 20 individuals, with

(p=4.1. Functions tested are shown in Table 2.

Data were analyzed using analysis of variance

(ANOVA). The output of ANOVA is the statistic.

F

F

is

the between-group variance (the average difference

between cell means) divided by the within-group vari-

ance, which is taken to be an estimate of error.

A

“p-

value” indicates the probability of deciding that the

null hypothesis of no difference is fal when it is actu-

ally true. Traditionally a p-value less than

0.05

is con-

sidered significant.

6 Results

Becau the various functions were scaled differ-

ently, resulting

in

incomparable means and variances,

within-function data were standardized to a scale with

mean=O and standard deviation=

1,

and factorial

ANOVA was conducted on the transformed data. As

mentioned above, in order to prerve the orthogonality

of the experimental design, Random and Gbest condi-

tions were dropped from the analysis. main effect

No

is reported for Function since scores were standardized

to that domain, thus all means are 0.0. Analytic results

are shown in Table means and standard deviations

1;

are in Appendix 1.

As can be en, there was no significant main effect

for Neighborhood Type, though it interacted signifi-

cantly with Function and with Number Moved.

The interaction of Neighborhood Type with Func-

tion was very strong, as it was en that populations

performed better on three of the functions when they

were in the Circle configuration, regardless of the

number

of edges moved, than in the Wheel configura-

tion. Performance on the Rastrigin function, however,

was just the opposite; Rastrigin populations performed

better in the Wheel topology.

Table Analysis of variance of factors interac-

1.

3

with

tions. NType=Neighborhood Type, Func=Function,

Nmoved=Number of Edges Moved.

Source

FuncxNtype

Nmoved 0.0780

FuncxNmoved 15 0.43 0.9694

NtypexNmoved 2.78 0.0168

FuncxNtypexNmoved 0.9724

unusually high where Number Moved=4 and topol-

ogy=Wheel, indicating inconsistent performance. In

the Wheel topology, as mentioned above, shortcuts can

result in alliances and formation of collaborating

sub-

populations, or in isolated islands, cut off from the

group’s progress.

This

same effect ems to account for the nearly-

significant main effect of Number Moved, p<0.0780.

The mean performance for Number Moved4 was

wor than that for other values.

A cond analysis was performed in order to de-

termine how the Gbest (Star: fully connected topology)

and Random (Randomly connected topology) condi-

tions compared to the rest. Scores were standardized

per function as before, but including Gbest and Ran-

dom conditions along with the orthogonal ones. T-tests

were conducted, comparing the orthogonal data with

Gbest only, and then comparing the orthogonal data

with Random only. Interestingly, both Gbest and Ran-

dom performed better than the other conditions com-

bined, p<0.05. Inspection of means showed that Gbest

topology was better than the combined mean on every

hnction, while the Random topology outperformed

others on all functions except Rastrigin.

7

Discussion

Watts and Strogetz’ mathematical model showed

the effects of randomizing a very small proportion of

connections. In the prent particle swarm implemen-

tations with populations of 20 individuals it was im-

possible to move

1%

or fewer of the links; smaller

population sizes however are usually appropriate with

the particle swarm method. Therefore this may not be

considered a valid test

of

the small-world hypothesis,

but rather simply an investigation into the effect. On

the other hand, the findings do show that the

so-

ciometry of the particle swarm has a significant effect

on its ability to find optima: the optimal pattern of con-

nectivity among individuals depends on the problem

being solved.

This study did not systematically manipulate as-

pects of test functions, but there are grounds for

speculation

as

to an explanation for the interaction. As

en in Appendix 2, the Sphere and Ronbrock func-

tions are unimodal, with smooth surfaces. The

Griewank function depicted in two dimensions looks

like a bumpy bowl that slopes gradually toward the

global optimum textured with many slight local op-

tima. The Rastrigin function though features many

different ,functions Wheels performed better than Angeline, P. J. Evolutionary optimization ver-

-

might be that the buffering Circles on Rastrigin only

-

effect of communicating through a “hub” slows the

population’s attraction toward the population best, pre-

venting premature convergence on local optima. Thus

a hypothesis can be propod for later rearch: cen-

tralized Wheel topologies may perform better on of America,

strongly multimodal landscapes.

Some effects may be due to the convergence en-

forced by the constriction coefficient. Interestingly,

one study with the Vmnx-type particle swarm reported Clerc, M., and Kennedy,

much poorer results on three of the functions

-

but Particle Swarm: Explosion, Stability, and Conver-

the “standard” particle swarm performed better on the gence in a Multi-Dimensional Complex Space.

Rastrigin function (Angeline,

1998). (1996).

This may suggest Eberhart, R. C., Simpson, P., and Dobbins, R.

that constriction is disadvantageous on problems with Computational Intelligence PC Boston:

many good local optima. On the other hand, that study

implemented slightly different forms of the func-

tions, including initialization ranges, and informal

testing with the current programs found that the con-

stricted version performed much better than the stan- Hopfield, J. J. Neurons with graded respon

dard form on all functions. have collective computational properties like tho

The cond finding, that changing four links on of two-state neurons. Proceedings of the National

Wheel structures except on the Rastrigin function Academy of Sciences,

- -

greatly impairs performance, is going to be harder to Hutchins, E. Cognition in the Wild. Cam-

explain. When three links are randomized, or five bridge,

links, performance is not especially affected, but four Kennedy, The particle swarm: Social adap-

shortcuts result degraded ability to optimize the tation of knowledge. Proceedings of the

in

test functions. In the Wheel topology, where all indi- ternational Conference Evolutionary Computa-

viduals are connected to one focal individual, shortcuts tion (Indianapolis, Indiana), IEEE Service

can be en to create subpopulations with individuals

that are relatively isolated from the focus. The fmding Latant, The psychology of social impact.

that Random connections performed relatively well American Psychologist,

-

less on Rastrigin makes this effect even harder to Levine, J. M., Resnick, L. B., and Higgins, E. T.

so

-

understand.

In sum, it has been shown that neighborhood topol- Review of Psychology,

ogy significantly affects the performance of a particle Milgram, The small world problem. Psy-

swarm, and that the effect is dependent on the function. chology Today,

Bibliography

Abelson, R.P, E. Aronson, McGuire, T.M. New-

W.J.

comb, M.J. Ronberg, P.H. Tannenbaum (Eds.)

&

(1 968).

Theories of Cognitive Consistency:

A

Sourcebook. Chicago: Rand-McNally.

Table Functions tested particle swarm

2.

in

trials.

Sphere

f

1

(XI x:

=

CL1

(1998).

sus particle swarm optimization: Philosophy and

performance differences.

Evolutionary Program-

ming

VIZ,

601-610.

Berlin: Springer.

Bavelas, A. Communication patterns in task-

(1 950).

oriented groups. Journal of the Acoustical Sociey

22,

727-730.

Brothers, L. Friday’s Footprints: How Society

(1997).

Shapes the Human Mind.

Oxford: Oxford Univer-

sity Press.

J. under review). The

(1999,

Tools.

Academic Press.

Granovetter, M. “The Strength of Weak

S. (1973).

Ties.” American Journal Sociology,

of

78:

1360-

1380.

(1984).

81,

3088-3092.

(1995).

MA:

MJT Press.

J.

(1997).

1997

In-

on

303-308.

Center, Piscataway,

NJ.

B.

(1981).

36,3 43 6.

-3

5

(1993).

Social foundations of cognition. Annual

44,

585-612.

S.

(1967).

22,6 1-67.

Nowak, A., Szamrej, and Latant, From

J.,

B.

(1990).

private attitude to public opinion: A dynamic theory

of social impact. Psychological Review,

97,

362-

376.

Watts and Strogetz Collective dynamics of

(1998).

‘small-world’ networks. Nature,

393,440-442.

I

1935

Authorized licend u limited to: SUN YAT-SEN UNIVERSITY. Downloaded on January 19, 2010 at 22:42 from IEEE Xplore. Restrictions apply.

Figure

1.

Sociometric topologies ofpopulations of size Top left is circle, top right is the

12. K=2,

same neighborhood with “small-world” shortcuts. the lower left is a “wheel” configuration,

two

On

and lower right is the wheel with small-world changes.

two

1936

Authorized licend u limited to: SUN YAT-SEN UNIVERSITY. Downloaded on January 19, 2010 at 22:42 from IEEE Xplore. Restrictions apply.

Appendix. I. Cell means condition.

by

Star

I I

91.6434190 46.7294972

1937

Authorized licend u limited to: SUN YAT-SEN UNIVERSITY. Downloaded on January 19, 2010 at 22:42 from IEEE Xplore. Restrictions apply.

Appendix Functions tested. sphere function. Top right: Griewank. Bottom left: Ronbrock. Bottom

2.

Top

Iej:

right: Rastrigin. All functions are plotted for their full range as reported in the text.

1938

Authorized licend u limited to: SUN YAT-SEN UNIVERSITY. Downloaded on January 19, 2010 at 22:42 from IEEE Xplore. Restrictions apply.