《7-4 基于循环神经网络架构的大规模供应链网络的仿真和优化.pdf》由会员分享,可在线阅读,更多相关《7-4 基于循环神经网络架构的大规模供应链网络的仿真和优化.pdf(23页珍藏版)》请在三个皮匠报告上搜索。
1、基于循环神经网络架构的大规模供应链网络的仿真和优化复旦大学管理学院&大数据学院洪 流 教授论文链接:https:/arxiv.org/abs/2201.05868|近十年来人工智能技术不断取得突破性进展推荐系统YouTube,Netflix,Amazon,字节跳动强化学习AlphaGo,自动驾驶、机器人图像识别图像识别,人脸识别,指纹识别,医学诊断自然语言处理Google Translate,舆情监测,自动问答算力提高是人工智能技术发展的原动力摩尔定律集成电路上可容纳的晶体管数目,约每隔两年便会增加一倍工业革命带来了机械力的提升(突破了人的体力限制)摩尔定律带来了计算力的提升(突破了人的脑力限
2、制)=,如果汽车按照这个速度发展,1970年的一万美元的甲壳虫汽车今天只需要1美分,而且时速可以达到5000公里/小时。供应链建模与优化传统的供应链建模和优化方法(例如线性规划、混合整数规划、离散事件仿真等)无法充分利用并行计算的大规模算力,例如最有名的优化问题求解器Gurobi和CPLEX只能支持最多32核。物流网络规划人员排班问题配送路径优化需求预测问题生产计划问题库存管理问题线性规划/混合整数规划模型基于人工智能方法的供应链建模与优化 目前已有一些将人工智能技术应用于供应链管理的尝试,例如利用机器学习模型进行需求预测等,主要是模型或算法的直接使用。我们团队致力于将人工智能技术的底层逻辑和
3、方法应用于供应链管理之中,解决当前供应链管理领域遇到问题和挑战。AI for Supply Chain案例:大规模库存优化 物 料 清 单(BOM,bill ofmaterials)用于描述生产最终产品所需的原材料、半成品的构成关系以及所需数量 我们的库存优化问题试图确定BOM网络中每个节点的安全 库 存 水 平(base-stocklevel)来最小化成本大规模库存优化国内某知名头部制造商BOM 节点超过50万个,链接超过400万条;活跃节点超过5万个,链接超过50万条;极为复杂的网络结构;库存价值约为¥200亿。库存策略优化问题:安全库存应该存放在那些节点上?安全库存量应该如何设定?这是一
4、个超大规模优化问题,主要的挑战来自于计算能力和计算速度现有方法和挑战随机服务模型(Stochastic service models,Clark&Scarf1960,Rosling 1989,Chen et al.2014)针对串行系统/装配系统,无法处理复杂BOM网络结构保证服务模型(Guaranteed service models,Simpson 1958,Graves&Willems 2000)主要针对生成树结构的网络 需要将随机问题转换为确定性问题仿真方法(Simulation approach,Glasserman&Tayur 1995)允许更一般的网络结构 运行时间通常很长问题定
5、义假设库存系统根据 base stock policy 运行,周期性(每天)检查需求和库存。仿真过程:计算inventory positions,产生orders;接收完成的orders,满足外部需求,更新on-hand inventories 和 backlogs 根据orders和可用的原材料决定生产情况 计算成本0,1,1,1,1,max 0,min 0,outoutt itit itit ioutoutoutt itit itit iIIPBDBIPBD=+=+(),outt it itiiiChpIB=+变量:库存位置、库存量优化目标:期望总成本最小、安全库存位置稀疏,1,1,1,1
6、,min 0,inoutt ititititioutint it it it iiIPIPODDOIPDDS=+=()1mintTStECS=基于仿真的优化方法仿真优化框架(Glasserman&Tayur 1995):建立仿真模型 梯度估计(IPA)随机梯度下降(SGD)传统库存仿真方法的复杂度:其中T为仿真的时段数,n为BOM网络节点个数传统库存仿真方法的耗时(单次采样):节点个数仿真模型梯度计算50001小时多个小时仿真模型梯度计算()2Tn()3Tn我们的目标是将运行时间降到可以接受的水平,从而至少可以实现50,000个节点的库存优化循环神经网络 循环神经网络是一类所有节点(循环单元)
7、按链式连接的神经网络 它在语音识别、语言建模、机器翻译等任务上表现出色 目前,循环神经网络模型的参数能达到千万量级 更新公式可表示为 训练中利用反向传播(BP)和SGD算法计算梯度()()1ttttthf WhUxbyg Vhc=+=+循环神经网络训练和库存优化的类比RNN训练库存优化结构更新公式目标函数优化变量神经网络权重base-stock levels优化算法随机梯度下降随机梯度下降()1ttthf WhUxb=+0,1,1,max 0,outoutt itit itit iIIPBD=+()(),1minTSttiiitoutt it iECSCIhBp=+()111min,NnTnT
8、nnnTtttLNLL yy=注意:库存优化只是用循环神经网络的计算架构,没有训练任何东西!循环神经网络训练和库存优化的类比关键问题:为什么RNN可以解决大规模问题?对解决大规模库存优化问题有什么启发?张量化:通过对仿真过程的矩阵化和张量化表示来实现并行计算;梯度计算:通过构建计算图和利用反向传播算法计算sample-path梯度;L1-正则化:通过L1-正则化结合随机梯度下降算法来实现优化结果的稀疏性。张量化:BOM的邻接矩阵 利用BOM网络的邻接矩阵,我们可以把整个仿真过程转化为矩阵/向量运算 利用TensorFlow等机器学习工具,矩阵运算可以轻松地并行化,甚至可以在GPU上运行 n个节
9、点的BOM网络邻接矩阵为n x n的方阵 对于大规模的网络,邻接矩阵的存储将会占用大量内存空间os.environCUDA_VISIBLE_DEVICES=1,0张量化:邻接矩阵的稀疏性 实际上BOM网络的邻接矩阵通常非常稀疏(例如,50万节点400万条边)可以利用稀疏矩阵技术减少内存消耗 一个有n个节点m条边的有向图的密度定义为:可以用平均出度来表示网络的稀疏度:()1mn n=()1mknnn=BOM网络的平均出度代表组成一个下游成品/半成品所需的上游部件的平均个数,通常来讲,它不会随着网络规模的增加而变大,即 基于BOM网络平均出度的性质以及稀疏矩阵技术的使用,仿真及梯度计算的复杂度能够
10、大大降低 constantn梯度计算:IPA和反向传播 IPA和BP产生相同的sample-path梯度 IPA采用正向计算模式 BP采用反向计算模式 如果利用TensorFlow等工具进行仿真代码编写,则可采用其内置的BP算法自动计算梯度计算图正向模式反向模式梯度计算:计算图和反向传播我们构建了库存仿真过程的计算图,并且基于计算图构建了针对我们问题的定制化反向传播算法L1-正则化:库存位置稀疏化 首先求解带L1-正则化项的优化问题来选择库存放置的位置:接着基于第一步的结果,固定S向量中特定的位置为0,求解新的优化问题,进一步优化库存值:()1*11argminTttSSECS=+()*101
11、min1TtStECSwhere SS=在第一步中,采用随机版的快速迭代阈值收缩算法(FISTA,fast iterative shrinkage-thresholding algorithm)进行求解 第二步采用随机梯度下降(SGD)算法进行求解受高维回归领域relaxed Lasso算法的启发,我们提出了一个两阶段的优化算法:数值实验结果:仿真节点个数传统方法我们算法-稠密我们算法-稀疏10002.21min0.28s0.19s500056.00min6.28s0.73s10000212.18min25.12s1.48s50000-632.21s6.92s100000-2535.56s13
12、.90s500000-/85.70s节点个数TensorFlow-CPU-denseTensorFlow-GPU-denseTensorFlow-CPU-sparseTensorFlow-GPU-sparse10001.66s4.60s1.69s2.98s500013.08s12.76s7.08s11.61s1000040.19s24.45s14.38s23.14s50000735.64s129.72s71.30s112.70s1000002912.50s/145.31s231.39s500000/775.07s1144.78s运行一次仿真所需时间:传统方法我们算法()2Tn()Tn时间复杂度
13、硬件条件:2 Intel Xeon Gold 6248R CPUs(每个24核),1 NVIDIA GeForce RTX 3090 GPU(10496核),256GB RAM8600倍数值实验结果:梯度计算节点个数TensorFlow-CPU-denseTensorFlow-GPU-denseTensorFlow-CPU-sparseTensorFlow-GPU-sparse10009.79s12.33s10.51s13.37s500059.94s54.59s48.06s55.02s10000152.76s108.37s100.99s110.11s500002453.98s/609.78s5
14、47.05s.54s/1874.00s/500000/20337.55s/计算一次梯度所需时间:(包括仿真运行时间)算法复杂度IPA-denseIPA-sparseBP-denseBP-sparse时间复杂度节点个数IPA-denseIPA-sparseBP-denseBP-sparse10000.55min0.34min1.00s0.81s500029.36min3.01min14.36s2.95s10000219.73min11.55min53.35s5.68s50000-654.67min1277.84s26.88s100000-/5152.54s54.97s500
15、000/305.64s()3Tn()2Tn()2Tn()Tn2300倍数值实验结果:库存优化节点数00000500000成本降幅3.38%2.07%3.32%2.17%节点数00000500000Stage125.14min92.40min198.10min19.36hrStage214.37min26.97min59.41min4.98hrTotal39.51min119.37min257.51min24.34hrStage1 优化效果Stage2 vs.Stage 1 优化效果运行时间平均成本库存位置 通过对库存优化问题和RNN类比,使得我们可以采用RNN的底层技术来解决大规模库存优化问题。提出的框架使得我们可以使用TensorFlow等高性能计算工具,从而降低了建模、优化和大规模并行化的障碍。在数值实验中,我们的方法在仿真与梯度计算的运行速度上较传统方法各自提升了数千倍,5万个节点的测试问题可以在2个小时内解决。该方法可以进一步拓展到其它大规模排队网络的建模和优化中(包括交通网络、服务网络等)。总 结非常感谢您的观看|