0
$\begingroup$

I need help using the following neighborhood search heuristic on the set S that is partitioned into A and B where A = {1, 2} and B = {3, 4}. This set partition is our initial solution x_0, and the neighborhood of the partition is defined as all partitions that can be obtained by switching an element of A with an element of B.

The Neighborhood Search Heuristic is given as

1: Start with some initial solution x_0

2: Set k=0

3: While There exists x in N(x_k) such that f(x)<= f(x_k) do

4: Set x_(k+1) = argmin {f(x)|x is in N(x_k)

5: Set k=k+1

6: end while

For each iteration, I'd like to show the current solution, the current neighborhood, and the value of each element in the neighborhood. I'd also like to give the value of the result when the heuristic terminates.

However, I have a lot of questions. There is a function f(x) mentioned in the heuristic, but I do not have an f(x) defined. I'm not sure how to proceed in the heuristic with this. Also, if I were to list the neighborhood after each iteration with its value, how would the value change if A and B and those in its neighborhood are still partitions of the set S? I also need to know this before I run the algorithm properly, since I have to choose a minimum.

If I could be walked through one or two iterations of this heuristic, this would be enough for me to understand. Thanks in advance.

$\endgroup$
1
$\begingroup$

Note that in each step of the algorithm, the value of $f(x_k)$ decreases (or in the worst case, stays the same) at each step. This algorithm tries to minimize the value of $f(x)$. So the choice of $f$ depends on what you are searching for.

Example

Let's say you're searching for a partition $x$ of $S=\{1,2,3,4\}$ into two subsets $A$ and $B$ such that the difference between the sums of $A$ and $B$ is minimized. In this case $f$ is simply the absolute value of the difference of the sums.

Initial condition

$$x_0=(\{1,2\},\{3,4\})$$ $$f(x_0)=|(1+2)-(3+4)|=4$$

First step

The neighborhood of $x_0$ consists of four elements, $$(\{3,2\},\{1,4\}), (\{4,2\},\{3,1\}), (\{1,3\},\{2,4\}), (\{1,4\},\{3,2\})$$ with respective scores of 0, 2, 2, and 0. We could select either the first or last element, here I'll take the first: $$x_1=(\{3,2\},\{1,4\})$$

Second step

The neighborhood of $x_1$ consists of four elements, $$(\{1,2\},\{3,4\}), (\{4,2\},\{1,3\}), (\{3,1\},\{2,4\}), (\{3,4\},\{1,2\})$$ with respective scores of 4, 2, 2, and 4. Since none have a score less than or equal to 0, the algorithm terminates.

Note that if you have two neighbors with equal scores, the algorithm above will flip between them endlessly; this can be fixed by changing the $\le$ to a $<$, or by keeping track of $x_{k-1}$ and excluding it from the search.

$\endgroup$
  • $\begingroup$ I appreciate the helpful reply. If I wanted to do the same thing with partitions A and B where A and B each had four elements, would there be 16 elements in the neighborhood? $\endgroup$ – Heath Huffman Oct 28 '14 at 19:45
  • $\begingroup$ @HeathHuffman Yes: for partitions of size n and m, the number of ways we can swap two elements from one to the other is equal to the number of choices for the element from A times the number of choices for the element from B, which is simply nm. $\endgroup$ – 2012rcampion Dec 2 '14 at 8:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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