如何求解问题

如何求解问题第1页，共121页，2023年，2月20日，星期六主要内容：传统方法：穷举搜索、局部搜索、单纯形法、贪婪算法、分而治之法、动态规划法、分枝定界法、A*算法现代方法：模拟退火、禁忌搜索、演化算法、约束处理技术、神经网络、模糊系统第2页，共121页，2023年，2月20日，星期六引言理性的人努力使自己适应这个世界；疯狂的人坚持使世界适应自己；因此，一切进步取决于疯狂的人们。------G.B.萧伯纳《革命家箴言》第3页，共121页，2023年，2月20日，星期六这不是一次算法讲座，但其中充满算法，算法不是讲座主题。讲座不仅为你提供必要的知识，更重要的是帮你拓展才能去构建新的问题和进行创造性的思维。有效的求解问题的重要性从来没有现在这么强烈。不幸的是，我们的麻烦在生命的早期就已出现。甚至早到上小学时，我们被教导去分解问题，去孤立地解决更简单、更小的问题，我们被填鸭式地灌输着问题的求解方法，却从未思考是否有其他办法！大学课本亦然！第4页，共121页，2023年，2月20日，星期六美国初三数学课本内容一个农夫有一个长方形的农场，它的周长是110米，面积是700平方米，问农场的边长各式多少？学生们用本章学的方法建立方程2x+2y=110Xy=700根据刚学过的知识，很快算出x，解决问题第5页，共121页，2023年，2月20日，星期六美国初三数学课本内容另一章是关于几何和讨论三角形性质的。末尾总结了一系列需要解决的问题。学生们毫不怀疑他应用这些定理来解决这些问题。但是这看上去并不是正确的教育之道。问题和方法的关系应该通过问题而不是对方法的讨论而得到。从长远看，这样弊大于利，它使的学生不能独立地思考问题！为了说明这一点，下面举例说明。第6页，共121页，2023年，2月20日，星期六证明：AD+DB<AC+CBCDAB第7页，共121页，2023年，2月20日，星期六很明显，三角形内的线段之和必定小于三角形两边之和有资料为证，此问题给本科生、研究生，甚至数学、工程、计算机方面的教授，他们中不到5%的人能在1个小时内解出这个问题，大部分人需要几个小时，还有些人根本就解不出来！有趣的的是这个问题出自美国5年级课本！如果你不能在1小时之内解决问题，那么此讲座正是为你而做！第8页，共121页，2023年，2月20日，星期六证明：AD+DB<AC+CBCDABE定理：三角形的任意两边之和必大于第三边。第9页，共121页，2023年，2月20日，星期六三个孩子的年龄有多大？数学家遇见多年未见的朋友。朋友说：我的三个孩子都是今天的生日，你能算出他们的年龄吗？他们三个的年龄之积是36，年龄之和是那栋房子的窗户数。数学家看过房子说：我还需要一点信息。朋友说：我大儿子的眼睛是蓝色的。数学家说：OK。我算出来了。第10页，共121页，2023年，2月20日，星期六三个孩子的年龄之积为36第一第二第三361118211231941922661632433第11页，共121页，2023年，2月20日，星期六年龄之和为房子的窗户数36+1+1=3818+2+1=2112+3+1=169+4+1=149+2+2=136+6+1=136+3+2=114+3+3=10第12页，共121页，2023年，2月20日，星期六如此推理假如房子的窗户数不是13，那么数学家就会立刻给出答案。但是，他说，还需要信息，因此只有两种可能的情况：（9，2，2）或（6，6，1）父亲说“大儿子眼睛是蓝色的”，所以三个孩子的年龄一定是：（9，2，2）第13页，共121页，2023年，2月20日，星期六1为何有些问题难以求解？搜索空间中可能解的数目太多以至于无法采用穷举搜索法去找到最优解问题是如此复杂以至于为了得到答案，我们不得不采用问题的简化模型，而实际上所得的结果是无用的描述可能解质量的评估函数或者有噪声或者随时间而变化，因此需要的不仅仅是一个解而是一系列解的解集可能解都被严格约束以至于构造哪怕一个可行解都是困难的，更不用说找最优解了求解问题的人没有作好充分准备或存在某种心里障碍使得他们难以找到答案第14页，共121页，2023年，2月20日，星期六几个典型问题及其搜索空间问题一：SAT问题逻辑学的一个基本问题是布尔可满足性问题（BooleanSatisfiabilityProblem，简称SAT），也就是使得包含一些布尔变量的复合语句取值为真。考虑以下包含100个布尔变量的范式：问题是要找出每个变量的真值指派，使得。第15页，共121页，2023年，2月20日，星期六可能解的空间有多大？解空间S的大小是：非常大！！此外，选取那种评估函数也不很清楚。我们希望评估函数有助于我们评价可能解的质量，越接近准确答案的值应该产生出越好的评估值。如果采用枚举搜索法，我们就不会在乎这些，只要一个一个地找，直到找到为止。但是如果想用评估函数指引我们比枚举法更快地找到最优解的话，那就不仅仅是要知道“正确”与“错误”了。这就使得用于解SAT问题的方法立刻显得复杂起来。第16页，共121页，2023年，2月20日，星期六问题二：TSP问题有些问题看起来比SAT问题更简单，因为它们提供了自然的评估函数，甚至解空间的大小也是可数的。例如，考虑旅行商问题（TravelingSalesmanProblem，简称TSP）。这个问题非常简单：旅行商必须以最短路径访问所有的城市一次且仅一次并回到出发地。第17页，共121页，2023年，2月20日，星期六图1.1给出了一个简单的对称的20城市的TSP，图中每对城市i到j的距离等于j到i的距离。即：dist（i，j）=dist（j，i）第18页，共121页，2023年，2月20日，星期六TSP的搜索空间是什么？

