Closed MustafaA107 closed 1 year ago
@MustafaA107 can you share the graph structure or the code you use for creating the graph?
@hasnainroopawalla I am getting this issue too.
A sample graph is provided below.
graph = Graph()
graph.add_edge("2", "1", travel_time=1655)
graph.add_edge("2", "3", travel_time=3230)
graph.add_edge("2", "11", travel_time=2367)
graph.add_edge("2", "10", travel_time=1368)
graph.add_edge("3", "2", travel_time=3230)
graph.add_edge("3", "10", travel_time=3230)
graph.add_edge("4", "3", travel_time=1213)
graph.add_edge("5", "3", travel_time=2472)
graph.add_edge("5", "6", travel_time=152)
graph.add_edge("6", "7", travel_time=2801)
graph.add_edge("6", "20", travel_time=1319)
graph.add_edge("7", "6", travel_time=2801)
graph.add_edge("7", "8", travel_time=867)
graph.add_edge("7", "19", travel_time=834)
graph.add_edge("9", "8", travel_time=201)
graph.add_edge("9", "10", travel_time=857)
graph.add_edge("9", "19", travel_time=1203)
graph.add_edge("10", "2", travel_time=1368)
graph.add_edge("10", "3", travel_time=2541)
graph.add_edge("10", "9", travel_time=857)
graph.add_edge("11", "2", travel_time=2367)
graph.add_edge("11", "12", travel_time=2368)
graph.add_edge("11", "15", travel_time=1409)
graph.add_edge("11", "19", travel_time=1653)
graph.add_edge("12", "13", travel_time=711)
graph.add_edge("12", "14", travel_time=541)
graph.add_edge("15", "11", travel_time=1409)
graph.add_edge("15", "14", travel_time=1678)
graph.add_edge("15", "16", travel_time=2144)
graph.add_edge("15", "18", travel_time=1487)
graph.add_edge("16", "15", travel_time=2144)
graph.add_edge("16", "17", travel_time=1585)
graph.add_edge("16", "23", travel_time=2557)
graph.add_edge("17", "16", travel_time=1585)
graph.add_edge("17", "18", travel_time=477)
graph.add_edge("17", "25", travel_time=156)
graph.add_edge("18", "15", travel_time=1487)
graph.add_edge("18", "17", travel_time=477)
graph.add_edge("18", "19", travel_time=870)
graph.add_edge("19", "20", travel_time=3977)
graph.add_edge("19", "18", travel_time=870)
graph.add_edge("19", "11", travel_time=1653)
graph.add_edge("19", "9", travel_time=1203)
graph.add_edge("19", "7", travel_time=834)
graph.add_edge("20", "21", travel_time=2945)
graph.add_edge("20", "23", travel_time=3054)
graph.add_edge("20", "19", travel_time=3977)
graph.add_edge("20", "6", travel_time=1319)
graph.add_edge("23", "22", travel_time=2561)
graph.add_edge("23", "16", travel_time=2557)
graph.add_edge("24", "23", travel_time=984)
graph.add_edge("24", "25", travel_time=2519)
source = "4"
destination = "1"
aco = ACO(graph)
aco_path, aco_cost = aco.find_shortest_path(source, destination)
print(f"ACO - path: {aco_path}, cost: {aco_cost}")
To fix it, let the ant stay stuck on a node after it has visited all nodes, until it gets tagged as unfit after max_iterations
.
In the Ant.take_step
method, adding the condition fixes the issue:
# Pick the next node based on the Roulette Wheel selection technique.
next_node = self._pick_next_node(unvisited_neighbors, self.alpha, self.beta)
if not next_node:
return
@king-phyte thanks for the suggestion! The logic to compute the shortest path using the solution ant was incorrect and has been fixed in Pull Request #7. cc: @MustafaA107
It might be a problem with my data set but I don't know why Dijkstra works fine but the ant colony it has a problem it gives me this error above It does not really specify anything that is wrong except the keyError : ""
Any way you can help would be appreciate it thank you for tour time