本文共 8747 字，大约阅读时间需要 29 分钟。

一、TSP问题

TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。简单示例如下图所示：

二、求解算法

下面使用遗传算法对此TSP问题求近似解，不了解此算法的同学请先移步此知乎链接：

最终效果如下图

# coding:utf:8import numpy as npimport randomimport matplotlib.pyplot as pltfrom matplotlib.ticker import FormatStrFormatterimport operatorimport timeimport pandas as pdfrom tsp1.mutations import select_best_mutaiondef main():    global p_mutation, max_generation    generation = 1    population_cur = init_population()    fitness = get_fitness(population_cur)    time_start = time.time()    # 终止条件    while generation < max_generation:        # 父代最好的留1/4活下来        population_next = select_sorted_population(fitness, population_cur, population_size // 4)        # 杂交        for i in range(population_size):            p1, p2 = selection(fitness, 2)            child1, child2 = crossover(population_cur[p1], population_cur[p2])            # 变异            if random.random() < p_mutation:                child1 = select_best_mutaion(child1, distmat)            if random.random() < p_mutation:                child2 = select_best_mutaion(child2, distmat)            population_next.append(child1)            population_next.append(child2)        # 选出下一代的种群        population_next = select_sorted_population(get_fitness(population_next), population_next, population_size)        # 找出精英记录下来        pre_max_fitness, pre_max_individual = get_elite(fitness, population_cur)        record(pre_max_fitness)        # 换代        population_cur = population_next        generation += 1        # 更新fitness        fitness = get_fitness(population_cur)    # 记录并画图    final_fitness, final_individual = get_elite(fitness, population_cur)    record(final_fitness)    time_end = time.time()    print('进化花费时间：', time_end - time_start)    print('最后的路径距离（km）：', get_distance(final_individual) * 111)    plot(final_individual)    return# 排序，并且返回length长的populationdef select_sorted_population(fitness, population, length):    global population_size    sort_dict = {
   }    for i in range(len(population)):        sort_dict[(fitness[i], 1 / fitness[i])] = i    sorted_key = sorted(sort_dict.keys(), key=operator.itemgetter(0), reverse=True)    sorted_index = [sort_dict[i] for i in sorted_key]    sorted_population = [population[i] for i in sorted_index]    return sorted_population[:length]# 画图def plot(sequence):    global record_distance, coordinates    plt.figure(figsize=(15, 6))    plt.subplot(121)    plt.plot(record_distance)    plt.ylabel('distance')    plt.xlabel('iteration ')    plt.subplot(122)    x_list = []    y_list = []    for i in range(len(sequence)):        lat = coordinates[sequence[i]][0]        lon = coordinates[sequence[i]][1]        x_list.append(lat)        y_list.append(lon)        for one in name.itertuples(index=False):            lat1 = one[0]            if lat1 == lat:                lon1 = one[1]                if lon1 == lon:                    # 显示城市名                    city = one[2]                    plt.text(lat, lon, city)                    print(city)                    print(' |')                    break    lat = coordinates[sequence[0]][0]    lon = coordinates[sequence[0]][1]    x_list.append(lat)    y_list.append(lon)    for one in name.itertuples(index=False):        lat1 = one[0]        if lat1 == lat:            lon1 = one[1]            if lon1 == lon:                # 显示城市名                city = one[2]                print(city)                break    plt.plot(x_list, y_list, 'c-', label='Route')    plt.plot(x_list, y_list, 'ro', label='Location')    # 防止科学计数法    ax = plt.gca()    ax.xaxis.set_major_formatter(FormatStrFormatter('%.2f'))    ax.yaxis.set_major_formatter(FormatStrFormatter('%.2f'))    plt.xlabel("Longitude")    plt.ylabel("Latitude")    plt.title("Tsp Route")    plt.rcParams['font.sans-serif'] = ['SimHei']  # 显示中文标签    plt.rcParams['axes.unicode_minus'] = False  # 这两行需要手动设置    plt.grid(True)    plt.legend()    plt.show()# 获取最好的数据def get_elite(fitness, population):    max_index = fitness.index(max(fitness))    max_fitness = fitness[max_index]    max_individual = population[max_index]    return max_fitness, max_individualdef record(f):    global record_distance    # 经纬度转千米的单位要乘以111    record_distance.append(1 / f * 111)# 轮赌盘选择算子def selection(fitness, num):    def select_one(fitness, fitness_sum):        size = len(fitness)        i = random.randint(0, size - 1)        while True:            if random.random() < fitness[i] / fitness_sum:                return i            else:                i = (i + 1) % size    res = set()    fitness_sum = sum(fitness)    while len(res) < num:        t = select_one(fitness, fitness_sum)        res.add(t)    return res# 获得一个旅行路径的距离def get_distance(sequence):    global distmat    cost = 0    for i in range(len(sequence)):        cost += distmat[sequence[i - 1]][sequence[i]]    return cost# 计算适应值def get_fitness(population):    fitness = []    for i in range(len(population)):        fitness.append(1 / get_distance(population[i]))    return fitness# 杂交算子def crossover(parent1, parent2):    global individual_size    a = random.randint(1, individual_size - 1)    child1, child2 = parent1[:a], parent2[:a]    for i in range(individual_size):        if parent2[i] not in child1:            child1.append(parent2[i])        if parent1[i] not in child2:            child2.append(parent1[i])    return child1, child2# 初始化种群def init_population():    global individual_size, population_size    population_init = []    for i in range(population_size):        l = list(range(individual_size))        population_init.append(random.sample(l, individual_size))    return population_init# 获得城市之间的距离矩阵def get_distmat(M):    length = M.shape[0]    distmat = np.zeros((length, length))    for i in range(length):        for j in range(i + 1, length):            distmat[i][j] = distmat[j][i] = np.linalg.norm(M[i] - M[j])    return distmatif __name__ == "__main__":    # 准备数据    file = 'data1.csv'    demo = 'demo.csv'    coordinates = pd.read_csv(file, usecols=[1, 2], header=None).values    name = pd.read_csv(demo, usecols=[0, 1, 2], encoding='gbk', header=None)    distmat = get_distmat(coordinates)    # 参数初始化    individual_size = coordinates.shape[0]    max_generation = 3500    population_size = 10    p_mutation = 0.2    record_distance = []    # 运行    main()

