<jupyter_start><jupyter_text><jupyter_code>! pip3 install mlrose

import mlrose
import numpy as np
import matplotlib.pyplot as plt
import timeit<jupyter_output>Collecting mlrose
  Downloading https://files.pythonhosted.org/packages/a0/7f/9b17fb837c2bc5f0482fd0ea4a16a47b91ee53b6e33fb151eae47a956ac4/mlrose-1.1.0-py3-none-any.whl
Requirement already satisfied: scipy in /usr/local/lib/python3.6/dist-packages (from mlrose) (1.1.0)
Requirement already satisfied: sklearn in /usr/local/lib/python3.6/dist-packages (from mlrose) (0.0)
Requirement already satisfied: numpy in /usr/local/lib/python3.6/dist-packages (from mlrose) (1.14.6)
Requirement already satisfied: scikit-learn in /usr/local/lib/python3.6/dist-packages (from sklearn->mlrose) (0.20.2)
Installing collected packages: mlrose
Successfully installed mlrose-1.1.0<jupyter_text>Knapsack Problem======<jupyter_code>weights = [10, 5, 2, 8, 15]
values = [1, 2, 3, 4, 5]
max_weight_pct = 0.6
fitness = mlrose.Knapsack(weights, values, max_weight_pct)
problem = mlrose.DiscreteOpt(length = 5, fitness_fn = fitness,
                         maximize = True, max_val = max(weights))
state = np.array([1, 0, 2, 1, 0])
fitness.evaluate(state)<jupyter_output><empty_output><jupyter_text>Simulated Annealing-------<jupyter_code># Define decay schedules
schedule = mlrose.GeomDecay()
dic = {}

def tune_schedule(schedule):
  fit_scores = []

  for i in range(50):
    best_state, best_fitness = mlrose.simulated_annealing(problem, schedule = schedule,
                                                          max_attempts = 10, max_iters = 1000,
                                                          init_state = state)
    print('Iteration ', str(i))
    print('The best state found is: ', best_state)
    print('The fitness at the best state is: ', best_fitness)
    print('\n')

    fit_scores.append(best_fitness)

  print('The average fitness is '+ str(sum(fit_scores) / 50) + ' for ' + str(schedule) + '.')
  
  return sum(fit_scores) / 50

dic[schedule] = tune_schedule(schedule)
schedule = mlrose.ExpDecay()
dic[schedule] = tune_schedule(schedule) 

print('\n')

schedule = mlrose.ArithDecay()
dic[schedule] = tune_schedule(schedule)
SA_best_schedule = max(dic, key=lambda key: dic[key])

attempts = range(10, 110, 10)

best_score = 0
best_score_index = -1

fit_scores = [0] * len(attempts)

for i, a in enumerate(attempts):
  best_state, best_fitness = mlrose.simulated_annealing(problem, schedule = SA_best_schedule,
                                                        max_attempts = a, max_iters = 1000,
                                                        init_state = state)
#   print('Iteration ', str(i))
#   print('The best state found is: ', best_state)
#   print('The fitness at the best state is: ', best_fitness)
#   print('\n')

  fit_scores[i] = best_fitness

  if best_fitness > best_score:
    best_score = best_fitness
    best_score_index = (i + 1) * 10

plt.plot(fit_scores)

plt.title("Fitness at Various # of Attempts")
plt.xlabel("# (Attempts - 10) / 10")
plt.ylabel("Fitness Score")
plt.show()

print('The maximum fitness score of ' + str(best_score) + ' is obtained in ' + str(best_score_index) + ' attempts.')
SA_best_attempt = best_score_index

iters = range(100, 5000, 100)

