云栖TechDay第33期，阿里巴巴iDST Staff Engineer杨森带来题为“优化介绍及应用实践”的演讲。本文主要从用户需求开始谈起，对婚姻配对算法进行了介绍，重点谈及了分配问题、路径规划和组合优化等问题，最后总结了优化的重要性。
以上是精彩内容整理：
用户需求
说起阿里巴巴，第一个标签肯定是电商平台。电商平台的核心问题就是如何关联用户、商品和卖家，是否成功的关键就是如何去高效率的匹配。如何高效率的匹配用户和商品，这直接影射出两个非常直观的问题：
首先我们要知道用户想要什么，我们才能去高效的匹配用户和商品。在大数据、没有机器学习等技术没有广泛应用之前，最简单的方法做一个简单的统计，把一些非常受欢迎的商品列在页面的上面，而这个在商业分析中可以称之为一个描述性的分析，相当于去利用一个历史数据来分析历史上用户的喜好。 最近几年大数据机器学习广泛的运用，使得我们可以精确的预测用户的需求，可以做到“千人千面”。
这就是一个比较常用的流程，首先我们有一些行为数据，包括交易信息、行为数据，甚至还有一些位置的信息，然后我们通过这些信息，用机器学习的方法就可以把用户的画像构建出来。 然后我们再通过一些实时的数据，一些上下文信息，比如说一个用户前一个点击和下一个点击，这些上下文的信息再通过一些机器学习的技术，可以得到一个很好的预测。其实抽象起来无非就是一个输入，然后去学习一个决策的函数，产生一个输出。无论是Deep learning还是GBDT，都是可以抽象成这类的。 机器学习就是一个从数据中总结的重要的模式， 通过用户的一些特征或者行为的交易数据、历史数据，可以去预测用户在将来需要什么，而这个阶段在商业分析中称之为预测分析，就是如何通过历史数据试图去预测将来会发生什么，比方说预测用户的需求。
当我们知道了用户的需求之后，下一步问题就是如何去匹配用户的需求。我们知道用户想要哪些商品，问题的关键是如何把这堆商品很好的提供给用户，从而实现交易最大化。 其实有一个很简单的场景，假如供是远远大于需的，作为平台我们为了实现交易最大化，贪心算法其实可以达到最优。 因为用户过来的时候，我们可以把最好的、最希望买的东西展现给他，因为我们库存是没有限制的。 但很多现实的场景中，往往是供小于需的，就是说每个商店是有一些库存量的限制，这样就需要去决策，这个商品到底是给这个用户还是给另一个用户，从而达到一个全局上的最优，这就是一个优化的问题。 如何发现最优解，这个阶段其实在商业分析中可以认为是第三个阶段，规范式分析，或者称为指导式分析，本质上如何通过仿真或者一些数学建模，希望能进行合理的智能决策，从而知道将来为什么要发生、达到什么目的、通过什么形式达到这个目的，这是一个决策的过程。
优化算法：婚姻配对
说起优化算法， 婚姻配对是一个很好的例子。 其实准确来说，以上的图片并不能囊括所有的关系。 我们把男女关系进行简化，认为每个男的对每个女的都有一个排序，都有一个喜好程度，比方说，Bob最喜欢heiki大于geeta大于irina，女方也对男方有一个喜好排序。 如果我们要进行婚姻配对的时候，真实情况下我们不可能满足每个人的需求，比方说屌丝比较喜欢女神，但女神并不一定喜欢屌丝，所以说我们不可能让每个人都很happy。在这个例子中geeta是非常受欢迎的，男生Bob可能是比较受女生欢迎的，但这个配对只能One to one，这是一个非常经典的问题，稳定婚姻的一个stable marriage，这个问题其实应用了很多的场景，比方说在美国医科生如何配对医院是通过这个模型去解的，还有高中生怎么去选高中也是通过稳定婚姻模型去做的。我们得到一个稳定的婚姻配对，这样可以尽量减少出轨这种不安定性的因素，假设Carl遇到了irina，irina会觉得Carl其实比David要好，David会觉得heiki比irina要好，这是一个非常不稳定的婚姻配对，通过这个问题说明我们优化问题：
第一，我们想让多数人能happy，这其实就是一个优化目标；
第二，我们想让婚姻配对尽量稳定，这其实就有一个约束条件。 优化很大程度上是如何去做一个tradeoff，在这个有限的空间里面去尽量找到一个最优解，就是优化目标。
婚姻配对问题有个经典的算法叫DA算法。 它的流程是，如果男生还没有订婚的话，让男去向女求婚，第一次尝试肯定是最喜欢的那个女生。 在男生求完婚之后，每个女生都会接受被求婚（也有可能这个女的没有被求婚），女生会在自己的可选集中挑一个最好的，把其他拒绝掉。 如果男生被拒掉，那个男生可以下一轮继续求婚，选择下一个最喜欢的女生，候选人继续求，但假设这个女生碰到的男生是比之前更好，她会把之前那个人踹掉，然后把最好的这个留住，通过这种流程，得出结果就是stable marriage。 怎么说呢？这个算法如果是男的求婚，其实也被称为Man optimal olgorithm，就是男生最优算法，即如果男生去求婚，得到好处最多。 这也就是说，幸福其实应该主动争取的。 这个模型感觉很简单，因为它只需要一个排序，不需要一个量化的数字，但是假设我们知道Bob对每个人的喜欢程度或者幸福度可以量化，我们都可以知道一个数值的话，很明显这个算法得出的结果并不是一个最优的，因为如果可以量化，可以通过一些建模的方式去解，广告问题就是类似的，我们在在线展示广告展示里面，它的核心就是如何去用有限的资源，达到整体最大化效益，因为每个广告都有预算的。
每个用户对于广告都可以算出来一个喜好程度，或者称之为回报，比方说我们能算出点击的概率是多少。 CTR作为广告的根本，预测已经可以做的很准。 假设我们的目标是想优化最大的点击量，因为在有一些模式下， 广告主需要为点击付钱给平台。 如果整体的点击数最大，相当于平台收益最多。 但这个问题我们有一个投放量的约束，就是说其实每一个广告主的广告都有一个预算，每天每个广告主对广告的投放量其实都有限制。
图中为只有两个流量和两个广告的一个例子，比方说男生对两个广告的一个喜好程度CTR的预估，第一个广告是0.8，第二个广告是0.6；女生对两个广告喜好程度是0.7和0.2，如果没有一个预算的约束，我想最大化整体的点击数无非就是把这个最好的、最有可能被点击的广告分给两个用户，0.8和0.7，从而达到最优。 但是现实中我们是有一些约束的，假设约束是每个广告只能展现一次，这个广告虽然喜好是0.8，但为了最大化点击率依然不能分给他。
我们在线上的应用，其实就是供需关系的一个投放量，假设我们不考虑投放量约束的时候，比方说长棒是一个供，我的预算很多，广告主其实想推广我的产品，但产品有可能是一个新品，很多人不知道， CTR可能就很小。 我其实想推广，但是可能没有那么多人去点，如果用贪心算法，就会造成供需不匹配。 如果要考虑投放量的约束，进行优化算法的优化之后，可以看到供需还是比较匹配的，我们在线上使用最优化算法之后，我们的收入是有15%的提升，这其实就是把流量和广告进行一个调整。
分配问题：抽象
分配问题抽象也是比较经典的问题，给定一个二分图，二分图就是说一边是用户，一边是广告，可以称为左边有M个agents，右边有N个Tasks，每个agent-task pair都有一个reward，其实最优化的任务分配其实就是一个最大化的总奖励，但是它是有一些约束，这个task只能分配给有限一个agents，在这个广告例子上，就是说广告只能展现多少次，是有限制的，这个问题其实可以描述成一个整数规划的问题。
Pij就相当于是一个Reward，假设A用户和task配对，xij就是一个decision variable，一个决策的变量，它其实被限制为0和1. 如果是0就不展现，如果是1就应该展现，就是说不能超过预算， Customer来说明其实只能分配一个，这是一个静态的建模方式。如果问题比较小， 常用的solver也是可以直接求解。 但在如阿里巴巴这种大数据情况下，广告PV数其实是几十亿的，广告数也是几百万，这些常用的solver并不很好的求解这样大数据问题。 其实还有另外一个问题就是现实中很多应用是它不能事先获得所有的数据，因此这种静态的建模方式并不适用。 在我们很多实际的应用中，其实是动态的建模，比方说广告这种情况用户可能是随时出现的，那么，如何根据用户的一些分数做一个实时的决策，去分配广告呢？打车平台的用户和司机是同时出现的，那怎么去实时做一个分配匹对？
这是我们现实中的一些常用场景，是一个动态的在线分配问题，那这个模型T表示时间，表示按照每个时间点来进行的流量，这个问题的解可以有多种方式去解，比方说可以先积攒一部分数据，求解一个小的问题的对偶变量（或者称为控制变量），然后通过控制变量去进行决策，即求解xij。 例如一小时数据的控制变量再去影射回原来那个问题，来进行算Xij。 通过这样的情况，一旦得到控制变量之后，其实后面的23个小时的决策都可以通过控制变量去进行实时决策。 我们算法可以证明这种在线的优化方式，长期优化一定是最优的 ： 假设问题够大（预算够大）， 在线最优解和理想静态建模的最优解的误差可以够小。
其他应用
除了广告，这种分配算法还有很多的应用场景。 其实准确来说，就是如何在有限的资源进行合理的分配。 这些例子包括消息推送，因为每个用户每天push的个数是受限的，如何去最大化打开数？还有在线流量分配，购物券分发，购物券分发是有一些额度，我有一些cost，然后分给哪些人能给我们引流，给平台带来的GMV最多，还有问大家的消息分发，其实说的是一个有约束的优化问题，如何在有限的资源进行合理的分配资源，进而达到一个最优的收益，这是电商场景中比较常见的优化算法。
路径规划
另一种优化方法就是路径规划，路径规划其实是一个非常传统的图优化问题，比方说我们从GPS去做一个导航，就是一个最短路径的问题。 另外一个比较广泛应用的路径优化问题是车辆路径规划的问题， 就是我们有一个仓库，每个用户有很多的需求，尽量去用最少的车辆从仓库出发，用最少的行车距离来满足用户的快递需求。 车辆路径规划其实有很多应用场景，最直观的就是订单揽收，比方说上图红色点是一个深圳的订单分布，然后我们做了一个调度分单，不同颜色每个是Driver去负责不同颜色的订单揽收，然后进行路径规划之后，通过这种优化，整体的行车路径接近节省50%。 这个问题其实也可以包括两个部分，一是分配算法，一是最短路径算法。
一个经典的路径规划问题，其实不仅仅是一个比较直观的订单揽收可以抽象成路径规划问题，比方说这个问题是一个订单的波次，菜鸟每天在我们用户购买发生交易之后，这个订单会到仓库的管理系统，可以抽象成就有一个订单池子，订单池子如何去进行波次，生成一个拣选单，让它行走的距离最短。 如果路径不是很好优化的话，拣选的效率会受到影响，所以这其实也可以转化成路径规划的问题。 不过在整个链路中，其实这个问题可以模拟成三个问题：我们怎么去分配，把这个订单分配到每个拣选单里面，进而让每个拣选单路径最短。 这个问题也可以转化成一个VRP的车径路径规划问题的一种扩展，我们现在和菜鸟一起合作，开发了一个VRP Solver，可以支持多种VRP路径规划需求，包括经典的VRP，包括有时间窗口的VRP，有各种VIP的求解器，基准数据集评测优于开源Jsprit。
装箱算法
再说一个组合优化的例子，叫装箱算法，这也是一个非常经典的算法， 就是说我们怎么把商品用最少的箱子去装。 这在天猫超市有很大的应用场景，因为天猫超过一定限额是包邮的，为了超过限额，很多人都买很多东西，对于我们其实想用最少的箱子去邮寄，这样就可以节省成本。 其实装箱是物流成本非常核心的问题，而且Bin packing并不仅仅是物流上面的问题，可以扩展到计算资源调度。 装箱算法的目标是减少箱子个数、提高空间利用率和优化拣货路径，这些问题虽然看起来很基本，但这是非常难的问题，它解的好坏直接与商品个数和运行时间是成比例的，我们装箱算法可以达到每单节省2毛到3毛，可以降低到耗材的15%，如果要把这个算法用到去年整量的数据，可以节省几千万。
我们刚才讲三大类的优化问题：一种是分配问题，如何通过有限的资源合理分配，达到我们收益最大化，在阿里有很多的应用场景；另一种是像bin packing这种组合优化问题，除了装箱算法，还有一种类似于任务调度的组合优化问题；还有一种非常广泛应用的路径规划，比方说O2O的送货路径怎么规划，其实也可以推动路径规划算法进行优化。
优化引擎
我们针对三类问题开发出了一个优化引擎来支持这三大类的问题，我们这种优化引擎现在已经有一部分的应用部署到云端，如果有需求的可以进行试用。 我们在集团内部支持很多优化的需求，优化问题真的是无处不在的，阿里每天有很多应用程序需要运行，像机器学习或者各种model、各种query都要去运行，那如何把这些应用程序分配计算资源，尽量用最少的计算资源去满足计算需求，本质上就是最优化问题。
还有计算平台。比方说ODPS、Hadoop、Spark、flink其实都有一个资源调度的模块，如何合理去调度资源，进而把效率提升，如果在计算平台上面，还要用算法，基本可以认为机器学习和深度学习本身是有一个优化问题，优化就是机器学习的基础。
在业务层面也有很多的场景，像广告消息的push message，还有物流，就是比较传统的装箱算法，去调度甚至路径规划；阿里云的智慧城市，比方说交通如何调度，红绿灯如何调度等等，说明优化问题是无处不在的。
优化的重要性，第一是数据增值，我们可以充分的使用大数据来进行，比方说广告投放，其实就是机器学习+优化的一个完美结合，通过预测用户的一个点击精确预测用户的点击，然后再通过优化算法进行优化，可以让整体的平台收益达到最高。
另一个例子就是云平台的增值服务，比方说计算资源如何管理，这本身就是一个很好的优化问题，hadoop等都有一个标配的调度模块，我们可以针对业务场景做的更好，优化的另一个重要性是提升效率和降低成本，AWS从2014年开始每年都在降价，但是它的运营利润率每年在上涨，从12.5%提升到23.5%，其实内部进行了大量的优化工作，还有数据中心的PUE每年都在持续的下降，因为对这种云平台，成本的控制真正是一个核心的竞争力。
优化另一个重要作用是系统地平衡多目标间的tradeoff，比方说广告收益和用户体验，一味的去追求收益，可能会影响用户体验，还有物流效率和费用等。
杨森：阿里巴巴iDST Staff Engineer，美国亚利桑那州州立大学计算机博士学位，致力于优化和机器学习研究。2015年在加入阿里巴巴后，参与并负责多个推荐项目的核心算法开发。从2016年开始，致力于开发和应用前沿的优化技术去更有效的使用和分配公共和私有资源，并负责开发和沉淀优化引擎。