Implementing Ant colony optimization in python- solving Traveling salesman problem
- Implementing gradient descent in python (click here)
- Implemention of particle swarm optimization (click here)
- Implementing Gradient Descent In Quality Control to minimize “Defect rate” — Python (click here)
Ant colony optimization (ACO) is a method inspired by the behavior of ants when they search for food.
It is a metaheuristic optimization algorithm inspired by the behavior of ants. It is commonly used to solve combinatorial optimization problems like the Traveling Salesman Problem (TSP), the job shop scheduling problem, the vehicle routing problem, and the Knapsack problem.
When ants look for food, they move randomly, leaving a pheromone trail behind them. Other ants follow these pheromone trails to find the food. The more ants that follow a trail, the stronger the pheromone trail becomes.
say in this example (figure),
first, some Ant goes through the gray line, and it doesn't find the food. Since only some Ant’s went through this way, the “pheromone” left by the ant will be minimal. These ant communicates with other ants not to follow this path.
Second another set of some Ants goes through the orange line, and it finds food. These ant communicates with other ants that the food is found. So the other ant knows how to reach food following the “pheromone” train (orange path).
Once the location of food is found, the other set of ants diverge to find the shortest path to the food from their ant colony. If the shortest path is found, then the shortest path is communicated to other ants. Now more ant’s travel through the shortest path (red line) thus creating very strong “pheromone” trail. So finally ant’s use the (red line) to go from their colony to food source.
Similarly, in ACO, we have a group of artificial ants that are trying to find the best solution to a problem.
For example, if we want to find the shortest path between two points, the artificial ants move randomly from one point to another, leaving a pheromone trail behind them.
The pheromone trail indicates the quality of the path that the ant took. The ants prefer to follow the pheromone trail that is stronger, which corresponds to a better path.
Steps involved in Ant colony optimization:
- Initialization: We start by placing the ants on the starting point.
- Movement: Each ant selects a point to move to based on a probabilistic function that takes into account the pheromone level and the heuristic information. The heuristic information can be thought of as a measure of how good a particular point is.
- Updating pheromone trails: The pheromone trail on each edge is updated based on the quality of the solution found by the ant that traversed that edge.
- Termination: We stop the algorithm after a certain number of iterations or when a satisfactory solution is found.
By repeating these steps, the ants will gradually converge on the best solution to the problem. ACO can be used to solve a wide range of optimization problems, such as the traveling salesman problem, where the goal is to find the shortest path that visits a set of cities.
Pros & Cons of Ant colony optimization:
Advantages :
- Ant colony optimization is easy to implement and does not require complex mathematical knowledge.
- It is a very flexible algorithm and can be used in various problem domains.
- It can handle multiple objectives and constraints.
- It is a metaheuristic algorithm that can quickly find high-quality solutions in a large solution space.
- It has the ability to find near-optimal solutions, even in cases where the search space is very large or poorly understood.
Disadvantages:
- The algorithm may converge to a suboptimal solution if the parameter settings are not carefully selected.
- The algorithm may become computationally expensive if there are a large number of ants and/or iterations required to find a solution.
- The quality of the solution may be dependent on the pheromone initialization, which can be difficult to optimize.
- The algorithm may require a large number of iterations to converge to a solution, which may be a disadvantage if fast convergence is required.
SOLVING TRAVELING SALESMAN PROBLEM:
The Traveling Salesman Problem (TSP) is a famous mathematical problem in computer science and operations research. In this problem, a salesman needs to visit a set of cities exactly once and return to the original city. The task is to find the shortest possible route that the salesman can take to visit all the cities and return to the starting city.
The TSP is an optimization problem and can be applied to various real-world scenarios. For example, a delivery person may want to visit a set of cities to deliver packages and return to the starting point while minimizing the distance traveled. Another example is a circuit board drilling machine that needs to drill holes at various locations on the board.
Finding the exact solution for TSP becomes computationally expensive as the number of cities increases. The number of possible paths between cities grows exponentially with the number of cities. Hence, it is necessary to use heuristic algorithms like ant colony optimization or genetic algorithms to find an approximate solution to the TSP.
IMPLEMENTATION
import numpy as np
import matplotlib.pyplot as plt
from mpl_toolkits.mplot3d import Axes3D
def distance(point1, point2):
return np.sqrt(np.sum((point1 - point2)**2))
def ant_colony_optimization(points, n_ants, n_iterations, alpha, beta, evaporation_rate, Q):
n_points = len(points)
pheromone = np.ones((n_points, n_points))
best_path = None
best_path_length = np.inf
for iteration in range(n_iterations):
paths = []
path_lengths = []
for ant in range(n_ants):
visited = [False]*n_points
current_point = np.random.randint(n_points)
visited[current_point] = True
path = [current_point]
path_length = 0
while False in visited:
unvisited = np.where(np.logical_not(visited))[0]
probabilities = np.zeros(len(unvisited))
for i, unvisited_point in enumerate(unvisited):
probabilities[i] = pheromone[current_point, unvisited_point]**alpha / distance(points[current_point], points[unvisited_point])**beta
probabilities /= np.sum(probabilities)
next_point = np.random.choice(unvisited, p=probabilities)
path.append(next_point)
path_length += distance(points[current_point], points[next_point])
visited[next_point] = True
current_point = next_point
paths.append(path)
path_lengths.append(path_length)
if path_length < best_path_length:
best_path = path
best_path_length = path_length
pheromone *= evaporation_rate
for path, path_length in zip(paths, path_lengths):
for i in range(n_points-1):
pheromone[path[i], path[i+1]] += Q/path_length
pheromone[path[-1], path[0]] += Q/path_length
fig = plt.figure(figsize=(8, 6))
ax = fig.add_subplot(111, projection='3d')
ax.scatter(points[:,0], points[:,1], points[:,2], c='r', marker='o')
for i in range(n_points-1):
ax.plot([points[best_path[i],0], points[best_path[i+1],0]],
[points[best_path[i],1], points[best_path[i+1],1]],
[points[best_path[i],2], points[best_path[i+1],2]],
c='g', linestyle='-', linewidth=2, marker='o')
ax.plot([points[best_path[0],0], points[best_path[-1],0]],
[points[best_path[0],1], points[best_path[-1],1]],
[points[best_path[0],2], points[best_path[-1],2]],
c='g', linestyle='-', linewidth=2, marker='o')
ax.set_xlabel('X Label')
ax.set_ylabel('Y Label')
ax.set_zlabel('Z Label')
plt.show()
# Example usage:
points = np.random.rand(10, 3) # Generate 10 random 3D points
ant_colony_optimization(points, n_ants=10, n_iterations=100, alpha=1, beta=1, evaporation_rate=0.5, Q=1)
OTHER ARTICLES
