用Python写出狼群算法解决tsp问题的完整代码
时间: 2024-01-05 09:02:10 浏览: 52
以下是使用Python实现狼群算法解决TSP问题的完整代码:
```python
import numpy as np
import random
# 城市坐标生成函数
def generate_data(num_points):
data = []
for i in range(num_points):
x = random.randint(0, 100)
y = random.randint(0, 100)
data.append([x, y])
return np.array(data)
# 距离计算函数
def calculate_distance(route, data):
distance = 0
for i in range(len(route)-1):
start = route[i]
end = route[i+1]
distance += np.linalg.norm(data[start] - data[end])
distance += np.linalg.norm(data[route[-1]] - data[route[0]])
return distance
# 狼类
class Wolf:
def __init__(self, data, alpha=1, beta=2, delta=3):
self.data = data
self.alpha = alpha
self.beta = beta
self.delta = delta
self.position = np.random.permutation(len(data))
self.fitness = calculate_distance(self.position, self.data)
def update_fitness(self):
self.fitness = calculate_distance(self.position, self.data)
def update_position(self, beta_wolf, delta_wolf):
r1 = np.random.random()
r2 = np.random.random()
A = 2*self.alpha*r1 - self.alpha
C = 2*r2
D = abs(C*beta_wolf.position - self.position)
E = 2*r2
F = abs(E*delta_wolf.position - self.position)
new_position = (beta_wolf.position - A*D) + (delta_wolf.position - A*F)
self.position = np.clip(new_position, 0, len(self.position)-1)
# 狼群类
class WolfPack:
def __init__(self, data, num_wolves):
self.wolves = [Wolf(data) for i in range(num_wolves)]
self.best_fitness = float('inf')
self.best_position = None
def update_best(self):
for wolf in self.wolves:
if wolf.fitness < self.best_fitness:
self.best_fitness = wolf.fitness
self.best_position = wolf.position
def run(self, num_iterations):
for i in range(num_iterations):
for wolf in self.wolves:
beta_wolf = self.wolves[random.randint(0, len(self.wolves)-1)]
delta_wolf = self.wolves[random.randint(0, len(self.wolves)-1)]
wolf.update_position(beta_wolf, delta_wolf)
wolf.update_fitness()
self.update_best()
print(f"Iteration {i}: Best Fitness = {self.best_fitness}")
# 主函数
if __name__ == '__main__':
data = generate_data(20)
pack = WolfPack(data, num_wolves=10)
pack.run(num_iterations=100)
print(f"Best Route: {pack.best_position}")
print(f"Best Fitness: {pack.best_fitness}")
```
注意:此代码仅用作学习和研究目的,不适用于生产环境。同时,该算法在处理大规模TSP问题时可能会受到限制,因此需要对其进行改进和优化。