可以看作是n个城市的排列的集合。n个城市的任意排列产生一个有序表，它决定了所访问的城市的顺序，从商人的家所在城市开始，然后经过所有城市直至回家。最优解就是产生最小费用的那个排列。注意，以下路径是相同的：

2-…-6-15-3-11-19-1715-3-11-19-17-2-…-6

3-11-19-17-2-…-6-15第19页，共121页，2023年，2月20日，星期六搜索空间与评估函数搜索空间的大小：n！/（2n）TSP的解空间大到令人无法置信！评估函数的选择对于路径：15-3-11-19-17-2-…-6Cost=dist(15,3)+dist(3,11)+…+dist(6,15)第20页，共121页，2023年，2月20日，星期六问题三：NLP问题现在来看第三个例子：一个特定的非线性规划问题（NonlinearProgammingProblem,简称NLP）这是一个在科学文献中研究过的难题。迄今为止，还没有哪种传统的优化算法能给出一个令人满意的结果。事实上它是非线性规划问题11个测试函数中的第二个。第21页，共121页，2023年，2月20日，星期六问题是求函数：的最大值，使满足条件其中第22页，共121页，2023年，2月20日，星期六第23页，共121页，2023年，2月20日，星期六解空间是多大？函数G2是非线性的，它的全局最大值未知，但存在于原点附近。它的解空间是多少呢？如果精确到小数点后第6位，那么每个变量就有10000000=107个取值，因此搜索空间的大小是：107n

这个值要远远大于相应的TSP的解的数目。即使n=50时，NLP的可能解在取6位小数的精度时，达到10350个！第24页，共121页，2023年，2月20日，星期六评估函数如何？怎样评价不同解的质量？有一种方法是将G2本身作为评估函数，使函数G2取值更大的解被认为优于使其值更小的解。问题是，如图所示，图中有不可行区域，并且所有不可行点被置为0。可行区域和不可行区域的边界由等式来限定，并且最优解靠近这个边界。即使没有这个额外的难题，仅仅凭其可供选择的解的数目之巨大就足以看出这些看似简单的问题所面临的巨大挑战，由此可见，评估这些解的方法并不总是显而易见的。第25页，共121页，2023年，2月20日，星期六2几个基本概念求解问题的所有算法有三个基本概念是相同的，不管采用什么技术，都必须确定：（1）表示方式—对可选择的候选解进行编码（2）目标—描述了要达到的目的（3）评估函数—给出了给定表示方式下的任意特定解的质量第26页，共121页，2023年，2月20日，星期六这是一个极好的例子给你6根火柴棒，你的任务是以他们为边搭建起4个等边三角形。很容易用5根建立起两个这样的三角形，却很难将它扩展到4个三角形，特别是只剩下1根火柴棍。第27页，共121页，2023年，2月20日，星期六从一个错误的搜索空间开始，你将永远不可能找到正确答案四个等边三角形，6根火柴第28页，共121页，2023年，2月20日，星期六定义一个搜索问题现在定义一个搜索问题。给定搜索空间S和它的可行部分FS，要求找到某一xF，使对所有的yF，有Eval（x）Eval（y）（极小化问题）满足上述条件的点x叫做全局解。找到问题的这样一个全局解是很困难的！第29页，共121页，2023年，2月20日，星期六邻域和局部最优解S—搜索空间xN（x）如果对于所有的yN（x），都满足Eval（x）Eval（y），那么x就是局部最优解。X的邻域第30页，共121页，2023年，2月20日，星期六爬山法