def SA_iters(iters, best_schedule, best_attempt):
  best_score = 0
  best_score_index = -1
  
  fit_scores = [0] * len(iters)

  for i, a in enumerate(iters):
    best_state, best_fitness = mlrose.simulated_annealing(problem, schedule = best_schedule,
                                                          max_attempts = best_attempt, max_iters = a,
                                                          init_state = state)
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')

    fit_scores[i] = best_fitness
    
    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = (i + 1) * 100

  plt.plot(fit_scores)

  plt.title("Fitness at Various # of Iterations")
  plt.xlabel("# (Iters - 100) / 100")
  plt.ylabel("Fitness Score")
  plt.show()
  
  print('The maximum fitness score of ' + str(best_score) + ' is obtained in ' + str(best_score_index) + ' iterations.')
  
  return best_score_index, fit_scores

SA_results = SA_iters(iters, SA_best_schedule, SA_best_attempt)

SA_best_iter = SA_results[0]
  
SA_fit_scores = SA_results[1]
# Returns the maximum value  
# with knapsack of W capacity 
def knapSack(W, wt, val, n): 
  
    # dp[i] is going to store maximum  
    # value with knapsack capacity i. 
    dp = [0 for i in range(W + 1)] 
  
    ans = 0
  
    # Fill dp[] using above recursive formula 
    for i in range(W + 1): 
        for j in range(n): 
            if (wt[j] <= i): 
                dp[i] = max(dp[i], dp[i - wt[j]] + val[j]) 
    return dp[W] 
acc_SA_fit_scores = []
SA_times = []

for i in range(5, 13):
  weights = np.random.randint(1, 15, size=i).tolist()
  print('Weights: ', weights)
  
  values = np.array(np.arange(1, i + 1)).tolist()
  print('Values: ', values)
  
  max_weight_pct = 0.6
  fitness = mlrose.Knapsack(weights, values, max_weight_pct)
  
  state = np.random.randint(3, size=i)
  print('Initial State: ', state)
  
  problem = mlrose.DiscreteOpt(length = i, fitness_fn = fitness,
                           maximize = True, max_val =i)
  
  start_time = timeit.default_timer()
    
  best_state, best_fitness = mlrose.simulated_annealing(problem, schedule = SA_best_schedule,
                                                        max_attempts = SA_best_attempt, max_iters = SA_best_iter,
                                                        init_state = state) 
  
  end_time = timeit.default_timer()
  training_time = end_time - start_time
  SA_times.append(training_time)
    
  print('N: ', str(i))
  print('W: ', int(max_weight_pct * sum(weights)))
  print('The best state found is: ', best_state)
  print('The fitness at the best state is: ', best_fitness)
  max_fit = knapSack(int(max_weight_pct * sum(weights)), weights, values, i)
  print('The maximum fitness is: ', max_fit)
  print('\n')
  
  acc_SA_fit_scores.append(best_fitness / max_fit)

  
plt.plot(acc_SA_fit_scores)

plt.title("Fitness at Various # Items")
plt.xlabel("# Items - 5")
plt.ylabel("Fitness Score/Max Fitness")
plt.show()

plt.plot(SA_times)

plt.title("Simulated Annealing Run Time")
plt.xlabel("# Items - 5")
plt.ylabel("Run Time")
plt.show()<jupyter_output>Weights:  [11, 4, 6, 2, 14]
Values:  [1, 2, 3, 4, 5]
Initial State:  [1 0 1 2 2]
N:  5
W:  22
The best state found is:  [0 2 1 4 0]
The fitness at the best state is:  23.0
The maximum fitness is:  44


Weights:  [11, 6, 11, 3, 11, 11]
Values:  [1, 2, 3, 4, 5, 6]
Initial State:  [1 2 0 0 0 1]
N:  6
W:  31
The best state found is:  [0 1 0 5 0 1]
The fitness at the best state is:  28.0
The maximum fitness is:  40


Weights:  [14, 10, 3, 9, 12, 13, 4]
Values:  [1, 2, 3, 4, 5, 6, 7]
Initial State:  [0 0 2 1 1 1 1]
N:  7
W:  39
The best state found is:  [6 5 0 1 2 3 4]
The fitness at the best state is:  0.0
The maximum fitness is:  66


