在本論文中，我們使用一以基因演算法作為主要架構的多軌跡搜尋演算法來解此二問題，並針對目前在相同領域的相關研究其遇到的瓶頸，例如缺乏深度搜尋導致解品質欠佳以及缺乏動態調整搜尋範圍機制等弱點加以改進。我們也應用本論文所提出的多軌跡搜尋演算法於Eckart Zitzler 與 Lothar Thiele在1999年時所提出的多目標背包問題測試題組以及我們自製的多目標無限容量設施選址問題的測試題組，和其他演算法進行比較，均獲得不錯的結果。 Both the multi-objective 0-1 knapsack problem and the multi-objective unconstrained facility location problem are NP-Hard problems. The solutions to both problems can be represented by binary sequence.
The knapsack problem is defined as follows. Given a set of items, each item has its own weight and value, We want to select a collection of items such that the total weight of these items is less than or equal to a given weight limit and the total value is as large as possible. The knapsack problem is a popular research topic in the algorithm flied with many applications such as the hardware design, the stock cutting, and the budget problem.
The unconstrained facility location problem is defined as follows. Given a set of potential facility locations and a set of customers, We want to choose a set of facility locations to open such that the cost is minimized. It is a popular research topic in the business flied.
In this thesis, we propose a new Multiple Trajectory Search(MTS) algorithm which is based on the genetic algorithm and apply this new algorithm to both problems. The proposed algorithm tries to search the solution space more systematically and more thoroughly.
The proposed Multiple Trajectory Search was applied to the knapsack benchmark instances proposed by Eckart Zitzler and Lothar Thiele in 1999 and the result were compared with other state-of-the-art methods. Revealed by the experimental results, the MTS is very competitive with other algorithms on the multi-objective 0-1 knapsack problem.