用遗传算法(GA)来解决 MTSP(多旅行商问题)-Yinode Blog

引言

本文章会侧重实际运用，给出对于 MTSP 和 TSP 问题的一个 GA 算法，并具有较高可用性的方案。并在最后给出一个可以跑在Web Browser 上的可视化 Demo。

并且会基于问题给出一些我自己的思路和最终结果。

旅行商问题

旅行商问题（最短路径问题）（英语：travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。问题在1930年首次被形式化，并且是在最优化中研究最深入的问题之一。许多优化方法都用它作为一个基准。尽管问题在计算上很困难，但已经有了大量的启发式和精确方法，因此可以完全求解城市数量上万的实例，并且甚至能在误差1%范围内估计上百万个城市的问题。

本文要解决的问题是属于旅行商问题的变种多旅行商问题(MTSP)

也就是求多个旅行商共同从某个起点出发，在各自经过一条汉密尔顿回路之后，回到起点。 求所有路径长度总和最小的一种走法

常规的回溯算法(也就是穷举)不可能多项式时间内解决该问题(无论是 TSP 还是 MSTP),所以基本没有实用性。所以本文介绍一种利用 GA（遗传算法）解决 MTSP 的方法。

遗传算法

遗传算法（英语：genetic algorithm (GA) ）是计算数学中用于解决最优化的搜索算法，是进化算法的一种。进化算法最初是借鉴了进化生物学中的一些现象而发展起来的，这些现象包括遗传、突变、自然选择以及杂交等等。

遗传算法通常实现方式为一种计算机模拟。对于一个最优化问题，一定数量的候选解（称为个体）可抽象表示为染色体，使种群向更好的解进化。传统上，解用二进制表示（即0和1的串），但也可以用其他表示方法。进化从完全随机个体的种群开始，之后一代一代发生。在每一代中评价整个种群的适应度，从当前种群中随机地选择多个个体（基于它们的适应度），通过自然选择和突变产生新的生命种群，该种群在算法的下一次迭代中成为当前种群。

遗传算法是一种仿生学算法，与之类似的还有蚁群算法和萤火虫算法,他们旨在模拟大自然中的一种现象，在迭代过程中不断趋向更好的结果，相比较而言，GA 是一种实现起来比较简单的算法，所以我采用了该算法来解决 MTSP 问题。

遗传算法的基本概念

下面介绍一下 GA 算法的主要概念，当然这里面的某些概念可能并不是用 GA 算法所必须使用的。事实上我最后的解决方案就没用 Cross over.

population

族群，代表了当前一系列的解，映射到我们的 MTSP 问题中，族群中的一个人口就是一种 MSTP 的解决方案，族群一般会限定数量，比如一个族群里面有500个人口，代表有500个解。

fitness

健康程度，可以认为是这个解的优秀程度，对每个人口的健康程度进行评估，在每次进化过程中，尝试保留更健康的人口里的优秀基因，从而不断逼近最优解

cross over

这个过程类似我们大自然种两个个体的交配过程，汲取父母双方的基因，从而生出一个包涵父母双方特征的孩子。通常来说，我们更倾向于选择更优秀的后代来进行交配

mutate

基因突变，同样是一个仿生学概念，在生成孩子之后，我们可以配合一定的突变概率，对孩子的基因进行某种方式上的突变(比如对基因组进行 swap shuffle)，该方式能够在父母基因的基础之上增加一点变化，从而可能突变出更好基因。

evolution

结合上面的操作，我们将 population 进行健康评估 > cross over > mutate 之后，就能生成新一代的人口，通常来说，这个新一代的人口内部整体健康情况会优于上一代的人口。

用遗传算法解决 TSP 问题

我们先别把步子迈的太大，先考虑如何用 GA 解决 TSP 问题。

这里介绍一个视频，我认为讲的很不错，适合入门，建议观看，这里给出 youtube 链接。

Coding Challenge #35.4: Traveling Salesperson with Genetic Algorithm

我这里简单介绍下他里面核心的 cross over 以及 mutate 过程

表示

考虑我们拥有一组点 ['a','b','c','d'] 我们应该如何表示一种旅行商问题的解?

事实上我们完全可以使用一个按照路径访问顺序放置的一维数组来表示我们的解决方案,比如 ['b','a','d','c']代表b > a > d > c 这样一条路径，为了写起来更方便，我们完全可以存储结构上不考虑回路回到起点，只要在计算距离的时候，加上最后一个节点到第一个节点的距离就可以。

cross over

接下来考虑给定 A , B 两个解，如何得出两个解 Cross Over 后的结果。