Weights:  [6, 12, 9, 1, 8, 8, 6, 14]
Values:  [1, 2, 3, 4, 5, 6, 7, 8]
Initial State:  [0 2 2 1 2 2 0 2]
N:  8
W:  38
The best state found is:  [0 4 0 3 1 1 0 5]
The fitness at the best state is:  0.0
The maximum fitness is:  152


Weights:  [10, 13, 11, 9, 12, 4, 4, 14, 12]
Values:  [1, 2, 3, 4, 5, 6, 7, 8, 9]
Initial State:  [0 1 1 0 1 1 2 0 1]
N:  9
W:  53[...]<jupyter_text>Genetic Algorithms-------<jupyter_code>weights = [10, 5, 2, 8, 15]
values = [1, 2, 3, 4, 5]
max_weight_pct = 0.6
fitness = mlrose.Knapsack(weights, values, max_weight_pct)

problem = mlrose.DiscreteOpt(length = 5, fitness_fn = fitness,
                         maximize = True, max_val = max(weights))

state = np.array([1, 0, 2, 1, 0])
fitness.evaluate(state)
pop = range(50, 1000, 50)

def tune_pop(pop):
  best_score = 0
  best_score_index = -1
  
  fit_scores = [0] * len(pop)

  for i, a in enumerate(pop):
    best_state, best_fitness = mlrose.genetic_alg(problem, pop_size=a, mutation_prob=0.1, max_attempts=10, max_iters=np.inf)
    
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')

    fit_scores[i] = best_fitness
    
    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = (i + 1) * 50

  plt.plot(fit_scores)

  plt.title("Fitness at Various Populations")
  plt.xlabel("(Population - 50) / 50")
  plt.ylabel("Fitness Score")
  plt.show()
  
  print('The maximum fitness score of ' + str(best_score) + ' is obtained with population ' + str(best_score_index) + '.')
  
  return best_score_index

optimal_pop = tune_pop(pop)
def tune_rate(optimal_pop):
  rate = 0.01
  
  best_score = 0
  best_score_index = -1
  
  fit_scores = [0] * 20

  for i in range(20):
    best_state, best_fitness = mlrose.genetic_alg(problem, pop_size=optimal_pop, mutation_prob=rate, max_attempts=10, max_iters=np.inf)
    
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')

    fit_scores[i] = best_fitness
    
    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = i * 0.05
      
    rate += 0.05

  plt.plot(fit_scores)

  plt.title("Fitness at Various Rates of Mutation")
  plt.xlabel("Rate * 20")
  plt.ylabel("Fitness Score")
  plt.show()
  
  print('The maximum fitness score of ' + str(best_score) + ' is obtained with mutation rate ' + str(best_score_index) + '.')
  
  return best_score_index

optimal_rate = tune_rate(optimal_pop)
def GA_tune_attempts(optimal_pop, optimal_rate):

  attempts = range(10, 110, 10)
  
  best_score = 0
  best_score_index = -1
  
  fit_scores = [0] * len(attempts)

  for i, a in enumerate(attempts):
    best_state, best_fitness = mlrose.genetic_alg(problem, pop_size=optimal_pop, mutation_prob=optimal_rate, max_attempts=a, max_iters=np.inf)
    
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')
  
    fit_scores[i] = best_fitness

    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = (i + 1) * 10

  plt.plot(fit_scores)

  plt.title("Fitness at Various # of Attempts")
  plt.xlabel("# (Attempts - 10) / 10")
  plt.ylabel("Fitness Score")
  plt.show()

  print('The maximum fitness score of ' + str(best_score) + ' is obtained in ' + str(best_score_index) + ' attempts.')
  
  return best_score_index

optimal_attempt = GA_tune_attempts(optimal_pop, optimal_rate)
def GA_iters(optimal_pop, optimal_rate, optimal_attempt):
  best_score = 0
  best_score_index = -1
  
  iters = range(100, 5000, 100)
  
  fit_scores = [0] * len(iters)

  for i, a in enumerate(iters):
    best_state, best_fitness = mlrose.genetic_alg(problem, pop_size=optimal_pop, mutation_prob=optimal_rate, max_attempts=optimal_attempt, max_iters=a)

  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')

    fit_scores[i] = best_fitness
    
    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = (i + 1) * 100

  plt.plot(fit_scores)

  plt.title("Fitness at Various # of Iterations")
  plt.xlabel("# (Iters - 100) / 100")
  plt.ylabel("Fitness Score")
  plt.show()
  
  print('The maximum fitness score of ' + str(best_score) + ' is obtained in ' + str(best_score_index) + ' iterations.')
  
  return best_score_index, fit_scores

