Answers.Body: <p>The hill-climbing algorithm to implement is as follows:</p>
  
  <ol>
  <li>The algorithm should take four inputs: as always, there will be a multiset S and integer
  k, which are the <code>Subset</code> and <code>Sum</code> for the Subset Sum problem; in addition, there
  will be two integers q and r, with roles defined below.</li>
  <li>Do the following q times:</li>
  </ol>
  
  <p>(a) Choose a random subset (multiset) <span class="math-container">$S_0$</span> of S as the <code>current</code> subset.</p>
  
  <p>(b) Do the following (<code>hill climbing</code>) r times:</p>
  
  <p>i. Find a random neighbor T (see definition of neighbor below) of the current
  subset.</p>
  
  <p>ii. If neighbor T has smaller residue, then make T the current subset.</p>
  
  <p>(c) Keep track of the residue of the final current subset when starting with subset
  <span class="math-container">$S_0$</span>.</p>
  
  <ol start="3">
  <li>Return the smallest residue of the q subsets tested by the algorithm.</li>
  </ol>
  
  <p><strong>Definition</strong>: Subset (multiset) B ⊆ S is a neighbor of a subset A of S if you can transform
  A into B by moving one or two integers from A to B, or by moving one or two integers from
  B to A, or by swapping one integer in A with one integer in B.
  An easy way to generate a random neighbor B of a subset A of S is as follows:</p>
  
  <ol>
  <li>Order the elements of S as <span class="math-container">$x_1, x_2, ..., x_n$</span>.</li>
  <li>Initialize B to be a clone of A.</li>
  <li>Choose two distinct random indices i and j, where <span class="math-container">$1 ≤ i; j ≤ n$</span>.</li>
  <li>if <span class="math-container">$x_i$</span> is in A, remove it from B. Otherwise, add xi to B.</li>
  <li>if <span class="math-container">$x_j$</span> is in A, then with probability 0.5, remove it from B. If <span class="math-container">$x_j$</span> is not in A, then with
  probability 0.5, add <span class="math-container">$x_j$</span> to B.</li>
  </ol>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2020-03-24T19:17:58.540Z
Answers.LastActivityDate: 2020-03-24T19:17:58.540Z
Answers.UserDisplayName: Mostafa Ghadimi
Answers.Body: <p>The state space itself seems OK but your approach has some disadvantages. First, you need to pick an initial state of size <span class="math-container">$n$</span>. What if the optimal solution is of size <span class="math-container">$\frac{n}{4}$</span> or <span class="math-container">$10n$</span>? Then the search could take a long time using this approach because you are starting far away. If there are multiple solutions, do you care which one you find or is the smallest zero subset preferred? I'm going to assume that the empty set <span class="math-container">$X'=\{\}$</span> is not a solution and that solutions with smaller cardinality are preferred.</p>
  <p>I would suggest using a generative heuristic to construct the initial state and then running your hill climbing procedure from that state. For example, a generative heuristic could be something like: &quot;pick the pair of elements (<span class="math-container">$x_1$</span>,<span class="math-container">$x_2$</span>) from <span class="math-container">$X$</span> such that <span class="math-container">$x_1 + x_2$</span> is as close to zero as possible, and set <span class="math-container">$X' =\{x_1, x_2\}$</span> as the initial state&quot;. To apply this heuristic you will need to initially check <span class="math-container">$n(n-1)$</span> subsets of pairs. If this is not a solution, it will hopefully be very close to the solution in the state space and therefore a good place to start.</p>
  <p>Another problem is the hill climbing does not remember previously visited states, and you could end up infinitely looping when you allow moves to both add and delete elements from <span class="math-container">$X'$</span>. For example, suppose <span class="math-container">$X'=\{1\},X=\{-3,-50,-50,100\}$</span>. Clearly the optimal solution is <span class="math-container">$X''=\{-50,-50,100\}$</span> but your method will add element <span class="math-container">$-3$</span> to <span class="math-container">$X'$</span> first, then remove <span class="math-container">$-3$</span>, then pick <span class="math-container">$-3$</span> again etc, because these states have a lower objective value than any state with one of <span class="math-container">$-50$</span> or <span class="math-container">$100$</span> in it. So I think you need to use a more sophisticated approach that prevents visiting the same state twice.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-04-19T09:32:25.320Z
