English  |  正體中文  |  简体中文  |  Items with full text/Total items : 43312/67235
Visitors : 2106436      Online Users : 6
RC Version 5.0 © Powered By DSPACE, MIT. Enhanced by NTU/NCHU Library IR team.
National Chung Hsing University Institutional Repository - NCHUIR > 理學院 > 資訊網路與多媒體研究所 > 依資料類型分類 > 碩博士論文 >  多軌跡搜尋演算法解多目標的無限容量設施選址問題以及多目標的背包問題

Please use this identifier to cite or link to this item: http://nchuir.lib.nchu.edu.tw/handle/309270000/154562

標題: 多軌跡搜尋演算法解多目標的無限容量設施選址問題以及多目標的背包問題
Multiple Trajectory Search Algorithms for Multi-objective Unconstrained Facility Location Problem and Multi-objective 0-1 Knapsack Problem
作者: 余奕德
I-TE, YU
Contributors: 曾怜玉
資訊網路多媒體研究所
關鍵字: 多軌跡搜尋演算法;基因演算法;背包問題;無限容量設施選址問題
Multi-objective 0-1 knapsack problem;multi-objective unconstrained facility location problem;genetic algorithm;multiple trajectory search;NP-Hard problem
日期: 2012
Issue Date: 2013-11-21 10:56:42 (UTC+8)
Publisher: 資訊網路多媒體研究所
摘要: 多目標背包問題以及多目標無限容量設施選址問題均為NP-Hard問題,近年有許多學者用演化式演算法來解這兩個問題,其解都可以二元序列表示。

背包問題的主要目標為從各種價值以及重量皆相異的物品中,挑選出一組物品集合,使此集合總價值最大且總重量不超過背包容量。在演算法領域是一個熱門的研究範疇,且在硬體設計、存貨切割、資金編列預算等最佳化問題上有諸多應用。無限容量設施選址問題則有一組顧客所在點以及潛在設施點,主要目標為挑選一個開啟設施組合,使整體開店成本最小且利潤最大,在現實生活中例如工廠設廠或商店選址開店皆有許多不同的應用。

在本論文中,我們使用一以基因演算法作為主要架構的多軌跡搜尋演算法來解此二問題,並針對目前在相同領域的相關研究其遇到的瓶頸,例如缺乏深度搜尋導致解品質欠佳以及缺乏動態調整搜尋範圍機制等弱點加以改進。我們也應用本論文所提出的多軌跡搜尋演算法於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.
Appears in Collections:[依資料類型分類] 碩博士論文

Files in This Item:

File Description SizeFormat
nchu-101-7099083013-1.pdf1310Kb357View/Open
index.html0KbHTML160View/Open


 


學術資源

著作權聲明

本網站為收錄中興大學學術著作及學術產出,已積極向著作權人取得全文授權,並盡力防止侵害著作權人之權益。如仍發現本網站之數位內容有侵害著作權人權益情事者,請權利人通知本網站維護人員,將盡速為您處理。

本網站之數位內容為國立中興大學所收錄之機構典藏,無償提供學術研究與公眾教育等公益性使用。

聯絡網站維護人員:wyhuang@nchu.edu.tw,04-22840290 # 412。

DSpace Software Copyright © 2002-2004  MIT &  Hewlett-Packard  /   Enhanced by   NTU/NCHU Library IR team Copyright ©   - Feedback