Human-Guided Tabu Search
We have extended past work on human-in-the-loop optimization, allowing human users to guide a more powerful search algorithm, called "tabu" search. Â Â There are two advantages of tightly integrating human judgement in the process of optimization. First, the human users can guide systems to solutions that satisfy various real-world constraints. Second, human users can use their visual skills, ability to learn, and strategic sense to improve the performance of the computer search algorithm.
Background & Objective: The motivation of this project is to combine the skills of people and computers to better solve hard combinatorial problems, such as scheduling or vehicle routing problems. In our previous work, users could invoke only a simple, exhaustive algorithm, known as "hill-climbing". We have extended our approach so that users can also guide a more powerful, heuristic search.
Technical Discussion: In our system, the users control the computer's search algorithm by assigning "priorities" to elements of the current solution (e.g., operations in jobshop scheduling, or customers in vehicle routing problems.) Â These priorities constrain the set of possible modifications that the search algorithm will consider, thus allowing the user to focus the search algorithm on promising areas of the search space. We have developed a version of tabu search that can be constrained by the same priority mechanisms as exhaustive search. Furthermore, this algorithm can itself be encoded as a function which continually adjusts the priorities, thus making tabu search easy to implement in our systems. Our initial results indicate that human-guided tabu search is superior to unguided tabu search. And, users can find significantly better solutions when given tabu search in addition to exhaustive search. Using our new system, we have already found new best solutions to benchmark vehicle-routing problems found on the web.
| Technical Reports: | |
| Teaching Applied Computing without Programming: A Case-Based Introductory Course for General Education | |
Technology Areas:
Sensor and Data Systems
Artificial Intelligence
Modification Date: January 23, 2007