GA_best_iter, GA_fit_scores = GA_iters(optimal_pop, optimal_rate, optimal_attempt)
acc_GA_fit_scores = []
GA_times = []

for i in range(5, 13):
  weights = np.random.randint(1, 15, size=i).tolist()
  print('Weights: ', weights)
  
  values = np.array(np.arange(1, i + 1)).tolist()
  print('Values: ', values)
  
  max_weight_pct = 0.6
  fitness = mlrose.Knapsack(weights, values, max_weight_pct)
  
  state = np.random.randint(3, size=i)
  print('Initial State: ', state)
  
  problem = mlrose.DiscreteOpt(length = i, fitness_fn = fitness,
                           maximize = True, max_val=i)
  
  start_time = timeit.default_timer()
    
  best_state, best_fitness = mlrose.genetic_alg(problem, pop_size=optimal_pop, mutation_prob=optimal_rate, max_attempts=optimal_attempt, max_iters=GA_best_iter)
  
  end_time = timeit.default_timer()
  training_time = end_time - start_time
  GA_times.append(training_time)
    
  print('N: ', str(i))
  print('W: ', int(max_weight_pct * sum(weights)))
  print('The best state found is: ', best_state)
  print('The fitness at the best state is: ', best_fitness)
  max_fit = knapSack(int(max_weight_pct * sum(weights)), weights, values, i)
  print('The maximum fitness is: ', max_fit)
  print('\n')
  
  acc_GA_fit_scores.append(best_fitness / max_fit)

  
plt.plot(acc_GA_fit_scores)

plt.title("Fitness at Various # Items")
plt.xlabel("# Items - 5")
plt.ylabel("Fitness Score/Max Fitness")
plt.show()

plt.plot(GA_times)

plt.title("Genetic Algorithm Run Time")
plt.xlabel("# Items - 5")
plt.ylabel("Run Time")
plt.show()<jupyter_output>Weights:  [6, 2, 12, 10, 1]
Values:  [1, 2, 3, 4, 5]
Initial State:  [1 0 1 0 0]
N:  5
W:  18
The best state found is:  [1 4 0 0 4]
The fitness at the best state is:  29.0
The maximum fitness is:  90


Weights:  [12, 8, 3, 10, 7, 10]
Values:  [1, 2, 3, 4, 5, 6]
Initial State:  [1 0 2 2 1 2]
N:  6
W:  30
The best state found is:  [0 0 5 0 2 0]
The fitness at the best state is:  25.0
The maximum fitness is:  30


Weights:  [6, 10, 8, 1, 8, 9, 3]
Values:  [1, 2, 3, 4, 5, 6, 7]
Initial State:  [0 2 1 2 1 2 1]
N:  7
W:  27
The best state found is:  [0 0 0 6 0 0 6]
The fitness at the best state is:  66.0
The maximum fitness is:  108


Weights:  [12, 7, 11, 3, 13, 9, 8, 11]
Values:  [1, 2, 3, 4, 5, 6, 7, 8]
Initial State:  [1 0 1 0 1 2 1 2]
N:  8
W:  44
The best state found is:  [0 0 0 7 0 0 3 0]
The fitness at the best state is:  49.0
The maximum fitness is:  56


Weights:  [6, 4, 4, 13, 1, 1, 10, 8, 5]
Values:  [1, 2, 3, 4, 5, 6, 7, 8, 9]
Initial State:  [1 2 0 2 2 1 1 2 1]
N:  9
W:  31
The[...]<jupyter_text>MIMIC-----<jupyter_code>weights = [10, 5, 2, 8, 15]
values = [1, 2, 3, 4, 5]
max_weight_pct = 0.6
fitness = mlrose.Knapsack(weights, values, max_weight_pct)

