Ring topology does not return the best cost

[whzup]

Describe the bug
Running the LocalBest optimizer does not return the best cost of the optimization process. If you run the script below the follwing output is given:

INFO:pyswarms.single.local_best:Iteration 1/100, cost: 847.0467466827712
INFO:pyswarms.single.local_best:Iteration 26/100, cost: 784.4191764179053
INFO:pyswarms.single.local_best:Iteration 51/100, cost: 775.2795994743307
INFO:pyswarms.single.local_best:Iteration 76/100, cost: 774.6121293244548
INFO:pyswarms.single.local_best:================================
Optimization finished!
Final cost: 774.5646
Best value: [9.489872738932803, -8.940524059524515]

[774.56456744   6.23082841   6.44505618   4.51367892  47.0349935
   2.42419718]
INFO:pyswarms.single.global_best:Iteration 1/100, cost: 17.993903172180232
INFO:pyswarms.single.global_best:Iteration 26/100, cost: 1.0102225946801522
INFO:pyswarms.single.global_best:Iteration 51/100, cost: 0.9793392229345586
INFO:pyswarms.single.global_best:Iteration 76/100, cost: 0.9740472710360936
INFO:pyswarms.single.global_best:================================
Optimization finished!
Final cost: 0.9740
Best value: [0.9989202107600275, 4.901628864717682]

[0.9740844  0.97442641 0.97406909 0.9744485  0.97396594 0.97411942]

To Reproduce
Run the following script:

import pyswarms as ps
import numpy as np
from pyswarms.utils.functions import single_obj as fx

# Set-up hyperparameters
import pyswarms as ps
import numpy as np
from pyswarms.utils.functions import single_obj as fx

# Set-up hyperparameters
options = {'c1': 0.5, 'c2': 0.3, 'w':0.9, 'p':1, 'k':1}
bounds = (np.array([-10,-10]),np.array([10,10]))
# Call instance of PSO
optimizer = ps.single.LocalBestPSO(n_particles=6, dimensions=2, options=options, bounds=bounds)
# Perform optimization
best_cost, best_pos = optimizer.optimize(fx.levi_func, iters=100, verbose=3, print_step=25)
print(optimizer.swarm.pbest_cost)


# Call instance of PSO
optimizer = ps.single.GlobalBestPSO(n_particles=6, dimensions=2, options=options, bounds=bounds)
# Perform optimization
best_cost, best_pos = optimizer.optimize(fx.levi_func, iters=100, verbose=3, print_step=25)
print(optimizer.swarm.pbest_cost)

The GlobalBest class returns the best cost it found while the LocalBest class does not.

Expected behaviour
The LocalBest class should return the best cost it found as well.

Environment (please complete the following information):

• OS: Windows
• PySwarms Version v0.2.1
• Python Version 3.7.0

Additional context

My guess is that something like this happens. The blue circles are particles and the arrow denote the "is a neighbour of" relationship. When this happens the compute_gbest does not work properly, I guess. I'm not entirely sure though.

[whzup]

If there is a nice algorithm to make a path graph of the points this might be an easy solution.

[whzup]

A pathfinding algorithm might suffice.

[ljvmiranda921]

Before we jump into adding a new algorithm in LocalBestPSO, it's better to double-check our implementation first. Maybe this is where the bug arises.

My suggestion is to check the traditional lbest algorithm, compare it with our implementation, and see if there are any discrepancies. My reference is this textbook-algorithm from A. Engelbrecht, Computational Intelligence 2nd Ed., p.291.

Where a neighbor is defined as

My guess is that we are failing to assign the personal best as global best on the whole iteration.
This might be related to #33 and #34 , and I might have overriden the changes when I wrote the backend module. 👍 I think we should revert to the changes introduced in those PRs and incorporate them in our topology, that might solve the problem.

Also @whzup, when does this problem occur? Whenever we have odd number of neighbors? static=False? Etc?

[whzup]

test.txt
Did some tests you can find the results in the file above. It looks like the effect can only be observed in the case of 1 neighbour which enforces my hypothesis that it has something to do with the connectivity of the topology. I observed the same thing when I tested the Random topology with a naive approach where I just assigned random neighbours.

[ljvmiranda921]

Ok understood. How would a shortest-path algorithm solve this?

