爬山法
数学方法
概念
解多变量无约束最优化问题的一类方法。有的书上称直接法或直接搜索法,是通过点的直接移动产生的目标值有所改善的点,经过这样的移动,逐步到达使目标函数最优的点。如果我们把目标函数的几何图形看成一个山峰,那么点的直接移动就像人在爬山,选择方向,逐步向山顶移动。可分为轴向搜索法、单纯形调优法、Powell法等。轴向搜索法是以沿坐标轴方向移动为基础的搜索方法,在进行每一轮沿坐标轴方向搜索时,是从一参考点出发,依次沿平行于各个坐标轴方向连续作对应的目标函数值改进的搜索移动,并以最后获得的点作为下一轮迭代点。同时,为提高求解的效率.还要采取某些加快收敛的措施。
问题求解的过程就是努力沟通问题的起始状态和目标状态之间的联系链条,由起始状态出发,逐步向目标推移、逼近的过程。在思维课题的求解活动中,人们几乎总是一直关注着所要达到的最终目标,试图不断地向目标逼近。这就像在登山活动中运动员时刻把顶峰放在心目之中,力图接近它、占领它一样。在解决思维课题时,我们经常自觉或不自觉地运用着能够尽量向目标靠拢的方法。这也就是通常所说的爬山法。
步骤
简单地说,爬山法就是按照下述原则进行试探的方法。这就是在每一状态下都选取这样的步骤进行试探:由这个步骤所达到的终结状态是所有可容许步骤所能达到的终结状态中,最接近最终目标的一个。这样的步骤称为最优步骤。按照这样的原则依次选取步骤,顺序试探下去,直到最终目标为止。如果达不到最终目标,可以回过头来,从已经经历过的某一中间状态开始,改用直接效果稍差一点的次优步骤,沿着另一条分支途径再行试探下去。当然,也可以一下子回转到整个问题的起始状态,沿着另一条全新的途径进行试探。到底应当返回到什么状态开始另行试探,这要由解题者根据具体情况作出自己的判断。
与中途法关系
爬山法与中途点法是彼此接近的方法。中途点法在实质上也就是通过一个个的中途点而向最终目标逼近的方法。同时,在问题求解活动中,这两种方法也是紧密相联.可以配合使用的。比如,有一个数学问题,要求决定两个量v,u之间的关系。我们可以把求出包含v,u的关系式(其中可以含有其他未知量)和求出只包含v,u和已知量的关系式作为两个中途点,把整个求解过程区分为三个小阶段。在每个小阶段中又可分别应用爬山法来进行试探。在第一阶段中,那些能够得出同时把v,u包括进去的关系式的步骤将被看做是较优的步骤;而能够得出既把v,u同时包含在内,又含有最少的其他未知量,并且显得比较简单.对其他未知量容易加以分离、代换和消除的关系式的步骤就是最优步骤。在第二阶段中,那些能够消除其他未知量个数最多的步骤将是最优步骤。把爬山法同中途点法结合起来运用,可以更好地发挥它们的作用。
特点
爬山法要求人们在推演的每一步上作出局部性的合理选择.为进行试探提供了作出衡量、判别的一种原则,使试探工作能具有更明显的条理性和某种程度上的程序性与可操作性。在问题求解活动中.人们也往往是自觉或不自觉地运用着爬山法的原则。不过,尽管爬山法有着相当广泛的应用,但却并非是总能奏效的,因为它也有着明显的弱点和局限性。
首先,在许多思维课题的求解活动中,我们既无法具体地开列出从某一状态出发的所有容许推演步骤,更难以判定在这些步骤所得出的各种终结状态中哪一个同最终目标最为接近。例如,在求证某一几何命题时,一般情况下,我们并不清楚可以运用哪些几何定理,能够作出哪些辅助图形,更难以从各种推演步骤所可能得出的结果中把最接近于最终目标的结果选取出来。这种状况的存在,给爬山法的运用带来了原则性的困难。
其次,解决问题的有效思路大多是迂回曲折的。“曲径通幽处。禅房花木深”。对于需要充分发挥思维的创造性功能的问题求解来说.几乎总是需要历经曲折才能找到通向目标的路径。在某些情况下,甚至还需要暂时沿着同目标正相背离的途径进行一段路程,才能够达到探隐索幽,揭示事物底蕴,觅得待求结果的目的。与此相反,那些一开始就直接向目标逼近,能够带来明显进展的路径,却有可能把我们引入无法达到目标的死胡同之中。对于不少问题来说,甚至完全有可能“在解题过程的末尾困难成堆”。“这就像有许许多多小路,你可以沿着这些小路爬到很接近顶峰的地方,却只有少数几条路可以直接通到最高峰。所以爬山法(在解题的意义上)虽然能大大缩小尝试范围,却仍然不是解这类问题的好方法。你能用爬山法走完解这类问题的大半路程,却往往在最后时刻功亏一篑。”
应当指出,对于爬山法同推演路径的迂回曲折不相适应的弱点,我们是可以在一定程度上设法加以补救的。只要把目光放远一些,不是只看到当前的一步,而是看到接续下去的两步、三步乃至更多的步数,也就能够跨越局部存在的迂回曲折,看清楚在较大范围内真正能向上攀登的道路。
人们在求解问题时总是要力图达到目标;但经验丰富、眼界开阔的人可以看得更远一点,审度出欲进先退、欲取姑与的曲折关系。虽然在某一步上远离了目标,但在第二步、第三步上却可以前进得更多,使先前的损失得到加倍的补偿;而不是像没有经验的人那样,只能看到眼前的一步。虽然从所采取的那一步来说是前进了。但接着下去却会很快地面对绝壁悬崖,陷入走投无路的困境之中。这就如同下象棋一样.初学的人大多老是盯着对方的棋子,总想多“吃掉”一个,哪怕是“吃掉”一个无足轻重的小卒,也会一阵沾沾自喜.而无力认识这一步着法对以后的着法和整个棋局带来的不良后果。高明的棋手看到的就不止一步。他会对两三步、乃至更多步以后的情况作出判断。如果接下去几步之后确实能够把对方置于死地,即使在要着的一步上会引起车的丢失,也是乐意为之的。至于在思维课题的求解活动中怎样才能看得更远一点,认清真正取得进展的标志,却并不存在普遍有效的标
准与原则,只能主要凭借自己的经验和进行洞察与鉴别的能力来作出判断。
应用
(1)建立一个描述数据库变化的单极值函数,且使极值对应目标状态;
(2)选取使函数值增长最大的那条规则作用于数据库;
(3)重复上步,直到没有规则使函数值继续增长。
参考资料
最新修订时间:2023-11-17 22:33
目录
概述
概念
参考资料