3搜索问题-启发式搜索.ppt

搜索问题搜索问题1启发式搜索启发式搜索启发式搜索，也称为有信息搜索，借助问题的特定启发式搜索，也称为有信息搜索，借助问题的特定知识来帮助选择搜索方向知识来帮助选择搜索方向在搜索过程中对待扩展的每一个节点进行评估，得在搜索过程中对待扩展的每一个节点进行评估，得到最好的位置，再从这个位置进行搜索直到目标。到最好的位置，再从这个位置进行搜索直到目标。启发式搜索的目的是省略大量无谓的搜索路径，提启发式搜索的目的是省略大量无谓的搜索路径，提到效率。到效率。在启发式搜索中，对节点的评价是十分重要的，评在启发式搜索中，对节点的评价是十分重要的，评价函数是搜索成败的关键。价函数是搜索成败的关键。启发式搜索启发式搜索评评价价函函数数，也也称称为为启启发发函函数数提提供供问问题题的的启启发发性性信信息息，按其用途划分，可分为以下三类：按其用途划分，可分为以下三类：用用于于扩扩展展节节点点的的选选择择，即即用用于于决决定定应应先先扩扩展展哪哪一一个个节节点点，以免盲目扩展以免盲目扩展用用于于生生成成节节点点的的选选择择，即即用用于于决决定定应应生生成成哪哪些些后后续续节节点点，以免盲目地生成过多无用节点以免盲目地生成过多无用节点用用于于删删除除节节点点的的选选择择，即即用用于于决决定定应应删删除除哪哪些些无无用用节节点点，以免造成进一步的时空浪费以免造成进一步的时空浪费启发式搜索启发式搜索一个节点一个节点n n的评价函数的构造通常由两部分构成的评价函数的构造通常由两部分构成从初始节点到当前节点从初始节点到当前节点n n的路径耗散的路径耗散从当前节点从当前节点n n到目标节点的期望耗散到目标节点的期望耗散即：评价函数可表示为：即：评价函数可表示为：这两部分里，这两部分里，通常是比较明确的，容易得通常是比较明确的，容易得到到而而 难以构造，也没有固定的模式，需要难以构造，也没有固定的模式，需要根据具体问题分析根据具体问题分析利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解启发式图搜索启发式图搜索引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。希望：希望：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。基本思想基本思想评价函数的格式：f(n)=g(n)+h(n)f(n)：评价函数h(n)：启发函数g(x)从初始节点S0到节点x的实际代价；h(x)从x到目标节点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，h(x)称为启发式函数。1 1、启发式搜索启发式搜索算法算法A A（A A算法）算法）g*(n)：从s到n的最短路径的耗散值h*(n)：从n到g的最短路径的耗散值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值定义定义开始开始把把S放入放入OPEN表，表，计算估价函数计算估价函数 f(s)OPEN表为空表？表为空表？选取选取OPEN表中表中f值最小的节点值最小的节点i放入放入CLOSED表表i为目标节点吗？为目标节点吗？扩展扩展i，得后继节点，得后继节点j，计算，计算f(j)，提供返回，提供返回节点节点i的指针，利用的指针，利用f(j)对对OPEN表重新排表重新排序，调整亲子关系及指针序，调整亲子关系及指针失败失败成功成功有序搜索算法框图有序搜索算法框图是是否否是是否否v算法A A算法算法1.Open:=(s)1.Open:=(s)，f(s):=g(s)+h(s);f(s):=g(s)+h(s);2.LOOP:IF Open=()THEN EXIT(FAIL);2.LOOP:IF Open=()THEN EXIT(FAIL);3.n:=FIRST(OPEN);3.n:=FIRST(OPEN);4.IF GOAL(n)THEN EXIT(SUCCESS);4.IF GOAL(n)THEN EXIT(SUCCESS);5.REMOVE(n,Open),ADD(n,Closed);5.REMOVE(n,Open),ADD(n,Closed);6.EXPAND(n)(m6.EXPAND(n)(mi i)，把把mmi i作为作为n n的后继节点添入的后继节点添入G G，计算计算 f(nmf(nmi i)=g(nm)=g(nmi i)+h(m)+h(mi i)；6-1)ADD(m6-1)ADD(mj j,Open);,Open);6-2)IF f(nm6-2)IF f(nmk k)f(m)f(mk k)THEN f(m)THEN f(mk k):=f(nm):=f(nmk k););6-3)IF f(nm6-3)IF f(nml l)h*(n),搜索的节点数少，搜索范围小，搜索的节点数少，搜索范围小，效率高，但不能保证得到最优解。效率高，但不能保证得到最优解。如果如果h(n)=h*(n)，这种情况下，搜索的节点数多，这种情况下，搜索的节点数多，搜索范围大，效率低，但能得到最优解搜索范围大，效率低，但能得到最优解启发式搜索启发式搜索满足满足h(n)=h*(n)条件的条件的A A搜索，称为搜索，称为A*(A-A*(A-star)star)搜索搜索A*A*搜索中，搜索中，h(n)越接近越接近h*(n)，搜索效率越高，搜索效率越高宽度优先算法可以看作宽度优先算法可以看作A*A*算法的特例，即：算法的特例，即：g(n)是节点所在的层数，是节点所在的层数，h(n)=0 0 代价树宽度搜索也可以看作代价树宽度搜索也可以看作A*A*算法的特例，即：算法的特例，即：g(n)是节点是节点n的实际路径耗散，的实际路径耗散，h(n)=0 0跟前两个算法一样，跟前两个算法一样，A*A*算法也具有完备性和最优算法也具有完备性和最优性性启发式搜索启发式搜索例：八数码问题例：八数码问题启发函数启发函数1 1：h1(n)=不在位的不在位的数码的总数数码的总数问题问题1 1：图中：图中S0S0状态状态h(S0)是什么，是什么，h*(S0)又是什么又是什么问题问题2 2：这个启发函数是否一定：这个启发函数是否一定满足满足h(n)=h*(n)问题问题3 3：对于八数码问题，还能：对于八数码问题，还能提出其他的启发函数吗？提出其他的启发函数吗？h(S0)=4启发式搜索启发式搜索例：八数码问题例：八数码问题启发函数启发函数2 2：h2(n)=所所有数码到目标位置的距有数码到目标位置的距离和（曼哈顿距离）离和（曼哈顿距离）问题问题1 1：图中：图中S0S0状态状态h(S0)是什么，是什么，h*(S0)又又是什么是什么问题问题2 2：这个启发函数是：这个启发函数是否一定满足否一定满足h(n)=h*(n)数码1：1 数码2：1数码3：0 数码4：0数码5：0 数码6：1数码7：0 数码8：2h2(S0)=5启发式搜索启发式搜索A*A*算法算法当当h(n)=h*(n)时，同时满足完备性和最优时，同时满足完备性和最优性要求性要求h(n)越接近于真实耗散越接近于真实耗散h*(n)，算法的搜索效算法的搜索效率越高，对内存和时间的需求越小率越高，对内存和时间的需求越小如果满足如果满足h(n)=h*(n)，是最完美的是最完美的A*算法算法h(n)的设计是的设计是A*算法的核心，也是最困难的算法的核心，也是最困难的地方地方完备的：如果存在解，则一定能找到该解最优的可纳的：如果存在解，则一定能找到最优解搜索目标时的搜索空间的节点数是目标深度的指数，搜索过程中的复杂性呈指数级增长。并且，它在内存空间中保存了所有的节点。A*A*算法分析算法分析2.5.32.5.3分支限界法分支限界法 分分支支限限界界法法是是优优先先扩扩展展当当前前具具有有最最小小耗耗散散值值分分支支路路径径的的叶节点叶节点n n，其评价函数为，其评价函数为f(n)=g(n)f(n)=g(n)。其其思思想想是是：建建立立一一个个局局部部路路径径（或或分分支支）的的队队列列表表，每每次次都都选选耗耗散散值值最最小小的的那那个个分分支支上上的的叶叶节节点点来来扩扩展展，直直到到生成含有目标节点的路径为止。生成含有目标节点的路径为止。分支界限法分支界限法(最小代价优先法最小代价优先法)基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察,而不管这个节点在搜索树的什么位置上。算法与前面的“全局择优法”仅有引导搜索的函数不同，前者为启发函数h(x)，后者为代价g(x)。注意：代价值g(x)是从初始节点So方向计算而来的,而启发函数值h(x)则是朝目标节点方向计算的。分支限界法分支限界法 过程过程 Branch-BoundBranch-Bound1 1）QUEUEQUEUE：=（s-ss-s），），g g（s s）=0=0；2 2）LOOPLOOP：IF QUEUE=IF QUEUE=（）（）THEN EXITTHEN EXIT（FAILFAIL）；）；3 3）PATHPATH：=FIRST=FIRST（QUEUEQUEUE），），n n：=LAST=LAST（PATHPATH）；）；4 4）IF GOALIF GOAL（n n）THEN EXITTHEN EXIT（SUCCESSSUCCESS）；）；5 5）EXPANDEXPAND（n n）mmi i，计计 算算 g g（mmi i）=g=g（n n，mmi i），REMOVEREMOVE（s-ns-n，QUEUEQUEUE），），ADDADD（s-n-ms-n-mi i，QUEUEQUEUE）；）；6 6）QUEUE QUEUE 中局部路径中局部路径g g值最小者排在前面；值最小者排在前面；7 7）GO LOOPGO LOOP；例：八城市地图网问题例：八城市地图网问题例：八城市地图网问题例：八城市地图网问题应用分支限界法求应用分支限界法求解图解图2-142-14的最短路的最短路径问题，其搜索图径问题，其搜索图如图如图2-152-15所示。所示。图2-14八城市地图网示意图 SDBDCEDFEBFABEBFACtg=01g=3A2g=4g=7g=83g=9g=64g=11g=105g=11g=126g=107g=139g=15g=148g=1310g=15g=151112g=14g=1613图2-15分支限界搜索图求解过程中求解过程中QUEUEQUEUE的结果：的结果：初始（初始（s s（0 0）1 1）（）（A A（3 3）D D（4 4）2 2）（）（D D（4 4）B B（7 7）D D（8 8）3 3）（）（E E（6 6）B B（7 7）D D（8 8）A A（9 9）4 4）（）（B B（7 7）D D（8 8）A A（9 9）F F（1010）B B（1111）5 5）（）（D D（8 8）A A（9 9）F F（1010）B B（1111）C C（1111）E E（1212）6 6）（）（A A（9 9）F F（1010）E E（1010）B B（1111）C C（1111）E E（1212）7 7）（）（F F（1010）E E（1010）B B（1111）C C（1111）E E（1212）B B（1313）8 8）（）（E E（1010）B B（1111）C C（1111）E E（1212）t t（13)B13)B（1313）)9 9）（）（B B（1111）C C（1111）E E（1212）t t（1313）B B（1313）F F（1414）B B（1515）1010）（）（C C（1111）E E（1212）t t（1313）B B（1313）F F（1414）B B（1515）A A（15)C15)C（1515）1111）（）（E E（1212）t t（1313）B B（1313）F F（1414）B B（1515）A A（1515）C C（1515）1212）（）（t t（1313）B B（1313）F F（1414）D D（1414）B B（1515）A A（1515）C C（1515）F F（1616）1313）结束。）结束。2.5.42.5.4动态规划法动态规划法 动态规划法实际上是对分支限界法的改进。动态规划法实际上是对分支限界法的改进。动态规划原理指出，求动态规划原理指出，求stst的最佳路径时，对某个中间节的最佳路径时，对某个中间节点点I I，只考虑，只考虑s s到到I I中具有最小耗散值这一条局部路径就可中具有最小耗散值这一条局部路径就可以，其余以，其余s s到到I I的路径是多余的。的路径是多余的。如果对于任何n，当h(n)=0时，A*算法就成为了动态规划算法。具有动态规划原理的分支限界算法具有动态规划原理的分支限界算法过程过程Dynamic-ProgrammingDynamic-Programming1 1）QUEUEQUEUE：=（s-ss-s），），g g（s s）=0=0；2 2）LOOPLOOP：IF QUEUEIF QUEUE：=（）（）THEN EXITTHEN EXIT（FAILFAIL）；）；3 3）PATHPATH：=FIRST=FIRST（QUEUEQUEUE），），n n：=LAST=LAST（PATHPATH）；）；4 4）IF GOALIF GOAL（n n）THEN EXITTHEN EXIT（SUCCESSSUCCESS）；）；5 5）EXPANDEXPAND（n n）mmi i，计计算算g g（mmi i）=g=g（n n，mmi i），REMOVEREMOVE（s-ns-n，QUEUEQUEUE），），ADDADD（s-ms-mi i，QUEUEQUEUE）；）；6 6）QUEUE QUEUE 中中有有多多条条到到达达某某一一公公共共节节点点的的路路径径时时，只只保保留留耗耗散散值值最最小小的的那那条路径，其余删去，并重新排序，条路径，其余删去，并重新排序，g g值最小者排在前面；值最小者排在前面；7 7）GO LOOPGO LOOP；SAD1g=0g=3g=42BDg=7g=83AEg=9g=64BFg=11g=105ECg=11g=126tg=13图2-16动态规划原理的搜索树 动态规划动态规划st第一阶段第二阶段第三阶段第四阶段第五阶段加权状态图搜索加权状态图与代价树加权状态图与代价树设A城是出发地,E城是目的地,边上的数字代表两城之间的交通费。试求从A到E最小费用的旅行路线。代价树的搜索。所谓代价，可以是两点之间的距离、交通费用或所需时间等等。通常用g(x)表示从初始节点So到节点x的代价,用c(xi,xj)表示父节点xi到子节点xj的代价,即边(xi,xj)的代价。从而有 g(xj)g(xi)c(xi,xj)而 g(So)0 旅行商问题（Traveling-Salesman Problem，TSP）设有n个互相可直达的城市,某推销商准备从其中的A城出发,周游各城市一遍,最后又回到A城。要求为该推销商规划一条最短的旅行路线。该问题的状态为以A打头的已访问过的城市序列:A So:A。Sg:A,A。其中“”为其余n-1个城市的一个序列。状态转换规则：状态转换规则：规规则则1 1 如果当前城市的下一个城市还未去过,则去该城市,并把该城市名排在已去过的城市名序列后端。规规则则2 2 如果所有城市都去过一次,则从当前城市返回A城,把A也添在去过的城市名序列后端。状态图表示（简化）状态图表示（简化）一个问题的状态图是一个三元组 (S,F,G)其中S是问题的初始状态集合,F是问题的状态转换规则集合,G是问题的目标状态集合。一个问题的全体状态及其关系就构成一个空间,称为状态空间。所以,状态图也称为状态空间图。例例 迷宫问题的状态图表示。S：SoF：(So,S4),(S4,So),(S4,S1),(S1,S4),(S1,S2),(S2,S1),(S2,S3),(S3,S2),(S4,S7),(S7,S4),(S4,S5),(S5,S4),(S5,S6),(S6,S5),(S5,S8),(S8,S5),(S8,S9),(S9,S8),(S9,Sg)G：Sg X1X2X3XX0X4X7X6X5八数码难题的状态图表示。用向量 A(X0,X1,X2,X3,X4,X5,X6,X7,X8)表示,Xi为变量,Xi的值就是所在方格内的数字。于是,向量A就是该问题的状态表达式。我们将棋局 设初始状态和目标状态分别为 So(0,2,8,3,4,5,6,7,1)Sg(0,1,2,3,4,5,6,7,8)例：在下图所示的由例：在下图所示的由1717根火柴组成的图案中，去掉根火柴组成的图案中，去掉5 5根火根火柴，柴，使图案形成三个小正方形。使图案形成三个小正方形。解：解：（1 1）以火柴棍为单位进行去除操作，需要实验的总次数是）以火柴棍为单位进行去除操作，需要实验的总次数是 次。次。（2 2）以小方块为单位进行去除操作，需要实验的总次数是）以小方块为单位进行去除操作，需要实验的总次数是 次。次。（3 3）考虑到火柴去掉）考虑到火柴去掉5 5根后还有根后还有1212根，要形成三个小方块，根，要形成三个小方块，那么这三个小方块不能有公共边，在此图案中仅有两种可那么这三个小方块不能有公共边，在此图案中仅有两种可能。能。状态图搜索策略小结 爬山法搜索模拟退火搜索局部剪枝搜索局部搜索算法局部搜索算法启发式搜索启发式搜索-爬山法爬山法爬山法爬山法模拟人们出游爬山的决策过模拟人们出游爬山的决策过程程以目标值增加的方向为搜索以目标值增加的方向为搜索方向方向如果有多个增加的方向，选如果有多个增加的方向，选使目标值增加速度最快的方使目标值增加速度最快的方向向爬山法会在某个峰顶终止，爬山法会在某个峰顶终止，其相邻状态中没有更高的目其相邻状态中没有更高的目标值了，称为局部极大值标值了，称为局部极大值启发式搜索启发式搜索-爬山法爬山法爬山法的基本步骤爬山法的基本步骤1 1、初始化，确定初始节点等参数、初始化，确定初始节点等参数2 2、检查当前节点是否满足目标条件，如果满足，则搜索成、检查当前节点是否满足目标条件，如果满足，则搜索成功，结束功，结束3 3、取邻域中每一个相邻节点，计算其目标函数的改进值、取邻域中每一个相邻节点，计算其目标函数的改进值4 4、取改进值最大的相邻节点作为搜索目标，替换当前节点、取改进值最大的相邻节点作为搜索目标，替换当前节点5 5、检查是否满足循环终止条件。如果满足，则中止循环，、检查是否满足循环终止条件。如果满足，则中止循环，否则转步否则转步2 2启发式搜索启发式搜索-爬山法爬山法爬山法的缺陷爬山法的缺陷难以处理山肩的情况难以处理山肩的情况贪婪搜索方向不一定是正确的搜索方向贪婪搜索方向不一定是正确的搜索方向启发式搜索启发式搜索-爬山法爬山法爬山法的改进爬山法的改进随机爬山法：在上山移动中随机的选择下一步随机爬山法：在上山移动中随机的选择下一步可回溯爬山法：给定启发式的回溯策略，允许回头搜索其他可回溯爬山法：给定启发式的回溯策略，允许回头搜索其他节点节点洪水爬山法：洪水爬山法：不断寻找改进方向不断寻找改进方向允许水平移动允许水平移动可回溯可回溯启发式搜索启发式搜索-模拟退火模拟退火算法算法（simulated annealingsimulated annealing）爬山法是完完全全的贪心法，每次都选择一个当前最优解，因此只能搜索到局部的最优值。模拟退火其实也是一种贪心算法，但是它的搜索过程引入了随机因素。模拟退火算法以一定的概率以一定的概率来接受一个比当前解要差的解，因此有可能有可能会跳出这个局部的最优解，达到全局的最优解。移动后得到更优解，则总是接受该移动移动后的解比当前解要差，则以一定的概率接受移以一定的概率接受移动，而且这个概率随着时间推移逐渐降低（逐渐降动，而且这个概率随着时间推移逐渐降低（逐渐降低才能趋向稳定）低才能趋向稳定）这里的“一定的概率”的计算参考了金属冶炼的退火过程，这也是模拟退火算法名称的由来模拟退火算法模拟退火算法模拟退火搜索：结合爬山法和随机行走模拟退火搜索：结合爬山法和随机行走比喻：在冶金中退火是为了增强金属和玻璃的韧性和硬度而先把它们加热到高温然后逐渐冷却的过程启发式搜索启发式搜索-模拟退火算法模拟退火算法模拟退火过程模拟退火过程思想来源于固体退火原理，属于热力学范畴思想来源于固体退火原理，属于热力学范畴将固体加温至充分高，再让其缓慢冷却将固体加温至充分高，再让其缓慢冷却加温时，固体内部的粒子随温升脱离原先的平衡态，变为加温时，固体内部的粒子随温升脱离原先的平衡态，变为无序状无序状缓慢冷却时，粒子活性逐渐下降，逐渐停留在不同状态，缓慢冷却时，粒子活性逐渐下降，逐渐停留在不同状态，重新形成粒子的排列结构重新形成粒子的排列结构如果降温过程足够缓慢，粒子的排列就会达到一种平衡态，如果降温过程足够缓慢，粒子的排列就会达到一种平衡态，使系统能量最小使系统能量最小 启发式搜索启发式搜索-模拟退火算法模拟退火算法初始状态加温冷却启发式搜索启发式搜索-模拟退火算法模拟退火算法模拟退火的基本步骤模拟退火的基本步骤:(1)初始化：初始温度初始化：初始温度T(充分大充分大)，初始状态，初始状态S，迭代迭代次数次数L (2)对对k=1，L重复第重复第(3)至第至第6步：步：(3)产生新解产生新解S (4)计算增量计算增量t=C(S)-C(S)，其中，其中C(S)为评价函数为评价函数 (5)若若t0，然后转第，然后转第2步。步。启发式搜索启发式搜索-模拟退火算法模拟退火算法冷却进度表：冷却进度表：是指调整模拟退火法的一系列重要参数，它控制温度参数是指调整模拟退火法的一系列重要参数，它控制温度参数T T的初值及其衰减函数。的初值及其衰减函数。冷却进度表的内容：冷却进度表的内容：控制参数控制参数T T的初值的初值;控制参数控制参数T T的衰减函数；的衰减函数；每一个温度下的迭代次数每一个温度下的迭代次数L L，即每一次随机游走过程，要迭代，即每一次随机游走过程，要迭代多少次，才能趋于一个准平衡分布多少次，才能趋于一个准平衡分布结束条件结束条件启发式搜索启发式搜索-模拟退火算法模拟退火算法模拟退火算法的关键点模拟退火算法的关键点初始温度必须足够高初始温度必须足够高在每一个温度下，状态的转换必须足够充分在每一个温度下，状态的转换必须足够充分温度温度T T的下降必须足够缓慢的下降必须足够缓慢启发式搜索启发式搜索-模拟退火算法模拟退火算法模拟退火算法的优缺点模拟退火算法的优缺点 优点：优点：计算过程简单，通用，鲁棒性强计算过程简单，通用，鲁棒性强适用于并行处理，可用于求解复杂的非线性优化问题适用于并行处理，可用于求解复杂的非线性优化问题缺点：缺点：如果降温过程足够缓慢，多得到的解的性能会比较好，但与如果降温过程足够缓慢，多得到的解的性能会比较好，但与此相对的是收敛速度太慢此相对的是收敛速度太慢;如果降温过程过快，很可能得不到全局最优解如果降温过程过快，很可能得不到全局最优解爬山算法：兔子朝着比现在高的地方跳去。它找到了不远处的最高山峰。可能这只兔子“登泰山而小天下”，但是却没有找到珠穆朗玛峰。这就是爬山算法，它不能保证局部最优值就是全局最优值。模拟退火：对兔子来说，兔子喝醉了。他迷迷糊糊地跳了很长时间。这期间，它可能走向高处，也可能踏入平地。但是，他渐渐清醒了并朝最高方向跳去。为了保证有比较优的解，算法运行时间比较长，这也是模拟退火的最大缺点。人喝醉了酒办起事来都不利索，何况兔子？例如有这样一个问题：为了找出地球上最高例如有这样一个问题：为了找出地球上最高的山珠穆朗玛峰，一群有志气的兔子们开始的山珠穆朗玛峰，一群有志气的兔子们开始想办法。想办法。遗传算法：兔子们吃了失忆药片，并被发射到太空，然后随机落到了地球上的某些地方。他们不知道自己的使命是什么。但是，如果你过几年就杀死一部分海拔低的兔子，多产的兔子们自己就会找到珠穆朗玛峰。禁忌搜索:兔子们知道一个兔的力量是渺小的。他们互相转告着，哪里的山已经找过，并且找过的每一座山他们都留下一只兔子做记号。他们制定了下一步去哪里寻找的策略。兔子们找到了泰山，它们之中的一只就会留守在这里，其他的再去别的地方寻找。就这样，一大圈后，把找到的几个山峰一比较，珠穆朗玛峰脱颖而出。这种方法的有的是“记忆”,所以的兔子能记住他们已选中哪座山,下一步就避免了重复搜索.根据生物进化思想的启发而得出的一种全局优化算法。它模拟达尔文的自然选择学说和自然界的生物进化过程，借喻生物进化过程特别是遗传学的术语于原理来求解问题。遗传算法由美国Michigan大学J.Holland教授于1973年首先提出。GA是基于“适者生存，优胜劣汰”的一种高度并行、随机和自适应的优化算法，采用简单的编码技术来表示各种复杂的结构，并通过对一组编码表示进行简单的遗传操作和优胜劣汰的自然选择来指导学习和确定搜索的方向。遗传算法遗传算法GA(genetic algorithm)GA(genetic algorithm)遗传算法的操作对象是一群二进制串(称为染色体、个体)，即种群。这里每一个染色体都对应问题的一个解。从初始种群出发，采用基于适当的选择策略在当前种群中选择个体，使用杂交和变异来产生下一代种群。如此模仿生命的进化一代代演化下去，直到满足期望的终止条件为止，从而求得问题的最优解或满意解。首先根据问题的目标函数对可行解进行编码，可行解进行编码后称为个体。编码方案建立了可行解与个体之间的一一映射。随机产生一组初始个体构成初始种群，种群中染色体的数目称为种群的大小或规模。用设计好的适应度函数来评价每一个染色体的优劣，即染色体对环境的适应程度(简称为适应度)，用来作为以后遗传操作的依据。进行选择过程，选择过程的目的是为了从当前种群中选出优良的染色体，使它们成为新一代的染色体。判断染色体优良与否的准则是各自的适应度，即染色体的适应度越高，其被选择的机会就越多。通过选择操作，产生了一个新种群。对新种群按交叉概率执行交叉操作；按变异概率对群体中的每一个个体执行变异操作。变异操作的目的是挖掘种群中个体的多样性，克服有可能陷入局优解的弊病。通过上述、的运算产生的染色体成为后代。对新的种群(即父代和后代)重复进行选择、交叉和变异操作。经过给定次数的迭代处理或满足目标条件后，把最好的染色体作为优化问题的最优解。编码编码产生初始群体产生初始群体计算适应计算适应度函数度函数遗传算子：选择（赌盘选择）、交叉（单点或多点）遗传算子：选择（赌盘选择）、交叉（单点或多点）、变异（单点或多点）、变异（单点或多点）用两种搜索方法解决八数码难题(要求过程，最好有open表和close表)作业作业123845712384567（目标状态）（初始状态）6