遗传算法 (解决TSP旅行商问题) 附Python代码-526互联

1.什么是TSP旅行商问题？

1.1 问题本质

旅行商问题是一个经典的组合优化问题。

问题实质是一个带权完全无向图，找一个权值最小的Hamilton回路。( 即点到点的最优路径问题 )

早期的研究者使用精确算法求解该问题，常用的方法包括：分枝定界法、线性规划法、动态规划法等。但是，随着问题规模的增大，精确算法将变得无能为力，因此，在后来的研究中，国内外学者重点使用近似算法或启发式算法，主要有遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。

1.2 深入分析

时间复杂度问题

2.什么是遗传算法？

2.1 遗传算法的科学定义

结合生物学，通过模拟自然进化过程搜索最优解的方法。

是学科与学科之间思想交互的体现。

主要特点是直接对结构对象进行操作，采用概率化的寻优方法，自适应地调整搜索方向。

参数编码、初始群体的设定、适应度函数的设计、遗传操作设计、控制参数设定五个要素组成了遗传算法的核心内容。（5个参数？）

2.2 遗传算法的执行过程

结合生物学实现迭代，进化。（有点-_-||）

遗传算法的执行过程

3.问题的引出与形象化解决

3.1 寻找最高山峰，袋鼠蹦跳问题

爬山算法，模拟退火，遗传算法

3.2 大体实现过程

首先寻找一种对问题潜在解进行“数字化”编码的方案。（建立表现型和基因型的映射关系）
随机初始化一个种群（那么第一批袋鼠就被随意地分散在山脉上），种群里面的个体就是这些数字化的编码。
接下来，通过适当的解码过程之后（得到袋鼠的位置坐标）。
用适应性函数对每一个基因个体作一次适应度评估（袋鼠爬得越高当然就越好，所以适应度相应越高）。
用选择函数按照某种规定择优选择（每隔一段时间，射杀一些所在海拔较低的袋鼠，以保证袋鼠总体数目持平。）
让个体基因变异（让袋鼠随机地跳一跳）。
然后产生子代（希望存活下来的袋鼠是多产的，并在那里生儿育女）。

并不是寻找最优解，而是找到最优的近似解

它并不关心如何去找最优解。而贪心算法（模糊）和动态规划（精确）则是考虑每一步的最优解如何找到。

4. 具体实现

4.1 编码方式

作用：基因分离，统一所有个体表达

二进制编码法、浮点编码法、符号编码法。

二进制编码：简单但不稳定
浮点编码法：表示范围大但不精确( 只是相对不精确不精确体现在无法表示所有小数)
符号编码法：好（不了解。。。）

对于TSP问题，采用实数编码

每个个体为一组城市路径顺序

4.2 评价个体的适应度

通过适应性函数给每个个体打分，根据目标函数，最合适的留下。

分数总是非负的，但目标函数可正可负，所以需要在目标函数与分数(适应性函数)之间做合适的变换。

对于TSP问题，可以将路径的倒数设置为适应度，毕竟路径越长，越不合适。

有趣的分数体现

通过基因，将boolean[]中的数据二进制化（位运算）比如：

true true false true false = 11010

在将这个二进制数转化为10进制 26

26就作为当前个体的分数

4.3 个体优化生态选择

优化方式需要建立一种概率关系

常用的选择算法：

轮盘赌选择【没特点】个体的适应度值与整个种群适应度值和的比例。根据比例选择个体。误差较大
随机竞争选择【最差个体一定被淘汰】　

每次选择两个进行对比，选满为止
最佳保留选择【最优个体一定被保留】

每次选最好的
无回放随机选择（也叫期望值选择）【公平】

每个个体有分数，越优秀分数越高，每次根据生存期望扣减分数(交叉减0.5，未交叉减1)，分数为0淘汰。
确定式选择 【直观】

整数用来确定个数，小数部分用来确定分数（整数部分不影响分数）

2.2 3.4 5.1 的排序就是：5.1 2.2 3.4
无回放余数随机选择 【误差小】
均匀排序【误差小】
最佳保存策略【额。。。最大最小不参与评分】
随机联赛选择【相对公平】

选取几个个体，挑选最好的。
排挤选择 【多样】

子类排挤父类

4.4 交叉和选择

选择

选择操作从旧群体中以一定概率选择优良个体组成新的种群，以繁殖得到下一代个体。

两个个体通过融合，变异的方式形成新的个体（个数不确定，看设置，毕竟一对夫妻可以有多个孩子）

