遗传算法-求解TSP问题

其他 评论

基本思路

代码实现

1）主函数

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
#主函数
def main():
    #设置初始参数
    port_num = 10 #节点的个数
    size = 500  # 种群个体数量
    iter = 1000 #演化代数
    pc = 0.8 # 杂交概率
    pm = 0.1  # 变异概率
    x_range = 500 #节点所在范围
    y_range = 500
     
    #生成节点坐标
    x,y = create_coordinate(port_num, x_range, y_range)
     
    #查看节点位置
    plt.scatter(x,y, c='r', s=15) #生成散点图，每个点就是要展示的个体
    plt.title("节点位置")
    plt.show() #画出图像
     
     
    #生成种群基因
    gene = creat_gene(port_num,size)
     
    #记录每代最优个体
    best_x = []
    best_y = []
     
    #进行迭代
    for i in range(iter):
        fit = fitness(gene,x,y) #计算适应度
         
        best_gene,best_fit = best(gene,fit) #找出当代最优解
        best_x.append(best_gene)
        best_y.append(best_fit)
         
        gene = selection(gene,fit) #选择新个体，更新基因
        gene = crossover(gene, pc) #杂交
        gene = mutation(gene,pm) #变异
 
    #找出最优结果
    most_best_fit = min(best_y)
    most_best_gene = best_x[best_y.index(most_best_fit)]
     
     
    way(most_best_gene,x,y)#查看最终路径
    plot_iter_curve(iter,best_y)
    print('最优解为：\n路线:',most_best_gene , '\nD=',min(best_y),'米')

主函数展示了算法的整体思路，即

①确定各参数（节点数量、种群数量、演化代数、杂交及变异概率、节点取值范围）

②确定节点坐标

③产生初代个体基因

④对个体进行评价并选出当代最优个体

⑤重新生成新的种群（通过重新选择、交叉、变异产生）

重复④⑤直到满足设定的迭代次数

得到迭代过程中的最优解

2）节点坐标生成

1
2
3
4
5
6
7
8
9
10
#生成节点坐标
def create_coordinate(port_num, x_range, y_range):
    x = []
    y = []
    for i in range(port_num):
        x1 = random.randint(0, x_range)
        y1 = random.randint(0, y_range)
        x.append(x1)
        y.append(y1)
    return x,y

TSP问题中，节点位置是固定的，可以从外部导入。此处没有固定数据，因此使用随机生成的点

3）生成种群基因

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#生成种群基因
def creat_gene(port_num,size):
    all_point = [x for x in range(port_num)]
    allin = []
    for i in range(size):
        point_all = all_point[:]
        d = []
        for j in range(len(point_all)):
            c = len(point_all)
            b = random.randint(0,c-1)
            a = point_all.pop(b)
            d.append(a)
        allin.append(d)
    return allin

对于TSP问题，因为节点本身可以进行编号，因此种群基因可以直接使用节点编号进行表示，如[1,3,2,4,7,6,5]…

具体生成思路为：产生包含所有节点编号的列表，如[0,1,2,3,4,5,6,7]（节点从0编号），之后循环，每次随机取出列表一个元素，直到把列表中元素取完，则生成一个个体。因为每次取的元素随机，因此产生的个体是随机的

4）计算适应度

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#计算适应度
def fitness(gene,x,y):
    fit = []
    for i in range(len(gene)):
        one_gene = gene[i]
        xx = []
        yy = []
        for j in one_gene:
            xx.append(x[j])
            yy.append(y[j])
        distence = 0
        for k in range(len(xx)-1):
            dis = math.sqrt(pow((xx[k]-xx[k+1]),2)+pow((yy[k]-yy[k+1]),2))
            distence += dis
        distence = round(distence,3)
        fit.append(distence)
    return fit

适应度即根据个体基因，从第一点到最后一点，每两点间的距离相加

5）选出当代最优个体

1
2
3
4
5
#找出最优解
def best(gene,fit):
    value_y = min(fit) #找出y列表中的最小值
    value_x = gene[fit.index(value_y)] #index()返回数值所在列表对应的索引值
    return value_x,value_y

此处注意是找最小值

6）轮盘赌选择个体

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
#轮盘赌选个体
def selection(gene,fit):
    value_rate = []
    fit_reciprocal = [100/i for i in fit]
     
    # 适应度总和
    total_fit = sum(fit_reciprocal)
     
    # 归一化，使概率总和为1
    for i in range(len(fit_reciprocal)):
        value_rate.append(fit_reciprocal[i] / total_fit)
    value_rate = np.cumsum(value_rate)
     
    #产生新种群个体的个数
    x_len = len(gene)
     
    # 轮盘赌每次的概率值
    ms = sorted([random.random() for i in range(x_len)])
     
    #轮盘赌选出个体
    fitin = 0
    newin = 0
    new_gene = gene[:]
    # 转轮盘选择法
    while newin < x_len:
        # 如果这个概率大于随机出来的那个概率，就选这个
        if (ms[newin] < value_rate[fitin]):
            new_gene[newin] = gene[fitin]
            newin = newin + 1
        else:
            fitin = fitin + 1
    return new_gene

