南邮自动化人工智能8--自动规划30865.pptx

《南邮自动化人工智能8--自动规划30865.pptx》由会员分享，可在线阅读，更多相关《南邮自动化人工智能8--自动规划30865.pptx（41页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章第八章 自动规划自动规划 教学内容：介绍自动规划的基本概念和各种规划系统。教学内容：介绍自动规划的基本概念和各种规划系统。教学重点：机器人规划的作用与任务、积木世界的规划系教学重点：机器人规划的作用与任务、积木世界的规划系 统、基于模拟退火算法的机器人局部路径规划。统、基于模拟退火算法的机器人局部路径规划。教学难点：教学难点：Strips规划系统。规划系统。教学方法：课堂教学为主，注意结合例子来说明抽象概念。教学方法：课堂教学为主，注意结合例子来说明抽象概念。教学要求：本章为选修内容，掌握机器人规划的作用与任教学要求：本章为选修内容，掌握机器人规划的作用与任 务，并一般了解有哪几种规划方

2、法。务，并一般了解有哪几种规划方法。第一节第一节 自动规划概述自动规划概述 8.1.1规划的概念和作用规划的概念和作用1、规划的概念及作用、规划的概念及作用规划的概念：规划的概念：规划是一种重要的问题求解技术，它从某规划是一种重要的问题求解技术，它从某个特定的问题状态出发，寻求一系列行为动作，并建立个特定的问题状态出发，寻求一系列行为动作，并建立一个操作序列，直到求得目标状态为止。一个操作序列，直到求得目标状态为止。规划的作用：规划的作用：规划可用来监控问题求解过程，并能够在规划可用来监控问题求解过程，并能够在造成较大的危害之前发现差错。规划的好处可归纳为简造成较大的危害之前发现差错。规划的好

3、处可归纳为简化搜索、解决目标矛盾以及为差错补偿提供基础。化搜索、解决目标矛盾以及为差错补偿提供基础。战略规划：战略规划：就是组织制定长期目标并将其付诸实施。第就是组织制定长期目标并将其付诸实施。第一阶段确定目标；第二阶段制定规划。一阶段确定目标；第二阶段制定规划。城市规划：城市规划：指城市政府为了实现一定时期内经济社会发指城市政府为了实现一定时期内经济社会发展目标，确定城市性质，规模和发展方向，合理利用土展目标，确定城市性质，规模和发展方向，合理利用土地，协调空间布局和各项建设所作的综合部署和具体安地，协调空间布局和各项建设所作的综合部署和具体安排。排。人生规划：人生规划：根据社会发展的需要和

4、个人发展的志向，对根据社会发展的需要和个人发展的志向，对自己的未来的发展道路做出一种预先的策划和设计。包自己的未来的发展道路做出一种预先的策划和设计。包括健康规划，事业规划，情感规划，晚景规划。括健康规划，事业规划，情感规划，晚景规划。子规划的分层结构例子子规划的分层结构例子 规划的作用：规划的作用：科学规划方法不仅对国家和社会贡献很大，对科学规划方法不仅对国家和社会贡献很大，对于个人学习和工作也极为有益。于个人学习和工作也极为有益。8.1.2规划的分类与问题分解途径规划的分类与问题分解途径 1、规划的分类、规划的分类(1):按规划内容分按规划内容分(2):按规划方法分按规划方法分(3):按规

5、划性质分按规划性质分任务规划任务规划(高层规划高层规划)路径规划路径规划(中层规划中层规划)轨迹规划轨迹规划(底层规划底层规划)2、问题分解途径及方法、问题分解途径及方法把某些较复杂的问题分解为一些较小的子问题。有把某些较复杂的问题分解为一些较小的子问题。有两条实现这种分解的重要途径。两条实现这种分解的重要途径。第一条重要途径是当从一个问题状态移动到下一个第一条重要途径是当从一个问题状态移动到下一个状态时，无需计算整个新的状态，而只要考虑状态中可状态时，无需计算整个新的状态，而只要考虑状态中可能变化了的那些部分。能变化了的那些部分。第二条重要途径是把单一的困难问题分割为几个有第二条重要途径是把