（hill-climbingmethod）就像所有的局部搜索算法一样，都是运用迭代改进的技术。每次迭代从当前点的邻域中选取一个新点，若新点的评估值优于当前点，它就变成当前点；否则就选取当前点邻域中的其他点来比较。很明显，这种爬山法只能提供局部最优解。第31页，共121页，2023年，2月20日，星期六简单迭代爬山法的思想现在有很多种爬山算法，主要是在新解与当前解进行比较的方式上有所不同。开始时，当前解的所有可能邻域都被考虑，并且将具有最好评估值eval（vn）的点vn与当前点vc做比较。若eval（vc）比eval（vn）差，则新点vn就成为当前点；否则，则没有可能再进行局部改造：该算法已经达到局部最优或全局最优（变量local=TRUE）在这种情况下，算法的下一次迭代（t=t+1）随机选取一个新的当前点来执行。第32页，共121页，2023年，2月20日，星期六Procedure迭代爬山法Begint=0

初始化bestrepeatlocal=FALSE

随机选取一个当前点VC

评估VC

repeat

在VC的邻域中选择所有新点从这个新点的集合中找使评估函数eval的值最优的点Vnifeval（Vn）好于eval（Vc）

thenVc=Vn

elselocal=TRUEuntillocalt=t+1ifVc好于bestthenbest=Vcuntilt=MAXend简单迭代爬山法第33页，共121页，2023年，2月20日，星期六3传统方法—第一部分穷举搜索局部搜索单纯形法第34页，共121页，2023年，2月20日，星期六穷举搜索

（exhaustivesearch）检查搜索空间中的每一个解直到找到最好的全局解。如果要解决的是一个小问题，并且有时间去枚举出整个搜索空间时，保证你能用穷举法找到最优解。如果面临一个较大的问题，不要用此法，因为你永远也无法列举完所有情况。第35页，共121页，2023年，2月20日，星期六局部搜索1、从搜索空间中找到一个解并进行评估其质量，将它定义为当前解。2、变换当前解为一个新解并评估它的值。3、如果此解比当前解更好，则将当前解用新解替换，否则抛弃新解。4、重复2、3直至在给定集中找不到改进解。此类算法的关键：变换类型。第36页，共121页，2023年，2月20日，星期六线性规划单纯形法--1947年，美国空军服役转任斯坦福大学的科学家丹茨格教授。椭球法—1979年苏联名不见经传的数学家哈奇扬。内点法--1984年，美国贝尔实验室年轻的印度裔数学家卡马卡。第37页，共121页，2023年，2月20日，星期六运筹学的主要分支：一、

线性规划

二、

非线性规划

三、

动态规划

四、

图与网络分析

五、

存储论

六、

排队论

七、

对策论

八、

决策论

