求解|破51项纪录的背后：华为云擎天架构调度求解引擎解读( 二 ) 引擎|华为|约束|背后|纪录|架构

在计算复杂性和最优化领域，有个“没有免费的午餐（NFL，No Free Lunch）”理论，即对于优化问题，在有限的搜索空间中，当且仅当我们指定了具体的问题的时候，我们才能说一个优化方法要优于另一种优化方法。或者说，理论上，并不存在一个在所有问题上都能获得最优结果的算法。
常用求解NP难约束优化问题的方法，大致可分为精确算法和启发式算法。
精确算法，如Branch-and-cut, Branch-and-bound 等，可以在理论上保证算法朝最优解收敛，但是通常适用于问题规模较小的情况。对于云上这么大规模（上亿决策变量）与复杂约束的问题，求解时长与资源消耗都是计算机无法接受的，因此并不适合在云场景下使用。
启发式算法，又可以分为简单启发式和元启发式。二者最大的区别就是，简单启发式算法更多的是问题相关的，而元启发式算法更多的是“问题无关”的。或者说，简单启发式算法对于A问题有效，但是对于B问题可能完全无法使用。但是，元启发式是相对“通用”的搜索框架，几乎可应用到所有的优化问题上面。
这么听起来，元启发式算法是不是违反了NFL理论，在使用一个算法解决所有问题？
并不是。元启发式算法内部一般包含两种关键机制，就是搜索集中性（ intensification）的机制和搜索的疏散性（diversification）的机制。前者负责搜索当前解的周围区域，而后者负责逃出局部优陷阱去更有“前途”的搜索区域。而一个完善的搜索策略就是要做二者的折中或者平衡，这里并没有一个“完美策略”可以使得该策略在所有优化问题上的性能都最好，所以也恰恰是符合NFL理论的。
在决定采用什么求解算法之前，我们再来看看云上面临的最优化问题的两个特点：
云上面临的是不止一个而是一系列的优化问题，问题之间可能具有一定的相似性和关联性。比如在线资源调度、资源容量管理、资源碎片整理等，都以云资源为核心且具有相似的模型和约束。
云上的绝大多数优化问题并不要求必须得全局最优解，而是要求在限定的时间内，给出尽可能高质量的解。
结合NFL理论、元启发式算法的特点以及云上优化问题的特点，我们采用基于元启发式的求解框架就顺理成章了。元启发式算法可以在限定时间内求解问题的“足够好的解”，同时，使用元启发式的问题无关性来适应多种多样的优化的问题。另外，又由于云上系列问题的相似性和关联性，针对某个问题的优化策略很可能也会在其他相近或者关联问题上生效，多个问题又往往可以联合优化。
当然并不是我们只要使用了元启发式框架整个引擎和算法就万事大吉了，求解框架只是第一步。复杂问题的建模、求解的算法集、策略集、参数调教都是我们的重点工作。尤其建模更是重中之重，它关系到问题的复杂度以及解是不是可以被应用到实际的生产环境当中去。我们还尝试引入多种元启发式算法框架，引入和设计多种集中性和疏散性策略包括文献中最好的方法以及团队创新的方法，并尝试创新的组合以及参数优化，包括引导式局部搜索、种群管理甚至是基于机器学习的手段，来丰富我们的策略，使得求解引擎能够对云上一系列的问题生效。比如，新的引导式局部搜索和种群管理策略就是我们刷新本次PDPTW记录的两项关键技术。此外，我们采用了并行化、参数自适应等多种技术来进一步改善我们求解引擎的性能表现和适应能力。
至此，我们取得了一些优秀成果，包括此前获得GECCO2020 OCP&USCP;竞赛冠军，以及此次刷新51项PDPTW问题榜单。更为重要的是，面向云场景的约束规划问题优化求解引擎作为华为云擎天架构的一部分，为华为云的资源规划、资源经营保障、资源弹性能力等方面提供了强大的优化算法支持，最终客户也会从弹性能力保障、服务质量等方面获益。在探索云上最优化问题的道路上，我们并非闭门造车，华为云联合ICPC组委会将在12月12日-12月20日在线举办ICPC 2020 NERC华为挑战赛，以云上调度挑战问题为题，邀请全球算法精英一同探索云上最优解之道。
目前基于华为云擎天架构加持的竞享实例正在热销中，针对任务型、可容错的算力密集型场景，提供超高性价比算力，在保证使用时长的情况下还可节省85%的使用成本。同时，华为云“双12会员节”，还有更多高性能、高性价实例正在热促，全场低至1.5折！更有企业客户专享权益、新购满额送P40 Pro活动，多款产品优惠，助你上云一步到位！阅读原文，了解详情。
(阅读原文跳转连接：https://activity.huaweicloud.com/1212_promotion/index.html?utm_source=InfoQ&utm;_medium=banner&utm;_campaign=&utm;_content=&utm;_term=&utm;_adplace=AdPlace036568)