如何求解问题.ppt

1、如何求解问题 -现代启发式算法,How to Solve It Modern Heuristics,主要内容：,传统方法： 穷举搜索、局部搜索、单纯形法、贪婪算法、分而治之法、动态规划法、分枝定界法、A*算法 现代方法： 模拟退火、禁忌搜索、演化算法、约束处理技术、神经网络、模糊系统,引言,理性的人努力使自己适应这个世界； 疯狂的人坚持使世界适应自己； 因此，一切进步取决于疯狂的人们。 -G.B.萧伯纳革命家箴言,这不是一次算法讲座，但其中充满算法，算法不是讲座主题。,讲座不仅为你提供必要的知识，更重要的是帮你拓展才能去构建新的问题和进行创造性的思维。 有效的求解问题的重要性从来没有现在这么强

2、烈。 不幸的是，我们的麻烦在生命的早期就已出现。甚至早到上小学时，我们被教导去分解问题，去孤立地解决更简单、更小的问题，我们被填鸭式地灌输着问题的求解方法，却从未思考是否有其他办法！大学课本亦然！,美国初三数学课本内容,一个农夫有一个长方形的农场，它的周长是110米，面积是700平方米，问农场的边长各式多少？ 学生们用本章学的方法建立方程 2x+2y=110 Xy=700 根据刚学过的知识，很快算出x，解决问题,美国初三数学课本内容,另一章是关于几何和讨论三角形性质的。末尾总结了一系列需要解决的问题。学生们毫不怀疑他应用这些定理来解决这些问题。 但是这看上去并不是正确的教育之道。问题和方法的关

3、系应该通过问题而不是对方法的讨论而得到。从长远看，这样弊大于利，它使的学生不能独立地思考问题！ 为了说明这一点，下面举例说明。,证明：AD+DBAC+CB,C,D,A,B,很明显，三角形内的线段之和必定小于三角形两边之和,有资料为证，此问题给本科生、研究生，甚至数学、工程、计算机方面的教授，他们中不到5%的人能在1个小时内解出这个问题，大部分人需要几个小时，还有些人根本就解不出来！ 有趣的的是这个问题出自美国5年级课本！ 如果你不能在1小时之内解决问题，那么此讲座正是为你而做！,证明：AD+DBAC+CB,E,定理：三角形的任意两边之和必大于第三边。,三个孩子的年龄有多大？,数学家遇见多年未见

4、的朋友。 朋友说：我的三个孩子都是今天的生日，你能算出他们的年龄吗？ 他们三个的年龄之积是36，年龄之和是那栋房子的窗户数。 数学家看过房子说：我还需要一点信息。 朋友说：我大儿子的眼睛是蓝色的。 数学家说：OK。我算出来了。,三个孩子的年龄之积为36,第一 第二 第三 36 1 1 18 2 1 12 3 1 9 4 1 9 2 2 6 6 1 6 3 2 4 3 3,年龄之和为房子的窗户数,36+1+1=38 18+2+1=21 12+3+1=16 9+4+1=14 9+2+2=13 6+6+1=13 6+3+2=11 4+3+3=10,如此推理,假如房子的窗户数不是13，那么数学家就会立

5、刻给出答案。但是，他说，还需要信息，因此只有两种可能的情况： （9，2，2） 或 （6，6，1） 父亲说“大儿子眼睛是蓝色的”， 所以三个孩子的年龄一定是： （9，2，2）,1 为何有些问题难以求解？,搜索空间中可能解的数目太多以至于无法采用穷举搜索法去找到最优解 问题是如此复杂以至于为了得到答案，我们不得不采用问题的简化模型，而实际上所得的结果是无用的 描述可能解质量的评估函数或者有噪声或者随时间而变化，因此需要的不仅仅是一个解而是一系列解的解集 可能解都被严格约束以至于构造哪怕一个可行解都是困难的，更不用说找最优解了 求解问题的人没有作好充分准备或存在某种心里障碍使得他们难以找到答案,几个

