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

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

背景


作为阿里达摩院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

钉钉大群:32451444   找群主

image.png




目录
相关文章
|
1天前
|
搜索推荐
【hoare优化版】快速排序算法 | 三数取中&小区间优化(2)
【hoare优化版】快速排序算法 | 三数取中&小区间优化(2)
4 0
|
7天前
|
存储 算法 搜索推荐
掌握数据结构与算法,成为技术大牛
数据结构与算法是计算机科学中至关重要的基础知识,它们的应用贯穿于各种编程语言和技术领域。本文将介绍数据结构与算法的基本概念及其在实际开发中的应用,帮助读者打下坚实的技术基础,成为真正的技术大牛。
24 4
|
12天前
|
算法 大数据
【MATLAB】鲸鱼算法优化混合核极限学习机(WOA-HKELM)回归预测算法
【MATLAB】鲸鱼算法优化混合核极限学习机(WOA-HKELM)回归预测算法
27 2
|
13天前
|
缓存 Rust 算法
Rust中的数据结构与算法优化实践
在Rust编程语言中,优化数据结构与算法是提高程序性能的关键。本文首先介绍了Rust的特点,然后重点讨论了如何在Rust中优化数据结构和算法,包括使用标准库中的高效数据结构、自定义数据结构的优化技巧、算法选择与改进、以及Rust特性如所有权和借用检查器的应用。通过实际案例,我们将展示如何在Rust中实现更高效的数据结构与算法。
|
30天前
|
算法 5G 网络性能优化
基于遗传优化的多属性判决5G-Wifi网络切换算法matlab仿真
基于遗传优化的多属性判决5G-Wifi网络切换算法matlab仿真
|
30天前
|
存储 安全 算法
保护数据隐私的安全加密算法:技术守护个人信息安全的利器
在数字化时代,个人信息安全日益受到威胁。本文将深入探讨安全加密算法的重要性,以及如何利用先进的技术保护个人数据的隐私。从对称加密到非对称加密,再到现代密码学的发展,我们将一一解析这些技术的原理和应用。通过了解安全加密算法,我们可以更好地保护个人数据隐私,确保信息的安全传输和存储。
24 3
|
1月前
|
机器学习/深度学习 算法
【Matlab智能算法】PSO优化(双隐层)BP神经网络算法
【Matlab智能算法】PSO优化(双隐层)BP神经网络算法
|
1月前
|
存储 人工智能 搜索推荐
【探索排序算法的魅力:优化、性能与实用技巧】(下)
【探索排序算法的魅力:优化、性能与实用技巧】
|
1月前
|
搜索推荐
【探索排序算法的魅力:优化、性能与实用技巧】(中)
【探索排序算法的魅力:优化、性能与实用技巧】

热门文章

最新文章