Skip to content

Instantly share code, notes, and snippets.

@geosteffanov

geosteffanov/city.py

Created February 8, 2018 22:18
Show Gist options
  • Save geosteffanov/45633524ef8f9146adcbeeeb5f5f7f83 to your computer and use it in GitHub Desktop.
Save geosteffanov/45633524ef8f9146adcbeeeb5f5f7f83 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
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)
Raw
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
Raw
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
Raw
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)
Raw
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))
Raw
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))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment