Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· openaiHugging Face Suzhen/CodeChat

请利用遗传算法解决以下的旅行商问题:…

  1. User

    请利用遗传算法解决以下的旅行商问题: 一个旅行者需要到国内的10个城市旅行,各城市的坐标见下面。请设计一个合理的线路使旅行者所行的路程(坐标间距离,非球面距离)之和最小。注意:每个城市只能访问一次,且最后要回到原来出来的城市。 要求:输出适应度函数的进化曲线,展示线路的动态变化过程及最终的线路图。 城市编号 X坐标 Y坐标 1 16.47 96.1 2 16.47 94.44 3 20.09 92.54 4 22.39 93.37 5 25.23 97.24 6 17.2 96.29 7 16.3 97.38 8 14.05 98.12 9 16.53 97.38 10 21.52 95.59 实验语言不限给出代码

  2. Assistant

    由于遗传算法涉及到种群的初始化、适应度函数的定义、选择算子、交叉算子和变异算子等多个方面,本篇文章将会根据以上需求,给出完整的旅行商问题求解代码。

    首先,我们需要将城市的坐标数据读入程序中,并将其保存为数组的形式。

    代码如下:

    import numpy as np
    
    cities = np.array([[16.47, 96.1],
                       [16.47, 94.44],
                       [20.09, 92.54],
                       [22.39, 93.37],
                       [25.23, 97.24],
                       [17.2, 96.29],
                       [16.3, 97.38],
                       [14.05, 98.12],
                       [16.53, 97.38],
                       [21.52, 95.59]])
    num_cities = cities.shape[0]  # 城市数量
    

    接下来,我们需要定义适应度函数,即求出当前染色体代表的路径的总长度。这里使用欧几里得距离(即两点之间的直线距离)来计算路径长度。

    代码如下:

    def distance(path):
        total_distance = 0
        for i in range(num_cities-1):
            start, end = path[i], path[i+1]
            total_distance += np.sqrt(np.sum(np.square(cities[start] - cities[end])))
        # 最后加上回到出发城市的距离
        total_distance += np.sqrt(np.sum(np.square(cities[path[0]] - cities[path[-1]])))
        return total_distance
    

    然后,我们需要初始化种群。为了方便,这里直接使用随机数生成初始种群,其中种群规模为100,染色体长度为10,并且每个染色体均不包含相同的城市编号。

    代码如下:

    np.random.seed(42)
    population_size = 100  # 种群规模
    chromosome_length = num_cities  # 染色体长度
    population = np.empty((population_size, chromosome_length), dtype=int)
    for i in range(population_size):
        population[i] = np.random.permutation(num_cities)
    

    接下来,我们需要定义选择算子、交叉算子和变异算子。

    这里直接使用轮盘赌算法作为选择算子,交叉算子采用顺序交叉法(即将两个染色体从随机的位置切开,并将第二个染色体中未出现在第一个染色体中的城市按顺序插入到第一个染色体的对应位置),变异算子采用交换变异法(即随机选择两个位置,交换这两个位置上的城市编号)。

    代码如下:

    def select(pop, fitness):
        idx = np.random.choice(population_size, size=2,
                               replace=False, p=fitness/fitness.sum())
        return pop[idx]
    
    def crossover(parent1, parent2):
        p1, p2 = np.sort(np.random.randint(0, chromosome_length, size=2))
        child1 = np.array([-1] * chromosome_length)
        child1[p1:p2+1] = parent1[p1:p2+1]
        idx = p2 + 1
        for i in range(num_cities):
            if idx == num_cities:
                idx = 0
            if parent2[i] not in child1:
                child1[idx] = parent2[i]
                idx += 1
        return child1
    
    def mutation(chromosome):
        idx1, idx2 = np.random.permutation(num_cities)[:2]
        chromosome[idx1], chromosome[idx2] = chromosome[idx2], chromosome[idx1]
        return chromosome
    

    接下来,我们需要对种群进行迭代优化,直到达到预设的最大迭代次数(这里取200)或者取得了最优解。其中,每一代种群中的适应度最小值和平均值均会被记录下来,以便后续绘制进化曲线。

    我们的遗传算法迭代优化流程如下:

    1. 计算种群中每个染色体的适应度。
    2. 根据适应度计算出每个染色体的选择概率。
    3. 从种群中选择两个染色体进行交叉操作,然后进行变异操作,产生一个新的染色体。将新染色体加入到后代种群中。
    4. 根据精英选择策略,将当前种群的最优染色体加入到下一代种群中。
    5. 计算下一代种群的适应度,更新最优染色体。
    6. 如果满足结束条件,则跳出循环。

    代码如下:

    max_iter = 200  # 最大迭代次数
    elite_ratio = 0.1  # 精英选择比例
    mutation_rate = 0.1  # 变异概率
    fitness_history = []  # 记录适应度函数的进化曲线
    best_path = None  # 记录最优路径
    best_distance = float('inf')  # 记录最短路径长度
    for i in range(max_iter):
        # 计算适应度函数
        fitness = np.array([1/distance(p) for p in population])
        # 记录适应度函数的进化曲线
        fitness_history.append(fitness.min())
        # 精英选择策略
        elite_population = population[np.argsort(fitness)[-int(elite_ratio*population_size):]]
        new_population = elite_population.copy()
        # 生成新一代种群
        while len(new_population) < population_size:
            # 选择两个染色体进行交叉操作
            parent1, parent2 = select(population, fitness)
            child = crossover(parent1, parent2)
            # 对新染色体进行变异操作
            if np.random.rand() < mutation_rate:
                child = mutation(child)
            new_population = np.vstack([new_population, child])
        population = new_population
        # 更新最优路径
        min_distance_idx = np.argmin(fitness)
        if fitness[min_distance_idx] < best_distance:
            best_path = population[min_distance_idx].copy()
            best_distance = fitness[min_distance_idx]
        print("Iteration {:3d}: shortest distance = {:.5f}".format(i+1, best_distance))
    
    print("Best path found:")
    print(best_path)
    

    接下来,我们绘制适应度函数的进化曲线。

    代码如下:

    import matplotlib.pyplot as plt
    
    plt.plot(fitness_history)
    plt.xlabel('Generation')
    plt.ylabel('Fitness')
    plt.show()
    

    最后,我们可以使用matplotlib绘制出最优路径。

    代码如下:

    fig, ax = plt.subplots()
    ax.plot(cities[:, 0], cities[:, 1], 'o', label='Cities')
    ax.plot(cities[best_path, 0], cities[best_path, 1], 'r-', label='Path')
    ax.plot(cities[[best_path[-1], best_path[0]], 0], cities[[best_path[-1], best_path[0]], 1], 'r-', label='Return')
    plt.legend()
    plt.show()
    

    完整代码如下:

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.