6、单一的困难问题分割为几个有希望的较为容易解决的子问题。希望的较为容易解决的子问题。3、域的预测和规划的修正、域的预测和规划的修正(1)域的预测域的预测规划方法的成功取决于问题论域的另一特性规划方法的成功取决于问题论域的另一特性-预测。如预测。如果通过在实际上执行某个操作序列来寻找问题的解答，那末果通过在实际上执行某个操作序列来寻找问题的解答，那末在这个过程的任何一步都能确信该步的结果。但对于不可预在这个过程的任何一步都能确信该步的结果。但对于不可预测的论域，最好能考虑可能的结果的集合，这些结果很可能测的论域，最好能考虑可能的结果的集合，这些结果很可能按照它们出现的可能性以某个次序排列。然后，产

7、生一个规按照它们出现的可能性以某个次序排列。然后，产生一个规划，并试图去执行这个规划。划，并试图去执行这个规划。(2)规划的修正规划的修正如果规划在执行中失败了，那么就需要对它进行修订，如果规划在执行中失败了，那么就需要对它进行修订，为便于修订，在规划过程中不仅要记下规划的执行步骤，而为便于修订，在规划过程中不仅要记下规划的执行步骤，而且也要记下每一步骤必须且也要记下每一步骤必须被执行的理由被执行的理由。大多规则的执行主。大多规则的执行主要是按目标定向模式工作的。在种模式下，规划系统从目标要是按目标定向模式工作的。在种模式下，规划系统从目标状态向可达到的初始状态进行搜索。状态向可达到的初始状态

8、进行搜索。8.1.3规划系统的任务与方法规划系统的任务与方法 在规划系统中，必须具有执行下列各项任务的方法：在规划系统中，必须具有执行下列各项任务的方法：(1)根据最有效的启发信息，选择应用于下一步的最好规根据最有效的启发信息，选择应用于下一步的最好规则。则。(2)应用所选取的规则来计算由于应用该规则而生成的新应用所选取的规则来计算由于应用该规则而生成的新状态。状态。(3)对所求得的解答进行检验。对所求得的解答进行检验。(4)检验空端，以便舍弃它们，使系统的求解工作向着更检验空端，以便舍弃它们，使系统的求解工作向着更有效的方向进行。有效的方向进行。(空端：即死端，指无法从它到达目标的端点。空端

9、：即死端，指无法从它到达目标的端点。)(5)检验殆正确的解答，并应用具体的技术使之完全正确。检验殆正确的解答，并应用具体的技术使之完全正确。下面讨论能够执行上述下面讨论能够执行上述5项任务的方法。项任务的方法。1、选择和应用规则、选择和应用规则在选择合适的应用规则时最广泛采用的技术是：首先要在选择合适的应用规则时最广泛采用的技术是：首先要查出期望目标状态与现有状态之间的差别集合，然后辨别出那查出期望目标状态与现有状态之间的差别集合，然后辨别出那些与减少这些差别有关的规则。些与减少这些差别有关的规则。2、检验解答与空端、检验解答与空端当规划系统找到一个能够把初始问题状态变换为目标状态当规划系统找

10、到一个能够把初始问题状态变换为目标状态的操作符序列时，此系统就成功地求得问题的一个解答。的操作符序列时，此系统就成功地求得问题的一个解答。如果搜索过程是从初始状态正向推理的，那么可以删去任如果搜索过程是从初始状态正向推理的，那么可以删去任何导致何导致某种状态某种状态的路径，从这种状态出发是的路径，从这种状态出发是无法达到目标状态无法达到目标状态的。（空端）的。（空端）如果搜索过程是从目标状态逆向推理的，那么当确信无法如果搜索过程是从目标状态逆向推理的，那么当确信无法达到初始状态，或者搜索过程进展甚微时，可以终止该路径的达到初始状态，或者搜索过程进展甚微时，可以终止该路径的搜索。搜索。3、修正殆

11、正确解、修正殆正确解一个求解殆可分解问题的办法是：当执行与所提出的解答一个求解殆可分解问题的办法是：当执行与所提出的解答相对应的操作符序列时，检查求得的状态，并把它与期望目相对应的操作符序列时，检查求得的状态，并把它与期望目标加以比较。标加以比较。修正一个殆正确的解答的修正一个殆正确的解答的较好较好办法是办法是:注意有关出错的知注意有关出错的知识，然后加以直接修正。识，然后加以直接修正。修正一个殆正确的解答的修正一个殆正确的解答的更好更好办法是办法是:实际上不是对解答实际上不是对解答进行全面的修正进行全面的修正,而是不完全确定地让它们保留到最后的可能而是不完全确定地让它们保留到最后的可能时刻。

