2 背景

搜索是一种电脑可以找到解决问题的内在手段。对于问题的小型搜索空间，搜索可以成为一种一个解决办法的有效途径，特别是使用一个已知的搜索算法。这意味着，可避免专门关注这个问题书写了新的算法。搜索也是一个找到缺乏高效的算法问题的有用的手段。许多完全NP问题属于这一类问题。虽然搜索不能解决棘手，复杂的问题，在许多情况下，它最终将找到可以接受的很好的解决方案- 而且往往比可能的枚举要好。

过去传统的办法来解决给定的搜索或优化问题要适应一套搜索算法和参数并执行，比较实证和分析结果。直觉上，如果某一特定搜索算法显示更好的结果，可以说，搜索算法是更加适应所定义的搜索空间的问题的，至少在对比的替代搜寻技术的测试。

探索各种搜索技术问题的需要从大多数问题的本质上看，搜索是困难的。那个由Wolpert和Macready指出没有免费的午餐（NFL）的定理显示，通过所有的搜索问题的空间，没有搜索算法优于随机搜索或例举 。类似的结果已经在优化问题中显示出。NFL定理在理论上是无可辩驳的，但一个反论点的影响是空间的所有的搜索问题是的兴趣不大。相反，现实世界的问题关系到大多数人都结构和规律，如果不具有挑战性，搜索空间。

再重申NFL定理进化计算， Culberson还指出问题的计算复杂性理论甚至强于NFL定理。 完全NP问题和其他棘手的问题是有结构、完全明确。这种结构不能利用搜索-或任何已知的算法-解决NP完全问题。然而，棘手的问题（如著名的旅行商问题）通常采用的测试问题搜索算法和其他软件计算技术。虽然解决这些问题将不会被即将在大多数情况下，我们往往是兴趣获得合理的解决办法，以已知个案。在软计算领域这是一个积极的工作，在这种启发下，这种方法用于查找难处理问题近似的解决方案。因此，搜索算法可以非常实际的找到难处理问题的答案。我们面临的挑战是给当前问题找到一个优秀的搜索算法。

使用元启发式搜索是企图自动发现有用的搜索算法的模式和参数。在遗传算法中，一种办法是将包括搜索参数内搜索问题的代表性，让搜索机制找到一个有用的参数。这就是所谓的自适应遗传算法。一个典型的例子是福格蒂的研究，它适应在运行中的突变率。良，姚和牛顿讨论自我适应的步长在evoltionary算法中的使用。Ombuki, Nakamura and Onaga运用遗传算法对完全NP问题进行调度。在其gkGA算法，三种不同的启发式战略，以解决调度解决方案中染色体编码问题。这些战略必须遵守同样的演变的影响其余问题的代表性。他们表明，更好的整体性能得到允许的搜索算法，发现适当的僵局启发式。

在文中的遗传规划中，元搜索或元进化也被研究，并且常常关系到新的变异算子特勒使用共同进化产生复制算子被用于主程序的并行算法[ 17 ] 。 Angeline [ 1 ] ，和IBA和德盖瑞斯[ 7 ] ，利用自适应进化交叉算子适应正在运行的程序。埃德蒙兹探讨共同进化的变异算子，如交叉[ 3 ] 。在所有这些文件，变异的元进化算子能够适应特定的问题，使用通用的算子，有利于更好地性能相比。

也许在元搜索最有贡献的例子是Spector和Robinson的研究工作了。他们把基于堆栈的语言应用于遗传规划，这个程序可以访问和处理它们。研究的目标之一就是看问题是不是收敛的。