第38页，共121页，2023年，2月20日，星期六4传统方法—第二部分贪婪算法分而治之法动态规划法分枝定界法A*算法第39页，共121页，2023年，2月20日，星期六贪婪算法(greedyalgorithm)贪婪算法通过一系列步骤构造完整解来解决问题。这个算法流行的原因很明显：简单！贪婪法的基本思想出奇的简单：一个一个地为所有的决策变量赋值，在每一步作出最佳的决定。当然，这个过程假定了一种决策的启发式思想，即在每一步作最好的移动，以获得最大的“好处”，这就是“贪婪”这个名字的来由。但是这种方法也是目光短浅的，因为每一步作出最佳决定并不一定最终能得到全局最优解。第40页，共121页，2023年，2月20日，星期六贪婪算法和SAT问题对从1到n的每个变量，不分次序，指定一个真值，使其尽可能地满足最大数目的当前未满足子局。如果不分胜负，则随机选择一个最好赋值。将所有变量按照它们在子局中出现的频率，从大到小进行排序。依照上面次序，对每个变量进行赋值，使满足最大数目的当前未满足子局。如果不分胜负，则随机选择一个。根本找不到一个解决SAT问题的贪婪算法！第41页，共121页，2023年，2月20日，星期六方法1方法2方法3…对于每一种你能想象的常识性启发式规则，都能找出一个特例使得这种规则看上去非常愚蠢！贪婪算法和TSP问题第42页，共121页，2023年，2月20日，星期六对于NLP问题确实没有有效的贪婪算法，但可以设计一些具有贪婪特征的算法。例如，优化包含两个变量的函数，可以设定其中一个变量x1保持不变，让另一个变量x2变化，直到找到一个“最优解”；然后让x2保持不变，让x1变化，直到找到一个新的“最优解”。这种线性搜索的方法可以扩展到n维。贪婪算法和NLP问题第43页，共121页，2023年，2月20日，星期六然而，如果x1和x2相关，也就是说出现x1和x2的乘积项，这个过程就很差。除非用户建立的“评估”函数使得相关性不明显，否则最好不要使用这个方法。严格的说，线性搜索并不是真正的贪婪算法，因为它只计算完整解。然而它在某一时刻对于单维情况，总是试图选择最好的可能机会，这确实符合贪婪算法的基本思想。第44页，共121页，2023年，2月20日，星期六贪婪算法无论是应用在SAT、TSP、NLP，还是其他领域上，从概念上说都是很简单的，但是通常它们为这种简单性付出的代价是：无法解决包含多个相关参数的复杂问题，而现实问题往往如此！贪婪算法小结第45页，共121页，2023年，2月20日，星期六分而治之法有时候把一个看似复杂的问题分解成若干个较小的问题来求解是一个很好的办法。你可以逐个地求解这些较简单的问题，然后找一种方法将各部分的解组合成一个完整的答案，这就是分而治之法（divideandconquer,简称D&C）。注意当子问题的解组合成一个完整解时，要确保这个解就是你要寻找的答案！第46页，共121页，2023年，2月20日，星期六分而治之法的大致框架ProcedureD&C(P)Begin将问题Ｐ分解成子问题Ｐ１，…Ｐｋｆｏｒｉ＝１ｔｏｋｄｏｉｆｓｉｚｅ（Ｐｉ）＜ρｔｈｅｎ求解Ｐｉ（得到ｓｉ）ｅｌｓｅｓｉ

←Ｄ＆Ｃ（Ｐｉ）将组合到最终解中Ｅｎｄ图４.２求解问题Ｐ的分而治之之递归过程第47页，共121页，2023年，2月20日，星期六有一个２ｍ维的棋盘，上面有一个小洞，现在的任务是用一些“Ｌ”形的积木来覆盖整个棋盘第48页，共121页，2023年，2月20日，星期六第49页，共121页，2023年，2月20日，星期六第50页，共121页，2023年，2月20日，星期六动态规划法动态规划法(dynamicprogramming)的原理是：在求解问题的过程中，通过处理位于当前位置和所达目标之间的中间点来找到整个问题的解。整个过程是递归的，每下一个中间点都是已访问过的点的一个函数。适合于解决那些“次数很重要和操作的顺序很关键”的问题的一类方法。第51页，共121页，2023年，2月20日，星期六适合于动态规划法的标准问题必须具有下列特点整个问题的求解可以划分成若干阶段的一系列决策过程每个阶段有若干可能状态一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态在任一个阶段，最佳的决策序列（策略）和该阶段以前的决策无关各阶段状态之间的转换有明确定义的费用，而且在选择最佳决策时有递归关系第52页，共121页，2023年，2月20日，星期六

