遗传算法解决TSP问题

发表于 | 更新于 | 分类于
研究生课程 计算智能第四章模拟进化算法大作业

计算智能第三次大作业，用python实现。

用遗传算法（GA）解决旅行商问题（TSP）。遗传算法是模拟进化算法的一种，经典的仿生学算法。这个算法有毒，结果没有模拟退火好,而且好慢。

问题描述

​ TSP问题（旅行商问题）是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。

​ 转换为图论问题即：给定一个 $n$ 个节点的加权完全图 $d$ ，求一权重最小的哈密尔顿回路 $p$ 。

​ 动态规划求解的经典问题。用遗传算法来实现。

要点

参数

  1. 问题条件符号
    • 总共 $N$ 个节点，节点用数字编号 $0,1,\cdots,n-1$ 表示
    • 任意两个节点距离用邻接矩阵 $ d[i,j] $ ,其中 $i,j\in {0,1,\cdots,n-1} $
  2. 遗传算法符号
    • 种群规模 $M$ ,可取$M = 27N$
    • 路径$p[i][0:N-1]$ 表示种群中第i个元素所对应的路径$[0:N-1]$
    • 路径长度$l[i]$ 表示种群中第i个元素所对应的路径长度
    • 归一化适应度 $p[i]$
    • 变异概率 $P_m = 0.1= 10%$
    • 杂交本次实验采用取父代的一半，母代的剩余部分，不需要参数
  3. 特殊符号
    • 为了运行结果展示的方便，将全局的随机种子$seed = 1$。

细节介绍

遗传算法主要的操作有：杂交、变异、选择。对于每一代种群都进行这三种操作，如此往复，直到满足停止条件。

按程序写的顺序介绍一下每个函数实现的细节。顺便说一下停止条件。

杂交：hybrid

杂交分两步，第一步是适应度的计算，程序里用cal_adp()函数实现，第二步是杂交，让适应度越高的个体杂交的几率越大。

  1. 适应度函数计算：cal_adp()

    适应度函数主要是给杂交操作提供数据，以便适应度越高的杂交计算当前种群的。主要的步骤就是：计算路径长度$l[i]$，取适应度$p[i] = \frac{1}{l[i]}$,然后归一化

    $p[i] = \frac{p[i]}{\Sigma p[i]}$ ,将适应度作为杂交被选取到的概率。

  2. 杂交

    根据适应度选取两个不同个体，然后各自作为父亲，取前一半路径，剩下一半取另外一个个体的剩余路径，生成两个子代。

    进行$\frac{M}{2}$次这样的操作，产生$M$个子代。

变异：mutate

变异就是将杂交后生成的子代中每一个进行一个变异操作：若随机数小于变异概率，随机调换该个体中的两个节点。

选择：generate

生成下一代，这里不将杂交变异后的子代直接作为下一代，而是选取当前父代的一些最优解随机插入子代中代替子代的一部分。从而生成新的子代。

停止条件

如果连续一定代的遗传，其最优的解都没有变化，那么就将其视为收敛，这里设定为500。

python代码

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
import numpy as np
import random
import copy
import math
import sys
import pylab as pl
import matplotlib as plt


