<jupyter_start><jupyter_text>Ant Colony Optimization on Uber Mumbai data<jupyter_code>import pandas as pd
import numpy as np
import seaborn as sns
import matplotlib.pyplot as plt
import json
import networkx as nx
%cd drive/My\ Drive/Datasets/Uber<jupyter_output>/content/drive/My Drive/Datasets/Uber<jupyter_text>Exploratory Data Analysis<jupyter_code>df_hod = pd.read_csv('mumbai-hexclusters-2019-3-OnlyWeekdays-HourlyAggregate.csv')
df_dow = pd.read_csv('mumbai-hexclusters-2019-3-WeeklyAggregate.csv')
id_names =  json.load(open('mumbai_hexclusters.json'))
df_hod.head()
df_dow.head()
sns.heatmap(df_hod.corr(), annot=True, fmt=".2f")
plt.show()
df_hod.hist(column='hod', bins=24)
plt.xlabel('Hour of Day')
plt.ylabel('Count')
plt.title('Uber usage per hour of day')
plt.show()

df_hod.hist(column='mean_travel_time')
plt.xlabel('Travel time (seconds)')
plt.ylabel('Count')
plt.title('Uber trip times')
plt.show()
df_dow.hist(column='dow', bins=7)
plt.xlabel('Day of week')
plt.ylabel('Count')
plt.title('Uber usage per day of the week')
plt.show()

df_dow.hist(column='mean_travel_time')
plt.xlabel('Travel time(seconds)')
plt.ylabel('Count')
plt.title('Uber trip times')
plt.show()
source_deg = dict(df_hod['sourceid'].value_counts())
source_deg = sorted(source_deg.items())
x, y = zip(*source_deg)
plt.plot(x, y)
plt.xlabel('Location ID')
plt.ylabel('Degree')
plt.show()
def get_name(id):
  for hex in id_names['features']:
    if hex['properties']['MOVEMENT_ID'] == str(id):
      return (hex['properties']['DISPLAY_NAME'])
source_deg = sorted(source_deg, key=lambda x: x[1])
print("Most common starting locations: ")
for place in source_deg[:10]:
  name = get_name(place[0])
  if name == "Unnamed Road":
      continue
  print(place[0], name)
dst_deg = dict(df_hod['dstid'].value_counts())
dst_deg = sorted(dst_deg.items())
x, y = zip(*dst_deg)
plt.plot(x, y)
plt.xlabel('location')
plt.ylabel('degree')
plt.show()
dst_deg = sorted(dst_deg, key=lambda x: x[1])
print("Most common destinations: ")
for place in dst_deg[:10]:
  name = get_name(place[0])
  if name == "Unnamed Road":
      continue
  print(place[0], name)<jupyter_output>Most common destinations: 
562 School Rd
331 0, Nandivili Road, Omsai Chawl, <NAME>
543 <NAME>
365 Madh - Marve Rd
478 vipul waykar b401
174 0, Walkeshwar Rd, <NAME>, <NAME><jupyter_text>Implementing Ant Colony Optimization<jupyter_code>import random
import numpy as np

class Graph(object):
    def __init__(self, cost_matrix: list, rank: int):
        self.matrix = cost_matrix
        self.rank = rank
        self.pheromone = [[1 / (rank * rank) for j in range(rank)] for i in range(rank)]


class ACO(object):
    def __init__(self, ant_count: int, generations: int, alpha: float, beta: float, rho: float, q: int,
                 strategy: int):
        self.Q = q
        self.rho = rho
        self.beta = beta
        self.alpha = alpha
        self.ant_count = ant_count
        self.generations = generations
        self.update_strategy = strategy

    def _update_pheromone(self, graph: Graph, ants: list):
        for i, row in enumerate(graph.pheromone):
            for j, col in enumerate(row):
                graph.pheromone[i][j] *= self.rho
                for ant in ants:
                    graph.pheromone[i][j] += ant.pheromone_delta[i][j]

    def solve(self, graph: Graph, verbose: bool = False):
        best_cost = float('inf')
        best_solution = []
        avg_costs = []
        best_costs = []
        for gen in range(self.generations):
            ants = [_Ant(self, graph) for i in range(self.ant_count)]
            curr_cost = []
            for ant in ants:
                for i in range(graph.rank - 1):
                    ant._select_next()
                ant.total_cost += graph.matrix[ant.tabu[-1]][ant.tabu[0]]
                curr_cost.append(ant.total_cost)
                if ant.total_cost < best_cost:
                    best_cost = ant.total_cost
                    best_solution = [] + ant.tabu
                ant._update_pheromone_delta()
            self._update_pheromone(graph, ants)
            best_costs.append(best_cost)
            avg_costs.append(np.mean(curr_cost))
            if verbose:
                print('Generation #{} best cost: {}, avg cost: {}, path: {}'.format(
                    gen+1, best_cost, avg_costs[-1], best_solution))
        return best_solution, best_cost, avg_costs, best_costs


