Python遗传算法解TSP

yinda_peng

专业选修课人工智能概论讲了遗传算法（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 = [
    [1304, 2312], [3639, 1315], [4177, 2244], [3712, 1399], [3488, 1535],
    [3326, 1556], [3238, 1229], [4196, 1004], [4312, 790], [4386, 570],
    [3007, 1970], [2562, 1756], [2788, 1491], [2381, 1676], [1332, 695],
    [3715, 1678], [3918, 2179], [4061, 2370], [3780, 2212], [3676, 2578],
    [4029, 2838], [4263, 2931], [3429, 1908], [3507, 2367], [3394, 2643],
    [3439, 3201], [2935, 3240], [3140, 3550], [2545, 2357], [2778, 2826],
    [2370, 2975]
]

# 定义个体类
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[i]
            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[city1 - 1]
        x2, y2 = city_pos[city2 - 1]
        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 = [ind.fitness / fitness_sum for ind in population]
    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[i])
                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] + \
                              [city for city in parent2.sequence if city not in parent1.sequence[:cross_point]]
            child2_sequence = parent2.sequence[:cross_point] + \
                              [city for city in parent1.sequence if city not in 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[idx1], individual.sequence[idx2] = individual.sequence[idx2], individual.sequence[idx1]

# 遗传算法主函数
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, "秒")

yinda_peng

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

FishC

遗传算法解决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[i]
        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 = [ind.fitness / fitness_sum for ind in population]
    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[i])
                break
    return selected

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

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

FishC

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 = [ind.fitness / fitness_sum for ind in population]
    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[i])
                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[idx1], individual.sequence[idx2] = individual.sequence[idx2], individual.sequence[idx1]

### 说明

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

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

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