轮盘赌选择个体的思路同上一篇，实际调试中出现了所选个体值越来越大，即每代越来越差的状况，原因如下：

越优化越差是因为我直接套用了遗传算法的selection，那个是求最大值的，而TSP要求的是最小值。
解决方案：selection函数里面把适应度取倒数，小的变大，然后再选个体。通过索引还是能对上基因型的，就实现了选出较小值

在实际使用中，对适应度取倒之后又放大了100倍。这是考虑到原适应度值几千，取倒后太小，再进行归一化的时候区分度太小。（但实际好像没什么影响，因为取倒计算结果的精度足够高）

7）杂交

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
#杂交
def crossover(gene, pc):
    # 一定概率杂交，主要是杂交种群种相邻的两个个体
    pop = gene[:]
    pop_len = len(pop)
    i = 0
    while i < pop_len :
        # 随机看看达到杂交概率没
        if (random.random() < pc):
            #随机选取两个个体进行杂交
            rand1 = random.randint(0, len(pop)-1)
            rand2 = random.randint(0, len(pop)-1)
 
 
            # 随机选取杂交点
            cpoint = random.randint(1, len(gene[0])-1)
 
            #路线不重复，因此
            out1 = gene[rand1]
            out2 = gene[rand2]
             
 
            part1 = out1[0:cpoint]
            part2 = out1[cpoint:]
             
            if out1 == out2:
                new1 = out1
                new2 = out2
            else:
                new11 = [i for i in out2 if i not in part1]
                new22 = [i for i in out2 if i not in part2]
 
                new1 = part1 + new11
                new2 = new22 + part2
 
 
            pop[i] = new1
            pop[i+1] = new2
        i+=2
    return pop

此处杂交与上一篇类似，不同在于：

TSP要求节点不重复，因此直接杂交大部分不符合

解决方法：对两条染色体，第一条从杂交点切开得到前后两段；之后，第一条染色体前半段基因+第二条染色体消除前半段所含基因后剩余的基因（消除后剩余基因顺序不变）得到新的染色体①；第二条染色体消除后半段所含基因后剩余的基因（消除后剩余基因顺序不变）+第一条染色体后半段基因，得到新染色体②

如果随机选出的两个染色体相同（优化到后期），则直接将其当做新的染色体①②

8）基因突变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#基因突变(交换两个基因的位置)
def mutation(gene,pm):
    pop = gene[:]
    px = len(pop)
    py = len(pop[0])
    #py = 10
    # 每条染色体随便选一个杂交
    for i in range(px):
        if (random.random() < pm):
            mpoint1 = random.randint(0, py - 1)
            mpoint2 = random.randint(0, py - 1)
            a = pop[i][mpoint1]
            b = pop[i][mpoint2]
            pop[i][mpoint1] = b
            pop[i][mpoint2] = a
    return pop

在基因突变环节，同样有节点不重复的要求，因此对染色体随机选出两点，进行点对点交换

tips：如果随机出来的两个点都是正中间，则变异后染色体仍不变

9）迭代过程中每代最优解变化

1
2
3
4
5
6
7
#查看迭代过程中结果变化
def plot_iter_curve(iter, results):
    X = [i for i in range(iter)]
    Y = [results[i] for i in range(iter)]
    plt.plot(X, Y)
    plt.title("各代最优解")
    plt.show()

10）运行程序

1
2
3
4
start_time = time.time()  # 记录程序开始运行时间
main()
end_time = time.time()  # 记录程序结束运行时间
print('运行时间：%f 秒' % (end_time - start_time))

设置了时间统计，记录算法运行花费时间

11）用到的库

1
2
3
4
5
6
7
8
import matplotlib.pyplot as plt
import math
import random
import numpy as np
import time
  
plt.rcParams['font.sans-serif']=['SimHei'] #用来正常显示中文标签
plt.rcParams['axes.unicode_minus']=False #用来正常显示负号

运行结果

最终运行结果：

分别为：随机生成的节点分布情况、算法结束后最优解给出的路线、优化过程中每一代的最优解对应的距离

总结

对于TSP问题，与求函数值不同之处在于节点不重复，因此交叉变异需要相应设计；又有求解最大/最小值的区别，对应的个体选择函数进行相应调整

另外，GA求解TSP问题，花费时间与节点个数基本正比，在（我的）个人电脑上跑的结果简单统计如下（迭代1000代）：

5个点：11-12秒

10个点：19-20秒

15个点：29-30秒

20个点：37-38秒

50个点：90秒左右

整体来说，还没出现随着点数增多，时间爆炸的现象（也可能是实验点数还少），时间基本是正比。

没有添加淘汰函数，第一想法是添加了会跑的更快，之后想到淘汰函数的作用是加速迭代，让算法收敛的更快，但不会减少总运行时间，所以就不添加了。（也可能会有效果，因为优化到后期，基因较好之后交叉变异运算会减少）

实际上总时间还是与迭代次数有关，因此尽量让算法收敛更快，之后减少迭代次数，就能获得更好的展示效果。

枫与风