组合优化 (三) 算法简介
由于生产实践中面临的绝大多数具有实际意义的组合优化问题都已经在理论上被证明属于难以使用可接受的计算资源在可接受的时间内求解的 NP-Hard 问题, 其求解算法不像 P 问题一样存在标准答案.
此外, 在实际的工业应用中, 由于未来的不确定性以及评价指标常常无法完美量化等问题, 耗费大量计算资源和时间精确求出最优解几乎没有实际意义.
所以, 组合优化算法的设计往往是在优度与速度之间寻找平衡点.
由于生产实践中面临的绝大多数具有实际意义的组合优化问题都已经在理论上被证明属于难以使用可接受的计算资源在可接受的时间内求解的 NP-Hard 问题, 其求解算法不像 P 问题一样存在标准答案.
此外, 在实际的工业应用中, 由于未来的不确定性以及评价指标常常无法完美量化等问题, 耗费大量计算资源和时间精确求出最优解几乎没有实际意义.
所以, 组合优化算法的设计往往是在优度与速度之间寻找平衡点.
面对一个复杂的组合优化问题, 把它描述清楚本身就不是一个简单的问题.
常规开发往往允许模棱两可的描述, 需求修修补补虽然很烦, 但往往只是工作量的问题.
而算法研发由于其专用性, 细微的需求变化可能导致一个算法完全失效, 除非重新设计整个框架不然无法解决新的问题.
所以, 严谨的需求分析或问题描述对于算法研发格外重要.
对于一个组合优化问题, 我们一般使用数学规划的形式化语言对其进行无二义性的定义, 作为算法工程中的需求分析文档.
组合优化也叫离散优化, 是运筹优化的重要组成部分, 其中 “组合” 是排列组合的组合.
从字面上理解这个名词, 组合优化是要从呈组合数复杂度爆炸式增长的解空间中, 寻找最优的解向量, 即制定最优决策方案.
组合优化问题涉及了分配, 调度, 指挥, 路由等众多类型的问题.
作为人工智能的重要分支, 组合优化与时下大热的统计学习存在着千丝万缕的联系.
统计学习更侧重于预测和单步决策, 比如预测出了某件商品的销量, 就可以知道需要进多少货; 预测出了某个区域的人流量, 就可以知道需要分配多少保安巡逻; 检测出患者有某种疾病, 就可以知道要开什么药.
相比之下, 组合优化更注重涉及多方的, 全局的, 系统性的序列决策.
与此同时, 部分统计学习种的模型训练算法与求解组合优化问题的方法往往有异曲同工之妙, 因为离散优化与连续优化在思想上有很多相通之处.
以下观点仅针对博士招聘或者高级职位的招聘, 如果只是想招个码农一丝不苟地完成编码任务, 可以忽略此文…
最近参加某公司的博士特招, 收到了的一封邮件说让我做个编程测试.
与普通校招不同, 这封邮件并没有让我去 OJ 平台做题, 而是直接在邮件正文中给了 3 道题让我几天内做完并回复邮件.
这种新颖的形式让我眼前一亮, 虽然最后招聘人员的回复让我发现我想多了, 但是还是想分享一下自己的思考.
最近遇到了一个小问题, 大致是已知一块玻璃上有些瑕疵, 如何切割出一块给定大小的矩形区域, 让它的位置尽量靠近左下角, 但是不与任何瑕疵重合.
虽然原始问题要求的是不与任何瑕疵重合, 但是对于一个给定的格局, 比如已知一些瑕疵会同时被覆盖, 有些瑕疵显然是不需要考虑的, 我们称其为 “被支配” 的瑕疵.
所以其实我们只需要避开没有 “被支配” 的瑕疵, 如下图中红色的点, 而绿色的点显然是不需要考虑的.
最近做项目的过程中发现, 甲方使用的系统里据说调用了 Quintiq 的优化算法, 但是甲方表示这个算法求出来的结果完全不能用, 于是这个功能长期处于闲置状态.
突然想起之前听说中石油中石化都买了 Aspen 的系统, 但是成品油配送基本上也没用系统自带的算法, 还是在由调度员人工调度.
此外, 还听说上海交大的某教授二十年前刚从国外回来的时候, 去找东航说要帮他们做航线规划的算法, 结果东航说就那么点飞机, 人调度就够了, 不需要什么算法.
高中数学选修课学过区间消去法, 用于求解简单的单变量无约束的优化问题.
其中的典型有二分法和黄金分割法 (0.618法), 后来还知道黄金分割法其实是斐波那契法的简化.
而很多人似乎并不清楚这两种方法的区别和适用场景.
读研之后一直在做运筹学相关的问题, 遇到的优化问题都是上百万维的多约束多目标的组合优化问题.
偶然间遇到了一个简单的一维的情况, 突然来了一种莫名的自信觉得自己可以比当时的高中数学老师讲得更清楚…
科学是一种描述世界运转的方法, 不能解释任何现象的成因.
人类的科学是一套建立在少数 “显然成立” 的假设之上的知识体系, “力” 就是一种假设存在的相互作用关系.
给定一个初始状态, 科学也许可以预测状态的转移, 或者说现象.
可能其中会用到一些复杂的理论, 而这些复杂的理论可以用更简单的理论解释.
但是如果你要追根溯源, 找到现象的本质, 那么科学是做不到的.