Python遗传算法解TSP

yinda_peng

专业选修课人工智能概论讲了遗传算法（GA），老师说让我们做一下遗传算法解TSP，刚好暑假搞数学建模学了点遗传算法，代码嘛，套着GA的模版改一改，就可以解TSP了

首先简单介绍一下遗传算法解TSP的基本思路：

• 初始化：随机生成一定数量的个体（路径序列），每个个体表示一条旅行路线。
• 适应度评估：计算每条路径的总距离，将距离转化为适应度值（适应度与路径长度成反比）。
• 选择：通过轮盘赌选择或其他选择机制，选择适应度较高的个体进入下一代。
• 交叉：随机选择一对个体，并在其路径中交叉生成新个体。
• 变异：随机选择个体并在其路径中交换城市，以增加多样性。
• 迭代：重复进行评估、选择、交叉和变异，直到达到指定代数或收敛条件。
• 输出结果：返回适应度最高的路径及其长度。
  

1. import random
   
2. import math
   
3. import numpy as np
   
4. import time
   
5. 
   
6. # 相关的系数
   
7. PC = 0.55  # 交叉概率
   
8. PM = 0.05   # 变异概率
   
9. POP_SIZE = 100  # 种群规模
   
10. N_GENERATIONS = 700  # 进化代数
    
11. N_CITIES = 31  # 城市数量
    
12. SEED = 20  # 随机种子
    
13. 
    
14. # 城市坐标
    
15. city_pos = [
    
16.     [1304, 2312], [3639, 1315], [4177, 2244], [3712, 1399], [3488, 1535],
    
17.     [3326, 1556], [3238, 1229], [4196, 1004], [4312, 790], [4386, 570],
    
18.     [3007, 1970], [2562, 1756], [2788, 1491], [2381, 1676], [1332, 695],
    
19.     [3715, 1678], [3918, 2179], [4061, 2370], [3780, 2212], [3676, 2578],
    
20.     [4029, 2838], [4263, 2931], [3429, 1908], [3507, 2367], [3394, 2643],
    
21.     [3439, 3201], [2935, 3240], [3140, 3550], [2545, 2357], [2778, 2826],
    
22.     [2370, 2975]
    
23. ]
    
24. 
    
25. # 定义个体类
    
26. class Individual:
    
27.     def __init__(self, sequence):
    
28.         self.sequence = sequence  # 城市访问序列
    
29.         self.fitness = 0  # 适应度
    
30.         self.p_fitness = 0  # 适应度概率
    
31.         self.sum_p_fitness = 0  # 累加适应度概率
    
32. 
    
33.     # 计算路径的适应度
    
34.     def calculate_fitness(self):
    
35.         total_distance = 0  # 总的距离
    
36.         for i in range(N_CITIES):
    
37.             city1 = self.sequence[i]
    
38.             city2 = self.sequence[(i + 1) % N_CITIES]  # 回到起始城市
    
39.             total_distance += self.calculate_distance(city1, city2)
    
40.         self.fitness = 50000 - total_distance  # 适应度越高越好
    
41. 
    
42.     # 计算两个城市之间的距离
    
43.     @staticmethod
    
44.     def calculate_distance(city1, city2):
    
45.         x1, y1 = city_pos[city1 - 1]
    
46.         x2, y2 = city_pos[city2 - 1]
    
47.         return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
    
48. 
    
49. # 初始化种群
    
50. def initialize_population():
    
51.     population = []
    
52.     for _ in range(POP_SIZE):
    
53.         sequence = list(range(1, N_CITIES + 1))
    
54.         random.shuffle(sequence)  # 随机打乱城市顺序
    
55.         individual = Individual(sequence)
    
56.         population.append(individual)
    
57.     return population
    
58. 
    
59. # 计算适应度
    
60. def calculate_fitness(population):
    
61.     for individual in population:
    
62.         individual.calculate_fitness()
    
63. 
    
64. # 选择操作
    
65. def selection(population):
    
66.     population.sort(key=lambda ind: ind.fitness, reverse=True)  # 按适应度排序
    
