知识库

知识库资源

当前位置:首页>知识库
全部 14 商业 3

启发式:放弃最优解之后,怎么办?

时间:2021-04-24   访问量:1047

欢迎来到《算法通识课》

上一讲我们说到,当问题规模比较大的时候,即使用分支定界策略,找到最优解也还是很慢。慢到你这辈子过完了,计算机都没给你返回答案。

这时候,我们就得退而求其次。能不能放弃对最优解的执念,割舍一点解决问题的质量,换来一些运行效率高的算法呢?

当然可以。怎么做呢?这就引出我们这一讲要介绍的算法策略:启发式算法。

1 启发式算法:基于人类直觉认识的算法

什么是启发式算法呢?咱们看一个例子。

比如你现在想要环中国自驾游。从北京出发,把中国的各个省级行政区都游历一遍,各个省的省会、自治区的首府,以及直辖市、特别行政区,全都走一遍,而且要把花在路上的时间尽量缩短,行程应该怎么安排呢?

方案太多了,你可能一时间想不到。这个问题在算法界有个学名,叫“旅行商问题”。

旅行商问题是一个组合优化问题,特别复杂。上一讲我们也提到了,这类问题,找到一个可行解很容易,但找到最优解特别难。

比如你从北京出发,第一个目的地应该是哪里呢?有33个选项。第二站到哪里,有32个选项。把所有路线都考虑到,有10的36次方这么多种组合。

把这些组合都评估一遍,找到最优方案,即使用我们上一讲说到的分支定界法,也是非常困难的。

那怎么办呢?咱们先把算法放在一边,想想自己遇到这个问题会怎么做。

考虑三十几个城市的旅行顺序很困难,但如果只考虑一个城市总是可以的吧。

比如说,从北京出发,用最短的时间,再去一个城市,去哪个城市呢?这就比较简单了。天津就符合标准,可以选天津作为第一站。到了天津之后,我们还是只看一步,找找除了北京和天津之外的目的地哪个离自己最近,那就把它当作第二站的目的地。这第二站是石家庄。

以此往复,最后就能制定出一套行程,而且写成算法也能高效运行。

但这套算法是最优的吗?大部分时候都不是,但它特别符合人的直觉。这就是解决旅行商问题的一个简单的启发式算法。

旅行商问题在实际当中很常见。比如说你的快递公司,要派出多个邮递员到不同的地点送货、收货。每一个邮递员的线路规划就类似于一个旅行商问题。

概括地说,启发式算法是人们通过对问题的理解,以某一套规则制定出来的一类算法。启发式算法通常放弃了最优解,但却能得到还不错的可行解。

这里有一个值得我们注意的地方。一个适用于旅行商问题的启发式算法,是不能用在别的问题上面的。启发式算法是针对特定问题设计出来的,需要具体问题具体分析。这是启发式算法的一个重要特征。

2 元启发式算法:基于对自然认识的算法

那问题来了,使用启发式算法,需要我们对问题本身有足够的了解。这就导致每个启发式算法的使用范围有限。有没有对各个问题都适用的启发式算法呢?

有。但我们不再管它们叫启发式算法,而叫它们元启发式算法。这里的“元”在英文中对应的单词是meta,代表的是“超越、关于”的意思。所以元启发式算法可以理解为,比普通启发式算法高一层,是产生启发式算法的算法思想。

我们来具体说个例子。我们知道,地球上的生物是通过基因的遗传,环境的筛选变成现在这个样子的。而达尔文的学说告诉我们,正是这种基因演变、环境选择的过程,造就了有很高适应性的生物。

那我们能不能在算法中模拟这个过程,解决一些实际问题呢?

能!这样做的算法就叫“基因算法”。

怎么模拟基因呢?生物界中的基因是由A, T, C, G等几种碱基排成的一个序列。其实是不是A, T, C, G并不重要,重要是它们排成的序列。

比如我们前面课程里讲的“背包问题”,要解决“怎么用一个背包背走最值钱的东西”这个问题。怎么模拟?如果拿第一和第二个物品,不拿第三和第四个,那这个决策就可以写成[1,1,0,0]这么一个序列。这和基因序列就很相似。

这个把实际问题中的决策,转化成某种类似基因序列的过程叫“编码”。

基因编码出来了,后续的过程,还得有杂交。杂交,就是雌雄两性在交配的时候,把自己一半的基因传递给后代的过程。这个过程怎么模拟呢?

比如说,父亲的序列是[1,1,0,0],母亲是[0,0,1,1],他们生了两个孩子。那孩子的基因序列就可以分别是[1,1,1,1]和[0,0,0,0],各自继承父母基因序列的前一半和后一半。这就实现了对杂交的模拟。

当然,咱们刚刚举的例子很简单,只是众多编码和杂交模拟方式中的一种。不同的问题有不同的模拟方法,同样的问题也可以有不同的模拟方法。

即便是这样,基因算法的整个框架还是一致的。 基因遗传主要包括了四个步骤,编码、杂交、突变和选择,我们只要规定好如何模拟这四个步骤,基因算法就确定了。

这个框架给了基因算法很强的灵活性。作为元启发式算法中的一种,它并不和某个特别的问题挂钩。所以基因算法也可以用到其它组合优化的问题上去。