应用这个方法时首先从目标开始，反向地工作直到当前状态。也就是说首先确定最后一个阶段的最佳决策，然后在此基础上确定倒数第二个阶段的最佳决策，依次继续下去。第53页，共121页，2023年，2月20日，星期六用动态规划法解最短路问题1234105678974641535214324633334第54页，共121页，2023年，2月20日，星期六最优策略：1-3-5-8-10或1-4-5-8-10

或1-4-6-9-10。123410567897464153521432463333434476117811第55页，共121页，2023年，2月20日，星期六它是一种启发式算法其思想就是去掉那些明明知道不可能在其中找到最优解的搜索空间。它是建立在对搜索空间连续划分的思想上的。首先必须要知道任意特定解的代价的上界（或者下界，这要看是求最大值还是最小值）。分枝定界法

（branchandbound）第56页，共121页，2023年，2月20日，星期六如果已经有一个解，其代价是c个单位，并且知道下一个要尝试的解的代价有一个下界，比c要大，并且我们是求极小值，那么根本不必去计算这个将尝试的解有多糟糕，而只需忽略它，去尝试另一个可能解。我们可以将整个搜索空间想象成树状结构，分枝定界的启发式思想是剪去那些我们不感兴趣的分枝。分枝定界法的基本思想第57页，共121页，2023年，2月20日，星期六分枝定界法算法Procedure分枝定界Begin初始化CD初始化fboundwhile(不满足终止条件)do移去最好的盒子C→Di缩减或子划分Di→D’i修改fboundC←C∪

D’ifor所有的Di

∈Cdoif(f(Di)的下界)>fboundthen从C中移去DiEnd第58页，共121页，2023年，2月20日，星期六A*算法在任何给定时刻都采用最好的移动却可能会带来麻烦。比如贪婪法的执行结果并不总是很好，其问题就在于现在是较好的，却不一定是后面所需要的。假若我们有一个评估函数，它能提供足够的信息来避免这些陷阱，那我们就可以使用这种贪婪法以获得更好的性能。这个简单的思想带来了一个叫做“最佳优先”搜索（best-firstsearch）的概念及其扩展形式---A*算法。第59页，共121页，2023年，2月20日，星期六A*算法与深度优先搜索、广度优先搜索的主要区别最佳优先搜索探索的是下一个最有希望的结点，而深度优先搜索是以一种任意的模式往尽可能深的地方搜索，而广度优先搜索则搜索完一层中所有的结点后才进入下一层最佳优先搜索使用的是启发式规则，给每个结点提供一个性能值，深度优先搜索和广度优先搜索则不这样做第60页，共121页，2023年，2月20日，星期六旅行者过桥问题四个旅行者ABCD夜晚要过一座桥，他们只有一盏老式油灯用作照明，每次最多允许过两人，每人过桥时间不同。A—1min，B—2min，C—5min，D—10min两人一起过桥，时间由慢者决定。如何安排最好的组合，使他们花最短的时间过去？第61页，共121页，2023年，2月20日，星期六给出一个局部最优解A提着油灯护送每人过桥。A和B一起过桥，2minA自己回来，1minA和C一起过桥，5minA自己回来，1minA和D一起过桥，10min总共19min事实上还有更好的答案，你能找到吗？第62页，共121页，2023年，2月20日，星期六5跳离局部最优前面讨论的传统的求解问题的策略，它们中有些能保证找到全局解，有些则不能，但它们都遵循一个共同的模式。那就是，它们或者能够保证找到全局解但在求解一些典型的实际问题时代价太大（太耗时），或者容易“陷入”局部最优。由于很难加速一个能保证找到最优解的算法，即对于大多数实际问题很难找到多项式时间算法（因为它们大多是NP难问题），那么剩下的选择就是设计出能够跳离局部最优的算法。第63页，共121页，2023年，2月20日，星期六“噢！一匹插上翅膀的骏马！”爬山法：当到达一个局部最优解后便产生一个新的起始点，搜索重新开始。下面两种方法分别基于：1、一个附加参数（温度），用于改变从搜索空间的一个点移动到另一个点的概率---模拟退火（SimulatedAnnealing，SA）。2、一个记忆装置，用于驱使算法探索搜索空间的新区域---禁忌搜索（tabusearch）。第64页，共121页，2023年，2月20日，星期六简单爬山法—MAX=1Procedure局部搜索Beginx=S中的某个初始点

