Ant Colony optimisation for finding subsets with ~0 sum I have a set A = [x1, x2...xn] where xi in R (real). I need to find all non intersecting subsets with subset sum ~0 (approximately equal to zero).

Since the set can have non zero real numbers, I have opted to use Ant Colony Optimisation for this problem. I have implemented this in python and the program tends to be a  bit slow (python dictionaries for the graph). It takes around 60 seconds for 100 ants for single iteration. The algorithm goes like this:


Create a graph with the whole list of real numbers (fully connected)
Initialise the graph edges with w0
Each vertex has an associated value
Initialise the position of ants at random nodes
Ants select next nodes based on edge weights
Once an ant completes tour - the sum of all vertex values > threshold 1 (1000000) or &lt; threshold 2 (~0.1), the path weights are updated based on path sum and global path updates (pheromone evaporation) after this


The questions I have:


Is the usage of ACO relevant here?
How can I improve the speed of the implementation?
Your problem is no harder and no easier than the approximate subset-sum problem.  There is a natural approach for your problem:


Find any subset that sums to something close to zero, and output it.  Remove those numbers from the set $A$.
Go back to step 1 and repeat, until the set $A$ is empty.


This requires a way to find a subset that sums to approximately zero, i.e., an approximation algorithm for the subset-sum problem.  That problem is well-studied and can be solved in polynomial time using an approach based on rounding and dynamic programming.

I don't see any reason to expect ant colony programming to be better than the standard approaches; and I wouldn't be surprised if it is worse.