Exploiting commonality in heuristic search

启发式搜索技术是一种系统的方法，用于探索大量可能的解决方案，以获得最能实现某些目标的一个解决方案。例如，在婚宴上安排客人的方法有很多，但新婚夫妇仍然要花很长时间才能找到一个他们都能同意的。对于这个问题，大多数夫妇会使用一种迭代改进的形式——从一个解决方案开始，对它进行修改以创建一个新的解决方案，进行额外的修改，等等，直到找到一个最终的可接受的解决方案。启发式搜索技术，如遗传算法、模拟退火、禁忌搜索等，都是进行迭代改进的方法。具体地说，这些搜索技术都使用“更改操作符”（创建新解决方案的方法）和“控制策略”（控制接受哪些新解决方案的方法）。例如，你可能建议换两张桌子，你的伴侣可能会说“不，那更糟”或“是的，但这仍然需要解决”。启发式搜索技术往往是由它们的控制策略来定义的，它们的更改操作符往往或多或少是相同的——取一个候选解决方案并对其进行更改。理想情况下，更改的解决方案组件应该是需要改进的东西，而保留的解决方案组件应该是相当好的东西。然而，大多数更改操作符只检查他们更改的内容。最近提出的共性假设（来自遗传算法）表明，“好”解决方案的共性组件是应该保留的东西。例如，所有把你伴侣的父母放在前面的桌子安排都是可以接受的，所以这可能是没有成效的改变。不幸的是，许多启发式搜索技术（例如模拟退火和禁忌搜索）只适用于单个解决方案，因此它们的更改操作符通常无法访问这些“历史”信息。因此，探索共性保存在启发式搜索技术中的作用可能会导致新的技术独立的想法，如何改进它们。

Heuristic search techniques are systematic methods to explore a large set of possible solutions for the one solution that best achieves some objective.  For example, there are many ways to arrange guests at a wedding reception, but it can still take newlyweds a long time to find one that they can both agree on.  For this problem, most couples would use a form of iterative improvement - start with one solution, make changes to it to create a new solution, make additional changes, etc, until a final acceptable solution is found.   Heuristic search techniques such as genetic algorithms, simulated annealing, tabu search, etc are all methods that perform iterative improvement.  Specifically, these search techniques all employ "change operators" (methods to create new solutions) and "control strategies" (methods to control which new solutions are accepted).  For example, you might suggest swapping two tables, and your partner might say "no, that's worse" or "yes, but this still needs to be addressed".    Heuristic search techniques tend to be defined by their control strategies, and their change operators tend to be more or less the same - take a candidate solution and make changes to it.  Ideally, the solution components that are changed should be things that need improvement, and the solution components that are kept should be the things that are pretty good.  However, most change operators only examine the things that they change.    The recently developed Commonality Hypothesis (from genetic algorithms) suggests that solution components that are common to "good" solutions are the things that should be kept.  For example, all table arrangements that place your partner's parents at the front have been accepted, so this is something that might be unproductive to change.  Unfortunately, many heuristic search techniques (e.g. simulated annealing and tabu search) only work with a single solution, so their change operators do not normally have access to this "historic" information.  Thus, exploring the role of commonality preservation in heuristic search techniques may lead to new technique-independent ideas on how to improve them.