如何求解问题ppt课件

如何求解问题-现代启发式算法,1,主要内容：,传统方法：穷举搜索、局部搜索、单纯形法、贪婪算法、分而治之法、动态规划法、分枝定界法、A*算法现代方法：模拟退火、禁忌搜索、演化算法、约束处理技术、神经网络、模糊系统,2,引言,理性的人努力使自己适应这个世界；疯狂的人坚持使世界适应自己；因此，一切进步取决于疯狂的人们。-G.B.萧伯纳革命家箴言,3,这不是一次算法讲座，但其中充满算法，算法不是讲座主题。,讲座不仅为你提供必要的知识，更重要的是帮你拓展才能去构建新的问题和进行创造性的思维。有效的求解问题的重要性从来没有现在这么强烈。不幸的是，我们的麻烦在生命的早期就已出现。甚至早到上小学时，我们被教导去分解问题，去孤立地解决更简单、更小的问题，我们被填鸭式地灌输着问题的求解方法，却从未思考是否有其他办法！大学课本亦然！,4,美国初三数学课本内容,一个农夫有一个长方形的农场，它的周长是110米，面积是700平方米，问农场的边长各式多少？学生们用本章学的方法建立方程2x+2y=110Xy=700根据刚学过的知识，很快算出x，解决问题,5,美国初三数学课本内容,另一章是关于几何和讨论三角形性质的。末尾总结了一系列需要解决的问题。学生们毫不怀疑他应用这些定理来解决这些问题。但是这看上去并不是正确的教育之道。问题和方法的关系应该通过问题而不是对方法的讨论而得到。从长远看，这样弊大于利，它使的学生不能独立地思考问题！为了说明这一点，下面举例说明。,6,证明：AD+DBAC+CB,C,D,A,B,7,很明显，三角形内的线段之和必定小于三角形两边之和,有资料为证，此问题给本科生、研究生，甚至数学、工程、计算机方面的教授，他们中不到5%的人能在1个小时内解出这个问题，大部分人需要几个小时，还有些人根本就解不出来！有趣的的是这个问题出自美国5年级课本！如果你不能在1小时之内解决问题，那么此讲座正是为你而做！,8,证明：AD+DBfboundthen从C中移去DiEnd,58,A*算法,在任何给定时刻都采用最好的移动却可能会带来麻烦。比如贪婪法的执行结果并不总是很好，其问题就在于现在是较好的，却不一定是后面所需要的。假若我们有一个评估函数，它能提供足够的信息来避免这些陷阱，那我们就可以使用这种贪婪法以获得更好的性能。这个简单的思想带来了一个叫做“最佳优先”搜索（best-firstsearch）的概念及其扩展形式-A*算法。,59,A*算法与深度优先搜索、广度优先搜索的主要区别,最佳优先搜索探索的是下一个最有希望的结点，而深度优先搜索是以一种任意的模式往尽可能深的地方搜索，而广度优先搜索则搜索完一层中所有的结点后才进入下一层最佳优先搜索使用的是启发式规则，给每个结点提供一个性能值，深度优先搜索和广度优先搜索则不这样做,60,旅行者过桥问题,四个旅行者ABCD夜晚要过一座桥，他们只有一盏老式油灯用作照明，每次最多允许过两人，每人过桥时间不同。A1min，B2min，C5min，D10min两人一起过桥，时间由慢者决定。如何安排最好的组合，使他们花最短的时间过去？,61,给出一个局部最优解,A提着油灯护送每人过桥。A和B一起过桥，2minA自己回来，1minA和C一起过桥，5minA自己回来，1minA和D一起过桥，10min总共19min事实上还有更好的答案，你能找到吗？,62,5跳离局部最优,前面讨论的传统的求解问题的策略，它们中有些能保证找到全局解，有些则不能，但它们都遵循一个共同的模式。那就是，它们或者能够保证找到全局解但在求解一些典型的实际问题时代价太大（太耗时），或者容易“陷入”局部最优。由于很难加速一个能保证找到最优解的算法，即对于大多数实际问题很难找到多项式时间算法（因为它们大多是NP难问题），那么剩下的选择就是设计出能够跳离局部最优的算法。,63,“噢！一匹插上翅膀的骏马！”,爬山法：当到达一个局部最优解后便产生一个新的起始点，搜索重新开始。下面两种方法分别基于：1、一个附加参数（温度），用于改变从搜索空间的一个点移动到另一个点的概率-模拟退火（SimulatedAnnealing，SA）。2、一个记忆装置，用于驱使算法探索搜索空间的新区域-禁忌搜索（tabusearch）。,64,简单爬山法MAX=1,Procedure局部搜索Beginx=S中的某个初始点While（improve（x）“no”）dox=improve（x）返回xend,注：子程序improve（x）从x的邻域返回一个新点y。若y比x好，那么子程序返回这个点的值，否则，返回“no”,65,简化的模拟退火算法,Procedure模拟退火Beginx=S中的某个初始点While（不满足终止条件）dox=improve？（x，T）修改T返回xend,66,模拟退火与局部搜索的区别,过程的终止条件模拟退火执行到满足某个外部的终止条件时停止，而局部搜索则要求找到一个改进解。模拟退火中并不要求函数improve？（x，T）一定返回x邻域的一个更好点，而是返回一个可以接受解y，这依赖于当前温度T。模拟退火中参数T被定期修改，其值直接影响improve？的输出，局部搜索没有此特征。,67,禁忌搜索算法,Procedure禁忌搜索Beginx=S中的某个初始点While（不满足终止条件）dox=improve？（x，H）修改H返回xend,在算法的结构上与模拟退火相同，函数也是返回一个可接受解y，它不一定比x更好，但其接受与否是基于搜索的历史H。,68,你的直觉如何？,对一个复杂的问题试着先猜测一个解，这是人的天性。一些猜测看起来也很直观，并且有些人也似乎更具直觉。你驾车以40km/h的从北京到上海，然后立即返回，车速为60km/h。试问整个旅程的平均速率是多少？,69,华尔街股市著名的诡计,一个狡诈的股票经纪人挑选出1024个人作为可能的客户（受骗者）。每天，给他们邮寄一份有关股市在第二天涨或跌的预测，一直持续10天。到第10天末，一个不幸的受害者会惊异地发现股票经纪人所预测的股市走势百发百中，10次都准确，那么从直觉他感到此人就是“神仙”！问题出在哪儿呢？,70,6演化算法,前面的算法都是以单个解作为每次迭代中进行下次搜索的基础。贪婪算法是通过每次获得局部最大改进来逐步建立解；动态规划在得到最终的完整解之前先求解许多小的子问题；分支定界则将搜索空间组织成一些子空间，然后剔除其中的一些子空间。相反，局部搜索、模拟退火和禁忌搜索则处理完整解。每次迭代都会获得一个局部最优解，下次迭代继续改进。不管区别如何，共同点就是一次只处理或构造一个解。,71,目前的规则,确定性规则：爬山法，如果被检查的邻域解更好，则移动到这个邻域解并从这里开始搜索；否则继续在当前邻域内搜索；概率性规则：模拟退火，如果被检查的邻域解更好，则接受这个解作为新的当前解；否则或者以一定的概率接受这个较差解或继续在当前邻域内搜索；到目前为止搜索的历史：禁忌搜索，接受可得到的最好邻域解，它并不一定要比当前解更好，但是一定不能是列于存储器中的一个受限制的或“禁忌”的移动。,72,基于“种群”的算法,兔子与狐狸在兔子种群里，有些机灵，被吃的可能性较小，因此更容易幸存并繁衍。在繁殖中会保留这些特点。每只幼兔不是双亲的复制体，而是双亲的随机扰动。经过多代之后的兔子就会表现出一些有利于它们同狐狸甚至其他兔子竞争的特性。同时，狐狸也在进化！,73,演化算法的过程,创建一个个体种群，表示所解决问题的潜在解集；评估个体；引入某种选择压力，保留较好个体，淘汰较差个体；应用变化算子产生待测试的新个体。重复执行“评估-选择-变化”的循环若干次。,74,演化算法的优点,大多数经典优化算法采用的是固定的评估函数，对它的任何修改都要重新启动算法。演化算法则是内在适应的，种群中的个体与当前环境相适应。易于与其他算法相结合。并行性一次求解可以返回多个解，供选择。程序设计心理学，你是创造者！,75,这些东西有一个与众不同,有12枚硬币，其中1枚是假币。假币的重量与真币不同，但不知是重还是轻。给你一架天平。用最少的次数，找出这枚假币，并说明它是重还是轻。,76,演化算法设计思想,演化求解问题的基本思想相当简单：由所解决任务的候选解组成一个种群，然后通过随机变化和选择等一代代演化下去。其中随机变化提供了发现新解的机制，选择则确定保持哪些解作为下一步搜索的基础。本质上而言，任何在可能解的状态空间内对点不进行重取样的搜索过程，对于所有问题的平均执行效果相同。一个从不进行重取样的爬山算法在试图寻找函数最大值时，平均效果等同于一个没有重复取样的盲目随机搜索。,77,演化算法描述,大多数演化算法的方程描述：xt+1=s(v(xt),其中xt是以x为表示方式t时刻的种群，v(.)是变化算子，s(.)是选择算子。这个差分方程表示每一代的随机演化过程。过程：产生一个与相关问题的潜在解的种群，设计一些从旧解产生新解的变化算子，并应用选择机制保留那些最好解到当前代。,78,最短路径是什么？,四个城市分别位于正方形的四个顶点，现在的任务是设计一个道路网络，使得每个城市都与其他城市相连接且道路的总长最短。,四个城市位置,79,可能的方案,80,这个答案是最优的！,81,8旅行商问题TSP,将局部最优算法与演化算法结合混合算法基于Karp-Steele算法中的分而治之技术扩展的演化算法边组装杂交算法反序-杂交算法、旅行商问题是一个足以说明一个看似简单的问题如何面临许多意想不到的挑战的典型例子！例如哥德巴赫猜想。,82,斑马问题著名的约束满足问题,五个颜色各异的房子里，住着不同国籍的人，他们饲养的宠物、喜欢喝的饮料以及拥有的汽车也各不相同，加上下面的信息：1、英国人住在红房子里2、西班牙人养狗3、居住在绿房子里的人喝可乐4、乌克兰人喝蛋酒5、绿房子是象牙色房子的右邻,83,6、拥有老爷车的人养蜗牛7、拥有福特车的人住在黄房子里8、住在中间房子里的人喝牛奶9、挪威人住在最左边的房子里10、拥有雪佛莱的人与养狐狸的人是邻居11、拥有福特车的人与养马的人是邻居12、拥有奔驰汽车的人爱喝桔汁13、日本人开大众汽车14、挪威人的邻居住在蓝房子里,84,形式化的表示方法,Aii号房子的颜色Bi住i号房子的人喝的饮料Ci住i号房子的人的国籍Di住i号房子的人拥有的汽车Ei住i号房子的人饲养的宠物,85,变量的取值范围,86,根据条件可以得出,Ifci=Sthenei=D(i=2,3,4,5),87,最后的答案,88,为什么要练习这类问题？,练习解决这种约束满足问题的好处是训练你的逻辑思维，考虑什么是可能的什么是不可能的。这些问题也出现在研究生入学考试中，因此记住一句老生的忠告：提前做好准备吧！如果你已经完成了学业，那么就该庆幸这一切终于过去了！,89,9约束处理技术,现实世界的每个问题都包含约束，你根本无法摆脱这些约束。只有教科书中才可能遇到无约束问题。事实上所有的决策问题都包含约束。正是这些约束的形式使各种类型的问题相互不同。根据问题的表示形式，约束可以表示为规则、数据依赖、代数式或其他形式。,90,蜗牛爬杆,一只蜗牛顺着一根10米高的旗杆往上爬，白天向上爬5米，晚上睡觉下滑4米，问需要多少天蜗牛才能爬到旗杆的顶端？,91,利用空间来描述约束,92,处理约束的最常用的方法,惩罚函数法,93,10针对问题调整算法,渴望一夜暴富的人，一年之内将被绳之以法-L.达芬奇杂记几乎每个实用的启发式搜索算法都由某个参数集控制，但是这些方法中没有哪一个能将一切都封装到一个礼品盒中，让你一打开盒子就可以获得一份惊喜！在缺少理论指导的情况下，最好能找到一种自动优化参数的方法，使得在这些参数的控制下，演化算法能找到更好的解。,94,本章小结,一个演化算法的有效性依赖于它的各个组成部分（表示方式、变化算子等）及其相互作用。影响演化算法的最优化参数设置的主要障碍之一是这些参数之间的非线性相互作用。依赖人的智能和专业技术是设计演化算法（包括参数设计）的最好办法。,95,11随时间变化的环境与噪声,一个二次碗，每个抽样点加入高斯噪声,96,现实世界永远是变化的,在实际问题的求解中，只找到一个解并固守这个解是远远不够的，你必须随着问题的改变不断地寻找新的解。当求解的目标改变时，解也必须随之改变。即使目标随着时间的推移本质上保持不变，然而在竞争的环境中，与竞争对手的目标的交互方式也会发生改变。这就要求根据面对的问题重新考虑解。,97,著名的囚犯两难问题,两个犯人被关在不同房间，检察官分别说：若你们都认罪，判4年；假如你认罪，但他不认罪。你释放，他判5年；你们俩都不认罪，分别2年。,98,数学模型,加入OPEC的国家就像在玩囚犯两难游戏,99,12神经网络,100,13模糊系统,1965年Zadeh提出模糊集理论他描述“年老”的模糊集隶属函数：这不是唯一的隶属函数,101,Zadeh“年老”模糊隶属函数,102,模糊系统的概念与应用,模糊集与概率测度隶属度与隶属函数模糊集运算与模糊关系模糊控制器模糊聚类模糊神经网络模糊TSP演化模糊系统,103,你喜欢简单的解决办法吗？,两个杯子分别盛水和果汁，体积相等。取一匙果汁放入水中，搅拌后再取一匙混合液体放回装果汁的杯中。问：水中的果汁与果汁中的水哪一个更多？,104,这一个例子也很有说服力,要举行一个由937名选手参加的网球锦标赛，获胜的选手可以继续比赛，失利的选手将被淘汰。为了完成这个锦标赛需要进行多少场比赛？,105,一般的计算方法,锦标赛的全部场次（87名种子选手）：1+2+4+8+16+32+64+128+256+425=936,决赛,半决赛,1/4决赛,106,答案可以这样计算！,因为一场比赛只淘汰1名选手，因此在有n名选手参加的锦标赛中，必须淘汰n-1名选手而产生1名胜者，因此需要进行n-1场比赛。所以937名选手，需要936场比赛！,107,等分问题,一个正方形分成相等的四部分，OK右边的图，如何分成相等的四部分？,108,原来如此！,再出问题：右边的正方形，如何分成相等的五部分？,109,14混合系统,没有任何单个算法称得上是解决所有问题的最好方法。必须将问题的有关知识以某种有用的方式结合到算法中；否则，它比随机搜索好不到哪里去。解决这个问题的一种方式是将演化算法与更多的标准过程相混合。总之，将演化算法与其他过程相结合的混合方法多种多样。,110,计算智能会议上的经典玩笑,一篇文章的标题用于改善对于定义了数据挖掘中生成专家系统的一个递归规则集的树的禁忌搜索中的记忆规则的一种自适应的贪婪的神经-模糊-演化-退化方法,你可以创造任意多的其他可能性。诀窍在于知道如何巧妙地找到不同方法之间的协同性，使整个方法尽可能地简洁。,111,本章小结,演化算法提供了一种特别灵活的求解问题的方法。不仅可以将它们与更多的传统算法相混合，还可以通过从多方面对他们进行扩充。多种群、记忆、个体学习、群体学习、人工鱼群以及众多想法都可以被合成进去。事实上，你无所不能，当然有时想象力的匮乏会使你裹足不前。,112,没有免费的午餐,这种灵活性很有价值。但根据“没有免费的午餐定理”，没有一个算法能最好地解决所有问题。尽管从理论上讲，混合系统本身具有一定的魅力，但是我们应当把精力集中于解决问题，而不是去进行各种精巧而无用的模拟。不管白猫黑猫抓住老鼠就是好猫！,113,15总结,食人者使用刀叉，算不算进步？-StanislawLee散思集面临问题是，首先要问的是“我的目标是什么？”求解是一门艺术，就像追求艺术需要付出努力一样，它需要实践。使自己真正变得擅长求解问题的一个办法就是不断地用