一、 TSP 问题

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

二、求解算法

下面使用遗传算法对此 TSP 问题求近似解
主要运行代码如下：

# coding:utf:8

import numpy as np

import random

import matplotlib . pyplot as plt

from matplotlib . ticker import FormatStrFormatter

import operator

import time

import pandas as pd

 

from tsp1 . mutations import select_best_mutaion

 

 

def 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 长的 population

def 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_individual

 

 

def 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 distmat

 

 

if __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 ()

 

·        1

·        2

·        3

·        4

·        5

·        6

·        7

·        8

·        9

·        10

·        11

·        12

·        13

·        14

·        15

·        16

·        17

·        18

·        19

·        20

·        21

·        22

·        23

·        24

·        25

·        26

·        27

·        28

·        29

·        30

·        31

·        32

·        33

·        34

·        35

·        36

·        37

·        38

·        39

·        40

·        41

·        42

·        43

·        44

·        45

·        46

·        47

·        48

·        49

·        50

·        51

·        52

·        53

·        54

·        55

·        56

·        57

·        58

·        59

·        60

·        61

·        62

·        63

·        64

·        65

·        66

·        67

·        68

·        69

·        70

·        71

·        72

·        73

·        74

·        75

·        76

·        77

·        78

·        79

·        80

·        81

·        82

·        83

·        84

·        85

·        86

·        87

·        88

·        89

·        90

·        91

·        92

·        93

·        94

·        95

·        96

·        97

·        98

·        99

·        100

·        101

·        102

·        103

·        104

·        105

·        106

·        107

·        108

·        109

·        110

·        111

·        112

·        113

·        114

·        115

·        116

·        117

·        118

·        119

·        120

·        121

·        122

·        123

·        124

·        125

·        126

·        127

·        128

·        129

·        130

·        131

·        132

·        133

·        134

·        135

·        136

·        137

·        138

·        139

·        140

·        141

·        142

·        143

·        144

·        145

·        146

·        147

·        148

·        149

·        150

·        151

·        152

·        153

·        154

·        155

·        156

·        157

·        158

·        159

·        160

·        161

·        162

·        163

·        164

·        165

·        166

·        167

·        168

·        169

·        170

·        171

·        172

·        173

·        174

·        175

·        176

·        177

·        178

·        179

·        180

·        181

·        182

·        183

·        184

·        185

·        186

·        187

·        188

·        189

·        190

·        191

·        192

·        193

·        194

·        195

·        196

·        197

·        198

·        199

·        200

·        201

·        202

·        203

·        204

·        205

·        206

·        207

·        208

·        209

·        210

·        211

·        212

·        213

·        214

·        215

·        216

·        217

·        218

·        219

·        220

·        221

·        222

·        223

·        224

·        225

·        226

·        227

·        228

·        229

·        230

·        231

·        232

·        233

·        234

·        235

·        236

·        237

·        238

·        239

·        240

·        241

·        242

·        243

·        244

·        245

·        246

·        247

·        248

·        249

·        250

·        251

·        252

·        253

·        254

·        255

·        256

·        257

mutations.py

# coding:utf:8

import random

 

 

# SMB

def 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

 

 

# irgibnnm

def 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

 

·        1

·        2

·        3

·        4

·        5

·        6

·        7

·        8

·        9

·        10

·        11

·        12

·        13

·        14

·        15

·        16

·        17

·        18

·        19

·        20

·        21

·        22

·        23

·        24

·        25

·        26

·        27

·        28

·        29

·        30

·        31

·        32

·        33

·        34

·        35

·        36

·        37

·        38

·        39

·        40

·        41

·        42

·        43

·        44

·        45

·        46

·        47

·        48

·        49

·        50

·        51

·        52

·        53

·        54

·        55

·        56

·        57

·        58

·        59

·        60

·        61

·        62

·        63

·        64

·        65

·        66

·        67

·        68

·        69

·        70

·        71

·        72

·        73
迭代次数与距离的关系

data1.csv

Beijing,116.41667,39.91667

shanghai,121.43333,34.5

tianjin,117.2,39.13333

guangzhou,113.23333,23.16667

zhuhai,113.51667,22.3

hangzhou,120.2,30.26667

chongqing,106.45,29.5667

qingdao,120.33333,36.03333

fuzhou,119.3,26.08333

lanzhou,103.73333,36.03333

nanchang,115.9,28.68333

nanjing,118.78333,32.05

shenyang,123.38333,41.8

zhengzhou,113.65,34.76667

wuhan,114.31667,30.51667

xian,108.95,34.26667

changchun,125.35,43.8833

haikou,110.35,20.01667

guiyang,106.71667,26.56667

changsha,113,28.2

·        1

·        2

·        3

·        4

·        5

·        6

·        7

·        8

·        9

·        10

·        11

·        12

·        13

·        14

·        15

·        16

·        17

·        18

·        19

·        20

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, 长沙

·        1

·        2

·        3

·        4

·        5

·        6

·        7

·        8

·        9

·        10

·        11

·        12

·        13

·        14

·        15

·        16

·        17

·        18

·        19

·        20

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