基于DEAP库的python进化算法–遗传算法实践–最短路径问题

1147-柳同学

发表文章数:589

热门标签

, ,
首页 » 算法 » 正文

一.前言

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

二.最短路径问题描述

最短路径问题是在给定权的有向图或无向图中,从连接两个节点的边上寻找权数之和最小的路径的问题。
基于DEAP库的python进化算法--遗传算法实践--最短路径问题

三.最短路径问题示例

示例问题如图所示:
基于DEAP库的python进化算法--遗传算法实践--最短路径问题
每条边上显示该边的长度,求从节点1到节点10的最短路径
基于DEAP库的python进化算法--遗传算法实践--最短路径问题

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

1.个体编码

  1. 一种编码方案是使用二进制序列对边进行编码,为每条边分配一个二进制变量,为1代表选择该边加入路径,为0则代表不选择该边。但是这样的编码方式会生成大量的不可行解,相对于搜索空间,可行域极小,难以找到可行解。
  2. 一种编码方案是用优先度对节点进行编码:要想获得一条可行路径,需要从起始节点到结束节点依次将有路径连接的相邻接点放入备选解中。而每一次沿路径前进中可能会有多个节点作为下一步选择,节点的优先度就代表了在有多个选项的下一个节点中,要选择哪个节点放入备选解
    基于DEAP库的python进化算法--遗传算法实践--最短路径问题

2.代码实现

遗传算法操作:

  1. 个体编码-用优先度对个体进行编码
  2. 评价函数-用字典保存每条路径的长度,根据路径索引对应长度,对求得路径长度加和作为评价函数,此时为最小化问题。
  3. 育种选择:锦标赛选择
  4. 变异算法:交叉-有序交叉,突变-乱序突变
  5. 环境选择:子代完全代替父代,无精英保留
#!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,base

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)

# 生成序列编码-优先级序列
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-9
        index= 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 = 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',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.values
            del 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 + selectInd
    pop = 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

可视化
基于DEAP库的python进化算法--遗传算法实践--最短路径问题

未经允许不得转载:作者:1147-柳同学, 转载或复制请以 超链接形式 并注明出处 拜师资源博客
原文地址:《基于DEAP库的python进化算法–遗传算法实践–最短路径问题》 发布于2020-11-29

分享到:
赞(0) 打赏

评论 抢沙发

评论前必须登录!

  注册



长按图片转发给朋友

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏

Vieu3.3主题
专业打造轻量级个人企业风格博客主题!专注于前端开发,全站响应式布局自适应模板。

登录

忘记密码 ?

您也可以使用第三方帐号快捷登录

Q Q 登 录
微 博 登 录