12、时刻。第二节第二节 任务规划任务规划8.2.1积木世界的机器人问题积木世界的机器人问题 机器人问题既比较简单，又很直观。在机器人问题的机器人问题既比较简单，又很直观。在机器人问题的典型表示中，机器人能够执行一套动作。典型表示中，机器人能够执行一套动作。在这个例子中机器人能够执行的动作举例如下：在这个例子中机器人能够执行的动作举例如下：unstack(a,b)：把堆放在积木：把堆放在积木b上的积木上的积木a拾起。在拾起。在进行这个动作之前，要求进行这个动作之前，要求机器人的手为空手机器人的手为空手，而且，而且积木积木a的顶上是空的的顶上是空的。stack(a,b)：把积木把积木a堆放在积木堆放在

13、积木b上。动作之前要求上。动作之前要求机械手必须已抓住积木机械手必须已抓住积木a，而且，而且积木积木b顶上必须是空的顶上必须是空的。pickup(a)：从桌面上拾起积木从桌面上拾起积木a，并抓住它不放。，并抓住它不放。在动作之前要求在动作之前要求机械手为空手机械手为空手，而且，而且积木积木a顶上没有任何顶上没有任何东西东西。putdown(a)：把积木把积木a放置到桌面上。要求动作之前放置到桌面上。要求动作之前机械手已抓住积木机械手已抓住积木a。采用状态描述作为数据库的产生式系统是一种最简单的采用状态描述作为数据库的产生式系统是一种最简单的问题求解系统。机器人问题的状态描述和目标描述均可用谓问

14、题求解系统。机器人问题的状态描述和目标描述均可用谓词逻辑公式构成。为了指定机器人所执行的操作和执行操作词逻辑公式构成。为了指定机器人所执行的操作和执行操作的结果，需要应用下列谓词：的结果，需要应用下列谓词：ON(a,b)：积木积木a在积木在积木b之上。之上。ONTABLE(a)：积木积木a在桌面上。在桌面上。CLEAR(a)：积木积木a顶上没有任何东西。顶上没有任何东西。HOLDING(a)：机械手正抓住积木机械手正抓住积木a。HANDEMPTY：械手为空手。械手为空手。举例：积木世界由一些有标记的立方形积木，互相堆迭在一举例：积木世界由一些有标记的立方形积木，互相堆迭在一起构成；机器人有个可

15、移动的机械手，它可以抓起积起构成；机器人有个可移动的机械手，它可以抓起积木块并移动积木从一处至另一处。木块并移动积木从一处至另一处。提问：请同学就图提问：请同学就图8.1积木世界的机器人问题应用谓词公式积木世界的机器人问题应用谓词公式的合取描述此目标为：的合取描述此目标为：ON(B，C)ON(A，B)。?初始状态的描述初始状态的描述:图图8.1积木世界的机器人问题积木世界的机器人问题8.2.2用用F规则求解规划序列规则求解规划序列 采用采用F规则表示机器人的动作，这是一个叫做规则表示机器人的动作，这是一个叫做STRIPS规划系统的规则，它由规划系统的规则，它由3部分组成。部分组成。第一部分是先

16、决条件。第一部分是先决条件。为了使为了使F规则能够应用到状态描述中去。规则能够应用到状态描述中去。第二部分是一个叫做删除表的谓词。第二部分是一个叫做删除表的谓词。当一条规则被应用于某个状态描述或数据库时，当一条规则被应用于某个状态描述或数据库时，就从该数据库删去删除表的内容。就从该数据库删去删除表的内容。第三部分叫做添加表。第三部分叫做添加表。当把某条规则应用于某数据库时，就把该添加表当把某条规则应用于某数据库时，就把该添加表的内容添进该数据库。的内容添进该数据库。对于堆积木的例子中对于堆积木的例子中 move 这个动作可以表示如下：这个动作可以表示如下：move(x,y,z)：把物体把物体

