《人工智能chapter3》由会员分享，可在线阅读，更多相关《人工智能chapter3（122页珍藏版）》请在金锄头文库上搜索。
1、第三章第三章搜索原理搜索原理上一章中我们研究了知识表示方法，为人工智能问题的求解打下了基础。上一章中我们研究了知识表示方法，为人工智能问题的求解打下了基础。从问题表示到问题的解决，有一个求解的过程。接下来要研究的是求解的从问题表示到问题的解决，有一个求解的过程。接下来要研究的是求解的过程，采用的基本方法包括搜索和推理。本章先介绍搜索技术，将要讨论过程，采用的基本方法包括搜索和推理。本章先介绍搜索技术，将要讨论问题求解的搜索原理，包括一些早期的搜索技术或用于解决比较简单问题问题求解的搜索原理，包括一些早期的搜索技术或用于解决比较简单问题的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理，包括
2、的搜索原理和一些比较新的能够求解比较复杂问题的搜索原理，包括A*算算法、遗传算法和模拟退火算法等。法、遗传算法和模拟退火算法等。1状态图的例子：设有三枚钱币，其排列处在“正，正，反”状态，现允许每次可翻动其中任意一个钱币，问只允许操作三次的情况下，如何翻动钱币使其变成“正，正，正”或“反，反，反”状态。若“正面”用“1”表示，“反面”用“0”表示，则问题化成求解从初始状态（1,1,0）到目标状态（1，1，1）或(0,0,0)的路径问题，且该路径的长度为3。（1，1，0）-（1，1，1）或（1,1,0）-(0,0,0)23八数码问题（8-puzzle problem）在一个3*3的方格棋盘上放置
3、着1，2，3，4，5，6，7，8八个数码，每个数码占一个格，且有一个空格。这些数码可在棋盘上移动，其移动规则是：与空格相邻的数码方可移入空格。现在的问题是对于给定的初始棋局和目标棋局（如下图），给出移动的序列。45 3.13.1盲目搜索盲目搜索盲目搜索盲目搜索 盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。(1)图搜索策略图搜索策略(2)宽度优先搜索宽度优先搜索(3)深度优先搜索深度优先搜索(4)等等代价搜索代价搜索6 图搜索策略图搜索策略7图的说明：一个图由节点的集合组成，节点之间由弧线连接。如果弧是图的说明：一个图由节点
4、的集合组成，节点之间由弧线连接。如果弧是有方向的话，则这种图称为有向图，否则称为无向图。在图搜索策有方向的话，则这种图称为有向图，否则称为无向图。在图搜索策略中，节点代表状态描述，弧代表操作。略中，节点代表状态描述，弧代表操作。图搜索图搜索(GRAPHSEARCH)的一般过程如下：的一般过程如下：(1)建立一个只含有起始节点建立一个只含有起始节点S的搜索图的搜索图G，把，把S放到一个叫做放到一个叫做OPEN的的未扩展节点表中（简称未扩展节点表中（简称OPEN表）。表）。(2)建立一个叫做建立一个叫做CLOSED的已扩展节点表（简称的已扩展节点表（简称CLOSED表），其表），其初始为空表。初始
5、为空表。(3)LOOP：若：若OPEN表是空表，则失败退出。表是空表，则失败退出。8(4)选择选择OPEN表上的第一个节点，把它从表上的第一个节点，把它从OPEN表移出并表移出并放进放进CLOSED表中。称此节点为节点表中。称此节点为节点n，它是它是CLOSED表表中节点的编号。中节点的编号。(5)若若n为一目标节点，则有解并成功退出，此解是追踪图为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从中沿着指针从n到到S这条路径而得到的这条路径而得到的(指针将在第指针将在第7步中步中设置设置)。(6)扩展节点扩展节点n，同时生成不是同时生成不是n的祖先的那些后继节点的的祖先的那些后继节点的
6、集合集合M。把。把M的这些成员作为的这些成员作为n的后继节点添入图的后继节点添入图G中。中。9(7)对那些未曾在对那些未曾在G中出现过的中出现过的(既未曾在既未曾在OPEN表上或表上或CLOSED表上出现过的表上出现过的)M成员设置一个通向成员设置一个通向n的指针。把的指针。把M的这些成员加进的这些成员加进OPEN表。对已经在表。对已经在OPEN或或CLOSED表上表上的每一个的每一个M成员，确定是否需要更改通到成员，确定是否需要更改通到n的指针方向。对的指针方向。对已在已在CLOSED表上的每个表上的每个M成员，确定是否需要更改图成员，确定是否需要更改图G中中通向它的每个后裔节点的指针方向。
7、通向它的每个后裔节点的指针方向。(8)按某一任意方式或按某个探试值，重排按某一任意方式或按某个探试值，重排OPEN表。表。(9)GOLOOP。10图搜索算法中的几个重要名词图搜索算法中的几个重要名词 3搜索图与搜索树搜索图与搜索树此过程生成一个明确的图G(称为搜索图)和一个G的子集T(称为搜索树)，树T上的每个节点也在图G中。搜索树是由第7步中设置的指针来确定的。G中的每个节点(除S外)都有一个只指向G中一个父辈节点的指针，该父辈节点就定为树中那个节点的唯一父辈节点。11一般搜索过程框图一般搜索过程框图12图搜索方法的几点分析：图搜索方法的几点分析：图搜索过程的第图搜索过程的第8步对步对OPE
8、N表上的节点进行排序，以便能够从表上的节点进行排序，以便能够从中选出一个中选出一个“最好最好”的节点作为第的节点作为第4步扩展用。这种排序可以是任意步扩展用。这种排序可以是任意的即盲目的的即盲目的(属于盲目搜索属于盲目搜索)，也可以用以后要讨论的各种启发思想，也可以用以后要讨论的各种启发思想或其它准则为依据或其它准则为依据(属于启发式搜索属于启发式搜索)。每当被选作扩展的节点为目。每当被选作扩展的节点为目标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点标节点时，这一过程就宣告成功结束。这时，能够重现从起始节点到目标节点的这条成功路径，其办法是从目标节点按指针向到目标节点的这条成功路径
9、，其办法是从目标节点按指针向S返回追返回追溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终溯。当搜索树不再剩有未被扩展的端节点时，过程就以失败告终(某某些节点最终可能没有后继节点，所以些节点最终可能没有后继节点，所以OPEN表可能最后变成空表表可能最后变成空表)。在失败终止的情况下，从起始节点出发，一定达不到目标节点。在失败终止的情况下，从起始节点出发，一定达不到目标节点。13 宽度优先搜索宽度优先搜索(breadth-firstsearch)的定义：的定义：如果搜索是以接近起始节点的程如果搜索是以接近起始节点的程度依次扩展节点的，那么这种搜索就叫做宽度优先搜索度依次扩展节点的，那么这
10、种搜索就叫做宽度优先搜索(breadth-firstsearch)。从图可见，这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必从图可见，这种搜索是逐层进行的；在对下一层的任一节点进行搜索之前，必须搜索完本层的所有节点。须搜索完本层的所有节点。宽度优先搜索宽度优先搜索宽度优先搜索宽度优先搜索 14宽度优先搜索算法宽度优先搜索算法如下：如下：(1)把起始节点放到把起始节点放到OPEN表中表中(如果该起始节点为一目标节点，则求得如果该起始节点为一目标节点，则求得一个解答一个解答)。(2)如果如果OPEN是个空表，则没有解，失败退出；否则继续。是个空表，则没有解，失败退出；否则继续。(3)把
11、第一个节点把第一个节点(节点节点n)从从OPEN表移出，并把它放入表移出，并把它放入CLOSED扩展扩展节点表中。节点表中。(4)扩展节点扩展节点n。如果没有后继节点，则转向上述第如果没有后继节点，则转向上述第(2)步。步。(5)把把n的所有后继节点放到的所有后继节点放到OPEN表的末端，并提供从这些后继节点表的末端，并提供从这些后继节点回到回到n的指针。的指针。(6)如果如果n的任一个后继节点是个目标节点，则找到一个解答，成功退的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第出；否则转向第(2)步。步。1516宽度优先搜索方法分析：宽度优先搜索方法分析：宽度优先搜索是图搜索
12、一般过程的特殊情况，将图搜索一般过程中的第宽度优先搜索是图搜索一般过程的特殊情况，将图搜索一般过程中的第8步具体化为本算法中的第步具体化为本算法中的第6步，这实际是将步，这实际是将OPEN表作为表作为“先进先出先进先出”的队列进行操作。的队列进行操作。宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途宽度优先搜索方法能够保证在搜索树中找到一条通向目标节点的最短途径；这棵搜索树提供了所有存在的路径径；这棵搜索树提供了所有存在的路径(如果没有路径存在，那么对有如果没有路径存在，那么对有限图来说，我们就说该法失败退出；对于无限图来说，则永远不会终止限图来说，我们就说该法失败退出；对于无限
13、图来说，则永远不会终止)。例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就例：把宽度优先搜索应用于八数码难题时所生成的搜索树，这个问题就是要把初始棋局变为如下目标棋局的问题：是要把初始棋局变为如下目标棋局的问题：171819通过该算法及通过该算法及open和和closed表的变化过程可知，表的变化过程可知，open表的数据结构是一个队列表的数据结构是一个队列（queue），），closed表是一个顺序表表是一个顺序表(sequencelist)，保存了搜索路径。保存了搜索路径。该算法是完备的，即问题有解的话，则一定能找到解，且是最优解（路径最短），该算法是完备的，即问题有解的话，
14、则一定能找到解，且是最优解（路径最短），这是优点，缺点是搜索效率低。这是优点，缺点是搜索效率低。20 深度优先搜索深度优先搜索另一种盲目另一种盲目(无信息无信息)搜索叫做搜索叫做深度优先搜索深度优先搜索(depth-firstsearch)。下图是下图是一个深度优先搜索示意图。一个深度优先搜索示意图。分析深度优先搜索示意图可看出，在深度优先搜索中，我们首先扩展最新产分析深度优先搜索示意图可看出，在深度优先搜索中，我们首先扩展最新产生的生的(即最深的即最深的)节点。深度相等的节点可以任意排列。节点。深度相等的节点可以任意排列。21定义节点的深度如下：定义节点的深度如下：(1)起始节点起始节点(即
15、根节点即根节点)的深度为的深度为0。(2)任何其它节点的深度等于其父辈节点深度加上任何其它节点的深度等于其父辈节点深度加上1。对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某对于许多问题，其状态空间搜索树的深度可能为无限深，或者可能至少要比某个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径个可接受的解答序列的已知深度上限还要深。为了避免考虑太长的路径(防止搜防止搜索过程沿着无益的路径扩展下去索过程沿着无益的路径扩展下去)，往往给出一个节点扩展的最大深度，往往给出一个节点扩展的最大深度深度深度界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。
16、界限。任何节点如果达到了深度界限，那么都将把它们作为没有后继节点处理。值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一定就是值得说明的是，即使应用了深度界限的规定，所求得的解答路径并不一定就是最短的路径。最短的路径。22有深度界限的深度优先搜索算法如下：有深度界限的深度优先搜索算法如下：(1)把起始节点把起始节点S放到未扩展节点放到未扩展节点OPEN表中。如果此节点为一目标节点，则得表中。如果此节点为一目标节点，则得到一个解。到一个解。(2)如果如果OPEN为一空表，则失败退出。为一空表，则失败退出。(3)把第一个节点把第一个节点(节点节点n)从从OPEN表移到表移到CLOSED
17、表。表。(4)如果节点如果节点n的深度等于最大深度，则转向的深度等于最大深度，则转向(2)。(5)扩展节点扩展节点n，产生其全部后裔，并把它们放入产生其全部后裔，并把它们放入OPEN表的前头。如果没有后表的前头。如果没有后裔，则转向裔，则转向(2)。(6)如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，如果后继节点中有任一个为目标节点，则求得一个解，成功退出；否则，转向转向(2)。2324通过分析可知通过分析可知open表的数据结构是一个堆栈表的数据结构是一个堆栈(stack),这是与广度优先搜索的唯这是与广度优先搜索的唯一区别，也就是说扩展生成的结点总是加入到栈顶，扩展时总是
18、选择最新生成一区别，也就是说扩展生成的结点总是加入到栈顶，扩展时总是选择最新生成的结点。的结点。特点：可能误入歧途找不到解，不是完备的，得到的解不一定是最优解（最短特点：可能误入歧途找不到解，不是完备的，得到的解不一定是最优解（最短路径）。路径）。25 等代价搜索等代价搜索有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性有些问题并不要求有应用算符序列为最少的解，而是要求具有某些特性的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小的解。搜索树中每条连接弧线上的有关代价以及随之而求得的具有最小代价的解答路径，与许多这样的广义准则相符合。宽度优先搜索可被推代价的解答路径，
19、与许多这样的广义准则相符合。宽度优先搜索可被推广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，广用来解决这种寻找从起始状态至目标状态的具有最小代价的路径问题，这种推广了的宽度优先搜索算法叫做等代价搜索算法这种推广了的宽度优先搜索算法叫做等代价搜索算法。26等代价搜索算法：等代价搜索算法：等代价搜索方法以等代价搜索方法以g(i)的递增顺序扩展其节点，其算法如下：的递增顺序扩展其节点，其算法如下：(1)把起始节点把起始节点S放到未扩展节点表放到未扩展节点表OPEN中。如果此起始节点为一目标节点，则求中。如果此起始节点为一目标节点，则求得一个解得一个解;否则令否则令g(S)=0。(2
20、)如果如果OPEN是个空表，则没有解而失败退出。是个空表，则没有解而失败退出。(3)从从OPEN表中选择一个节点表中选择一个节点i，使其使其g(i)为最小。如果有几个节点都合格，那么就为最小。如果有几个节点都合格，那么就要选择一个目标节点作为节点要选择一个目标节点作为节点i(要是有目标节点的话要是有目标节点的话)；否则，就从中选一个作为节点；否则，就从中选一个作为节点i。把节点把节点i从从OPEN表移至扩展节点表表移至扩展节点表CLOSED中。中。(4)如果节点如果节点i为目标节点，则求得一个解。为目标节点，则求得一个解。(5)扩展节点扩展节点i。如果没有后继节点，则转向第如果没有后继节点，则
21、转向第(2)步。步。(6)对于节点对于节点i的每个后继节点的每个后继节点j，计算计算g(j)=g(i)+c(i,j)，并把所有后继节点并把所有后继节点j放进放进OPEN表。提供回到节点表。提供回到节点i的指针。的指针。(7)转向第转向第(2)步。步。27283.23.2启发式搜索启发式搜索启发式搜索启发式搜索盲目搜索的不足：效率低，耗费过多的计算空间与时间。盲目搜索的不足：效率低，耗费过多的计算空间与时间。分析前面介绍的宽度优先、深度优先搜索，或等代价搜索算法分析前面介绍的宽度优先、深度优先搜索，或等代价搜索算法,其主要其主要的差别是的差别是OPEN表中待扩展节点的顺序问题。人们就试图找到一种
22、方法表中待扩展节点的顺序问题。人们就试图找到一种方法用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，用于排列待扩展节点的顺序，即选择最有希望的节点加以扩展，那么，搜索效率将会大为提高。搜索效率将会大为提高。启发信息：进行搜索技术一般需要某些有关具体问题领域的特性的信息，启发信息：进行搜索技术一般需要某些有关具体问题领域的特性的信息，把此种信息叫做启发信息。把此种信息叫做启发信息。把利用启发信息的搜索方法叫做启发性搜索方法。把利用启发信息的搜索方法叫做启发性搜索方法。29假设初始状态、算符和目标状态的定义都是完全确定的，然后决定一个假设初始状态、算符和目标状态的定义都是完全确定的，
23、然后决定一个搜索空间。因此，问题就在于如何有效地搜索这个给定空间。搜索空间。因此，问题就在于如何有效地搜索这个给定空间。启发信息按其用途可分为下列启发信息按其用途可分为下列3种：种：(1)用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索用于决定要扩展的下一个节点，以免像在宽度优先或深度优先搜索中那样盲目地扩展。中那样盲目地扩展。(2)在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节在扩展一个节点的过程中，用于决定要生成哪一个或哪几个后继节点，以免盲目地同时生成所有可能的节点。点，以免盲目地同时生成所有可能的节点。(3)用于决定某些应该从搜索树中抛弃或修剪的节点。用于决定某些
24、应该从搜索树中抛弃或修剪的节点。在本节中，我们只讨论利用上述第一种启发信息的状态空间搜索算法，在本节中，我们只讨论利用上述第一种启发信息的状态空间搜索算法，即决定哪个是下一步要扩展的节点。这种搜索总是选择即决定哪个是下一步要扩展的节点。这种搜索总是选择“最有希望最有希望”的的节点作为下一个被扩展的节点。这种搜索叫做有序搜索节点作为下一个被扩展的节点。这种搜索叫做有序搜索(orderedsearch)。 启发式搜索策略启发式搜索策略 30用来估算节点希望程度的量度，叫做估价函数用来估算节点希望程度的量度，叫做估价函数(evaluationfunction)。一个节点的一个节点的希望希望(prom
25、ise)有几种不同的定义方法。在状态空间问题有几种不同的定义方法。在状态空间问题中，一种方法是估算目标节点到此节点的距离；另一种方法认为，解答中，一种方法是估算目标节点到此节点的距离；另一种方法认为，解答路径包括被估价过的节点，并计算全条路径的长度或难度。每个不同的路径包括被估价过的节点，并计算全条路径的长度或难度。每个不同的衡量标准只能考虑该问题中这个节点的某些决定性特性，或者对给定节衡量标准只能考虑该问题中这个节点的某些决定性特性，或者对给定节点与目标节点进行比较，以决定相关特性。点与目标节点进行比较，以决定相关特性。我们用符号我们用符号f来标记估价函数，用来标记估价函数，用f(n)表示节
26、点表示节点n的估价函数值。暂时令的估价函数值。暂时令f为任意函数，以后我们将会提出为任意函数，以后我们将会提出f是从起始节点约束地通过节点是从起始节点约束地通过节点n而到达而到达目标节点的最小代价路径上的一个估算代价。目标节点的最小代价路径上的一个估算代价。 估价函数估价函数 31我们用估价函数我们用估价函数f来排列来排列GRAPHSEARCH第第8步中步中OPEN表上的节点。根据习惯，表上的节点。根据习惯，OPEN表上的节点按照它们表上的节点按照它们f函数值的递增顺序排列。根据推测，某个具有低的估价值的节点较函数值的递增顺序排列。根据推测，某个具有低的估价值的节点较有可能处在最佳路径上。应用
27、某个算法有可能处在最佳路径上。应用某个算法(例如等代价算法例如等代价算法)选择选择OPEN表上具有最小表上具有最小f值的值的节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索或最佳优先搜索，而其算法节点作为下一个要扩展的节点。这种搜索方法叫做有序搜索或最佳优先搜索，而其算法就叫做有序搜索算法或最佳优先算法。可见它总是选择最有希望的节点作为下一个要扩就叫做有序搜索算法或最佳优先算法。可见它总是选择最有希望的节点作为下一个要扩展的节点。有序搜索展的节点。有序搜索(orderedsearch)又称为最好优先搜索又称为最好优先搜索(best-firstsearch)。 有序搜索有序搜索有序状态空间搜
28、索算法如下：有序状态空间搜索算法如下：(1)把起始节点把起始节点S放到放到OPEN表中，计算表中，计算f(S)并把其值与节点并把其值与节点S联系起来。联系起来。(2)如果如果OPEN是个空表，则失败退出，无解。是个空表，则失败退出，无解。(3)从从OPEN表中选择一个表中选择一个f值最小的节点值最小的节点i。结果有几个节点合格，当其中有一个为目标结果有几个节点合格，当其中有一个为目标节点时，则选择此目标节点，否则就选择其中任一个节点作为节点节点时，则选择此目标节点，否则就选择其中任一个节点作为节点i。(4)把节点把节点i从从OPEN表中移出，并把它放入表中移出，并把它放入CLOSED的扩展节点
29、表中。的扩展节点表中。(5)如果如果i是个目标节点，则成功退出，求得一个解。是个目标节点，则成功退出，求得一个解。32(6)扩展节点扩展节点i，生成其全部后继节点。对于生成其全部后继节点。对于i的每一个后继节点的每一个后继节点j：(a)计算计算f(j)。(b)如果如果j既不在既不在OPEN表中，又不在表中，又不在CLOSED表中，则用估价函数表中，则用估价函数f把它添入把它添入OPEN表。表。从从j加一指向其父辈节点加一指向其父辈节点i的指针，以便一旦找到目标节点时记住一个解答路径。的指针，以便一旦找到目标节点时记住一个解答路径。(c)如如果果j已在已在OPEN表上或表上或CLOSED表上，则
30、比较刚刚对表上，则比较刚刚对j计算过的计算过的f值和前面计算过的该值和前面计算过的该节点在表中的节点在表中的f值。如果新的值。如果新的f值较小，则值较小，则(i)以此新值取代旧值。以此新值取代旧值。(ii)从从j指向指向i，而不是指向它的父辈节点。而不是指向它的父辈节点。(iii)如果节点如果节点j在在CLOSED表中，则把它移回表中，则把它移回OPEN表表(7)转向转向(2)，即，即GOTO(2)。宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先宽度优先搜索、等代价搜索和深度优先搜索统统是有序搜索技术的特例。对于宽度优先搜索，我们选择搜索，我们选择f(i)作为节点
31、作为节点i的深度。对于等代价搜索，的深度。对于等代价搜索，f(i)是从起始节点至节点是从起始节点至节点i这段路这段路径的代价。径的代价。有序搜索的有效性直接取决于有序搜索的有效性直接取决于f的选择，如果选择的的选择，如果选择的f不合适，有序搜索就可能失去一个最不合适，有序搜索就可能失去一个最好的解甚至全部的解。如果没有适用的准确的希望量度，那么好的解甚至全部的解。如果没有适用的准确的希望量度，那么f的选择将涉及两个方面的的选择将涉及两个方面的内容：一方面是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任内容：一方面是一个时间和空间之间的折衷方案；另一方面是保证有一个最优的解或任意
32、解。意解。333435 A*算法算法 A*算法的估价函数：算法的估价函数：让我们描述一个特别的估价函数，这个估价函数让我们描述一个特别的估价函数，这个估价函数f使得在任意节点上其函数值使得在任意节点上其函数值f(n)能估算出从节点能估算出从节点S到节点到节点n的最小代价路径的代价与从节点的最小代价路径的代价与从节点n到某一目标节点到某一目标节点的最小代价路径的代价之总和，也就是说的最小代价路径的代价之总和，也就是说f(n)是约束通过节点是约束通过节点n的一条最小代价的一条最小代价路径的代价的一个估计。因此，路径的代价的一个估计。因此，OPEN表上具有最小表上具有最小f值的那个节点就是所估计值的
33、那个节点就是所估计的加有最少严格约束条件的节点，而且下一步要扩展这个节点是合适的。的加有最少严格约束条件的节点，而且下一步要扩展这个节点是合适的。36在正式讨论在正式讨论A*算法之前，我们先介绍几个有用的记号。令算法之前，我们先介绍几个有用的记号。令k(ni，nj)表示表示任意两个节点任意两个节点ni和和nj之间最小代价路径的实际代价之间最小代价路径的实际代价(对于两节点间没有通对于两节点间没有通路的节点，函数路的节点，函数k没有定义没有定义)。于是，从节点。于是，从节点n到某个具体的目标节点到某个具体的目标节点ti，某一条最小代价路径的代价可由某一条最小代价路径的代价可由k(n,ti)给出。
34、我们令给出。我们令h*(n)表示整个表示整个目标节点集合目标节点集合ti上所有上所有k(n,ti)中最小的一个，因此，中最小的一个，因此，h*(n)就是从就是从n到目标节点最小代价路径的代价，而且从到目标节点最小代价路径的代价，而且从n到目标节点能够获得到目标节点能够获得h*(n)的的任一路径就是一条从任一路径就是一条从n到某个目标节点的最佳路径到某个目标节点的最佳路径(对于任何不能到达对于任何不能到达目标节点的节点目标节点的节点n，函数函数h*没有定义没有定义)。37通常我们感兴趣的是想知道从已知起始节点通常我们感兴趣的是想知道从已知起始节点S到任意节点到任意节点n的一条最佳路径的代的一条最
35、佳路径的代价价k(S,n)。为此，引进一个新函数为此，引进一个新函数g*，这将使我们的记号得到某些简化。对所这将使我们的记号得到某些简化。对所有从有从S开始可达到开始可达到n的路径来说，的路径来说，函数函数g*定义为定义为g*(n)=k(S,n)。其次，我们定义其次，我们定义函数函数f*，使得在任一节点使得在任一节点n上其函数值上其函数值f*(n)就是从节点就是从节点S到节点到节点n的一条最佳路的一条最佳路径的实际代价加上从节点径的实际代价加上从节点n到某目标节点的一条最佳路径的代价之和，即到某目标节点的一条最佳路径的代价之和，即f*(n)=g*(n)+h*(n)因而因而f*(n)值就是从值就
36、是从S开始约束通过节点开始约束通过节点n的一条最佳路径的的一条最佳路径的代价，而代价，而f*(S)=h*(S)是一条从是一条从S到某个目标节点中间无约束的一条最佳路径的到某个目标节点中间无约束的一条最佳路径的代价。代价。我们希望估价函数我们希望估价函数f是是f*的一个估计，此估计可由下式给出：的一个估计，此估计可由下式给出：f(n)=g(n)+h(n)。其中：其中：g是是g*的估计；的估计；h是是h*的估计。对于的估计。对于g(n)来说，一个明显的选择就是搜索来说，一个明显的选择就是搜索树中从树中从S到到n这段路径的代价，这一代价可以由从这段路径的代价，这一代价可以由从n到到S寻找指针时，把所
37、遇到寻找指针时，把所遇到的各段弧线的代价加起来给出的各段弧线的代价加起来给出(这条路径就是到目前为止用搜索算法找到的从这条路径就是到目前为止用搜索算法找到的从S到到n的最小代价路径的最小代价路径)。这个定义包含了。这个定义包含了g(n)g*(n)。对于对于h*(n)的估计的估计h(n)，它它依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数依赖于有关问题的领域的启发信息。这种信息可能与八数码难题中的函数W(n)所用的那种信息相似。我们把所用的那种信息相似。我们把h叫做启发函数。叫做启发函数。38定义定义1:在在GRAPHSEARCH过程中，如果第过程中，如果第8步的重排步的重排O
38、PEN表是依据表是依据f(x)=g(x)+h(x)进行的，则称该过程为进行的，则称该过程为A算法。算法。定义定义2:在在A算法中，如果对所有的算法中，如果对所有的x，h(x)h*(x)成立成立,则称则称h(x)为为h*(x)的下界，的下界，它表示某种偏于保守的估计。它表示某种偏于保守的估计。定义定义3:采用采用h*(x)的下界的下界h(x)为启发函数的为启发函数的A算法，称为算法，称为A*算法。当算法。当h=0时，时，A*算法就变为有序搜索算法。算法就变为有序搜索算法。A*算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一般算法是一种有序搜索算法，其特点在于对估价函数的定义上。对于一
39、般的有序搜索，总是选择的有序搜索，总是选择f值最小的节点作为扩展节点。因此，值最小的节点作为扩展节点。因此，f是根据需要找到是根据需要找到一条最小代价路径的观点来估算节点的，所以，可考虑每个节点一条最小代价路径的观点来估算节点的，所以，可考虑每个节点n的估价函数的估价函数值为两个分量：从起始节点到节点值为两个分量：从起始节点到节点n的代价以及从节点的代价以及从节点n到达目标节点的代价。到达目标节点的代价。A算法和算法和A*算法的定义算法的定义394041 双向搜索双向搜索 搜索过程的目的是发现一条通过问题空间从初始状态到达目标状态的路径，这搜索过程的目的是发现一条通过问题空间从初始状态到达目标
40、状态的路径，这种搜索可以向两个方向进行：种搜索可以向两个方向进行：（1）从初始状态开始的正向搜索；（）从初始状态开始的正向搜索；（2）从目标）从目标状态开始的逆向搜索。状态开始的逆向搜索。把搜索过程描述为一套规则的应用，就比较容易描述专用的搜索算法而不涉及把搜索过程描述为一套规则的应用，就比较容易描述专用的搜索算法而不涉及搜索方向。另外一种可能性是同时从初始状态正向搜索及从目标状态逆向搜索，搜索方向。另外一种可能性是同时从初始状态正向搜索及从目标状态逆向搜索，直到这两条路径在中途某处相交接为止。这种搜索策略叫做双向搜索。直到这两条路径在中途某处相交接为止。这种搜索策略叫做双向搜索。423.3遗
41、传算法遗传算法一一、遗传算法概述、遗传算法概述 二、遗传算法原理二、遗传算法原理三、遗传算法的应用三、遗传算法的应用43一、遗传算法概述一、遗传算法概述1、智能优化算法 2、基本遗传算法 3、遗传算法的特点 441 1、智能优化算法、智能优化算法 智能优化算法又称为现代启发式算法，是一种具有全局优化性能、通用性强、且适合于并行处理的算法。这种算法一般具有严密的理论依据，而不是单纯凭借专家经验，理论上可以在一定的时间内找到最优解或近似最优解。 45常用的智能优化算法 （1）遗传算法 （Genetic Algorithm， 简称GA） （2）模拟退火算法（Simulated Annealing，
42、简称SA） （3）禁忌搜索算法（Tabu Search， 简称TS） 46智能优化算法的特点它们的共同特点：都是从任一解出发，按照某种机制，以一定的概率在整个求解空间中探索最优解。由于它们可以把搜索空间扩展到整个问题空间，因而具有全局优化性能。47遗传算法起源 遗传算法是由美国的J. Holland教授于1975年在他的专著自然界和人工系统的适应性中首先提出的，它是一类借鉴生物界自然选择和自然遗传机制的随机化搜索算法 。 48遗传算法的搜索机制 遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象，在每次迭代中都保留一组候选解，并按某种指标从解群中选取较优的个体，利用遗传算子(选
43、择、交叉和变异)对这些个体进行组合，产生新一代的候选解群，重复此过程，直到满足某种收敛指标为止。 492 2、基本遗传算法、基本遗传算法基本遗传算法（Simple Genetic Algorithms，简称SGA，又称简单遗传算法或标准遗传算法），是由Goldberg总结出的一种最基本的遗传算法，其遗传进化操作过程简单，容易理解，是其它一些遗传算法的雏形和基础。 50基本遗传算法的组成 （1）编码（产生初始种群）（2）适应度函数（3）遗传算子（选择、交叉、变异）（4）运行参数51(1)(1)编码编码 GA是通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串。正如研究生物遗传是从染色体着手
44、，而染色体则是由基因排成的串。SGA使用二进制串进行编码。 52几个术语 基因型：101000111 表现型：0.63编码解码个体（染色体）基因53初始种群 SGA采用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。 54(2)适应度函数适应度函数 遗传算法对一个个体（解）的好坏用适应度函数值来评价，适应度函数值越大，解的质量越好。适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的唯一标准，它的设计应结合求解问题本身的要求而定。 55选择算子遗传算法使用选择运算来实现对群体中的个体进行优胜劣汰操作：适应度高的个体被遗传到下一代群体中的概率大；适应度低的
45、个体，被遗传到下一代群体中的概率小。选择操作的任务就是按某种方法从父代群体中选取一些个体，遗传到下一代群体。SGA中选择算子采用轮盘赌选择方法。 (3)遗传遗传算子算子56轮盘赌选择方法 轮盘赌选择又称比例选择算子，它的基本思想是：各个个体被选中的概率与其适应度函数值大小成正比。设群体大小为n ，个体i 的适应度为 Fi，则个体i 被选中遗传到下一代群体的概率为： 57轮盘赌选择方法的实现步骤（1） 计算群体中所有个体的适应度函数值（需要解码）；（2） 利用比例选择算子的公式，计算每个个体被选中遗传到下一代群体的概率；（3） 采用模拟赌盘操作（即生成0到1之间的随机数与每个个体遗传到下一代群体
46、的概率进行匹配）来确定各个个体是否遗传到下一代群体中。58交叉算子 所谓交叉运算，是指对两个相互配对的染色体依据交叉概率 Pc 按某种方式相互交换其部分基因，从而形成两个新的个体。交叉运算是遗传算法区别于其他进化算法的重要特征，它在遗传算法中起关键作用，是产生新个体的主要方法。 SGA中交叉算子采用单点交叉算子。 59单点交叉运算 交叉前：00000|0111000000001000011100|00000111111000101交叉后：00000 |0000011111100010111100 |01110000000010000交叉点交叉点60变异算子 所谓变异运算，是指依据变异概率 Pm
47、 将个体编码串中的某些基因值用其它基因值来替换，从而形成一个新的个体。遗传算法中的变异运算是产生新个体的辅助方法，它决定了遗传算法的局部搜索能力，同时保持种群的多样性。交叉运算和变异运算的相互配合，共同完成对搜索空间的全局搜索和局部搜索。 SGA中变异算子采用基本位变异算子。 61基本位变异算子 基本位变异算子是指对个体编码串随机指定的某一位或某几位基因作变异运算。对于基本遗传算法中用二进制编码符号串所表示的个体，若需要进行变异操作的某一基因座上的原有基因值为0，则变异操作将其变为1；反之，若原有基因值为1，则变异操作将其变为0 。 62基本位变异算子的执行过程 变异前：00000111000
48、0000010000变异后：000001110001000010000变异点变异点63(4)运行参数运行参数 （1）M ： 种群规模 （2）T ： 遗传运算的终止进化代数 （3）Pc ： 交叉概率 （4）Pm ： 变异概率 64SGA的框图 产生初始群体产生初始群体是否满足停止准则是否满足停止准则是是输出结果并结束输出结果并结束计算个体适应度值计算个体适应度值比例选择运算比例选择运算单点交叉运算单点交叉运算基本位变异运算基本位变异运算否否产生新一代群体产生新一代群体执行执行M/2M/2次次653、遗传算法的特点、遗传算法的特点 （1）群体搜索，易于并行化处理； （2）不是盲目穷举，而是启发式搜
49、索；（3）适应度函数不受连续、可微等条件的约束，适用范围很广。66二、遗传算法原理二、遗传算法原理1、遗传算法的数学基础 2、遗传算法的收敛性分析 3、遗传算法的改进 671 1、遗传算法的数学基础遗传算法的数学基础（1）模式定理 （2）积木块假设 68模式模式是指种群个体基因串中的相似样板，它用来描述基因串中某些特征位相同的结构。在二进制编码中，模式是基于三个字符集(0,1,*)的字符串，符号*代表任意字符，即 0 或者 1。 模式示例：10*169两个定义定义1：模式 H 中确定位置的个数称为模式 H 的阶，记作O(H)。例如O(10*1)=3 。定义2：模式 H 中第一个确定位置和最后一
50、个确定位置之间的距离称为模式 H 的定义距，记作(H)。例如(10*1)=4 。 70模式的阶和定义距的含义模式阶用来反映不同模式间确定性的差异，模式阶数越高，模式的确定性就越高，所匹配的样本数就越少。在遗传操作中，即使阶数相同的模式，也会有不同的性质，而模式的定义距就反映了这种性质的差异。 71模式定理模式定理：具有低阶、短定义距以及平均适应度高于种群平均适应度的模式在子代中呈指数增长。模式定理保证了较优的模式（遗传算法的较优解）的数目呈指数增长，为解释遗传算法机理提供了数学基础。 72模式定理从模式定理可看出，有高平均适应度、短定义距、低阶的模式，在连续的后代里获得至少以指数增长的串数目，
51、这主要是因为选择使最好的模式有更多的复制，交叉算子不容易破坏高频率出现的、短定义长的模式，而一般突变概率又相当小，因而它对这些重要的模式几乎没有影响。 73积木块假设 积木块假设：遗传算法通过短定义距、低阶以及高平均适应度的模式（积木块），在遗传操作下相互结合，最终接近全局最优解。 模式定理保证了较优模式的样本数呈指数增长，从而使遗传算法找到全局最优解的可能性存在；而积木块假设则指出了在遗传算子的作用下，能生成全局最优解。 742 2、遗传算法的收敛性分析遗传算法的收敛性分析遗传算法要实现全局收敛，首先要求任意初始种群经有限步都能到达全局最优解，其次算法必须由保优操作来防止最优解的遗失。与算法
52、收敛性有关的因素主要包括种群规模、选择操作、交叉概率和变异概率。 75种群规模对收敛性的影响通常，种群太小则不能提供足够的采样点，以致算法性能很差；种群太大，尽管可以增加优化信息，阻止早熟收敛的发生，但无疑会增加计算量，造成收敛时间太长，表现为收敛速度缓慢。76选择操作对收敛性的影响选择操作使高适应度个体能够以更大的概率生存，从而提高了遗传算法的全局收敛性。如果在算法中采用最优保存策略，即将父代群体中最佳个体保留下来，不参加交叉和变异操作，使之直接进入下一代，最终可使遗传算法以概率1收敛于全局最优解。77交叉概率对收敛性的影响交叉操作用于个体对，产生新的个体，实质上是在解空间中进行有效搜索。交
53、叉概率太大时，种群中个体更新很快，会造成高适应度值的个体很快被破坏掉；概率太小时，交叉操作很少进行，从而会使搜索停滞不前，造成算法的不收敛。 78变异概率对收敛性的影响变异操作是对种群模式的扰动，有利于增加种群的多样性 。但是，变异概率太小则很难产生新模式，变异概率太大则会使遗传算法成为随机搜索算法。 79遗传算法的本质 遗传算法本质上是对染色体模式所进行的一系列运算，即通过选择算子将当前种群中的优良模式遗传到下一代种群中，利用交叉算子进行模式重组，利用变异算子进行模式突变。通过这些遗传操作，模式逐步向较好的方向进化，最终得到问题的最优解。 803 3、遗传算法的改进遗传算法的改进遗传欺骗问题
54、：在遗传算法进化过程中，有时会产生一些超常的个体，这些个体因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解。 81遗传算法的改进途径（1）对编码方式的改进 （2）对遗传算子 的改进（3）对控制参数的改进 （4）对执行策略的改进 82对编码方式的改进二进制编码优点在于编码、解码操作简单，交叉、变异等操作便于实现，缺点在于精度要求较高时，个体编码串较长，使算法的搜索空间急剧扩大，遗传算法的性能降低。格雷编码克服了二进制编码的不连续问题 ，浮点数编码改善了遗传算法的计算复杂性 。 83对遗传算子 的改进排序选择 均匀交叉 逆序变异（1 1） 对群体中的所有个
55、体对群体中的所有个体按其适应度大小进行降序排按其适应度大小进行降序排序；序；（2 2） 根据具体求解问题，根据具体求解问题，设计一个概率分配表，将各设计一个概率分配表，将各个概率值按上述排列次序分个概率值按上述排列次序分配给各个个体；配给各个个体；（3 3） 以各个个体所分配到以各个个体所分配到的概率值作为其遗传到下一的概率值作为其遗传到下一代的概率，基于这些概率用代的概率，基于这些概率用赌盘选择法来产生下一代群赌盘选择法来产生下一代群体。体。 84对遗传算子 的改进排序选择 均匀交叉 逆序变异（1 1） 随机产生一个与个体随机产生一个与个体编码长度相同的二进制屏蔽编码长度相同的二进制屏蔽字字
56、P = WP = W1 1W W2 2W Wn n ；（2 2） 按下列规则从按下列规则从A A、B B两两个父代个体中产生两个新个个父代个体中产生两个新个体体X X、Y Y：若：若W Wi i = 0 = 0，则，则X X的第的第i i个基因继承个基因继承A A的对应基因，的对应基因，Y Y的第的第i i个基因继承个基因继承B B的对应基的对应基因；若因；若W Wi i = 1 = 1，则，则A A、B B的第的第i i个基因相互交换，从而生成个基因相互交换，从而生成X X、Y Y的第的第i i个基因。个基因。 85对遗传算子 的改进排序选择 均匀交叉 逆序变异变异前：变异前：3 4 8 |
57、 7 9 6 5 | 2 13 4 8 | 7 9 6 5 | 2 1变异前：变异前：3 4 8 | 5 6 9 7 | 2 13 4 8 | 5 6 9 7 | 2 186对控制参数的改进 Schaffer建议的最优参数范围是： M = 20-100， T = 100-500， Pc = 0.4-0.9， Pm = 0.001-0.01。87对控制参数的改进Srinvivas等人提出自适应遗传算法，即PC和Pm能够随适应度自动改变，当种群的各个个体适应度趋于一致或趋于局部最优时，使二者增加，而当种群适应度比较分散时，使二者减小，同时对适应值高于群体平均适应值的个体，采用较低的PC和Pm，使性
58、能优良的个体进入下一代，而低于平均适应值的个体，采用较高的PC和Pm，使性能较差的个体被淘汰 。88对执行策略的改进混合遗传算法免疫遗传算法小生境遗传算法单亲遗传算法并行遗传算法89三、遗传算法的应用三、遗传算法的应用1、遗传算法的应用领域 2、遗传算法的应用示例 901 1、遗传算法的应用领域遗传算法的应用领域（1）组合优化 （2）函数优化 （3）自动控制 （4）生产调度 （5）图像处理 （6）机器学习 （7）人工生命 （8）数据挖掘 91遗传算法应用于组合优化随着问题规模的增大，组合优化问题的搜索空间也急剧扩大，有时在计算机上用枚举法很难甚至不可能求出其最优解。实践证明，遗传算法已经在求解
59、旅行商问题、背包问题、装箱问题、布局优化、网络路由等具有NP难度的组合优化问题上取得了成功的应用。 922 2、遗传算法的应用示例遗传算法的应用示例弹药装载问题弹药装载问题（Ammunition Loading Problem，简称ALP），就是在满足各类通用弹药运输规程和安全性的前提下，如何将一批通用弹药箱装入军用运输工具，使得通用弹药的装载效率达到最大值的问题。应用应用193AGSAA的基本原理在弹药装载中，考虑到模拟退火算法的基本思想是跳出局部最优解，将模拟退火思想引入遗传算法，应用改进型遗传算法和模拟退火算法相结合，构建自适应遗传模拟退火算法（AGSAA），从而综合了全局优化和局部搜索
60、的特点，为解决弹药装载这一组合优化问题提供了新的思路。94AGSAA的编码方式AGSAA采用二进制编码方式，每一个二进制位对应一个待装弹药箱，若为，表示该弹药箱装入运输工具，为则不装。95AGSAA的解码和适应度函数AGSAA采用弹药装载的启发式算法来解码，解码后最终确定装入运输工具的弹药箱。适应度函数主要考虑两个方面，即载重率和积载率，对这两个因素加权，来计算适应度函数值。96弹药装载的启发式算法（1）定位规则（Locating rule）定位规则是指用来确定当前待装弹药箱在运输工具剩余装载空间中摆放位置的规则。（2）定序规则（Ordering rule）定序规则是指用来确定弹药箱放入运输工
61、具装载空间先后顺序的规则。97遗传算子的选择AGSAA的选择算子采用轮盘赌选择算子，并结合最优保存策略；变异算子采用基本位变异算子；同时，在变异运算之后，增加退火算子，以增强算法的局部搜索能力；交叉概率和变异概率为自适应概率，以提高种群的进化效率。98交叉算子的选择由于AGSAA是采用将弹药箱的编号排列成串来进行编码的，如果个体交叉采用传统方式进行，就有可能使个体的编码产生重复基因（即一个弹药箱编号在一个个体中出现两次以上），从而产生不符合条件的个体，因此，AGSAA采用的是部分映射交叉算子。 99例例1.设设f(x)=-x2+2x +0.5，求求maxf(x),x -1,2。应用应用2我们将
62、通过这个简单的求最值问题来详细给出遗传算法的整个过程。（1）编码和产生初始群体）编码和产生初始群体u 首先需要确定编码的策略，也就是说如何把 -1,2 区间内的数用计算机语言表示出来。编码就是从表现型到基因型的映射，编码时要注意以下三个原则：n 完备性：问题空间中所有点（潜在解）都能成为GA编码空间中的点（染色体位串）的表现型；n 健全性：GA编码空间中的染色体位串必须对应问题空间中的某一潜在解；n 非冗余性：染色体和潜在解必须一一对应100编码u 我们采用二进制形式来解决编码问题，即将某个变量值代表的个体表示为一个0, 1二进制串。串的长度取决于求解的精度，例如假设求解精度为保留六位小数，由
63、于区间 -1, 2 的长度为 3，则必须将该区间分为 3 106 等分。因为 2213 106222，所以编码所用的二进制串至少需要22位。二进制串（b21b20b19b1b0）与 a,b 内实数的一一映射：二进制串十进制数a,b内实数b21b20b19b1b0101编码转化到 -1,2 内的实数为：例例.二进制串 a= 其对应的十进制数为：102产生初始群体u 随机的产生一个初始群体。pop1= ， % a1 ， % a2 ， % a3 % a4这里假设初始群体的个体数为 4。转化成 -1,2 之间的十进制数即为：下面就需要解决每个染色体个体的适应值pop1= 1.523032,0.5740
64、22,-0.697235,0.247238103（2）定义适应函数和适应值由于目标函数 f(x) 在 -1,2 内的值有正有负，所以必须通过建立适应函数与目标函数的映射关系，保证映射后的适应值非负，而且目标函数的优化方向应对应于适应值增大的方向，也为以后计算各个体的入选概率打下基础。 定义适应函数 ：为了便于计算，这里的 Fmin 采用了一个特定的输入值 例：例：如果取如果取Fmin=-1，则则f(x)=1对应的适应值为对应的适应值为g(x)=2104适应函数和适应值上述随机产生的初始群体，取 Fmin=-1，则则它们的目标函数值和适应值分别为：f(pop1)= 1.226437,1.3185
65、43,-1.380607,0.933350g(pop1)= 2.226437,2.318543, 0,1.933350105（3）确定选择标准u 用适应值比例来作为入选概率。u 设给定的规模为 n 的群体 pop=a1,a2,.,an ，个体 ai 的适应值为 g(ai)，则其入选概率为n 上述随机产生的初始群体，它们的入选概率分别为：p(pop1)=g(pop1)/sum(g(pop1) =0.343675, 0.357892, 0, 0.298433106产生种群 （4）产生种群u将入选概率大的个体选入种群，淘汰概率小的个体，并用概率最大的个体补入种群，得到与原群体大小同样的种群。newp
66、op1= ， % a1 ， % a2 ， % a2 % a4n 在上述随机产生的初始群体中，淘汰掉 a3，再加入 a2，得到新的种群：107交叉（5）交叉u 交叉也就是将一组染色体上对应基因段的交换得到新的染色体，然后得到新的染色体组，组成新的群体。n 将前面得到的 newpop1 的四个个体两两配对，重复的不配对，进行交叉（可以在任一位进行交叉）： 新的群体 jchpop1108变异（6）变异u 变异就是通过一个小概率改变染色体位串上的某个基因。n 现把 jchpop1 中第 3 个个体中的第 9 位改变，就产生了变异，得到了新的群体 pop2 ：pop2= , , , 然后重复上述的选择、
67、交叉、变异，直到满足终止条件为止然后重复上述的选择、交叉、变异，直到满足终止条件为止109终止条件 （7）终止条件u 遗传算法的终止条件有两类常见条件：n 采用设定最大（遗传）代数的方法，一般可设定为 50代，此时就可能得出最优解此种方法简单易行，但可能不是很精确n 根据个体的差异来判断，通过计算种群中基因多样性测度，即所有基因位相似程度来进行控制110 遗传算法作为一种对生物进化现象进行仿真的程序，取得了人工遗传的模遗传算法作为一种对生物进化现象进行仿真的程序，取得了人工遗传的模拟效果，具有自适应性。在遗传算法的结构中遗传操作和选择机制是两个拟效果，具有自适应性。在遗传算法的结构中遗传操作和
68、选择机制是两个重要的因素，其联系可用重要的因素，其联系可用遗传算法遗传算法=遗传操作遗传操作+选择过程选择过程这个逻辑关系来这个逻辑关系来表示。表示。如果一个应用问题不能求得目标函数的全局最优值如果一个应用问题不能求得目标函数的全局最优值,而只能或只希望而只能或只希望求一定意义下的求一定意义下的满意解满意解，这时，这时,可供选择的方法之一自然是遗传算法，可供选择的方法之一自然是遗传算法，因为遗传算法比其他算法有更多的优势。可喜的是因为遗传算法比其他算法有更多的优势。可喜的是,近年来遗传算法在商近年来遗传算法在商业应用方面取得了一系列重要成果。遗传算法的商业应用五花八门业应用方面取得了一系列重要
69、成果。遗传算法的商业应用五花八门,覆盖覆盖面甚广面甚广,比如通用电器公司的计算机辅助设计系统比如通用电器公司的计算机辅助设计系统Engeneous,这是一个采这是一个采用了遗传算法以及其他传统的优化技术做为寻优手段的混合系统用了遗传算法以及其他传统的优化技术做为寻优手段的混合系统(hybridsystem)。Engeneous已成功地应用于汽轮机设计已成功地应用于汽轮机设计,并改善了新的波音并改善了新的波音777发动机的性能，这是目前正在研究和应用的一个重要方面。发动机的性能，这是目前正在研究和应用的一个重要方面。展望展望111遗传算法具有隐并行性，它可容易改造成为并行遗传算法具有隐并行性，它
70、可容易改造成为并行/分布式算法，用来解决那些复分布式算法，用来解决那些复杂性问题。杂性问题。到目前，遗传算法的理论机制仍不是很清楚，这可能和生命科学的研究一到目前，遗传算法的理论机制仍不是很清楚，这可能和生命科学的研究一样，将是一个永恒的研究课题，但也是一个难题。已有很多学者对遗传算法作样，将是一个永恒的研究课题，但也是一个难题。已有很多学者对遗传算法作了一些深入的研究，近几十年来，遗传算法的文献已相当多，由于时间所限，了一些深入的研究，近几十年来，遗传算法的文献已相当多，由于时间所限，仅介绍了遗传算法的一些基本知识。仅介绍了遗传算法的一些基本知识。112模拟退火算法来源于固体退火原理，将固体
71、加温至充分高，再让其徐徐冷却，模拟退火算法来源于固体退火原理，将固体加温至充分高，再让其徐徐冷却，加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋加温时，固体内部粒子随温升变为无序状，内能增大，而徐徐冷却时粒子渐趋有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根有序，在每个温度都达到平衡态，最后在常温时达到基态，内能减为最小。根据据Metropolis准则，粒子在温度准则，粒子在温度T时趋于平衡的概率为时趋于平衡的概率为e-E/(kT)，其中其中E为温为温度度T时的内能，时的内能，E为其改变量，为其改变量，k为为Boltzmann常数。用固体退火模拟组合
72、优常数。用固体退火模拟组合优化问题，将内能化问题，将内能E模拟为目标函数值模拟为目标函数值f，温度温度T演化成控制参数演化成控制参数t，即得到解组合即得到解组合优化问题的模拟退火算法：由初始解优化问题的模拟退火算法：由初始解i和控制参数初值和控制参数初值t开始，对当前解重复开始，对当前解重复“产生新解产生新解计算目标函数差计算目标函数差接受或舍弃接受或舍弃”的迭代，并逐步衰减的迭代，并逐步衰减t值，算法终止值，算法终止时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式时的当前解即为所得近似最优解，这是基于蒙特卡罗迭代求解法的一种启发式随机搜索过程。退火过程由冷却进度表随机搜索
73、过程。退火过程由冷却进度表(CoolingSchedule)控制，包括控制参控制，包括控制参数的初值数的初值t及其衰减因子及其衰减因子t、每个每个t值时的迭代次数值时的迭代次数L和停止条件和停止条件S。3.4模拟退火算法模拟退火算法 113 模拟退火算法可以分解为解空间、目标函数和初始解三部分模拟退火算法可以分解为解空间、目标函数和初始解三部分。模拟退火算法的模型模拟退火算法的模型114 (1)初始化：初始温度初始化：初始温度T(充分大充分大)，初始解状态，初始解状态S(是算法迭代的起点是算法迭代的起点)，每每个个T值的迭代次数值的迭代次数L(2)对对k=1，L做第做第(3)至第至第6步：步：
74、(3)产生新解产生新解S(4)计算增量计算增量t=C(S)-C(S)，其中其中C(S)为评价函数为评价函数(5)若若t0，然后转第然后转第2步。步。模拟退火的基本思想模拟退火的基本思想115116 第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接第一步是由一个产生函数从当前解产生一个位于解空间的新解；为便于后续的计算和接受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构受，减少算法耗时，通常选择由当前新解经过简单地变换即可产生新解的方法，如对构成新解的全部或部分元素进行置换、互换等，注意到产生新解的变换方法决定了当前新成新解的全部或部分元素
75、进行置换、互换等，注意到产生新解的变换方法决定了当前新解的邻域结构，因而对冷却进度表的选取有一定的影响。解的邻域结构，因而对冷却进度表的选取有一定的影响。第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目第二步是计算与新解所对应的目标函数差。因为目标函数差仅由变换部分产生，所以目标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差标函数差的计算最好按增量计算。事实表明，对大多数应用而言，这是计算目标函数差的最快方法。的最快方法。第三步是判断新解是否被接受第三步是判断新解是否被接受,判断的依据是一个接受准则，最常用的接受准则是判断的依据是一个接受
76、准则，最常用的接受准则是Metropo1is准则准则:若若t0则接受则接受S作为新的当前解作为新的当前解S，否则以概率否则以概率exp(-t/T)接受接受S作作为新的当前解为新的当前解S。第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解第四步是当新解被确定接受时，用新解代替当前解，这只需将当前解中对应于产生新解时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可时的变换部分予以实现，同时修正目标函数值即可。此时，当前解实现了一次迭代。可在此基础上开始下一轮试验。而当新解被判定为舍弃时，则在原当前解的基础上继续下在此基础上开始下一轮试验。而当新
77、解被判定为舍弃时，则在原当前解的基础上继续下一轮试验。一轮试验。模拟退火算法新解的产生和接受模拟退火算法新解的产生和接受117 模拟退火算法与初始值无关，算法求得的解与初始解状态模拟退火算法与初始值无关，算法求得的解与初始解状态S(是算法迭代的起点是算法迭代的起点)无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率无关；模拟退火算法具有渐近收敛性，已在理论上被证明是一种以概率l收敛收敛于全局最优解的全局优化算法；模拟退火算法具有并行性。于全局最优解的全局优化算法；模拟退火算法具有并行性。模拟退火算法的简单应用模拟退火算法的简单应用 作为模拟退火算法应用，讨论货郎担问题作为模拟退火算
78、法应用，讨论货郎担问题(TravellingSalesmanProblem，简记为简记为TSP)：设有设有n个城市，用数码个城市，用数码1,n代表。城市代表。城市i和城市和城市j之间的距离为之间的距离为d(i，j)i,j=1,nTSP问题是要找遍访每个域市恰好一次的一条回路，且其路径问题是要找遍访每个域市恰好一次的一条回路，且其路径总长度为最短。总长度为最短。求解求解TSP的模拟退火算法模型可描述如下：的模拟退火算法模型可描述如下：解空间解空间解空间解空间S是遍访每个城市恰好一次的所有回路，是是遍访每个城市恰好一次的所有回路，是1，n的所有的所有循环排列的集合，循环排列的集合，S中的成员记为中
79、的成员记为(w1,w2,，wn)，并记并记wn+1=w1。初始解初始解可选为可选为(1，n)。118目标函数目标函数此时的目标函数即为访问所有城市的路径总长度或称为代价函数：此时的目标函数即为访问所有城市的路径总长度或称为代价函数：新解的产生新解的产生随机产生随机产生1和和n之间的两相异数之间的两相异数k和和m，若，若km，则将则将(w1,w2,，wk,wk+1,，wm,，wn)变为：变为：(wm,wm-1,，w1,wm+1,，wk-1,wn,wn-1,，wk).上述变换方法可简单说成是上述变换方法可简单说成是“逆转中间或者逆转两端逆转中间或者逆转两端”。119代价函数差代价函数差设将设将(w
80、1,w2,，wn)变换为变换为(u1,u2,，un),则代则代价函数差为：价函数差为：模拟退火算法的应用很广泛，可以较高的效率求解最大截问题模拟退火算法的应用很广泛，可以较高的效率求解最大截问题(MaxCutProblem)、0-1背包问题背包问题(ZeroOneKnapsackProblem)、图着色问图着色问题题(GraphColouringProblem)、调度问题调度问题(SchedulingProblem)等等。等等。120 模拟退火算法的参数控制问题模拟退火算法的参数控制问题模拟退火算法的应用很广泛，可以求解模拟退火算法的应用很广泛，可以求解NP完全问题，但其参数难以控制，其主完全
81、问题，但其参数难以控制，其主要问题有以下三点：要问题有以下三点：(1)温度温度T的初始值设置问题。的初始值设置问题。温度温度T的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、的初始值设置是影响模拟退火算法全局搜索性能的重要因素之一、初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；初始温度高，则搜索到全局最优解的可能性大，但因此要花费大量的计算时间；反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，反之，则可节约计算时间，但全局搜索性能可能受到影响。实际应用过程中，初始温度一般需要依据实验结果进行若干次调整。初始温度一般需要依据实验结果进行若干次
82、调整。(2)退火速度问题。退火速度问题。模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温模拟退火算法的全局搜索性能也与退火速度密切相关。一般来说，同一温度下的度下的“充分充分”搜索搜索(退火退火)是相当必要的，但这需要计算时间。实际应用中，是相当必要的，但这需要计算时间。实际应用中，要针对具体问题的性质和特征设置合理的退火平衡条件。要针对具体问题的性质和特征设置合理的退火平衡条件。(3)温度管理问题。温度管理问题。温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于温度管理问题也是模拟退火算法难以处理的问题之一。实际应用中，由于必须考虑计算复杂度的切实可行性等问题，
83、常采用如下所示的降温方式：必须考虑计算复杂度的切实可行性等问题，常采用如下所示的降温方式：T(t+1)kT(t)式中式中k为正的略小于为正的略小于1.00的常数，的常数，t为降温的次数。为降温的次数。121第三章第三章总结总结本章所讨论的知识的搜索与推理是人工智能研究另一本章所讨论的知识的搜索与推理是人工智能研究另一核心问题。核心问题。这里讨论的几种比较早期的搜索技术以及两种近些年这里讨论的几种比较早期的搜索技术以及两种近些年来研究得比较多的搜索算法来研究得比较多的搜索算法，它们适合于解决不太复它们适合于解决不太复杂的问题。杂的问题。（1）盲目搜索技术）盲目搜索技术（2）启发式搜索技术）启发式搜索技术（3）遗传算法）遗传算法（4）模拟退火算法）模拟退火算法122
