资讯 业界
此为临时链接,仅用于文章预览,将在时失效

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

作者:王金许
2017/06/27 23:05

雷锋网按:日前,雷锋网报道了钛媒体和杉数科技主办的 2017 AI 大师论坛,其中,杉数科技首席科学顾问叶荫宇出席了活动并发表了学术演讲。作为在运筹学领域的顶尖学者,叶荫宇以《优化算法的思想及应用》为题,主要在运筹学应用的物流选址及路径优化、库存管理、投资组合优化三个方面详细阐述了他的看法。

从古至今,“优化”一直是生产生活中重要的部分。而运筹学作为优化算法的重要根基,在第二次世界大战期间首先在英美两国发展起来,学者把运筹学描述为就组织系统进行各种经营所作出决策的科学手段。二战结束后,人们将运筹学应用到了企业和政府之中,为经济发展加速,运筹学广泛的引用在生产、服务、金融行业之中。在大数据时代,运筹学进一步蓬勃发展,而如何将大数据转化为最优决策成为了运筹学重点课题。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

叶荫宇简介:叶荫宇是斯坦福大学李国鼎工程讲座教授(K. T. Li Chair Professor),也是优化领域基石算法之一——内点算法的奠基人之一。因贡献突出,他曾获得美国运筹与管理学会冯·诺依曼理论奖,也是迄今为止唯一获得此奖的华人学者。在业界,叶荫宇担任了优化软件公司 MOSEK 科技顾问委员会主席、杉数科技的首席科学顾问。

以下为叶荫宇演讲内容,雷锋网进行了不改变原意的编辑 :

1982 年刚到美国读书的时候 AI 非常热,但那时候年轻人不知道我差点就去搞 AI 了。那时候要搞所谓的专家系统 AI 空间,学的语言是学 Lisp,没有很多的数据,人家有些就总结不出来,AI 就慢慢的冷下去了。我比较喜欢数学,就从事了运筹学。

什么是运筹学?它是一种研究优化的学问,就是怎么能够在实际生活中,把事情做到极值,不仅仅是找一个可行的方案,而是一定要找到最优的方案。

Nothing at all takes place in the Universe in which some rule of maximum or minimum does not appear. 这是大数学家欧拉的话。这种理论也是基于自然形成,也是所谓的一个平衡,也是能量函数,到了极值。

说到运筹学,数学怎么能接地气,怎么落到实地,怎么真正对人们生活产生一些影响?数学家们就开始寻求这样的方案。在二次大战的时候,如何研究盟军配置,还包括一些博弈问题,以前看过一个电影叫《A Beautiful Mind》,研究这个东西研究到博弈空间。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

标志性的结果就是 1947 年 George Dantzig 提出线性优化,为优化中最经典的算法, 这就是里程碑的意义。之后到经济发展中,运筹学得到很快的发展,特别是计算机的高速发展。以前是结构问题,可能是要 1 小时,现在可能不到 1 秒就可以解出来,所以这个硬件的控制,也有算法的提高。

运筹学比 AI 要老,但是 AI 和机器学习又提供了一种机会,很多顶层的东西都是要靠优化,不管是学习还是刚才讲到的要用决策问题。

整个来说,所谓优化在满足我们时有很多要决策的,而且也都是需要比较量化的。满足一定的约束条件下,使某一个函数最大,这就是优化问题,怎么把一个问题变成这个东西,就需要建模。所以我们一般是从建模到求解,然后再到决策,然后我们就需要一套算法来求解。

在这个里面,把实际问题变成数学问题,再变成优化问题,然后来求解。什么叫大数据,有很多不同的这个解释,数据大到一定程度以后,就可以量化了。量化以后,我们可以用数学的方程、公式来描述它,然后来决策,变成一个量化的决策问题。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

1982 年我去美国中间经历了 AI,当时是最红,现在又红起来。但是有些点我觉得没变的,优化好像始终是不动点一样,不管是你在各行各业都需要它,因为在这点上也可以说起来像统计、数学还是一些机理。

这里面有很多算法的问题,学习有很多深度学习、MDP、机器学习等等。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

我个人怎么理解 AI?特别是大数据时代的商务决策,各自所采取的作用,我们要用到很多计算机、信息学,包括机器学习、数据搜集,然后我们要通过很多机器学习做一些规律性分析,然后建模做出决策。

从中医的角度来说,有点像拉脉一样,拉了脉以后老中医有一个决策,中医来说就是开处方药。而在这个过程中如何判断准确,开什么处方,有些东西要用三钱,有些东西要四钱,但是有些中医搞的不好就是比较模糊,“当归少许”这个就不清楚。

