熟女人妻一区二区在线,99re自拍视频,国产亚洲制服中文字幕

最大流量問題描述

最大流量問題時考慮在網(wǎng)絡(luò)中各路徑承受能力的情況下，最大限度的運送同種物品的問題，即在網(wǎng)絡(luò)模型中給定各邊容量的情況下，求從出發(fā)地到目的地的最大運送物品數(shù)量。

在由 $m$ 個節(jié)點的點集合 $V$ 和 $n$ 個邊的邊集合 $A$ 組成的圖 $G=(V,A)$ 中，當(dāng)各邊 $(i,j)$ 對應(yīng)的容量 $u_{ij}$ 給定時，只有一個輸入口(source)和一個輸出口(sink)的最大流量的數(shù)學(xué)模型可以描述為：
$max\ z=f \\s.t.\ \sum_{j\in Suc(i)}x_{ij}-\sum_{k\in Pre(i)}x_{ki}=\left\{ \begin{array} ff,\ i=1\\ 0,\ i=2,3,...,m-1\\ -f,\ i=m \end{array} \right. \\0 \le x_{ij} \le u_{ij}, \ i,j=1,2,...,m \\f \ge 0$
其中 $Suc(i)$ 和 $Pre(i)$ 分別為節(jié)點 $i$ 的后續(xù)節(jié)點集和前續(xù)節(jié)點集， $\sum_{k\in Pre(i)}x_{ki}$ 表示從其他節(jié)點進(jìn)入到節(jié)點 $i$ 的總流量，而 $\sum_{k\in Suc(i)}x_{ij}$ 表示從節(jié)點 $i$ 流出的流量。

求解最大流量問題的代表性算法有Ford-Fulkerson法和Maximum Flow法等。

最大流量問題示例

一個最大流量問題的示例問題如圖所示：

MaxFlowProb_description

各邊的容量限制如下表：

i	j	$c_{ij}$
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

遺傳算法求解最大流量問題

個體編碼

此處依然采用優(yōu)先級編碼，對各個節(jié)點給予優(yōu)先級；在生成路徑時根據(jù)優(yōu)先級挑選路徑下一步的節(jié)點。

解碼

在解碼過程中，需要不斷生成從源節(jié)點(source)向后的路徑，為路徑上所有邊分配流量，并剔除無法再承載的路徑。具體過程如下：

Step 1：基于優(yōu)先度生成路徑 $P$ ，其過程同之前的最短路徑問題；
Step 2：將該條路徑的流量設(shè)置為路徑上最小邊的流量 $f\leftarrow min\{u_{ij}|(i,j)\in P\}$ ，將該條路徑流量累加至總流量 $f_{overall}\leftarrow f_{overall}+f$ ；
Step 3：更新各邊上的容量 $u_{ij}\leftarrow u_{ij}-f, \forall\ (i,j)\in P$ ；
Step 4：更新各節(jié)點的后續(xù)節(jié)點集和前續(xù)節(jié)點集，如果有 $u_{ij}=0$ ，意味著路徑 $ij$ 已經(jīng)不能承受更多負(fù)載，從節(jié)點 $i$ 的后續(xù)節(jié)點集 $S_i$ 中刪除 $j$ ，即 $S_i\leftarrow S_i \backslash\{j\},\ \forall(i,j)\in P\ and\ u_{ij}=0$ ；對于后續(xù)節(jié)點集為空的節(jié)點 $i$ ，從該節(jié)點向后已經(jīng)沒有可行路徑，從 $i$ 的前續(xù)節(jié)點集 $P_i$ 的所有節(jié)點的后續(xù)節(jié)點集中刪除 $i$ ，即 $S_j \leftarrow S_j\backslash\{i\},\ \forall j \in P_i,\ i \in V\ and\ S_i=\emptyset$ ；
Step 5：如果 $S_0 \ne \emptyset$ ，回到Step 1，繼續(xù)迭代；否則返回總流量 $f_{overall}$ 。

其他遺傳算法操作

評價函數(shù)：解碼過程中得到的總流量 $f_{overall}$
育種選擇：binary錦標(biāo)賽選擇
變異算法：交叉-有序交叉(OX)，突變-亂序突變(Shuffle Index)
環(huán)境選擇：子代完全替換父代(無精英保留)

代碼示例

完整代碼如下：

## 環(huán)境設(shè)定
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)

