import json import math import random from tour import Tour def euclidean_distance(pt1, pt2): return math.sqrt((pt1[0] - pt2[0]) ** 2 + (pt1[1] - pt2[1]) ** 2) def generate_matchings(L): if len(L) == 0: yield [] for (index, i2) in enumerate(L[1:]): for other_part in generate_matchings( [L[ind] for ind in range(1, len(L)) if ind != index + 1] ): yield [(L[0], i2)] + other_part def one_random_matching(L): match = [] L = list(L) while len(L) > 0: ind1 = random.randint(0, len(L) - 1) pt1 = L.pop(ind1) ind2 = random.randint(0, len(L) - 1) pt2 = L.pop(ind2) match.append([pt1, pt2]) return match class TSP: def __init__(self, cities): self.cities = list(map(tuple, cities)) @staticmethod def random_cities(N): return [ (round(random.random(), 2), round(random.random(), 2)) for _ in range(N) ] @staticmethod def from_file(file_name): return TSP(json.loads(open(file_name, "r").read())) def score(self, tour): return sum(euclidean_distance(v1, v2) for (v1, v2) in tour.edges.items()) def tweak(self): pass def random_tour(self): vertices_left = set(self.cities) edges = dict() source = random.sample(vertices_left, 1)[0] start = source vertices_left.remove(source) while len(vertices_left) > 0: sink = random.sample(vertices_left, 1)[0] vertices_left.remove(sink) edges[source] = sink source = sink edges[source] = start return Tour(edges) def random_grasp_tour(self, alpha): """ pick a random greedyish tour for the GRASP metaheuristic at each step, we look at the distance to all possible next cities, then we pick randomly from those that add a distance <= c, where c = min + alpha * (max - min) """ vertices_left = set(self.cities) edges = dict() source = random.sample(vertices_left, 1)[0] start = source vertices_left.remove(source) while len(vertices_left) > 0: dist_dict = { city: euclidean_distance(source, city) for city in vertices_left } c_max = max(dist_dict.values()) c_min = min(dist_dict.values()) cutoff = c_min + alpha * (c_max - c_min) sink = random.choice([c for c in vertices_left if dist_dict[c] <= cutoff]) vertices_left.remove(sink) edges[source] = sink source = sink edges[source] = start return Tour(edges) def k_opt(self, tour, k, try_only_random_matching=False): # print("starting with: ",tour.edges) vertices = list(tour.edges.keys()) sources_to_break = random.sample(vertices, k) sinks_to_break = [tour.edges[v] for v in sources_to_break] # print("sources:",sources_to_break) # print("sinks:",sinks_to_break) partial_edges = tour.edges.copy() score_loss = sum( euclidean_distance(source, partial_edges[source]) for source in sources_to_break ) for source in sources_to_break: del partial_edges[source] open_vertices = sources_to_break + sinks_to_break if try_only_random_matching: matchings = [one_random_matching(open_vertices)] else: matchings = list(generate_matchings(open_vertices)) best_score_change = None best_edges = None while len(matchings) > 0: matching = matchings.pop(0) score_gain = sum(euclidean_distance(v1, v2) for (v1, v2) in matching) # print("matching: ", matching) edge_list = list(partial_edges.items()) edge_list += matching # print("edge list: ", edge_list) # we now have a bunch of pairs (v_i. v_j) that we have to try to # reconstruct into a tour, if possible new_edges = [] active = edge_list[0][0] # print("\tactive =", active) start = active new_edges.append(active) valid_edges = True while len(edge_list) > 0: relevant_edges = [e for e in edge_list if active in e] # print("\trelevant =", relevant_edges) assert len(relevant_edges) > 0 next_vertex = [v for v in relevant_edges[0] if v != active][0] # print("\tnext_vertex =", next_vertex) new_edges.append(next_vertex) active = next_vertex edge_list.remove(relevant_edges[0]) if active == start: # print("done. len =",len(edge_list)) if len(edge_list) > 0: valid_edges = False break valid_one_random = False if valid_edges: score_change = score_gain - score_loss if best_score_change is None or score_change < best_score_change: # print("new best edges =", new_edges) best_score_change = score_change best_edges = new_edges if try_only_random_matching: valid_one_random = True if try_only_random_matching: if valid_one_random: break else: matchings.append(one_random_matching(open_vertices)) new_dict = {} for i in range(len(best_edges) - 1): new_dict[best_edges[i]] = best_edges[i + 1] # new_dict[best_edges[-1]] = best_edges[0] return Tour(new_dict) # , best_score_change @staticmethod def partially_mapped_crossover(tour1, tour2): assert len(tour1.edges) == len(tour2.edges) n = len(tour1.edges) city_list = list(tour1.edges.keys()) # build tours into list form because it will be easier T1 = [random.choice(city_list)] while len(T1) < n: T1.append(tour1.edges[T1[-1]]) T2 = [random.choice(city_list)] while len(T2) < n: T2.append(tour2.edges[T2[-1]]) cutpoints = sorted(random.sample(list(range(n + 1)), 2)) child = [None for _ in range(n)] # copy part between cutpoints from parent #2 into child for index in range(cutpoints[0], cutpoints[1]): child[index] = T2[index] # build the map that fixes duplicates middle_map = {T2[i]: T1[i] for i in range(cutpoints[0], cutpoints[1])} # now try to build the rest from T1 for index in range(n): if index >= cutpoints[0] and index < cutpoints[1]: # we're in the middle, do nothing assert child[index] is not None continue child[index] = T1[index] while child[index] in middle_map: child[index] = middle_map[child[index]] # now child is done, convert back to dict form child_dict = {child[i]: child[i + 1] for i in range(n - 1)} child_dict[child[-1]] = child[0] return Tour(child_dict) @staticmethod def order_crossover(tour1, tour2): assert len(tour1.edges) == len(tour2.edges) n = len(tour1.edges) city_list = list(tour1.edges.keys()) # build tours into list form because it will be easier T1 = [random.choice(city_list)] # T1 = [(1, 1)] while len(T1) < n: T1.append(tour1.edges[T1[-1]]) T2 = [random.choice(city_list)] # T2 = [(1, 1)] while len(T2) < n: T2.append(tour2.edges[T2[-1]]) cutpoints = sorted(random.sample(list(range(n + 1)), 2)) # cutpoints = [3, 6] # print(cutpoints) child = [None for _ in range(n)] # copy part between cutpoints from parent #2 into child for index in range(cutpoints[0], cutpoints[1]): child[index] = T2[index] # print(child) # now we put in entries of T1 in the order they apppear, after the second # cutpoint placement_index = cutpoints[1] % n T1_index = cutpoints[1] % n while any(c is None for c in child): while T1[T1_index] in child: T1_index = (T1_index + 1) % n child[placement_index] = T1[T1_index] placement_index = (placement_index + 1) % n # now child is done, convert back to dict form child_dict = {child[i]: child[i + 1] for i in range(n - 1)} child_dict[child[-1]] = child[0] return Tour(child_dict) @staticmethod def cycle_crossover(tour1, tour2): assert len(tour1.edges) == len(tour2.edges) n = len(tour1.edges) city_list = list(tour1.edges.keys()) # build tours into list form because it will be easier # T1 = [random.choice(city_list)] # T1 = [(1, 1)] T1 = [min(city_list)] while len(T1) < n: T1.append(tour1.edges[T1[-1]]) # T2 = [random.choice(city_list)] T2 = [min(city_list)] while len(T2) < n: T2.append(tour2.edges[T2[-1]]) child = [None for _ in range(n)] while any(c is None for c in child): active_index = min(i for i in range(n) if child[i] is None) # print("new loop: AI=", active_index) if random.randint(0, 1) == 0: active_parent = T1 non_active_parent = T2 else: active_parent = T2 non_active_parent = T1 child[active_index] = active_parent[active_index] # print(f"taking {active_parent[active_index]}") other_entry = non_active_parent[active_index] while other_entry not in child: active_index = active_parent.index(other_entry) child[active_index] = other_entry other_entry = non_active_parent[active_index] # print(active_index) # print(f"taking {other_entry}") # now child is done, convert back to dict form child_dict = {child[i]: child[i + 1] for i in range(n - 1)} child_dict[child[-1]] = child[0] return Tour(child_dict) @staticmethod def graph_partitioning_crossover(tour1, tour2): pass @staticmethod def _graph_partition(tour1, tour2): vertices = set(tour1.edges.values()) print(vertices) cities = set(vertices) checked = set() t1_neighbor_dict = { c: {tour1.edges[c], [k for k in cities if tour1.edges[k] == c][0]} for c in cities } t2_neighbor_dict = { c: {tour2.edges[c], [k for k in cities if tour2.edges[k] == c][0]} for c in cities } components = [] while len(vertices) > 0: # find one component to_check = {vertices.pop()} active_component = [] print("new component") while len(to_check) > 0: active = to_check.pop() print(active) if active in checked: continue checked.add(active) active_component.append(active) if active in vertices: vertices.remove(active) # need to find the neighbors of "active" that # (1) don't go through edges in both tours # (2) ... something about vertices of degree 4??? # I think don't go through them at all? # if active is a vertex of degree 4 itself, we do not go anywhere from # here, it's a dead end if ( len( set(t1_neighbor_dict[active]).union( set(t2_neighbor_dict[active]) ) ) == 4 ): continue # now we want to look at neighbors that are not neighbors of both and # look there as well # find the two cities that "active" points to in tour1, and then # restrict to only those that have not been considered yet t1_neighbors = [ t1n for t1n in t1_neighbor_dict[active] if t1n in vertices ] # find the two cities that "active" points to in tour2, and then # restrict to only those that have not been considered yet t2_neighbors = [ t2n for t2n in t2_neighbor_dict[active] if t2n in vertices ] for N1 in t1_neighbors: if N1 not in t2_neighbors: # allowed to explore N1 as part of this component to_check.add(N1) for N2 in t2_neighbors: if N2 not in t1_neighbors: # allowed to explore N2 as part of this component to_check.add(N2) components.append(active_component) return components