所以这里面是需要有一些量化、需求管理和规律性分析。我觉得机器学习确实做的好,但怎么决策里面都有一些很传统的优化模型和运筹学模型。

我给大家举几个简单的例子,为什么有些决策模型并不需要深刻的理解就可以得出来?

一、物流选址及路径优化

比如说这个选址问题,寻求一个区域内最优的仓库选择,成本最少。我要建一二三四五个库建在什么地方,那么这里面就要权衡很多,一次建设费多少,建设费之后我服务区域有多大,区域大了以后人家从很远的地方跑过来运输成本就高了,那么你可以写成一个像这样的数学规划方法。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

那么这样的问题怎么选才好,以前的算法,我就把它写成一个整数规划。现在不行,好像有些算法,像几个月都算不出解来。现在很多东西,要随时的,有些东西看成是网络,就要把这个点放在上面,进行随时的调配、重新选址。这个时候我的算法就非常快,然后就会有很多近似算法,这里面我们也做过一些工作,就是比较确定性的这个问题,这里面的算法,选址的问题。

那么有一个问题就稍微更复杂一点,不是选址,那么选一个仓库提供一个区域服务,但是这个是叫 HUB 的选址,有些不是从仓库发到某一个顾客上,某一个是要经过中转站,再到顾客。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

比如说航班的调运问题,那么这个中转站怎么选才好,有一部分有问题,这里面就会有一些选择。通常我们把选址的问题,叫作战略性的决策,一旦选了以后几年都不会变。决策又分为战略决策、战术决策、operation 决策,而这里面是 operation 决策。

我现在要送货,送到这么多的点上,如何都送出去然后回到出发的地点使整个距离最小,这是旅行商问题,这也是很经典、很确定性的。

在整个地方因为又叫车辆调度问题,当然实际问题比这更复杂,一辆车不能跑,可能几千上万辆车谁跑哪些地点、哪些区域、又怎么选址,这里面就非常非常复杂了,而且需要取货,同时送货,你取货的话必须要保证在某一个时间点上,或者时间窗口。这个就是运筹学比较擅长的问题,要非常实时的做这些问题。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

这是一个简单的解决方案,分而治之,我现在有 5 辆车要服务这个区域,首先就建立一个服务区的概念,怎么把这个大的区域分成 50 分,每一个区域选择一个分点,这个我们叫区域选择,非常的大。

选了以后,我知道我在分这个区域的时候,每个区域的这个工作量都是什么,尽量的均匀的,要不然我一个区域很大,跑两天跑不完,一个区域半天就跑完了。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

这应用在实际问题中。大家看到了没有,这里面有 50 辆车,现在这个图在做什么,找路径。这是一个实际问题,原来是一个大的地理数据图,那么这个问题是每一个街道都要跑的,我再划分这个区域的时候每个区域里街道的总长度是基本上相似的。但是哪怕街道一样,我要拿每一个颜色的这个就有这个扯进去跑,我在跑这个区域的时候,怎么跑到最大,把所有的街道都跑一趟,这个时候就有路径问题。

这个问题从优化、运筹学说是研究很老的问题。要把每个街道都走一道,然后这各区域就完成了,这个主要是为了地图公司。

美国有一个很有名的地图公司,后来诺基亚买了。我相信大家肯定用过 GPS,是两个核心技术,一个核心技术也就是卫星定位,经度纬度定位以后,所以的地理信息位置,都是搜集过来的,那么街道的地理数据,城市在不断的变,所以每次都要派一辆车或者用图像的信息把街道信息改变都要重新搜集进来,要派一辆车把每个街道跑一道。上面就一个摄像头,非常高效,然后全部搜起来,去做这个事情。

这个时候每一个城市都要把这个街道跑一道的话,不可能跑一辆车,可能是 50 辆车,我们怎么划分这个车辆的区域,以前是用邮政编码来分,由于城市的改变有些邮政编码,有的会大好几倍。这样分就不合理,我们要根据这个瞬时情况进行分析。如何判断有效,原来要用 75 辆车现在 60 辆就够了,原来用两天时间,现在一天半,我们确实讲,效率提高了25% 到 30%,这个技术诺基亚还在用,全世界 26 个国家在使用。

我不知道大家刚才看到我在排序的过程中,在这个路径过程当中大家也都没有遇到,我原来认为我排出来最后的总路程最短,后来给我们提一个要求这里面有多少是左转多少是右转,你能不能排路径的时候,尽量向右转。因为考虑的是要完成的时间,左转所要花的时间,要比向右转高 5 到 10 倍。因为有红绿灯,所以我们用运筹学的办法把这个解决掉。

