Students:
Ana Carmen Estrada Real A01748866
Jesús Leopoldo Llano García A01748867
Cody Eduardo Evans Trajo A01207043
a) Choose a solution method from the metaheuristics of Ant System, Bees Algorithm, and Particle Swarm Optimization.
We chose the bees algorithm.
b) Document your solution by specifying: i) How do you describe and codify the solutions and how will you represent them in Python for the chosen method?
We represent the initial board (from 0's and 1's) to '#' and '-', then we generate the random bees (n) (every bee is a list of locations for the sensors)and evaluate the solutions. We define the selected bees (m), the elite bees (e), and how many neighbors each will have. The size of the neighborhood for those bees is defined as choosing only one sensor from the selected bee (or elite) with random and move just that sensor to a random place. We evaluate the new bees from each place, choose the best ones, assign them to a new list and generate the remaining scouts with random again. All of this inside of a for depending on the amount of generations we want. Finaly we select the best bee after all the iterations and print it.
ii) How do you generate the initial solutions?
With the function rand_bees, we generate lists of random locations. The only restriction for the locations is that the sensors should be inside the board, so it takes into account the size of every sensor.
iii) How are the new solutions generated from the current solutions during the execution of the method? iv) How do you evaluate the solutions you want to optimize?
We place the sensors in the board, with the function eval_mat and count the empty spaces, then add a minus sign and choose the max values.
c) Modify the Python code provided to solve the problem. Document it internally with Python comments. Indicate how to run it.
d) You must experiment with different values for the parameters required by the chosen metaheuristic, trying to find appropriate values to solve the problem. Summarize the results of the experiments.
import matplotlib.pyplot as plt
import numpy as np
import random as r
## A Function to copy the grid
def copy(grid):
init_grid = []
for row in grid:
temp_row =[]
for elem in row:
temp_row.append(elem)
init_grid.append(temp_row)
return init_grid
## A Function to evaluate the board with sensors, we count empty spaces and add a minus to maximize it
def eval_num(grid):
X=0
for j in range (0, len(grid)):
for k in range (0, len(grid[j])):
if grid [j][k] == '-':
X=X+1
return -X
## For printing the grid
def printmat(grid):
for i in range(len(grid)):
for j in range(len(grid)):
print(grid[i][j], end=" ")
print()
## To get the initial grid from 0,1 to '#' and '-'
def initial_grid(grid):
init_grid = copy(grid)
for i in range(len(grid)):
for j in range(len(grid)):
if grid[i][j] == 1:
init_grid[i][j] ='-'
else:
init_grid[i][j] ='#'
return init_grid
## Turn the coordinates of the sensors to boards we can evaluate
def eval_mat(grid, sensors_range, locations):
for i in range(0, len(sensors_range)):
sensor_size = sensors_range[i]
for j in range (0, len(grid)):
for k in range (0, len(grid[j])):
g = [j,k]
#print (g)
if np.all(np.asarray(locations[i]) == np.asarray(g)):
rng = sensors_range [i]
for n in range (0, rng):
for m in range (0, rng):
if grid [j+m][k] == '-':
grid [j+m][k] = i+1
if grid [j+m][k+n] == '-':
grid [j+m][k+n] = i+1
if grid [j][k+n] == '-':
grid [j][k+n] = i+1
return grid
## Generate random bees
def rand_bees(num):
r.seed()
init_bees = []
for i in range(num):
bees = []
for j in range(len(sensors_range)):
bees.append([r.randint(0, 5-sensors_range[j]), r.randint(0, 5-sensors_range[j])])
init_bees.append(bees)
#print(init_bees)
return init_bees
## Evaluate the bees
def eval_bees(grid, sensors, bees):
ev_bees = []
for i in range(len(bees)):
sgrid = copy(init_grid)
#printmat(eval_mat(sgrid, sensors_range, init_bees[i]))
ev_bees.append(eval_num(eval_mat(sgrid, sensors_range, init_bees[i])))
#print()
#print(ev_bees)
return ev_bees
## Choose m selected bees
def selec_bees(num, ev_bees, current_bees):
m=num
best_bees = []
best_sites = []
bees = ev_bees.copy()
old_bees = current_bees.copy()
for j in range(m):
best_sites.append(max(bees))
k = bees.index(max(bees))
best_bees.append(old_bees[k])
del bees[k]
del old_bees[k]
#print(best_bees)
return best_sites, best_bees
## Elite bees
def elite_bees(num, ev_bees, current_bees):
e = num
best_bees_e = []
best_sites_e = []
bees_e = ev_bees.copy()
old_bees1 = current_bees.copy()
for j in range(e):
best_sites_e.append(max(bees_e))
k = bees_e.index(max(bees_e))
best_bees_e.append(old_bees1[k])
del bees_e[k]
del old_bees1[k]
#print(best_bees_e, k, ev_bees, bees_e)
return best_bees_e
## The good bees are the rest of the selected but not elite
def good_bees(num, sites, select_bees):
sel=num
best_bees_se = []
best_sites_se = []
bees_se = sites.copy()
old_best = select_bees.copy()
for j in range(sel):
best_sites_se.append(min(bees_se))
k = bees_se.index(min(bees_se))
best_bees_se.append(old_best[k])
del bees_se[k]
del old_best[k]
#print(best_bees_se)
return best_bees_se
## Generate the neighbors of the elite bees
def neig_elite(e, n2, elite_bees, sensors_range):
rand_bees_elite = []
for j in range(n2+1):
for i in range(e):
rand_bees_elite.append(elite_bees[i])
for i in range(2, len(rand_bees_elite)):
sens = r.randint(0, 3)
rand_bees_elite[i][sens]=[r.randint(0, 5-sensors_range[sens]), r.randint(0, 5 -sensors_range[sens])]
#print(rand_bees_elite)
return rand_bees_elite
## Generate the neighbors of the good bees
def neig_good(g, n1, other_bees, sensors_range):
rand_bees_sel = []
for j in range(n1+1):
for i in range(g):
rand_bees_sel.append(other_bees[i])
for i in range(2, len(rand_bees_sel)):
sens = r.randint(0, len(sensors_range)-1)
rand_bees_sel[i][sens]=[r.randint(0, 5-sensors_range[sens]), r.randint(0, 5-sensors_range[sens])]
#print(rand_bees_sel)
return rand_bees_sel
## New list of scouts
def new_scouts(new_bees, elite_best, good_best):
new_bee=new_bees.copy()
for i in range(len(elite_best)):
new_bee.append(elite_best[i])
for j in range(len(good_best)):
new_bee.append(good_best[j])
#print(new_bee)
return new_bee
## Get the final best bee
def best_bee(grid, ev_bees, current_bees, sensors_range):
ev = []
bee = []
ev.append(max(ev_bees))
k = ev.index(max(ev_bees))
bee.append(current_bees[k])
print('Final Best Score and Coordinates of the sensors')
print(ev, bee)
locations = bee
for i in range(0, len(sensors_range)):
sensor_size = sensors_range[i]
for j in range (0, len(grid)):
for k in range (0, len(grid[j])):
g = [j,k]
if np.all(np.asarray(locations[0][i]) == np.asarray(g)):
rng = sensors_range[i]
for n in range (0, rng):
for m in range (0, rng):
if grid [j+m][k] == '-':
grid [j+m][k] = i+1
if grid [j+m][k+n] == '-':
grid [j+m][k+n] = i+1
if grid [j][k+n] == '-':
grid [j][k+n] = i+1
print('Final: Best State')
printmat(grid)
sensors_range = [3,2,4,1]
grid = [[1,1,1,0,1,0], [1,0,0,1,1,1], [0,0,1,1,0,1], [1,1,1,1,1,1], [0,0,0,1,1,1], [1,1,1,1,0,0]]
print('Initial Grid:')
init_grid = initial_grid(grid)
printmat(initial_grid(grid))
print(eval_num(init_grid))
Initial Grid: - - - # - # - # # - - - # # - - # - - - - - - - # # # - - - - - - - # # -24
n = 25
m=10
e=5
g=m-e
n2=4
n1=2
gen=150
init_bees = rand_bees(n)
for i in range(gen):
ev = eval_bees(init_grid, sensors_range, init_bees)
sites, sel_bees = selec_bees(m, ev, init_bees)
sitese, elit_bees = selec_bees(e, ev, init_bees)
other_bees = good_bees(g, sites, sel_bees)
neig_elit = neig_elite(e, n2, elit_bees, sensors_range)
neigh_good = neig_good(g, n1, other_bees, sensors_range)
ev_e = eval_bees(init_grid, sensors_range, neig_elit)
ev_g = eval_bees(init_grid, sensors_range, neigh_good)
sitese, elit_best = selec_bees(e, ev_e, neig_elit)
sitese, good_best = selec_bees(g, ev_g, neigh_good)
new_bees = rand_bees(n-m)
new_scout = new_scouts(new_bees, elit_best, good_best)
init_bees=new_scout
ev_s = eval_bees(init_grid, sensors_range, new_scout)
best_bee(init_grid, ev_s, new_scout, sensors_range)
Final Best Score and Coordinates of the sensors [-9] [[[1, 2], [3, 3], [0, 0], [4, 0]]] Final: Best State 3 3 3 # - # 3 # # 2 1 - # # 1 1 # - 3 1 1 1 1 - # # # 1 2 - - - - - # #
Note: We did not put a restriction for sensors being on top of each other, so there can be more than one in the same place, but we hope the algorithm finds out the best configuration.