• 精选
  • 会员

三个重要结论

2020年7月21日  来源:多样性红利 作者:【美】斯科特·佩奇 提供人:chenpo21......

现在已经触及到了一个重要的想法:以各自的局部最优解,也就是景观中的高峰来表示问题解决者。问题解决者(或问题解决程序)通常拥有许多局部最优解,而且他总会有一个最优的解决方案。所有人都同意珠穆朗玛峰是世界最高峰!问题解决者可能找不到珠穆朗玛峰,但是如果把他放上珠穆朗玛峰,他会认出这是一个高峰。接下来将提出三个观察结论,它们能够将问题解决者的特征与各自的局部最优解联系起来。

观察结论一描述的是较好的问题解决者与局部最优解之间的关系:

个人表现更好的问题解决者有更好的局部最优解:那些个人表现更好的问题解决者往往会被锁定在价值相对较高的局部最优解上。

这个观察结论说明,价值相对较高的局部最优解是有优势的。再次以旅行商问题为例。如果某个问题解决者有两个局部最优解:一个是总里程为2 300千米的路线,其实这就是全局最优解,另一个是总里程为2 400千米的路线,那么这个人可能会比其他有两个别的局部最优解的问题解决者表现得更好,例如其中一个总里程为2 900千米。需要注意的是,在这里假设这两个问题解决者找到他们各自的局部最优解的可能性相等,稍后将放宽这个假设。

观察结论二是,更好的问题解决者倾向于只拥有较少的局部最优解。他们所使用的视角、所创建的景观不那么崎岖;根据定义,不那么崎岖的景观的局部最优解相对较少一些。或者,他们可能拥有更多的启发式,可以更容易离开各自景观中的高峰。无论具体原因是什么,他们都会较少被卡在局部高峰上。

更好的问题解决者所拥有的局部最优解较少:那些个人表现更好的问题解决者倾向于拥有更少的局部最优解。

要解释这个结论,所需要的直觉也很简单。局部最优解就是可能会让问题解决者卡住的点。但是,这些局部最优解中必定有一个是最佳解决方案,其他局部最优解的价值都比不上它,卡在其他解决方案上会导致更糟的结果。一般来说,局部最优解越多,搜索就越容易卡在某个局部最优解上,从而问题解决者的表现就越差。

还可以把前两个观察结论组合起来。“个人”表现好的问题解决者应该具有相对较少的局部最优解,而且他们的局部最优解都具有较高的价值。相反,可以预期“个人”表现差的问题解决者具有很多局部最优解,但是其中许多局部最优解的价值都比较低。

上述结论虽然有很强的说服力,但是用问题解决者所拥有的局部最优解数量以及价值来刻画他们的特征,并不能到达目的地。问题解决者找到每个局部最优解的概率也很重要。假设一个问题解决者只有两个局部最优解,其中一个是全局最优解,另一个是价值相对来说更低一些的局部最优解。但是如果几乎总是找到低价值的局部最优解,那他的平均表现就会很差。反过来,如果几乎总能找到全局最优解,那他的平均表现就会很好。为了更正式地说明这个观点,在这里引入一个“吸引盆”(basin of attraction)的概念。笼统地说,一个局部最优解吸引盆的大小,就等于问题解决者被卡在那个峰值上的概率。

吸引盆这个术语源于物理学,可以通过想象厨房或浴室中的各种盆得到一个直观的理解。试想一下,把一个超级弹跳球扔进一个放满各种大小和形状水槽的房间里会怎样?球将从一个水槽跳到另一个水槽,最后停留在某个水槽底部。在其他所有条件都相同的情况下,可以预测,一个水槽越大、越深,球落在这个水槽底部的可能性就越大。也可以将同样的直觉应用于登山,但是必须将画面颠倒过来看。物理学家经常讲最小化,问题解决者则希望实现最大化,因此,对于问题解决者来说,“盆”的深度和大小,可以用来类比山峰的高度和宽度、(见图6-5)。

图6-5 盆与峰

尽管个人和团队都在试图实现最优化,但这里还是遵循学术上的惯例,使用“盆”这个术语。

凯伦和保罗是两个在南美洲种植香蕉的农场主,他们正在尝试培育一种保质期更长的香蕉。假设,最好的香蕉在被采摘后有30天的保质期。凯伦使用的是传统的遗传育种技术,这是她的启发式。假设这种技术会导致三个局部最优解:最好的解决方案,保质期为30天;次好的解决方案,保质期为24天;再次的解决方案,保质期为12天。保罗则依赖于转基因技术。他的启发式也有三个局部最优解:能够分别生产出保质期为30天、25天和20天的香蕉。如果这两个问题解决者能够找到他们的每个局部最优解,那么保罗的表现将比凯伦更好。

为了说明吸引盆大小的重要性,再假设凯伦的最佳解决方案有一个更大的吸引盆,这就是说,她在2/3的时间内都能够找到最优的解决方案,而只在1/6的时间内会以发现其他两个非最优解决方案中的某一个而告终。同时假设保罗找到他的三个解决方案的机会都相等。在这些假设下,凯伦的平均表现将更好。