再举一个路径优化的问题,大家都在搞所谓的无人仓。有一些小车搬运载有货物的托盘到空闲工作台,然后小车搬运到托盘从工作台回到仓库空储位,我们叫回库。然后小车搬运空托盘从工作台到托盘回收处,我们叫回收。这里面都是一些货柜,怎么拖起来怎么用,又要路径又要协调。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

我觉得在我们国内研究机器人,研究的比较多的是提高机器人自身的能力,我觉得做的非常好。个人能力都非常好,但是我们国家在很多问题上,缺少通盘调配和安排。机器人那么强,在一个团队工作的时候是不是就很强了,我们就比较缺乏统筹的软件决策系统。就像我们中国足球到个人,也许有些能力很强,但是在一起就不行。我们很注重个人能力的提高,人都不要输在起跑线上,但是我觉得我们国家,长期缺乏一种集体的、统筹的,这样决策的开发,或者能力的提高。每个机器人都在瞎跑的话肯定不行,包括无人车。

很多公司都在考虑无人车的技术多强,但是其实最主要的问题是什么,反而是无人车之间的协调、调配和统一指挥。

比如说这里面是工作台,某一个区域的货来了以后,我们来分担,然后这是一个动图,整个的这个货品的分担,这里面有很多问题。我们在研究过程中,比如说这里面的路径,怎么找路径,从设计上来说,你是设计成单行线还是双程线,这里面有学问的,如果设置单行线跑的距离要长,碰撞的可能性就少一些,这里面都可以通过优化来进行解决。

比如,我们跟合作的电商进行物流仓统筹调配,其中的算法也都是算出来的。这里面是三配,机器人怎么配到货柜,怎么收检这个站,这个方法目前是用机器人去托盘,拖这个货柜,把整个的货柜用到旁边的这个台上,然后又把这个拿下来,再把托盘送回去。

我们中国人就很喜欢把国外的东西搬过来,首先是机器人,把整个的货柜拖起来,可能那个货柜员就检一个东西下来。那么为什么说货柜不动,而且货源坐在机器人身上然后去检货呢,可能人需要多一点,但是货柜可以装的更高了,空间利用率更高了。

我觉得我们大家可以想到一些更好的,但是这套技术可以用,而且人坐在机器上,不仅前后移动还可以升降货柜,可以放更高,运行过程中形成三位的仓库而不是平面的仓库,这样我们就可以计算出来,包括货的这个密度,增加多少,仓库的利用率可以增加多少。那么对于像我们国家,人力相对比较便宜,房非常贵,是不是就更好一点,但整个也是靠产品运输来优化问题进行求解。

从优化的模型下,各种各样的这个决策,还有算法,我在国内跟工业界接触也有一段时间,工业界总是觉得我们需要深度学习,需要机器学习,需要把预测的精度再提高 1%,提高 1%。我觉得有时候忽略了一点,有个测不准的这个定理到一定时候不可能提高的,有一个不确定的这个规律存在。

股票市场存在一两百年,也没有人能 100% 预测股票市场,所以在测不准的情况下,在决策上是不是可以做点工作,在知道测不准,可能有不同的这个状况出现的情况下,我的决策是不是可以调整一下,从数据到决策我们是不是也可以做一些工作。比如说我可以保证我在期望值省时一些,但是我保证永远不会破产,防备那些恶性大事件发生,所以这些模型在 OR 应用到很多的。

比如说路径优化,搞了一个 PonyPlus,我给这个送货员把一个任务今天要派 10 个单,给到这个送货员,就搞一个辅助工具怎么去路径最好,排了一个,这里面都有这样一些工具。

二、库存管理

这里面最典型的是库存问题,就是典型的知道你测不准,我怎么能够把局测做到最好,把库存做到最好。以前早的时候还没有深度学习,比如你是小零售商,你进货进多少,进一个星期的货,但是不知道这个星期有多少,多的有多的损失,少的有少的损失。所以这个时候运筹学就有一套方法来处理这个问题。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

最近大家是否听说过美联航上面有一个人,因为机票卖多了,上了飞机被人拖下去,后来是赔了几个亿,为什么说这是典型问题,是不确定环境下的决策?

飞机上座位是固定的 300 个,你事先只卖 300 张票,不会卖多,来的人都可以登记,问题是总有 5% 到 10% 的人,因为各种各样的原因是不会来的。那么你卖 300 张票,5% 到 10% 是不会来,那么那部分就会损失,所以航空公司一般都会多卖一点。这个道理是一样的它也要权衡,它知道有些人不来,我怎么多卖几张,最好的是有些人不来,不来的人数正好是我多卖的人数。但是永远是测不准的,也就出现美联航的这个问题。

