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 < 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?