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.