mutations.py

# coding:utf:8import random# SMBdef select_best_mutaion(s, distmat):    s_res = [slide_mutation(s[:]), inversion_mutation(s[:]), irgibnnm_mutation(s[:], distmat)]    res = [get_distance(s_res[0], distmat), get_distance(s_res[1], distmat), get_distance(s_res[2], distmat)]    min_index = res.index(min(res))    return s_res[min_index]# 滑动变异def slide_mutation(s):    a, b = get_two_randint(len(s))    t = s[a]    for i in range(a + 1, b + 1):        s[i - 1] = s[i]    s[b] = t    return s# 获得一个旅行路径的距离def get_distance(sequence, distmat):    cost = 0    for i in range(len(sequence)):        cost += distmat[sequence[i - 1]][sequence[i]]    return cost# 倒置变异def inversion_mutation(s):    # 自己手写的2变换    a, b = get_two_randint(len(s))    for i in range(a, (a + b) // 2 + 1):        s[i], s[b + a - i] = s[b + a - i], s[i]    return s# 返回（小，大）两个随机数def get_two_randint(size):    b = a = random.randint(0, size - 1)    while a == b:        b = random.randint(0, size - 1)    if a > b:        return b, a    return a, b# irgibnnmdef irgibnnm_mutation(s, distmat):    a, b = get_two_randint(len(s))    # 先inversion    for i in range(a, (a + b) // 2 + 1):        s[i], s[b + a - i] = s[b + a - i], s[i]    # 再RGIBNNM    b = (b + 1) % len(s)    min = b - 1    for i in range(len(s)):        if i == b:            continue        if distmat[b][min] > distmat[b][i]:            min = i    s[b], s[min - 4] = s[min - 4], s[b]    return s

运行结果示例，只截图了一半

Beijing,116.41667,39.91667shanghai,121.43333,34.5tianjin,117.2,39.13333guangzhou,113.23333,23.16667zhuhai,113.51667,22.3hangzhou,120.2,30.26667chongqing,106.45,29.5667qingdao,120.33333,36.03333fuzhou,119.3,26.08333lanzhou,103.73333,36.03333nanchang,115.9,28.68333nanjing,118.78333,32.05shenyang,123.38333,41.8zhengzhou,113.65,34.76667wuhan,114.31667,30.51667xian,108.95,34.26667changchun,125.35,43.8833haikou,110.35,20.01667guiyang,106.71667,26.56667changsha,113,28.2

demo.csv

116.41667,39.91667,北京121.43333,34.5,上海117.2,39.13333,天津113.23333,23.16667,广州113.51667,22.3,珠海120.2,30.26667,杭州106.45,29.5667,重庆120.33333,36.03333,青岛119.3,26.08333,福州103.73333,36.03333,兰州115.9,28.68333,南昌118.78333,32.05,南京123.38333,41.8,沈阳113.65,34.76667,郑州114.31667,30.51667,武汉108.95,34.26667,西安125.35,43.8833,长春110.35,20.01667,海口106.71667,26.56667,贵阳113,28.2,长沙

如需更换城市找到相关城市的经纬度，修改此文件即可。

转载地址：http://pugdf.baihongyu.com/