6、典型问题及其搜索空间,问题一：SAT问题 逻辑学的一个基本问题是布尔可满足性问题（Boolean Satisfiability Problem，简称SAT ），也就是使得包含一些布尔变量的复合语句取值为真。考虑以下包含100个布尔变量的范式：,问题是要找出每个变量 的真值指派，使得 。,可能解的空间有多大？,解空间S的大小是： 非常大！,此外，选取那种评估函数也不很清楚。我们希望评估函数有助于我们评价可能解的质量，越接近准确答案的值应该产生出越好的评估值。如果采用枚举搜索法，我们就不会在乎这些，只要一个一个地找，直到找到为止。但是如果想用评估函数指引我们比枚举法更快地找到最优解的话，那就不仅仅

7、是要知道“正确”与“错误”了。这就使得用于解SAT问题的方法立刻显得复杂起来。,问题二：TSP问题,有些问题看起来比SAT问题更简单，因为它们提供了自然的评估函数，甚至解空间的大小也是可数的。例如，考虑旅行商问题（Traveling Salesman Problem，简称TSP）。这个问题非常简单：旅行商必须以最短路径访问所有的城市一次且仅一次并回到出发地。,图1.1给出了一个简单的对称的20城市的TSP，图中每对城市i到j 的距离等于j 到i的距离。 即：dist（i，j）= dist（j，i）,TSP的搜索空间是什么？,可以看作是n个城市的排列的集合。n个城市的任意排列产生一个有序表，它决

8、定了所访问的城市的顺序，从商人的家所在城市开始，然后经过所有城市直至回家。最优解就是产生最小费用的那个排列。 注意，以下路径是相同的： 2- -6-15-3-11-19-17 15-3-11-19-17-2-6 3-11-19-17-2-6-15,搜索空间与评估函数,搜索空间的大小：n！/（2n） TSP的解空间大到令人无法置信！ 评估函数的选择 对于路径：15-3-11-19-17-2-6 Cost=dist(15,3)+ dist(3,11)+ dist(6,15),问题三：NLP问题,现在来看第三个例子：一个特定的非线性规划问题（Nonlinear Progamming Problem,

9、简称NLP）这是一个在科学文献中研究过的难题。迄今为止，还没有哪种传统的优化算法能给出一个令人满意的结果。事实上它是非线性规划问题11个测试函数中的第二个。,问题是求函数：,的最大值，使满足条件,其中,解空间是多大？,函数G2是非线性的，它的全局最大值未知，但存在于原点附近。它的解空间是多少呢？如果精确到小数点后第6位，那么每个变量就有10000000=107个取值，因此搜索空间的大小是：107n 这个值要远远大于相应的TSP的解的数目。即使n=50时，NLP的可能解在取6位小数的精度时，达到10350个！,评估函数如何？怎样评价不同解的质量？,有一种方法是将G2本身作为评估函数，使函数G2取

10、值更大的解被认为优于使其值更小的解。问题是，如图所示，图中有不可行区域，并且所有不可行点被置为0。可行区域和不可行区域的边界由等式 来限定，并且最优解靠近这个边界。即使没有这个额外的难题，仅仅凭其可供选择的解的数目之巨大就足以看出这些看似简单的问题所面临的巨大挑战，由此可见，评估这些解的方法并不总是显而易见的。,2 几个基本概念,求解问题的所有算法有三个基本概念是相同的，不管采用什么技术，都必须确定： （1）表示方式对可选择的候选解进行编码 （2）目标描述了要达到的目的 （3）评估函数给出了给定表示方式下的任 意特定解的质量,这是一个极好的例子,给你6根火柴棒，你的任务是以他们为边搭建起4个等

11、边三角形。很容易用5根建立起两个这样的三角形，却很难将它扩展到4个三角形，特别是只剩下1根火柴棍。,从一个错误的搜索空间开始，你将永远不可能找到正确答案,四个等边三角形，6根火柴,定义一个搜索问题,现在定义一个搜索问题。给定搜索空间S和它的可行部分FS，要求找到某一xF，使对所有的y F，有 Eval（x） Eval（y）（极小化问题） 满足上述条件的点x叫做全局解。 找到问题的这样一个全局解是很困难的！,邻域和局部最优解,S搜索空间,x,N（x）,如果对于所有的y N（x），都满足Eval（x） Eval（y），那么x就是局部最优解。,X的邻域,爬山法（hill-climbing metho

