遗传算法实践(四) 最短路径问题

2019-07-15 本文已影响0人 ChaoesLuol

前言

在优化问题中，网络模型是很重要的一类问题，各种物流配送计划、供应链管理、公路网络设计等等问题都可以简化为网络模型。从这里开始我们会进入基本网络模型，回顾最短路径、最大流量、最小费用流、最小生成树等网络模型中的基本问题。

最短路径问题描述

最短路径问题是在给定权的有向图/无向图中，从连接两个节点的边上寻找权数之和最小的路径的问题。

在由 $m$ 个节点组成的有向图 $G=(V,A)$ 中，当弧 $(i,j)$ 的距离 $c_{ij}$ 给定时，最短路径问题可以被描述为0-1整数规划问题：
$min\ z=\sum_{i=1}^{m}\sum_{j=1}^{m}c_{ij}x_{ij} \\s.t. \sum_{j=1}^{m}x_{ij}-\sum_{k=1}^{m}x_{ki}=\left\{ \begin{array} 11,\ i=1 \\ 0,\ i=2,3,...,m-1\\ -1,\ i=m \end{array} \right. \\x_{ij}=0 \ or \ 1\ (i,j=1,2,...,m)$
$x_{ij}$ 是边 $(i,j)$ 的决策变量，为1时代表选择该边，为0时代表不选择该边。

求解这类问题的经典算法有Dijkstra算法，BellmanFord算法，Warshall-Floyd算法等，这里我们用遗传算法来进行求解。

最短路径问题示例

示例问题如图所示：

shortest path problem_description

每条边上显示该边的长度（或者理解为cost），求从节点1到节点10的最短路径。

i	j	$c_{ij}$
1	2	36
1	3	27
2	4	18
2	5	20
2	3	13
3	5	12
3	6	23
4	7	11
4	8	32
5	4	16
5	6	30
6	7	12
6	9	38
7	8	20
7	9	32
8	9	15
8	10	24
9	10	13

遗传算法求解最短路径问题

个体编码

一个比较自然的编码方案是使用二进制序列对边进行编码，为每条边分配一个二进制变量，为1代表选择该边加入路径，为0则代表不选择该边。但是这样的编码方式会生成大量的不可行解，相对于搜索空间，可行域极小，难以找到可行解。

另一种编码方案是用优先度对节点进行编码：要想获得一条可行路径，需要从起始节点到结束节点依次将有路径连接的相邻节点放入备选解中。而每一次沿路径前进中可能会有多个节点作为下一步选择，节点的优先度就代表了在有多个选项的下一个节点中，要选择哪个节点放入备选解。

优先度编码的解码方式如下：

Step 1: 生成与节点 $v_i(i=1,2,...,m-1)$ 邻接的节点集合 $S_i$ ，将路径初始化为 $\empty$ ，当前节点初始化为 $v_0$ ，目标节点设置为 $v_e$ 。
Step 2: 从当前节点 $v_i$ 出发，在当前节点的邻接节点集合 $S_i$ 中选择优先度最高的节点 $v_q$ ，加入路径，并从邻接节点集中删除选中的节点 $S_i\leftarrow S_i \backslash \{v_q\}$ ；
Step 3: 当 $v_i\ne v_e$ 时，重复Step 2。

这样就可以基于优先度，生成从 $v_0$ 到 $v_e$ 的一条可行路径。

其他遗传算法操作

评价函数：用字典保存每条路径长度，根据路径索引对应长度，对求得路径长度加和作为评价函数；此时为最小化问题
育种选择：binary锦标赛选择
变异算法：交叉-有序交叉(OX)，突变-乱序突变(Shuffle Index)
环境选择：子代完全替换父代(无精英保留)

代码示例

## 环境设定
import numpy as np
import matplotlib.pyplot as plt
from deap import base, tools, creator, algorithms
import random

params = {
    'font.family': 'serif',
    'figure.dpi': 300,
    'savefig.dpi': 300,
    'font.size': 12,
    'legend.fontsize': 'small'
}
plt.rcParams.update(params)

# -------------------------
## 问题定义
creator.create('FitnessMin', base.Fitness, weights=(-1.0,))
creator.create('Individual', list, fitness=creator.FitnessMin)

## 个体编码
geneLength = 10
toolbox = base.Toolbox()
toolbox.register('genPerm', np.random.permutation, geneLength)
toolbox.register('individual', tools.initIterate, creator.Individual, toolbox.genPerm)

## 解码
# 存储每个节点的可行路径，用于解码
nodeDict = {'1':[2,3], '2':[3,4,5], '3':[5,6], '4':[7,8], '5':[4,6], '6':[7,9], '7':[8,9],
            '8':[9,10], '9':[10]}
def decode(ind):
    # 输入一个优先度序列之后，返回一条从节点1到节点10的可行路径
    path = [1]
    while not path[-1] == 10:
        curNode = path[-1] # 当前所在节点
        toBeSelected = nodeDict[str(curNode)] # 获取可以到达的下一个节点列表
        priority = np.asarray(ind)[np.asarray(toBeSelected)-1] # 获取优先级,注意列表的index是0-9
        nextNode = toBeSelected[np.argmax(priority)]
        path.append(nextNode)
    return path
        
## 评价函数
# 存储距离矩阵，用于评价个体
costDict = {'12':36, '13':27, '24':18, '25':20, '23':13, '35':12, '36':23, 
            '47':11, '48':32, '54':16, '56':30, '67':12, '69':38, '78':20, 
            '79':32, '89':15, '810':24, '910':13}
def evaluate(ind):
    path = decode(ind) # 路径：节点顺序表示
    pathEdge = list(zip(path[::1], path[1::1]))# 路径：用边表示
    pathLen = 0
    for pair in pathEdge:
        key = str(pair[0]) + str(pair[1])
        if not key in costDict:
            raise Exception("Invalid path!", path)       
        pathLen += costDict[key] # 将该段路径长度加入
    return (pathLen),
toolbox.register('evaluate', evaluate)

## 数据记录
stats = tools.Statistics(key=lambda ind:ind.fitness.values)
stats.register('min', np.min)
stats.register('avg', np.mean)
stats.register('std', np.std)

## 注册需要的工具
toolbox.register('select', tools.selTournament, tournsize=2)
toolbox.register('mate', tools.cxOrdered)
toolbox.register('mutate', tools.mutShuffleIndexes, indpb=0.5)

## 注册参数
toolbox.popSize = 100
toolbox.ngen = 200
toolbox.cxpb = 0.8
toolbox.mutpb = 0.1

## 生成初始族群
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
pop = toolbox.population(toolbox.popSize)

# -------------------------
## 遗传算法
pop, logbook= algorithms.eaSimple(pop, toolbox, cxpb=toolbox.cxpb, mutpb=toolbox.mutpb, 
                    ngen=toolbox.ngen, stats=stats, verbose=True)

计算结果：

## 输出结果
bestInd = tools.selBest(pop,1)[0]
bestFit = bestInd.fitness.values[0]
print('最优解为: '+str(decode(bestInd)))
print('最短路径为: '+str(bestFit))

## 可视化迭代过程
maxFit = logbook.select('min')
avgFit = logbook.select('avg')
plt.plot(maxFit, 'b-', label='Minimum Fitness')
plt.plot(avgFit, 'r-', label='Average Fitness')
plt.xlabel('# Gen')
plt.ylabel('Fitness')
plt.legend(loc='best')

## 结果
# 最优解为: [1, 3, 6, 9, 10]
# 最短路径为: 101.0

迭代过程可视化如下：

Shortest path problem_priority based coding

得到的路径如下：

shortest path problem_rsl