While（improve（x）“no”）dox=improve（x）返回xend注：子程序improve（x）从x的邻域返回一个新点y。若y比x好，那么子程序返回这个点的值，否则，返回“no”第65页，共121页，2023年，2月20日，星期六简化的模拟退火算法Procedure模拟退火Beginx=S中的某个初始点

While（不满足终止条件）dox=improve？（x，T）修改T

返回xend第66页，共121页，2023年，2月20日，星期六模拟退火与局部搜索的区别过程的终止条件—模拟退火执行到满足某个外部的终止条件时停止，而局部搜索则要求找到一个改进解。模拟退火中并不要求函数improve？（x，T）一定返回x邻域的一个更好点，而是返回一个可以接受解y，这依赖于当前温度T。模拟退火中参数T被定期修改，其值直接影响improve？的输出，局部搜索没有此特征。第67页，共121页，2023年，2月20日，星期六禁忌搜索算法Procedure禁忌搜索Beginx=S中的某个初始点

While（不满足终止条件）dox=improve？（x，H）修改H

返回xend在算法的结构上与模拟退火相同，函数也是返回一个可接受解y，它不一定比x更好，但其接受与否是基于搜索的历史H。第68页，共121页，2023年，2月20日，星期六你的直觉如何？对一个复杂的问题试着先猜测一个解，这是人的天性。一些猜测看起来也很直观，并且有些人也似乎更具直觉。你驾车以40km/h的从北京到上海，然后立即返回，车速为60km/h。试问整个旅程的平均速率是多少？第69页，共121页，2023年，2月20日，星期六华尔街股市著名的诡计一个狡诈的股票经纪人挑选出1024个人作为可能的客户（受骗者）。每天，给他们邮寄一份有关股市在第二天涨或跌的预测，一直持续10天。到第10天末，一个不幸的受害者会惊异地发现股票经纪人所预测的股市走势百发百中，10次都准确，那么从直觉他感到此人就是“神仙”！问题出在哪儿呢？第70页，共121页，2023年，2月20日，星期六6演化算法前面的算法都是以单个解作为每次迭代中进行下次搜索的基础。贪婪算法是通过每次获得局部最大改进来逐步建立解；动态规划在得到最终的完整解之前先求解许多小的子问题；分支定界则将搜索空间组织成一些子空间，然后剔除其中的一些子空间。相反，局部搜索、模拟退火和禁忌搜索则处理完整解。每次迭代都会获得一个局部最优解，下次迭代继续改进。不管区别如何，共同点就是一次只处理或构造一个解。第71页，共121页，2023年，2月20日，星期六目前的规则确定性规则：爬山法，如果被检查的邻域解更好，则移动到这个邻域解并从这里开始搜索；否则继续在当前邻域内搜索；概率性规则：模拟退火，如果被检查的邻域解更好，则接受这个解作为新的当前解；否则或者以一定的概率接受这个较差解或继续在当前邻域内搜索；到目前为止搜索的历史：禁忌搜索，接受可得到的最好邻域解，它并不一定要比当前解更好，但是一定不能是列于存储器中的一个受限制的或“禁忌”的移动。第72页，共121页，2023年，2月20日，星期六基于“种群”的算法兔子与狐狸在兔子种群里，有些机灵，被吃的可能性较小，因此更容易幸存并繁衍。在繁殖中会保留这些特点。每只幼兔不是双亲的复制体，而是双亲的随机扰动。经过多代之后的兔子就会表现出一些有利于它们同狐狸甚至其他兔子竞争的特性。同时，狐狸也在进化！第73页，共121页，2023年，2月20日，星期六演化算法的过程创建一个个体种群，表示所解决问题的潜在解集；评估个体；引入某种选择压力，保留较好个体，淘汰较差个体；应用变化算子产生待测试的新个体。重复执行“评估-选择-变化”的循环若干次。第74页，共121页，2023年，2月20日，星期六演化算法的优点大多数经典优化算法采用的是固定的评估函数，对它的任何修改都要重新启动算法。演化算法则是内在适应的，种群中的个体与当前环境相适应。易于与其他算法相结合。并行性一次求解可以返回多个解，供选择。程序设计心理学，你是创造者！第75页，共121页，2023年，2月20日，星期六这些东西有一个与众不同有12枚硬币，其中1枚是假币。假币的重量与真币不同，但不知是重还是轻。给你一架天平。用最少的次数，找出这枚假币，并说明它是重还是轻。第76页，共121页，2023年，2月20日，星期六演化算法设计思想演化求解问题的基本思想相当简单：由所解决任务的候选解组成一个种群，然后通过随机变化和选择等一代代演化下去。其中随机变化提供了发现新解的机制，选择则确定保持哪些解作为下一步搜索的基础。本质上而言，任何在可能解的状态空间内对点不进行重取样的搜索过程，对于所有问题的平均执行效果相同。一个从不进行重取样的爬山算法在试图寻找函数最大值时，平均效果等同于一个没有重复取样的盲目随机搜索。第77页，共121页，2023年，2月20日，星期六演化算法描述大多数演化算法的方程描述：x[t+1]=s(v(x[t])),其中x[t]是以x为表示方式t时刻的种群，