12、d）,就像所有的局部搜索算法一样，都是运用迭代改进的技术。 每次迭代从当前点的邻域中选取一个新点，若新点的评估值优于当前点，它就变成当前点；否则就选取当前点邻域中的其他点来比较。 很明显，这种爬山法只能提供局部最优解。,简单迭代爬山法的思想,现在有很多种爬山算法，主要是在新解与当前解进行比较的方式上有所不同。 开始时，当前解的所有可能邻域都被考虑，并且将具有最好评估值eval（vn）的点vn与当前点vc做比较。 若eval（vc）比 eval（vn）差，则新点vn就成为当前点；否则，则没有可能再进行局部改造：该算法已经达到局部最优或全局最优（变量local=TRUE） 在这种情况下，算法的下一

13、次迭代（t=t+1）随机选取一个新的当前点来执行。,Procedure 迭代爬山法 Begin t=0 初始化 best repeat local=FALSE 随机选取一个当前点VC 评估VC repeat 在VC的邻域中选择所有新点 从这个新点的集合中找使评估函数eval的值最优的点Vn if eval（Vn）好于eval（Vc） then Vc= Vn else local=TRUE until local t=t+1 if Vc 好于best then best= Vc until t=MAX end,简单迭代爬山法,3 传统方法第一部分,穷举搜索 局部搜索 单纯形法,穷举搜索（exha

14、ustive search）,检查搜索空间中的每一个解直到找到最好的全局解。 如果要解决的是一个小问题，并且有时间去枚举出整个搜索空间时，保证你能用穷举法找到最优解。 如果面临一个较大的问题，不要用此法，因为你永远也无法列举完所有情况。,局部搜索,1、从搜索空间中找到一个解并 进行评估其质量，将它定义为当前解。 2、变换当前解为一个新解并评估它的值。 3、如果此解比当前解更好，则将当前解用 新解替换，否则抛弃新解。 4、重复2、3直至在给定集中找不到改进解。 此类算法的关键：变换类型。,线性规划,单纯形法-1947年，美国空军服役转任斯坦福大学的科学家丹茨格教授。 椭球法1979年苏联名不见经

15、传的数学家哈奇扬。 内点法-1984年，美国贝尔实验室年轻的印度裔数学家卡马卡。,运筹学的主要分支：,一、线性规划二、非线性规划三、动态规划四、图与网络分析五、存储论六、排队论七、对策论八、决策论,4 传统方法第二部分,贪婪算法 分而治之法 动态规划法 分枝定界法 A*算法,贪婪算法(greedy algorithm),贪婪算法通过一系列步骤构造完整解来解决问题。这个算法流行的原因很明显：简单！贪婪法的基本思想出奇的简单：一个一个地为所有的决策变量赋值，在每一步作出最佳的决定。当然，这个过程假定了一种决策的启发式思想，即在每一步作最好的移动，以获得最大的“好处”，这就是“贪婪”这个名字的来由。

16、但是这种方法也是目光短浅的，因为每一步作出最佳决定并不一定最终能得到全局最优解。,贪婪算法和SAT问题,对从1到n的每个变量，不分次序，指定一个真值，使其尽可能地满足最大数目的当前未满足子局。如果不分胜负，则随机选择一个最好赋值。 将所有变量按照它们在子局中出现的频率，从大到小进行排序。 依照上面次序，对每个变量进行赋值，使满足最大数目的当前未满足子局。如果不分胜负，则随机选择一个。 根本找不到一个解决SAT问题的贪婪算法！,方法1 方法2 方法3 对于每一种你能想象的常识性启发式规则，都能找出一个特例使得这种规则看上去非常愚蠢！,贪婪算法和TSP问题,对于NLP问题确实没有有效的贪婪算法，但

17、可以设计一些具有贪婪特征的算法。 例如，优化包含两个变量的函数，可以设定其中一个变量x1保持不变，让另一个变量x2变化，直到找到一个“最优解”；然后让x2保持不变，让x1变化，直到找到一个新的“最优解”。这种线性搜索的方法可以扩展到n维。,贪婪算法和NLP问题,然而，如果x1和x2相关，也就是说出现x1和x2的乘积项，这个过程就很差。除非用户建立的“评估”函数使得相关性不明显，否则最好不要使用这个方法。 严格的说，线性搜索并不是真正的贪婪算法，因为它只计算完整解。然而它在某一时刻对于单维情况，总是试图选择最好的可能机会，这确实符合贪婪算法的基本思想。,贪婪算法无论是应用在SAT、TSP、NLP

