Mass-spring-damper Motion Dynamics-based Particle Swarm Optimization

(1)

Mass-spring-damper Motion Dynamics-based Particle Swarm Optimization

Ki-Baek Lee and Jong-Hwan Kim

Abstract— Mass-spring-damper motion dynamics-based particle swarm optimization (MMD-PSO) is a novel optimization paradigm based on motion dynamic model which consists of mass, spring and damper. In MMD-PSO some particles, which are located fitter places than other particles, drop their anchor and connect springs and dampers between the anchors and all the particles. These connections influence the movements of the particles so as to proceed to fitter places attracted by the anchors. To demonstrate the effectiveness of MMD-PSO, several experiments are carried out on numerical optimization problems with complex test functions. The results show that proposed MMD-PSO is more powerful than original PSO and PSO mass-spring analogy in terms of robustness and convergence speed with no tuning parameters.

I. INTRODUCTION

Problems which need global optimization frequently arise in practical engineering applications. These problems usually require controller parameters satisfying desired well-known time domain specification such as rise time, settling time and percent-overshoot. The optimization process starts from mod- eling the system under control and designing an objective function based on the time-domain specification each value of which item depends on the controller parameters. The objective function can be successfully modeled in a simple problem; however, it is often difficult or impossible to get it in a closed form in case of the function is nonlinear and non-differentiable.

In this case, stochastic optimization techniques such as evolutionary programming (EP), evolution strategies (ES) and genetic algorithm (GA), can be applied because of their robustness compared to the traditional optimization methods such as calculus-based and enumerative strategies [1], [2], [3], [4]. However, in spite of their advantages, such evolutionary algorithms (EAs) require considerable computing power and need various considerations and tunings for implementation. Particle swarm optimization (PSO), which models a bird ﬂock or a ﬁsh swarm, can be also used for this purpose [5], [6]. PSO shows faster convergence speed even with less number of computations than GA [7]. However, conventional PSO also requires design parameters to be tuned.

The goal of this paper is to upgrade the conventional PSO such that it can ﬁnd global solution as fast as possible without any tuning parameters. Proposed PSO algorithm is based on the motion dynamics of mechanical system modelled by

Ki-Baek Lee and Jong-Hwan Kim are with the Department of Electrical Engineering and Computer Science, Korea Avdanced Institute of Science and Technology, Daejon, Republic of Korea, (phone: +82-42-869-5448;

email:{kblee, johkim}@rit.kaist.ac.kr).

mass-spring-damper. After particles are initially distributed, they explore the search space following the mass-spring- damper motion dynamics model. Anchors are placed on the several current ﬁttest positions, and the particles are pulled by springs and dampers connected to the anchors. As generation proceeds, eventually the particles gather to the optimal solution. Its computation time is relatively shorter than that of other algorithms. In addition, proposed algorithm shows robustness against local minimum problems. The effectiveness of the algorithm is veriﬁed by carrying out experiments on well-known test functions.

The remainder of this paper is organized as follows.

In Section II, MMD-PSO along with its terminology is described in detail. Section III presents the experiment results on test functions including De Jong functions, Griewangk’s function, Rastrigin’s function, Ackley’s function, and Schwe- fel’s (sine root) function. The results are compared with those by original PSO and PSO mass-spring analogy [7], [8]. Finally, conclusions and further works follow in Section IV.

II. PROPOSEDPSO ALGORITHM

A. Terminology

Let us assume that thei-th particle has the mass, mi, which follows the following Newton’s second law:

Fi= mi¨xi (1)

whereFiis the force of thei-th particle and xiis the position of thei-th particle.

An anchor is a heavy object used to attach something at a specific point. Also, let us introduce a concept of anchor, which is a heavy object at a specific fixed point used to fasten something securely. In this paper, it is assumed that anchors have infinite mass and do not move.

A spring is a ﬂexible elastic object used to store mechanical energy. Springs follow the Hooke’s law, described as

Fsi= −kxdi0 (2)

where Fsi is the force exerted by the spring on the i-th particle,di0is the distance from thei-th particle to the origin andkxis the modulus of elasticity. Assume springs have zero mass, and do not break.

A damper is a device that deadens, restrains, or depresses the motion of the particle. It is used to represent viscosity and satisﬁes the following equation:

Fdi= −kv˙xi (3)

(2)

whereFdi is the force exerted by the damper on thei-th particle,xi is the position of thei-th particle and kv is the modulus of viscosity. Dampers are also assumed to have zero mass.

B. Configuring search space and fitness values Search spaceS is defined as

S ⊂ Rⁿ

and the position of thei-th particle in the search space is represented by the following vector:

xi= [xi1 xi2 xi3 ... xin]^T ∈ S.

At the position of thei-th particle, the ﬁtness value fiis deﬁned as

fi= f(xi). (4)

The greater the fitness value, the fitter the position of the fitness value. The higher the fitness value, the fitter the position of the particle. Therefore, the goal of the searching process is to find the position of the particle with the highest fitness value.

C. Dynamic motion model of the particle

Figure 1 shows a particle connected to an anchor with a spring and a damper. Let us assume that there areN particles

anchor

particle

damper

spring

Fig. 1. Particle,anchor,spring and damper

andM anchors. Net force Fiacting on thei-th particle can be derived by (2) and (3) as follows:

Fi= Fsi+ Fdi

= −

M j=1

(k_j^adij+ ki˙xi) (5)

wherek_j^ais the modulus of elasticity of the spring from the j-th anchor, ki is the modulus of viscosity of the damper to thei-th particle and dij is the distance between thei-th particle and thej-th anchor. The distance is deﬁned as

d = x − x^a

wherex^a_j is the position of thej-th anchor. Then, (5) can be rewritten as

F =

M j=1

k^aj(x^aj− xi) − ki˙xi

. (6)

By substituting (6) to (1), the acceleration of thei-th particle is calculated as

¨xi=

M j=1

(k_j^a(x^a_j − xi) − ki˙xi

mi . (7)

Above equation can be rewritten in a discrete time represen- tation as follows:

vi[k+1]−vi[k] =

_M

j=1

k^a_j(x^a_j[k] − xi[k]) − kivi[k]

mi (8)

where vi[k] is the velocity of the i-th particle at k-th generation and xi[k] is the position of the i-th particle at k-th generation. By setting the value of mi unit, the update rules for Mass-spring-damper motion dynamics-based particle swarm optimization can be derived as

⎧⎨

⎩

vi[k + 1] = vi[k] +_M

j=1

kj^a(x^aj[k] − xi[k]) − kivi[k]

xi[k + 1] = xi[k] + vi[k + 1].

(9) D. Procedure of the proposed PSO algorithm

N particles are ﬁrst distributed at random according to uniform distribution in the search space. Figure 2(a) shows the initial positions ofN particles.

(a) Initial positions ofN particles (b) Selected M anchors (black circles) amongN particles

Fig. 2. Particles and anchors

After initialization, the ﬁtness at each position can be evaluated by (4).M best positions are selected and anchors are dropped at their position. Figure 2(b) shows the visual- ization ofN particles and M anchors, where black circles indicate the anchors. As soon as anchors are dropped, springs and dampers are connected between each anchor and all the particles. In this paper, the modulus of elasticity of the spring connected from thej-th anchor, j = 1, 2, · · · , M, is deﬁned as

kj^a= f_j^a (10)

where f_j^a is the ﬁtness value at the position of the j-th anchor. The physical meaning of (10) is that the anchor at

(3)

high fitness position gets strong springs. In other words, the anchor pull the particles strongly proportional to the fitness of its position. Similarly, the modulus of viscosity of thei-th particle,i = 1, 2, · · · , N, is defined as

ki= fi (11)

wherefiis the ﬁtness value at the position of thei-th particle.

(11) implies that the particle resists external forces as much as its ﬁtness. Therefore, (9) can be rewritten as

⎧⎨

⎩

vi[k + 1] = vi[k] +M j=1

fj^a(x^aj[k] − xi[k]) − fivi[k] xi[k + 1] = xi[k] + vi[k + 1]

(12) In each generation ﬁtness values are calculated and new M best positions are selected to drop an anchor. This process is repeated until certain termination criterion is satisﬁed.

Trajectories of the particles can be obtained by the update rules, (12). As these update rules show, there are no tuning parameters because ﬁtness values are directly used for them.

Figure 3 shows the movements of the particles as generation passes by.

(a) generationk = 0 (b)k = 25

(c)k = 50 (d)k = 75

Fig. 3. Movements of the particles

The generic pseudo-code of the proposed PSO is described as follows:

1) initialize the positions ofN particles 2) repeat

a) evaluate the particles for ﬁtness values b) selectM best positions

c) drop an anchor at each ofM position d) for each anchoraido

i) for each particlepjdo

A) connect a spring and a damper betweenai

andpj

B) calculate the force exerted onpj

C) calculate the displacement ofpj

D) update the position ofpj

3) until termination criterion is met

III. EXPERIMENT WITH COMPLEX TEST FUNCTIONS A. Environment conﬁguration

In this experiment, search spaceS was deﬁned as S ⊂ R²