class GA():
    def __init__(self, N, M, randseed=None):  # 城市数量 N；种群规模 M；随机数种子 rand
        self.N = N
        self.M = M
        self.seed = randseed
        # d 距离邻接矩阵
        self.d = []
        self.path = []
        self.newpath = []
        self.l = []
        self.p = []
        self.bestl = sys.maxsize
        # 杂交概率 pc 变异概率 pm
        self.pm = 0.1
        self.pc = 0.5

        # 生成 d 距离邻接矩阵
        np.random.seed(self.seed)
        self.d = np.random.randint(1, 1000, (self.N, self.N))
        self.d = np.triu(self.d, 1) + np.triu(self.d, 1).T  # 生成完全图

        # 生成一个含M个个体的初始种群
        x = [i for i in range(self.N)]
        for i in range(self.M):
            self.path.append(copy.copy(x))
            random.shuffle(x)
        # print('init')
        # print('d 距离邻接矩阵')
        # print(self.d)
        # print('初始路径距离矩阵')
        # print(self.path)

    def cal_adp(self):  # 计算适应度 储存当前代最优值
        # 路径 path[i][:]
        # 路径长度 l[i]
        # 归一化适应度 adp[i]
        # 生成一个含M个个体的初始种群
        # 生成路径 path[i][:] 第i个个体路径
        # 生成路径长度 l[i] 第i个个体路径长度
        self.l = []
        self.p = []
        self.bestl = sys.maxsize
        self.bestpath = []
        for i in range(self.M):
            length = 0
            for j in range(self.N - 1):
                length += self.d[self.path[i][j]][self.path[i][j + 1]]
            length += self.d[self.path[i][self.N - 1]][self.path[i][0]]
            self.l.append(copy.copy(length))

        # 生成归一化适应度 p[i]  储存当前代最优值
        for i in range(self.M):
            self.p.append(math.pow(self.l[i], -1))
            if self.bestl > self.l[i]:
                self.bestl = copy.copy(self.l[i])
                self.bestpath = copy.deepcopy(self.path[i])
                # print('l[i]',self.l[i])
        sump = math.fsum(self.p)
        for i in range(self.M):
            self.p[i] /= sump

    def hybrid(self):  # 杂交
        self.path = sorted(self.path, key=lambda i: self.p[self.path.index(i)])
        self.p = sorted(self.p)
        # print('杂交前path')
        # print(np.array(self.path))
        for i in range(1, self.M):
            self.p[i] += self.p[i - 1]
        # print(p)
        self.newpath = []
        for i in range(self.M // 2):  # 进行M/2次杂交 一共生成M个子代
            x, y = 0, 0
            while x == y:
                a, b = np.random.rand(), np.random.rand()
                x, y = 0, 0
                while a > self.p[x]:
                    x += 1
                while b > self.p[y]:
                    y += 1
            # x作为父代
            child = self.path[x][:self.N // 2]
            child2 = list(set(self.path[y]) - set(child))
            child2.sort(key=self.path[y].index)
            # print(self.path[x],self.path[y])
            # print(child,child2)
            self.newpath.append(child + child2)

            # y作为父代
            child = self.path[y][:self.N // 2]
            child2 = list(set(self.path[x]) - set(child))
            child2.sort(key=self.path[x].index)
            # print(self.path[x],self.path[y])
            # print(child,child2)
            self.newpath.append(child + child2)

        # print('杂交后newpath')
        # print(np.array(self.newpath))

    def mutate(self):  # 变异
        # print(np.array(self.path))
        for i in range(self.M):
            if np.random.rand() < self.pm:  # 概率变异
                a, b = 0, 0
                while a == b:
                    a, b = np.random.randint(0, self.N), np.random.randint(0, self.N)
                self.newpath[i][a], self.newpath[i][b] = self.newpath[i][b], self.newpath[i][a]
                # print(i,a,b)

    def generate(self):  # 生成下一代 将M个子代 和 M个父代合并筛选 出M个子代的新种群
        # print(np.array(self.newpath))
        # print(np.array(self.path))
        # t = self.newpath +self.path[:self.M//2]
        t = self.newpath
        l = []
        for i in range(int(self.M)):
            length = 0
            for j in range(self.N - 1):
                length += self.d[t[i][j]][t[i][j + 1]]
            length += self.d[t[i][self.N - 1]][t[i][0]]
            l.append(copy.copy(length))
        t = sorted(t, key=lambda i: l[t.index(i)])
        l = sorted(l)
        #print('l[0]',l[0])
        # if l[0] < self.l[0]:
        #     t[self.M-1] = copy.copy(self.path[self.M-1])
        t[np.random.randint(0,self.M)] = copy.copy(self.path[self.M-1])
        self.path = t[:self.M]  # 切取最优秀的前M个成为子代path
        # print('新子代path')
        # print(np.array(self.path))


if __name__ == '__main__':
    tsp = GA(N=30, M=1000, randseed=1)  # 初始化
    ans = sys.maxsize
    log = []
    stp = 0
    tim = 0
    while stp <= 1000:  # 100代最优解没变化则停止
        tim += 1  # 记录生成次数
        tsp.cal_adp()  # 计算适应度
        log.append(tsp.bestl)
        # print(ans)
        if tsp.bestl == ans:
            stp += 1
        elif tsp.bestl != ans:
            ans = tsp.bestl
            stp = 0
        tsp.hybrid()  # 杂交
        tsp.mutate()  # 变异
        tsp.generate()  # 生成子代
        print(tsp.bestl,tim)
    print('Path:', tsp.bestpath)
    print('Length:', tsp.bestl)
    print('Times', tim)