18、，还是其他领域上，从概念上说都是很简单的，但是通常它们为这种简单性付出的代价是：无法解决包含多个相关参数的复杂问题，而现实问题往往如此！,贪婪算法小结,分而治之法,有时候把一个看似复杂的问题分解成若干个较小的问题来求解是一个很好的办法。你可以逐个地求解这些较简单的问题，然后找一种方法将各部分的解组合成一个完整的答案，这就是分而治之法（divide and conquer,简称D&C）。 注意当子问题的解组合成一个完整解时，要确保这个解就是你要寻找的答案！,分而治之法的大致框架,Procedure D&C(P) Begin 将问题分解成子问题， （）求解（得到） （） 将组合到最终解中 ,图.求

19、解问题的分而治之之递归过程,有一个维的棋盘，上面有一个小洞，现在的任务是用一些“”形的积木来覆盖整个棋盘,动态规划法,动态规划法(dynamic programming)的原理是：在求解问题的过程中，通过处理位于当前位置和所达目标之间的中间点来找到整个问题的解。整个过程是递归的，每下一个中间点都是已访问过的点的一个函数。 适合于解决那些“次数很重要和操作的顺序很关键”的问题的一类方法。,适合于动态规划法的标准问题必须具有下列特点,整个问题的求解可以划分成若干阶段的一系列决策过程 每个阶段有若干可能状态 一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态 在任一个阶段，最佳的决策序列（策略

20、）和该阶段以前的决策无关 各阶段状态之间的转换有明确定义的费用，而且在选择最佳决策时有递归关系,应用这个方法时首先从目标开始，反向地工作直到当前状态。也就是说首先确定最后一个阶段的最佳决策，然后在此基础上确定倒数第二个阶段的最佳决策，依次继续下去。,用动态规划法解最短路问题,最优策略：1-3-5-8-10或1-4-5-8-10或1-4-6-9-10。,3,4,4,7,6,11,7,8,11,它是一种启发式算法 其思想就是去掉那些明明知道不可能在其中找到最优解的搜索空间。它是建立在对搜索空间连续划分的思想上的。首先必须要知道任意特定解的代价的上界（或者下界，这要看是求最大值还是最小值）。,分枝定

21、界法（branch and bound）,如果已经有一个解，其代价是c个单位，并且知道下一个要尝试的解的代价有一个下界，比c要大，并且我们是求极小值，那么根本不必去计算这个将尝试的解有多糟糕，而只需忽略它，去尝试另一个可能解。 我们可以将整个搜索空间想象成树状结构，分枝定界的启发式思想是剪去那些我们不感兴趣的分枝。,分枝定界法的基本思想,分枝定界法算法,Procedure 分枝定界 Begin 初始化 CD 初始化 fbound while (不满足终止条件) do 移去最好的盒子CDi 缩减或子划分Di Di 修改fbound C C Di for 所有的Di C do if(f(Di)的下

22、界) fbound then 从C中移去Di End,A*算法,在任何给定时刻都采用最好的移动却可能会带来麻烦。比如贪婪法的执行结果并不总是很好，其问题就在于现在是较好的，却不一定是后面所需要的。假若我们有一个评估函数，它能提供足够的信息来避免这些陷阱，那我们就可以使用这种贪婪法以获得更好的性能。这个简单的思想带来了一个叫做“最佳优先”搜索（best-first search）的概念及其扩展形式- A*算法。,A*算法与深度优先搜索、广度优先搜索的主要区别,最佳优先搜索探索的是下一个最有希望的结点，而深度优先搜索是以一种任意的模式往尽可能深的地方搜索，而广度优先搜索则搜索完一层中所有的结点后才