我们可以先根据数组的长度，生成一个随机的 [i,j] 的区间，先把 A 的 [i,j] 区间内的节点放置到 result 中，然后遍历 B , 把所有不包含在 A[i,j] 内的元素都放置到 result中。

mutate

在得到Cross Over 的结果后，我们可以考虑对其按照突变概率进行一定程度的突变。

我们可以随机抓取两个元素进行 swap 交换操作。当然你可以考虑随机生成两个区间 swap 两个区间。

总体流程

初始化人口(随机生成路径序列)
评估每个人口的健康程度生成 fitness 数组 (需要归一化)
根据健康程度，在当前族群里面抓取两个父母(越健康，抓取到概率就越大)
根据两个父母进行 Cross Over 生成后代，并根据一定概率进行基因突变
重复3,4步骤，直到生成目标的人口数量，完全生成新一代族群
检查是否达到目标代数，达到则结束，否则继续进入步骤2

用遗传算法解决 MTSP 问题

K 均值 + 常规 GA 算法

其实我一开始解决 MTSP 问题的时候，采用的最初方案是先使用 K 均值分类算法，先进行聚类，随后对每个类使用上述的 GA 算法进行迭代，但是这个方法有几个无法避免的问题。

K 均值算法每次分类的结果不是特别稳定，这一块可以通过对 K 均值初始随机选点的过程进行优化解决
每个组最终任务量可能会出现非常大的偏差，导致很难改进成均分任务的多旅行商问题(eq-mtsp)
由于先进行分组，算法的可扩展性会大大降低，比如不但需要考虑距离上的因素，还要考虑时间，最大里程限制，等等额外的功能。

在完成了第一版的方案后，我开始尝试单纯使用 GA 来解决 MTSP 问题。

单独使用 GA 算法

表示

在思考解决方案之前，我们依旧需要先考虑一下我们应该如何表示多个旅行商，这里给出两种可行的表示，当然这两种方式本质相同，可以互相转化。

我个人更推荐第二种方式，遍历路径起来可能会麻烦一点，但是操作效率更高，而且跟我接下来讲的操作会有直接关联。或者你可以使用冗余的方式，同时存储两种方式（初版算法可以更多的考虑可读性和扩展性，冗余也是可以接受的）。

二维数组

let paths = [
    ['a','d','e'],
    ['c','b']
]

一维数组+break

let paths = ['a','d','e','c','d']
let breaks = [3,2]

breaks数组代表了分类区间，第一条路径包涵三个节点，第二条路径包涵两个节点

如何生成更优质的下一代

既然是遗传，核心在于如何在当前的人口基础之上生成更健康的下一代。带着这个问题，我自己设想并实现了第一版，但是收敛速度非常不理想，后面我搜索了一些论文，也了解了一些相关实现，试了很多方案，最终找到了一个收敛速度比较理想的方法，这里给出大致步骤。

随机采样并进行组合突变

该方法直接抛弃掉了 Cross Over 过程，转而单纯的采样优秀的样本进行各种组合突变。

首先我们使用随机采样的方式来获取种群中的优秀基因，按序选择一个大小为10的区间，随后遍历该区间，找出健康程度最高的那个，复制出10个副本，对每个副本进行不同类型的突变

  evo() {
    let newPopulation = []
    let rdPopIndexs = _.shuffle(this.population.map((v, i) => i))
    for (let i = 0; i < this.population.length; i += 10) { // 每次循环都会生成10个
      // 随机抽取10个元素 找到其中最好的 然后复制出10个副本
      const bestIndex = this.findBest(rdPopIndexs.slice(i, i + 10), this.fitness)
      const best = this.population[bestIndex]
      const bestPops = new Array(10).fill(1).map(() => best.getCopy())

      // 对10个副本分别进行不同方式的基因突变
      for (let i = 0; i < 10; i++) {
        bestPops[i].mutate(i)
      }
      newPopulation = newPopulation.concat(bestPops)
    }
    this.population = newPopulation
  }

