Python遗传算法解TSP
专业选修课人工智能概论讲了遗传算法（GA），老师说让我们做一下遗传算法解TSP，刚好暑假搞数学建模学了点遗传算法，代码嘛，套着GA的模版改一改，就可以解TSP了首先简单介绍一下遗传算法解TSP的基本思路：[*]初始化：随机生成一定数量的个体（路径序列），每个个体表示一条旅行路线。
[*]适应度评估：计算每条路径的总距离，将距离转化为适应度值（适应度与路径长度成反比）。
[*]选择：通过轮盘赌选择或其他选择机制，选择适应度较高的个体进入下一代。
[*]交叉：随机选择一对个体，并在其路径中交叉生成新个体。
[*]变异：随机选择个体并在其路径中交换城市，以增加多样性。
[*]迭代：重复进行评估、选择、交叉和变异，直到达到指定代数或收敛条件。
[*]输出结果：返回适应度最高的路径及其长度。
import random
import math
import numpy as np
import time
# 相关的系数
PC = 0.55# 交叉概率
PM = 0.05 # 变异概率
POP_SIZE = 100# 种群规模
N_GENERATIONS = 700# 进化代数
N_CITIES = 31# 城市数量
SEED = 20# 随机种子
# 城市坐标
city_pos = [
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
, , , , ,
]
# 定义个体类
class Individual:
def __init__(self, sequence):
self.sequence = sequence# 城市访问序列
self.fitness = 0# 适应度
self.p_fitness = 0# 适应度概率
self.sum_p_fitness = 0# 累加适应度概率
# 计算路径的适应度
def calculate_fitness(self):
total_distance = 0# 总的距离
for i in range(N_CITIES):
city1 = self.sequence
city2 = self.sequence[(i + 1) % N_CITIES]# 回到起始城市
total_distance += self.calculate_distance(city1, city2)
self.fitness = 50000 - total_distance# 适应度越高越好
# 计算两个城市之间的距离
@staticmethod
def calculate_distance(city1, city2):
x1, y1 = city_pos
x2, y2 = city_pos
return math.sqrt((x1 - x2) ** 2 + (y1 - y2) ** 2)
# 初始化种群
def initialize_population():
population = []
for _ in range(POP_SIZE):
sequence = list(range(1, N_CITIES + 1))
random.shuffle(sequence)# 随机打乱城市顺序
individual = Individual(sequence)
population.append(individual)
return population
# 计算适应度
def calculate_fitness(population):
for individual in population:
individual.calculate_fitness()
# 选择操作
def selection(population):
population.sort(key=lambda ind: ind.fitness, reverse=True)# 按适应度排序
selected = population[:POP_SIZE // 4]# 选择适应度前 25% 的个体
# 轮盘选择
fitness_sum = sum(ind.fitness for ind in population)
probabilities =
cumulative_probabilities = np.cumsum(probabilities)
while len(selected) < POP_SIZE:
r = random.random()
for i, cum_prob in enumerate(cumulative_probabilities):
if r <= cum_prob:
selected.append(population)
break
return selected
# 交叉操作
def crossover(selected):
next_population = []
while len(next_population) < POP_SIZE:
parent1, parent2 = random.sample(selected, 2)
if random.random() <= PC:# 按照交叉概率进行交叉
cross_point = random.randint(1, N_CITIES - 1)
child1_sequence = parent1.sequence[:cross_point] + \
]
child2_sequence = parent2.sequence[:cross_point] + \
]
next_population.append(Individual(child1_sequence))
next_population.append(Individual(child2_sequence))
else:
next_population.append(Individual(parent1.sequence))
next_population.append(Individual(parent2.sequence))
return next_population
# 变异操作
def mutation(population):
for individual in population:
if random.random() <= PM:# 按照变异概率进行变异
idx1, idx2 = random.sample(range(N_CITIES), 2)# 随机选择两个城市进行交换
individual.sequence, individual.sequence = individual.sequence, individual.sequence
# 遗传算法主函数
def genetic_algorithm():
population = initialize_population()# 初始化种群
max_fitness_history = []# 记录每代的最大适应度
for generation in range(N_GENERATIONS):
calculate_fitness(population)# 计算适应度
max_fitness = max(ind.fitness for ind in population)# 找到最大适应度
max_fitness_history.append(max_fitness)
print(f"代数: {generation}, 最大适应度: {max_fitness}")
selected = selection(population)# 选择
next_population = crossover(selected)# 交叉
mutation(next_population)# 变异
population = next_population# 更新种群
# 输出结果
best_individual = max(population, key=lambda ind: ind.fitness)
print("最佳路径:", "->".join(map(str, best_individual.sequence)))
print("路径长度:", 50000 - best_individual.fitness)
if __name__ == "__main__":
start_time = time.time()
genetic_algorithm()
print("总时间:", time.time() - start_time, "秒")
杂交的方式，轮盘赌，还有变异，这些可以自己调，可以有自己的规则，还有编码方式，适应度的计算函数，都可以改 遗传算法解决TSP问题的代码实现中，你已经提供了一个基本的框架。以下是一些需要补充和修正的地方：
1. **城市坐标**：需要填充`city_pos`列表，确保每个城市都有一个(x, y)坐标。
2. **个体类的路径计算**：在`calculate_fitness`方法中，`city1`和`city2`的索引需要正确设置。
3. **初始化种群**：`initialize_population`函数中需要初始化`population`列表。
4. **选择操作**：在`selection`函数中，`probabilities`需要计算每个个体的选择概率。
以下是修正后的代码片段：
# 城市坐标示例
city_pos = [
(0, 0), (1, 1), (2, 2), (3, 3), (4, 4),
(5, 5), (6, 6), (7, 7), (8, 8), (9, 9),
(10, 10), (11, 11), (12, 12), (13, 13), (14, 14),
(15, 15), (16, 16), (17, 17), (18, 18), (19, 19),
(20, 20), (21, 21), (22, 22), (23, 23), (24, 24),
(25, 25), (26, 26), (27, 27), (28, 28), (29, 29),
(30, 30)
]
# 计算路径的适应度
def calculate_fitness(self):
total_distance = 0
for i in range(N_CITIES):
city1 = self.sequence
city2 = self.sequence[(i + 1) % N_CITIES]# 回到起始城市
total_distance += self.calculate_distance(city1, city2)
self.fitness = 50000 - total_distance
# 初始化种群
def initialize_population():
population = []
for _ in range(POP_SIZE):
sequence = list(range(N_CITIES))
random.shuffle(sequence)
individual = Individual(sequence)
population.append(individual)
return population
# 选择操作
def selection(population):
population.sort(key=lambda ind: ind.fitness, reverse=True)
selected = population[:int(0.25 * POP_SIZE)]
fitness_sum = sum(ind.fitness for ind in population)
probabilities =
cumulative_probabilities = np.cumsum(probabilities)
while len(selected) < POP_SIZE:
r = random.random()
for i, cum_prob in enumerate(cumulative_probabilities):
if r < cum_prob:
selected.append(population)
break
return selected
请根据你的具体需求和城市坐标进行调整。希望这些修改能帮助你更好地实现遗传算法解决TSP问题！如果有其他问题，欢迎继续提问。
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。 yinda_peng 发表于 2024-10-11 20:10
杂交的方式，轮盘赌，还有变异，这些可以自己调，可以 ...
要实现遗传算法解决TSP问题，你可以根据自己的需求调整杂交、选择和变异的方式。以下是一些建议和代码补充：
### 杂交（交叉）
常用的杂交方法有部分映射交叉（PMX）、顺序交叉（OX）等。你可以选择其中一种或自己设计。
### 轮盘赌选择
轮盘赌选择是根据适应度概率选择个体。你需要计算每个个体的适应度概率，并使用累积概率进行选择。
### 变异
变异可以通过交换路径中的两个城市来实现，以增加种群的多样性。
### 代码补充
以下是对你提供的代码的补充和修正：
# 初始化种群
def initialize_population():
population = []
for _ in range(POP_SIZE):
sequence = list(range(N_CITIES))
random.shuffle(sequence)# 随机打乱城市顺序
individual = Individual(sequence)
population.append(individual)
return population
# 计算适应度
def calculate_fitness(population):
for individual in population:
individual.calculate_fitness()
# 选择操作
def selection(population):
population.sort(key=lambda ind: ind.fitness, reverse=True)# 按适应度排序
selected = population[:POP_SIZE // 4]# 选择适应度前 25% 的个体
# 轮盘选择
fitness_sum = sum(ind.fitness for ind in population)
probabilities =
cumulative_probabilities = np.cumsum(probabilities)
while len(selected) < POP_SIZE:
r = random.random()
for i, cum_prob in enumerate(cumulative_probabilities):
if r < cum_prob:
selected.append(population)
break
return selected
# 交叉操作
def crossover(parent1, parent2):
# 这里可以实现PMX或OX等交叉方法
pass
# 变异操作
def mutate(individual):
if random.random() < PM:
idx1, idx2 = random.sample(range(N_CITIES), 2)
individual.sequence, individual.sequence = individual.sequence, individual.sequence
### 说明
- **初始化种群**：生成随机路径序列。
- **适应度计算**：根据路径总距离计算适应度。
- **选择**：使用轮盘赌选择适应度高的个体。
- **交叉和变异**：实现交叉和变异以生成新个体。
你可以根据需要调整这些方法的实现细节。希望这些信息对你有帮助！
以上回复来自 FishC AI 小助理，如未能正确解答您的问题，请继续追问。
页:
[1]