Exploiting commonality in heuristic search

利用启发式搜索中的共性

• 批准号: 249927-2007
• 负责人: Chen, Stephen
• 金额: $ 0.58万
• 依托单位: York University
• 依托单位国家: 加拿大
• 项目类别: Discovery Grants Program - Individual
• 财政年份: 2007
• 资助国家: 加拿大
• 起止时间: 2007-01-01 至 2008-12-31
• 项目状态: 已结题
• 来源: https://www.nserc-crsng.gc.ca/ase-oro/Details-Detailles_eng.asp?id=362303
• 关键词: Exploiting; commonality; 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.

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