Python实现Ant Colony Optimization算法示例与解释

Ant Colony Optimization（ACO）算法是一种启发式算法，模拟蚂蚁寻找食物的行为，用于解决组合优化问题。它通过模拟蚂蚁在搜索过程中释放信息素、选择路径以及更新信息素浓度来寻找最优解。

import random

# 创建一个简单的图表示城市间的距离
# 这里使用字典表示城市之间的距离，0表示城市本身到自身的距离，-1表示不可达
distances = {
    'A': {'A': 0, 'B': 5, 'C': 2, 'D': 4},
    'B': {'A': 5, 'B': 0, 'C': 3, 'D': 2},
    'C': {'A': 2, 'B': 3, 'C': 0, 'D': 7},
    'D': {'A': 4, 'B': 2, 'C': 7, 'D': 0}
}

# ACO算法的主要函数
def ant_colony_optimization(distances, iterations=100, num_ants=5, evaporation_rate=0.5, alpha=1, beta=2):
    pheromones = {city: {neighbor: 1 for neighbor in distances[city]} for city in distances}
    best_path = None
    best_distance = float('inf')

    for _ in range(iterations):
        for ant in range(num_ants):
            current_city = random.choice(list(distances.keys()))
            visited_cities = [current_city]

            while len(visited_cities) < len(distances):
                probabilities = []

                # 计算下一个城市的概率
                for city, distance in distances[current_city].items():
                    if city not in visited_cities:
                        pheromone = pheromones[current_city][city]
                        probabilities.append((city, (pheromone ** alpha) * ((1 / distance) ** beta)))

                # 选择下一个城市
                total = sum(prob[1] for prob in probabilities)
                probabilities = [(city, prob[1] / total) for city, prob in probabilities]
                next_city = random.choices([prob[0] for prob in probabilities], [prob[1] for prob in probabilities])[0]

                visited_cities.append(next_city)
                current_city = next_city

            # 计算路径总距离
            distance = sum(distances[visited_cities[i]][visited_cities[i + 1]] for i in range(len(visited_cities) - 1))
            if distance < best_distance:
                best_distance = distance
                best_path = visited_cities

            # 更新信息素浓度
            for i in range(len(visited_cities) - 1):
                pheromones[visited_cities[i]][visited_cities[i + 1]] *= (1 - evaporation_rate)
                pheromones[visited_cities[i + 1]][visited_cities[i]] *= (1 - evaporation_rate)
                pheromones[visited_cities[i]][visited_cities[i + 1]] += 1 / distance
                pheromones[visited_cities[i + 1]][visited_cities[i]] += 1 / distance

    return best_path, best_distance

# 使用示例
best_path, best_distance = ant_colony_optimization(distances)
print("最优路径:", best_path)
print("最短距离:", best_distance)

免责申明：文章和图片全部来源于公开网络，如有侵权，请通知删除 server@dude6.com