由此,可以得到观察结论三:吸引盆的大小是重要的,好的问题解决者往往有更大的吸引盆,从而更容易到达更好的局部最优解。

在目前为止所阐述的内容的基础上,可以将问题解决者描述为一组局部最优解,以及停留在每个局部最优解上的概率。在上面这个例子中,可以将凯伦这个问题解决者描述为:有三个局部最优解,其集合为{30,24,12},每个局部最优解的的概率为()。同样,可以把保罗表示为:有三个局部最优解,其集合为{30,25,20},相应的概率是()。当然,需要注意的是,在这些局部最优解中已经包含了全局最优解。两个人都必须找到最好的解决方案。

这种将问题解决者描述为局部最优解的集合以及找到概率的方法是非常有用的,但它不是问题解决者集合的一种视角。接下来将会证明,两个问题解决者即便有完全不同的视角和启发式,也仍然能够产生相同的局部最优解与相同的找到局部最优解的概率。因此,从问题解决者到一个附加了概率的局部最优解集合的映射,应当被视为一种解释,它能够对问题解决者进行分类。这种分类从表面上看似乎过于琐碎了,但是事实并非如此。它使我们能够在内部解决问题多样性与外部解决问题多样性之间做出区分。这是一个重要的区分。

内部的解决问题多样性与外部的解决问题多样性

在开始讨论这个区分之前,先回过头去“盘点”一下已经学到手的东西。一个人的视角和启发式定义了某个现有解决方案的“邻居”,即问题解决者打算去搜索的解决方案,也就是视角、启发式能够识别出来的解决方案。视角和启发式是解决问题的内在因素,外部观察者不一定知道它们。外部观察者可以观察到的是解决问题的外在因素,也就是问题解决者如何通过各种方法来找到解决方案。当然,仅仅是了解这些东西,也需要观察者付出一定的努力,但是在这里,暂且忽略这一点。

下面给出的一个例子需要你放慢阅读速度,仔细研究。这个例子并不困难,但需要耐心。先重置一下你的认知框架,就像某个大城市的公共交通系统图一样,看上去似乎一团糟,但是有一个基本的逻辑在里面。在这个例子中,两个问题解决者的视角和启发式都不相同,但是都同样是外部的,他们在解决方案的空间中以完全相同的方式进行搜索。

先从视角开始讨论。在图6-6所示的两个视角中,每一个视角都以各自的方式组织了8个可能的解决方案,分别用立方体上的字母A~H表示。阿尔法视角组织解决方案的方法是,按字母顺序以逆时针方向排列在每个层级上。混杂视角则随机排列立方体上的字母。

图6-6 一个立方体的两种视角

有两个问题解决者,萨姆和麦迪。萨姆使用了阿尔法视角,而麦迪所使用的则是混杂视角。同时萨姆和麦迪还使用了不同的启发式,每人都有三个启发式。定义他们的启发式,要用到立方体的各条棱。麦迪的三个启发式都需要沿着这些棱移动。从混杂视角中的解决方案A出发,麦迪要沿着立方体的三条棱,找到解决方案G、C和F:G位于A的右边,C位于A的后面,F位于A的上面。

与麦迪相比,萨姆则使用了更加复杂的启发式。他的第一个启发式要沿着左右维度及前后维度移动。从A开始,萨姆找到了C。他的第二个启发式方法沿着左右维度及上下维度移动。再一次,从A开始,萨姆找到F。他的第三个启发式要在所有三个维度上移动。这种启发式导致他移动到了立方体上最远那个角落。这是“反其道而行之”启发式的立方体版。使用这个启发式,萨姆直接从A跳跃到了G。

图6-7有助于理解萨姆和麦迪对他们视角的搜索。

图6-7 内部多样性及外部等价性

如图6-7所示,萨姆和麦迪都要从A出发找到同样的三个解决方案。不过,只要花点工夫就可以证明,无论从哪里开始,这种等价性依然成立。例如,使用如上所述的启发式,如果麦迪从解决方案D开始,那么他将找到F、B和G。萨姆也是一样,如果他从D开始,那么他路过A横走到B、路过C上行到G,并跳到对角的F(见图6-6)。

理解这个例子需要付出一些努力。喜欢数学的人可能觉得它很酷,但是你需要关注它的含义吗?9是的。这个例子表明,内部多样性(多样性视角和多样性启发式)不一定会导致外部多样性(在解决方案空间中的不同搜索方式)。人与人之间当然会有不同,但是他们仍然可能会以同样的方式去寻找解决方案。具有多样性视角和启发式的人们在解决问题时仍然可能类似。10换句话说,多样性的视角和启发式可能会相互抵消。这种抵消可能不会非常频繁地发生,但是不能保证,两个使用不同表示方法并且应用不同问题求解技术的人,肯定会以不同方式去寻找解决方案。因此结论是:多样性的人也可能不会以不同的方式去解决问题。

多样性 / 解决问题

如涉及版权,请著作权人与本网站联系,删除或支付费用事宜。

0000