problem = mlrose.DiscreteOpt(length = 5, fitness_fn = fitness,
                         maximize = True, max_val = 5)

state = np.array([1, 0, 2, 1, 0])
fitness.evaluate(state)
pop = range(50, 1000, 50)

def MIMIC_tune_pop(pop):
  best_score = 0
  best_score_index = -1
  
  fit_scores = [0] * len(pop)

  for i, a in enumerate(pop):
    best_state, best_fitness = mlrose.mimic(problem, pop_size=a, keep_pct=0.2, max_attempts=10,
          max_iters=np.inf)
    
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')

    fit_scores[i] = best_fitness
    
    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = (i + 1) * 50

  plt.plot(fit_scores)

  plt.title("Fitness at Various Populations")
  plt.xlabel("(Population - 50) / 50")
  plt.ylabel("Fitness Score")
  plt.show()
  
  print('The maximum fitness score of ' + str(best_score) + ' is obtained with population ' + str(best_score_index) + '.')
  
  return best_score_index

MIMIC_optimal_pop = MIMIC_tune_pop(pop)
def MIMIC_tune_rate(optimal_pop):
  rate = 0.01
  
  best_score = 0
  best_score_index = -1
  
  fit_scores = [0] * 20

  for i in range(20):
    best_state, best_fitness = mlrose.mimic(problem, pop_size=optimal_pop, keep_pct=rate, max_attempts=10,
          max_iters=np.inf)
    
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')

    fit_scores[i] = best_fitness
    
    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = i * 0.05
      
    rate += 0.05

  plt.plot(fit_scores)

  plt.title("Fitness at Various Proportion of Samples Kept")
  plt.xlabel("Rate * 20")
  plt.ylabel("Fitness Score")
  plt.show()
  
  print('The maximum fitness score of ' + str(best_score) + ' is obtained with ' + str(best_score_index) + ' proportion samples kept.')
  
  
  return best_score_index

MIMIC_optimal_rate = MIMIC_tune_rate(MIMIC_optimal_pop)
def MIMIC_tune_attempts(optimal_pop, optimal_rate):

  attempts = range(10, 110, 10)
  
  best_score = 0
  best_score_index = -1
  
  fit_scores = [0] * len(attempts)

  for i, a in enumerate(attempts):
    best_state, best_fitness = mlrose.mimic(problem, pop_size=optimal_pop, keep_pct=optimal_rate, max_attempts=a,
          max_iters=np.inf)  
    
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')
  
    fit_scores[i] = best_fitness

    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = (i + 1) * 10

  plt.plot(fit_scores)

  plt.title("Fitness at Various # of Attempts")
  plt.xlabel("# (Attempts - 10) / 10")
  plt.ylabel("Fitness Score")
  plt.show()

  print('The maximum fitness score of ' + str(best_score) + ' is obtained in ' + str(best_score_index) + ' attempts.')
  
    
  return best_score_index

MIMIC_optimal_attempt = MIMIC_tune_attempts(MIMIC_optimal_pop, MIMIC_optimal_rate)
def MIMIC_iters(optimal_pop, optimal_rate, optimal_attempt):
  best_score = 0
  best_score_index = -1
  
  iters = range(100, 5000, 100)
  
  fit_scores = [0] * len(iters)

  for i, a in enumerate(iters):
    best_state, best_fitness = mlrose.mimic(problem, pop_size=optimal_pop, keep_pct=optimal_rate, max_attempts=optimal_attempt,
          max_iters=a) 
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')

    fit_scores[i] = best_fitness
    
    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = (i + 1) * 100

  plt.plot(fit_scores)

  plt.title("Fitness at Various # of Iterations")
  plt.xlabel("# (Iters - 100) / 100")
  plt.ylabel("Fitness Score")
  plt.show()
  
  print('The maximum fitness score of ' + str(best_score) + ' is obtained in ' + str(best_score_index) + ' iterations.')
  
  return best_score_index, fit_scores