17、x 从物体从物体 y 上面移到物体上面移到物体 z 上面。上面。先决条件：先决条件：CLEAR(x),CLEAR(z)，ON(x,y)删除表：删除表：ON(x,y)，CLEAR(z)添加表：添加表：ON(x,z)，CLEAR(y)如果如果movemove为此机器人仅有的操作符或适用动作，那为此机器人仅有的操作符或适用动作，那么，可以生成如下图所示的搜索图或搜索树：么，可以生成如下图所示的搜索图或搜索树：8.2 8.2 表示表示 move move 动作的搜索树动作的搜索树 下面更具体地考虑图下面更具体地考虑图8.1 中所示的例子，机器人的中所示的例子，机器人的 4 个动作个动作(或操作符或操作

18、符)可用可用 STRIPS 形式表示如下：形式表示如下：(1)stack(X,Y)先决条件和删除表：先决条件和删除表：HOLDING(X)CLEAR(Y)添加表：添加表：HANDEMPTY，ON(X，Y)(2)unstack(X,Y)先决条件：先决条件：HANDEMPTYON(X，Y)CLEAR(X)删除表：删除表：ON(X，Y)，HANDEMPTY 添加表：添加表：HOLDING(X)，CLEAR(Y)(3)pickup(X)先决条件：先决条件：ONTABLE(X)CLEAR(X)HANDEMPTY 删除表：删除表：ONTABLE(X)HANDENPTY 添加表：添加表：HOLDING(X)

19、(4)putdown(X)先决条件和删除表：先决条件和删除表：HOLDING(X)添加表：添加表：ONTABLE(X)，HANDEMPTY 假定目标为假定目标为8.1 所示的状态，即所示的状态，即 ON(B,C)ON(A,B)从图从图8.1（a）所示的初始状态描述开始正向操作，只所示的初始状态描述开始正向操作，只有有 unstack(C,A)和和 pickup(B)两个动作可以应用两个动作可以应用 F 规则。规则。图图8.3所示给出这个问题的全部状态空间，并用粗线指出所示给出这个问题的全部状态空间，并用粗线指出了从初始状态了从初始状态(用用S0标记标记)到目标状态到目标状态(用用G标记标记)的

20、解答路的解答路径。径。与习惯的状态空间图画法不同的是，这个状态空与习惯的状态空间图画法不同的是，这个状态空间图显出问题的对称性，而没有把初始节点间图显出问题的对称性，而没有把初始节点S0S0放在图放在图的顶点上。此外，要注意到本例中的每条规则都有一的顶点上。此外，要注意到本例中的每条规则都有一条条逆规则逆规则，如图，如图7.3 7.3 所示。所示。例例:积木世界机器人问题的状态空间积木世界机器人问题的状态空间(见见P216-217)图8.3积木世界机器人问题的状态空间积木世界机器人问题的状态空间 沿着粗线所示的支路，从初始状态开始，正向地依沿着粗线所示的支路，从初始状态开始，正向地依次读出连接

21、弧线上的次读出连接弧线上的 F 规则，就得到一个能够达到目标规则，就得到一个能够达到目标状态的动作序列于下：状态的动作序列于下：unstack(C,A),putdown(C),pickup(B)，stack(B,C),pickup(A),stack(A,B)就把这个动作序列叫做达到这个积木世界机器人就把这个动作序列叫做达到这个积木世界机器人问题目标的规划。问题目标的规划。8.3.1STRIPS系统的组成系统的组成 STRIPS（StanfordResearchInstituteProblemSolver）整个整个STRIPS系统的组成如下：系统的组成如下：(1)世界模型。为一阶谓词演算公式。世