比如说,飞机的设计。

飞机设计中的一个重要目标就是最大化它的航程。而这个航程以复杂的形式依赖于飞机设计中的各个参数,比如飞机重量,翼展,动力,机翼后掠角,等等。怎么在每个变量的限制条件中,找到一个好的组合呢?这时候就可以用基因算法。而基因算法也还在很多不同领域有所应用。

这就是元启发式算法在不同问题上的通用性。

元启发式算法还有一个很有趣的特点,就是它们对自然中逻辑的借用。

比如说基因算法,利用的是遗传中“适者生存”的道理,把适应度低的解淘汰掉。

蚁群算法,是利用蚁群信息素的概念,对网络问题进行求解。

粒子群算法,模拟鸟类觅食的过程,可以对最优解的位置进行搜索。

小小总结一下,元启发式算法是通过对自然运作的逻辑观察,或者对人类解决问题时通用逻辑的观察,总结出来的一系列通用启发式算法。

3 什么时候才用启发式算法

启发式算法和元启发式算法虽然有不同,但很类似,我们为了简单,统称它们为启发式算法。

我们刚刚了解了它们是怎么运作的,要么很符合直觉,要么很符合自然规律,好像挺好用。但其实不到迫不得已,算法工程师并不会用它。为什么呢?我说两个它不好用的地方。

第一,启发式算法对最优解没有保证。

比如说我们刚才讲过的旅行商问题。按我们刚刚说的,走一步看一步的方法,得到的结果和真正的最优路径相比,相差多少呢?我们不知道。

所以,如果你想保证自己用的路线,最大限度地接近最优路线,启发式算法并不好用。

第二,启发式算法好不好用,是一个试错的过程。

我们要解决一个问题,可以用不同的启发式算法,哪个更好呢?只有试试才知道。

一个算法多久能得到比较好的解呢?只有试试才知道。

如果问题中的某个参数稍稍改变了,算法的表现会变吗?只有试试才知道。

你听到这,会不会觉得启发式算法根本不靠谱?也并不是。我再和你分享一个用启发式算法特别成功的案例。

20世纪的80年代,IBM公司是电脑芯片的重要制造商之一,他们要做大量的芯片设计工作。芯片的设计有个难点,就是如果芯片上的电路摆放得不合理,就会降低整个芯片的运行效率。

但芯片设计师并没有特地为了提高效率,就对电路的摆放进行优化。因为在当时,能把电路安上就不错了,优化就别提了。

这时候,一个叫柯克帕特里克的工程师突发奇想,从金属冶炼的过程中找到了灵感。

在冶金行业中,有一个工艺,叫退火。就是让金属的温度慢慢降低。“慢慢”很重要,因为这样金属内部的原子,才能有充分的时间随机运动,最后得到的金属,延展性和韧性都更好。

柯克帕特里克发现,寻找最优电路设计的过程,也可以看作是一个在搜索空间里随机运动的过程。

最开始,温度比较高,随机运动比较剧烈,即使我们从设计方案A跳到方案B,没有提高运行效率,这个跳跃也可以发生。但随着温度慢慢降低,发生跳跃的要求也慢慢增高,只有新方案的效率更高,我们才能从旧的方案跳到新的方案。最后,方案慢慢稳定,我们得到了一个最终的设计方案。

这套算法方案就叫“模拟退火”。模拟退火算法能把芯片设计的效率提高10%到60%。

为什么模拟退火这么成功呢?因为这个问题特别适合用启发式算法来解决。

在电路设计的问题中,我们知道最优解很难找到,但至少有一个可行解。在有了可行解的基础上,任何提高都是好的。这时候,启发式算法就很适合。

所以,在找不到最优解的时候,我们可以退而求其次,用启发式算法来求解。但启发式算法又是一把双刃剑,带来好处的同时,又会增添一些新的烦恼。

总结一下这讲的内容。启发式算法是一类要么符合人的直觉,要么符合自然规律的算法。遇到特别复杂的组合优化问题时,如果找不到最优解,我们可以转而使用启发式算法,找到不错的可行解。

 划重点

1 遇到特别复杂的组合优化问题时,如果找不到最优解,我们可以转而使用启发式算法,找到不错的可行解。

2 启发式算法是人们通过对问题的理解,以某一套规则制定出来的一类算法。

3 元启发式算法是通过人们对自然或者人类解决问题时通用逻辑的观察和模拟,总结出来的一系列通用启发式算法。

最后,给你留一道思考题。你曾经遇到过哪个组合优化问题,解决的时候用的是什么样的启发式算法呢?

当我们不损失求解的质量,就求不出来解的时候,启发式算法是一个办法。还有一种算法策略,蒙特卡罗方法,也是这样。我们下一讲详细来说。


上一篇:分支定界:怎样决定谁是“被淘汰者”?

下一篇:蒙特卡罗:丢失确定性之后,怎么办?

发表评论:

评论记录:

未查询到任何数据!
点击这里给我发消息

在线咨询

咨询专员 点击这里给我发消息

点击这里给我发消息 售后服务专员

在线咨询

免费通话

24小时免费咨询

请输入您的联系电话,座机请加区号

免费通话

微信扫一扫

微信联系
返回顶部