接下来就是组合运用不同类型的突变，所有的突变都基于我们上面说的第二种表示方法，必要时也会对线路进行重新分区，这意味着每条线路内的节点发生变化的同时，线路的长度也可能发生变化。

  mutate(i) {
    // // 第一种方式 选择随机区间然后随机插入
    // // 复用之间的 break 重新生成 paths
    if (i === 1) {
      this.totalStore = this.swapInsert(this.totalStore)
      this.genPathsByBreakRanges()
    }

    if (i === 2) {
      this.totalStore = this.flipInset(this.totalStore)
      this.genPathsByBreakRanges()
    }

    if (i === 3) {
      this.totalStore = this.leftSlideInsert(this.totalStore)
      this.genPathsByBreakRanges()
    }

    if (i === 4) {
      this.totalStore = this.rightSlideInsert(this.totalStore)
      this.genPathsByBreakRanges()
    }

    if (i === 5) {
      this.breaks = this.getRouterRange()
      this.genPathsByBreakRanges()
    }

    if (i === 6) {
      this.totalStore = this.flipInset(this.totalStore)
      this.breaks = this.getRouterRange()
      this.genPathsByBreakRanges()
    }

    if (i === 7) {
      this.totalStore = this.swapInsert(this.totalStore)
      this.breaks = this.getRouterRange()
      this.genPathsByBreakRanges()
    }

    if (i === 8) {
      this.totalStore = this.leftSlideInsert(this.totalStore)
      this.breaks = this.getRouterRange()
      this.genPathsByBreakRanges()
    }

    if (i === 9) {
      this.totalStore = this.rightSlideInsert(this.totalStore)
      this.breaks = this.getRouterRange()
      this.genPathsByBreakRanges()
    }
}

所以我介绍一下基本的突变方法

// 在 total router 选择一个随机区间 最后随机插入
  swapInsert(routers) {
    const [i, j] = utils.randomSample(0, routers.length, 2)
    const segment = routers.slice(i, j)
    routers.splice(i, j - i)
    const insertIndex = utils.random(0, routers.length - 1)
    routers.splice(insertIndex, 0, ...segment)
    return routers
  }

  // 在 total router 选择一个随机区间 然后反转 最后随机插入
  flipInset(routers) {
    const [i, j] = utils.randomSample(0, routers.length, 2)
    const segment = routers.slice(i, j).reverse()
    routers.splice(i, j - i)
    const insertIndex = utils.random(0, routers.length - 1)
    routers.splice(insertIndex, 0, ...segment)
    return routers
  }

  // 在 total router 选择一个随机区间 然后将最右边的元素放到最左边 最后随机插入
  leftSlideInsert(routers) {
    const [i, j] = utils.randomSample(0, routers.length, 2)
    const segment = routers.slice(i, j)
    routers.splice(i, j - i)
    segment.unshift(segment.pop())
    const insertIndex = utils.random(0, routers.length - 1)
    routers.splice(insertIndex, 0, ...segment)
    return routers
  }

  // 在 total router 选择一个随机区间 然后将最右边的元素放到最左边 最后随机插入
  rightSlideInsert(routers) {
    const [i, j] = utils.randomSample(0, routers.length, 2)
    const segment = routers.slice(i, j)
    routers.splice(i, j - i)
    segment.push(segment.shift())
    const insertIndex = utils.random(0, routers.length - 1)
    routers.splice(insertIndex, 0, ...segment)
    return routers
  }

然后是获取随机分区以及根据 breaks 进行重新分区方法，这里我做了冗余，也就是同时保存了两种表示方式，后面可以进一步优化性能。

  // 获取一个随机化但是具有一定限制的区间
  getRouterRange() {
    const upper = (RM.getLocations().length)
    // fa fb 代表了随机分区的上下限，也就是基于平均值的倍数
    const fa = upper / config.lineCount * 8
    const fb = upper / config.lineCount * 0.01

    let a = utils.randomRange(this.totalStore.length, config.lineCount)
    while (true) {
      if (a.every(i => i < fa && i > fb)) {
        break
      } else {
        a = utils.randomRange(this.totalStore.length, config.lineCount)
      }
    }
    return a
  },
  // 根据当前分隔区间和全部路由 重新分配到 paths 二维数组中
  genPathsByBreakRanges() {
    this.paths = new Array(this.breaks.length).fill(1).map(() => new Array())
    let k = 0
    for (let i = 0; i < this.breaks.length; i++) {
      let range = this.breaks[i]
      while (range--) {
        this.paths[i].push(this.totalStore[k++])
      }
    }
  }

以上的突变方法特别感谢 mTSP-IPGA 提供的灵感，实际组合利用起来收敛速度非常快

code

github

live demo

引用

A Novel Approach to Solve Multiple Traveling Salesmen Problem by Genetic Algorithm

Optimization of Multiple Traveling Salesmen Problem by a Novel Representation Based Genetic Algorithm

[离散数学及其运用 TSP部分]

mTSP-IPGA

用遗传算法(GA)来解决 MTSP(多旅行商问题)

TOC

引言