蚁群算法python代码

蚁群算法是一种模拟蚂蚁觅食行为的优化算法，常用于解决组合优化问题，如旅行商问题。

python
import random
class AntColony:
def __init__(self, distances, n_ants, decay, alpha=1, beta=1):
"""
Args:
distances (2D numpy.array): Square matrix of distances. Diagonal is assumed to be np.inf.
n_ants (int): Number of ants running per iteration
decay (float): Rate it which pheromone decays. The pheromone value is multiplied by decay, so 0.95 will lead to decay,
whereas 1.0 will keep the values constant.
alpha (int or float): exponenet on pheromone, higher alpha gives pheromone more weight. Default=1
beta (int or float): exponent on distance, higher beta give distance more weight. Default=1
"""
self.distances  = distances
self.pheromone  = 1 / (len(distances)**2) * np.ones(distances.shape)
self.all_inds  = range(len(distances))
self.n_ants    = n_ants
self.decay     = decay
self.alpha     = alpha
self.beta      = beta
def run(self, n):
"""
Args:
n (int): Number of iterations
"""
best_path = None
all_time_best_path = ("placeholder", np.inf)
for i in range(n):
all_paths = self.gen_all_paths()
self.spread_pheronome(all_paths, self.pheromone, self.distances)
self.pheromone * self.decay
self.intensify_pheromone(self.best_path(all_paths), self.pheromone, self.distances)
if self.best_path(all_paths) == all_time_best_path:
best_path = self.best_path(all_paths)
if self.best_path(all_paths)[1] < all_time_best_path[1]:
all_time_best_path = self.best_path(all_paths)
return all_time_best_path
def spread_pheronome(self, all_paths, pheromone, distances):
"""
Args:
all_paths (list): all the paths of the ants
pheromone (2D numpy.array): pheromone matrix
distances (2D numpy.array): distance matrix
"""
pheromone * self.decay
for path in all_paths:
for move in path:
pheromone[move] += 1 / distances[move]
def intensify_pheromone(self, best_path, pheromone, distances):
"""
Args:
best_path (tuple): the best path and its length
pheromone (2D numpy.array): pheromone matrix
distances (2D numpy.array): distance matrix
"""
for move in best_path[0]:
pheromone[move] += 1 / distances[move]
def gen_path_dist(self, path):
"""
Args:
path (list): list of moves ant has made
"""
total_dist = 0
for move in path:
total_dist += self.distances[move]
return total_dist
def best_path(self, all_paths):
"""
Args:
all_paths (list): all the paths of the ants
"""
all_paths = all_paths
all_paths_dist = []
for path in all_paths:
all_paths_dist.append((path, self.gen_path_dist(path)))
return min(all_paths_dist, key=lambda x: x[1])
def gen_all_paths(self):
"""
Returns:
all_paths (list): all the paths of the ants
"""
all_paths = []
for i in range(self.n_ants):
path = self.gen_path(0)
while set(path) != set(self.all_inds):
path = self.gen_path(0)
all_paths.append(path)
return all_paths
def gen_path(self, start):
"""
Args:
start (int): starting location of the ant
Returns:
path (list): the path of the ant
"""
path = []
visited = set()
visited.add(start)
prev = start
for i in range(len(self.distances)-1):
move = self.pick_move(self.pheromone[prev], self.distances[prev], visited)
path.append((prev, move))
prev = move
visited.add(move)
path.append((prev, start)) # going back to where we started    
return path
def pick_move(self, pheromone, dist, visited):
"""
Args:
pheromone (1D numpy.array): pheromone of the current node
dist (1D numpy.array): distance matrix of the current node
visited (set): set of visited nodes
Returns:
move (int): the next move
"""
row = pheromone ** self.alpha * (( 1.0 / dist) ** self.beta)
row[list(visited)] = 0
norm_row = row / row.sum()
move = np_choice(self.all_inds, 1, p=norm_row)[0]
return move

这是一个简单的ACO算法实现。这个实现中使用了NumPy库，你可能需要安装它，你可以使用

bash
pip install numpy

要使用这个算法，你需要创建一个包含节点之间距离的距离矩阵。例如，如果有3个节点，你的距离矩阵可能是这样的：

python
import numpy as np
distances = np.array([
[0, 1, 2],
[1, 0, 3],
[2, 3, 0]
])

然后，你可以创建AntColony对象并运行算法：

python
aco = AntColony(distances, n_ants=3, decay=0.95, alpha=1, beta=2)
best_path = aco.run(100)
print("Best Path:", best_path[0])
print("Best Distance:", best_path[1])

python
import numpy as np
from numpy.random import choice as np_choice
class AntColony:
def __init__(self, distances, n_ants, decay, alpha=1, beta=1):
self.distances  = distances
self.pheromone  = np.ones(self.distances.shape) / len(distances)
self.all_inds   = range(len(distances))
self.n_ants     = n_ants
self.decay      = decay
self.alpha      = alpha
self.beta       = beta
def run(self, n):
all_time_best_path = None
for i in range(n):
all_paths = self.gen_all_paths()
self.spread_pheromone(all_paths, self.pheromone, self.distances)
self.pheromone * self.decay
self.intensify_pheromone(self.best_path(all_paths), self.pheromone, self.distances)
if all_time_best_path is None or self.best_path(all_paths)[1] < all_time_best_path[1]:
all_time_best_path = self.best_path(all_paths)
return all_time_best_path
def spread_pheromone(self, all_paths, pheromone, distances):
for path in all_paths:
for move in path:
pheromone[move] += 1 / distances[move]
def intensify_pheromone(self, best_path, pheromone, distances):
for move in best_path[0]:
pheromone[move] += 1 / distances[move]
def gen_path_dist(self, path):
total_dist = 0
for move in path:
total_dist += self.distances[move]
return total_dist
def best_path(self, all_paths):
all_paths = all_paths
all_paths_dist = []
for path in all_paths:
all_paths_dist.append((path, self.gen_path_dist(path)))
return min(all_paths_dist, key=lambda x: x[1])
def gen_all_paths(self):
all_paths = []
for i in range(self.n_ants):
path = self.gen_path(0)
while set(path) != set(self.all_inds):
path = self.gen_path(0)
all_paths.append(path)
return all_paths
def gen_path(self, start):
path = []
visited = set()
visited.add(start)
prev = start
for i in range(len(self.distances)-1):
move = self.pick_move(self.pheromone[prev], self.distances[prev], visited)
path.append((prev, move))
prev = move
visited.add(move)
path.append((prev, start))  # going back to where we started
return path
def pick_move(self, pheromone, dist, visited):
row = pheromone ** self.alpha * ((1.0 / dist) ** self.beta)
row[list(visited)] = 0
norm_row = row / row.sum()
move = np_choice(self.all_inds, 1, p=norm_row)[0]
return move

这个修复的版本应该更加稳定和准确。使用这个修复的版本，你可以按照上面的例子创建AntColony对象并运行算法。这个算法可能需要根据具体问题进行调整和优化。