Source code for evol.problems.routing.magicsanta

import math
from collections import Counter
from itertools import chain
from typing import List, Union

from evol.helpers.utils import sliding_window
from evol.problems.problem import Problem


[docs]class MagicSanta(Problem): def __init__(self, city_coordinates, home_coordinate, gift_weight=None, sleigh_weight=1): """ This problem is based on this kaggle competition: https://www.kaggle.com/c/santas-stolen-sleigh#evaluation. :param city_coordinates: List of tuples containing city coordinates. :param home_coordinate: Tuple containing coordinate of home base. :param gift_weight: Vector of weights per gift associated with cities. :param sleigh_weight: Weight of the sleight. """ self.coordinates = city_coordinates self.home_coordinate = home_coordinate self.gift_weight = gift_weight if gift_weight is None: self.gift_weight = [1 for _ in city_coordinates] self.sleigh_weight = sleigh_weight
[docs] @staticmethod def distance(coord_a, coord_b): return math.sqrt(sum([(z[0] - z[1]) ** 2 for z in zip(coord_a, coord_b)]))
[docs] def check_solution(self, solution: List[List[int]]): """ Check if the solution for the problem is valid. :param solution: List of lists containing integers representing visited cities. :return: None, unless errors are raised. """ set_visited = set(chain.from_iterable(solution)) set_problem = set(range(len(self.coordinates))) if set_visited != set_problem: missing = set_problem.difference(set_visited) extra = set_visited.difference(set_problem) raise ValueError(f"Not all cities are visited! Missing: {missing} Extra: {extra}") city_counter = Counter(chain.from_iterable(solution)) if max(city_counter.values()) > 1: double_cities = {key for key, value in city_counter.items() if value > 1} raise ValueError(f"Multiple occurrences found for cities: {double_cities}")
[docs] def eval_function(self, solution: List[List[int]]) -> Union[float, int]: """ Calculates the cost of the current solution for the TSP problem. :param solution: List of integers which refer to cities. :return: """ self.check_solution(solution=solution) cost = 0 for route in solution: total_route_weight = sum([self.gift_weight[t] for t in route]) + self.sleigh_weight distance = self.distance(self.home_coordinate, self.coordinates[route[0]]) cost += distance * total_route_weight for t1, t2 in sliding_window(route): total_route_weight -= self.gift_weight[t1] city1 = self.coordinates[t1] city2 = self.coordinates[t2] cost += self.distance(city1, city2) * total_route_weight last_leg_distance = self.distance(self.coordinates[route[-1]], self.home_coordinate) cost += self.sleigh_weight * last_leg_distance return cost