蚁群算法解决tsp问题python
时间: 2023-07-25 18:07:35 浏览: 63
蚁群算法是一种基于模拟蚂蚁在寻找食物时的行为进行优化的算法,可以用于解决TSP问题。下面是Python代码实现:
```python
import random
# 城市距离矩阵,可以根据需要修改
distance_matrix = [
[0, 2, 3, 4, 5],
[2, 0, 4, 5, 1],
[3, 4, 0, 6, 2],
[4, 5, 6, 0, 3],
[5, 1, 2, 3, 0]
]
# 蚂蚁数量
ant_count = 10
# 信息素挥发率
evaporation_rate = 0.5
# 信息素重要程度因子
alpha = 1
# 启发函数重要程度因子
beta = 2
# 最大迭代次数
max_iteration = 100
# 初始信息素浓度
init_pheromone = 1.0
# 启动城市
start_city = 0
# 计算城市之间的启发式信息,这里采用倒数
def get_heuristic(city1, city2):
return 1.0 / distance_matrix[city1][city2]
# 初始化信息素浓度矩阵
pheromone_matrix = []
for i in range(len(distance_matrix)):
row = []
for j in range(len(distance_matrix[i])):
if i == j:
row.append(0)
else:
row.append(init_pheromone)
pheromone_matrix.append(row)
# 迭代搜索
best_distance = float('inf')
best_route = []
for iteration in range(max_iteration):
# 蚂蚁进行搜索
routes = []
for ant in range(ant_count):
# 初始化蚂蚁的位置和已经访问的城市
current_city = start_city
visited_cities = [current_city]
# 搜索完所有城市后回到起点
while len(visited_cities) < len(distance_matrix):
# 计算当前城市到各个未访问城市的转移概率
probabilities = []
for city in range(len(distance_matrix)):
if city not in visited_cities:
pheromone = pheromone_matrix[current_city][city]
heuristic = get_heuristic(current_city, city)
probability = (pheromone ** alpha) * (heuristic ** beta)
probabilities.append((probability, city))
# 轮盘赌选择下一个城市
total_probability = sum(probability for probability, _ in probabilities)
selected_probability = random.uniform(0, total_probability)
current_probability = 0
next_city = None
for probability, city in probabilities:
current_probability += probability
if current_probability >= selected_probability:
next_city = city
break
# 更新当前城市和已经访问的城市
current_city = next_city
visited_cities.append(current_city)
# 计算路线长度并保存路线
distance = sum(distance_matrix[visited_cities[i]][visited_cities[i + 1]] for i in range(len(visited_cities) - 1))
distance += distance_matrix[visited_cities[-1]][visited_cities[0]]
routes.append((visited_cities, distance))
# 更新最优路线
for visited_cities, distance in routes:
if distance < best_distance:
best_distance = distance
best_route = visited_cities
# 更新信息素浓度
for i in range(len(pheromone_matrix)):
for j in range(len(pheromone_matrix[i])):
pheromone_matrix[i][j] *= (1 - evaporation_rate)
for visited_cities, distance in routes:
for k in range(len(visited_cities) - 1):
if visited_cities[k] == i and visited_cities[k + 1] == j:
pheromone_matrix[i][j] += (1.0 / distance)
break
# 输出当前迭代次数、最优路线长度和最优路线
print('Iteration {}: best distance = {}, best route = {}'.format(iteration, best_distance, best_route))
```
在上述代码中,我们定义了城市距离矩阵、蚂蚁数量、信息素挥发率、信息素重要程度因子、启发函数重要程度因子、最大迭代次数、初始信息素浓度、启动城市等参数,并实现了一个函数来计算城市之间的启发式信息。在初始化信息素浓度矩阵后,我们进行了迭代搜索,每次搜索时每只蚂蚁按照一定的概率选择下一个城市,并更新信息素浓度矩阵。最后输出最优路线长度和最优路线。