and the position vectorx was represented as x = [x1x2]^T ∈ S.

The number of particles,N was set to 100 (10 × 10), 169 (13 × 13) and 225 (15×15). The number of anchors, M was set to4. The methods to be compared were original PSO and PSO mass-spring analogy (PSO-MSA). Update rules of original PSO and PSO-MSA were used, respectively, as follows:

• original PSO

⎧⎨

⎩

vi[k + 1] = w · vi[k] + c0· (x^pBesti − xi[k]) +c1· (x^gBest− xi[k]

xi[k + 1] = xi[k] + vi[k + 1]

wherew, c0, and c1 are the tuning parameters of original PSO,vi the velocity of thei-th particle, xithe position of thei-th particle, x^pBesti the best position of thei-th particle, andx^gBestthe current global best position of the particles.

• PSO-MSA

vi[k + 1] = α · vi[k] + C · (xi[k]) xi[k + 1] = αvi[k + 1] + (1 − C)xi[k]

whereα and c are the tuning parameters of PSO-MSA. The values of tuning parameters of each method were set as shown in Table I. Note that MMD-PSO did not require any additional tuning parameters. All the three algorithms was terminated after one hundred generations.

Function Tuning parameters

Original PSO

W C0 C1

0.5 0.5 0.5

PSO-MSA α C

0.5 0.5

MMD-PSO None

TABLE I TUNING PARAMETER SETTING

(4)

B. Test functions

Following seven functions were selected as test functions:

1) First De Jong function [9]

f(x1, x2) = x12+ x22

(−10.0 < x1, x2< 10.0)

2) Second De Jong function (Rosenbrock’s saddle) [10]

f(x1, x2) = 100 · (x12− x1)²+ (1 − x1)² (−2.0 < x1, x2< 2.0)

3) Fifth De Jong function (Shekel’s Foxholes) [11]

f(x1, x2) = 1

0.002 +₂₅

i=1 1

(i−1)+P2

j=1(xj−ai,j)⁶

(−50.0 < x1, x2< 50.0) ai,1= (-32, -16, 0, 16, 32) fori = 1,2,3,4,5 ai,1=ai mod5,1

ai,2= (-32, -16, 0, 16, 32) fori = 1,6,11,16,21 ai,2=ai+k,2,k=1,2,3,4

4) Griewangk’s function [12]

f(x1, x2) = x12

4000+ x22

4000− cos(x1) · cos(x2

2) + 1 (−10.0 < x1, x2< 10.0)

5) Rastrigin’s function [12], [13]

f(x1, x2) = 20.0 + x12− 10.0 · cos(2πx1) +x22− 10.0 · cos(2πx2)

(−6.0 < x1, x2< 6.0) 6) Ackley’s function [14], [15]

f(x1, x2) = −20.0 · e^−0.2

qx12+x22 2

−ecos(2πx1)+cos(2πx2 )

2 + 20.0 + e

(−50.0 < x1, x2< 50.0) 7) Schwefel’s (sine root) function [16]

f(x1, x2) = 2 · 418.9829 − x1sin(

|x1|)

−x2sin(

|x2|) (−500.0 < x1, x2< 500.0)

C. Experiment results

In experiments, each algorithm was performed 50 times for each test function with the same number of generations of 100. Table II shows the summary of the experimental results.

For each case of the number of particles, MMD-PSO is dominant. With sufﬁciently large number of particles, MMD- PSO is dominant as shown in Table II(c). In addition to the best solutions, the worst solutions of the MMD-PSO were the smallest for all the test functions. In particular, in the cases of second De Jong function, Griewangk’s function, Rastrigin’s function and Schewefel’s function, original PSO and PSO- MSA tended to approach the local minima. However, MMD- PSO successfully avoided the local minima and could reach the global solution. Mean and median values of MMD-PSO were much smaller than those of other methods. Relatively small variance of MMD-PSO also veriﬁes that it is much robuster than other ones.

Figure 4 shows the comparison results from the view point of convergence speed. For three test functions such as first De Jong, fifth De Jong, and Ackley’s function, the algorithms showed similar convergence speed. Thus, the rusults for the rest four functions such as second De Jong, Griewangk’s, Rastringin’s, and Schewefel’s function, were compared as shown in Figure 4. In the figure,X and Y axes represent the number of generations and the best value for each test function at that generation, respectively. Smaller values mean better results since the functions are fit to minimization problems. In other words, the faster it reduces, the better the result is. Among the four figures, Figure 4(a), Figure 4(c) and Figure 4(d) show that MMD-PSO has considerably faster convergence rate than the others. In the case of Figure 4(b), MMD-PSO and original PSO showed similar converged rate.

