Java教程
遗传算法5 更复杂的配货应用
本文主要是介绍遗传算法5 更复杂的配货应用，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
说明
在实际的应用中，我们首先关心：
- 1 目标是什么（目标函数）
- 2 都有哪些约束
本质上遗传算法解决的是有目标的随机搜索问题， 约束减少了不必要区域的随机搜索。
解决问题的标志是提出有效的方案，这个方案可以称为解，或者个体，或者说一行记录。按遗传算法的概念，若干个体构成了一个种群（一组解），其中每个个体都是一种随机搜索的方案。
在经过历次进化后，最后留下来的种群个体是高度相似的。
内容
1 场景
连锁商店(S)的配货问题。
- 1 商店有两类货物G1和G2,货物有重量和体积
- 2 商店有一定时间窗口可以收货（按小时，一天最多24个slot)
- 3 一共有两种货车，V1可以运送G1和G2, V2可以运送G2
- 4 V1和V2都有大小尺寸（会影响配送费）： V1L, V1M, V2L, V2M
- 5 商店定期会上报货物需求计划
目的：派送货物的总成本最低（基本上就是车次最少）
- 1 希望里程尽量短
- 2 货车的满载率尽量高
2 模型抽象
一个配送计划（一行）是一个个体，每一列都是可约束的条件。
简单起见，我们假设一天只有3个时间段(T1, T2),只有两个商店(S1,S2)
| S1.T1.G1 | S1.T1.G2 | S1.T2.G1 | S1.T2.G2 | S2.T1.G1 | S2.T1.G2 | S2.T2.G1 | S2.T2.G2 | T1.V1L | T1.V1M | T1.V2L | T1.V2M | T2.V1L | T2.V1M | T2.V2L | T2.V2M |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| x1 | x2 | x3 | x4 | x5 | x6 | x7 | x8 | x9 | x10 | x11 | x12 | x13 | x14 | x15 | x16 |
x1~x16 就是这个个体的染色体。
目标函数也很简单，假设各种车型的价格分别为p1~p4：
最小化： p1 * (T1.V1L + T2.V1L) + p2 * (T1.V1M + T2.V1M) + p3 * (T1.V2L + T2.V2L) + p4 * (T1.V2M + T2.V2M)
比较麻烦的是约束。
- 等号约束：确保相等。例如货物的配送数量和需求数量。
- < 约束： 确保不超过。例如配送获取的重量和体积不能超过货车的。
- 不等号约束：例如S1在T1不收货，那么T1的所有>0的方案都是无效的。
其他的一些常规性约束例如：
- x1在 [0, S1.G1] 任何一时刻的配货不会超过总需求
还有一些更复杂的约束：
- 如果s1和s2的地理距离比较近，那么可以安排同一批次的车
3 进一步分析
假设：
- 1 如果有单店需求大于一个车最大载量的，不需要运筹（专车配送）
- 2 店的数量可能很多，商品的数量可能很多，因此方案（个体）不能使用哑变量编码，否则会过大(宽表要变长表）
一家店，一个sku的必要字段限制为5。假设sku的数量为1000， 店铺的数量为1万，那么这个方案理论上的长度为5千万（向量）
| 商店 | 时间 | SKU编号 | 数量 | 运输车编号 |
|---|---|---|---|---|
| s1~s10000 | t0~t23 | k1~k10000 | 0~10000 | v1~v10000 |
实际上，每家门店在某个时刻的sku不会太多，否则光是装卸和理货就能崩溃了。所以我们不要一开始就建立一个大而全的问题，而是每次根据实际的需求进行初始化。
假设一家店每个周期报送的sku是20个，一共有1千家店，那么这个向量也就长度1万。一个配送方案形如：
s1| t0 | k1 | 1 | v1 …
比较直接的约束是：记在某个货车下的重量和体积不能超限。
这里需要根据方案中的v进行遍历，然后筛选出不合格的个体。
例如
# 找到违反约束条件的个体在种群中的索引，保存在向量exIdx中（如：若0、2、4号个体违反约束条件，则编程找出他们来）
exIdx1 = np.where(np.where(x == 3)[1] - np.where(x == 6)[1] < 0)[0]
比较麻烦或者说隐晦的约束有：
- 1 某些类型的货物不能用某些车
- 2 某些车运送了好几家店的货物，要确保运送时间能和店铺的运行时间衔接上
需要编写函数来将一些个体给去掉,例如原来的目标函数中引入了当时的种群（相当于是新的约束性随机结果）
def aimFunc(self, pop): # 目标函数，pop为传入的种群对象
Vars = pop.Phen # 得到决策变量矩阵
x1 = Vars[:, [0]] # 取出第一列得到所有个体的x1组成的列向量
x2 = Vars[:, [1]] # 取出第二列得到所有个体的x2组成的列向量
x3 = Vars[:, [2]] # 取出第三列得到所有个体的x3组成的列向量
x4 = Vars[:, [3]]
...
我们的函数就是以行向量为入参，将有问题（不可能）的个体摘出来。原来的一个简单版本是这样，直接处理列向量（某个维度）。最后将约束挂到CV上。
# 计算目标函数值，赋值给pop种群对象的ObjV属性
pop.ObjV = c1* x3 + c2 * x4
# 采用可行性法则处理约束，生成种群个体违反约束程度矩阵
# 约束
# 约束1：k1x1 + k2x2 - y1 - y2 = 0
cv1 = np.abs(k1* x1 + k2* x2 - x3 - x4)
# 约束2： x1m1 + x2m2 + M1 + M2 - M <=0
cv2 = x1 * m1 + x2 * m2 + M1 + M2 - M
# 约束3：x3 * 1day/ t1 - N1
cv3 = 1440 * x3/t1 - N1
# 约束4：x4 * 1day/t2 - N2
cv4 = 1440 * x4 / t2 - N2
# 约束5：y1 -n1 <=0
cv5 = x3 - n1
# 约束6：y2 -n2 <=0
cv6 = x4 - n2
pop.CV = np.hstack([cv1,cv2,cv3,cv4,cv5,cv6]) # 第1.2.3个约束
约束可以添加任意个，然后水平堆叠为矩阵(horizonal stack)。例如：
# 变量只有4个，添加到6个数值说明这是某一列
cv1 = [[True, True, True, True, True, True]]
cv2 = [[True, True, True, True, True, True]]
cv3 = [[True, True, True, True, True, True]]
CV = np.hstack([cv1,cv2,cv3])
---
array([[ True, True, True, True, True, True, True, True, True,
True, True, True, True, True, True, True, True, True]])
所以需要有一个更复杂的函数来满足配货的高级约束。
4 构造数据和简单约束的部分
假设现在有两家店s1和s2 ,需求如下
| 商店名 | SKU | 数量 | 体积 | 重量 |
|---|---|---|---|---|
| s1 | sku1 | 11 | 0.03 | 14.25 |
| s1 | sku2 | 16 | 0.04 | 16.35 |
| s2 | sku1 | 9 | 0.05 | 17.3 |
| s2 | sku2 | 5 | 0.04 | 17.3 |
| s2 | sku3 | 5 | 0.03 | 13.6 |
将一天按十分钟分为144个时隙：
- s1: 12:00~24:00 可以收货
- s2: 20:00~24:00 可以收货
问题简单定义如下：
import numpy as np
import geatpy as ea
# s1.sku1 = 11
# s1.sku2 = 16
# s2.sku1 = 9
# s2.sku2 = 5
# s2.sku3 = 5
class MyProblem(ea.Problem): # 继承Problem父类
def __init__(self):
name = 'MyProblem' # 初始化name（函数名称，可以随意设置）
M = 1 # 初始化M（目标维数）
maxormins = [1] # 初始化目标最小最大化标记列表，1：min；-1：max
Dim = 21 # 初始化Dim（决策变量维数）
varTypes = [1] * Dim # 初始化决策变量类型，0：连续；1：离散
# 决策变量下界
lb = [72,0,0, # s1.sku1:slot1, qty,vehicle
122,0,0, # s1.sku1:slot2, qty,vehicle
72,0,0, # s1.sku2:slot1, qty,vehicle
122,0,0, # s1.sku2:slot2, qty,vehicle
120,0,0, # s2.sku1:slot1, qty,vehicle
120,0,0, # s2.sku2:slot1, qty,vehicle
120,0,0, # s2.sku3:slot1, qty,vehicle
]
# 决策变量上界
ub = [121,11,5, # s1.sku1:slot1, qty,vehicle
143,11,5, # s1.sku1:slot2, qty,vehicle
121,16,5, # s1.sku2:slot1, qty,vehicle
143,16,5, # s1.sku2:slot1, qty,vehicle
143,9,5, # s2.sku1:slot1, qty,vehicle
143,5,5, # s2.sku2:slot1, qty,vehicle
143,5,5, # s2.sku3:slot1, qty,vehicle
]
lbin = [1]*Dim # 决策变量下边界
ubin = [1]*Dim # 决策变量上边界 # 调用父类构造方法完成实例化
ea.Problem.__init__(self, name, M, maxormins, Dim, varTypes, lb, ub, lbin, ubin)
def aimFunc(self, pop): # 目标函数，pop为传入的种群对象
Vars = pop.Phen # 得到决策变量矩阵
# 约束条件需要考虑的维度
# s1有两个sku在两个slot(两次收货)
group_num = 3 # 每组元素的值
s1_sku1_slot1 = Vars[:, [1 + 0*group_num]] # 取出第一列得到所有个体的x1组成的列向量
s1_sku1_slot2 = Vars[:, [1 + 1*group_num]]
s1_sku2_slot1 = Vars[:, [1 + 2*group_num]]
s1_sku2_slot2 = Vars[:, [1 + 3*group_num]]
s2_sku1_slot1 = Vars[:, [1 + 4*group_num]]
s2_sku2_slot1 = Vars[:, [1 + 5*group_num]]
s2_sku3_slot1 = Vars[:, [1 + 6*group_num]]
# 计算成本（目标）需要考虑的维度(使用的货车)
v1 = Vars[:, 2 + 0*group_num]
v2 = Vars[:, 2 + 1*group_num]
v3 = Vars[:, 2 + 2*group_num]
v4 = Vars[:, 2 + 3*group_num]
v5 = Vars[:, 2 + 4*group_num]
v6 = Vars[:, 2 + 5*group_num]
v7 = Vars[:, 2 + 6*group_num]
# print(type(Vars))
# print(Vars)
# 计算目标函数值，赋值给pop种群对象的ObjV属性
tem_result = fs.operation_dedup_match_sum([v1,v2,v3,v4,v5, v6, v7] ,car_list, price_list, method='rows' )
pop.ObjV = np.expand_dims(tem_result, axis=-1)
# 采用可行性法则处理约束，生成种群个体违反约束程度矩阵
# 约束类型：1.等号约束 2.例外约束 3.小于约束
# 约束1：配送的货物总数要和需求相等
cv1_s1_sku1 = np.abs(s1_sku1_slot1+s1_sku1_slot2 -11)
cv2_s1_sku2 = np.abs(s1_sku2_slot1+s1_sku2_slot2 -16)
cv3_s2_sku1 = np.abs(s2_sku1_slot1 -9)
cv4_s2_sku2 = np.abs(s2_sku2_slot1 -5)
cv5_s2_sku3 = np.abs(s2_sku3_slot1 -5)
pop.CV = np.hstack([cv1_s1_sku1,cv2_s1_sku2,cv3_s2_sku1,cv4_s2_sku2,cv5_s2_sku3]) # 将约束汇聚
可以看到时间，货品数量很容易在变量取值的时候约束
# -*- coding: utf-8 -*-
"""main.py"""
import geatpy as ea # import geatpy
# from MyProblem import MyProblem # 导入自定义问题接口
"""===============================实例化问题对象================================"""
problem = MyProblem() # 生成问题对象
"""==================================种群设置=================================="""
Encoding = 'RI' # 编码方式(用BG好像效率更高)
NIND = 100 # 种群规模
Field = ea.crtfld(Encoding, problem.varTypes, problem.ranges, problem.borders) # 创建区域描述器
population = ea.Population(Encoding, Field, NIND) # 实例化种群对象（此时种群还没被初始化，仅仅是完成种群对象的实例化）
"""================================算法参数设置================================="""
myAlgorithm = ea.soea_EGA_templet(problem, population) # 实例化一个算法模板对象
myAlgorithm.MAXGEN = 2000 # 最大进化代数
myAlgorithm.logTras = 1 # 设置每隔多少代记录日志，若设置成0则表示不记录日志
myAlgorithm.verbose = True # 设置是否打印输出日志信息
myAlgorithm.drawing = 0 # 设置绘图方式（0：不绘图；1：绘制结果图；2：绘制目标空间过程动画；3：绘制决策空间过程动画）
"""===========================调用算法模板进行种群进化==============--==========="""
[BestIndi, population] = myAlgorithm.run() # 执行算法模板，得到最优个体以及最后一代种群
# BestIndi.save() # 把最优个体的信息保存到文件中
"""==================================输出结果=================================="""
print('用时：%f 秒' % myAlgorithm.passTime)
print('评价次数：%d 次' % myAlgorithm.evalsNum)
if BestIndi.sizes != 0:
print('最优的目标函数值为：%s' % BestIndi.ObjV[0][0])
print('最优的控制变量值为：')
for i in range(BestIndi.Phen.shape[1]):
print(BestIndi.Phen[0, i])
else:
print('没找到可行解。')
---
...
1886| 186814 | 2000 | 5000 | 2.12222E+03 | 2000 | 5.12679E+02
1887| 186913 | 2000 | 5000 | 2.06522E+03 | 2000 | 4.37492E+02
1888| 187012 | 2000 | 4000 | 2.04545E+03 | 2000 | 2.98065E+02
1889| 187111 | 2000 | 5000 | 2.12903E+03 | 2000 | 6.08644E+02
1890| 187210 | 2000 | 5000 | 2.14894E+03 | 2000 | 5.82684E+02
1891| 187309 | 2000 | 5000 | 2.06383E+03 | 2000 | 4.32915E+02
1892| 187408 | 2000 | 5000 | 2.06667E+03 | 2000 | 4.42217E+02
输出结果
best_solution = pd.DataFrame([BestIndi.Phen[0]], columns=['s1.sku1.timeslot1' ,'s1.sku1.timeslot1.qty', 's1.sku1.timeslot1.vehicle',
's1.sku1.timeslot2' ,'s1.sku1.timeslot2.qty', 's1.sku1.timeslot2.vehicle',
's1.sku2.timeslot1' ,'s1.sku2.timeslot1.qty', 's1.sku2.timeslot1.vehicle',
's1.sku2.timeslot2' ,'s1.sku2.timeslot2.qty', 's1.sku2.timeslot2.vehicle',
's2.sku1.timeslot1' ,'s2.sku1.timeslot1.qty', 's2.sku1.timeslot1.vehicle',
's2.sku2.timeslot1' ,'s2.sku2.timeslot1.qty', 's2.sku2.timeslot1.vehicle',
's2.sku3.timeslot1' ,'s2.sku3.timeslot1.qty', 's2.sku3.timeslot1.vehicle'])
best_solution.T
---
s1.sku1.timeslot1 104.0
s1.sku1.timeslot1.qty 3.0
s1.sku1.timeslot1.vehicle 2.0
s1.sku1.timeslot2 136.0
s1.sku1.timeslot2.qty 8.0
s1.sku1.timeslot2.vehicle 2.0
s1.sku2.timeslot1 73.0
s1.sku2.timeslot1.qty 13.0
s1.sku2.timeslot1.vehicle 2.0
s1.sku2.timeslot2 125.0
s1.sku2.timeslot2.qty 3.0
s1.sku2.timeslot2.vehicle 2.0
s2.sku1.timeslot1 143.0
s2.sku1.timeslot1.qty 9.0
s2.sku1.timeslot1.vehicle 2.0
s2.sku2.timeslot1 136.0
s2.sku2.timeslot1.qty 5.0
s2.sku2.timeslot1.vehicle 2.0
s2.sku3.timeslot1 120.0
s2.sku3.timeslot1.qty 5.0
s2.sku3.timeslot1.vehicle 2.0
这篇关于遗传算法5 更复杂的配货应用的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
微服务架构中API版本控制的实践09-28
-
AI给的和自己写的Python代码，都无法改变输入框的内容，替换也不行09-28
-
Sentinel配置限流资料：新手入门教程09-27
-
Sentinel配置限流资料详解09-27
-
Sentinel限流资料：新手入门教程09-27
-
Sentinel限流资料入门详解09-26
-
Springboot框架资料：初学者入门教程09-26
-
Springboot框架资料详解：新手入门教程09-26
-
Springboot企业级开发资料：新手入门指南09-26
-
SpringBoot企业级开发资料新手指南09-26
-
Springboot微服务资料入门教程09-26
-
SpringBoot微服务资料入门指南09-26
-
Springboot项目开发资料：新手入门及初级实战教程09-26
-
Springboot项目开发资料：新手入门教程09-26
-
SpringCloud Alibaba资料入门详解09-26
栏目导航