class _Ant(object):
    def __init__(self, aco: ACO, graph: Graph):
        self.colony = aco
        self.graph = graph
        self.total_cost = 0.0
        self.tabu = []
        self.pheromone_delta = []
        self.allowed = [i for i in range(graph.rank)]
        self.eta = [[0 if i == j else 1 / graph.matrix[i][j] for j in range(graph.rank)] for i in range(graph.rank)]
        start = random.randint(0, graph.rank - 1)
        self.tabu.append(start)
        self.current = start
        self.allowed.remove(start)

    def _select_next(self):
        denominator = 0
        for i in self.allowed:
            denominator += self.graph.pheromone[self.current][i] ** self.colony.alpha * self.eta[self.current][i] ** self.colony.beta
        probabilities = [0 for i in range(self.graph.rank)]
        for i in range(self.graph.rank):
            try:
                self.allowed.index(i)
                probabilities[i] = self.graph.pheromone[self.current][i] ** self.colony.alpha * \
                    self.eta[self.current][i] ** self.colony.beta / denominator
            except ValueError:
                pass
        selected = 0
        rand = random.random()
        for i, probability in enumerate(probabilities):
            rand -= probability
            if rand <= 0:
                selected = i
                break
        self.allowed.remove(selected)
        self.tabu.append(selected)
        self.total_cost += self.graph.matrix[self.current][selected]
        self.current = selected

    def _update_pheromone_delta(self):
        self.pheromone_delta = [
            [0 for j in range(self.graph.rank)] for i in range(self.graph.rank)]
        for _ in range(1, len(self.tabu)):
            i = self.tabu[_ - 1]
            j = self.tabu[_]
            if self.colony.update_strategy == 1:
                self.pheromone_delta[i][j] = self.colony.Q
            elif self.colony.update_strategy == 2:
                self.pheromone_delta[i][j] = self.colony.Q / self.graph.matrix[i][j]
            else:
                self.pheromone_delta[i][j] = self.colony.Q / self.total_cost
dow = 5
locations = random.sample(list(df_dow.sourceid.unique()), k=50)
print("Locations:")
for _ in locations:
  print(get_name(_))
df = df_dow.loc[df_dow['dow'] == dow][['sourceid', 'dstid', 'mean_travel_time']]
df = df.loc[df['sourceid'].isin(locations) & df['dstid'].isin(locations)]
df
remapped_locations = { y:x for x,y in enumerate(locations) }
df['sourceid'].replace(remapped_locations, inplace=True)
df['dstid'].replace(remapped_locations, inplace=True)
df
g = nx.from_pandas_edgelist(df, source='sourceid', target='dstid')
nx.draw(g)
max_time = int(df.loc[df['mean_travel_time'].idxmax()]['mean_travel_time'])
cost_matrix = [[ max_time for _ in range(len(locations))] for _ in range(len(locations))]
for index, row in df.iterrows():
  if row['sourceid']==row['dstid']:
    cost_matrix[int(row['sourceid'])][int(row['dstid'])] = 0
    continue
  cost_matrix[int(row['sourceid'])][int(row['dstid'])] = int(row['mean_travel_time'])

print(np.matrix(cost_matrix))
ant_count = 20
alpha = 1.0
beta = 10.0
rho = 0.1
q = 10000
g = 15
aco = ACO(ant_count=ant_count, generations=g, alpha=alpha,beta=beta, rho=rho, q=q, strategy=2)
graph = Graph(cost_matrix, len(locations))
best_path, cost, avg_costs, best_costs = aco.solve(graph, True)
print("Optimal Path: Time=" + str(cost/60/60) +" hours")
def get_key(val): 
    for key, value in remapped_locations.items(): 
         if val == value: 
             return key
for place in best_path:
  print(get_name(get_key(place)))
x_values = [i for i in range(g)]
plt.title("Best Cost vs Generation for " + str(ant_count) + " Ants")
plt.ylabel("Best Cost")
plt.xlabel("Current Generation")
plt.plot(x_values, best_costs)
plt.show()

x_values = [i for i in range(g)]
plt.title("Avg Cost vs Generation for " + str(ant_count) + " Ants")
plt.ylabel("Avg Cost")
plt.xlabel("Current Generation")
plt.plot(x_values, avg_costs)
plt.show()<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.14076003314786315, 'fraction_numerical': 0.01100982597371848, 'mean_word_length': 3.079188797682279, 'pattern_counts': {'":': 2, '<': 17, '<?xml version=': 0, '>': 15, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '3', 'dir': 'jupyter-structured-clean-dedup', 'id': '293257', 'license': 'MIT', 'n_tokens_mistral': 3052, 'n_tokens_neox': 2883, 'n_words': 638, 'path': 'ACO_AI2_1.ipynb', 'repo_name': 'siddhaling/3D-Visualization-Sentiment-Information-and-Classification-using-Combined-Classifier', 'size': '8479'}