city.py

#!/usr/bin/env python3

from town import TrafficLight
import numpy as np

class City:
    # TODO: input distibution
    # lights ids start from 0 for the streets
    def __init__(self, lights_count, streets, checkpoints=3, capacity=10, lights=None, dist=(2, 1)):
        self.lights = lights if lights else [TrafficLight() for _ in range(lights_count)]
        self.lights_count  = len(self.lights)
        self.dist = dist
        self.map = { index: [None for _ in range(4)] for index in range(lights_count)}
        for (f, to, direction) in streets:
            self.map[f][direction] = (to, [0 for _ in range(checkpoints)])

        self.boundary_lights = [(index, direction) for index in range(self.lights_count)
                                 for direction in range(4) if self.map[index][direction] == None]

    def add_cars(self):
        for index, direction in self.boundary_lights:
            self.lights[index].counters[direction] += max(0, round(np.random.normal(self.dist[0], self.dist[1])))

    def clear_city(self):
        for light in self.lights:
            light.clear_counters()


city = City(4, [(0, 1, 1), (0, 2, 2), (1, 3, 2)])
city.add_cars()
# for light in city.lights:
#     print(light)

print(sum([city.lights[index].counters[direction] for index, direction in city.boundary_lights]) / len(city.boundary_lights))
city.clear_city()
print(sum([city.lights[index].counters[direction] for index, direction in city.boundary_lights]) / len(city.boundary_lights))
# print(city.map)
# for light in city.lights:
#     print(light)

# for light in city.boundary_lights:
#     print(light)

constants.py

""" Our unit of time 1t = 10sec.
"""

""" [ Up, Right, Down, Left ] """

MIN_PERIOD = 3
MAX_PERIOD = 18

""" Ratio of green/red lights """

MIN_RATIO = 10
MAX_RATIO = 90

simulated_annealing.py

import numpy as np
from random import random
class SimulatedAnnealing:
    def __init__(self, initial_temp = 10000, annealing_rate = 0.003):
        self.initial_temp = initial_temp
        self.annealing_rate = annealing_rate

    @staticmethod
    def acc_prob(current, neighbour, temperature):
        return min(1.0, np.exp((current - neighbour) / temperature))



    def optimize(self, estimator, generator, initial_state=None):
        current_state = initial_state if initial_state else generator.generate_random() 
        best_state = current_state
        current_energy = estimator.energy(current_state)
        best_energy = current_energy
        
        temperature = self.initial_temp
        while temperature > 1:
            neighbour_state = generator.generate_neighbour(current_state)
            neighbour_energy = estimator.energy(neighbour_state)

            if self.acc_prob(current_energy, neighbour_energy, temperature) > random():
                current_state = neighbour_state
                current_energy = neighbour_energy

            if current_energy < best_energy:
                best_state = current_state
                best_energy = current_energy


            temperature *= (1 - self.annealing_rate)

        return best_state, best_energy

simulation.py

from copy import deepcopy
from random import randrange
from town import *
import constants

def tweak_parameter(current, left_boundary, right_boundary, deviation):
	range_start = max(left_boundary, current - deviation)
	range_end = min(right_boundary, current + deviation)

	return randrange(range_start, range_end + 1)