[whzup]

Hmm, maybe the solution with the shortest-path algorithm isn't what we want.
I found something interesting in the test file I made. In the case of neighbors=1, the returned best cost is always the first entry in the pbest_cost array.
Here is the test file with the pbest_cost array printed.
Also, the ring topology does not even compute any neighbours when the number of neighbours is equal to 1 (which feels a bit counterintuitive to me but whatever). Maybe this line of code does not work properly(?):

if k == 1:
    # The minimum index is itself, no mapping needed.
    best_neighbor = swarm.pbest_cost[self.neighbor_idx][:, np.newaxis].argmin(
         axis=1
    )

I find it suspicious that there is no comparison in the LocalBest class as there are in the algorithm you mentioned. But everything above 1 works so I guess it has something to do with this special case for k=1 I mentioned above.

[whzup]

I switched the best position and the best cost of the swarm fixture in the conftest file for the topologies. It has the same best position and best cost as before but they are now on index 1 instead of index 0.
Before:

...
"pbest_cost": np.array([1, 2, 3]),
"pbest_pos": np.array([[1, 2, 3], [4, 5, 6], [7, 8, 9]]),
...

My change:

...
"pbest_cost": np.array([2, 1, 3]),
"pbest_pos": np.array([[4, 5, 6], [1, 2, 3], [7, 8, 9]]),
...

Apparently, the Random topology had some issues as well. To obtain the best position (in every topology except Star) we are using this code:

# Doesn't work
best_pos = swarm.pbest_pos[
                np.argmin(swarm.pbest_cost[best_neighbor])
            ]

But this returns the index of the particle that has the neighbour with the best cost (one long relationship 😄 give it a thought) not the index of the particle that has the best cost which we are looking for. Funny enough. By chance, this always returned the index 0 which was actually the best particle in the tests we were using until now. That's why the tests passed all the time. I changed it to the following:

# Does work
best_pos = swarm.pbest_pos[
                best_neighbor[np.argmin(swarm.pbest_cost[best_neighbor])]
            ]

Now it returns the right result every time I run the tests. It also resolved some of the test failures of the Ring topology. The problem this issue is actually about can be resolved by a quick change from this:

# Doesn't work
best_neighbor = swarm.pbest_cost[self.neighbor_idx][:, np.newaxis].argmin(axis=1)

To that:

# Does work
best_neighbor = swarm.pbest_cost[self.neighbor_idx][:, np.newaxis].argmin(axis=0)

The first one creates a column vector and searches for the minimum in each row so it just returns an array of zeros because in every row there is only a single entry (which is on index 0).
Do you agree with my reasoning @ljvmiranda921? 😄
To prevent such things I suggest that we expand our test structure for the topologies by adding a bigger swarm. Additionally, we should change the best cost to less trivial values and indices.

[whzup]

I'd like to test it with the test script I used to detect this issue. Do you know a way to do this?

[ljvmiranda921]

Hey Aaron, Great analysis! So the culprit was how the best_pos is being assigned right? Instead of getting the index of the actual particle with the best fitness, what we’re getting is the particle that neighbors it? Let me reply to you properly once I go to school. Great job! I’ll check on how we can run the tests similar to what you have done :)

[whzup]

Hi, Lester 😄. Yes, exactly. And the wrong axis was used to determine the best neighbours.
I found a StackOverflow question which describes the steps to install a package from a GitHub branch. It doesn't work for me though. I still get the version of the master branch.
This is the paste of the code I used for the testing.
I'm going to do a PR so you can view the changes.

[ljvmiranda921]

Yo @whzup !

Will a test asserting min(swarm.pbest_cost) == swarm.best_cost suffice for all cases? Even if we change the number of neighbors, we want to assure that the particle with the smallest possible fitness will always be considered.

A short integration test like the one you posted in pastebin is also a nice idea. We conjure up a small swarm in conftest, set the random seed, and check if the value will always be the case. I believe in pytest or numpy there is an approx() method that can test equality with tolerance.

Also, I might be quite inactive for the next two weeks until August 4 (next two weeks: conference and moving out). I suggest we do a feature lock in the development branch (no new features, just bug fixes if possible) so that I can keep up with my backlog in #157 and prepare for v.0.3.0 release by next month. What do you think?