什么是优化技术?给算法小白同学的快速讲解和上手文

简介: 经常被尊贵的客户问,什么是优化技术,能干啥?小白一文快速入门,并掌握业界前沿的高效上手方案!

背景


作为阿里达摩院MindOpt的产品经理,经常被尊贵的客户问,什么是优化求解器,能干啥?


一般我都秀下面类似的图。这张图改版了很多次,目标都是给各位老板讲解:

优化求解器是一款底层数学软件,求解优化问题,可以用在各行各业。

用了优化求解技术,能得到 “最大化收益、最小化成本” 的方案,“满足规则的可行方案”。

image.png


老板们听了很开心,觉得是个好技术。


然后,他们会让下面的技术同学研究下。

然后,技术同学过来看文档了,很痛苦:很多个案例、很多个文档链接,几百个API或属性概念,还甚至有“建模语言”需要学!


因此, 本文我用一个曾经小白学习的视角,来讲解什么是优化问题,以及要如何用这个优化技术。


1. 术语定义

优化问题:在给定约束条件下,找到一个目标函数的最优解(最大值或最小值)。

优化求解器:求解这个优化问题的软件。


看了这个定义,是不是有种 “不明觉厉、但听君一席话如听一席话” 的感觉,还是没有get到这个东西是什么,能做什么用。

别着急,接下来快速get。


2. 快速get理解优化是什么


作为初学者,如果对优化技术陌生,可以把 “求解优化问题” 理解为 “解一个不等式方程组”,“解方程的”。


优化问题就是这个要计算的方程组。接下来我们引入一些数学公式,让大家更直观理解。

放心,都是初高中数学水平的数学公式。

引用说明:下面的公式均来自 MindOpt新发布的基于大模型的“AI工程师”MindOpt Copilot 生成的内容截图,或者案例广场公开内容截图。大家也可以进去聊天生成自己需要的示例公式和代码。


2.1. 方程:一个鸡兔同笼问题

问题:

有一笼兔子和鸡,兔子和鸡各有一个头,兔子有4只脚,鸡有两只脚。笼子上有 35 个头,下有94 个脚。请问兔子和鸡的数目各是多少?


对应的数学公式如下红框所示 (MindOpt Copilot生成)

image.png

可以看到数学公式中,有两个 “等号 = ” 描写的约束关系的方程组。

这个时候算出来的结果是:

- 兔子的数量x=12

- 鸡的数量y=23


这是个方程组,是的,优化求解器也可以算方程组。


2.1.  不等式方程组+目标函数:鸡兔同笼问题的优化问题

一个优化问题,与上面大家熟知的方程对比, 会增加:不等式关系,然后增加了一个目标。


比如上面的例子更改下问题:

有一笼兔子和鸡,兔子和鸡各有一个头,兔子有4只脚,鸡有两只脚。笼子上有头至少有30个,下面脚至多80个。要想兔子最多,请问最多有多少个兔子?


这个时候,公式如下图 (MindOpt Copilot生成),变化主要是

  1. 对应的数学公式的约束就是个不等式的关系:最多,最少。subject to 就是约束的意思,有时会写成 st.
  2. 增加了目标,想要兔子最多。对应 maximize x,也就是优化的目标函数 f = x,优化方向是最大化。

image.png

这个时候,在求解这个方程组时:

  • 如果只考虑不等式的约束,解可能就是个域(有多种解、多个可行域)。比如 x=1,y=29;  x=3,y=29; x=3, y= 30……等等
  • 增加了要将x最大化这个目标,就相当于在这个域里面找最大值。这个时候可以利用优化求解器进行计算,得出最优目标时候的变量取值,如下:

- 兔子的数量 x=10,  

- 鸡的数量y=20.


需要注意的是:在有些情况下,最优目标时的变量取值也有可能是个域(多解)的情况。


这里,是不是有高中学线性规划的感觉了?比如下面的高一的数学题,是不是很熟悉?

image.png

这些就是优化问题。

它们采用的是最基础的线性规划的建模方法。

接下来,我们从应用领域和问题维度的角度,来拓展下优化问题的思路。


3. 拓展思路

3.1 拓展应用场景

在各类业务场景中,都有可使用“优化问题”的方法来描述业务遇到的问题。

比如餐饮饭店、资产投资、生产制造、物流货运、零售、广告、文旅售票、人力资源、电力能源、航空航天、农业种植、医疗保健、游戏竞技策略等,或者家长们常遇到的数学应用题。


下面我们举2个例子:

例1. 电商互联网常见的广告资源的安排:

电商平台要为一家新兴手游公司进行广告推广,平台有两种广告类型可供选择:类型A、类型B、类型C。广告类型A的转化率为5%,每投放一次费用为10元;广告类型B的转化率为8%,每投放一次费用为15元; 广告类型B的转化率为7.7%,每投放一次费用为12元。手游公司需要至少获得1000次投放,并且总费用不能超过20000元。每种类型广告都希望至少投放5次。平台希望最大化累计转化数,要如何规划广告投放?



得到如下的优化问题数学公式 (MindOpt Copilot生成)

image.png

最后用优化求解器算得的解是:

广告类型A投放次数=5

广告类型B投放次数=6 广告类型C投放次数=1655
- 目标函数值 = 128.165
为了最大化累计转化数,电商平台应该投放5次类型A的广告(每次转化率为5%,每次费用为10元),6次类型B的广告(每次转化率为8%,每次费用为15元),以及1655次类型C的广告(每次转化率为7.7%,每次费用为12元)。此时,累计转化数最大,为128.165次。


例2.  企业人力资源的员工福利安排:

假设一家公司想要给每位员工至少提供以下三种福利中的一种:健身房、健康保险和午餐补贴。给每个员工提供使用健身房需支付50元,健康保险需支付20元,午餐补贴需支付15元。公司有100名员工,每天福利投入的成本上限是4000。公司希望最小化支出,同时尽可能多地为员工提供福利,每种福利至少有30份。该如何规划福利?


得到如下的优化问题数学公式 (MindOpt Copilot生成)

image.png

此种问题有多目标,最小化成本,最大化福利数。上述的公式把这个问题简单化,变成一个单目标问题,约束增加福利数大于人数100。最后调用求解器得到:

提供健身房福利的员工人数=30

提供健康保险福利的员工人数=30

提供午餐补贴福利的员工人数=40

- 目标函数值 = 2700

为了最小化福利支出,同时尽可能多地为员工提供福利,公司应该为30位员工提供健身房福利(每人每天成本50元),为30位员工提供健康保险福利(每人每天成本20元),并为40位员工提供午餐补贴福利(每人每天成本15元)。这样,每天的福利支出最低,为2700元。



3.2 拓展问题维度和类型


上面的问题都只有几个变量(未知数),还比较简单,如果有很多的变量呢,方程将很长,一般是用矩阵的方式来表达。数据可能是用表格来表示的,比如 MindOpt Copilot 也支持的csv表格输入。


问题比如:

image.png


也有用 大sigma 来表达求和 ∑ 的,比如下面几个金融投资里面应用的优化问题:

image.png


这里看到公式,是不是有些头大了?

别担心,我们做实际问题的时候就容易理解清楚了。

当前,仅需要了解以下几个数学概念:

  • 线性、非线性:优化问题里面常说的“线性”就是一次关系,y =3x就是一次的,线性关系。y = 4 *x*x 就是二次的,属于非线性关系。当前大部分优化问题是着重处理线性关系和二次关系,再高次就不好解了。
  • 连续变量、整数变量:变量x的取值类型。如果有的变量只能是整数,不能是小数,或者说是“离散的”。与之相对的是“连续的”。离散的问题优化起来会方法不一样,会变困难,因此经常有问题需要松弛下,使得变为连续的。
  • 问题 “凸” 和 “非凸”。凸优化是个研究生课程,比较难。普通人需要掌握凸问题更好求解,非凸不好求解。因此列数学公式描述业务问题时,尽量避免非凸的情况。比如尽量是线性的关系。多次的关系很容易出现非凸的情况。


3.3 更丰富的优化问题类型列表


更进一步的,优化问题的数学模型根据不同的业务有很复杂的模型。


基本就是要掌握好:可以控制的变量、业务约束、优化目标的情况。


不同的数学模型适合不同的场景,在优化问题计算的时候,也会有不同的复杂度。


常见的优化问题类型会以下的词汇来描述:

image.png | image.png


看到这么多名词,也不需要焦虑,他们都有对应的命名规则,方便与其他算法同学沟通用的。

如果沟通不明白,可以贴一个数学公式出来也很方便。数学公式手写也是可以的!


命名规则比如:

  • 线性规划,英文是Linear Programming,简称LP,对应的数说目标函数是线性关系。
  • 如果加上变量有些是整数(integer),则组合成MILP(Mixed Integer Programming),混合整数的线性规划问题。
  • 如果目标里面有二次项,则称为二次规划 QP(Quadratic Programming)。
  • 如果约束里面有二次项,则称为二次约束规划 QC (Quadratic Constraint),组合还有QCQP
  • 再进一步的根据目标约束的类型,还可以进一步分类描述不同类型的问题,很多种
  • 再进一步,根据问题的优化计算方式,还可以取名字,比如零阶优化、黑盒优化、梯度下降、无梯度优化