交叉方式：

单点交叉：指在个体编码串中只随机设置一个交叉点，然后再该点相互交换两个配对个体的部分染色体。

13567 90324 ------》13267 90354
两点交叉与多点交叉：指在个体编码串中随机设置两(多)个交叉点，然后再该点相互交换两个配对个体的部分染色体。
均匀交叉：两个配对个体的每个基因座上的基因都以相同的交叉概率进行交换，从而形成两个新个体。（..............）
算术交叉：随机把其中几个位于同一位置的编码进行交换，产生新的个体。（................）

像这样：

对应的二进制交叉：

010|100|110 010|010|110

110|010|100 --------> 110|100|100

4.5 变异

遗传算法中的变异运算是指将个体染色体编码串中的某些基因座上的基因值用该基因座的其他等位基因来替换，从而形成一个新个体。

变异算子主要有以下两个目的：

（1）改善遗传算法的局部搜索能力。（2）维持群体的多样性，防止出现早熟现象。

变异算子的设计包括如下两方面内容：

（1）如何确定变异点的位置？（2）如何进行基因值替换？

变异方式：单点变异、多点变异，均匀变异、翻转变异

5.算法终止条件

已达到最大世代数（一般手动设置，用于限制算法消耗的运行时间）
在过去的几代中个体没有明显的改进，这可以通过存储每一代获得的最佳适应度值，然后将当前的最佳值与预定的几代之前获得的最佳值进行比较来实现。如果差异小于某个阈值，则算法可以停止。
算法的时间过长。
内存oom

以下附上Python代码

# coding=utf-8
from math import floor
import numpy as np
import time
import matplotlib.pyplot as plt  # 导入所需要的库


