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
    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