23、进入下一层 最佳优先搜索使用的是启发式规则，给每个结点提供一个性能值，深度优先搜索和广度优先搜索则不这样做,旅行者过桥问题,四个旅行者ABCD夜晚要过 一座桥，他们只有一盏老式 油灯用作照明，每次最多允 许过两人，每人过桥时间不同。 A1min，B2min，C5min，D10min 两人一起过桥，时间由慢者决定。 如何安排最好的组合，使他们花最短的时间过去？,给出一个局部最优解,A提着油灯护送每人过桥。 A和B一起过桥，2min A自己回来，1min A和C一起过桥，5min A自己回来，1min A和D一起过桥，10min 总共19min 事实上还有更好的答案，你能找到吗？,5 跳离局部最优

24、,前面讨论的传统的求解问题的策略，它们中有些能保证找到全局解，有些则不能，但它们都遵循一个共同的模式。那就是，它们或者能够保证找到全局解但在求解一些典型的实际问题时代价太大（太耗时），或者容易“陷入”局部最优。由于很难加速一个能保证找到最优解的算法，即对于大多数实际问题很难找到多项式时间算法（因为它们大多是NP难问题），那么剩下的选择就是设计出能够跳离局部最优的算法。,“噢！一匹插上翅膀的骏马！”,爬山法：当到达一个局部最优解后便产生一个新的起始点，搜索重新开始。 下面两种方法分别基于： 1、一个附加参数（温度），用于改变从搜索空间的一个点移动到另一个点的概率-模拟退火（Simulated A

25、nnealing，SA）。 2、一个记忆装置，用于驱使算法探索搜索空间的新区域-禁忌搜索（tabu search）。,简单爬山法MAX=1,Procedure 局部搜索 Begin x=S中的某个初始点 While（improve（x）“no”）do x=improve（x） 返回 x end,注：子程序improve（x）从x的邻域返回一个新点y。若y比x好，那么子程序返回这个点的值，否则，返回“no”,简化的模拟退火算法,Procedure 模拟退火 Begin x=S中的某个初始点 While（不满足终止条件）do x=improve？（x，T） 修改 T 返回 x end,模拟退火与局

26、部搜索的区别,过程的终止条件模拟退火执行到满足某个外部的终止条件时停止，而局部搜索则要求找到一个改进解。 模拟退火中并不要求函数improve？（x，T）一定返回x邻域的一个更好点，而是返回一个可以接受解y，这依赖于当前温度T。 模拟退火中参数T被定期修改，其值直接影响improve？的输出，局部搜索没有此特征。,禁忌搜索算法,Procedure 禁忌搜索 Begin x=S中的某个初始点 While（不满足终止条件）do x=improve？（x，H） 修改 H 返回 x end,在算法的结构上与模拟退火相同，函数也是返回一个可接受解y，它不一定比x更好，但其接受与否是基于搜索的历史H。,你

27、的直觉如何？,对一个复杂的问题试着先 猜测 一个解，这是人的天性。一些猜测看起来也很直观，并且有些人也似乎更具直觉。 你驾车以40km/h的从北京到上海，然后立即返回，车速为60km/h。试问整个旅程的平均速率是多少？,华尔街股市著名的诡计,一个狡诈的股票经纪人挑选出1024个人作为可能的客户（受骗者）。每天，给他们邮寄一份有关股市在第二天涨或跌的预测，一直持续10天。到第10天末，一个不幸的受害者会惊异地发现股票经纪人所 预测的股市走势百发百中，10次都准确，那么从直觉他感到此人就是“神仙”！ 问题出在哪儿呢？,6 演化算法,前面的算法都是以单个解作为每次迭代中 进行下次搜索的基础。 贪婪算

28、法是通过每次获得局部最大改进来逐步建立解；动态规划在得到最终的完整解之前先求解许多小的子问题；分支定界则将搜索空间组织成一些子空间，然后剔除其中的一些子空间。 相反，局部搜索、模拟退火和禁忌搜索则处理完整解。每次迭代都会获得一个局部最优解，下次迭代继续改进。 不管区别如何，共同点就是一次只处理或构造一个解。,目前的规则,确定性规则：爬山法，如果被检查的邻域解更好，则移动到这个邻域解并从这里开始搜索；否则继续在当前邻域内搜索； 概率性规则：模拟退火，如果被检查的邻域解更好，则接受这个解作为新的当前解；否则或者以一定的概率接受这个较差解或继续在当前邻域内搜索； 到目前为止搜索的历史：禁忌搜索，接受