class Gena_TSP(object):

    def __init__(self, data,
                 maxgen=1000,
                 size_pop=100,
                 cross_prob=0.80,
                 pmuta_prob=0.02,
                 select_prob=0.8):
        self.maxgen = maxgen  # 最大迭代次数
        self.size_pop = size_pop  # 群体个数
        self.cross_prob = cross_prob  # 交叉概率
        self.pmuta_prob = pmuta_prob  # 变异概率
        self.select_prob = select_prob  # 选择概率

        self.data = data  # 城市的左边数据
        self.num = len(data)  # 城市个数 对应染色体长度
        # 距离矩阵n*n, 第[i,j]个元素表示城市i到j距离matrix_dis函数见下文
        self.matrix_distance = self.matrix_dis()

        # 通过选择概率确定子代的选择个数
        self.select_num = max(floor(self.size_pop * self.select_prob + 0.5), 2)

        # 父代和子代群体的初始化（不直接用np.zeros是为了保证单个染色体的编码为整数，np.zeros对应的数据类型为浮点型）
        self.chrom = np.array([0] * self.size_pop * self.num).reshape(self.size_pop,
                                                                      self.num)  # 父 print(chrom.shape)(200, 14)
        self.sub_sel = np.array([0] * int(self.select_num) * self.num).reshape(self.select_num, self.num)  # 子 (160, 14)

        # 存储群体中每个染色体的路径总长度，对应单个染色体的适应度就是其倒数  #print(fitness.shape)#(200,)
        self.fitness = np.zeros(self.size_pop)

        self.best_fit = []  ##最优距离
        self.best_path = []  # 最优路径

    # 计算城市间的距离函数  n*n, 第[i,j]个元素表示城市i到j距离
    def matrix_dis(self):
        res = np.zeros((self.num, self.num))
        for i in range(self.num):
            for j in range(i + 1, self.num):
                res[i, j] = np.linalg.norm(self.data[i, :] - self.data[j, :])  # 求二阶范数 就是距离公式
                res[j, i] = res[i, j]
        return res

    # 随机产生初始化群体函数
    def rand_chrom(self):
        rand_ch = np.array(range(self.num))  ## num 城市个数 对应染色体长度  =14
        for i in range(self.size_pop):  # size_pop  # 群体个数 200
            np.random.shuffle(rand_ch)  # 打乱城市染色体编码
            self.chrom[i, :] = rand_ch
            self.fitness[i] = self.comp_fit(rand_ch)

    # 计算单个染色体的路径距离值，可利用该函数更新fittness
    def comp_fit(self, one_path):
        res = 0
        for i in range(self.num - 1):
            res += self.matrix_distance[one_path[i], one_path[i + 1]]  # matrix_distance n*n, 第[i,j]个元素表示城市i到j距离
        res += self.matrix_distance[one_path[-1], one_path[0]]  # 最后一个城市 到起点距离
        return res

    # 路径可视化函数
    def out_path(self, one_path):
        res = str(one_path[0] + 1) + '-->'
        for i in range(1, self.num):
            res += str(one_path[i] + 1) + '-->'
        res += str(one_path[0] + 1) + '\n'
        print(res)

    # 子代选取，根据选中概率与对应的适应度函数，采用随机遍历选择方法
    def select_sub(self):
        fit = 1. / (self.fitness)  # 适应度函数
        cumsum_fit = np.cumsum(fit)  # 累积求和   a = np.array([1,2,3]) b = np.cumsum(a) b=1 3 6
        pick = cumsum_fit[-1] / self.select_num * (
                    np.random.rand() + np.array(range(int(self.select_num))))  # select_num  为子代选择个数 160
        i, j = 0, 0
        index = []
        while i < self.size_pop and j < self.select_num:
            if cumsum_fit[i] >= pick[j]:
                index.append(i)
                j += 1
            else:
                i += 1
        self.sub_sel = self.chrom[index, :]  # chrom 父

    # 交叉，依概率对子代个体进行交叉操作
    def cross_sub(self):
        if self.select_num % 2 == 0:  # select_num160
            num = range(0, int(self.select_num), 2)
        else:
            num = range(0, int(self.select_num - 1), 2)
        for i in num:
            if self.cross_prob >= np.random.rand():
                self.sub_sel[i, :], self.sub_sel[i + 1, :] = self.intercross(self.sub_sel[i, :], self.sub_sel[i + 1, :])

    def intercross(self, ind_a, ind_b):  # ind_a，ind_b 父代染色体 shape=(1,14) 14=14个城市
        r1 = np.random.randint(self.num)  # 在num内随机生成一个整数 ，num=14.即随机生成一个小于14的数
        r2 = np.random.randint(self.num)
        while r2 == r1:  # 如果r1==r2
            r2 = np.random.randint(self.num)  # r2重新生成
        left, right = min(r1, r2), max(r1, r2)  # left 为r1,r2小值 ，r2为大值
        ind_a1 = ind_a.copy()  # 父亲
        ind_b1 = ind_b.copy()  # 母亲
        for i in range(left, right + 1):
            ind_a2 = ind_a.copy()
            ind_b2 = ind_b.copy()
            ind_a[i] = ind_b1[i]  # 交叉 （即ind_a  （1,14） 中有个元素 和ind_b互换
            ind_b[i] = ind_a1[i]
            x = np.argwhere(ind_a == ind_a[i])
            y = np.argwhere(ind_b == ind_b[i])

            """
                   下面的代码意思是 假如 两个父辈的染色体编码为【1234】，【4321】 
                   交叉后为【1334】，【4221】
                   交叉后的结果是不满足条件的，重复个数为2个
                   需要修改为【1234】【4321】（即修改会来
                   """
            if len(x) == 2:
                ind_a[x[x != i]] = ind_a2[i]  # 查找ind_a 中元素=- ind_a[i] 的索引
            if len(y) == 2:
                ind_b[y[y != i]] = ind_b2[i]
        return ind_a, ind_b

    # 变异模块  在变异概率的控制下，对单个染色体随机交换两个点的位置。
    def mutation_sub(self):
        for i in range(int(self.select_num)):  # 遍历每一个 选择的子代
            if np.random.rand() <= self.cross_prob:  # 如果随机数小于变异概率
                r1 = np.random.randint(self.num)  # 随机生成小于num==可设置 的数
                r2 = np.random.randint(self.num)
                while r2 == r1:  # 如果相同
                    r2 = np.random.randint(self.num)  # r2再生成一次
                self.sub_sel[i, [r1, r2]] = self.sub_sel[i, [r2, r1]]  # 随机交换两个点的位置。

    # 进化逆转  将选择的染色体随机选择两个位置r1:r2 ，将 r1:r2 的元素翻转为 r2:r1 ，如果翻转后的适应度更高，则替换原染色体，否则不变
    def reverse_sub(self):
        for i in range(int(self.select_num)):  # 遍历每一个 选择的子代
            r1 = np.random.randint(self.num)  # 随机生成小于num==14 的数
            r2 = np.random.randint(self.num)
            while r2 == r1:  # 如果相同
                r2 = np.random.randint(self.num)  # r2再生成一次
            left, right = min(r1, r2), max(r1, r2)  # left取r1 r2中小值，r2取大值
            sel = self.sub_sel[i, :].copy()  # sel 为父辈染色体 shape=（1,14）

            sel[left:right + 1] = self.sub_sel[i, left:right + 1][::-1]  # 将染色体中(r1:r2)片段 翻转为（r2:r1)
            if self.comp_fit(sel) < self.comp_fit(self.sub_sel[i, :]):  # 如果翻转后的适应度小于原染色体，则不变
                self.sub_sel[i, :] = sel

    # 子代插入父代，得到相同规模的新群体
    def reins(self):
        index = np.argsort(self.fitness)[::-1]  # 替换最差的（倒序）
        self.chrom[index[:self.select_num], :] = self.sub_sel