一般我们决策是什么,业内通过拍卖的形式,你愿意乘坐下一次航班,给你多少钱,美联航说到 600 块钱就不向上提,所以我们要找一个权衡,多卖几张最好。

这点我们做过很多实际案例特别是在我们国内比较大的电商里,帮他安排,通常周转率在 29 天的,那么现在降 16.5%,库存的金额大家也都知道零售商最怕的就是库存周转率太低,买了人家的东西自己又卖不出去,库存金额降 19.2%,现货率提升了,GMV 上升 1.9%,而周转天数下降到 16.5%。就是说我们主要是降低了这部分人力,在不损失这两个标准的情况下。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

还有一个办法根据某一个电商的特点,叫闪购,出一份货卖一个星期就不卖了,那么这个时候他们通常这个电商把那个星期的预测,需要备多少货就决定下来,我们采取两阶段的策略,首先我有一个总的估量,但是我发货的时候是发三天的货,通过第一天的销量我再决定追不追货,不知道大家听懂了没有,本来一周的需求量是 100,我实际送到前沿仓库送 60 件,头一天的这个销量是够,我是否需要把这 40 件补上去就看第一天的销量,第一天的销量对后续的这个预测度就更高。

王曦也是我们斯坦福的学生,现在是杉数的产品经理。设计了一个叫 Stockgo,根据我们跟电商还有其他接触的这个规律,我们觉得应该给每一个中小电商,至少提供一个可能的工具,观察库存的周转来确定,帮助他决策。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

这里面有很多的功能,比如说对目前库存状态的量化评估,对高精度的销量预测,高精度的补货策略,供应链管理的智能化转型,包括很多的机器学习工具还有深度学习工具,对你的库存状态进行评估,精确到每一个 SKU,还有补货策略,以及个性化的全云端解决方案,也可以直接把数据传送到杉数,然后帮你进行诊脉。

总的目的是,把这些 OR 的东西对经济起大作用,这是已经在跟很多 ERP 的公司发给他们使用,通常周转率会提高到 50%,资金及人力成本降低,电商自动化库存能力也都是在提高,这是一个小工具,到时候这些能够为广大的小电商服务。你也可以自己调整,但是至少给了你一个可能性。

三、投资组合优化

最后我就讲一讲最近还研究一些投资组合优化,也就是防范风险。

这里面很多情况有一个叫 Markowitz,叫现代投资前沿理论。Markowitz 也是在我们斯坦福工作过一段时间,把投资组合的问题写成一个二次规划,它的目标函数不是线性函数,是二次函数,所有的约束也都是线性。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

如何解这个问题解的最快,这个时候我们就有很多的问题,因为出现了二次函数呢,大家知道在统计中,二次的 X 的平方通常描述变化量,我们需要波动不太大,这就是简单的这个二次函数,实际上要解的也就是二次规划,常见的软件 Barra、Axioma、ITG、Mosek 等。

那么在交易过程当中,你的算法你的求解器比人家快一些,我个人认为高频交易的竞赛也就是算法速度的这个竞赛。我知道国内就用到过这样的模型,自己解需要解 10 秒钟的时间。从 10 秒到 0.04 秒,这里面有算法的模型。

FICO 也是二次规划的问题,很多大数据公司,越来越重视优化,我个人认为美国最早的大数据公司就是产生 FICO 的一家公司,国内是叫征信打分,就是最早的一个公司把个人所有的信息收集起来给这个人的信誉打分。我 1982 年去美国要租房子到银行开款,人家就必要 FICO,我说我是中国来的没有,到美国租房要担保首先就是看这个 FICO,打这个分。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

这个公司后来做的很好,大家都用他的 FICO,也就提供这个服务,包括在网上查一查这个征信也都要交钱,这是美国很早的大数据公司,收集很多公司对每个人也都有打分。就是我说的英国优化公司,就被这个 FICO 公司买下来,在大数据处理中需要优化,能力需要加强。

这里面刚才我提到,我个人呢,包括杉数里我们很多人也跟美国运通公司做了很多,它是一个纯信用卡公司,不是一个单元,实际上是一个担保公司。信用卡消费什么东西,你如果消费了什么东西,把前期的这个还上,你没什么,要还不上就加利息,我总跟人家讲运通公司是合法的高利贷公司,国内有些高利贷公司可能就是比较野蛮。但是他是比较合法的,利率确实比较高。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

