Python实现蚁群算法：解决复杂优化问题的智能寻径策略

import numpy as np
import matplotlib.pyplot as plt
import random
from tqdm import tqdm

class AntColony:
    def __init__(self, distances, n_ants=10, n_iterations=100, 
                 decay=0.5, alpha=1, beta=2, Q=100):
        """
        蚁群算法优化器
        :param distances: 城市间距离矩阵
        :param n_ants: 蚂蚁数量
        :param n_iterations: 迭代次数
        :param decay: 信息素挥发率
        :param alpha: 信息素重要程度
        :param beta: 启发式信息重要程度
        :param Q: 信息素强度常数
        """
        self.distances = distances
        self.n_ants = n_ants
        self.n_iterations = n_iterations
        self.decay = decay
        self.alpha = alpha
        self.beta = beta
        self.Q = Q
        
        # 初始化信息素矩阵
        self.pheromone = np.ones(distances.shape) / len(distances)
        # 存储所有可能路径的启发信息（距离的倒数）
        self.heuristic = 1 / (distances + 1e-10)  # 避免除零错误
        
        # 存储最佳路径及其长度
        self.best_path = None
        self.best_length = float('inf')
        
        # 存储每代最佳路径长度用于绘图
        self.history = []

    def run(self):
        """执行优化过程"""
        for _ in tqdm(range(self.n_iterations)):
            all_paths = self._generate_paths()
            self._update_pheromone(all_paths)
            
            # 更新全局最佳路径
            current_best_path, current_best_length = min(
                all_paths, key=lambda x: x[1]
            )
            
            if current_best_length < self.best_length:
                self.best_path = current_best_path
                self.best_length = current_best_length
                
            self.history.append(self.best_length)
        
        return self.best_path, self.best_length

    def _generate_paths(self):
        """所有蚂蚁构建完整路径"""
        all_paths = []
        for _ in range(self.n_ants):
            path = self._construct_path()
            path_length = self._calculate_length(path)
            all_paths.append((path, path_length))
        return all_paths

    def _construct_path(self):
        """单只蚂蚁构建路径"""
        # 随机选择起始城市
        start = random.randint(0, len(self.distances)-1)
        path = [start]
        unvisited = set(range(len(self.distances)))
        unvisited.remove(start)
        
        # 遍历所有城市
        while unvisited:
            next_city = self._select_next_city(path[-1], unvisited)
            path.append(next_city)
            unvisited.remove(next_city)
            
        return path

    def _select_next_city(self, current, unvisited):
        """根据概率选择下一个城市"""
        probabilities = []
        
        # 计算所有未访问城市的转移概率
        for city in unvisited:
            pheromone = self.pheromone[current][city] ** self.alpha
            heuristic = self.heuristic[current][city] ** self.beta
            probabilities.append(pheromone * heuristic)
        
        # 归一化概率
        total = sum(probabilities)
        probabilities = [p / total for p in probabilities]
        
        # 轮盘赌选择下一个城市
        return random.choices(list(unvisited), weights=probabilities, k=1)[0]

    def _calculate_length(self, path):
        """计算路径总长度"""
        total = 0
        for i in range(len(path)):
            total += self.distances[path[i-1]][path[i]]
        return total

    def _update_pheromone(self, all_paths):
        """更新信息素矩阵"""
        # 信息素挥发
        self.pheromone *= (1 - self.decay)
        
        # 信息素增强
        for path, length in all_paths:
            # 只增强精英蚂蚁的路径（前10%）
            if length <= sorted([p[1] for p in all_paths])[int(0.1 * len(all_paths))]:
                for i in range(len(path)):
                    # 在路径的每条边上增加信息素
                    self.pheromone[path[i-1]][path[i]] += self.Q / length

    def plot_learning_curve(self):
        """绘制学习曲线"""
        plt.figure(figsize=(10, 6))
        plt.plot(self.history, 'b-', linewidth=2)
        plt.title('蚁群算法优化过程')
        plt.xlabel('迭代次数')
        plt.ylabel('最短路径长度')
        plt.grid(True)
        plt.show()

def create_distance_matrix(cities):
    """根据城市坐标创建距离矩阵"""
    n = len(cities)
    matrix = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            if i != j:
                # 计算欧几里得距离
                matrix[i][j] = np.linalg.norm(cities[i] - cities[j])
    return matrix

# 示例使用
if __name__ == "__main__":
    # 随机生成城市坐标
    np.random.seed(42)
    cities = np.random.rand(25, 2) * 100  # 25个城市
    
    # 创建距离矩阵
    dist_matrix = create_distance_matrix(cities)
    
    # 初始化并运行蚁群算法
    aco = AntColony(
        dist_matrix,
        n_ants=20,
        n_iterations=200,
        decay=0.5,
        alpha=1,
        beta=3,
        Q=100
    )
    
    best_path, best_length = aco.run()
    print(f"最佳路径长度: {best_length:.2f}")
    print(f"最佳路径顺序: {best_path}")
    
    # 绘制优化过程
    aco.plot_learning_curve()
    
    # 可视化最优路径
    plt.figure(figsize=(10, 8))
    plt.scatter(cities[:, 0], cities[:, 1], c='red', s=100)
    
    # 绘制路径
    for i in range(len(best_path)):
        start = cities[best_path[i-1]]
        end = cities[best_path[i]]
        plt.plot([start[0], end[0]], [start[1], end[1]], 'b-')
    
    plt.title(f'最佳旅行商路径 (长度: {best_length:.2f})')
    plt.xlabel('X坐标')
    plt.ylabel('Y坐标')
    plt.grid(True)
    plt.show()