Dear Sir,
I am trying to set graph for Ant colony algorithm implementation.
But I am getting Error says :
Traceback (most recent call last):
File "hay4_ACO.py", line 317, in <module>
main()
File "hay4_ACO.py", line 278, in main
aco.set_graph(Objgraph_mat)
File "hay4_ACO.py", line 111, in set_graph
self.size = len(graph)
AttributeError: Graph_mat instance has no attribute '__len__'
Please help me to resolve this issue. I am new bee in this & Some how i have managed to get myself up to this.
Code Is :
import os, sys
import optparse
import subprocess
import random
from Queue import PriorityQueue
import xml.sax
from xml.sax import saxutils, parse, make_parser, handler
from copy import copy
from itertools import *
SUMO_HOME = "/home/dhaval/sumo-1.0.0/"
try:
sys.path.append(os.path.join(SUMO_HOME, "tools"))
# import the library
import sumolib
from sumolib import checkBinary
from sumolib.net import Net
from sumolib.net import NetReader
from sumolib.net import Lane
from sumolib.net import Edge
from sumolib.net import Node
from sumolib.net import Connection
from sumolib.net import Roundabout
except ImportError:
sys.exit("please declare environment variable 'SUMO_HOME' as the root directory of your sumo installation (it should contain folders 'bin', 'tools' and 'docs')")
import random
graph = sumolib.net.readNet('Dijkstra1.net.xml')
import traci
# the port used for communicating with your sumo instance
PORT = 8873
# implementation of an undirected graph using Adjacency Matrix, with weighted or unweighted edges
class Vertex:
def __init__(self, n):
self.name = n
class Graph_mat:
vertices = {}
edges = []
edge_indices = {}
def add_vertex(self, vertex):
if isinstance(vertex, Vertex) and vertex.name not in self.vertices:
self.vertices[vertex.name] = vertex
for row in self.edges:
row.append(0)
self.edges.append([0] * (len(self.edges)+1))
self.edge_indices[vertex.name] = len(self.edge_indices)
return True
else:
return False
def add_edge(self, u, v, weight=1):
if u in self.vertices and v in self.vertices:
self.edges[self.edge_indices[u]][self.edge_indices[v]] = weight
self.edges[self.edge_indices[v]][self.edge_indices[u]] = weight
return True
else:
return False
def print_graph(self):
for v, i in sorted(self.edge_indices.items()):
print(v + ' ')
for j in range(len(self.edges)):
print(self.edges[i][j])
print(' ')
class Ant():
def __init__(self):
self.cost = 0
self.trace = [0]
def start_travel(self):
self.cost = 0
self.trace = [0]
def add_vertex(self, _vertex, _cost):
self.trace.append(_vertex)
self.cost += _cost
def get_position(self):
return self.trace[-1]
def get_cost(self):
return self.cost
def get_path(self):
path = []
for i in range(len(self.trace) - 1):
path.append((self.trace[i], self.trace[i + 1]))
return path
class ACOAlgorithm():
'''
Ant colony optimization algorithms to find shortest path
'''
def __init__(self):
self.evaporation_rate = 0.8
self.threshhold = 0.5
self.remain_path = 0
def set_graph(self, graph):
self.size = len(graph)
self.num_ant = 20*self.size ** 2
self.ant = [Ant() for _ in range(self.num_ant)]
self.distance = graph
self.pheromones = [[1.0]* self.size for _ in range(self.size)]
max_distance = 0
for i in range(len(self.distance)):
for j in range(len(self.distance[0])):
if self.distance[i][j] > max_distance:
max_distance = self.distance[i][j]
for i in range(len(self.distance)):
for j in range(len(self.distance[0])):
if self.distance[i][j] > 0:
self.distance[i][j] /= max_distance*1.0
else:
self.pheromones[i][j] = -1.0
def process(self):
while True:
self._start_travel()
self._find_edge()
if self._finish_travel():
break
for i in range(self.num_ant):
if len(self.ant[i].trace) == self.size:
print 'trace %s' % (self.ant[i].trace)
break
def _start_travel(self):
for i in range(self.num_ant):
self.ant[i].start_travel()
def _find_edge(self):
while not self._have_ant_completed():
for i in range(len(self.ant)):
available_edge = 0
for e in range(self.size):
if e not in self.ant[i].trace and self.pheromones[self.ant[i].get_position()][e] > 0:
available_edge += (2.0 - self.distance[self.ant[i].get_position()][e])*self.pheromones[self.ant[i].get_position()][e]
last_e = -1
prob_edge = 0
prob_random = random.uniform(0.0, 1.0)
for e in range(self.size):
if e not in self.ant[i].trace and self.pheromones[self.ant[i].get_position()][e] > 0:
prob_edge += (2.0 - self.distance[self.ant[i].get_position()][e])*self.pheromones[self.ant[i].get_position()][e]/available_edge
last_e = e
if prob_edge >= prob_random:
break
if last_e >= 0:
self.ant[i].add_vertex(last_e, self.distance[self.ant[i].get_position()][last_e])
else:
self.ant[i].start_travel()
def _finish_travel(self):
# find short path
avg_cost = 0
ant_completed = 0
for i in range(len(self.ant)):
if len(self.ant[i].trace) == self.size:
avg_cost += self.ant[i].get_cost()
ant_completed += 1
avg_cost /= ant_completed
# update pheromones
for i in range(len(self.pheromones)):
for j in range(len(self.pheromones[0])):
if self.pheromones[i][j] > 0:
self.pheromones[i][j] *= (1 - self.evaporation_rate)
for i in range(len(self.ant)):
if self.ant[i].get_cost() < avg_cost:
update_pheromones = self.ant[i].get_path()
for x,y in update_pheromones:
self.pheromones[x][y] += avg_cost/self.ant[i].get_cost()
# remove path has small pheromones
if self.remain_path > 2*(self.size - 1):
for i in range(len(self.pheromones)):
for j in range(len(self.pheromones[0])):
if self.pheromones[i][j] <= self.threshhold:
self.pheromones[i][j] = -1.0
else:
min_pheromones = 999999.99
for i in range(len(self.pheromones)):
for j in range(len(self.pheromones[0])):
if min_pheromones > self.pheromones[i][j] > 0:
min_pheromones = self.pheromones[i][j]
for i in range(len(self.pheromones)):
for j in range(len(self.pheromones[0])):
if self.pheromones[i][j] <= min_pheromones:
self.pheromones[i][j] = -1.0
# check exist only one path
self.remain_path = 0
for i in range(len(self.pheromones)):
for j in range(len(self.pheromones[0])):
if self.pheromones[i][j] > 0:
self.remain_path += 1
return self.remain_path < self.size
def _have_ant_completed(self):
for i in range(len(self.ant)):
if len(self.ant[i].trace) == self.size:
return True
return False
def AntColony(graph, start, end=None):
D = {} # dictionary of final distances
P = {} # dictionary of predecessors
return (D,P)
def shortestPath(graph, start, end):
"""
Find a single shortest path from the given start vertex to the given end vertex.
The input has the same conventions as Dijkstra().
The output is a list of the vertices in order along the shortest path.
"""
start = graph.getEdge(start)
end = graph.getEdge(end)
D,P = AntColony(graph, start, end)
Path = []
#while 1:
# Path.append(end)
# if end == start: break
# end = P[end]
#Path.reverse()
return Path
def generate_routefile():
with open("dijkstra_000.rou.xml", "w") as routes:
print >> routes, """<routes>
<vType id="vehicle1" accel="0.8" decel="4.5" sigma="0.5" length="5" minGap="2.5" maxSpeed="16.67" guiShape="passenger"/>
<route id="1" edges="1 3 5 9" /> </routes>"""
def main():
traci.init(PORT)
Objgraph_mat = Graph_mat()
aco = ACOAlgorithm()
for edge in graph.getEdges():
Objgraph_mat.add_vertex(Vertex(edge.getFromNode().getID()))
Objgraph_mat.add_vertex(Vertex(edge.getToNode().getID()))
for edge in graph.getEdges():
Objgraph_mat.add_edge(edge.getFromNode().getID(), edge.getToNode().getID())
Objgraph_mat.print_graph()
aco.set_graph(Objgraph_mat)
#aco.process()
#route = shortestPath(graph, '1', '18')
#for x in range(len(route)):
# print route[x],
#edges = [str (edge.getID()) for edge in route]
#create the new route for vehicle
#traci.route.add("0", edges)
#assign the new route for vehicle with id vehicle1
#traci.vehicle.add("vehicle0","0")
for i in range(1000): # or whatever nulmber of steps you want to simulate
traci.simulationStep()
traci.close()
sys.stdout.flush()
def get_options():
optParser = optparse.OptionParser()
optParser.add_option("--nogui", action="" default=False, help="run the commandline version of sumo")
options, args = optParser.parse_args()
return options
# this is the main entry point of this script
if __name__ == "__main__":
options = get_options()
# this script has been called from the command line. It will start sumo as a
# server, then connect and run
if options.nogui:
sumoBinary = checkBinary('sumo')
else:
sumoBinary = checkBinary('sumo-gui')
generate_routefile()
# this is the normal way of using traci. sumo is started as a
# subprocess and then the python script connects and runs
sumoProcess = subprocess.Popen([sumoBinary, "-c", "dijkstra.sumo.cfg", "--tripinfo-output", "tripinfo.xml", "--remote-port", str(PORT)], stdout=sys.stdout, stderr=sys.stderr)
main()
sumoProcess.wait()
--