Particle Swarm Optimization .*;

Pattern Search Example

This example is another variation on PSO which searches for a specific pattern of letters. In this case, the word "bingo". From the start, the algorithm doesn't know what letters it's searching for, what order they're supposed to be in, or even how many letters are in the word. To aid in it's search, the algorithm uses the Levenshtein measure of distance. The Levenshtein distance is useful in finding the difference between sequences, and is often used to measure the difference between words in various search utilities.

  • MAX_LENGTH - maximum number of letters to combine.
  • MIN_LENGTH - minimum number of letters to combine.
  • TARGET - the word to search for.
  • CHAR_SET - characters available to search with.
  • PARTICLE_COUNT - number of particles to use.
  • V_MAX - maximum velocity allowed.
  • V_MIN - minimum velocity allowed. This might seem counter-intuitive to PSO, but it really does help.
  • MAX_EPOCHS - maximum number of epochs to run algorithm.

Normally, PSO algorithms complete when the velocity reaches zero, but in this case, it actually helps to keep it from zero. This example gets stuck in local minima almost every time with velocity at zero. By keeping it just above, the target word is more likely to be found.

The CHAR_SET in this example range from "a" to "z" for the sake of simplicity, but more or less characters can easily be included.

 

Example Results 1

MAX_LENGTH = 6, MIN_LENGTH = 2, PARTICLE_COUNT = 10, V_MAX = 4.0, V_MIN = 1.0. The second particle found it in 1012 epochs.

ningo = 1
bingo = 0
ningogg = 3
ninxkn = 4
bigoin = 3
iiggog = 3
ijnsoi = 4
ignjni = 5
ninionnn = 5
ggnnncnn = 7
Changes for particle 1: 1
Changes for particle 2: 1
Changes for particle 3: 1
Changes for particle 4: 1
Changes for particle 5: 2
Changes for particle 6: 2
Changes for particle 7: 2
Changes for particle 8: 2
Changes for particle 9: 4
epoch number: 1012

 

Example Results 2

MAX_LENGTH = 6, MIN_LENGTH = 2, PARTICLE_COUNT = 10, V_MAX = 4.0, V_MIN = 0.0. V_MIN set to zero will usually get stuck in local minima. It's still interesting to see the solutions arrived at.

epoch number: 19998
kbingo = 1
binogo = 1
biingo = 1
bbngiii = 4
knidooo = 5
kbinonn = 4
kbingin = 3
bjpngnkk = 5
kbnnnnbo = 5
nninnnnn = 6
Changes for particle 1: 0
Changes for particle 2: 0
Changes for particle 3: 2
Changes for particle 4: 2
Changes for particle 5: 2
Changes for particle 6: 3
Changes for particle 7: 3
Changes for particle 8: 3
Changes for particle 9: 4
epoch number: 19999

 

Example Results 3

MAX_LENGTH = 10, MIN_LENGTH = 0, PARTICLE_COUNT = 10, V_MAX = 4.0, V_MIN = 1.0. It also helps to set the minimum and maximum search length to somewhere close to the target word size. Here, the min and max are set to 10 and zero, involving a much larger search space. Even 20000 epoch won't be enough to find the target word. Still interesting are the solutions it came up with.

nibinpgbob = 5
nibpnpgobbi = 7
inpnbpnboopp = 9
rbpgppgbopqnn = 10
nibibbbvbpppp = 11
nibnwpbnbdddn = 11
iipgnbdgwwwnn = 10
nibhppgbobwub = 10
ibiopggbbepbb = 10
nibidbcwibpkbb = 12
Changes for particle 1: 2
Changes for particle 2: 3
Changes for particle 3: 3
Changes for particle 4: 3
Changes for particle 5: 3
Changes for particle 6: 3
Changes for particle 7: 3
Changes for particle 8: 3
Changes for particle 9: 4
epoch number: 19999

 

Example Results 4

MAX_LENGTH = 10, MIN_LENGTH = 0, PARTICLE_COUNT = 20, V_MAX = 4.0, V_MIN = 1.0. Increasing the particle count doesn't help.

epoch number: 19998
kbingo = 1
binogo = 1
biingo = 1
bbngiii = 4
knidooo = 5
kbinonn = 4
kbingin = 3
bjpngnkk = 5
kbnnnnbo = 5
nninnnnn = 6
Changes for particle 1: 0
Changes for particle 2: 0
Changes for particle 3: 2
Changes for particle 4: 2
Changes for particle 5: 2
Changes for particle 6: 3
Changes for particle 7: 3
Changes for particle 8: 3
Changes for particle 9: 4
epoch number: 19999

 

public void footer() {
About | Contact | Privacy Policy | Terms of Service | Site Map
Copyright© 2009-2012 John McCullock. All Rights Reserved.
}