Swarm Intelligence (PDF)

chapter seven The Particle Swarm This chapter introduces the particle swarm rules of the algorithm, which say nothing in its binary and real-numbered forms. The about the existence of a problem or how to book so far has b...

chapter seven The Particle Swarm This chapter introduces the particle swarm rules of the algorithm, which say nothing in its binary and real-numbered forms. The about the existence of a problem or how to book so far has been preparing a context, de- solve it. Yet through reciprocal social influ- scribing related paradigms in computer sci- ence each individual betters its “fitness” (the ence and social science, discussing culture term is less appropriate here than in discus- and norms and language and other scien- sion of evolutionary algorithms), and the per- tific and philosophical developments that, if formance of the population improves. We we have been successful, will make the parti- would not say that the adaptive culture algo- cle swarm seem like an obvious thing to rithm is an especially powerful way to solve propose. problems, but it is a good introduction to The Adaptive Culture Model in the previ- some social algorithms that are. ous chapter hints at what can happen as a re- The particle swarm algorithm is intro- sult of the simplest imaginable interactions duced here in terms of social and cogni- of the simplest imaginable agents—if these tive behavior, though it is widely used as a can even be called “agents.” Given a large problem-solving method in engineering and space of possibilities, the population is often computer science. We have discussed binary able to find multivariate solutions, patterns encoding of problems, and the first version that solve problems, through a stripped- of the particle swarm we present here is de- down form of social interaction. signed to work in a binary search space. Later It is worth emphasizing that individuals in in the chapter we introduce the more com- the culture model are not trying to solve monly used version, which operates in a problems. They are only following the simple space of real numbers. 287 Team LRN 288 Chapter Seven—The Particle Swarm Sociocognitive Underpinnings: Evaluate, Compare, and Imitate A very simple sociocognitive theory underlies the Adaptive Culture Model and particle swarms. We theorize that the process of cultural adaptation comprises a high-level component, seen in the formation of patterns across individuals and the ability to solve problems, and a low-level com- ponent, the actual and probably universal behaviors of individuals, which can be summarized in terms of three principles (Kennedy, 1998): Evaluate Compare Imitate Evaluate The tendency to evaluate stimuli—to rate them as positive or negative, attractive or repulsive—is perhaps the most ubiquitous behavioral char- acteristic of living organisms. Even the bacterium becomes agitated, run- ning and tumbling, when the environment is noxious. Learning cannot occur unless the organism can evaluate, can distinguish features of the environment that attract and features that repel, can tell good from bad. From this point of view, learning could even be defined as a change that enables the organism to improve the average evaluation of its environment. Compare Festinger’s social comparison theory (1954) described some of the ways that people use others as a standard for measuring themselves, and how the comparisons to others may serve as a kind of motivation to learn and change. Festinger’s theory in its original form was not stated in a way that was easily tested or falsified, and a few of the predictions generated by the theory have not been confirmed, but in general it has served as a backbone for subsequent social-psychological theories. In almost every- thing we think and do, we judge ourselves through comparison with others, whether in evaluating our looks, wealth, humor, intelligence (note that IQ scales are normed to a population average; in other words, Team LRN  A Model of Binary Decision 289 your score tells you how you compare to others—which is really the point, isn’t it?), or other aspects of opinion and ability. Individuals in the Adaptive Culture Model—and in particle swarms—compare themselves with their neighbors on the critical measure and imitate only those neighbors who are superior to themselves. The standards for social be- haviors are set by comparison to others. Imitate You would think that imitation would be everywhere in nature; it is such an effective way to learn to do things. Yet, as Lorenz has pointed out, very few animals are capable of real imitation; in fact, he asserts that only humans and some birds are capable of it. Some slight variations of social learning are found among other species, but none compare to our ability to mimic one another. While “monkey see, monkey do,” well describes the imitative behavior of our cousins, human imitation comprises taking the perspective of the other person, not only imitating a behavior but re- alizing its purpose, executing the behavior when it is appropriate. In The Cultural Origins of Human Cognition, Michael Tomasello argues that social learning of several kinds occurs in chimpanzees, but true imitation learn- ing, if it occurs at all, is rare. For instance, an individual’s use of an object as a tool may call another individual’s attention to the object; this sec- ond individual may use the same object, but in a different way. True imi- tation is central to human sociality, and it is central to the acquisition and maintenance of mental abilities. The three principles of evaluating, comparing, and imitating may be combined, even in simplified social beings in computer programs, en- abling them to adapt to complex environmental challenges, solving ex- tremely hard problems. Our view diverges from the cognitive viewpoint in that nothing besides evaluation, comparison, and imitation takes place within the individual; mind is not found in covert, private cham- bers hidden away inside the individual, but exists out in the open; it is a public phenomenon. A Model of Binary Decision Consider a bare-bones individual, a simple being with only one thing on its mind, one set of decisions to make, yes/no or true/false, binary deci- sions, but very subtle decisions, where it is hard to decide which choices Team LRN 290 Chapter Seven—The Particle Swarm to make. For each decision, this supersimplified individual can be in one state or the other, either in the yes state, which we will represent with a 1, or the no = 0 state. It is surrounded by other yes/no individuals, who are also trying to decide. Should I say yes? Should I say no? They all want to make the best choices. Two important kinds of information are available to these primitive beings. The first is their own experience; that is, they have tried the choices and know which state has been better so far, and they know how good it was. But these social beings have a second consideration; they have knowledge of how the other individuals around them have per- formed. In fact they are so simple that all they know is which choices their neighbors have found most positive so far and how positive the best pattern of choices was. If these stripped-down beings are anything like people, they know how their neighbors have done by observing them and by talking with them about their experiences. These two types of information correspond to Boyd and Richerson’s individual learning and cultural transmission. The probability that the individual will choose “yes” for any of the decisions is a function of how successful the “yes” choice has been for them in the past relative to “no.” The decision is also affected by social influence, though the exact rule in humans is admittedly not so clear. Social impact theory states that the individual’s binary decisions will tend to agree with the opinion held by the majority of others, weighted by strength and proximity. But even that rule is somewhat vague, given ambiguities in the concepts of strength and proximity. For the present introductory model we will just say that individuals tend to be influenced by the best success of anyone they are connected to, the member of their sociometric neighborhood that has had the most success so far. While we admit this is an oversimplification, it has a kernel of truth that justifies the parsimony it brings to the model. Individuals can be connected to one another according to a great number of schemes, some of which will be mentioned in Chapter 8. Most particle swarm implementations use one of two simple sociometric prin- ciples (see Figure 7.1). The first, called gbest, conceptually connects all members of the population to one another. The effect of this is that each particle is influenced by the very best performance of any member of the entire population. The second, called lbest (g and l stand for “global” and “local”), creates a neighborhood for each individual comprising itself and its k nearest neighbors in the population. For instance, if k = 2, then each individual i will be influenced by the best performance among a group made up of particles i − 1, i, and i + 1. Different neighborhood to- pologies may result in somewhat different kinds of effects. Unless stated Team LRN  A Model of Binary Decision 291 The “lbest” neighborhood with k = 2. Each individual's neighborhood contains itself and its two adjacent neighbors. The first and last are connected. 1 2 3 4 5 6 7 8 Individual #3 has found the best position so far in #4's neighborhood. Therefore, #4's velocity will be adjusted toward #3's previous best position and #4's own previous best position. 1 2 3 4 5 6 7 8 0.72 0.33 0.54 Best fitness so far The “gbest” neighborhood. Assuming that #3 has found the best fitness so far in the entire population, all others' velocities will be attracted toward its previous best position. Figure 7.1 The two most common types of neighborhoods. Team LRN 292 Chapter Seven—The Particle Swarm otherwise, the following discussions will presume lbest neighborhoods with k = 2 (sometimes described as “neighborhood = 3”). In a sociocognitive instance the individual must arrange an array of decisions or judgments in such a way that they all fit together, what we call “making sense” or “understanding” things. The individual must be able to evaluate, compare, and imitate a number of binary choices simultaneously. Evaluation of binary strings can be accomplished in one step. In the psychological case, that is, if we are talking about humans, we can again use the concept of cognitive dissonance to evoke the sense of tension that exists when an array of decisions contains inconsistencies. We expe- rience the state as discomfort and are motivated to change something to reduce the tension, to improve the evaluation. Dissonance as described by Festinger provides a single measure of cognitive evaluation, exactly as “fitness” is a single measure of genetic or phenotypic goodness. How do we improve cognitive fitness? Of course there are plenty of theories about this. In Ajzen and Fishbein’s Reasoned Action Model, (1980) intent is seen as a function of two kinds of things that should be getting familiar by now (see Figure 7.2). On the one hand, intent is affected by the person’s attitude toward the behavior; for instance, if they believe vi- olence is harmful or immoral, then they may intend not to act violently. This attitude is formed, in Ajzen (pronounced “eye-zen”) and Fishbein’s theory, by a linear combination of beliefs that the behavior will result in some outcomes (bi) times the individual’s evaluation of those out- comes (ei): n Ao = ∑b i e i i=1 This kind of expectancy-value model of attitude has existed in some form for many years, and we will not criticize its linearity or asymptotic issues here (never mind the decades-old debate about summing versus averaging). We are interested in the fact that intent has a second cause, which Ajzen and Fishbein call the subjective norm. The subjective norm regarding a behavior is also built up, in their theory, as a linear sum of products, but this time the factors entering into the formula are social. The individual’s subjective norm toward a behavior is a sum of the prod- ucts of their beliefs that certain others think they should or should not perform the behavior, multiplied by the motivation to comply with each of those others: n SNo = ∑b i mi i=1 Team LRN  A Model of Binary Decision 293 Attitude toward behavior Intention Behavior Subjective norm Figure 7.2 According to the Reasoned Action Model, behavior is a function of intention and only remotely of the individual’s attitude about the behavior. To point out the obvious, these two components of the theory of rea- soned action map easily onto the components of Boyd and Richerson’s cultural transmission model; that is, there is an individual term (individ- ual learning or attitude toward a behavior) and a social term (cultural transmission or subjective norm). These two kinds of concepts are found in other theories as well and are represented in our decision model as the two terms that make up the change formula. We theorize that the coexis- tence of these two modes of knowledge, that is, knowledge acquired by the senses through experience in the world and knowledge acquired from others, gives humans the intellectual advantage; it is the source of our intelligence. Besides their past experience and inputs from the social environ- ment, another factor that affects the individual’s decision is their cur- rent propensity or position regarding the issue. They may start with a strongly negative attitude and have subsequent positive experiences re- garding the choice or attitude object—but still have a negative feeling about it. The positive experiences may make the individual more likely to choose the positive alternative, but in order to shift the individual’s gen- eral propensity into the positive domain, the decision threshold would still have to shift upwards. If the individual’s initial position is extreme, the probability is lower of its changing—for one thing, the individual is less likely to try the other alternative. In mathematical terms, we are proposing a model wherein the proba- bility of an individual’s deciding yes or no, true or false, or making some Team LRN 294 Chapter Seven—The Particle Swarm other binary decision, is a function of personal and social factors (Ken- nedy and Eberhart, 1997): P(xid (t ) = 1) = f (xid (t − 1), v id (t − 1), pid , p gd ) where P(xid(t)=1) is the probability that individual i will choose 1 (of course the probability of their making the zero choice is 1 − P) for the bit at the dth site on the bitstring xid(t) is the current state of the bitstring site d of individual i t means the current time step, and t − 1 is the previous step vid(t − 1)is a measure of the individual’s predisposition or current probability of deciding 1 pid is the best state found so far, for example, it is 1 if the individ- ual’s best success occurred when xid was 1 and 0 if it was 0 pgd is the neighborhood best, again 1 if the best success attained by any member of the neighborhood was when it was in the 1 state and 0 otherwise The decisions themselves will be stochastic, if for no better theoretical reason than that we never know all the forces involved—it is very un- likely that any decision is made based solely on isolated facts pertaining directly to that decision alone. A lot of randomness allows exploration of new possibilities, and a little bit allows exploitation by testing patterns similar to the best one found so far; thus we can balance between those two modes of search by adjusting the uncertainty of decisions. The parameter v id (t ),an individual’s predisposition to make one or the other choice, will determine a probability threshold. If v id (t ) is higher, the individual is more likely to choose 1, and lower values favor the 0 choice. Such a threshold needs to stay in the range [0.0, 1.0]. We have already seen one straightforward function for accomplishing this, when we talked about neural networks. The sigmoid function 1 s(v id ) = 1+ exp(−v id ) squashes its input into the requisite range and has properties that make it agreeable to being used as a probability threshold (though there is noth- ing magical about this particular function). Team LRN  A Model of Binary Decision 295 We wish to adjust the individual’s disposition toward the successes of the individual and the community. To do that we construct a formula for each vid in the current time step that will be some function of the differ- ence between the individual’s current state or position and the best points found so far by itself and by its neighbors. We want to favor the best position, but not so much that the individual ceases searching pre- maturely. If we simply added ( pid − xid(t−1)) and ( pgd − xid(t−1)) to vid (t), it would move upward when the difference between the individual’s pre- vious best and most recent states, or the difference between the neigh- borhood’s best and the individual’s most recent states, equaled 1, and would be attracted downward if either difference equaled −1. The proba- bility threshold moves upward when the bests are ones and downward when they are zeroes. In any situation we do not know whether the individual-learning or the social-influence terms should be stronger; if we weight them both with random numbers, then sometimes the effect of one, and sometimes the other, will be stronger. We use the symbol ϕ (the Greek letter phi) to represent a positive random number drawn from a uniform distribution with a predefined upper limit. In the binary version the limit is some- what arbitrary, and it is often set so that the two ϕ limits sum to 4.0. Thus the formula for binary decision is v id (t ) = v id (t − 1) + ϕ1 ( pid − xid (t − 1)) + ϕ 2 ( p gd − xid (t − 1)) if ρ id < s(v id (t )) then xid (t ) = 1; else xid (t ) = 0 where ρid is a vector of random numbers, drawn from a uniform distribu- tion between 0.0 and 1.0. These formulas are iterated repeatedly over each dimension of each individual, testing every time to see if the cur- rent value of xid results in a better evaluation than pid, which will be up- dated if it does. Boyd and Richerson varied the relative weighting of indi- vidual experience and social transmission according to some theoretical suggestions; the current model acknowledges the differential effects of the two forces without preconceptions about their relative importance. Sometimes decisions are based more on an individual’s personal experi- ence and sometimes on their perception of what other people believe, and either kind of information will dominate sometimes. One more thing: we can limit vid so that s(vid) does not approach too closely to 0.0 or 1.0; this ensures that there is always some chance of a bit flipping (we also don’t want vi moving toward infinity and overloading the exponential function!). A constant parameter Vmax can be set at the Team LRN 296 Chapter Seven—The Particle Swarm start of a trial to limit the range of vid. In practice, Vmax is often set at ±4.0, so that there is always at least a chance of s(Vmax) ≈ 0.0180 that a bit will change state. In this binary model, Vmax functions similarly to mutation rate in genetic algorithms. Individuals make their decision in a population, where they are influ- enced by the successes of their neighbors. As each individual’s decision is affected by (pgd − xid(t − 1)), that is, (usually) some other individual’s suc- cess, they influence one another and tend to move toward a common po- sition. As an individual begins to approximate its neighbor’s best posi- tion, it may perform better and influence its neighbors, and on and on; good decisions spread through the population. We are comfortable call- ing this the formation of a culture in a computational population. In this section we have developed an extremely parsimonious model of binary choice as a function of individual learning and social influence. Individuals tend to gravitate probabilistically toward the decisions that have resulted in successes for themselves and their colleagues. The result is optimization of each individual’s decision vector and convergence of the population on an optimal pattern of choices. The entire algorithm, maximizing goodness, is shown in pseudocode: Loop For i = 1 to number of individuals r r if G ( x i ) > G ( pi ) then do //G() evaluates goodness For d = 1 to dimensions pid = xid //pid is best so far Next d End do g=i //arbitrary For j = indexes of neighbors r r If G ( p j ) > G ( pg ) then g = j //g is index of best performer in the neighborhood Next j For d = 1 to number of dimensions v i (t ) = v id (t − 1) + ϕ1( pid − x id (t − 1)) + ϕ2 ( pgd − x id (t − 1)) v id ∈ (−Vmax, + Vmax ) if ρid < s (v id (t )) then x id (t ) = 1; else x id (t ) = 0 ; Next d Next i Until criterion Team LRN