更改

===搜索和优化===

===搜索和优化===

Many problems in AI can be solved in theory by intelligently searching through many possible solutions:<ref name="Search"/> [[#Deduction, reasoning, problem solving|Reasoning]] can be reduced to performing a search. For example, logical proof can be viewed as searching for a path that leads from [[premise]]s to [[Logical consequence|conclusions]], where each step is the application of an [[inference rule]].<ref name="Logic as search"/> [[Automated planning and scheduling|Planning]] algorithms search through trees of goals and subgoals, attempting to find a path to a target goal, a process called [[means-ends analysis]].<ref name="Planning as search"/> [[Robotics]] algorithms for moving limbs and grasping objects use [[local search (optimization)|local searches]] in [[Configuration space (physics)|configuration space]].<ref name="Configuration space"/> Many [[machine learning|learning]] algorithms use search algorithms based on [[optimization (mathematics)|optimization]].

对于大多数真实世界的问题，简单的穷举搜索<ref name="Uninformed search"/>很难满足要求: 搜索空间(要搜索的位置数)很快就会增加到天文数字。结果就是搜索速度太慢或者永远不能完成。对于许多问题，解决方法是使用“'''启发式 Heuristics''' ”或“'''经验法则 Rules of Thumb''' ” ，优先考虑那些更有可能达到目标的选择，并且在较短的步骤内完成。在一些搜索方法中，启发式方法还可以完全移去一些不可能通向目标的选择(称为“修剪搜索树”)。<ref name="Informed search"/>启发式为程序提供了解决方案所在路径的“最佳猜测”。<ref name="Russell & Norvig 2003"/><ref name="Poole, Mackworth & Goebel 1998"/><ref name="Luger & Stubblefield 2004"/><ref name="Nilsson 1998"/>启发式把搜索限制在了更小的样本规模里。<ref name ="Tecuci 2012>Tecuci, Gheorghe (March–April 2012). "Artificial Intelligence". Wiley Interdisciplinary Reviews: Computational Statistics. 4 (2): 168–180. doi:10.1002/wics.200</ref>

对于大多数真实世界的问题，简单的穷举搜索<ref name="Uninformed search"/>很难满足要求: 搜索空间(要搜索的位置数)很快就会增加到天文数字。结果就是搜索速度太慢或者永远不能完成。对于许多问题，解决方法是使用“'''启发式 Heuristics''' ”或“'''经验法则 Rules of Thumb''' ” ，优先考虑那些更有可能达到目标的选择，并且在较短的步骤内完成。在一些搜索方法中，启发式方法还可以完全移去一些不可能通向目标的选择(称为“修剪搜索树”)。<ref name="Informed search"/>启发式为程序提供了解决方案所在路径的“最佳猜测”。启发式把搜索限制在了更小的样本规模里。

[[File:ParticleSwarmArrowsAnimation.gif|thumb|粒子群搜索全局最小]]

 

[[演化计算]]用到了优化搜索的形式。例如，他们可能从一群有机体(猜测)开始，然后让它们变异和重组，选择适者继续生存 (改进猜测)。经典的演化算法包括遗传算法、基因表达编程和遗传编程。<ref name="Luger & Stubblefield 2004"/><ref name="Nilsson 1998"/><ref name="Holland, John H. (1975)">Holland, John H. (1975). Adaptation in Natural and Artificial Systems. University of Michigan Press. ISBN 978-0-262-58111-0.</ref><ref name="Koza, John R. (1992)">Koza, John R. (1992). Genetic Programming (On the Programming of Computers by Means of Natural Selection). MIT Press. Bibcode:1992gppc.book.....K. ISBN 978-0-262-11170-6.</ref><ref name="Poli(2008)">Poli, R.; Langdon, W. B.; McPhee, N. F. (2008). A Field Guide to Genetic Programming. Lulu.com. ISBN 978-1-4092-0073-4 – via gp-field-guide.org.uk.</ref>或者，分布式搜索过程可以通过群智能算法进行协调。搜索中使用的两种流行的群算法是粒子群优化（禽流启发植绒和）蚁群优化（灵感来源于蚂蚁小径）。<ref name="Society based learning"/><ref>{{cite book|author1=Daniel Merkle|author2=Martin Middendorf|editor1-last=Burke|editor1-first=Edmund K.|editor2-last=Kendall|editor2-first=Graham|title=Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques|date=2013|publisher=Springer Science & Business Media|isbn=978-1-4614-6940-7|language=en|chapter=Swarm Intelligence}}</ref>

A very different kind of search came to prominence in the 1990s, based on the mathematical theory of [[optimization (mathematics)|optimization]]. For many problems, it is possible to begin the search with some form of a guess and then refine the guess incrementally until no more refinements can be made. These algorithms can be visualized as blind [[hill climbing]]: we begin the search at a random point on the landscape, and then, by jumps or steps, we keep moving our guess uphill, until we reach the top. Other optimization algorithms are [[simulated annealing]], [[beam search]] and [[random optimization]].<ref name="Optimization search"/>

 

在20世纪90年代，一种非常不同的基于数学最优化理论的搜索引起了人们的注意。对于许多问题，可以从某种形式的猜测开始搜索，然后逐步细化猜测，直到无法进行更多的细化。这些算法可以喻为盲目地爬山: 我们从地形上的一个随机点开始搜索，然后，通过跳跃或登爬，我们把猜测点继续向山上移动，直到我们到达山顶。其他的优化算法有 '''模拟退火算法''' 、'''定向搜索''' 和'''随机优化''' 。<ref name="Optimization search"/>

 

 

 

 

 

 

 

[[Evolutionary computation]] uses a form of optimization search. For example, they may begin with a population of organisms (the guesses) and then allow them to mutate and recombine, [[artificial selection|selecting]] only the fittest to survive each generation (refining the guesses). Classic [[evolutionary algorithms]] include [[genetic algorithms]], [[gene expression programming]], and [[genetic programming]].<ref name="Genetic programming"/> Alternatively, distributed search processes can coordinate via [[swarm intelligence]] algorithms. Two popular swarm algorithms used in search are [[particle swarm optimization]] (inspired by bird [[flocking (behavior)|flocking]]) and [[ant colony optimization]] (inspired by [[ant trail]]s).<ref name="Society based learning"/><ref>{{cite book|author1=Daniel Merkle|author2=Martin Middendorf|editor1-last=Burke|editor1-first=Edmund K.|editor2-last=Kendall|editor2-first=Graham|title=Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques|date=2013|publisher=Springer Science & Business Media|isbn=978-1-4614-6940-7|language=en|chapter=Swarm Intelligence}}</ref>

 

 

[[演化计算]]用到了优化搜索的形式。例如，他们可能从一群有机体(猜测)开始，然后让它们变异和重组，选择适者继续生存 (改进猜测)。经典的演化算法包括遗传算法、基因表达编程和遗传编程。<ref name="Genetic programming"/> Alternatively, distributed search processes can coordinate via [[swarm intelligence]] algorithms. Two popular swarm algorithms used in search are [[particle swarm optimization]] (inspired by bird [[flocking (behavior)|flocking]]) and [[ant colony optimization]] (inspired by [[ant trail]]s).<ref name="Society based learning"/><ref>{{cite book|author1=Daniel Merkle|author2=Martin Middendorf|editor1-last=Burke|editor1-first=Edmund K.|editor2-last=Kendall|editor2-first=Graham|title=Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques|date=2013|publisher=Springer Science & Business Media|isbn=978-1-4614-6940-7|language=en|chapter=Swarm Intelligence}}</ref>