在優化問題中,網絡模型是很重要的一類問題,各種物流配送計劃、供應鏈管理、公路網絡設計等等問題都可以簡化為網絡模型。從這里開始,我們會進入基本網絡模型,回顧最短路徑、最大流量、最小費用流、最小生成樹等網絡模型中的基本問題。
最短路徑問題是在給定權的有向圖或無向圖中,從連接兩個節點的邊上尋找權數之和最小的路徑的問題。
示例問題如圖所示:
每條邊上顯示該邊的長度,求從節點1到節點10的最短路徑
遺傳算法操作:
#!usr/bin/env python
# -*- coding:utf-8 _*-
"""
@author: liujie
@software: PyCharm
@file: 最短路徑.py
@time: 2020/11/29 16:30
"""
import numpy as np
import matplotlib.pyplot as plt
import random
from deap import creator,tools,baseparams = {'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)# 生成序列編碼-優先級序列
gen_size = 10
toolbox = base.Toolbox()
toolbox.register('Sequence',np.random.permutation,gen_size)
# 注冊個體
toolbox.register('Individual',tools.initIterate,creator.Individual,toolbox.Sequence)
# 注冊種群
toolbox.register('Population',tools.initRepeat,list,toolbox.Individual)# 解碼
# 存儲每個節點的可行路徑,用于解碼
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-9index= np.argmax(priority)nextNode = toBeSelected[index]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 eval(ind):# 將優先度序列轉換為可行路徑path = decode(ind) # 路徑:節點順序表示pathEdge = list(zip(path[::1], path[1::1])) # 路徑:用邊表示pathLen = 0for 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',eval)
# 注冊遺傳算法需要的工具
toolbox.register('select',tools.selTournament,tournsize=2)
toolbox.register('mate',tools.cxOrdered) # 有序交叉
toolbox.register('mutate',tools.mutShuffleIndexes,indpb = 0.5)# 創建統計對象
stats = tools.Statistics(key=lambda ind : ind.fitness.values)
stats.register('avg',np.mean)
stats.register('std',np.std)
stats.register('min',np.min)
stats.register('max',np.max)# 創建日志對象
logbook = tools.Logbook()
logbook.header = 'gen','avg','std','min','max'# 遺傳算法操作
pop_size = 100
N_GEN = 100
CXPB = 0.8
MUTPB = 0.2# 生成種群
pop = toolbox.Population(n = pop_size)# 評價初代種群
invalid_ind = [ind for ind in pop if not ind.fitness.valid]
fitnesses = list(map(toolbox.evaluate,invalid_ind))
for ind,fit in zip(invalid_ind,fitnesses):ind.fitness.values = fit
record = stats.compile(pop)
logbook.record(gen=0,**record)# 遺傳迭代
for gen in range(1+N_GEN):# 配種選擇selectTour = toolbox.select(pop,pop_size)# 復制selectInd = list(map(toolbox.clone,selectTour))# 交叉for child1,child2 in zip(selectInd[::2],selectInd[1::2]):if random.random() < CXPB:toolbox.mate(child1,child2)del child1.fitness.valuesdel child2.fitness.values# 變異for ind in selectInd:if random.random() < MUTPB:toolbox.mutate(ind)del ind.fitness.values# 對于被改變的個體,重新計算其適應度invalid_ind = [ind for ind in selectInd if not ind.fitness.valid]fitnesses = list(map(toolbox.evaluate,invalid_ind))for ind,fit in zip(invalid_ind,fitnesses):ind.fitness.values = fit# 精英育種-加速迭代combinedPop = pop + selectIndpop = tools.selBest(combinedPop,pop_size)# 記錄record = stats.compile(pop)logbook.record(gen = gen,**record)print(logbook)# 輸出結果
bestInd = tools.selBest(pop,1)[0]
bestFit = bestInd.fitness.values[0]
print('最優解為:',str(decode(bestInd)))
print('最短路徑為:',bestFit)# 可視化
min = logbook.select('min')
avg = logbook.select('avg')
gen = logbook.select('gen')
plt.plot(gen,min,'b-',label = 'MIN_FITNESS')
plt.plot(gen,avg,'r-',label = 'AVG_FITNESS')
plt.xlabel('gen')
plt.ylabel('fitness')
plt.legend(loc = 'best')
plt.tight_layout()
plt.show()
運行結果
gen avg std min max
0 119.58 13.8124 101 148
0 106.4 3.95221 101 111
1 102.87 2.50462 101 107
2 101 0 101 101
3 101 0 101 101
4 101 0 101 101
5 101 0 101 101
6 101 0 101 101
7 101 0 101 101
8 101 0 101 101
9 101 0 101 101
10 101 0 101 101
11 101 0 101 101
12 101 0 101 101
13 101 0 101 101
14 101 0 101 101
15 101 0 101 101
16 101 0 101 101
17 101 0 101 101
18 101 0 101 101
19 101 0 101 101
20 101 0 101 101
21 101 0 101 101
22 101 0 101 101
23 101 0 101 101
24 101 0 101 101
25 101 0 101 101
26 101 0 101 101
27 101 0 101 101
28 101 0 101 101
29 101 0 101 101
30 101 0 101 101
31 101 0 101 101
32 101 0 101 101
33 101 0 101 101
34 101 0 101 101
35 101 0 101 101
36 101 0 101 101
37 101 0 101 101
38 101 0 101 101
39 101 0 101 101
40 101 0 101 101
41 101 0 101 101
42 101 0 101 101
43 101 0 101 101
44 101 0 101 101
45 101 0 101 101
46 101 0 101 101
47 101 0 101 101
48 101 0 101 101
49 101 0 101 101
50 101 0 101 101
51 101 0 101 101
52 101 0 101 101
53 101 0 101 101
54 101 0 101 101
55 101 0 101 101
56 101 0 101 101
57 101 0 101 101
58 101 0 101 101
59 101 0 101 101
60 101 0 101 101
61 101 0 101 101
62 101 0 101 101
63 101 0 101 101
64 101 0 101 101
65 101 0 101 101
66 101 0 101 101
67 101 0 101 101
68 101 0 101 101
69 101 0 101 101
70 101 0 101 101
71 101 0 101 101
72 101 0 101 101
73 101 0 101 101
74 101 0 101 101
75 101 0 101 101
76 101 0 101 101
77 101 0 101 101
78 101 0 101 101
79 101 0 101 101
80 101 0 101 101
81 101 0 101 101
82 101 0 101 101
83 101 0 101 101
84 101 0 101 101
85 101 0 101 101
86 101 0 101 101
87 101 0 101 101
88 101 0 101 101
89 101 0 101 101
90 101 0 101 101
91 101 0 101 101
92 101 0 101 101
93 101 0 101 101
94 101 0 101 101
95 101 0 101 101
96 101 0 101 101
97 101 0 101 101
98 101 0 101 101
99 101 0 101 101
100 101 0 101 101
最優解為: [1, 3, 6, 9, 10]
最短路徑為: 101.0
可視化
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态