67.     selected = population[:POP_SIZE // 4]  # 选择适应度前 25% 的个体
    
68.     # 轮盘选择
    
69.     fitness_sum = sum(ind.fitness for ind in population)
    
70.     probabilities = [ind.fitness / fitness_sum for ind in population]
    
71.     cumulative_probabilities = np.cumsum(probabilities)
    
72.     while len(selected) < POP_SIZE:
    
73.         r = random.random()
    
74.         for i, cum_prob in enumerate(cumulative_probabilities):
    
75.             if r <= cum_prob:
    
76.                 selected.append(population[i])
    
77.                 break
    
78.     return selected
    
79. 
    
80. # 交叉操作
    
81. def crossover(selected):
    
82.     next_population = []
    
83.     while len(next_population) < POP_SIZE:
    
84.         parent1, parent2 = random.sample(selected, 2)
    
85.         if random.random() <= PC:  # 按照交叉概率进行交叉
    
86.             cross_point = random.randint(1, N_CITIES - 1)
    
87.             child1_sequence = parent1.sequence[:cross_point] + \
    
88.                               [city for city in parent2.sequence if city not in parent1.sequence[:cross_point]]
    
89.             child2_sequence = parent2.sequence[:cross_point] + \
    
90.                               [city for city in parent1.sequence if city not in parent2.sequence[:cross_point]]
    
91.             next_population.append(Individual(child1_sequence))
    
92.             next_population.append(Individual(child2_sequence))
    
93.         else:
    
94.             next_population.append(Individual(parent1.sequence))
    
95.             next_population.append(Individual(parent2.sequence))
    
96.     return next_population
    
97. 
    
98. # 变异操作
    
99. def mutation(population):
    
100.     for individual in population:
     
101.         if random.random() <= PM:  # 按照变异概率进行变异
     
102.             idx1, idx2 = random.sample(range(N_CITIES), 2)  # 随机选择两个城市进行交换
     
103.             individual.sequence[idx1], individual.sequence[idx2] = individual.sequence[idx2], individual.sequence[idx1]
     
104. 
     
105. # 遗传算法主函数
     
106. def genetic_algorithm():
     
107.     population = initialize_population()  # 初始化种群
     
108.     max_fitness_history = []  # 记录每代的最大适应度
     
109. 
     
110.     for generation in range(N_GENERATIONS):
     
111.         calculate_fitness(population)  # 计算适应度
     
112.         max_fitness = max(ind.fitness for ind in population)  # 找到最大适应度
     
113.         max_fitness_history.append(max_fitness)
     
114.         print(f"代数: {generation}, 最大适应度: {max_fitness}")
     
115. 
     
116.         selected = selection(population)  # 选择
     
117.         next_population = crossover(selected)  # 交叉
     
118.         mutation(next_population)  # 变异
     
119.         population = next_population  # 更新种群
     
120. 
     
121.     # 输出结果
     
122.     best_individual = max(population, key=lambda ind: ind.fitness)
     
123.     print("最佳路径:", "->".join(map(str, best_individual.sequence)))
     
124.     print("路径长度:", 50000 - best_individual.fitness)
     
125. 
     
126. if __name__ == "__main__":
     
127.     start_time = time.time()
     
128.     genetic_algorithm()
     
129.     print("总时间:", time.time() - start_time, "秒")

复制代码

yinda_peng

杂交的方式，轮盘赌，还有变异，这些可以自己调，可以有自己的规则，还有编码方式，适应度的计算函数，都可以改

FishC

遗传算法解决TSP问题的代码实现中，你已经提供了一个基本的框架。以下是一些需要补充和修正的地方：

1. **城市坐标**：需要填充`city_pos`列表，确保每个城市都有一个(x, y)坐标。

2. **个体类的路径计算**：在`calculate_fitness`方法中，`city1`和`city2`的索引需要正确设置。

3. **初始化种群**：`initialize_population`函数中需要初始化`population`列表。

4. **选择操作**：在`selection`函数中，`probabilities`需要计算每个个体的选择概率。

以下是修正后的代码片段：

1. # 城市坐标示例
   
2. city_pos = [
   
3.     (0, 0), (1, 1), (2, 2), (3, 3), (4, 4),
   
4.     (5, 5), (6, 6), (7, 7), (8, 8), (9, 9),
   
5.     (10, 10), (11, 11), (12, 12), (13, 13), (14, 14),
   
6.     (15, 15), (16, 16), (17, 17), (18, 18), (19, 19),
   
7.     (20, 20), (21, 21), (22, 22), (23, 23), (24, 24),
   
8.     (25, 25), (26, 26), (27, 27), (28, 28), (29, 29),
   
9.     (30, 30)
   
10. ]
    
11. 
    
12. # 计算路径的适应度
    
13. def calculate_fitness(self):
    
14.     total_distance = 0
    
15.     for i in range(N_CITIES):
    
16.         city1 = self.sequence[i]
    
17.         city2 = self.sequence[(i + 1) % N_CITIES]  # 回到起始城市
    
18.         total_distance += self.calculate_distance(city1, city2)
    
19.     self.fitness = 50000 - total_distance
    
20. 
    
21. # 初始化种群
    
22. def initialize_population():
    
23.     population = []
    
24.     for _ in range(POP_SIZE):
    
25.         sequence = list(range(N_CITIES))
    
26.         random.shuffle(sequence)
    
27.         individual = Individual(sequence)
    
28.         population.append(individual)
    
29.     return population
    
30. 
    
31. # 选择操作
    
32. def selection(population):
    
33.     population.sort(key=lambda ind: ind.fitness, reverse=True)
    
34.     selected = population[:int(0.25 * POP_SIZE)]
    
35.     fitness_sum = sum(ind.fitness for ind in population)
    
36.     probabilities = [ind.fitness / fitness_sum for ind in population]
    
37.     cumulative_probabilities = np.cumsum(probabilities)
    
38.     while len(selected) < POP_SIZE:
    
39.         r = random.random()
    
40.         for i, cum_prob in enumerate(cumulative_probabilities):
    
41.             if r < cum_prob:
    
42.                 selected.append(population[i])
    
43.                 break
    
44.     return selected

复制代码

请根据你的具体需求和城市坐标进行调整。希望这些修改能帮助你更好地实现遗传算法解决TSP问题！如果有其他问题，欢迎继续提问。

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。

FishC

yinda_peng 发表于 2024-10-11 20:10
杂交的方式，轮盘赌，还有变异，这些可以自己调，可以 ...

要实现遗传算法解决TSP问题，你可以根据自己的需求调整杂交、选择和变异的方式。以下是一些建议和代码补充：

### 杂交（交叉）

常用的杂交方法有部分映射交叉（PMX）、顺序交叉（OX）等。你可以选择其中一种或自己设计。

### 轮盘赌选择

轮盘赌选择是根据适应度概率选择个体。你需要计算每个个体的适应度概率，并使用累积概率进行选择。

### 变异

变异可以通过交换路径中的两个城市来实现，以增加种群的多样性。

### 代码补充

以下是对你提供的代码的补充和修正：

1. # 初始化种群
   
2. def initialize_population():
   
3.     population = []
   
4.     for _ in range(POP_SIZE):
   
5.         sequence = list(range(N_CITIES))
   
6.         random.shuffle(sequence)  # 随机打乱城市顺序
   
7.         individual = Individual(sequence)
   
8.         population.append(individual)
   
9.     return population
   
10. 
    
11. # 计算适应度
    
12. def calculate_fitness(population):
    
13.     for individual in population:
    
14.         individual.calculate_fitness()
    
15. 
    
16. # 选择操作
    
17. def selection(population):
    
18.     population.sort(key=lambda ind: ind.fitness, reverse=True)  # 按适应度排序
    
19.     selected = population[:POP_SIZE // 4]  # 选择适应度前 25% 的个体
    
20.     # 轮盘选择
    
21.     fitness_sum = sum(ind.fitness for ind in population)
    
22.     probabilities = [ind.fitness / fitness_sum for ind in population]
    
23.     cumulative_probabilities = np.cumsum(probabilities)
    
24.     while len(selected) < POP_SIZE:
    
25.         r = random.random()
    
26.         for i, cum_prob in enumerate(cumulative_probabilities):
    
27.             if r < cum_prob:
    
28.                 selected.append(population[i])
    
29.                 break
    
30.     return selected
    
31. 
    
32. # 交叉操作
    
33. def crossover(parent1, parent2):
    
34.     # 这里可以实现PMX或OX等交叉方法
    
35.     pass
    
36. 
    
37. # 变异操作
    
38. def mutate(individual):
    
39.     if random.random() < PM:
    
40.         idx1, idx2 = random.sample(range(N_CITIES), 2)
    
41.         individual.sequence[idx1], individual.sequence[idx2] = individual.sequence[idx2], individual.sequence[idx1]

复制代码

### 说明

- **初始化种群**：生成随机路径序列。
- **适应度计算**：根据路径总距离计算适应度。
- **选择**：使用轮盘赌选择适应度高的个体。
- **交叉和变异**：实现交叉和变异以生成新个体。

你可以根据需要调整这些方法的实现细节。希望这些信息对你有帮助！

以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。