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
Or "pretty bad", like 300000
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
