Exploiting commonality in heuristic search

利用启发式搜索中的共性

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

启发式搜索技术是一种系统的方法，用于探索一个最能实现某个目标的解决方案的一个可能的解决方案。 例如，在婚宴上安排宾客的方式有很多种，但新婚夫妇仍然需要很长时间才能找到一个双方都能接受的解决方案。对于这个问题，大多数夫妇会使用迭代改进的形式-从一个解决方案开始，对它进行修改以创建新的解决方案，进行额外的修改，等等，直到找到最终可接受的解决方案。 启发式搜索技术，如遗传算法，模拟退火，禁忌搜索等都是执行迭代改进的方法。 具体地说，这些搜索技术都采用了“改变操作符”（创建新解决方案的方法）和“控制策略”（控制接受哪些新解决方案的方法）。 例如，你可能建议交换两张桌子，你的伴侣可能会说“不，那更糟”或“是的，但这仍然需要解决”。