Overview
| module url | N/A | ||||||||||
| git repository | https://bitbucket.org/arrizza-public/ai-pso-simple-test-rb | ||||||||||
| git command | git clone git@bitbucket.org:arrizza-public/ai-pso-simple-test-rb.git | ||||||||||
| verification report | https://arrizza.com/web-ver/ai-pso-simple-test-rb-report.html | ||||||||||
| version info |
|
- repo status: Repo Information
- installation: Common Setup
Summary
The PSO (Particle Swarm Optimization) is a method to search a very large solution space efficiently. It is based on observations of ants and other social animals and how they search efficiently for food.
The original code was from AI Gemini, see original_simple_test.rb. I took that, refactored it, added the ability to change the run parameters more easily.
Solution space
The graph of the function used for this test is:
The function has many local minima and maxima and so should pose the best challenge to the PSO algorithm. In ut/mock_obj_max_func.rb there is an equivalent, inverted function which can be used for finding the global maxima.
Note the global minima is at 0.0. Therefore, the main.rb defines the better?() method to find minimum values.
Note also that this formula can be used with multiple dimensions.
Changes @dimensions = 3 to however many dimensions you want to try.
Note with 500 iterations:
- 2 dimensions: finds 0.0 usually within 100 tries; periodically needs 1 restart
- 3 dimensions: finds 0.0 usually within 200 tries; may need 1 or 2 restarts
- 4 dimensions: finds 0.0 usually within 400 tries; may need several restarts, may fail to find 0.0
- 5 dimensions: finds 0.0 usually within 500 tries; fails to find 0.0 in 500 tries about half the time
- more than 5 dimensions, fails nearly every time
Restart
I added the ability for the search to restart. The original code could get into a local minima/maxima and therefore not find the global minima/maxima. The restart solves this by detecting that scenario and then putting the particles into new random positions. while keeping the current global best position.
When I used the original algorithm with more than 2 dimensions, it failed to find 0.0 in 500 iterations. But adding the restarts increased the odds quite a bit.
How to use
./doit # run with default 3 dimensions
./do_ut # run unit tests
Typical output
Using 3 dimensions.
0] Best: 0.064155, -1.163064, 1.838379 cost: 15.071207
50] Best: 0.000579, 0.001134, 0.992355 cost: 0.996625
100] Best: 0.000003, 0.000007, 0.994955 cost: 0.994959
119] restarting particles
149] restarting particles
150] Best: -0.000000, -0.000000, 0.994959 cost: 0.994959
200] Best: 0.000324, -0.001229, 0.000252 cost: 0.000333
222] --> found 0.0
250] Best: -0.000005, -0.000003, -0.000003 cost: 0.000000
252] restarting particles
282] restarting particles
300] Best: -0.000004, 0.000001, 0.000001 cost: 0.000000
312] restarting particles
342] restarting particles
350] Best: -0.000004, 0.000001, 0.000001 cost: 0.000000
372] restarting particles
400] Best: -0.000004, 0.000001, 0.000001 cost: 0.000000
402] restarting particles
432] restarting particles
450] Best: -0.000004, 0.000001, 0.000001 cost: 0.000000
462] restarting particles
492] restarting particles
500] Best: -0.000004, 0.000001, 0.000001 cost: 0.000000
Optimization Complete!
Final Global Best posn: -0.000004, 0.000001, 0.000001
Final Global Best cost: 0.0
Using 6 dimensions:
0] Best: -4.026149, -4.886856, 1.124305, -3.020317, -2.001549, 0.024360 cost: 60.138192
50] Best: -0.981231, -0.969007, 0.089159, 0.988221, 0.974176, -1.084151 cost: 8.321972
100] Best: -0.990757, -0.995370, 0.004921, 0.993943, 0.992309, 0.002610 cost: 3.991122
150] Best: 0.043085, -0.994881, 0.000128, 0.967644, 0.984158, 0.002191 cost: 3.522299
200] Best: 0.000281, -0.995278, -0.000520, 0.995213, 0.994688, -0.000048 cost: 2.984994
250] Best: -0.003346, 0.000617, 0.001736, 0.994533, 0.992577, -0.001992 cost: 1.994760
300] Best: -0.000031, 0.000087, 0.000026, 0.994891, 0.994960, 0.000001 cost: 1.989921
334] restarting particles
350] Best: 0.000001, -0.000001, -0.000001, 0.994961, 0.994960, 0.000001 cost: 1.989918
364] restarting particles
394] restarting particles
400] Best: 0.000001, -0.000001, -0.000001, 0.994961, 0.994960, 0.000001 cost: 1.989918
424] restarting particles
450] Best: 0.000001, -0.000001, -0.000001, 0.994961, 0.994960, 0.000001 cost: 1.989918
454] restarting particles
484] restarting particles
500] Best: 0.000001, -0.000001, -0.000001, 0.994961, 0.994960, 0.000001 cost: 1.989918
Optimization Complete!
Final Global Best posn: 0.000001, -0.000001, -0.000001, 0.994961, 0.994960, 0.000001
Final Global Best cost: 1.989918