进化算法中的 蚁群遗传算法（Ant Colony Genetic Algorithm）

pythonCopy codeimport numpy as np
# 初始化参数
num_ants = 50  # 蚂蚁数量
num_iterations = 100  # 迭代次数
num_cities = 20  # 城市数量
alpha = 1  # 信息素重要程度
beta = 5  # 启发式信息重要程度
rho = 0.1  # 信息素挥发率
Q = 100  # 信息素增强强度
best_distance = np.inf  # 最佳路径长度
best_path = []  # 最佳路径
# 初始化城市坐标
cities = np.random.rand(num_cities, 2)
# 初始化距离矩阵
distances = np.zeros((num_cities, num_cities))
for i in range(num_cities):
    for j in range(i+1, num_cities):
        distances[i][j] = np.linalg.norm(cities[i] - cities[j])
        distances[j][i] = distances[i][j]
# 初始化信息素矩阵
pheromones = np.ones((num_cities, num_cities))
# 开始迭代
for it in range(num_iterations):
    # 初始化蚂蚁路径和距离
    paths = np.zeros((num_ants, num_cities+1), dtype=int)
    distances = np.zeros(num_ants)
    # 蚂蚁选择路径
    for ant in range(num_ants):
        # 初始化已访问城市列表
        visited = [False] * num_cities
        # 蚂蚁随机选择起始城市
        current_city = np.random.randint(num_cities)
        visited[current_city] = True
        paths[ant][0] = current_city
        # 按照蚁群算法规则选择路径
        for i in range(1, num_cities):
            probabilities = np.zeros(num_cities)
            # 计算每个未访问城市的转移概率
            for j in range(num_cities):
                if not visited[j]:
                    probabilities[j] = (pheromones[current_city][j] ** alpha) * ((1.0 / distances[current_city][j]) ** beta)
            # 轮盘赌选择下一个城市
            probabilities = probabilities / np.sum(probabilities)
            next_city = np.random.choice(range(num_cities), p=probabilities)
            visited[next_city] = True
            paths[ant][i] = next_city
            current_city = next_city
        # 计算路径长度
        paths[ant][-1] = paths[ant][0]  # 回到起始城市
        distances[ant] = np.sum(distances[ant][i][i+1] for i in range(num_cities))
    # 更新全局最佳路径
    if np.min(distances) < best_distance:
        best_distance = np.min(distances)
        best_path = paths[np.argmin(distances)]
    # 更新信息素
    delta_pheromones = np.zeros((num_cities, num_cities))
    for ant in range(num_ants):
        for i in range(num_cities):
            delta_pheromones[paths[ant][i]][paths[ant][i+1]] += Q / distances[ant]
    pheromones = (1 - rho) * pheromones + delta_pheromones
# 输出结果
print("最佳路径：", best_path)
print("最佳路径长度：", best_distance)

pythonCopy codeimport numpy as np
from heapq import heappop, heappush
def dijkstra(graph, start, end):
    # 初始化距离字典
    distances = {vertex: np.inf for vertex in graph}
    distances[start] = 0
    # 初始化前驱节点字典
    predecessors = {vertex: None for vertex in graph}
    # 初始化优先队列
    queue = [(0, start)]
    
    while queue:
        current_distance, current_vertex = heappop(queue)
        
        if current_distance > distances[current_vertex]:
            continue
        
        if current_vertex == end:
            break
        
        for neighbor, weight in graph[current_vertex].items():
            distance = current_distance + weight
            
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                predecessors[neighbor] = current_vertex
                heappush(queue, (distance, neighbor))
    
    # 构建最短路径
    path = []
    current_vertex = end
    
    while current_vertex != start:
        path.insert(0, current_vertex)
        current_vertex = predecessors[current_vertex]
    
    path.insert(0, start)
    
    return path, distances[end]
# 定义图的邻接表
graph = {
    'A': {'B': 1, 'C': 4},
    'B': {'A': 1, 'C': 2, 'D': 5},
    'C': {'A': 4, 'B': 2, 'D': 1},
    'D': {'B': 5, 'C': 1}
}
start = 'A'  # 起点
end = 'D'  # 目标点
path, distance = dijkstra(graph, start, end)
print("最短路径：", path)
print("最短路径长度：", distance)