v(.)是变化算子，s(.)是选择算子。这个差分方程表示每一代的随机演化过程。过程：产生一个与相关问题的潜在解的种群，设计一些从旧解产生新解的变化算子，并应用选择机制保留那些最好解到当前代。第78页，共121页，2023年，2月20日，星期六最短路径是什么？四个城市分别位于正方形的四个顶点，现在的任务是设计一个道路网络，使得每个城市都与其他城市相连接且道路的总长最短。四个城市位置第79页，共121页，2023年，2月20日，星期六可能的方案……第80页，共121页，2023年，2月20日，星期六这个答案是最优的！第81页，共121页，2023年，2月20日，星期六8旅行商问题TSP将局部最优算法与演化算法结合—混合算法基于Karp-Steele算法中的分而治之技术—扩展的演化算法边组装杂交算法反序-杂交算法、旅行商问题是一个足以说明一个看似简单的问题如何面临许多意想不到的挑战的典型例子！例如哥德巴赫猜想。第82页，共121页，2023年，2月20日，星期六斑马问题—著名的约束满足问题五个颜色各异的房子里，住着不同国籍的人，他们饲养的宠物、喜欢喝的饮料以及拥有的汽车也各不相同，加上下面的信息：1、英国人住在红房子里2、西班牙人养狗3、居住在绿房子里的人喝可乐4、乌克兰人喝蛋酒5、绿房子是象牙色房子的右邻第83页，共121页，2023年，2月20日，星期六6、拥有老爷车的人养蜗牛7、拥有福特车的人住在黄房子里8、住在中间房子里的人喝牛奶9、挪威人住在最左边的房子里10、拥有雪佛莱的人与养狐狸的人是邻居11、拥有福特车的人与养马的人是邻居12、拥有奔驰汽车的人爱喝桔汁13、日本人开大众汽车14、挪威人的邻居住在蓝房子里第84页，共121页，2023年，2月20日，星期六形式化的表示方法Ai—i号房子的颜色Bi—住i号房子的人喝的饮料Ci—住i号房子的人的国籍Di—住i号房子的人拥有的汽车Ei—住i号房子的人饲养的宠物第85页，共121页，2023年，2月20日，星期六变量的取值范围第86页，共121页，2023年，2月20日，星期六根据条件可以得出Ifci=Sthenei=D(i=2,3,4,5)第87页，共121页，2023年，2月20日，星期六最后的答案第88页，共121页，2023年，2月20日，星期六为什么要练习这类问题？练习解决这种约束满足问题的好处是训练你的逻辑思维，考虑什么是可能的什么是不可能的。这些问题也出现在研究生入学考试中，因此记住一句老生的忠告：提前做好准备吧！如果你已经完成了学业，那么就该庆幸这一切终于过去了！第89页，共121页，2023年，2月20日，星期六9约束处理技术现实世界的每个问题都包含约束，你根本无法摆脱这些约束。只有教科书中才可能遇到无约束问题。事实上所有的决策问题都包含约束。正是这些约束的形式使各种类型的问题相互不同。根据问题的表示形式，约束可以表示为规则、数据依赖、代数式或其他形式。第90页，共121页，2023年，2月20日，星期六蜗牛爬杆一只蜗牛顺着一根10米高的旗杆往上爬，白天向上爬5米，晚上睡觉下滑4米，问需要多少天蜗牛才能爬到旗杆的顶端？第91页，共121页，2023年，2月20日，星期六利用空间来描述约束第92页，共121页，2023年，2月20日，星期六处理约束的最常用的方法惩罚函数法第93页，共121页，2023年，2月20日，星期六10针对问题调整算法渴望一夜暴富的人，一年之内将被绳之以法-----L.达芬奇《杂记》几乎每个实用的启发式搜索算法都由某个参数集控制，但是这些方法中没有哪一个能将一切都封装到一个礼品盒中，让你一打开盒子就可以获得一份惊喜！在缺少理论指导的情况下，最好能找到一种自动优化参数的方法，使得在这些参数的控制下，演化算法能找到更好的解。第94页，共121页，2023年，2月20日，星期六本章小结一个演化算法的有效性依赖于它的各个组成部分（表示方式、变化算子等）及其相互作用。影响演化算法的最优化参数设置的主要障碍之一是这些参数之间的非线性相互作用。依赖人的智能和专业技术是设计演化算法（包括参数设计）的最好办法。第95页，共121页，2023年，2月20日，星期六11随时间变化的环境与噪声一个二次碗，每个抽样点加入高斯噪声第96页，共121页，2023年，2月20日，星期六现实世界永远是变化的在实际问题的求解中，只找到一个解并固守这个解是远远不够的，你必须随着问题的改变不断地寻找新的解。当求解的目标改变时，解也必须随之改变。即使目标随着时间的推移本质上保持不变，然而在竞争的环境中，与竞争对手的目标的交互方式也会发生改变。这就要求根据面对的问题重新考虑解。第97页，共121页，2023年，2月20日，星期六著名的囚犯两难问题两个犯人被关在不同房间，检察官分别说：若你们都认罪，判4年；假如你认罪，但他不认罪。你释放，他判5年；你们俩都不认罪，分别2年。第98页，共121页，2023年，2月20日，星期六数学模型认罪保持沉默认罪保持沉默（4，4）（0，5）（5，0）（2，2）加入OPEC的国家就像在玩囚犯两难游戏第99页，共121页，2023年，2月20日，星期六12神经网络第100页，共121页，2023年，2月20日，星期六13模糊系统1965年Zadeh提出模糊集理论他描述“年老”的模糊集隶属函数：这不是唯一的隶属函数第101页，共121页，2023年，2月20日，星期六Zadeh“年老”模糊隶属函数第102页，共121页，2023年，2月20日，星期六模糊系统的概念与应用模糊集与概率测度隶属度与隶属函数模糊集运算与模糊关系模糊控制器模糊聚类模糊神经网络模糊TSP演化模糊系统第103页，共121页，2023年，2月20日，星期六你喜欢简单的解决办法吗？两个杯子分别盛水和果汁，体积相等。取一匙果汁放入水中，搅拌后再取一匙混合液体放回装果汁的杯中。问：水中的果汁与果汁中的水哪一个更多？第104页，共121页，2023年，2月20日，星期六这一个例子也很有说服力要举行一个由937名选手参加的网球锦标赛，获胜的选手可以继续比赛，失利的选手将被淘汰。为了完成这个锦标赛需要进行多少场比赛？第105页，共121页，2023年，2月20日，星期六一般的计算方法锦标赛的全部场次（87名种子选手）：1+2+4+8+16+32+64+128+256+425=936决赛半决赛1/4决赛第106页，共121页，2023年，2月20日，星期六答案可以这样计算！因为一场比赛只淘汰1名选手，因此在有n名选手参加的锦标赛中，必须淘汰n-1名选手而产生1名胜者，因此需要进行n-1场比赛。所以937名选手，需要936场比赛！第107页，共121页，2023年，2月20日，星期六等分问题一个正方形分成相等的四部分，OK右边的图，如何分成相等的四部分？第108页，共121页，2023年，2月20日，星期六原来如此！再出问题：右边的正方形，如何分成相等的五部分？第109页，共121页，2023年，2月20日，星期六14混合系统没有任何单个算法称得上是解决所有问题的最