## 評價函數(shù)
# 類似鏈表，用字典存儲每個節(jié)點的可行路徑，用于解碼
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):
    '''輸入一個優(yōu)先度序列之后，返回一條從節(jié)點1到節(jié)點25的可行路徑 '''
    path = [1]
    endNode = len(ind)
    while not path[-1] == endNode:
        curNode = path[-1]  # 當(dāng)前所在節(jié)點
        if nodeDict[str(curNode)]:  # 當(dāng)前節(jié)點指向的下一個節(jié)點不為空時，到達(dá)下一個節(jié)點
            toBeSelected = nodeDict[str(curNode)]  # 獲取可以到達(dá)的下一個節(jié)點列表
        else:
            return path
        priority = np.asarray(ind)[np.asarray(
            toBeSelected)-1]  # 獲取優(yōu)先級,注意列表的index是0-9
        nextNode = toBeSelected[np.argmax(priority)]
        path.append(nextNode)
    return path


# 存儲每條邊的剩余容量，用于計算路徑流量和更新節(jié)點鏈表
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對應(yīng)的key
        edgeCapacity.append(capacityDict[key])  # 該邊對應(yīng)的剩余容量
    pathFlow = min(edgeCapacity)  # 路徑上的最大流量
    # 更新各邊的剩余容量
    for key in keys:
        capacityDict[key] -= pathFlow  # 注意這里是原位修改
    return pathFlow


def updateNodeDict(capacityDict, nodeDict):
    ''' 對剩余流量為0的節(jié)點，刪除節(jié)點指向；對于鏈表指向為空的節(jié)點，由于沒有下一步可以移動的方向，
    從其他所有節(jié)點的指向中刪除該節(jié)點
    '''
    for edge, capacity in capacityDict.items():
        if capacity == 0:
            key, toBeDel = str(edge).split(',')  # 用來索引節(jié)點字典的key，和需要刪除的節(jié)點toBeDel
            if int(toBeDel) in nodeDict[key]:
                nodeDict[key].remove(int(toBeDel))
    delList = []
    for node, nextNode in nodeDict.items():
        if not nextNode:  # 如果鏈表指向為空的節(jié)點，從其他所有節(jié)點的指向中刪除該節(jié)點
            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):
    '''評價函數(shù)'''
    # 初始化所需變量
    nodeDictCopy = copy.deepcopy(nodeDict)  # 淺復(fù)制
    capacityDictCopy = copy.deepcopy(capacityDict)
    paths = []
    pathFlows = []
    fOverall = 0
    # 開始循環(huán)
    while nodeDictCopy['1']:
        path = genPath(ind, nodeDictCopy)  # 生成路徑
        # 當(dāng)路徑無法抵達(dá)終點，說明經(jīng)過這個節(jié)點已經(jīng)無法往下走，從所有其他節(jié)點的指向中刪除該節(jié)點
        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) # 更新節(jié)點鏈表
    if outputPaths:
        return fOverall, paths, pathFlows
    return fOverall,
toolbox.register('evaluate', evaluate)

# 迭代數(shù)據(jù)
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)

# --------------------
# 遺傳算法參數(shù)
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)

計算結(jié)果：

## 輸出結(jié)果
bestInd = tools.selBest(pop,1)[0]
fOverall, paths, pathFlows = evaluate(bestInd, outputPaths=True)
print('最優(yōu)解路徑為: '+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')

##結(jié)果：
# 最優(yōu)解路徑為: [[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

最優(yōu)解對應(yīng)的各條邊上的負(fù)載如圖所示：

MaxFlowProb_rsl

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

遺傳算法實踐(五) 最大流量問題

遺傳算法實踐(五) 最大流量問題

最大流量問題描述

最大流量問題示例

遺傳算法求解最大流量問題

個體編碼

解碼

其他遺傳算法操作

代碼示例

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

i	j	$c_{ij}$
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

i	j	$c_{ij}$
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

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

遺傳算法實踐(五) 最大流量問題

最大流量問題描述

最大流量問題示例

遺傳算法求解最大流量問題

個體編碼

解碼

其他遺傳算法操作

代碼示例

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

i	j	$c_{ij}$
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