# 路径坐标
data = np.array([20.00, 96.10, 16.47, 94.44,
                 20.09, 92.54, 22.39, 93.37,
                 25.23, 97.24, 22.00, 96.05,
                 20.47, 97.02, 17.20, 96.29,
                 16.30, 97.38, 25.05, 98.12,
                 16.53, 96.50, 21.52, 95.59,
                 19.41, 97.13, 20.09, 92.55,
                 20.10, 95.10, 20.20, 94.10,
                 20.60, 96.88, 18.66, 90.20]).reshape(18, 2)


def main(data):
    Path_short = Gena_TSP(data)  # 根据位置坐标，生成一个遗传算法类
    Path_short.rand_chrom()  # 初始化父类

    ## 绘制初始化的路径图
    fig, ax = plt.subplots()
    x = data[:, 0]
    y = data[:, 1]
    ax.scatter(x, y, linewidths=0.1)
    for i, txt in enumerate(range(1, len(data) + 1)):
        ax.annotate(txt, (x[i], y[i]))
    res0 = Path_short.chrom[0]
    x0 = x[res0]
    y0 = y[res0]
    for i in range(len(data) - 1):
        plt.quiver(x0[i], y0[i], x0[i + 1] - x0[i], y0[i + 1] - y0[i], color='r', width=0.005, angles='xy', scale=1,
                   scale_units='xy')
    plt.quiver(x0[-1], y0[-1], x0[0] - x0[-1], y0[0] - y0[-1], color='r', width=0.005, angles='xy', scale=1,
               scale_units='xy')
    plt.show()
    print('初始染色体的路程: ' + str(Path_short.fitness[0]))

    # 循环迭代遗传过程
    for i in range(Path_short.maxgen):
        Path_short.select_sub()  # 选择子代
        Path_short.cross_sub()  # 交叉
        Path_short.mutation_sub()  # 变异
        Path_short.reverse_sub()  # 进化逆转
        Path_short.reins()  # 子代插入

        # 重新计算新群体的距离值
        for j in range(Path_short.size_pop):
            Path_short.fitness[j] = Path_short.comp_fit(Path_short.chrom[j, :])

        # 每隔三十步显示当前群体的最优路径
        index = Path_short.fitness.argmin()
        if (i + 1) % 50 == 0:
            # 获取当前时间戳 记录运算时间
            timestamp = time.time()
            formatted_time = time.strftime("%Y-%m-%d %H:%M:%S", time.localtime(timestamp))
            print(formatted_time)
            print('第' + str(i + 1) + '代后的最短的路程: ' + str(Path_short.fitness[index]))
            print('第' + str(i + 1) + '代后的最优路径:')
            Path_short.out_path(Path_short.chrom[index, :])  # 显示每一步的最优路径

        # 存储每一步的最优路径及距离
        Path_short.best_fit.append(Path_short.fitness[index])
        Path_short.best_path.append(Path_short.chrom[index, :])

    res1 = Path_short.chrom[0]
    x0 = x[res1]
    y0 = y[res1]
    for i in range(len(data) - 1):
        plt.quiver(x0[i], y0[i], x0[i + 1] - x0[i], y0[i + 1] - y0[i], color='r', width=0.005, angles='xy', scale=1,
                   scale_units='xy')
    plt.quiver(x0[-1], y0[-1], x0[0] - x0[-1], y0[0] - y0[-1], color='r', width=0.005, angles='xy', scale=1,
               scale_units='xy')
    plt.show()

    return Path_short  # 返回遗传算法结果类


Path_short = main(data)
print(Path_short)