From the results, it can be concluded that MMD-PSO can ﬁnd global solution more accurately than original PSO and PSO-MSA. In addition, MMD-PSO shows better convergence property than the others.

IV. CONCLUSIONS

This paper proposed a novel optimization method, MMD- PSO, based on motion dynamics model, which consisted of mass, spring, damper. For verifying the performance of MMD-PSO, seven complex test functions were used. The functions were ﬁrst De Jong function, second De Jong function, ﬁfth De jong function, Griewangk’s function, Rastrigin’s function, Ackley’s function and Schwefel’s (sine root) function. Experimental results demonstrated that the performance of MMD-PSO was competitive. Most of all, MMD-PSO did not require any tuning parameters which are indispensable to original PSO and PSO-MSA. In addition, MMD-PSO could approach the global best with better solution accuracy than other comparison methods. The convergence rate of MMD- PSO was also faster than others.

REFERENCES

[1] D. E. Goldberg, Genetic Algorithm in Search, Optimization and Machine Learning.

(5)

TABLE II

COMPARISON RESULTS OF TEST FUNCTIONS WITH METHODS OF ORIGINAL PSO,PSO-MSA,AND PROPOSEDMMD-PSO (a)N = 100

``````^Method ^Metric`` ^Worst ^Best ^Mean ^Median ^Variance

1^stDe Jong Original PSO 1.10e-16 7.46e-18 6.81e-17 6.69e-17 1.12e-33 PSO-MSA 1.31e-15 1.09e-16 1.71e-16 1.10e-16 7.17e-32

f₁ MMD-PSO 7.31e-16 4.40e-18 1.36e-16 1.01e-16 3.47e-32

2^ndDe Jong Original PSO 3.09e-16 4.03e-18 6.13e-17 4.86e-17 4.38e-33 PSO-MSA 5.44e+03 1.09e-16 4.86e+02 1.59e-16 2.27e+06

f₂ MMD-PSO 1.08e-16 3.25e-17 8.16e-17 9.05e-17 7.16e-34

5^thDe Jong Original PSO 9.98e-01 9.98e-01 9.98e-01 9.98e-01 5.19e-32 PSO-MSA 9.98e-01 9.98e-01 9.98e-01 9.98e-01 5.19e-32

f₃ MMD-PSO 9.98e-01 9.98e-01 9.98e-01 9.98e-01 5.19e-32

Griewangk’s Original PSO 1.23e-02 1.11e-16 6.66e-03 9.86e-03 3.20e-05 PSO-MSA 1.23e-02 1.11e-16 3.70e-03 1.11e-16 2.72e-05

f₄ MMD-PSO 9.86e-03 1.00e-20 1.48e-03 1.11e-16 1.31e-05

Rastrigin’s Original PSO 1.09e+00 1.00e-20 1.04e-01 1.00e-20 1.04e-01 PSO-MSA 7.43e-02 1.00e-20 3.71e-03 2.63e-14 2.76e-04

f5 MMD-PSO 7.71e-13 1.00e-20 4.26e-14 1.00e-20 2.97e-26

Ackley’s Original PSO 5.89e-16 5.89e-16 5.89e-16 5.89e-16 1.03e-62 PSO-MSA 7.67e-07 1.21e-10 8.68e-08 1.99e-09 3.68e-14

f6 MMD-PSO 7.21e-13 5.89e-16 3.66e-14 5.89e-16 2.59e-26

Schwefel’s Original PSO 1.19e+02 2.55e-05 3.03e+01 2.55e-05 2.74e+03 PSO-MSA 1.19e+02 2.55e-05 3.56e+01 2.55e-05 3.12e+03

f7 MMD-PSO 1.19e+02 2.55e-05 2.37e+01 2.55e-05 2.37e+03

(b)N = 169

f₁ MMD-PSO 6.10e-16 3.30e-17 1.35e-16 1.08e-16 1.88e-32

f₂ MMD-PSO 4.78e-14 3.53e-17 2.49e-15 1.07e-16 1.14e-28

f₃ MMD-PSO 9.98e-01 9.98e-01 9.98e-01 9.98e-01 5.19e-32

f₄ MMD-PSO 9.86e-03 1.00e-20 9.86e-04 1.11e-16 9.22e-06

Rastrigin’s Original PSO 9.35e-01 1.00e-20 4.67e-02 1.00e-20 4.37e-02 PSO-MSA 9.95e-03 1.00e-20 4.97e-03 2.63e-14 4.95e-06

f5 MMD-PSO 7.71e-13 1.00e-20 5.74e-14 1.00e-20 3.47e-26

