Implement new Topologies

[ljvmiranda921]

There are some topologies that we can implement in pyswarms.backend:

• Ring (static): currently, our Ring topology is dynamic. It looks for the nearest neighbors in the current iteration and there is some neighbor overlap. In a static-ring topology, the neighbors are locked down for each particle. There is still overlap, but it doesn't change every iteration. low-hanging fruit
• Von Neumann: a two-dimensional grid with neighbors in all four directions [North, East, West, South]
  References: HeuristicLab.
• Random: the position and velocity updates are affected randomly by any particle. Thus, each particle can move in any direction depending on the random particle that was chosen.

4. If you have any other ideas, just ping me!

Implementing a Topology

To implement a Topology, simply:

• Inherit from the pyswarms.backend.topology.Topology class
• Implement the following functions: compute_gbest(), compute_position, and compute_velocity.

You can check the implementations in the Star or Ring topologies.

References:

• Topology selection for particle swarm optimization
• Topology optimization for Particle Swarm Optimization

[ljvmiranda921]

Wanna try one, @szhan?

[szhan]

Yes! I am just finishing up a PR on another repo. I will get to this next!

P.S. The new release looks awesome! Great job!

[whzup]

FYI: Found this one when googling around a bit. According to that page, the pyramid and Von Neumann topologies are the best ones. There is also this WK-recursive pyramid topology which seems like bleeding edge technology (sadly I have no access to the paper).

[ljvmiranda921]

Woops just read this one.

Sure go ahead and pick one, @szhan ! I'm still finding ways on how to best represent the data structures for other topologies so this will be a learning experience for me too.

Awesome, @whzup ! Yes, I think pyramid and Von Neumann topologies are actually good. Really hoping we can implement one (or both) to release v.0.3.0. Thanks for pointing that one out!
I'll check that paper out! I'm in school so paywalls are no problemo.

[whzup]

Hey guys! I have implemented a class for a pyramid topology using the Delaunay triangulation from the scipy library. I'm on testing but I have some issues with the pytest tests. Since I have no experience with that I thought one of you guys might be able to help me.
I copied the test script for the star topology and replaced the Star() objects with Pyramid() objects. When I run the tests now the function test_compute_gbest_return_values actually works but the other two functions (for the velocity and position) return a TypeError (for all 3 test cases):

TypeError: compute_velocity() takes 2 positional arguments but 3 were given
and
TypeError: compute_position() takes 2 positional arguments but 3 were given

Which is kind of ironical as I have implemented these two functions similarly to the other two existing topologies like so:
(from .. import operators as ops)
return ops.compute_velocity(swarm, clamp)
return ops.compute_position(swarm, bounds)

Since the generation of the swarm is not dependent on the topology and the clamp parameter is defined in the pytest statement I cannot imagine where the functions receive the third argument from.

[ljvmiranda921]

Hey thanks @whzup ! Hmmm, that sounds weird. Would you mind opening a PR so we can see the code itself? My guess is that the invisible argument is coming from pytest's test parameters (or maybe in conftest).

