How do I solve the knapsack problem using the hill climbing algorithm?

Question

I need to solve the knapsack problem using hill climbing algorithm (I need to write a program). But I'm clueless about how to do it.

My code should contain a method called knapsack, the method takes two parameters, the first is a 2xN array of integers that represents the items and their weight and value, and the second is an integer that represents the maximum weight of the knapsack. I can assume that the initial state is an empty knapsack, and the actions are either putting objects in the Knapsack or swapping objects from in and out of the knapsack.

score 2 · Answer 1 · answered Mar 05 '19 at 03:48

I think there are at least three points that you need to think before implement Hill-Climbing (HC) algorithm:

First, the initial state. In HC, people usually use a "temporary solution" for the initial state. You can use an empty knapscak, but I prefer to randomly pick items and put it in the knapsack as the initial state. You can use a binary array to save the "pickup status" of each item such that if $a_i=1$ then you pick the $i$-th item and if $a_i=0$ then you don't pick the $i$-th item.

The next is the heuristic function. A function that evaluate your current state. Actually, you can define it freely (like the initial state) as long as the function can evaluate which state is better than the others. You can use a simple one:

$$ h = \begin{cases} -1, & \text{if}\ \sum (w_i \times a_i) > \text{MaxWeight} \\ \sum (v_i \times a_i), & \text{otherwise} \end{cases} $$

with $w_i$ and $v_i$ is the weight and the value of the $i$-th item respectively. One of the disadvantage of this function is if you have more than one invalid state (a state with the total weight is more than the limit), they have the same value, which is $-1$.

The last is the method to generate the neighbors of the current state. Once again, you are also free to define the method that you will use. I think your proposed actions are good enough:

reverse the status of an item (1 to 0 or 0 to 1). That means I add or reduce the item on the current state.
swap the status two items that have different value. Formally swap $a_i$ and $a_j$ with $ i \neq j$ and $ a_i \neq a_j$. That means I swap the item that I picked before with the item that I didn't pick before

Then, after you define everything you can run the algorithm as explained in Wikipedia:

currentNode = startNode;
loop do
    L = NEIGHBORS(currentNode);
    nextEval = -INF;
    nextNode = NULL;
    for all x in L 
        if (EVAL(x) > nextEval)
            nextNode = x;
            nextEval = EVAL(x);
    if nextEval <= EVAL(currentNode)
        //Return current node since no better neighbors exist
        return currentNode;
    currentNode = nextNode;

How do I solve the knapsack problem using the hill climbing algorithm?

1 Answers1