f6 MMD-PSO 9.41e-13 5.89e-16 1.20e-13 5.89e-16 8.62e-26

f7 MMD-PSO 1.18e+02 2.55e-05 1.78e+01 2.55e-05 1.88e+03

(c)N = 225

f₁ MMD-PSO 1.10e-16 3.20e-18 7.12e-17 6.81e-17 1.19e-33

f₂ MMD-PSO 1.08e-16 1.20e-17 8.00e-17 9.05e-17 8.94e-34

f₃ MMD-PSO 9.98e-01 9.98e-01 9.98e-01 9.98e-01 5.19e-32

f₄ MMD-PSO 1.11e-16 1.00e-20 1.05e-16 1.11e-16 6.16e-34

Rastrigin’s Original PSO 9.95e-01 1.00e-20 9.95e-02 1.00e-20 9.38e-02 PSO-MSA 5.13e-02 1.00e-20 2.56e-03 2.13e-14 1.31e-04

f₅ MMD-PSO 1.00e-20 1.00e-20 1.00e-20 1.00e-20 9.53e-34

f6 MMD-PSO 5.89e-16 5.89e-16 5.89e-16 5.89e-16 1.02e-62

f7 MMD-PSO 1.18e+02 2.55e-05 1.18e+01 2.55e-05 1.33e+03

(6)

0 20 40 60 80 100 10⁻²⁰

10⁻¹⁵ 10⁻¹⁰ 10⁻⁵ 10⁰

Generation 2nd De Jong function

Original PSO PSO−MSA MMD−PSO

(a) 2^ndDe Jong function

0 20 40 60 80 100

10⁻¹⁵ 10⁻¹⁰ 10⁻⁵ 10⁰

Generation

Griewangk‘s function

(b) Griewangk’s function

0 20 40 60 80 100

10⁻¹⁵ 10⁻¹⁰ 10⁻⁵ 10⁰

Generation

Rastrigin‘s function

(c) Rastrigin’s function

0 20 40 60 80 100

10⁻⁴ 10⁻² 10⁰ 10²

Generation

Schwefel‘s (sine root) function

(d) Schwefel’s (sine root) function Fig. 4. Comparison results from the view point of convergence speed (N = 225)

[2] D. B. Fogel, Evolutionary Computation: Toward a New Philosophy of Machine Intelligence, 2nd ed. Piscataway, NY: IEEE Press, 2000.

[3] H.-P. Schwefel, Evolution and Optimum Seeking. New York: Wiley Inter-Science, 1995.

[4] J.-H. Kim and H. Myung, “Evolutionary programming techniques for constrained optimization problems,” IEEE Trans. on Evolutionary Computation, vol. 1, no. 1, pp. 119–128, May 1997.

[5] C. W. Reynolds, “Flocks, herds and schools: A distributed behavioral model,” Comput. Graph., vol. 21, no. 4, pp. 25–34, 2001.

[6] F. Heppner and U. Grenander, “A stochastic nonlinear model for coordinated bird ﬂocks,” in The Ubiquity of Chaos, E. S. Krasner, Ed., Washington, DC: AAAS, 1990.

[7] B. Brandstatter and U. Baumgartner, “Particle swarm optimization- mass-spring system analogon,” IEEE Trans. on Magnetics, vol. 38, no. 2, Mar. 2002.

[8] J. Kennedy and R. C. Eberhart, “Particle swarm optimization,” in in Proc. IEEE Int. Conf. of Neural Networks, vol. IV, Perth, Australia, 1995, pp. 1942–1948.

[9] K. De Jong, “An analysis of the behavior of a class of genetic adaptive systems,” Ph.D. dissertation, University of Michigan, 1975.

[10] H. Rosenbrock, “An automatic method for ﬁnding the greatest or the least value of a function,” The Computer Journal, vol. 3, no. 3, pp.

175–184, 1960.

[11] J. Shekel, “Test functions for multimodal search techniques,” in Fifth Annual Princeton Conf. on Information Science and Systems, 1971.

[12] A. T¨orn and A. Zilinskas, “Global Optimization,” Lecture Notes in Computer Science, vol. 350, 1989.

[13] H. M¨uhlenbein, D. Schomisch, and J. Born, “The Parallel Genetic Algorithm as Function Optimizer,” Parallel Computing, vol. 17, no.

[14] D. H. Ackley, A connectionist machine for genetic hillclimbing.

Boston: Kluwer, 1987.

[15] T. B¨ack, Evolutionary algorithms in theory and practice. Oxford University Press, 1996.

[16] H.-P. Schweful, Numerical optimization of computer models. Chices- ter: Wiley & Sons, 1981.