MIMIC_best_iter, MIMIC_fit_scores = MIMIC_iters(MIMIC_optimal_pop, MIMIC_optimal_rate, MIMIC_optimal_attempt)
acc_MIMIC_fit_scores = []
MIMIC_times = []

for i in range(5, 13):
  weights = np.random.randint(1, 15, size=i).tolist()
  print('Weights: ', weights)
  
  values = np.array(np.arange(1, i + 1)).tolist()
  print('Values: ', values)
  
  max_weight_pct = 0.6
  fitness = mlrose.Knapsack(weights, values, max_weight_pct)
  
  state = np.random.randint(3, size=i)
  print('Initial State: ', state)
  
  problem = mlrose.DiscreteOpt(length = i, fitness_fn = fitness,
                           maximize = True, max_val = i)
  
  start_time = timeit.default_timer()
    
  best_state, best_fitness = mlrose.mimic(problem, pop_size=optimal_pop, keep_pct=optimal_rate, max_attempts=optimal_attempt,
        max_iters=MIMIC_best_iter) 
  
  end_time = timeit.default_timer()
  training_time = end_time - start_time
  MIMIC_times.append(training_time)
    
  print('N: ', str(i))
  print('W: ', int(max_weight_pct * sum(weights)))
  print('The best state found is: ', best_state)
  print('The fitness at the best state is: ', best_fitness)
  max_fit = knapSack(int(max_weight_pct * sum(weights)), weights, values, i)
  print('The maximum fitness is: ', max_fit)
  print('\n')
  
  acc_MIMIC_fit_scores.append(best_fitness / max_fit)

  
plt.plot(acc_MIMIC_fit_scores)

plt.title("Fitness at Various # Items")
plt.xlabel("# Items - 5")
plt.ylabel("Fitness Score/Max Fitness")
plt.show()

plt.plot(MIMIC_times)

plt.title("MIMIC Run Time")
plt.xlabel("# Items - 5")
plt.ylabel("Run Time")
plt.show()<jupyter_output>Weights:  [6, 6, 11, 13, 11]
Values:  [1, 2, 3, 4, 5]
Initial State:  [1 2 0 0 2]
N:  5
W:  28
The best state found is:  [0 1 0 0 2]
The fitness at the best state is:  12.0
The maximum fitness is:  12


Weights:  [6, 4, 5, 3, 5, 13]
Values:  [1, 2, 3, 4, 5, 6]
Initial State:  [2 0 2 1 1 2]
N:  6
W:  21
The best state found is:  [0 0 0 2 3 0]
The fitness at the best state is:  23.0
The maximum fitness is:  28


Weights:  [6, 7, 6, 11, 3, 1, 2]
Values:  [1, 2, 3, 4, 5, 6, 7]
Initial State:  [1 1 2 0 1 1 0]
N:  7
W:  21
The best state found is:  [1 0 0 0 0 6 4]
The fitness at the best state is:  65.0
The maximum fitness is:  126


Weights:  [3, 1, 9, 10, 10, 7, 2, 7]
Values:  [1, 2, 3, 4, 5, 6, 7, 8]
Initial State:  [2 2 2 2 0 0 0 2]
N:  8
W:  29
The best state found is:  [1 3 0 7 0 1 5 6]
The fitness at the best state is:  0.0
The maximum fitness is:  100


Weights:  [8, 11, 3, 1, 3, 9, 5, 6, 12]
Values:  [1, 2, 3, 4, 5, 6, 7, 8, 9]
Initial State:  [1 2 2 2 1 2 1 2 2]
N:  9
W:  34
The be[...]<jupyter_text>Randomized Hill Climbing-----<jupyter_code>weights = [10, 5, 2, 8, 15]
values = [1, 2, 3, 4, 5]
max_weight_pct = 0.6
fitness = mlrose.Knapsack(weights, values, max_weight_pct)

problem = mlrose.DiscreteOpt(length = 5, fitness_fn = fitness,
                         maximize = True, max_val = 5)