29、可得到的最好邻域解，它并不一定要比当前解更好，但是一定不能是列于存储器中的一个受限制的或“禁忌”的移动。,基于“种群”的算法,兔子与狐狸 在兔子种群里，有些机灵，被吃的可能性较小，因此更容易幸存并繁衍。在繁殖中会保留这些特点。每只幼兔不是双亲的复制体，而是双亲的随机扰动。经过多代之后的兔子就会表现出一些有利于它们同狐狸甚至其他兔子竞争的特性。 同时，狐狸也在进化！,演化算法的过程,创建一个个体种群，表示所解决问题的潜在解集； 评估个体； 引入某种选择压力，保留较好个体，淘汰较差个体； 应用变化算子产生待测试的新个体。 重复执行“评估-选择-变化”的循环若干次。,演化算法的优点,大多数经典优化算

30、法采用的是固定的评估函数，对它的任何修改都要重新启动算法。演化算法则是内在适应的，种群中的个体与当前环境相适应。 易于与其他算法相结合。 并行性 一次求解可以返回多个解，供选择。 程序设计心理学，你是创造者！,这些东西有一个与众不同,有12枚硬币，其中1枚是假币。 假币的重量与真币不同，但不知是重还是轻。 给你一架天平。 用最少的次数，找出这枚假币，并说明它是重还是轻。,演化算法设计思想,演化求解问题的基本思想相当简单：由所解决任务的候选解组成一个种群，然后通过随机变化和选择等一代代演化下去。其中随机变化提供了发现新解的机制，选择则确定保持哪些解作为下一步搜索的基础。 本质上而言，任何在可能解