类目很多,可遇到了后再查询标准术语,用于跨人沟通。


4. 优化问题的应用

优化问题在管理运筹、工业工程、经济学、物流、能源、金融等许多领域都有。优化技术属于底层的数学技术,应用面很广。在航空、航天、国防等也有应用。


对应求解优化问题的优化求解器,可以广泛应用于电力系统调度、生产计划、物流路径规划、投资组合优化等多个领域。

使用优化求解器可以帮助用户更方便、更快速地找到问题的最优解。


推荐可以去阿里达摩院求解器的案例广场 https://opt.aliyun.com/platform/case)看看,了解应用场景,和对应的简单的数学模型、源代码。比如:



5. 优化问题的求解计算

5.1 计算方法

优化问题的求解方法有:单纯形法、内点法、分枝定界法、梯度下降法、遗传算法等。在大学的运筹学课程里,一般会教求解线性规划(LP)需要的单纯形法,和求解带整数的线性规划(MILP)的分支定界法。


但是,在实际业务里,不太需要关心求解的方法,大都是借助工具来完成计算。

更多的需求是:需要了解不同算法计算的复杂度,是否能快速求解,如果不能,如何变更优化问题数学模型,使得能快速求解。


建议:求解方法这个知识点,仅作科普了解,更多地去准确描述好自己的优化问题是什么类型的问题,然后熟悉求解优化问题的工具,了解工具是否适合计算自己的优化问题。比如现在我们并不需要关心计算机是通过什么原理算出来了3+5=8,更多地去了解如何使用它。但是如果您刚好是这类计算工具的开发者,就需要查询相关的资料来学习。


在选择或者研究求解器时,一般会评估如下特性:

- 是否能求解

- 求解速度

- 稳定性

- 大规模问题求解能力和计算资源占用

- 接口易用性


开源的求解器和商用的求解器的差异主要是:求解速度、可求解问题的类型。速度差异可能有几百倍。

对于响应速度要求高的场景,通常就是能用和不能用的区别,导致很多场景没有上优化技术。


在很多限时要求高的场景,比如互联网、机器人的行业,建议直接用商用求解器(有的厂商提供免费版,比如阿里的MindOpt),直接体验高速版本验证方案效果。毕竟研发方案期间最耗时的是业务的数学建模,不要因为用错计算工具浪费太多时间浪费方案。就相当于,开发一个方案的一开始,先上一个高性能的电脑试试可行性,后面确认可行后,再研究怎么换芯片降成本。


小编这里推荐去MindOpt的平台去看商用的和开源的求解器软件,从这个案例 https://opt.aliyun.com/example/vqaeimyI3iEj ,复制项目进去尝试。全程浏览器里面操作,不需要操心软件安装和License。


5.2 有哪些软件可选?

当然是选阿里的 MindOpt 啦!毕竟是我亲娃!

或者用MindOpt APL建模语言,能一行指令切换求解器,方便对比测试。


依然给大家列一下更丰富的信息,供调研可用求解器。

国际上

国际上的优化软件起步很早,可以追溯到上世纪80年代。特别是商用的软件,积累了很多客户的经验,软件更稳定;且很少有研发的方案泄露出来,技术保密的很好,性能领先。


国际上的优化求解器:(仅列出常见的、且有软件获取地址的)


国产的:MindOpt,阿里的求解器

从15年后,国内多个团队开始逐步开始研发求解器模块。并且在19年20年,有商业公司的加入,研发的软件更稳定。


国内的优化求解器:(仅列出有软件可供下载使用的公司)

  • MindOpt:中国/阿里达摩院。
  • 小编备注:推荐指数 ❤️❤️❤️❤️❤️。
  • 当前支持:
  • 新手推荐用MindOpt线上的平台,不需要安装直接先学会使用,Notebook中直接码代码,上手学习更快捷。还有自研的代数建模语言、以及AI技术结合开发、大模型技术结合自动建模和码代码的方案,更贴合现代的AI+运筹结合的技术趋势。


  • COPT:中国/杉数。网址:https://www.shanshu.ai/copt 。根据页面指引填写信息申请安装包和License。国内研发的早的公司,求解效果不错。
  • 小编备注:不推荐。毕竟和我不亲哈哈哈哈
  • 因为这个功能和阿里的求解器MindOpt差异不大,目前主要优势是数学规划的求解能力全一些。可以提需求给MindOpt研发团队做针对性调优。
  • 而且用MindOpt APL建模语言编程,也是可以轻松一行代码就换调用COPT的!


