I got a kind of TSP-problem and an ant colony optimization solution for it. The thing is, I don't completely understand the mechanics of updating the pheromone at the end, could someone please explain it and tell if it's correct or not?
The problem is when I have a graph with more nodes this algorithm seems to give very bad results compared to a simple greedy algorithm. So, what's the problem?
# Graph data
NODES_AMOUNT = 5
MAX_AMOUNT_NODES = 6
MONEY_LIMIT = 600
COST_RND_MIN = 50
COST_RND_MAX = 300
# ant
NUM_ANTS = 5
NUM_ITERATIONS = 10
ALPHA = 1
BETA = 0.3
RHO = 0.4
Q = 100
def ant_colony_solution(K, C, kwargs):
"""
distances: a matrix of pairwise distances between cities
num_ants: number of ants in the colony
num_iterations: number of iterations to run the algorithm
alpha: controls the relative importance of the pheromone trail
beta: controls the relative importance of the edge cost
rho: controls the evaporation of the pheromone trail
q: controls the amount of pheromone deposited by each ant
"""
money_limit = kwargs["money_limit"]
ratio = kwargs["ratio"]
num_ants = kwargs["num_ants"]
num_iterations = kwargs["num_iterations"]
alpha = kwargs["alpha"]
beta = kwargs["beta"]
rho = kwargs["rho"]
q = kwargs["q"]
def cities_to_avoid_foo(K, current_city, starting, cities_, visited, spent):
avoid = []
for city in cities_:
if city == current_city:
avoid.append(city)
continue
elif city in visited:
avoid.append(city)
continue
current_to_city = K[current_city][city]
price_to_starting = K[city][starting]
if money_limit <= spent + price_to_starting + current_to_city:
avoid.append(city)
return avoid
num_cities = K.shape[0]
pheromone = np.ones((num_cities, num_cities)) / num_cities # matrix
best_route = None
best_interest = -float('inf') #
for i in range(num_iterations):
routes = [] # will contain the routes constructed by the ants
distances_ = [] # will contain the corresponding distances.
# For each iteration, we construct a solution for each ant in the colony. We iterate num_ants times.
for _ in range(num_ants):
route = []
money_spent = 0
visited = set()
# current_city = random.randint(0, num_cities-1)
current_city = 0
starting_city = current_city
visited.add(current_city)
route.append(current_city)
while True:
cities_to_avoid = set(cities_to_avoid_foo(K, current_city, starting_city, range(num_cities), visited, money_spent))
unvisited_cities = [l for l in range(num_cities) if l not in visited and l not in cities_to_avoid]
if len(unvisited_cities) == 0:
break
prob = np.zeros(num_cities)
denom = 0
for l in range(num_cities):
if l not in cities_to_avoid:
prob[l] = pheromone[current_city][l] ** alpha * (1/K[current_city][l]) ** beta
denom += prob[l]
prob /= denom
next_city = np.random.choice(range(num_cities), p=prob)
money_spent += K[current_city][next_city]
visited.add(next_city)
route.append(next_city)
current_city = next_city
# We append the ant's route and corresponding distance to the routes and distances_ lists.
routes.append(route)
interest = get_route_interest(C, route)
distances_.append(get_route_ratio(ratio, route))
# If the ant's route is better than the best route found so far, we update the best_interest and best_route variables.
# print(route, money_spent, get_route_interest(C, route))
if interest > best_interest:
best_interest = interest
best_route = route
# print(route, money_spent, get_route_interest(C, route))
# update the pheromone levels
# After all ants have constructed a solution, we evaporate the pheromone trail by multiplying all values by rho.
# We update the pheromone trail by depositing pheromone along the routes constructed by the ants.
# The amount of pheromone deposited is proportional to the inverse of the route length (1/distance_), multiplied by a constant q.
pheromone *= (1 - rho)
for route, distance in zip(routes, distances_):
for i in route:
try: # TODO ???
pheromone[i][i+1] += q / distance
except:
pheromone[i][i] += q / distance
# pheromone[route[-1]][route[0]] += q / distance
best_route.append(best_route[0])
return {
"optimal_path": best_route,
"total_interest": get_route_interest(C, best_route),
"spent": get_route_cost(K, best_route)
}
This code block: The # TODO ??? line is not something I'm sure about Does it need a fix or something?
for route, distance in zip(routes, distances_):
for i in route:
try: # TODO ???
pheromone[i][i+1] += q / distance
except:
pheromone[i][i] += q / distance
# pheromone[route[-1]][route[0]] += q / distance`
I tried looking about it online but didn't find the exact meanings of these and the answer to the code block question.
The section of code you provided is responsible for updating the pheromone levels in the ant colony optimization algorithm. Let's analyze it step by step:
for route, distance in zip(routes, distances_):
for i in route:
try: # TODO ???
pheromone[i][i+1] += q / distance
except:
pheromone[i][i] += q / distance
This loop iterates over each route constructed by the ants and updates the pheromone levels accordingly. Here's a breakdown of what's happening:
for route, distance in zip(routes, distances_): - This loop iterates over the routes and corresponding distances calculated by the ants. Each route represents a path traveled by an ant, and distance represents the length of that path.
for i in route: - This loop iterates over each city (node) in the route.
try: pheromone[i][i+1] += q / distance - This line attempts to update the pheromone level between city i and the next city in the route (i+1). It adds a certain amount of pheromone (q / distance) to the existing pheromone level.
q is a constant that controls the amount of pheromone deposited. distance is the length of the route traveled by the ant. The smaller the distance, the larger the amount of pheromone deposited. The try block is used to handle the last city in the route where there is no next city (i+1). In this case, the code falls into the except block.
except: pheromone[i][i] += q / distance - This line updates the pheromone level for the last city in the route. It adds the same amount of pheromone (q / distance) to the pheromone level of the city itself (pheromone[i][i]).
This is necessary because the last city in the route needs to have its pheromone level updated even though there is no connection to the next city. By updating the pheromone level of the last city, it helps the algorithm explore different paths in future iterations.
In summary, the code block updates the pheromone levels for each city and connection based on the routes constructed by the ants. The amount of pheromone deposited depends on the distance traveled by the ants, with a larger amount deposited for shorter routes. The try-except block handles the last city in the route where there is no next city connection.
Regarding the line with # TODO ???, it seems to be commented out and not affecting the code. If you have any specific concerns or issues related to that line, please provide more details, and I'll be happy to assist you further.