22、界模型。为一阶谓词演算公式。(2)操作符操作符(F规则规则)。包括先决条件、删除表和添加表。包括先决条件、删除表和添加表。(3)操作方法。应用状态空间表示和中间操作方法。应用状态空间表示和中间-结局分析。结局分析。例如：例如：状态：状态：(M，G)，包括初始状态、中间状态和目标状态。，包括初始状态、中间状态和目标状态。初始状态：初始状态：(M0，(G0)目标状态：得到一个世界模型，其中不遗留任何未满足目标状态：得到一个世界模型，其中不遗留任何未满足的目标。的目标。8.2.3STRIPS系统规划过程系统规划过程 每个每个STRIPS问题的解答为某个实现目标的操作符问题的解答为某个实现目标的操作符

23、序列，即达到目标的规划。下面举例说明序列，即达到目标的规划。下面举例说明STRIPS系统系统规划的求解过程。规划的求解过程。例例1考虑考虑STRIPS系统一个比较简单的情况，即要求机系统一个比较简单的情况，即要求机器人到邻室去取回一个箱子。机器人的初始状态和目标器人到邻室去取回一个箱子。机器人的初始状态和目标状态的世界模型示于图状态的世界模型示于图8.4。BOX1机器人箱子r1r2dBOX1机器人箱子r1r2d图图8.4 STRIPS的一个简化模型的一个简化模型设有两个操作符，即设有两个操作符，即gothru和和pushthru(“走过走过”和和“推过推过”)，分别描述于下：，分别描述于下：O

24、P1：gothru(d,r1,r2)；机器人通过房间机器人通过房间r1和房间和房间r2之间的之间的d，即机器人，即机器人从房间从房间r1走过门走过门d而进入房间而进入房间r2。先决条件：机器人在房间先决条件：机器人在房间r1内，而且门内，而且门d连接连接r1和和r2两个房间。两个房间。INROOM(ROBOT，r1)CONNECTS(d,r1,r2)；删除表：删除表：INROOM(ROBOT，S)；对于任何；对于任何S值。值。添加表：添加表：INROOM(ROBOT，r2)。OP2：pushthru(b,d,r1,r2)机器人把物体机器人把物体b从房间从房间r1经过门经过门d推到房间推到房间r

25、2。先决条件：先决条件：INROOM(b,r1)INROOM(ROBOT,r1)CONNECTS(d,r1,r2)删除表：删除表：INROOM(ROBOT,S)，INROOM(b,S);对于任何对于任何S。添加表：添加表：INROOM(ROBOT，r2),INROOM(b,r2)。例例:采用中间采用中间-结局分析方法来逐步求解机器人规划结局分析方法来逐步求解机器人规划(见见P219-221)差别表差别表假定这个问题的初始状态假定这个问题的初始状态M0和目标和目标G0如下：如下：M0：INROOM(ROBOT，R1)INROOM(BOX1,R2)CONNECTS(D1，R1，R2)G0：INRO

26、OM(ROBOT,R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2)假定这个问题的初始状态假定这个问题的初始状态M0和目标和目标G0如下：如下：M0：INROOM(ROBOT，R1)INROOM(BOX1,R2)CONNECTS(D1，R1，R2)G0：INROOM(ROBOT,R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2)BOX1机器人箱子R1R2DBOX1机器人箱子R1R2D图图8.4 STRIPS的一个简化模型的一个简化模型基于中间结局分析方法的规划求解基于中间结局分析方法的规划求解:采用中间结局分析方法来逐步求解这个机器人规划：采用中间结

27、局分析方法来逐步求解这个机器人规划：do GPS的主循环迭代，的主循环迭代，until M0与与G0匹配为止。匹配为止。begin。G0不能满足不能满足M0，找出，找出M0与与G0的差别。的差别。尽管这个问题不能马上得到解决，但是如果初始数据尽管这个问题不能马上得到解决，但是如果初始数据库含有语句库含有语句INROOM(BOX1，R1)，那么这个问题的求解，那么这个问题的求解过程就可以得到继续。过程就可以得到继续。GPS找到它们的差别找到它们的差别:d1 为为 INROOM(BOX1，R1)，即要把箱子即要把箱子(物体物体)放到目标房间放到目标房间 R1内。内。选取操作符：一个与减少差别选取操

28、作符：一个与减少差别d1有关的操作符。根有关的操作符。根据差别表，据差别表，STRIPS选取操作符为：选取操作符为：OP2：pushthru(BOX1,d,r1,R1)消去差别消去差别d1,为为OP2设置先决条件设置先决条件G1为：为：G1：INROOM(BOX1,r1)INROOM(ROBOT,r1)CONNECTS(d,r1,R1)这个先决条件被设定为子目标，而且这个先决条件被设定为子目标，而且STRIPS试图从试图从M0到达到达G1。尽管。尽管G1仍然不能得到满足，也不可能马上找到这仍然不能得到满足，也不可能马上找到这个问题的直接解答。不过个问题的直接解答。不过STRIP发现：发现：如果

29、如果 r1=R2,d=D1，当前数据库含有，当前数据库含有INROOM(ROBOT，R1)那么此过程能够继续进行。现在新的子目标那么此过程能够继续进行。现在新的子目标G1为：为：G1：INROOM(BOX1，R2)INROOM(ROBOT，R2)CONNECTS(D1，R2，R1)GPS(p)；重复第；重复第3步至第步至第5步，迭代调用，以求解此问题。步，迭代调用，以求解此问题。步骤步骤3：G1和和M0的差别的差别d2为为 INROOM(ROBOT，R2)即要求机器人移到房间即要求机器人移到房间R2。步骤步骤4：根据差别表，对应于：根据差别表，对应于d2的相关操作符为的相关操作符为 OP1：g

30、othru(d,r1,R2)步骤步骤5：OP1的先决条件为：的先决条件为：G2：INROOM(ROBOT，R1)CONNECTS(d,r1,R2)步骤步骤6：应用置换式：应用置换式r1=R1和和d=D1，STRIPS系统能够达到系统能够达到G2。把操作符把操作符gothru(D1,R1,R2)作用于作用于M0，求出中间状，求出中间状态态M1：删除表：删除表：INROOM(ROBOT，R1)添加表：添加表：INROOM(ROBOT，R2)M1：INROOM(ROBOT，R2)INROOM(BOX1，R2)CONNECTS(D1，R1，R2)把操作符把操作符pushthru应用中间状态应用中间状态

31、M1，删除表：删除表：INROOM(ROBOT，R2)，INROOM(BOX1，R2)添加表：添加表：INROOM(ROBOT，R1)，INROOM(BOX1，R1)得到另一中间状态得到另一中间状态M2为：为：M2：INROOM(ROBOT，R1)INROOM(BOX1，R1)CONNECTS(D1，R1，R2)M2=G0 end。由于由于M2与与G0匹配，所以通过中间结局分析解答了这个匹配，所以通过中间结局分析解答了这个机器人规划问题。机器人规划问题。在求解过程中，所用到的在求解过程中，所用到的STRIPS规则为操作符规则为操作符OP1和和OP2，即，即 gothru(D1,R1,R2),p

32、ushthru(BOX1,D1,R2,R1)中间状态模型中间状态模型M1和和M2，即子目标，即子目标G1和和G2，M2与目标与目标世界模型世界模型G0相同。相同。因此，得到的最后规划为因此，得到的最后规划为OP1，OP2，即，即 gothru(D1，R1，R2)，pushthru(BOX1,D1,R2,R1)BOX1机器人箱子R1R2DBOX1机器人箱子R1R2D图图8.5中间目标状态的目标模型中间目标状态的目标模型（a）中间目标状态中间目标状态M1（b）中间目标状态中间目标状态M2图图8.6机器人规划例题的搜索图机器人规划例题的搜索图 模拟退火算法模拟退火算法来源于来源于固体固体退火原理，将

33、固体加温至充分高，再让其徐退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部徐冷却，加温时，固体内部粒子粒子随随温升温升变为无序状，内能增大，而变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态平衡态，最后在，最后在常温常温时达到基态，内能减为最小时达到基态，内能减为最小。该该 思思 想想 是是 由由N.Metropolis等等 人人 于于1953年年 提提 出出。1983年年,S.Kirkpatrick等等成成功功地地将将退退火火思思想想引引入入到到组组合合优优化化领领域域。它它是是基基于于Monte-Carlo迭迭代代

34、求求解解策策略略的的一一种种随随机机寻寻优优算算法法，其其出出发发点点是是基基于于物物理理中中固固体体物物质质的的退退火火过过程程与与一一般般组组合合优优化化问问题题之之间间的的相相似似性性。模模拟拟退退火火算算法法从从某某一一较较高高初初温温出出发发，伴伴随随温温度度参参数数的的不不断断下下降降,结结合合概概率率突突跳跳特特性性在在解解空空间间中中随随机机寻寻找找目目标标函函数数的的全全局局最最优优解解，即即在在局局部部最最优优解解能能概概率率性性地地跳跳出出并并最最终终趋趋于于全全局局最最优优。模模拟拟退退火火算算法法是是一一种种通通用用的的优优化化算算法法，理理论论上上算算法法具具有有概

35、概率率的的全全局局优优化化性性能能,目目前前已已在在工工程程中中得得到到了了广广泛泛应应用用，诸诸如如VLSI、生生产产调调度度、控控制制工工程程、机机器器学学习习、神神经经网网络络、信信号号处处理理等等领领域域。蚁群优化算法是模拟蚂蚁觅食的原理，设计出的一种群集智能算法。蚂蚁在觅食过程中能够在其经过的路径上留下一种称之为信息素的物质，并在觅食过程中能够感知这种物质的强度，并指导自己行动方向，它们总是朝着该物质强度高的方向移动，因此大量蚂蚁组成的集体觅食就表现为一种对信息素的正反馈现象。某一条路径越短，路径上经过的蚂蚁越多，其信息素遗留的也就越多，信息素的浓度也就越高，蚂蚁选择这条路径的几率也就越高，由此构成的正反馈过程，从而逐渐的逼近最优路径，找到最优路径。