state = np.array([1, 0, 2, 1, 0])
fitness.evaluate(state)
restarts = range(0, 500, 5)

def tune_restarts(restarts):
  best_score = 0
  best_score_index = -1
  
  fit_scores = [0] * len(restarts)

  for i, a in enumerate(restarts):
    best_state, best_fitness = mlrose.random_hill_climb(problem, max_attempts=10, max_iters=np.inf, restarts=a,
                      init_state=state)
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')

    fit_scores[i] = best_fitness
    
    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = i * 5

  plt.plot(fit_scores)

  plt.title("Fitness at Various # Restarts")
  plt.xlabel("# Restarts / 5")
  plt.ylabel("Fitness Score")
  plt.show()
  
  print('The maximum fitness score of ' + str(best_score) + ' is obtained with ' + str(best_score_index) + ' restarts.')
  
  return best_score_index

optimal_restarts = tune_restarts(restarts)

def RHC_tune_attempts(optimal_restarts):

  attempts = range(10, 110, 10)
  
  best_score = 0
  best_score_index = -1
  
  fit_scores = [0] * len(attempts)

  for i, a in enumerate(attempts):
    best_state, best_fitness = mlrose.random_hill_climb(problem, max_attempts=a, max_iters=np.inf, restarts=optimal_restarts,
                      init_state=state)
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')
  
    fit_scores[i] = best_fitness

    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = (i + 1) * 10

  plt.plot(fit_scores)

  plt.title("Fitness at Various # of Attempts")
  plt.xlabel("# (Attempts - 10) / 10")
  plt.ylabel("Fitness Score")
  plt.show()

  print('The maximum fitness score of ' + str(best_score) + ' is obtained in ' + str(best_score_index) + ' attempts.')
  
  return best_score_index

RHC_optimal_attempt = RHC_tune_attempts(optimal_restarts)
def RHC_iters(optimal_restarts, optimal_attempt):
  best_score = 0
  best_score_index = -1
  
  iters = range(100, 5000, 100)
  
  fit_scores = [0] * len(iters)

  for i, a in enumerate(iters):
    best_state, best_fitness = mlrose.random_hill_climb(problem, max_attempts=optimal_attempt, max_iters=a, restarts=optimal_restarts,
                      init_state=state) 
  #   print('Iteration ', str(i))
  #   print('The best state found is: ', best_state)
  #   print('The fitness at the best state is: ', best_fitness)
  #   print('\n')

    fit_scores[i] = best_fitness
    
    if best_fitness > best_score:
      best_score = best_fitness
      best_score_index = (i + 1) * 100

  plt.plot(fit_scores)

  plt.title("Fitness at Various # of Iterations")
  plt.xlabel("# (Iters - 100) / 100")
  plt.ylabel("Fitness Score")
  plt.show()
  
  print('The maximum fitness score of ' + str(best_score) + ' is obtained in ' + str(best_score_index) + ' iterations.')
  
  return best_score_index, fit_scores

RHC_best_iter, RHC_fit_scores = RHC_iters(optimal_restarts, RHC_optimal_attempt)
acc_RHC_fit_scores = []
RHC_times = []

for i in range(5, 13):
  weights = np.random.randint(1, 15, size=i).tolist()
  print('Weights: ', weights)
  
  values = np.array(np.arange(1, i + 1)).tolist()
  print('Values: ', values)
  
  max_weight_pct = 0.6
  fitness = mlrose.Knapsack(weights, values, max_weight_pct)
  
  state = np.random.randint(3, size=i)
  print('Initial State: ', state)
  
  problem = mlrose.DiscreteOpt(length = i, fitness_fn = fitness,
                           maximize = True, max_val = i)
  
  start_time = timeit.default_timer()
    
  best_state, best_fitness = mlrose.random_hill_climb(problem, max_attempts=optimal_attempt, max_iters=RHC_best_iter, restarts=optimal_restarts,
                    init_state=state) 
  
  end_time = timeit.default_timer()
  training_time = end_time - start_time
  RHC_times.append(training_time)
    
  print('N: ', str(i))
  print('W: ', int(max_weight_pct * sum(weights)))
  print('The best state found is: ', best_state)
  print('The fitness at the best state is: ', best_fitness)
  max_fit = knapSack(int(max_weight_pct * sum(weights)), weights, values, i)
  print('The maximum fitness is: ', max_fit)
  print('\n')
  
  acc_RHC_fit_scores.append(best_fitness / max_fit)

  
