ホーム 書籍 電子書籍 ジャーナル 参考文献と会報 著者、編集者、レビュー者 A-Z商品インデックス 各受賞
Flexible Automation and Intelligent Manufacturing,  1997:<br>Proceedings of the Seventh International FAIM Conference

ISBN:
978-1-56700-089-4 (印刷)
978-1-56700-442-7 (オンライン)

PLUG AND PLAY FRAMEWORK FOR COMBINATORAL PROBLEM HEURISTICS

Andrew Wooster
Panasonic Technologies Kyushu Matsushita Electric Research Lab Research Triangle Park, NC, USA

要約

Combinatorial problems such as the traveling salesperson, assignment and set-covering problems often rear their heads in process optimization. Because these problems are NP-hard, it remains unlikely that they will yield global optima at reasonable computational cost. Therefore, we must rely on heuristic techniques which seek good, albeit sub-optimal, solutions at an acceptable cost. To this end, meta-heuristic search strategies are interesting because they require very little problem specific knowledge. What little they do need to know about a problem can be encapsulated in a neighborhood operator which provides a mechanism for seeking local optima. Unfortunately, these operators can be very difficult to implement and in this paper we define a practical interface for enumerating neighbors. Once a neighborhood operator has been defined, dynamic strategy selection becomes possible. This means that meta-heuristic strategies, such as simulated annealing and tabu search, can be plugged into problem contexts at run-time.