最大流量问题描述
最大流量问题时考虑在网络中各路径承受能力的情况下，最大限度的运送同种物品的问题，即在网络模型中给定各边容量的情况下，求从出发地到目的地的最大运送物品数量。
在由个节点的点集合
和
个边的边集合
组成的图
中，当各边
对应的容量
给定时，只有一个输入口(source)和一个输出口(sink)的最大流量的数学模型可以描述为：
其中和
分别为节点
的后续节点集和前续节点集，
表示从其他节点进入到节点
的总流量，而
表示从节点
流出的流量。
求解最大流量问题的代表性算法有Ford-Fulkerson法和Maximum Flow法等。
最大流量问题示例
一个最大流量问题的示例问题如图所示：
MaxFlowProb_description
各边的容量限制如下表：
| i | j | |
|---|---|---|
| 1 | 2 | 18 |
| 1 | 3 | 19 |
| 1 | 4 | 17 |
| 2 | 3 | 13 |
| 2 | 5 | 16 |
| 2 | 6 | 14 |
| 3 | 4 | 15 |
| 3 | 6 | 16 |
| 3 | 7 | 17 |
| 4 | 7 | 19 |
| 5 | 8 | 19 |
| 6 | 5 | 15 |
| 6 | 8 | 16 |
| 6 | 9 | 15 |
| 6 | 10 | 18 |
| 7 | 6 | 15 |
| 7 | 10 | 13 |
| 8 | 9 | 17 |
| 8 | 11 | 18 |
| 9 | 10 | 14 |
| 9 | 11 | 19 |
| 10 | 11 | 17 |
遗传算法求解最大流量问题
个体编码
此处依然采用优先级编码，对各个节点给予优先级；在生成路径时根据优先级挑选路径下一步的节点。
解码
在解码过程中，需要不断生成从源节点(source)向后的路径，为路径上所有边分配流量，并剔除无法再承载的路径。具体过程如下：
- Step 1：基于优先度生成路径
，其过程同之前的最短路径问题；
- Step 2：将该条路径的流量设置为路径上最小边的流量
，将该条路径流量累加至总流量
；
- Step 3：更新各边上的容量
；
- Step 4：更新各节点的后续节点集和前续节点集，如果有
，意味着路径
已经不能承受更多负载，从节点
的后续节点集
中删除
，即
；对于后续节点集为空的节点
的所有节点的后续节点集中删除
；
- Step 5：如果
，回到Step 1，继续迭代；否则返回总流量
。
其他遗传算法操作
- 评价函数：解码过程中得到的总流量
- 育种选择：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)
import copy
# --------------------
## 问题定义
creator.create('FitnessMax', base.Fitness, weights=(1.0,)) # 最大化问题
creator.create('Individual', list, fitness=creator.FitnessMax)
## 个体编码
toolbox = base.Toolbox()
geneLength = 11
toolbox.register('perm', np.random.permutation, geneLength)
toolbox.register('individual', tools.initIterate,
creator.Individual, toolbox.perm)
## 评价函数
# 类似链表，用字典存储每个节点的可行路径，用于解码
nodeDict = {'1': [2, 3, 4], '2': [3, 5, 6], '3': [4, 6, 7], '4': [7], '5': [8], '6': [5, 8, 9, 10],
'7': [6, 10], '8': [9, 11], '9': [10, 11], '10': [11]}
def genPath(ind, nodeDict=nodeDict):
'''输入一个优先度序列之后，返回一条从节点1到节点25的可行路径 '''
path = [1]
endNode = len(ind)
while not path[-1] == endNode:
curNode = path[-1] # 当前所在节点
if nodeDict[str(curNode)]: # 当前节点指向的下一个节点不为空时，到达下一个节点
toBeSelected = nodeDict[str(curNode)] # 获取可以到达的下一个节点列表
else:
return path
priority = np.asarray(ind)[np.asarray(
toBeSelected)-1] # 获取优先级,注意列表的index是0-9
nextNode = toBeSelected[np.argmax(priority)]
path.append(nextNode)
return path
# 存储每条边的剩余容量，用于计算路径流量和更新节点链表
capacityDict = {'1,2': 60, '1,3': 60, '1,4': 60, '2,3': 30, '2,5': 40, '2,6': 30,
'3,4': 30, '3,6': 50, '3,7': 30, '4,7': 40, '5,8': 60, '6,5': 20,
'6,8': 30, '6,9': 40, '6,10': 30, '7,6': 20, '7,10': 40, '8,9': 30,
'8,11': 60, '9,10': 30, '9,11': 50, '10,11': 50}
def traceCapacity(path, capacityDict):
''' 获取给定path的最大流量，更新各边容量 '''
pathEdge = list(zip(path[::1], path[1::1]))
keys = []
edgeCapacity = []
for edge in pathEdge:
key = str(edge[0]) + ',' + str(edge[1])
keys.append(key) # 保存edge对应的key
edgeCapacity.append(capacityDict[key]) # 该边对应的剩余容量
pathFlow = min(edgeCapacity) # 路径上的最大流量
# 更新各边的剩余容量
for key in keys:
capacityDict[key] -= pathFlow # 注意这里是原位修改
return pathFlow
def updateNodeDict(capacityDict, nodeDict):
''' 对剩余流量为0的节点，删除节点指向；对于链表指向为空的节点，由于没有下一步可以移动的方向，
从其他所有节点的指向中删除该节点
'''
for edge, capacity in capacityDict.items():
if capacity == 0:
key, toBeDel = str(edge).split(',') # 用来索引节点字典的key，和需要删除的节点toBeDel
if int(toBeDel) in nodeDict[key]:
nodeDict[key].remove(int(toBeDel))
delList = []
for node, nextNode in nodeDict.items():
if not nextNode: # 如果链表指向为空的节点，从其他所有节点的指向中删除该节点
delList.append(node)
for delNode in delList:
for node, nextNode in nodeDict.items():
if delNode in nextNode:
nodeDict[node].remove(delNode)
def evaluate(ind, outputPaths=False):
'''评价函数'''
# 初始化所需变量
nodeDictCopy = copy.deepcopy(nodeDict) # 浅复制
capacityDictCopy = copy.deepcopy(capacityDict)
paths = []
pathFlows = []
fOverall = 0
# 开始循环
while nodeDictCopy['1']:
path = genPath(ind, nodeDictCopy) # 生成路径
# 当路径无法抵达终点，说明经过这个节点已经无法往下走，从所有其他节点的指向中删除该节点
if path[-1] != 11:
for node, nextNode in nodeDictCopy.items():
if path[-1] in nextNode:
nodeDictCopy[node].remove(path[-1])
continue
paths.append(path) # 保存路径
pathFlow = traceCapacity(path, capacityDictCopy) # 计算路径最大流量
pathFlows.append(pathFlow) # 保存路径的流量
fOverall += pathFlow # 更新最大流量
updateNodeDict(capacityDictCopy, nodeDictCopy) # 更新节点链表
if outputPaths:
return fOverall, paths, pathFlows
return fOverall,
toolbox.register('evaluate', evaluate)
# 迭代数据
stats = tools.Statistics(key=lambda ind:ind.fitness.values)
stats.register('max', np.max)
stats.register('avg', np.mean)
stats.register('std', np.std)
# 生成初始族群
toolbox.popSize = 100
toolbox.register('population', tools.initRepeat, list, toolbox.individual)
pop = toolbox.population(toolbox.popSize)
# 注册工具
toolbox.register('select', tools.selTournament, tournsize=2)
toolbox.register('mate', tools.cxOrdered)
toolbox.register('mutate', tools.mutShuffleIndexes, indpb=0.5)
# --------------------
# 遗传算法参数
toolbox.ngen = 200
toolbox.cxpb = 0.8
toolbox.mutpb = 0.05
# 遗传算法主程序部分
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]
fOverall, paths, pathFlows = evaluate(bestInd, outputPaths=True)
print('最优解路径为: '+str(paths))
print('各路径上的流量为：'+str(pathFlows))
print('最大流量为: '+str(fOverall))
## 可视化迭代过程
maxFit = logbook.select('max')
avgFit = logbook.select('avg')
plt.plot(maxFit, 'b-', label='Maximum Fitness')
plt.plot(avgFit, 'r-', label='Average Fitness')
plt.xlabel('# Gen')
plt.ylabel('Fitness')
plt.legend(loc='best')
##结果：
# 最优解路径为: [[1, 4, 7, 6, 8, 9, 11], [1, 4, 7, 10, 11], [1, 3, 7, 10, 11], [1, 3, 6, 8, 9, 11], [1, 3, 6, 9, 11], [1, 3, 6, 9, 10, 11], [1, 2, 3, 6, 5, 8, 11], [1, 2, 5, 8, 11], [1, 2, 6, 5, 8, 11]]
# 各路径上的流量为：[20, 20, 20, 10, 20, 10, 10, 40, 10]
# 最大流量为: 160
MaximumFlowProblem_iterations
最优解对应的各条边上的负载如图所示：
MaxFlowProb_rsl
网友评论