来秀一下MindOpt 实际的应用的评测,给广大用MindOpt求解器的友友们增加点信心:

电力能源领域,这个问题规模非常大,海外求解器已经搞不定的行业。

MindOpt通过项目合作定制调优,整体最优。友商结果并没有我们优秀。

image.png

数据说明:有9/10的数据都是MindOpt第一,超过商用求解器,远超越开源的求解器。


而且MindOpt主打就是一个听劝,非常珍惜用户的反馈,并且尽快实现:

image.png


5.3 其他求解方法

除了上面讲的通用的优化求解软件外,还有很多特定行业的启发式的求解方法,可以更快获得对应解。

多数需要启发式求解的场景,是通用求解器无法快速求解的领域。比如带整数的优化问题。


启发式(Heuristic)算法的主要思想是模拟人类或者自然界的智慧和经验来寻找最优解或局部最优解。

常见的启发式方法有:遗传算法、粒子群算法、鱼群、蚁群算法等。在计算复杂的富含整数变量的优化问题里,如组合优化、路径规划、生产调度、排队论等场景验证有很好的结果。


使用启发式算法的时候,需要根据实际问题来选择,要关注参数和随机性带来的影响。


MindOpt Tuner调参器可以用于系统调参,通过根据输入到评价输出的探索,一步步迭代出更优的参数组合。可以联系MindOpt团队试用调参器的高阶用法。



6. 优化技术使用难点、推荐上手方案


求解环节,是目前有通用求解软件去进行可复制产品化的。

但是在用优化技术的应用里,有比较长的时间是在做其他的工作,如梳理问题、搜集数据、数学建模、调试。


每个地方都会形成耗时难点、专家经验。运筹优化工程师的从业者一般都是研究生。在和客户聊需求的时候,需要能引导出可实现的方向,去理清楚需求。非常的耗时和繁琐。且还会有的时候到最后发现不需要优化技术,直接规则硬计算(这个过程可以理解为是数学公式的一种变化)。


这也是用优化技术的付费用户,大部分是能源、航空、国防、餐饮巨头这些有钱大客户的原因。

有用,但普通企业用不起。


MindOpt 团队在逐步把这个成本打下来!


在初期,如果不清楚怎么用,可以去试一下 MindOpt新发布的基于大模型的“AI工程师”MindOpt Copilot ,MindOpt 团队在大语言模型LLM基础上进行了SFT训练,使得大模型具备了数学建模的能力,并且转换成了可运行的代码(得益于去年自研了MindOpt APL),业界创新、首个发布公开使用!正确率也是目前所知的业界第一!

这款聊天机器人在“优化”这个细分小领域,水平差不多达到高中生到大学生的样子。我们可以把前面的简单的模板工作,交给机器人来做,然后快速生成个项目,非常简单就上手开始开发了!

image.png

image.png


推荐的使用技巧:

image.png

比如下面视频的操作方式,快速启动一个优化项目研发,捋清楚数学建模和初步的方案尝试:

等有了数学建模的感觉、以及搜集好了数据后,我们可以再根据需求,看是要周期性调度软件上线、还是一次性使用的需求,制定对应的编代码的方案。


方案征集

当然,在优化领域,还有很多问题类型和求解器内核在研发。


我们也欢迎有对应 技术、并且想对客提供服务的企业、实验室或团队,与我们合作,一起服务给到用户。

当前方案征集中:

  • 定价问题 (建模,在线/离线计算求解)
  • 排班问题(问题、建模、求解)



联系MindOpt

钉钉号:damodi(达摩院决策智能实验室)

