I made a simulated annealing algorithm to share deficits in groups that fall within the same deficit range. I use range parameters (i.e -170 to -120) to determine the acceptable deficit. I also use a parameter to determine a minimum group size. The point is to get close to the global optimum within those parameters. Ran the script several times and managed to group 100% of my entities. However, with no maximum group size parameter, the script will make huge groups that stray away from theoretically ideal deficits. Indeed, a 188 entities group with a -170 deficit and a 32 entities group with the same deficit both fall within the parameters. Yet, this is not exactly a similar deficit to share given the massive difference in group size.
The groups in red feature this issue
Therefore, I added a maximum group size parameter. However, the script now fails to create any group and remains stuck at 0.0%. The speed of every iteration has also been considerably reduced. This surprises me because the minimum group size does not seem to affect speed. Here is the code with the new parameter. Question is : is this the proper way of implementing this parameter ? Why is it so slow ?
import random
import math
import time
import load_and_clean
from load_and_clean import Vertex
class Parameters:
def __init__(self):
self.num_subgraphs: int = 0
self.target_range: tuple = (0, 0)
self.initial_temperature: float = 0
self.cooling_rate: float = 0
self.max_iterations: int = 0
self.min_groupe_size: int = 0
self.max_group_size: int = 0 # Added parameter
self.revert_rate: float = 0
self.savepath: str = ''
def set_target_range(self, target_range_min, target_range_max):
self.target_range = (min(target_range_min, target_range_max), max(target_range_min, target_range_max))
def is_graph_connected_without(graph, excluded_vertex: Vertex):
visited = set()
def dfs(start_vertex: Vertex):
stack = [start_vertex]
while stack:
vertex = stack.pop()
visited.add(vertex)
for neighbor in vertex.neighbors:
if neighbor != excluded_vertex and neighbor not in visited and neighbor not in stack and neighbor in graph:
stack.append(neighbor)
if 2 >= len(graph):
return True
for vertex in graph:
if vertex != excluded_vertex:
dfs(vertex)
break
# Check if all vertices were visited
for vertex in graph:
if vertex != excluded_vertex and vertex not in visited:
return False
return True
def is_graph_fully_connected(graph: list):
if not graph:
return True
visited = set()
def dfs(start_vertex: Vertex):
stack = [start_vertex]
while stack:
vertex = stack.pop()
visited.add(vertex)
for neighbor in vertex.neighbors:
if neighbor not in visited and neighbor not in stack and neighbor in graph:
stack.append(neighbor)
dfs(graph[0])
for vertex in graph:
if vertex not in visited:
return False
return True
def get_vertexes_that_can_be_removed(subgraph: list):
can_be_removed = set()
for vertex in subgraph:
if is_graph_connected_without(subgraph, vertex):
can_be_removed.add(vertex)
return can_be_removed
def get_vertexes_that_can_be_added(subgraph):
can_be_added = set()
for vertex in subgraph:
for neighbor in vertex.neighbors:
if neighbor not in subgraph:
can_be_added.add(neighbor)
return can_be_added
def initial_solution(vertices, num_subgraphs):
subgraphs = [[] for _ in range(num_subgraphs)]
vertices_left = vertices.copy()
for subgraph in subgraphs:
for i in range( max(1, len(vertices)//num_subgraphs) ):
can_be_added = set(vertices_left)
if subgraph:
can_be_added = get_vertexes_that_can_be_added(subgraph)
can_be_added = can_be_added.intersection( set(vertices_left) )
if not can_be_added:
break
vertex = random.choice( list(can_be_added) )
vertices_left.remove(vertex)
subgraph.append(vertex)
added_new = True
while added_new:
added_new = False
temp_list = vertices_left.copy()
for vertex in temp_list:
random.shuffle(subgraphs)
for subgraph in subgraphs:
if vertex in get_vertexes_that_can_be_added(subgraph):
subgraph.append(vertex)
vertices_left.remove(vertex)
added_new = True
break
if vertices_left:
print('failed to group', len(vertices_left), 'commune(s).')
for vertex in vertices_left:
print(vertex.id_)
else:
print('All communes found a group during initialization')
return subgraphs
def is_subgraph_valid(subgraph: list, params: Parameters):
min_range, max_range = params.target_range
subgraph_sum = sum(vertex.value for vertex in subgraph)
if params.min_groupe_size > len(subgraph) or params.max_group_size < len(subgraph): # Check max group size
return False
return min_range <= subgraph_sum <= max_range
def objective_function(subgraphs, params: Parameters):
valid_coverage = 0
total_vertexes = 0
for i, subgraph in enumerate(subgraphs):
total_vertexes += len(subgraph)
if is_subgraph_valid(subgraph, params):
valid_coverage += len(subgraph)
return 1 - valid_coverage / total_vertexes
def neighbor_solution(subgraphs):
passes = random.randint(1, 20)
for i in range(passes):
subgraph_to_remove_from = random.choice(subgraphs)
subgraph_to_add_to = random.choice(subgraphs)
can_be_removed = get_vertexes_that_can_be_removed(subgraph_to_remove_from)
if not can_be_removed:
continue
if not subgraph_to_add_to:
vertex_to_move = random.choice(list(can_be_removed))
subgraph_to_remove_from.remove(vertex_to_move)
subgraph_to_add_to.append(vertex_to_move)
continue
can_be_added = get_vertexes_that_can_be_added(subgraph_to_add_to)
intersection: set = can_be_removed.intersection(can_be_added)
if not intersection:
continue
vertex_to_move = random.choice(list(intersection))
subgraph_to_remove_from.remove(vertex_to_move)
subgraph_to_add_to.append(vertex_to_move)
def present_group(subgraphs):
for i, subgraph in enumerate(subgraphs):
print(i, len(subgraph), sum(vertex.value for vertex in subgraph))
print()
def copy_subgraphs(subgraphs):
copied_subgraphs = []
for subgraph in subgraphs:
copied_subgraphs.append(subgraph.copy())
return copied_subgraphs
def save_solution(subgraphs: list, filename: str, params: Parameters):
with open(filename, "w") as file:
for group_id, subgraph in enumerate(subgraphs):
if is_subgraph_valid(subgraph, params):
for commune in subgraph:
file.write(f'{commune.id_},{group_id},{group_id}\n')
else:
for commune in subgraph:
file.write(f'{commune.id_},-1,{group_id}\n')
print('saved solution as', filename)
def load_solution(solution_filename: str, graph: list, num_subgraphs) -> list:
subgraphs = {}
communes_added_to_solution = 0
with open(solution_filename, "r") as file:
for line in file.readlines():
line = line.replace('\n', '').split(',')
commune_id = line[0]
group_id = line[2]
if group_id not in subgraphs:
subgraphs[group_id] = []
found = False
for vertice in graph:
if vertice.id_ == commune_id:
subgraphs[group_id].append(vertice)
found = True
communes_added_to_solution += 1
break
if not found:
print('failed to find', commune_id)
if communes_added_to_solution == len(graph):
print('solution grouping perfectly made from', solution_filename)
else:
print('load_solution: failed to put all communes in grouping')
subgraphs = list(subgraphs.values())
subgraphs_dif = num_subgraphs - len(subgraphs)
if subgraphs_dif > 0:
for _ in range(subgraphs_dif):
subgraphs.append([])
elif 0 > subgraphs_dif:
print('number of subgraph desired is inferior to the one loaded from solution file', solution_filename)
return subgraphs
def simulated_annealing(current_solution, params: Parameters):
current_objective = objective_function(current_solution, params)
best_solution = copy_subgraphs(current_solution)
best_objective = current_objective
temperature = params.initial_temperature
for iteration in range(params.max_iterations):
neighbor_solution(current_solution)
neighbor_objective = objective_function(current_solution, params)
delta_objective = neighbor_objective - current_objective
if iteration % 1000 == 0:
print('iteration', iteration, f'best coverage {1 - best_objective}%')
rand_val = random.random()
if delta_objective < 0 or rand_val < math.exp(-delta_objective / temperature):
current_objective = neighbor_objective
if current_objective < best_objective:
best_solution = copy_subgraphs(current_solution)
best_objective = current_objective
save_solution(best_solution, params.savepath + f'{int(time.time())}_{1 - best_objective}.csv', params)
elif params.revert_rate > random.random():
current_solution = copy_subgraphs(best_solution)
temperature *= params.cooling_rate
return best_solution, best_objective
params = Parameters()
params.savepath = ''
params.num_subgraphs = 73
params.set_target_range(-55, -200)
params.min_groupe_size = 13
params.max_group_size = 40 # Set your desired max group size
params.initial_temperature = 1
params.cooling_rate = 0.98
params.max_iterations = 1000000
params.revert_rate = 0.10
xxxxx= load_and_clean.load_regions_from_shapefile('')
xxxxx = load_and_clean.create_graph_from_dataframe(xxxxx['93'])
initial_grouping = initial_solution(xxxxx, params.num_subgraphs)
best_solution, best_objective = simulated_annealing(initial_grouping, params)
for i, subgraph in enumerate(best_solution):
print(f"Subgraph {i}: {[vertex.value for vertex in subgraph]}")
print(f"Objective Value: {best_objective}")```