This algorithm has resemblances with algorithm 1. However, instead of starting each iteration from a completely random solution, the starting solution is a ‘perturbation’ of the current solution. This perturbation is generally stronger than the operator used for hill-climbing. For example, you can use a 2-flip or 3-flip operator for a binary representation, when your hill-climbing uses 1-flip moves. Again you have a parameter num_iter, which determines how many perturbations you will attempt. You need to keep record of the best solution found. This will be the output of the algorithm.

import urllib2  # the lib that handles the url stuff
import numpy as np
import pandas as pd
#from random import randint
import random

input_data = []
url = "http://www.cs.stir.ac.uk/~goc/source/hard200.txt"
data = urllib2.urlopen(url) # it's a file like object and works just like a file
for line in data: # files are iterable
    input_data.append(map(int,line.split()))

instance_number = input_data.pop(0)[0]
max_capacity = input_data.pop()[0]
df = pd.DataFrame(input_data, columns=['no.', 'value', 'weight'])
df.head()
no. value weight
0 1 835 735
1 2 1670 1470
2 3 3340 2940
3 4 1087 987
4 5 1087 987
#function to generate a binary representation of the items selected.
def binrep(n,r):
    return "{0:0{1}b}".format(n, r)
#random.randint(1, 2**instance_number)
weights = np.array(df["weight"])   
values = np.array(df["value"])
best_value = 0
num_inter = 1000 #how many random points we use to initially use for search
n_flip = 2
lst_best_value = []
items_selected = np.array(map(int,binrep(random.randint(1, 2**instance_number), instance_number)))
while num_inter >0:
    max_eval = 1000
    for i in range(0,n_flip):
        idx = random.randint(0,instance_number-1)
        items_selected[idx] = int(not items_selected[idx])
    while max_eval >0:
        total_value = np.dot(values,items_selected)
        total_weight = np.dot(weights,items_selected)
        if total_weight <= max_capacity:
            if total_value > best_value:
                best_value = total_value
                lst_best_value.append(best_value)
        max_eval -=1
    num_inter -= 1
print lst_best_value
print "best value = ",max(lst_best_value)
[124386, 125272, 127014, 127404, 130015, 131189, 131698, 131735]
best value =  131735
%matplotlib inline
import matplotlib.pyplot as plt
plt.plot(list(xrange(0,len(lst_best_value))),lst_best_value)
plt.show
<function matplotlib.pyplot.show>

png

last edited: 01/06/19

Go to top