def tweak_traffic_light(traffic_light):
	result = deepcopy(traffic_light)

	result.period = tweak_parameter(result.period, constants.MIN_PERIOD, constants.MAX_PERIOD, 4)

	result.ratio = tweak_parameter(result.ratio, constants.MIN_RATIO, constants.MAX_RATIO, 20)
	result.offset = tweak_parameter(result.offset, 0, result.period, result.period // 4)

	return result

class CityGenerator:
	def generate_neighbour(self, current_state):
		neighbour = deepcopy(current_state)
		
		num_lights = neighbour.traffic_lights_count()
		traffic_light_index = randrange(num_lights)

		traffic_light = neighbour.get_traffic_light(traffic_light_index)
		traffic_light = tweak_traffic_light(traffic_light)

		neighbour.set_traffic_light(traffic_light_index, traffic_light)

		return neighbour

	def generate_random(self):
		pass

class CityEstimator:
	def energy(self, starting_state, t_steps=1000):
		current_state = deepcopy(starting_state)		
		current_state.restart_minute_count()

		for t in range(t_steps):
			current_state = current_state.move()

		energy = current_state.total_minute_count()
		return energy

count = 0
for i in range(100000):
	traffic_light = TrafficLight(6, 33, 1)
	tweaked = tweak_traffic_light(traffic_light)
	if (tweaked.offset > 2):
		# print("Period: {}, Ratio: {}, Offset: {}".format(tweaked.period, tweaked.ratio, tweaked.offset))
		count += 1

print(count)


		

town.py

from random import randrange
import constants
class TrafficLight:
	def __init__(self, period=None, ratio=None, offset=None, capacity=10):
		self.period = period if period else randrange(constants.MIN_PERIOD, constants.MAX_PERIOD + 1)
		self.ratio = ratio if ratio else randrange(constants.MIN_RATIO, constants.MAX_RATIO + 1)
		self.offset = offset if offset else randrange(0, self.period + 1)
		self.counters = [0 for _ in range(4)]

	""" returns True iff at time this traffic light shows green on its LEFT - RIGHT axis """
	def traffic_color(self, time):
		reduced = (self.offset + time) % self.period
		green_time = round(self.period * ((self.ratio) / 100))
		return reduced < green_time

	def __str__(self):
		return "Traffic Light: Period={}, Ratio={}, Offset={}, Counters={}".format(self.period, self.ratio, self.offset, self.counters)
		

	def clear_counters(self):
		self.counters = [0 for _ in range(4)]




class City:
	pass


class TrafficCheckpoint:
	pass



# light = TrafficLight()
# light.counters = [i ** 2 for i in range(4)]
# # print(light)
# print (light)
# light.clear_counters()
# print (light)

# for i in range(28):
# 	print("Color == Green == {} for i == {}".format(light.traffic_color(i), i))

traveling_salesman_decoupled.py

import simulated_annealing
from random import shuffle
from random import randrange
from copy import deepcopy


class City:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __sub__(self, other_city):
        delta_x = self.x - other_city.x
        delta_y = self.y - other_city.y
        return (delta_x ** 2 + delta_y ** 2) ** 0.5

    def __str__(self):
        return "{}, {}".format(self.x, self.y)


class Tour:
    def __init__(self, city_list):
        self.city_list = city_list

    def randomize(self):
        shuffle(self.city_list)

    def energy(self):
        distance = 0
        city_list = self.city_list
        for i in range(1, len(city_list)):
            distance += (city_list[i] - city_list[i - 1])

        return distance

    def __str__(self):
        result = ""
        for city in self.city_list:
            result +=  " | " + str(city)

        return result

class TourGenerator:
    def __init__(self, city_list):
        self.city_list = city_list
        self.num_cities = len(city_list)

    def generate_neighbour(self, current_tour):
        proposed_tour = Tour(deepcopy(current_tour.city_list))
        city_a = randrange(self.num_cities)
        city_b = randrange(self.num_cities)

        proposed_tour.city_list[city_a], \
        proposed_tour.city_list[city_b] = proposed_tour.city_list[city_b], proposed_tour.city_list[city_a]

        return proposed_tour

class TourEstimator:
    def energy(self, tour):
        return tour.energy()


if __name__ == "__main__":
    city_coords = [[60, 200],[180, 200],[80, 180],[140, 180],[20, 160],
                   [100, 160],[200, 160],[140, 140],[40, 120],[100, 120],
                   [180, 100],[60, 80],[120, 80],[180, 60],[20, 40],
                   [100, 40],[200, 40],[20, 20],[60, 20],[160, 20]]

    city_list = [City(coords[0], coords[1]) for coords in city_coords]
    start_tour = Tour(city_list)
    start_tour.randomize()
    print("Initial energy: {}".format(start_tour.energy()))

    optimizer = simulated_annealing.SimulatedAnnealing()
    estimator = TourEstimator()
    generator = TourGenerator(city_list)

    best_state, best_energy = optimizer.optimize(estimator, generator, initial_state=start_tour)

    print("Final energy: {}".format(best_energy))