0
$\begingroup$

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:

  1. Is the usage of ACO relevant here?
  2. How can I improve the speed of the implementation?
Improve this question
$\endgroup$
4
  • $\begingroup$ I don't understand what you want the output to be. If the input is the set $\{-3,-2,-1,1,2,3\}$, what should the output be? Is $\{-3,3\},\{-2,2\},\{-1,1\}$ a valid output? Is $\{-3,-2,-1,1,2,3\}$ a valid output? Is $\{-3,1,2\},\{-2,-1,3\}$ a valid output? $\endgroup$
    – D.W. ♦
    Mar 2, 2019 at 4:33
  • $\begingroup$ @D.W. Valid outputs would be : {-3,3}, {-2,2},{-1,1} or {−3,−2,−1,1,2,3} or {−3,1,2},{−2,−1,3} $\endgroup$
    – ranger101
    Mar 2, 2019 at 9:18
  • $\begingroup$ In short: (1) yes, ACO is potentially relevant for any hard problem and (2) implementation details in concrete languages (like Python) are off-topic for the site, unfortunately. If you have a working program, you could try your luck on Code Review SE. $\endgroup$
    – Juho
    Mar 2, 2019 at 11:17
  • 1
    $\begingroup$ I don't think this is a good fit for this site. "Is ACO appropriate?" is basically a matter of personal opinion, which is off-topic everywhere on Stack Exchange. How you can improve the speed of your implementation is a programming question, which is off-topic here. Or are you actually looking for algorithmic improvements? $\endgroup$
    – David Richerby
    Mar 3, 2019 at 13:51

1 Answer 1

Reset to default
1
$\begingroup$

Your problem is no harder and no easier than the approximate subset-sum problem. There is a natural approach for your problem:

  1. Find any subset that sums to something close to zero, and output it. Remove those numbers from the set $A$.

  2. 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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ the subset that needs to be found should be approximately equal to 0 (~0), apologies if the example confused you. $\endgroup$
    – ranger101
    Mar 3, 2019 at 4:05
  • $\begingroup$ @JijoJose, ahh, I did indeed miss that. If you mean "approximately equal to 0" as opposed to "exactly equal to 0", could you edit the question to state that a bit more explicitly? Also, there are standard algorithms for finding approximate solutions to the subset sum problem, so you can use them (see the Wikipedia article I linked to for one such algorithm). $\endgroup$
    – D.W. ♦
    Mar 3, 2019 at 4:57
  • $\begingroup$ I believed the subset sum problem required the sum to be know in advance but in this case, the sum cannot be defined in advance. I think its more like a problem to find subsets which has minimum sum. $\endgroup$
    – ranger101
    Mar 3, 2019 at 13:04
  • $\begingroup$ @JijoJose, I think you probably have a misunderstanding somewhere. The algorithms require the target to be known, not the exact sum. In your case the target is 0, so it is known. See, e.g., en.wikipedia.org/wiki/…. $\endgroup$
    – D.W. ♦
    Mar 3, 2019 at 18:51
  • $\begingroup$ @JijoJose, see updated answer; it is corrected to deal with the fact that you want the sum to be approximately 0, and I've updated the link to the algorithm. $\endgroup$
    – D.W. ♦
    Mar 3, 2019 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.