207 組合せ最適化問題における Proximate Optimality Principle を考慮した Tabu Search の探索効率改善

概要

論文の詳細を見る
Most of the actual problems with discrete mechanism can be formulated as a combinatorial optimization problem such as system scheduling problems. While many combinatorial optimization problems are supposed to be NP-Hard from the view point of complexity in a calculation theory. This means that it is extremely hard to obtain a strictly optimal solution within feasible computation time. Meta-heuristics is a new paradigm that aims to obtain an approximate solution within feasible computation time. In the meta-heuristics, Tabu search is one of the most effective algorithms for combinatorial optimization problems. While the intensification of Tabu Search is powerful, the diversification Tabu Search is not powerful. This paper proposes an algorithm-Tabu Search with multi-criteria for coordinating the intensification and diversification that takes a Proximate Optimality Principle (POP) into consideration-has several important features for solving combinatorial optimization problems. The Tabu Search with multi-criteria has two purpose, the value of objective functions and the evaluation of operations, these enable to achieve well-balanced search. The proposed algorithm is applied to Traveling Salesman Problems, that is typical combinatorial optimization problem, to verify the performance of search.
一般社団法人日本機械学会の論文
2002-10-04