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