knapsack_meta_heuristic_local_search.py

def remove_duplicate_candidates(N):
    '''
    Accept a list of candidate solutions (being binary lists) and make sure, each (element)-list is contained only once.

    :param N:
    :return: revised list containing no duplicate candidates
    '''
    unique_set = set(tuple(lst) for lst in N)
    unique_list_of_lists = [list(tpl) for tpl in unique_set]
    return unique_list_of_lists


def nb_knapsack(S):
    """
    Calculate the neighborhood of the starting solution S.

    NB: All solutions that arise from S by either
    a) adding an object
    b) removing an object
    c) removing a contained object AND adding a non-contained object

    :param S: Starting solution (list of n binary elements)
    :return: List of lists containing neighboring solutions
    """

    # Variable to collect the neighbor solutions
    N = []

    for i in range(len(S)):
        candidate = S.copy()
        # a),b) Generate all neighbors obtained by adding an object
        candidate[i] = int(not candidate[i])
        N.append(candidate)
    # c) Generate all neighbors obtained by swapping an object
    # first determine 0/1 positions in start solution
    zero_positions = [i for i in range(len(S)) if S[i] == 0]
    one_positions = [i for i in range(len(S)) if S[i] == 1]
    # then loop through all pairwise combinations of 0s/1s
    # and swap 0s/1s
    for zero_idx in zero_positions:
        for one_idx in one_positions:
            # jetzt einen Nachbarn erzeugen, wo 0 in 1 und 1 in 0 umgewandelt wird
            candidate = S.copy()
            candidate[zero_idx] = 1
            candidate[one_idx] = 0
            N.append(candidate)

    N = remove_duplicate_candidates(N)
    return N


def eval_func(S, values):
    '''
    calculate the scalar product of S and values

    :param S: a given solution as binary vector
    :param values: the values-vector to be multiplied with the bin-vector
    :return: the scalar product
    '''
    value = 0
    for i in range(len(S)):
        value = value + S[i] * values[i]
    return value


def local_search_knapsack(S, weights, values, capacity):
    '''
    perform one local search iteration in the neighborhood of the
    solution S

    :param S: Start solution
    :param weights: Weights of the objects of the knapsack problem
    :param values: Values assigned to the knapsack items
    :param capacity: Capacity of the knapsack
    :return: the best solution candidate found in this local search iteration
    '''
    best_solution = S
    best_value = eval_func(S, values)

    # determine the neighborhood of S
    N = nb_knapsack(S)
    print("Neighborhood (", S, ") is: ", N)
    # loop through all candidate solutions
    for candidate in N:
        weight = eval_func(candidate, weights)
        if weight <= capacity:
            # if knapsack capacity not exceeded (valid candidate)
            # evaluate obj. function
            cand_value = eval_func(candidate, values)
            # compare current solution with current best solution
            if cand_value > best_value:
                # found a better candidate: Save candidate in best_solution (for later..)
                best_solution = candidate
                # update best value
                best_value = cand_value

    # return best candidate
    print("Best solution:", best_solution, ", val: ", best_value)
    return best_solution


def meta_heuristic(S, weights, values, capacity):
    '''
    Apply a metaheuristic based on the starting solution S.

    Calls local_search_knapsack multiple times, selecting the best solution as the next starting solution,
    and outputs the local optimum in the end.

    :param S: Starting solution
    :param weights: Weights of the objects in the knapsack problem
    :param values: Values assigned to the knapsack items
    :param capacity: Capacity of the knapsack
    :return: Tuple containing the local optimum and its objective value
    '''
    old_sol = S
    stop_loop = False
    while not stop_loop:
        new_sol = local_search_knapsack(old_sol, weights, values, capacity)
        if new_sol == old_sol:
            stop_loop = True
        old_sol = new_sol

    obj_value = eval_func(new_sol, values)
    return new_sol, obj_value


# Main program
# Knapsack problem definition
S = [0, 1, 1, 0, 0]
weights = [4, 12, 1, 2, 1]
values = [10, 4, 2, 2, 1]
capacity = 15

# print(init_sol)
l_opt, l_val = meta_heuristic(S, weights, values, capacity)
print("Local Optimum: ", l_opt, ", Obj. val:", l_val)