TSP-旅行商问题(基于动态规划或蚁群算法求解)

• 25-03-07 18:01
• 3201
• 9892

blog.csdn.net

id="article_content" class="article_content clearfix"> id="content_views" class="markdown_views prism-atom-one-dark">

1. TSP问题

旅行商问题(Travelling salesman problem, TSP)是运筹学和理论计算机科学中经典的问题.具体问题如下:给定一系列城市和每对城市之间的距离,求解访问每座城市一次并回到起始城市的最短回路.

2. 动态规划

本节参考旅行商问题(动态规划)

2.1 理论介绍

假设节点数较少的TSP问题,我们完全可以使用穷举的方式得到最优解,但是在穷举过程中一定存在很多重复的计算.这时候我们就可以使用动态规划来避免这些重复计算以提高效率.
熟悉动态规划的同学一定知道,凡是可以使用动态规划求解优化问题,说明问题本身一定含有最优子问题,换言之,求解得到最优解,一定是由子问题的最优解组成.
换成数学的语言表达即,假设当前问题是想知道从节点i出发,访问剩余节点集合V的最短路径,将该问题表达成

$$d(i,V)$$

假如下一个节点选择了k节点能使该问题有最优解,那么本问题必定包含了子问题 d ( k , V − { k } ) d(k, V-\{\mathrm k\}) d(k,V−{k}),即从节点k出发访问剩余节点集合 V − { k } V-\{\mathrm k\} V−{k}.这是显而易见的,不妨反过来想,如果子问题不是最优,那么本问题一定不是最优的.
经过上面的分析,不难得出下面的动态规划方程:

d ( i , V ) = { c i s , V = ∅ , i ≠ s min ⁡ { c i k + d ( k , V − { k } ) } , k ∈ V , i ∉ V , V ≠ ∅ \mathrm d(\mathrm i,\mathrm V)= class="MathJax_Display">{cis,V=∅,i≠smin{cik+d(k,V−{k})},k∈V,i∉V,V≠∅" role="presentation">{cis,min{cik+d(k,V−{k})},V=∅,i≠sk∈V,i∉V,V≠∅$$\{\begin{array}{ll}{c}_{is},& \mathrm{V}=\mathrm{\varnothing },\mathrm{i}\ne \mathrm{s}\\ min\{c_{ik}+\mathrm{d}(\mathrm{k},\mathrm{V}-\{\mathrm{k}\})\},& \mathrm{k}\in \mathrm{V},\mathrm{i}\notin \mathrm{V},\mathrm{V}\ne \mathrm{\varnothing }\end{array}$$

d(i,V)={cis​,min{cik​+d(k,V−{k})},​V=∅,i=sk∈V,i∈/V,V=∅​

2.2 算法实现

有了上面的理论分析,基于动态规划求解TSP的算法实现就很容易理解.

利用动态规划方程我们很容易自底向上的计算各个子问题,直至得到我们想要求解的问题.具体操作就是使用一个DP表(下表是从节点0出发得到的DP表).

class="table-box">

索引	{null}	{1}	{2}	{1,2}	{3}	{1, 3}	{2, 3}	{1,2,3}
0	/	/	/	/	/	/	/	d(0, {1,2,3})
1	c(0,1)	/	d(1,{2})	/	d{1,{3}}	/	d(1,{2,3})	/
2	c(0,2)	d(2,{1})	/	/	d(2,{3})	d(2,{1,3})	/	/
3	c(0,3)	d(3,{1})	d(3,{2})	d(3,{1,2})	/	/	/	/

该表的更新顺序可以从左侧列开始递推到右侧列.注意DP表的维度,假设有n个节点(包含1个起始节点):

• 有n行
• 有$2^{n-1}$列

递推过程还需要遍历n次比较求 min ⁡ { c i k + d ( k , V − { k } ) } \min\{c_{ik}+\mathrm d(\mathrm k,\mathrm V-\{\mathrm k\})\} min{cik​+d(k,V−{k})}.因此通过动态规划求解TSP问题的时间复杂度为 $O(2^n{n}^2)$，因此大规模的TSP问题不能直接使用动态规划的方法求解.

def SolveTspByDp(nodes, close = False):
    """
    @brief: 动态规划解决 旅行商
    @note: 只适合小规模的运算 20个节点内
    @param nodes: 节点数组,nodes[0]是起点
    @param close:   true-寻找最优的闭环路径(回到起点)
                    false-非闭环最优路径
    """

    n = len(nodes)
    m = 1 << (n - 1)

    distances = np.zeros((n, n))
    for i in range(n):
        for j in range(n):
            if i != j:
                distances[i][j] = (nodes[i] - nodes[j]).Norm()
                # dx = nodes[i][0] - nodes[j][0]
                # dy = nodes[i][1] - nodes[j][1]
                # distances[i][j] = math.sqrt(dx*dx + dy*dy)

    dp = []
    for i in range(n):
        dp.append([1e10] * m)
    
    # 初始化DP表
    if close:
        # 考虑回到起点的情况
        for i in range(n):
            dp[i][0] = distances[i][0]
    else:
        # 不考虑回到起点的情况
        for i in range(n):
            dp[i][0] = 0

    for j in range(1, m):
        for i in range(1, n):
            dp[i][j] = 1e10

            if j >> (i-1) & 1:
                continue
        
            for k in range(1, n):
                if not (1 << (k-1) & j):
                    continue

                tmp = distances[i][k] + dp[k][j ^ (1 << (k-1))]
                if tmp < dp[i][j]:
                    dp[i][j] = tmp

    # 初始化路径并插入起点
    path = [0]
    s = m - 1
    while True:
        minValue = 1e10
        index = 0
        for i in range(1, n):
            if not ((1 << (i-1)) & s):
                continue
        
            tmp = distances[path[-1]][i] + dp[i][s ^ (1 << (i-1))]
            if tmp < minValue:
                minValue = tmp
                index = i
        
        path.append(index)
        s = s ^ (1 << (index-1))

        if not s:
            break
    
    return path
 class="hljs-button signin active" data-title="登录复制" data-report-click="{"spm":"1001.2101.3001.4334"}">

class="hide-preCode-box">

• 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

3. 蚁群算法

本节参考

• 蚁群算法解决TSP问题详细讲解
• 全局路径规划算法

上面提到,当TSP问题的规模较大时,基于动态规划的方法效率太低,不适合求解.这时候可能难以求解全局最优解,而只能采用概率方式求解近似最优解.
蚁群算法(Ant Colony Optimization, ACO)是一种在图中寻找优化路径的几率性算法,其核心思想来源于蚂蚁寻找食物过程中发现路径的行为,是一种模拟进化算法.
蚁群求解TSP问题其实很直观,每一次迭代过程中会先随机投放m只蚂蚁,每只蚂蚁在每个节点时面临一个问题,即如何选择下一个节点?

3.1 节点的选择

节点的选择取决于两部分因素:

• 当前节点与其它节点的距离:该值是作为一个启发值引导蚂蚁优先选择到下一个节点代价更低的;
• 信息素:信息素的名字就是直接来源于生物学上的叫法,其作用是根据历史迭代中总结的"经验",历史路径的距离越小则信息素浓度越高.

往下一个节点移动的概率用公式表达如下:

p i j k ( t ) = { [ τ i j ( t ) ] α [ η i j ] β ∑ k ∈ unvisit [ τ i k ( t ) ] α [ η i k ] β , j ∈ unvisit k 0 , else η i j = 1 d i j p_{ij}^k(t)= class="MathJax_Display">{[τij(t)]α[ηij]β∑k∈unvisit[τik(t)]α[ηik]β,j∈unvisitk0,else" role="presentation">⎧⎩⎨[τij(t)]α[ηij]β∑k∈unvisit[τik(t)]α[ηik]β,0,j∈unvisitkelse$$\{\begin{array}{ll}\frac{{\left[{\tau }_{ij}(t)\right]}^{\alpha }{\left[{\eta }_{ij}\right]}^{\beta }}{\sum _{k\in \text{unvisit}}{\left[{\tau }_{ik}(t)\right]}^{\alpha }{\left[{\eta }_{ik}\right]}^{\beta }},& j\in {\text{unvisit}}_k\\ 0,& \text{else}\end{array}$$