plt.plot(acc_RHC_fit_scores)

plt.title("Fitness at Various # Items")
plt.xlabel("# Items - 5")
plt.ylabel("Fitness Score/Max Fitness")
plt.show()

plt.plot(RHC_times)

plt.title("RHC Run Time")
plt.xlabel("# Items - 5")
plt.ylabel("Run Time")
plt.show()<jupyter_output>Weights:  [13, 9, 3, 9, 7]
Values:  [1, 2, 3, 4, 5]
Initial State:  [0 1 0 0 2]
N:  5
W:  24
The best state found is:  [0 1 0 0 2]
The fitness at the best state is:  12.0
The maximum fitness is:  24


Weights:  [13, 10, 14, 14, 1, 11]
Values:  [1, 2, 3, 4, 5, 6]
Initial State:  [2 2 1 2 1 2]
N:  6
W:  37
The best state found is:  [2 2 1 2 1 2]
The fitness at the best state is:  0.0
The maximum fitness is:  185


Weights:  [13, 4, 6, 11, 11, 2, 10]
Values:  [1, 2, 3, 4, 5, 6, 7]
Initial State:  [0 0 1 0 0 0 2]
N:  7
W:  34
The best state found is:  [0 0 1 0 0 4 2]
The fitness at the best state is:  41.0
The maximum fitness is:  102


Weights:  [2, 7, 13, 11, 7, 8, 14, 11]
Values:  [1, 2, 3, 4, 5, 6, 7, 8]
Initial State:  [0 0 0 0 1 2 0 2]
N:  8
W:  43
The best state found is:  [0 0 0 0 2 2 0 1]
The fitness at the best state is:  30.0
The maximum fitness is:  32


Weights:  [4, 6, 12, 11, 5, 13, 14, 10, 7]
Values:  [1, 2, 3, 4, 5, 6, 7, 8, 9]
Initial State:  [1 1 2 1 1 1 0 2 0]
N:  9
W: [...]<jupyter_text>Technique Comparison Plots-----<jupyter_code>def compare_time(SA_times, GA_times, MIMIC_times, RHC_times):
    
    plt.figure()
    plt.title("Search Times")
    plt.xlabel("# Items - 5")
    plt.ylabel("Search Time (s)")
    plt.plot(SA_times, '-', color="b", label="Simulated Annealing")
    plt.plot(GA_times, '-', color="r", label="Genetic Algorithms")
    plt.plot(MIMIC_times, '-', color="g", label="MIMIC")
    plt.plot(RHC_times, '-', color="m", label="Randomized Hill Climbing")
    plt.legend(loc="best")
    plt.show()
    
compare_time(SA_times, GA_times, MIMIC_times, RHC_times)
def compare_acc(SA_scores, GA_scores, MIMIC_scores, RHC_scores):
    
    plt.figure()
    plt.title("% Correctly Solved")
    plt.xlabel("# Items - 5")
    plt.ylabel("% Optimal Knapsack Value")
    plt.plot(SA_scores, '-', color="b", label="Simulated Annealing")
    plt.plot(GA_scores, '-', color="r", label="Genetic Algorithms")
    plt.plot(MIMIC_scores, '-', color="g", label="MIMIC")
    plt.plot(RHC_scores, '-', color="m", label="Randomized Hill Climbing")
    plt.legend(loc="best")
    plt.show()
    
compare_acc(acc_SA_fit_scores, acc_GA_fit_scores, acc_MIMIC_fit_scores, acc_RHC_fit_scores)<jupyter_output><empty_output>
StarcoderdataJupyterStructuredCleanDedup