## Particle Swarm Optimisation

• ```FOREWORD

1)
I will tell you what I know about Particle Swarm Optimization (PSO),
a technique that can be used to do for example Programming_9 or Logic_8

2)
I am no mathematician, so I will not use fancy mathematical language
or symbols that are not on my keyboard anyway. This is pure programming

3)
English is not my mother tongue, so forgive me errors in spelling, grammar etc.

4)
I will show you code in python and/or pseudo-code. If you do not know python, no matter.
Python is just as easy readable as pseudo-code.

INTRODUCTION

PSO is a technique of "artificial intelligence" (ai)
It is used in problems like those for example:

1)
You have one or more equations and some variables, the system having different solutions depending on what values the variables have.
You are looking for the best of those solutions fitting to a given problem.
-> That is called optimisation.
(Example: complicated technical applications like curves in antennae
and such)

2)
You have one or more equations and as many (or even more !) variables
You are looking for just some values for the variables that satisfy the equation(s)
(Example: Logic_8, Programming_9)

Below I will show you a very much simplified version of something like 2)
by explaining some principle ideas first and showing you the complete code then

BASIC IDEA -----------------------
Look those two equations:
x + y = 30
x * y = 200

Easy, you can nearly "see" the solutions.
x = 20 and y = 10 or vice versa.
Simple.. and of course quickly doable with normal mathematics.
But what if there are like 15 variables and a bunch of complex mathematical formulae involved ?
You use matrices (those give me headaches, and try to program that..)
Or you just use PSO..

Now, what does your brain do, when you just "see" the solution ?
Right, it just "tries out" some values for x and y, "10 and 10 is too little... etc"
That is easy to program, let us do it this way:

result_0 = 30  # given in the equations above
result_1 = 200

while error != 0:

test_x = some_random_integer
test_y = some_random_integer

error = 0  #reset
error = (test_x + test_y) - result_0   # check first equation
+ (test_x * test_y) - result_1   # check second equation

print test_x
print test_y

This program will find the solution, but it may take a long time.

PARTICLES --------------------------------
If you use some Object Oriented Programming Language
(Like Java, C++, Python ..etc..)
Then you easily can have multiple instances of that program running.
Lets say you make a class "Particle", make some Particle Objects, give them all that code above.
Then you have a bunch of Particles jumping through the "space", sort of looking for solutions.
One of them finds the solution -> program ends.

That is much faster than having just one little program doing the search.
Each particle has its own "personal" values for x and y
The particle that first hits on the correct values for x and y is the "winner"
The winners x and y are what we had been searching for

DISTANCE AND FITNESS ---------------------------------
Given
x + y = 30
x * y = 200

A test for some x and y on x+y gives a result.
That can be "right", like 30
It can be "pretty good" , like  31

We did express the "badness" of a solution above as "error"
Let us call it "distance" from now on, like the distance from the correct value:

distance = (test_x + test_y) - result_0		# check both equations
+ (test_x * test_y) - result_1

Let us further say:
a particle is more "fit" if its distance to the correct values is small
and less fit if its distance to the correct values is big

Like so:
fitness = 1 / distance
that gives big fitness for small distance.
And because computer explodes if distance = 0..
make that
fitness = 1 / distance + 0.1
That gives us a fitness of 10 for distance = 0.
And a particle that has fitness = 10 has solved the problem !
Each particle has its own, personal fitness, let us call it p_fitness

Pseudo-python-code for all we have done so far:

#equation one: x + y = 30
#equation two: x * y = 200

make some particles

while no particle has fitness 10:
for every particle:
try their next set of x and y on equations one and two
calculate their p_fitness

print winners values of x and y

VELOCITY ---------------------------------------
So far, the particles "jump" through space,
All of then checking random values for (x, y)
Like jumping from (1,2) to (1000, 990) in one hop and to (44, 777) in the next
If one is close to the right solutions right now, it might be far from it after the next hop.

Now we slow then down and make them move more gradually:
a) every particle gets a random starting value for x and y
b) they change those values for x and y by little and random amounts using a formula
for the velocity of the movement, simplified like this:

Every particle moves according to its own personal values for x, y, v_x, v_y

v_x = some_random_int
x = x + v_x

v_y = some_random_int
y = y + v_y

(This does not look much different from what we did above, but follow me patiently)

c) they all have a max "speed" (velocity) for moving through x and y.
We call it vmax, for example

Now they all will more or less rotate around their starting points.
For example some particle might be "cruising" in the area of (x, y) = (40, 140).

What we did so far now:

#equation one: x + y = 30
#equation two: x * y = 200

make some particles
give them all their own random x and y

while no particle has fitness 10:
for every particle:
get new random velocities v_x and v_y
reduce both velocities to vmax if necessary
update x to x+v_x
update y to y+v_y
try this new set of x and y on equations one and two
calculate p_fitness
print winners x and y

TWEAKING THE RANDOMNESS ---------------------------------------

#####This is the "heart" of the thing, which makes it so effective ###############
Now we do not change the velocity completely random anymore,
but we "tweak" the randomness:

1)
Each particle has a "personal best ever fitness" p_best_fitness
and p_best_x, p_best_y that had been used to achieve p_best_fitness

So, whenever they do a step, they compare the new p_fitness to their p_best_fitness
and they do
if p_fitness > p_best_fitness:
p_best_fitness = p_fitness
p_best_x = x
p_best_y = y
(p_best_fitness has been achieved with p_best_x and p_best_y)

2)
We introduce "best global fitness"
The main of the program checks every particle after every step for their p_fitness.
The best of all p_fitness becomes g_fitness (g for "global", p for "personal")

3)
The random v_x and v_y of every particle now shall be influenced by
a) their own personal "best ever solution" for x and y
b) the global "best ever solution" for x and y.
c) Two constants governing the relative strength of a) and b)

The two constants are:
c1 makes the influence of personal best values stronger
c2 makes the influence of global best values stronger
(I personally always set both of them to 2, dont know why, but works best)

And now we calculate the random speed v_x like this (v_y accordingly):

v_x = v_x + c1 * random * (p_best_x - present_x) # influence of personal best
+ c2 * random * (g_best_x - present_x) # influence of global best

random being anything between 0 and 1

Then we reduce to vmax if necessary:
if v_x < v_max: v_x = v_max

and we do the actual step, which in our example shall be an integer step:
present_x = (int)(present_x + v_x)

update present_y accordingly

SUMMARY ------------------------------
Yes. That was all..
The whole program as an overview:

#equation one: x + y = 30
#equation two: x * y = 200

make some particles
give them all their own random present_x and present_y

while no particle has fitness 10:
for every particle:
get new random and personal velocities v_x and v_y
reduce both to vmax if necessary
change position from x to x+v_x and y to y+v_y
try this new set of x and y on equations one and two
calculate p_fitness
update personal best fitness

determine winner
update global best fitness

print winners present x and y

CLOSING REMARKS ----------------------
Copy and paste the python code below, try it out.
You might have to change the indentations for yout text editor. This is
written and tested with geany.

I find it remarkable that a PSO (80 particles) solved any (tried like 5)
Programming_9 problem in usually less than 1000 milliseconds. Leaving me emough time for
the GET and POST stuff in order to finish within the given 2 seconds.

PYTHON CODE --------------------------------
Now here the complete code in python for what we did above with loads of comments:

import random #we need that for getting random numbers
random.seed()

#global variables
result_0 = 30		# from x + y = 30   equation one
result_1 = 200		# from x * y = 200  equation two

g_best_x = 0 		# initialize global best values for x and y to whatever
g_best_y = 0

g_best_fitness = -10.0  # initialize global best fitness to something really bad

##begin class Particle
class Particle:

present_x = 0	# let it start off somewhere
present_y = 0

p_best_x = present_x	# so far, there is no better best..
p_best_y = present_y

v_x = 0.0	# initialize velocities to something
v_y = 0.0

present_fitness = 0.0    #initialize fitness to something bad
p_best_fitness = 0.0

# These two I always set to 2.
c1 = 2 # own
c2 = 2 # best particle

present_distance = 10000 # initialize to something far away..
best_distance = 10000

def rand_1(self):			# I have that in a function for better overview
return random.random()

def move(self):  # the particle does the next step

self.v_x = self.v_x + self.c1 * self.rand_1() * (self.p_best_x - self.present_x) + self.c2 * self.rand_1() * (g_best_x - self.present_x)
if self.v_x > v_max: self.v_x = v_max
if self.v_x < -v_max: self.v_x = -v_max
self.present_x = (int)(self.present_x + self.v_x) #do step and make an int of it

self.v_y = self.v_y + self.c1 * self.rand_1() * (self.p_best_y - self.present_y) + self.c2 * self.rand_1() * (g_best_y - self.present_y)
if self.v_y > v_max: self.v_y = v_max
if self.v_y < -v_max: self.v_y = -v_max
self.present_y = (int)(self.present_y + self.v_y) #do step and make an int of it

# Let us check only positive integers here
if self.present_x < 0: self.present_x = 0;
if self.present_y < 0: self.present_y = 0;

def get_fitness(self):
dist = 0	#first get distance to result_0 and result_1
dist = dist + abs(result_0 - (self.present_x + self.present_y))
dist = dist + abs(result_1 - (self.present_x * self.present_y))

self.distance = dist
self.present_fitness = 1/(self.distance + 0.1);

if self.present_fitness > self.p_best_fitness: #update personal best fitness

self.p_best_x = self.present_x	#update personal best values for x and y
self.p_best_y = self.present_y

self.p_best_fitness = self.present_fitness
self.best_distance = self.distance

## end of class Particle

v_max = 5	# or whatever you like. found this by experimenting, is not crucial

particles = []

for k in range(80): 		# or how many you like. experiment with that..
x = Particle()
x.present_x = random.randint(0, 100); # put them somewhere random
x.present_y = random.randint(0, 100);

x.p_best_x = x.present_x	# update their p_best to that for starters
x.p_best_y = x.present_y

particles.append(x)

winner = 0 # winner will be the index of the winning particle

while g_best_fitness < 10.0:

for k in particles:	# every particle make one step
k.move()

count = 0
for i in particles:	# every particle evaluate that step

i.get_fitness()
count = count + 1
if i.p_best_fitness > g_best_fitness:
g_best_x = i.p_best_x	# if possible, update global best values..
g_best_y = i.p_best_y
g_best_fitness = i.p_best_fitness # ..and global best fitness

#want to watch ?
#print "new g_best_fitness: ", g_best_fitness, " -  particle_nr: ", count-1

winner = count - 1

print "winning nr: ", winner

print "best x: ", g_best_x
print "best y: ", g_best_y
print```