python遺傳算法代碼，基于DEAP庫的python進化算法--遺傳算法實踐--最短路徑問題-技術動態-匯編語言學習筆記

python遺傳算法代碼，基于DEAP庫的python進化算法--遺傳算法實踐--最短路徑問題

2023-12-09 阅读 28 评论 0

摘要：文章目錄一.前言二.最短路徑問題描述三.最短路徑問題示例三.遺傳算方法求解最短路徑問題1.個體編碼2.代碼實現一.前言在優化問題中，網絡模型是很重要的一類問題，各種物流配送計劃、供應鏈管理、公路網絡設計等等問題都可以簡化為網絡模型。從這里開始，

文章目錄

- - 一.前言
  - 二.最短路徑問題描述
  - 三.最短路徑問題示例
  - 三.遺傳算方法求解最短路徑問題
  - - 1.個體編碼
    - 2.代碼實現

一.前言

在優化問題中，網絡模型是很重要的一類問題，各種物流配送計劃、供應鏈管理、公路網絡設計等等問題都可以簡化為網絡模型。從這里開始，我們會進入基本網絡模型，回顧最短路徑、最大流量、最小費用流、最小生成樹等網絡模型中的基本問題。

二.最短路徑問題描述

最短路徑問題是在給定權的有向圖或無向圖中，從連接兩個節點的邊上尋找權數之和最小的路徑的問題。
在這里插入圖片描述

三.最短路徑問題示例

示例問題如圖所示：
在這里插入圖片描述
每條邊上顯示該邊的長度，求從節點1到節點10的最短路徑

三.遺傳算方法求解最短路徑問題

1.個體編碼

一種編碼方案是使用二進制序列對邊進行編碼，為每條邊分配一個二進制變量，為1代表選擇該邊加入路徑，為0則代表不選擇該邊。但是這樣的編碼方式會生成大量的不可行解，相對于搜索空間，可行域極小，難以找到可行解。
一種編碼方案是用優先度對節點進行編碼：要想獲得一條可行路徑，需要從起始節點到結束節點依次將有路徑連接的相鄰接點放入備選解中。而每一次沿路徑前進中可能會有多個節點作為下一步選擇，節點的優先度就代表了在有多個選項的下一個節點中，要選擇哪個節點放入備選解

2.代碼實現

遺傳算法操作：

個體編碼-用優先度對個體進行編碼
評價函數-用字典保存每條路徑的長度，根據路徑索引對應長度，對求得路徑長度加和作為評價函數，此時為最小化問題。
育種選擇：錦標賽選擇
變異算法：交叉-有序交叉，突變-亂序突變
環境選擇：子代完全代替父代，無精英保留

#!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

可視化
在這里插入圖片描述

原文链接：https://hbdhgg.com/4/193653.html

发表评论: