蚁群算法（Ant Colony Optimization, ACO）

简介

蚁群算法（Ant Colony Optimization, ACO）是一种基于自然启发的优化算法，由意大利学者马可·多里戈（Marco Dorigo）在1992年首次提出。它受自然界中蚂蚁觅食行为的启发，用于解决离散优化问题。

在自然界中，蚂蚁通过释放和追踪一种化学物质（即信息素）找到最短路径。蚁群算法通过模拟这种信息素的机制，在优化问题中迭代寻找近似最优解。

代码说明

距离矩阵：distance_matrix 是问题的输入，表示城市之间的距离。
信息素更新：信息素会随时间蒸发，并根据路径长度进行强化。
路径构建：每只蚂蚁根据概率选择下一步的城市，概率由信息素和启发式因子共同决定。
运行结果：输出最佳路径和对应路径长度。

代码

import numpy as np

class AntColony:
    def __init__(self, distance_matrix, n_ants, n_iterations, alpha=1, beta=2, evaporation_rate=0.5, Q=100):
        self.distance_matrix = distance_matrix
        self.n_ants = n_ants
        self.n_iterations = n_iterations
        self.alpha = alpha  # 控制信息素重要程度
        self.beta = beta  # 控制启发式因子的权重
        self.evaporation_rate = evaporation_rate
        self.Q = Q  # 信息素强度常数

        self.num_cities = distance_matrix.shape[0]
        self.pheromone_matrix = np.ones((self.num_cities, self.num_cities))  # 初始信息素矩阵

    def _initialize_ants(self):
        return [np.random.permutation(self.num_cities) for _ in range(self.n_ants)]

    def _calculate_path_length(self, path):
        return sum(self.distance_matrix[path[i], path[(i + 1) % len(path)]] for i in range(len(path)))

    def _update_pheromones(self, all_paths, all_lengths):
        self.pheromone_matrix *= (1 - self.evaporation_rate)  # 信息素蒸发
        for path, length in zip(all_paths, all_lengths):
            for i in range(len(path)):
                start, end = path[i], path[(i + 1) % len(path)]
                self.pheromone_matrix[start, end] += self.Q / length  # 信息素更新

    def _choose_next_city(self, current_city, visited):
        probabilities = []
        for city in range(self.num_cities):
            if city not in visited:
                pheromone = self.pheromone_matrix[current_city, city] ** self.alpha
                visibility = (1 / self.distance_matrix[current_city, city]) ** self.beta
                probabilities.append(pheromone * visibility)
            else:
                probabilities.append(0)

        probabilities = probabilities / np.sum(probabilities)
        return np.random.choice(range(self.num_cities), p=probabilities)

    def _construct_solution(self, ant):
        path = [ant]
        visited = set(path)
        for _ in range(self.num_cities - 1):
            next_city = self._choose_next_city(path[-1], visited)
            path.append(next_city)
            visited.add(next_city)
        return path

    def run(self):
        best_path = None
        best_length = float('inf')

        for iteration in range(self.n_iterations):
            all_paths = []
            all_lengths = []

            for ant in range(self.n_ants):
                start_city = np.random.randint(self.num_cities)
                path = self._construct_solution(start_city)
                length = self._calculate_path_length(path)

                all_paths.append(path)
                all_lengths.append(length)

                if length < best_length:
                    best_path = path
                    best_length = length

            self._update_pheromones(all_paths, all_lengths)

            print(f"Iteration {iteration + 1}: Best length = {best_length}")

        return best_path, best_length


# 示例距离矩阵
distance_matrix = np.array([
    [0, 2, 2, 5, 7],
    [2, 0, 4, 8, 2],
    [2, 4, 0, 1, 3],
    [5, 8, 1, 0, 2],
    [7, 2, 3, 2, 0]
])

# 创建蚁群算法实例
ant_colony = AntColony(distance_matrix, n_ants=10, n_iterations=100, alpha=1, beta=2, evaporation_rate=0.5, Q=100)

# 运行算法
best_path, best_length = ant_colony.run()

print("Best path:", best_path)
print("Best length:", best_length)