簡易檢索 / 詳目顯示

回結果列表
研究生： 石大維
論文名稱： 以多目標與限制最佳化觀點求解競賽旅程問題
Solving the Traveling Tournament Problem by Constrained Multiobjective Optimization
指導教授： 蔣宗哲
學位類別： 碩士
Master
系所名稱： 資訊工程學系
Department of Computer Science and Information Engineering
論文出版年： 2013
畢業學年度： 101
語文別： 中文
論文頁數： 62
中文關鍵詞： 競賽旅程問題 、變動鄰域 、模擬退火法 、限制處理機制 、多目標最佳化
論文種類： 學術論文
相關次數： 點閱：126  下載：10 
分享至:
查詢本校圖書館目錄 查詢臺灣博碩士論文知識加值系統 勘誤回報

    • 　　運動時間表問題 (Sport Timetabling Problem) 一直以來都是一個相當困難的問題，其影響的因素五花八門，像是運動員的需求、場館間的距離、商業和廣告的考量等等。其中針對球隊旅行產生了競賽旅程問題 (Traveling Tournament Problem)，本論文針對這樣的問題做研究。該問題原本為一個單目標最佳化問題，本論文將此問題發展為多目標最佳化問題，藉由此方式讓使用者能夠有多元的選擇，例如選擇一個總距離並非最短，但是能讓所有的隊伍移動距離較為平均的解。
    　　本論文提出群體式多鄰域模擬退火法 (Population-based Multi Neighborhood Simulated Annealing, PMNSA) ，其中使用變動鄰域搜尋法 (Variable Neighborhood Search) 與隨機選擇鄰域函式做比較，希望能找到一種效能較好的做法，接著使用模擬退火法 (Simulated Annealing) 以及群體式的 (population-based) 概念去搜尋，另外也改良過去競賽旅程問題所使用的鄰域函式，並比較其改良前後搜尋解空間的能力，藉由此方式提高搜尋的效能。在限制處理機制的部分採用原先單目標常用的懲罰函數 (penalty function) 以及ϵ-constraint做比較，並找到一個最適合此多目標最佳化問題的限制處理機制。最後本論文列出目前找到的多目標最佳解，以供之後做比較。

    誌謝 i 中文摘要 ii 目錄 iii 附表目錄 vii 附圖目錄 ix 第一章 緒論 1 1.1 研究動機 1 1.1.1 競賽旅程問題 1 1.1.2 鏡像競賽旅程問題 3 1.2 背景知識 4 1.2.1 啟發式演算法 4 1.2.2 多目標最佳化問題 5 1.2.3 限制處理機制 6 1.3 研究目的與貢獻 7 第二章 文獻探討 9 2.1 常見鄰域函式 9 2.2 區域搜尋法 14 2.2.1 模擬退火法 [5] [7] [8] 14 2.2.2 禁忌搜尋法 [9] 18 2.2.3 螞蟻演算法 [10] 18 2.2.4 迭代區域搜尋法 [11] 19 2.2.5 混和式區域搜尋演算法 [12] 23 2.3 群體式搜尋法 24 2.3.1 基因演算法 [13] 24 2.3.2 文化基因演算法 [14] 25 第三章 群體式多鄰域模擬退火法 27 3.1 產生初始化 (Initialize solution) 29 3.2 適應度評估 (Fitness function) 29 3.2.1 多目標處理機制 29 3.2.2 限制處理機制 31 3.2.2.1 懲罰函數 31 3.2.2.2 ε-constraint 32 3.3 迭代改良 (Iterative Improvement) 32 3.3.1 迭代改良 32 3.3.2 解評估方式 33 3.3.3 鄰域函式 33 3.4 變動鄰域模擬退火法 (Variable Neighborhood Simulated Annealing, VNSA) 33 3.5 更新候選解集合 (Update candidate solution set) 38 3.6 代數改變 (Generation change) 39 3.7 終止條件 (Stopping criterion) 39 第四章 實驗與分析 41 4.1 測試問題 41 4.2 效能指標 41 4.3 測試環境 41 4.4 參數設定 42 4.5 單目標最佳化實驗 43 4.5.1 迭代改良與模擬退火法比較 43 4.5.2 變動鄰域函式與隨機鄰域函式比較 45 4.5.3 改良後鄰域函式與改良前鄰域函式比較 46 4.5.4 變動鄰域函式順序比較 47 4.5.5 策略震盪與無策略震盪比較 50 4.5.6 懲罰值實驗 50 4.5.7 與現有最佳解比較 51 4.6 多目標最佳化實驗 52 4.7 ϵ-constraint實驗 56 第五章 結論與未來展望 59 參考文獻 61

    [1] K. Easton, G. Nemhauser, and M.A. Trick. (2001) The traveling tournament problem: description and benchmarks. T.Walsh (Ed.), Principles and Practice of Constraint Programming, Lecture Notes in Computer Science, 2239, 580–584.
    [2] K. Deb, A. Pratap, S. Agarwal, and T. Meyarivan. (2002, April) A fast and elitist multiobjective genetic algorithm: NSGA-II. IEEE Transactions on Evolutionary Computation, 6(2), 182 – 197.
    [3] E. Zitzler, M. Laumanns, and L. Thiele. (2001) SPEA2-Imprving the strength pareto evolutionary algorithm. Computer Engineering and Networks Laboratory (TIK), Report 103.
    [4] Q. Zhang, and H. Li. (2007) MOEA/D: A multiobjective evolutionary algorithm based on decomposition. IEEE Transations on Evolutionary Computation, 11 (6), 712 – 731.
    [5] A. Anagnostopoulos, L. Michel†, P.V. Hentenryck, and Y. Vergados. (2006) A simulated annealing approach to the traveling tournament problem. Journal of Scheduling, 9 (2), 177 – 193.
    [6] G. Langford. (2010) An improved neighbourhood for the traveling tournament problem. Arxiv preprint arXiv:1007.0501.
    [7] A. Lim, B. Rodrigues, and X. Zhang. (2006) A simulated annealing and hill-climbing algorithm for the traveling tournament problem. European Journal of Operational Research, 174 (3), 1459 – 1478.
    [8] P.V. Hentenryck, Y. Vergados. (2007) Population-based simulated annealing for traveling tournaments. Proceedings of the 22nd national conference on Artificial intelligence, 267 – 272.
    [9] L.D. Gaspero, and A. Schaerf. (2007) A composite-neighborhood tabu search approach to the traveling tournament problem. Journal of Heuristics, 13 (2), 189 – 207.
    [10] P.C. Chen, G. Kendall, and G.V. Berghe. (2007) An ant based hyper-heuristic for the travelling tournament problem. 2007. SCIS '07. IEEE Symposium on Computational Intelligence in Scheduling, 1 (5), 19 – 26.
    [11] C.C. Ribeiro, and S. Urrutia. (2007) Heuristics for the mirrored traveling tournament problem. European Journal of Operational Research, 179 (3), 775 – 787.
    [12] W. Wei, S. Fujimura, X. Wei, and C. Ding. (2010) A hybrid local search approach in solving the mirrored traveling tournament problem. IEEE 17Th International Conference on In Industrial Engineering and Engineering Management (IE&EM), 620 – 624.
    [13] N.S. Choubey. (2010) A novel encoding scheme for traveling tournament problem using genetic algorithm. IJCA Special Issue on Evolutionary Computation, 2, 79 – 82.
    [14] F.L. Biajoli, and L.A.N. Lorena. (2006) Mirrored traveling tournament problem: an evolutionary approach. Lecture Notes in Computer Science, 4140, 208 – 217.
    [15] M.A.M. de Carvalho, and L.A.N. Lorena. (2012) New models for the mirrored traveling tournament problem. Computers & Industrial Engineering, 63 (4), 1089 – 1095.
    [16] Challenge traveling tournament instances. http://mat.gsia.cmu.edu/TOURN/
    [17] D.C. Uthus, P.J. Riddle, and H.W. Guesgen. (2012) Solving the traveling tournament problem with iterative-deepening A∗. Journal of Scheduling,15 (5) ,601 – 614.

    下載圖示
    QR CODE