那么它的资源是什么,它的核心技术是什么?就是防范风险,希望你消费但又希望你不要还钱而且希望你还钱不要还得太快,但是又不希望你永远不还。当时在运通公司我们工作的时候,有一个专门的团队就搞这个,是一个大数据公司,特别是个人的一些数据在那个时候没有英特网,有比信用卡交易纪录的更多数据,也都是这个数据来进行识别。具体项目我不清楚了。

有一个就是我们帮他搞了一个怎么追债,运通公司信用卡如果三个月连续不还钱,人家不还钱不能雇杀手卸个脖子什么的,所以必须要通过合理的方法博弈,心理学很复杂的过程。所以有一些和追债公司联合起来一起搞。

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

很多是基于算法的,国内公司搞的这个 AI 非常热,趋势跟随很紧,在有些问题上结合中国特色进行研究和开发。我个人在 AI 革命过程中,看到了中国体制的这个优点。

为什么呢?也就是说文化的优点,你过 AI 这个问题,说句实话,深度学习这一块还是有很多理论依据,深度学习本身目前这个阶段,理论还在发展,做事情这个过程有点像我们中医,有什么问题它很有效,但是真正说出一个道道来还说不出来,有的时候也不是 100% 的准确,但是准确起来非常好,一个癌症病人吃了几副药好了,怎么解释,解释不了,所以我觉得特别适合中国的这个文化,不问缘由只看效果,西方在这块反而比较保守的。

所以我就说中国相对来说数据还比较公开自由,壁垒意识没那么强,像美国大公司数据绝对不会给你的,所以我觉得为 AI 开辟了很多前途。

但是中国发展过程中忽略了算法的力量,他们通常是以问题为根本,找了一些参考资料在开源软件中找一个算法进行试一试,这是要花非常大的这个功夫,确实是要耐得住寂寞,但是要用人家的开源软件,不给的话永远会被牵着鼻子走。我知道其实他们很需要线性规划或者说其他的运营规划。但是你要买人家,出于安全考虑也不行。

比如说 CPLEX,Mosek,现在有些大学、包括财经大学、杉数科技,不光是做实际应用,也培养自己的算法开发,这样的话就比较有核心技术了,真正的成为技术公司而不是咨询公司。

所以大家投资要是很有钱的话,要耐得住寂寞,要有核心的技术等等这样的一些东西。

未来的话,我觉得真是 AI、深度学习和机器学习提供了很多的支撑,模型规模也飞速增长,因为需要超大规模的优化算法,以前我认为我就要搞出个万能的算法,解所有的线性规划都要解得快,但是我后来反观看AI是非常定制的,我可以对某一类方法用的好就用那个方法,不是追求某一个统一的算法,或者类别法。反而是比较定制化的,用中国话来讲比较实用主义一些。

不一定追求理论上的完美,有一个统一的算法,所以这点上,我觉得反过来,AI 对我们的这个东西有很大的促进,什么问题需要什么样的算法,本身需要学习的过程。

还有一个问题,我们以前比较重视凸规划,大量的问题是凸规划。现在需要考虑如何集群化、软硬件结合,如何利用 GPU 实现并行运算,包括应用在智慧供应链、智能金融、健康管理等领域,我对我们国家的挂号系统,有很多的问题能不能采取更好的方法,这样的话对大家都有好处,这个东西,我们在 OR 叫排序。

总的来说我是搞运筹,因为也是搞优化的,1982 年到现在也大半辈子看到学术研究的起伏变化,我原来比较重视理论,很多问题都是写文章,证明一些东西,也小有成就,但是人到年纪大的时候维护自己工作利益所在。我觉得最大的利益还是对一般人生活产生一些影响,因为谁也不知道很多理论证明的结果有什么东西。

我仔细想,那些用 PonyPlus 的人,你证明不证明,我可能还是用这个方法。这就是到一定年龄的时候,就追求鼓励这些年轻人,不光是有一定的学术造诣,把自己的学术成果转化成技术,对人的基本生活产生影响,这才是 OR 的本质,OR 是一个接地气的科学,是一个落地的科学,怎么落地不能云里雾里说吓死人,经过我们的试验,还有杉数这些年轻人都是从斯坦福回来的学生,像运筹学,深度学习、机器学习确实对电商这些也都产生了一些影响。

所以我就希望大家多支持我们,使得中国的企业,从一个比较粗狂的形式进一步拓展为依赖于大数据、国际技术来进行决策的环境里面。

长按图片保存图片,分享给好友或朋友圈

运筹学教授叶荫宇:作为 AI 基石,优化算法如何在实际中应用?

扫码查看文章

正在生成分享图...

取消
相关文章