目录
相关文章
|
8天前
|
存储 算法 数据处理
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
|
6天前
|
机器学习/深度学习 算法 数据安全/隐私保护
基于生物地理算法的MLP多层感知机优化matlab仿真
本程序基于生物地理算法(BBO)优化MLP多层感知机,通过MATLAB2022A实现随机数据点的趋势预测,并输出优化收敛曲线。BBO模拟物种在地理空间上的迁移、竞争与适应过程,以优化MLP的权重和偏置参数,提升预测性能。完整程序无水印,适用于机器学习和数据预测任务。
|
7天前
|
算法 数据安全/隐私保护
基于二次规划优化的OFDM系统PAPR抑制算法的matlab仿真
本程序基于二次规划优化的OFDM系统PAPR抑制算法,旨在降低OFDM信号的高峰均功率比(PAPR),以减少射频放大器的非线性失真并提高电源效率。通过MATLAB2022A仿真验证,核心算法通过对原始OFDM信号进行预编码,最小化最大瞬时功率,同时约束信号重构误差,确保数据完整性。完整程序运行后无水印,展示优化后的PAPR性能提升效果。
|
10天前
|
机器学习/深度学习 数据采集 算法
基于PSO粒子群优化的CNN-LSTM-SAM网络时间序列回归预测算法matlab仿真
本项目展示了基于PSO优化的CNN-LSTM-SAM网络时间序列预测算法。使用Matlab2022a开发,完整代码含中文注释及操作视频。算法结合卷积层提取局部特征、LSTM处理长期依赖、自注意力机制捕捉全局特征,通过粒子群优化提升预测精度。适用于金融市场、气象预报等领域,提供高效准确的预测结果。
|
1天前
|
JavaScript 前端开发 算法
JavaScript 中通过Array.sort() 实现多字段排序、排序稳定性、随机排序洗牌算法、优化排序性能,JS中排序算法的使用详解(附实际应用代码)
Array.sort() 是一个功能强大的方法,通过自定义的比较函数,可以处理各种复杂的排序逻辑。无论是简单的数字排序,还是多字段、嵌套对象、分组排序等高级应用,Array.sort() 都能胜任。同时,通过性能优化技巧(如映射排序)和结合其他数组方法(如 reduce),Array.sort() 可以用来实现高效的数据处理逻辑。 只有锻炼思维才能可持续地解决问题,只有思维才是真正值得学习和分享的核心要素。如果这篇博客能给您带来一点帮助,麻烦您点个赞支持一下,还可以收藏起来以备不时之需,有疑问和错误欢迎在评论区指出~
|
3天前
|
机器学习/深度学习 资源调度 算法
基于入侵野草算法的KNN分类优化matlab仿真
本程序基于入侵野草算法(IWO)优化KNN分类器,通过模拟自然界中野草的扩散与竞争过程,寻找最优特征组合和超参数。核心步骤包括初始化、繁殖、变异和选择,以提升KNN分类效果。程序在MATLAB2022A上运行,展示了优化后的分类性能。该方法适用于高维数据和复杂分类任务,显著提高了分类准确性。
|
12天前
|
缓存 监控 算法
基于 C# 网络套接字算法的局域网实时监控技术探究
在数字化办公与网络安全需求增长的背景下,局域网实时监控成为企业管理和安全防护的关键。本文介绍C#网络套接字算法在局域网实时监控中的应用,涵盖套接字创建、绑定监听、连接建立和数据传输等操作,并通过代码示例展示其实现方式。服务端和客户端通过套接字进行屏幕截图等数据的实时传输,保障网络稳定与信息安全。同时,文章探讨了算法的优缺点及优化方向,如异步编程、数据压缩与缓存、错误处理与重传机制,以提升系统性能。
33 2
|
1天前
|
机器学习/深度学习 存储 算法
基于MobileNet深度学习网络的活体人脸识别检测算法matlab仿真
本内容主要介绍一种基于MobileNet深度学习网络的活体人脸识别检测技术及MQAM调制类型识别方法。完整程序运行效果无水印,需使用Matlab2022a版本。核心代码包含详细中文注释与操作视频。理论概述中提到,传统人脸识别易受非活体攻击影响,而MobileNet通过轻量化的深度可分离卷积结构,在保证准确性的同时提升检测效率。活体人脸与非活体在纹理和光照上存在显著差异,MobileNet可有效提取人脸高级特征,为无线通信领域提供先进的调制类型识别方案。
|
5天前
|
资源调度 算法 数据可视化
基于IEKF迭代扩展卡尔曼滤波算法的数据跟踪matlab仿真,对比EKF和UKF
本项目基于MATLAB2022A实现IEKF迭代扩展卡尔曼滤波算法的数据跟踪仿真,对比EKF和UKF的性能。通过仿真输出误差收敛曲线和误差协方差收敛曲线,展示三种滤波器的精度差异。核心程序包括数据处理、误差计算及可视化展示。IEKF通过多次迭代线性化过程,增强非线性处理能力;UKF避免线性化,使用sigma点直接处理非线性问题;EKF则通过一次线性化简化处理。
|
4天前
|
算法 数据安全/隐私保护 计算机视觉
基于sift变换的农田杂草匹配定位算法matlab仿真
本项目基于SIFT算法实现农田杂草精准识别与定位,运行环境为Matlab2022a。完整程序无水印,提供详细中文注释及操作视频。核心步骤包括尺度空间极值检测、关键点定位、方向分配和特征描述符生成。该算法通过特征匹配实现杂草定位,适用于现代农业中的自动化防控。

热门文章

最新文章