Just make sure that the branch you are working on is different from the inverse kinematics branch before (so we won't have any merge conflicts later on). 👍 I'll look at this later tonight or on Monday. Maybe @SioKCronin might want to take a look?

[szhan]

Awesome! Since @whzup has already implemented the pyramid topology, I will take a stab at the Von Neumann topology.

[SioKCronin]

Sorry to be slow on response. @szhan, I'm happy to help if you need anything with the Von Neumann topology.

[whzup]

Hey, guys! I was looking around on the internet for some interesting topologies and I found this paper. It actually claims that a Von Neumann topology is nothing more than a static ring topology with 4 neighbours 🙈. So I guess we can cross this one out. Furthermore, I found this paper, I like this proposal of the mixture of topologies (static and dynamic) in one swarm to combine the best of both. But it might require another Optimizer class and would be something for the future (v0.4.0 maybe?).
I am now working on a Random topology and I found a good paper for that. Although, I am not sure if it is (computationally) worth it to use Dijkstra's algorithm just so we can create a random topology. I'd have just used numpy.random for this task. What do you think?

[whzup]

Another thing: Currently we only have dynamic approaches for the topologies, except the Star topology which just uses all particles as a reference and therefore does not require special treatment. If we want to implement other static topologies, though, we need a way to include the swarm in the topology class so the swarm has fixed neighbours which do not have to be computed in every iteration. At the moment this might not be possible because the topology has no way to permanently assign neighbours to particles. I reckon the best step to take would be to initialize the swarm inside the topology classes and not in the SwarmOptimizer class as it is now. Reasons for that being:

• "Topical" connection: The topology and the swarm already have a strong topical connection. Initializing the swarm at the same time as we initialize the topology makes a lot of sense (to me at least).

• Less classes: The difference between the static and the dynamic version of a topology is then just defined by the placement of the initialization of the neighbourhood relationships (e.g. Delaunay triangulation, getting the nearest neighbours, etc.) inside the class either in the constructor or in the compute_gbest() method. Consequently, we could implement the static and dynamic version in one class and use a parameter to decide which one to be used.

• Gain of computation speed: If we don't initialize the swarm in the Topology classes and use a static topology it is necessary to calculate the neighbours in every iteration, thus we lose a lot of computation time to calculate the exact same neighbours over and over again.

If we use the swarm as a static attribute in the superclass Topology it might even be possible to use multiple topologies at the same time! Although, I don't know if it is possible to initizalize the swarm in the subclasses afterwards. Any thoughts on this idea?

[ljvmiranda921]

We can keep the neighbor parameter as an attribute to the Swarm class. It is flexible given the attrs module. We initialize the number of particles in the SwarmOptimizer beforehand, by that stage we can assign which one is a neighbor if which. ```python t = Ring(static=True) opt = GeneralOptimizer(n_particles=10, dimensions=2, options=options, topology=t) # By this stage we already have the indexing information for each neighbor. Computing gbest or lbest will just require accessing this matrix/data structure. We can keep this matrix either as an attribute to the Swarm or SwarmOptimizer. ``` The idea is that if you have 6 particles, we create a vector containing the “clusters.” Say we have a Ring topology (static with 2 neighbors), then we have a vector: [1, 1, 1, 2, 2, 2] : not necessarily in the order. Computing lbest for each cluster will then be as simple as accessing which particle is in group 1 or group 2, etc.

[ljvmiranda921]

The reason why we want to separate the Swarm and the Topology is because we want to delineate the particles and how they are connected: - The `Swarm` holds the data while the `Topology` holds the interactions among these datapoints (particles). - The latter governs how everything behaves, etc. And then, we have a SwarmOptimizer that enables this behavior.

[whzup]

Ok, I see your point. But we still need to pass the topology information to the swarm or vice versa. How about we implement a new method into the topology classes called assign_neighborhood(swarm) (not sure if this works, if not there is Python documentation for that). You can pass in the swarm and it sets the neighborhood attribute in the swarm. We have to pay attention with the data types because the Pyramid topology cannot use a np.array. Additionally, we can implement a boolean parameter in the topologies called static and use it to decide if we want to assign the neighbors in every iteration or just in the __init__ of the Optimizer class. Like so:

if self.top.static:
    self.top.assign_neighborhood(self.swarm)

in the __init__ method so that the neighbors are only assigned once, and:

if not self.top.static:
    self.top.assign_neighborhood(self.swarm)

in the iteration. @ljvmiranda921 do you think this is more approriate?

[ljvmiranda921]

Hi, @whzup that works and it's closer to how I imagined it. My e-mail replies are a bit confusing (and I realized that I cannot use markdown in e-mails).

Design-wise, I'd prefer to have a few number of methods in the Topology class exposed to the user. The behavior of these methods change depending on how the Topology is initialized (static=True, etc.)

By maintaining a strict set of methods exposed in the Topology class, it's easier to swap-out topologies whenever needed in the GeneralOptimizer.

I understand your point that we should not compute the neighbor information for each iteration, and there should be a way to store it. And this requires passing the Swarm information inside the Topology class. I maintain that the two classes should remain separated.

To add to your suggestion, what if we add an optional swarm parameter (default is None) during
__init__() and raise an error whenever static==True and swarm==None?

# ring.py
def __init__(static=False, swarm=None):
    if static and swarm==None:
        raise ValueError

In that case, we can create a neighbor_idx inside the Topology class whenever static==True. We then use that whenever we compute for the best scores etc. What do you think about this?

We can also add a compute_cluster_best() method to compute the best scores for each cluster in the swarm. Any thoughts, @whzup ?

[whzup]

There is one problem if we pass in the swarm as an optional parameter. If you use the GeneralOptimizer you'd have to do something like this:

import pyswarms as ps
# Other code
...
swarm = ps.backend.swarms.Swarm(params)
my_topology = Ring(static=True, swarm)
ps.single.GeneralOptimizer(func, swarm, topology=my_toplogy)

Which, in my opinion, adds an extra layer of complexity for the user. How about this, we have a neighbor_idx(=None by initialization) and a static attribute in the topology class. In the compute_gbest() method we check if the static parameter is True and if neighbor_idx is set to decide if we compute the neighbors again:

# in compute_gbest()
if self.static and neighbor_idx is None or not self.static:
   # Set neighbor_idx

So in the former, the neighbor_idx is only set in the first method call and in the latter, it's set in every method call. We have the swarm and the topology separated and a very easy solution like that.

On the compute_cluster_best() idea. This might be a possibility 😄 But how do you define a cluster? Just a certain amount of particles in a defined vicinity?

[ljvmiranda921]

Awesome, that's a good solution, @whzup ! So, the sample use-case will then be (?):

import pyswarms as ps
# Other code
t = Ring(static=True)
opt = ps.single.GeneralOptimizer(func, n_particles, dimensions, topology=t)

And then the neighbor_idx is generated at first call, then it checks if it's not None for every call.

For the cluster (I'm not sure of the correct name, unfortunately), it's just the local best between neighbors. So if we have 6 particles with 2 neighbors:

neighbor_idx = [1,2,3,3,1,2]

We compute for the best position found by those with index 1,2, and so on.
Looks pretty good to me, any holes I've missed?

[whzup]

Yes, that would be the sample use-case I guess 👍.

Isn't this almost the same as calculating the best neighbour then?
Do you think of treating the clusters as a kind of "subswarms"?

[ljvmiranda921]

Hmmm...not sure with the best terminology though. Let's just leave that for now. Maybe best_neighbor is fine. I'll just get back to this later on. But as a note to self (and others), the idea is to return a vector of shape (n_neighbors, ). With each value containing the best fitness for a given cluster.

[whzup]

Hey guys! I was pondering a bit about PSO topologies and I thought of another way to calculate a topology, I don't know if this already exists but it may be worth a thought. I thought about using convex hulls of the particles to create different layers of rings. So in the first stage we calculate the convex hull of the whole set of particles and connect the particles that lie on the convex hull:

The blue circles represent particles and the yellow edges represent the neighbour relationship.
For the next stage we only consider the points that aren't already connected so we calculate the convex hull of the set of particles that are not connected and again connect the particles that lie on the convex hull:

We repeat this process until we reached a point where no particles are left over:

Now to create a connected graph, we can pick random (or the first point in every neighbour array) particles out of two "neighbour" rings and connect them as well like so:

The orange lines represent the connection between different rings.
I think this kind of topology could be useful for optimizations with a high particle count. The outer circle will tend toward good solutions which are far from the centre of the function and thus may have a big "exploration rate" so it could pull the inner circles out of local minima. One pitfall I see is, that the calculation of the convex hull gets quite expensive for higher dimensions and therefore this topology may only be viable for low dimensional optimization. Maybe we can try to implement it in v0.4.0 and test it against other topologies. What do you think of this?

[whzup]

@szhan if you still want to implement the VonNeumann topology: I have the feature for static and dynamic topologies (discussed above) almost ready for PR. If it is accepted you can implement the VonNeumann topology by inheriting from the Ring topology. In the constructor of the VonNeumann topology, you can use the Ring constructor to set it to "static". Then you can override the compute_gbest() method. Regarding the parameter k (used for the neighbour count in the Ring topology) you can use it as the range r (see link above). The number of neighbours is a Delannoy number as described here (it depends on the dimension and the range). I think it's the easiest solution if you just call compute_gbest() of the Ring topology with the corresponding new parameters in the compute_gbest() of the VonNeumann topology. I hope this description is understandable 😄.

[ljvmiranda921]

I'll close this for now since we got the major ones in the development branch. Let's just refer back to this issue in the future for other swarm topologies. 👍