31、的状态空间内对点不进行重取样的搜索过程，对于所有问题的平均执行效果相同。一个从不进行重取样的爬山算法在试图寻找函数最大值时，平均效果等同于一个没有重复取样的盲目随机搜索。,演化算法描述,大多数演化算法的方程描述： xt+1=s(v(xt),其中xt是 以x为表示方式t时刻的种群， v(.)是变化算子，s(.)是选择算子。这个差分方程表示每一代的随机演化过程。 过程：产生一个与相关问题的潜在解的种群，设计一些从旧解产生新解的变化算子，并应用选择机制保留那些最好解到当前代。,最短路径是什么？,四个城市分别位于正方形的四个顶点，现在的任务是设计一个道路网络，使得每个城市都与其他城市相连接且道路的总长

32、最短。,四个城市位置,可能的方案,这个答案是最优的！,8 旅行商问题TSP,将局部最优算法与演化算法结合混合算法 基于Karp-Steele算法中的分而治之技术扩展的演化算法 边组装杂交算法 反序-杂交算法、 旅行商问题是一个足以说明一个看似简单的问题如何面临许多意想不到的挑战的典型例子！例如哥德巴赫猜想。,斑马问题著名的约束满足问题,五个颜色各异的房子里，住着不同国籍的人，他们饲养的宠物、喜欢喝的饮料以及拥有的汽车也各不相同，加上下面的信息： 1、英国人住在红房子里 2、西班牙人养狗 3、居住在绿房子里的人喝可乐 4、乌克兰人喝蛋酒 5、绿房子是象牙色房子的右邻,6、拥有老爷车的人养蜗牛 7

33、、拥有福特车的人住在黄房子里 8、住在中间房子里的人喝牛奶 9、挪威人住在最左边的房子里 10、拥有雪佛莱的人与养狐狸的人是邻居 11、拥有福特车的人与养马的人是邻居 12、拥有奔驰汽车的人爱喝桔汁 13、日本人开大众汽车 14、挪威人的邻居住在蓝房子里,形式化的表示方法,Aii号房子的颜色 Bi住i号房子的人喝的饮料 Ci住i号房子的人的国籍 Di住i号房子的人拥有的汽车 Ei住i号房子的人饲养的宠物,变量的取值范围,根据条件可以得出,If ci=S then ei=D (i=2,3,4,5),最后的答案,为什么要练习这类问题？,练习解决这种约束满足问题的好处是训练你的逻辑思维，考虑什么是可

34、能的什么是不可能的。这些问题也出现在研究生入学考试中，因此记住一句老生的忠告：提前做好准备吧！如果你已经完成了学业，那么就该庆幸这一切终于过去了！,9 约束处理技术,现实世界的每个问题都包含约束，你根本无法摆脱这些约束。只有教科书中才可能遇到无约束问题。 事实上所有的决策问题都包含约束。正是这些约束的形式使各种类型的问题相互不同。根据问题的表示形式，约束可以表示为规则、数据依赖、代数式或其他形式。,蜗牛爬杆,一只蜗牛顺着一根10米高的旗杆往上爬，白天向上爬5米，晚上睡觉下滑4米，问需要多少天蜗牛才能爬到旗杆的顶端？,利用空间来描述约束,处理约束的最常用的方法,惩罚函数法,10 针对问题调整算法

35、,渴望一夜暴富的人，一年之内将被绳之以法 -L.达芬奇杂记 几乎每个实用的启发式搜索算法都由某个参数集控制，但是这些方法中没有哪一个能将一切都封装到一个礼品盒中，让你一打开盒子就可以获得一份惊喜！ 在缺少理论指导的情况下，最好能找到一种自动优化参数的方法，使得在这些参数的控制下，演化算法能找到更好的解。,本章小结,一个演化算法的有效性依赖于它的各个组成部分（表示方式、变化算子等）及其相互作用。 影响演化算法的最优化参数设置的主要障碍之一是这些参数之间的非线性相互作用。 依赖人的智能和专业技术是设计演化 算法（包括参数设计）的最好办法。,11 随时间变化的环境与噪声,一个二次碗，每个抽样点加入高

36、斯噪声,现实世界永远是变化的,在实际问题的求解中，只找到一个解并固守这个解是远远不够的，你必须随着问题的改变不断地寻找新的解。当求解的目标改变时，解也必须随之改变。 即使目标随着时间的推移本质上保持不变，然而在竞争的环境中，与竞争对手的目标的交互方式也会发生改变。这就要求根据面对的问题重新考虑解。,著名的囚犯两难问题,两个犯人被关在不同房间，检察官分别说：若你们都认罪，判4年； 假如你认罪，但他不认罪。你释放，他判5年； 你们俩都不认罪，分别2年。,数学模型,加入OPEC的国家就像在玩囚犯两难游戏,12 神经网络,13 模糊系统,1965年Zadeh提出模糊集理论 他描述“年老”的模糊集隶属函

37、数： 这不是唯一的隶属函数,Zadeh“年老”模糊隶属函数,模糊系统的概念与应用,模糊集与概率测度 隶属度与隶属函数 模糊集运算与模糊关系 模糊控制器 模糊聚类 模糊神经网络 模糊TSP 演化模糊系统,你喜欢简单的解决办法吗？,两个杯子分别盛水和果汁，体积相等。 取一匙果汁放入水中，搅拌后再取一匙混合液体放回装果汁的杯中。 问：水中的果汁与果汁中的水哪一个更多？,这一个例子也很有说服力,要举行一个由937名选手参加的网球锦标赛，获胜的选手可以继续比赛，失利的选手将被淘汰。为了完成这个锦标赛需要进行多少场比赛？,一般的计算方法,锦标赛的全部场次（87名种子选手）： 1+2+4+8+16+32+64+128+256+425=936,决赛,半决赛,1/4决赛,答案可以这样计算！,因为一场比赛只淘汰1名选手，因此在有n名选手参加的锦标赛中，必须淘汰n-1名选手而产生1名胜者，因此需要进行n-1场比赛。 所以937名选手，需要936场比赛！,等分问题,一个正方形分成相等的四部分，OK 右边的图，如何分成相等的四部分？,原来如此！,再出问题：右边的正方形，如何分成相等的五部分？,14 混合系统,没有任何单个算法称得上是 解决所有问题的最好方法。 必须将问题的有关知识以某种 有用的方式结合到算法中；否则，它比随机搜索好不到哪里去。解决这个问题的一种方式是将演化算法与更