Well, 1 and 2 are random (1-dimensional) numbers, which scale the new directions. They are generated (1) at every update and (2) for each individual (and for this individual they hold for dimensions d=1, ...,D". I think this is how to understand the sentence.

Yeah, Oliver is correct.

Indeed, you are right! The newest versions of PSO or Standard PSO are going towards random updating, loosing their radix of swarm intelligence! I think this is a open issue which should make to rethink the followed approach. It is enough to look at the updating rule: with some manipulation you can obtain only a sort of random updating!

Thus, the PSO looses its social behavior. I think it is a pity

I believe the confusion stems from a somewhat sloppy use of the term "random vector". As you write your question, it sounds to me as if you think the resulting attraction vector is random in the sense that (at least) any direction in the search space is equally likely (there is also the length, but that is less relevant here). However, this is not the case: with random (uniform) choices of epsilon_1 and epsilon_2 in [0,1] (which, I believe, is the standard case), the result is a (random) restricted linear combination of the two attraction vectors. As a consequence, not all vectors (or directions) are equally likely. Rather only all linear combinations of the two attraction vectors with coefficients in [0,1] are equally likely, while all other vectors are impossible. (Simple example: if pbest = (1,0) and lbest = (0,1), the result can be (0.3,0.7) or (0.5,0.8), but it cannot be (-0.5, 0.2) or (0.3,-0.6) or (-0.4,-0.7).)

You may want to take a look at Bertrand's paradox, where a similarly sloppy use of "random chord" leads to similar problems.

I hope this helps.

As I understand it, the randomization process applies so as to introduce *some moderate* level of randomness in the velocity of each particle in each iteration, certainly the direction of the "random" vectors does not change at all by the randomization process, only their magnitudes. The update rule is such so that the new velocity of the particle will be what it previously was times the user-param \omega, PLUS a multiple of a uniformly random number in [0,\fi_p] times the difference of the particle's current position from the best known particle position, PLUS a multiple of another uniformly random number in [0,\fi_g] times the difference of the particle's current position from the best known swarm position. Therefore, for very small values of the user params \fi_g and \fi_p, despite the randomization, the velocity of each particle will remain constant throughout the optimization process if \omega=1, and will otherwise go to zero if \omega1 (of course, for very large values of the user-params \fi_p and/or \fi_g, the magnitudes will be very significant). So the update is meant to modify the velocity of the particle so as to apply a small "correction" to the trajectory of each particle towards a combination of the known best position for that particle, and the globally known best position. The position of the attractors (best known position for particle, and best globally known position for swarm) will only change when an improvement is made in either one or both of them.

In conclusion, the update rule is not designed so as to produce completely random vectors (that would end up making each particle perform simply a random walk, something not desired at all), but instead, it only randomizes the scale of the differences of the current vector's position from the attractors, and applies these scaled vectors to the current velocity.

In any case, in my (limited) set of experiments with PSO on unconstrained or box-constrained NLP problems, I found that PSO is inferior to GAs, as well as gradient descent methods (Newton, line-search, CG etc.)

Yes, epsilon 1 and epsilon 2 are random numbers. they only control the magnitude of the attraction vectors to pbest and lbest, so the direction of these vectors remains intact. consequently, the resultant overall attraction vector tend more to one of the lbest or pbest vectors, depends on the magnitude of its related random number. It is why the epsilon 1 and epsilon 2 control the convergence and exploration characteristics of the PSO.

Hum...kindish. 1 and 2 are random, or not, if you simply decide to decompose the equation and separate the random variables as 1 * r1, in which r1 varies between 0 and 1. Even if you decide to not decompose, then their main difference is really their maximum value.

In fact, we can characterize the PSO as a momentum vector plus two, or more, vectors with a certain random factor associated. Why more? Because in some works you also include the best neighbor solution or, in improved versions, you even add new parameters (e.g., fractional calculus inspiration as my work on https://www.researchgate.net/publication/230882606_Introducing_the_fractional-order_Darwinian_PSO?ev=srch_pub).

Also, those vectors may not be that constant...There are several strategies presented in the literature to adapt 1 and 2. As such, this results in a non-linear behavior of the PSO-based strategy.

Let's try to reply to your question then.

"Does anyone have any insight into the actual value of the attraction vectors after they are thoroughly randomized? "

No, that's why they are random. However, you can approximate to a deterministic version of the PSO by replacing the random vectors by their expected value, which would be half the value of the maximum amplitude of each 1 and 2.

The real question you should make is: What is the maximum value of those weights then?

This brings us to the problem of parameterized complexity. It is really hard to find the most rightful PSO combination because of its stochasticity. However, there are some works on stability theory that present a good approach. You should take a look at:

M. Clerc and J. Kennedy, The particle swarm - explosion, stability, and convergence in a multidimensional complex space, IEEE Transactions on Evolutionary Computation, 6(1) (2002), 58 - 73.

V. Kadirkamanathan, H. Selvarajah, and P. J. Fleming, Stability analysis of the particle dynamics in particle swarm optimizer,IEEE Transactions on Evolutionary Computation, 10(3) (2006), 245 - 255.

https://www.researchgate.net/publication/230882599_Analysis_and_Parameter_Adjustment_of_the_RDPSO_-_Towards_an_Understanding_of_Robotic_Network_Dynamic_Partitioning_based_on_Darwin%27s_Theory?ev=srch_pub

There are a few works studying the effects of both those parameters (or even others such as the inertial weight). For instance, a larger 2 (social weight) may cause premature convergence, thus increasing the level of exploitation over exploration.

Anyway...I think I already said too much. If you need any further help, just contact me. Just as a footnote, I wouldn't recommend you to use the standard PSO - it's kinda old and if you have complex problems (dynamic or with many sup-optimal solutions), you won't like the final result. Try PSO-based approaches with evolutionary properties.

Regards :)

Article Introducing the fractional-order Darwinian PSO

Article Analysis and Parameter Adjustment of the RDPSO - Towards an ...

Multiplying each component of a (difference) vector by different value does not only modify the length but also the direction of the vector. For example (1,1) may become (0.8, 0.3).

Furthermore, if you have the difference vector (a,b), when multiplying by values uniformly selected from [0,1] it is only poossible to generate vectors on the "box" ([0,a], [0,b]). Thus, the amount of possible "perturbed" vector that can be generated if the difference vector is (1,1) is larger than if the difference vector is (0.01, 0.01).

Taking this into account I believe It would be very interesting to draw a more accurate diagram of the PSO difference vector scheme.

Dear Stephen,

I might be wrong but it seems to me there is a double confusion in your original question.

The first one has to do with the "thoroughly randomized" vector and has already been clearly pointed out by Christian in his above comment, with which I fully agree. We have here a linear combination of vector with positive weights. Thus, even though some of these weights are random, the resulting combination is not allowed to take any possible direction in the search space.

The second confusion has to do with "However, e1 and e2 are independent random numbers". The fact that you used the word "However" sounds to me as if you thought that the linear combination you mentioned earlier in your first paragraph was actually being done with constant weights and then a random weight factor was being applied to scale the resulting combination. This is, of course, not the way the standard PSO algorithm works and this might explains why you are talking later on about "a scaled version of the attraction vector".

Maybe, there is a bit of confusion. What is the standard PSO we are referring to? I am referring to "Standard PSO 2011 (SPSO-2011)", which is "not coordinate dependent" as stated in web pages (see http://www.particleswarm.info/Programs.html) and really loose, in my opinion, the meaning of social behavior.

Other implementations present other issues!

I'm working from the source code in the following:

https://www.researchgate.net/publication/220740761_Black-box_optimization_benchmarking_for_noiseless_function_testbed_using_particle_swarm_optimization?ev=srch_pub

The code is

v = w*v + c1*rand(popsize,DIM).*(pbest-x) + c2*rand(popsize,DIM).* (repmat(gbest,popsize,1)-x);

Setting popsize to 1 and DIM to 10, the "epsilon vector" might be something like the following:

[0.8147 0.9058 0.1270 0.9134 0.6324 0.0975 0.2785 0.5469 0.9575 0.9649]

"each individual dimension d" is getting a unique random number.

However, if I multiply this "epsilon vector" to an attraction vector (e.g. [1 1 1 1 1 1 1 1 1 1]), I get something with a very different direction. In fact, I can get anything in an entire half hyperplane of 10 dimensions.

Yes, at least it's not a repulsion vector, but a half-hyperplane is a pretty wide range directions, and I think it does change how we should visualize the mechanisms of PSO.

Conference Paper Black-box optimization benchmarking for noiseless function t...

Well...the first implementation of the PSO was made by Kennedy & Eberhart in 1995 (http://www.cs.tufts.edu/comp/150GA/homeworks/hw3/_reading6%201995%20particle%20swarming.pdf). Even then, the random vector was defined to in such a way that each element should be randomly independent and, as a consequence, all the amplitudes of each dimension would vary accordingly. In fact, I use that implementation myself and the results are better for high-dimensional problems (e.g., hyperspectral image segmentation) than using a random scalar that would only change the amplitude as already suggested by some other people in this question.

Check this paper (if you have access to it or I'll send it to you):

http://onlinelibrary.wiley.com/doi/10.1002/tee.20326/abstract

You'll be able to see an example that follows exactly what you want in Fig. 1. Ofc you can try to still do something a little bit better...I did myself something similar but more complex and applied to robotics.

"Yes, at least it's not a repulsion vector, but a half-hyperplane is a pretty wide range directions". Because you're analyzing this as a direction vector. Try to simply imagine that the proportion of each component wherein each particle navigates is adjusted over time. This is a way to increase the level of exploration of particles and avoid being just another gradient method.

Hope this helps.

Antonino, in my comment I was referring to the version described in Section II of the paper mentioned by Stephen in his original question because I assumed that Stephen wanted to focus exclusively on that version.

Well, you could try to use constant coefficients, which would certainly result in premature convergence. Randomized values provide the diversity of the swarm and improve its exploration abilities. This is the only reason of this randomization.

Micael,

"Try to simply imagine that the proportion of each component wherein each particle navigates is adjusted over time."

I think it's useful to note that PSO has no advantage on a separable version of Rastrigin (e.g. BBOB 3) compared to a rotated version of Rastrigin (e.g. BBOB 15). So I don't think PSO is exploiting any type of dimension-by-dimension separability through these variable components.

Also, I'm "analyzing this as a direction vector" because that's what its effect is. I was doing some experiments comparing the motion vectors with the attraction vectors, and the complete lack of correlation between the two caught me off guard.

I think anyone who uses the standard image of vector addition (as I was) needs to rethink how PSO attraction vectors actually work. I'm not disputing that PSO works, but some movement in the half-hyperplane towards an attraction point is very different than the standard image of an attraction vector, and I think it would help us all in the PSO community to come up with more specific explanations for these effects.

Hi all,

in my mind, if we think about the effect of randomization over time, it is like a particle is attracted toward the pbest (or gbest) position by a sequence of 'biased' random jumps. This might look quite different than being attracted only by a scaled version of the difference vector.

If we do not consider the inertia and pick up only one out of pbest and lbest, I think we could visualize the path followed by a particle like in the attached image. This should increase the "exploration ability" of PSO, like Micael Couceiro said.

What do you think about this? Is it a too simplistic view?

Luca, although your image is quite a simplistic view, it is exactly that what happens in a planar problem (2D problem). I think people are over-thinking this topic too much in my opinion. There are a thousand papers around the PSO to say the least :)

Stephen, "So I don't think PSO is exploiting any type of dimension-by-dimension separability through these variable components. ". You may not want to exploit the PSO that way but the relation between dimensions is not that simply to retrieve since each dimension suffers from a random factor - Although you will find a relation in a steady-state regime, you can't ensure that relation at each iteration.

Hi friends

Using random variable as coefficient for Pbest and Lbest avoiding falling into local optimum and increase the search space .

For the optimization problem,we should do optimization several steps and the answer is the average of the answers of all because of the random aspect of optimization problems it 's not possible to have unique solution .

Luca, Micael,

Yes, it is a random walk. The velocity update diagram should really be visualized as a momentum vector, a scaled attraction vector to pbest, a scaled attraction vector to lbest, a random vector in the half hyperplane towards pbest, and a random vector in the half hyperplane towards lbest.

As mentioned several times in the discussion above, these random vectors add diversification.

I've been analyzing several performance characteristics between DE and PSO, and I think the addition of these random vectors to the PSO model will explain the results I have been getting.

Hi Everyone,

Thanks for a great discussion!

It is useful to know that there are multiple interpretations of epsilon, so this is something I will specify more explicitly about future implementations.

I was previously aware of "deterministic versions" of PSO, but the discussion makes the difference much greater than I had previously thought. This will be very useful for my current research.

I appreciate everyone's thought, time, and energy, and I wish you the best in your research endeavours. Thanks for helping with mine!

Cheers,

Stephen

Hi Everyone,

Here's an appendix to our discussion. I just wrote this for a paper, and I thought you might all find it useful.

Cheers,

Stephen

In original PSO [A], “velocities were adjusted according to their difference, per dimension, from best locations”, and this design guideline is further solidified in the 2007 standard for PSO which states that the attraction vectors are multiplied by the weights ε1 and ε2 which “are independent random numbers uniquely generated at every update for each individual dimension d =1 to D,” [B]. However, an interesting divergence has occurred to create a version with scalar random weights likely starting with “rand() and Rand() are two random functions in the range [0,1]” in [C] which becomes, for example, “r1 and r2 are independent random numbers between 0 and 1” in [D]. As an extreme, there is also “Canonical Deterministic PSO” in which the update equation “system does not contain stochastic factors” [E]. Conversely, since “the above dimension by dimension method is biased”, a “geometrical” form of update weights has also been proposed [F].

[A] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in Proc. IEEE ICNN, 1995, pp. 1942–1948.

[B] D. Bratton and J. Kennedy, “Defining a standard for particle swarm optimization,” in Proc. IEEE SIS, 2007, pp. 120–127.

[C] Y. Shi, and R. C. Eberhart, “A Modified Particle Swarm Optimizer,” in Proc. IEEE CEC, 1998, pp. 69–73.

[D] G. Venter and J. Sobieszczanski-Sobieski, “Particle Swarm Optimization,” AIAA, vol. 41, pp. 1583–1589, Aug 2003.

[E] K. Jin’no and T. Shindo, “Analysis of dynamical characteristic of canonical deterministic PSO,” in Proc. IEEE CEC, 2010, pp. 1105–1110.

[F] M. Clerc, “Standard Particle Swarm Optimisation,” Particle Swarm Central, Tech. Rep., 2012, http://clerc.maurice.free.fr/pso/SPSO_descriptions.pdf.

Stephen, your point is absolutely correct, but these vectors are at least in the same quadrant as the attractions are. Also, they are NOT CONVEX COMBINATION (these are random vectors not scalars). Take a look at rotation PSO's (these random diagonal matrices are replaced by rotation matrices which make a perfect sense). The story is much longer but this post is old as well, tell me if you were interested and we can revive this post by simply thinking about what is so special about this perturbation in PSO and what are other alternatives :-).

@Mohammad reza Bonyadi: You are right, the condition that epsilon_1 and epsilon_2 add up to 1 is not (necessarily) satisfied, which is required for a convex combination. I corrected my answer to "linear combination". One could say, though, that the result is a convex combination of the four points (1) the origin, (2) the vector from the particle to the local optimum, (3) the vector from the particle to the global optimum, and (4) the sum of the two vectors from the particle to the optima. That's what I actually had in mind, thinking visually about the question, to make the restriction of the result vector clear.

@Christian Borgelt: even if the constraint "adding up the random weights is 1" is true, they are still not convex combination. The reason is that the random choice is done for each dimension separately, which results in constructing a rectangle (assume that the value of dimensions is non-zero) which its diagonal links x and p or x and g. Now, you have two random vectors in these two rectangular areas and you add them up. It is seen that the new point generated by this random procedure is a random point in all convex hulls you can build upon x_t, any point in the rectangle generated by p-x, and any point in the rectangle generated by g-x (this was also explained in "Visualizing particle swarm optimization-Gaussian particle swarm optimization", but there was the linear form of PSO that was discussed there, and I think there was a mistake there in that paper). Assuming x_{t+1}=x_t+v_t+c1R1(p_t-x_t)+c2R2(g_t-x_t), the random point generated by x_t+c1R1(p_t-x_t)+c2R2(g_t-x_t) is MOVED then by v_t, which means the new point is not in the convex hull you can build upon x_t, x_t+c1R1(p_t-x_t), and x_t+c2R2(g_t-x_t). This mistake happen in the core proof in the paper "Particle swarms for linearly constrained optimisation" where everything was done based on convex combination, while the vector v_t was totally ignored.

@Mohammad reza Bonyadi: I believe that the problem lies in how the combination procedure is specified. I was referring to the seminal paper [Kenneth and Eberhart 1995], where the *vectors* are multiplied with random numbers epsilon_1 and epsilon_2. If this is the case, you get the convex combination I described. Of course, one may modify that to choosing a random number in [0,1] for each *element* of the vectors (and it seems that Stephen actually meant that, which I overlooked - actually I thought that by the d in his question he meant the particles and mistyped) and then you are certainly correct: the result vector may lie anywhere in a certain hyperbox defined by the elements of the two vectors. This can still be described as a convex combination, though, but one needs more source points, which can be constructed from the vectors (using individual vector elements and setting all other elements to 0).

However, I still believe that the main confusion that is expressed in Stephen's question stems from the oversight that even such a more flexible random combination still yields a fairly restricted result vector (rather than an "arbitrary" random vector), which has a clear tendency towards the (current) optima. That is, the vectors are not as "thoroughly randomized" as Stephen alleged in his question. The element-wise randomization introduces some (additional) scatter, yes (and this may be useful for exploring the search space), but the result will still not point, for example, in the opposite direction of any of the two vectors to the optima (unless they already point in opposite directions themselves), simply because the random numbers are restricted to [0,1]. If one would allow for random numbers from, say, [-1,1], one would get a more random result vector which has fairly little to do with the vectors to the optima (there are still restrictions, though, as certain dimensions are preferred to others due to the values of the vector elements, that is, in certain dimensions larger steps are possible than in others). I doubt, though, that such a choice would still let the algorithm work.

Acknowledging that the convex combination is then moved by the previous velocity, yes, this will be (most probably) a convex combination.

I agree with you that the perturbed vectors still have some information from the original vectors, as I said earlier, they are at least in the same "quadrants" (orthrands): I mean if you consider x as the center of the coordinates, the perturbed p-x will be in the same quadrant where p-x is (you might be interested in my paper "an analysis of the velocity vector of PSO", Journal of Heuristics, that discusses this). However, although this model of perturbation keeps some of these information, it has some limitations and even might be harmful. As an example, the perturbation (if it is done for each dimension separately) is dependent on the vector you are going to perturb. Consider the vector [1, 1] and compare it with [0.00001, 1] when both are perturbed the way they are perturbed in PSO. for the first vector, you will get almost a uniform distribution in the first quadrant while for the second, the distribution is totally different (skewed more towards the points closer to the first dimension). Also, I believe that the direction of the vectors p-x and g-x are very important. However, these directions might be completely changed when you multiply the dimensions by random numbers. As an example, for the second vector in my example you might get [0.000005, 0.01], which its direction is very different from the direction of [0.00001, 1].

About [-1, 1] perturbation, it can be both good and bad. It might be good because it might help in the following scenario: assume you have a two dimensional optimization problem that its objective value decreases when x and y go to positive infinity, but the global optima is in [-1, -1]. Now, if you initialize particles in the first quadrant, the probability that the particle do not attract to the positive infinity (which is in fact a trap) is very low. But, if you do the [-1, 1] perturbation, this doesnt happen. Also, it might be bad as the intensity of the perturbation is to high. A good thing about [-1, 1] is that its mean is zero, which leads to the point that particles always converge to their equilibrium if 0

Thank you to everyone for a productive discussion.  The ideas became an important part of the attached paper.

The original expectation was that PSO and DE would get "trapped" in a hyperplane smaller than the dimensionality of the search space if they used a population smaller than the dimensionality of the search space.  The "random vectors" in PSO are a very useful feature to combat this situation. 

Article Measuring the curse of dimensionality and its effects on par...

Hi Stephen;

Just a quick question: my understanding is that curse of dimensionality is not the case for separable functions as their minimizer can be found by running the algorithm separately on each dimension (see for example "Impacts of invariance in search: When CMA-ES and PSO face ill-conditioned and non-separable problems" or "a locally convergent rotationally invariant particle swarm optimization algorithm"). In this case, is the choice of sphere function (that is separable of course) the best for measuring curse of dimensionality in your paper? I do understand that a higher number of dimensions makes the separable problem harder, but it is not the best presentation of the curse of dimensionality as for separable functions you can resolve the issue. Also, PSO does that automatically, i.e., it presumes that the search space is separable and searches each dimension separately that is an advantage in optimizing separable functions. 

I think the results present a fair base-line.  Sphere is as simple a function as there is available.  If PSO and DE already experience super-linear convergence time on it, how can we expect any better anywhere else?

Hi Sptephen again;

I do appreciate that, such performance drop is of concern and good to be investigated. However, what I mean is that the usage of Sphere does not measure curse of dimensionality (because of the mentioned point).  Anyway, I think I got the point, it is not about curse of dimensionality then. Interestingly, I have also investigated similar thing as a part of one of my papers "a locally convergent rotationally invariant particle swarm optimization algorithm".

Article A locally convergent rotationally invariant particle swarm o...

Random vectors used to play big role in improve the solution of a multi-dimensional highly constrained optimization problem. Also, uniformly generated random number may not give good results.

PSO codes

https://www.researchgate.net/publication/296636431_Codes_in_MATLAB_for_Particle_Swarm_Optimization?ev=prf_pub

Code Codes in MATLAB for Particle Swarm Optimization

https://www.researchgate.net/publication/297245624_Particle_Swarm_Optimization_Algorithm_and_its_Codes_in_MATLAB

Research Particle Swarm Optimization: Algorithm and its Codes in MATLAB

I discuss this in detail in Section 3 of our survey of the state of the art in PSO (as of Apr 2018). Link is provided below. Let us know if you find it useful in your research:

Article Particle Swarm Optimization: A Survey of Historical and Rece...

The initial velocity of a particle is regulated by incrementing it in the positive or negative direction contingent on the current position being less than the best position and vice-versa (Shi and Eberhart, 1998). The random number generator was originally multiplied by 2 so that particles could have an overshoot across the target in the search space half of the time.

I also think it has more to do with strange attractors in a chaotic system. You do the randomization to avoid bias but you also make sure the momentum is controlled (by controlling the inertia) to guarantee sufficient exploration and subsequent exploitation of promising regions.

They undergo forces of attracttion and repulsión over other particles.

They are operated trough an operator that considers velocity and position iteratively

All the answer are great

The vectors in thier attractions to the best elements are evaluated continously in other regions. Therefore, the idea is to find better positions during this process