Answers.LastActivityDate: 2021-09-17T07:46:00.490Z
Answers.LastEditDate: 2021-09-17T07:46:00.490Z
Answers.UserDisplayName: Mike NZ
Body: <p>I want to solve the zero subset sum problem with the hill-climbing algorithm, but I am not sure I found a good state space for this.</p>
  
  <p>Here is the problem: consider we have a set of numbers and we want to find a subset of this set such that the sum of the elements in this subset is zero.</p>
  
  <p>My own idea to solve this by hill-climbing is that in the first step, we can choose a random subset of the set (for example, the main set is <span class="math-container">$X= \{X_1,\dots,X_n\}$</span> and we chose <span class="math-container">$X'=\{X_{i_1},\dots,X_{i_k}\}$</span> randomly), then the children of this state can be built by adding an element from <span class="math-container">$X-X'$</span> to <span class="math-container">$X'$</span> or deleting an element from <span class="math-container">$X'$</span> itself. This means that each state has <span class="math-container">$n$</span> children. and the objective function could be the sum of the elements in <span class="math-container">$X'$</span> that we want to minimize.</p>
  
  <p>Is this a good modeling? Are there better modelings or objective functions that can work more intelligently?</p>
  
Tags: <ai-design><hill-climbing><local-search>
Title: How can I solve the zero subset sum problem with hill climbing?
UserDisplayName: K.N
ThreadText: # How can I solve the zero subset sum problem with hill climbing?
  
  (Asked by: username_0 on 2020-03-12)
  
  I want to solve the zero subset sum problem with the hill-climbing algorithm, but I am not sure I found a good state space for this.
  
  Here is the problem: consider we have a set of numbers and we want to find a subset of this set such that the sum of the elements in this subset is zero.
  
  My own idea to solve this by hill-climbing is that in the first step, we can choose a random subset of the set (for example, the main set is $X= \{X\_1,\dots,X\_n\}$ and we chose $X'=\{X\_{i\_1},\dots,X\_{i\_k}\}$ randomly), then the children of this state can be built by adding an element from $X-X'$ to $X'$ or deleting an element from $X'$ itself. This means that each state has $n$ children. and the objective function could be the sum of the elements in $X'$ that we want to minimize.
  
  Is this a good modeling? Are there better modelings or objective functions that can work more intelligently?
  
  **Tags:** ai-design, hill-climbing, local-search
  
  
  ---
  
  ## 2 answers
  
  ### Answer by username_1 on 2020-03-24. Score: 0
  
  The hill-climbing algorithm to implement is as follows:
  
  1. The algorithm should take four inputs: as always, there will be a multiset S and integer
     k, which are the `Subset` and `Sum` for the Subset Sum problem; in addition, there
     will be two integers q and r, with roles defined below.
  2. Do the following q times:
  
  (a) Choose a random subset (multiset) $S\_0$ of S as the `current` subset.
  
  (b) Do the following (`hill climbing`) r times:
  
  i. Find a random neighbor T (see definition of neighbor below) of the current
  subset.
  
  ii. If neighbor T has smaller residue, then make T the current subset.
  
  (c) Keep track of the residue of the final current subset when starting with subset
  $S\_0$.
  
  3. Return the smallest residue of the q subsets tested by the algorithm.
  
  **Definition**: Subset (multiset) B ⊆ S is a neighbor of a subset A of S if you can transform
  A into B by moving one or two integers from A to B, or by moving one or two integers from
  B to A, or by swapping one integer in A with one integer in B.
  An easy way to generate a random neighbor B of a subset A of S is as follows:
  
  1. Order the elements of S as $x\_1, x\_2, ..., x\_n$.
  2. Initialize B to be a clone of A.
  3. Choose two distinct random indices i and j, where $1 ≤ i; j ≤ n$.
  4. if $x\_i$ is in A, remove it from B. Otherwise, add xi to B.
  5. if $x\_j$ is in A, then with probability 0.5, remove it from B. If $x\_j$ is not in A, then with
     probability 0.5, add $x\_j$ to B.
  
  
  ---
  
  ### Answer by username_2 on 2021-04-19. Score: 0
  
  The state space itself seems OK but your approach has some disadvantages. First, you need to pick an initial state of size $n$. What if the optimal solution is of size $\frac{n}{4}$ or $10n$? Then the search could take a long time using this approach because you are starting far away. If there are multiple solutions, do you care which one you find or is the smallest zero subset preferred? I'm going to assume that the empty set $X'=\{\}$ is not a solution and that solutions with smaller cardinality are preferred.
  
  I would suggest using a generative heuristic to construct the initial state and then running your hill climbing procedure from that state. For example, a generative heuristic could be something like: "pick the pair of elements ($x\_1$,$x\_2$) from $X$ such that $x\_1 + x\_2$ is as close to zero as possible, and set $X' =\{x\_1, x\_2\}$ as the initial state". To apply this heuristic you will need to initially check $n(n-1)$ subsets of pairs. If this is not a solution, it will hopefully be very close to the solution in the state space and therefore a good place to start.
  
  Another problem is the hill climbing does not remember previously visited states, and you could end up infinitely looping when you allow moves to both add and delete elements from $X'$. For example, suppose $X'=\{1\},X=\{-3,-50,-50,100\}$. Clearly the optimal solution is $X''=\{-50,-50,100\}$ but your method will add element $-3$ to $X'$ first, then remove $-3$, then pick $-3$ again etc, because these states have a lower objective value than any state with one of $-50$ or $100$ in it. So I think you need to use a more sophisticated approach that prevents visiting the same state twice.
  
  
  ---
  
  