以基因演算法應用於賽事時程表之最佳化問題

以作者查詢圖書館館藏

、以作者查詢臺灣博碩士

、以作者查詢全國書目

、勘誤回報

、線上人數：34

、訪客IP：18.224.20.254

姓名

張哲軒(Che-Hsuan Chang) 查詢紙本館藏

畢業系所

資訊工程學系

論文名稱

以基因演算法應用於賽事時程表之最佳化問題
(The Application of the Genetic Algorithm in Solving the Tournament Scheduling Problem)

相關論文

★ 以Q-學習法為基礎之群體智慧演算法及其應用	★ 發展遲緩兒童之復健系統研製
★ 從認知風格角度比較教師評量與同儕互評之差異：從英語寫作到遊戲製作	★ 基於檢驗數值的糖尿病腎病變預測模型
★ 模糊類神經網路為架構之遙測影像分類器設計	★ 複合式群聚演算法
★ 身心障礙者輔具之研製	★ 指紋分類器之研究
★ 背光影像補償及色彩減量之研究	★ 類神經網路於營利事業所得稅選案之應用
★ 一個新的線上學習系統及其於稅務選案上之應用	★ 人眼追蹤系統及其於人機介面之應用
★ 結合群體智慧與自我組織映射圖的資料視覺化研究	★ 追瞳系統之研發於身障者之人機介面應用
★ 以類免疫系統為基礎之線上學習類神經模糊系統及其應用	★ 基因演算法於語音聲紋解攪拌之應用

檔案

[Endnote RIS 格式]

[Bibtex 格式]

[相關文章]

[文章引用]

[完整記錄]

[館藏目錄]

[檢視]

[下載]

本電子論文使用權限為同意立即開放。
已達開放權限電子全文僅授權使用者為學術研究之目的，進行個人非營利性質之檢索、閱讀、列印。
請遵守中華民國著作權法之相關規定，切勿任意重製、散佈、改作、轉貼、播送，以免觸法。

摘要(中)

要舉辦一場賽事除了主辦單位、參賽選手和比賽場地之外，賽事時程表也是不可或缺的一環。賽事時程表規劃每場比賽的開始時間、結束時間和進行的場館與場地資訊。而編排一個賽事時程表需要考慮許多限制條件，如：賽事進行的日期、比賽時間及可用場地總數，且為了比賽的公平性，參賽選手於比賽間需要有充足的休息時間。
本論文針對賽事時程表的編排問題，參考實際賽事的編排結果及編排人員的編排方式，設計一套能編排各種規模賽事時程表的最佳化演算法。以賽程中的輪次為單位，透過編排賽程輪次進行的順序，接著利用編碼的方式決定每場比賽進行的時間與場地，降低編排賽事時程表的複雜度。利用基因演算法（Genetic Algorithm）作為最佳化演算法，搭配改善後的複製及交配方法與啟發式的突變方法，從數量眾多的賽事時程表編排組合中，找出最符合主辦單位需求及賽事時程表編排問題之編排結果。
本論文為驗證所提方法之實際應用性，利用不同的天數、場館總數和場地總數的實際賽事進行賽事時程表的編排測試。編排結果顯示各種規模的賽事都能編排出類似或是優於人工編排之效果。

摘要(英)

To host a tournament, in addition to the organizer, contestant and venue, the tournament schedule is also an indispensable part. It plans the start time, end time, and the other information for each game. However, scheduling the tournament needs to consider many restrictions, such as the date of the event, the time of the game and the total number of venues. Also, for the fairness of the game, the players need to have enough rest time between the games.
Aiming at the problem of scheduling schedules of events, this paper designs an optimized algorithm that can arrange schedules of events of various sizes with reference to the scheduling results of actual events and the arrangement methods used by experienced scheduling personnel. Taking the rounds in the schedule as the unit, by arranging the sequence of the rounds of the schedule, and then using some coding methods to determine the time and venue of each game to reduce the complexity of scheduling the schedule. Using Genetic Algorithm as the optimization algorithm, with improved replication and mating methods and heuristic mutation methods, the scheduling algorithm can find the most suitable schedules for the needs of the organizers and the result of the scheduling of the event schedule from a large number of competition schedule arrangements.
In order to verify the practical applicability of the proposed method, this thesis used the real events with different days, stadiums and venues to verify the tournament schedules. The experimental results show that all kinds of events can be scheduled similarly or better than real events arranged by experienced personnel.

關鍵字(中)

★ 賽事時程表
★ 賽程編排
★ 最佳化演算法
★ 基因演算法

關鍵字(英)

★ tournament scheduling problem
★ game scheduling
★ genetic algorithm

論文目次

摘要 i
ABSTRACT ii
致謝 iv
目錄 v
圖目錄 vii
表目錄 ix
第一章、緒論 1
1-1 研究動機 1
1-2 研究目的 2
1-3 論文架構 3
第二章、相關研究 4
2-1 最佳化方法 4
2-1-1 基因演算法 4
2-1-2 粒子群最佳化演算法 5
2-2 賽事時程表編排 7
2-2-1 聯盟類型賽事 8
2-2-2 錦標賽類型賽事 12
2-3 時程表編排 14
2-3-1 學校時程表編排 14
2-3-2 手術室時程編排 17
2-4 賽制種類 19
2-4-1 循環賽制 19
2-4-2 淘汰賽制 20
2-4-3 混合賽制 21
第三章、研究方法 23
3-1 賽事時程表編排規劃 23
3-1-1 賽事規畫 23
3-1-2 選手晉級規劃 24
3-1-3 賽程編排限制 25
3-2 評估方式與目標函數 26
3-3 基因演算法於賽事時程表編排規劃 28
3-3-1 編碼方式 29
3-3-2 初始化 34
3-3-3 複製、交配與突變 34
3-4 時段保留規劃 36
第四章、實驗設計與結果 38
4-1 實驗賽事介紹 38
4-2 編排問題與結果說明 40
4-3 基因演算法運算方法實驗 43
4-3-1 實驗設計 43
4-3-2 實驗結果與分析 44
4-4 賽事時程表時段保留實驗 49
4-5 賽事時程表編排之應用性 51
4-5-1 賽事時程表編排時間 51
4-5-2 線上軟體之賽事時程表編排效果 54
第五章、結論與未來展望 57
5-1 結論 57
5-2 未來展望 58
參考文獻 59

參考文獻

[1] "i運動資訊平台-運動現況統計," [Online]. Available: https://isports.sa.gov.tw/Apps/TIS08/TIS0801M_01V1.aspx?MENU_CD=M07&ITEM_CD=T01&MENU_PRG_CD=12&LEFT_MENU_ACTIVE_ID=26. [Accessed 02 06 2020].
[2] M. Gen and C. Runwei, Genetic Algorithms and Engineering Design, New York, 1997.
[3] K. James and E. Russell, "Particle swarm optimization," Proceedings of ICNN′95 - International Conference on Neural Networks, pp. 1942-1948, 1995.
[4] 趙于翔, “以群體智慧為基礎的最佳化演算法及其應用,” 國立中央大學資訊工程研究所博士論文, 2007.
[5] G. L. Nemhauser and M. A. Trick, Scheduling A Major College Basketball Conference, Operations Research, 1998.
[6] N. S. Choubey, "A Novel Encoding Scheme for Traveling Tournament Problem using Genetic Algorithm," in IJCA Special Issue on Evolutionary Computation, 2010.
[7] J. T. Yang, H. D. Huang, and J. T. Horng, "Devising a cost effective baseball scheduling by evolutionary algorithms," Proceedings of the 2002 Congress on Evolutionary Computation, pp. 1660-1665, 2002.
[8] C. F. Yang, "NBA Sports Game Scheduling Problem and GA-Based Solver," in International Conference on Industrial Engineering, Management Science and Application, 2017.
[9] D. Costa, "An Evolutionary Tabu Search Algorithm And The NHL Scheduling Problem," in INFOR, 1995.
[10] "107 i臺灣計畫上班族羽球錦標賽賽程表," [Online]. Available: https://drive.google.com/file/d/1s8Hu34b8hfna74XDRfcMmWJ2y9p5FY0a/view. [Accessed 02 06 2020].
[11] P. Wilke, M. Grobner, and N. Oster, "A Hybrid Genetic Algorithm for School Timetabling," AI 2002: Advances in Artificial Intelligence, pp. 455-464, 2002.
[12] D. Abramson and J. Abela, "A Parallel Genetic Algorithm for Solving the School Timetabling Problem," in In Proceedings of the Fifteenth Australian Computer Science Conference (ACSC-15), 1992.
[13] J. Caldeira and C. Agostinho, "School Timetabling using Genetic Search," Proceedings of the Practice and Theory of Automated Timetabling, pp. 115-122, 1999.
[14] R. Raghavjee and N. Pillay, "An Application of Genetic Algorithms to the School Timetabling Problem," Proceedings of SAICSIT 2008, pp. 193-199, 2008.
[15] K. Smith, D. Abramson, and D. Duke, "Hopfield neural networks for timetabling: formulations, methods, and comparative results," Computers & Industrial Engineering, pp. 283-305, 2003.
[16] B. Sigi, M. Golub, and V. Mornar, "Solving timetable scheduling problem using genetic algorithms," in Proceedings of the 25th International Conference on Information Technology Interfaces, 2003.
[17] B. Denton, J. Viapiano, and A. Vogl, "Optimization of surgery sequencing and scheduling decisions under uncertainty," Health Care Management Science, vol. 10, pp. 13-24, 2007.
[18] 陳德芳, “建立手術時間預測模式來從事電腦化手術室排程,” 國立臺灣大學醫療機構管理研究所碩士論文, 2006.
[19] A. Jebali, A. B. Alouane, and P. Ladet, "Operating rooms scheduling," International Journal of Production Economics, vol. 99, pp. 52-62, 2006.
[20] 賴世章, “計算是制會於資源分配之應用,” 國立中央大學資訊工程研究所碩士論文, 2008.
[21] T. Timucin and S. Birogul, "Implementation of Operating Room Scheduling with Genetic Algorithm and the Importance of Repair Operator," in 2018 2nd International Symposium on Multidisciplinary Studies and Innovative Technologies (ISMSIT), 2018.
[22] H. Fei, N. Meskens, and C. Chu, "A planning and scheduling problem for an operating theatre using an open scheduling strategy," Computers & Industrial Engineering, pp. 221-230, 2010.
[23] H. Fei, N. Meskens, and C. Chu, "An operating theatre planning and scheduling problem in the case of a block scheduling strategy," Service systems and service management, pp. 422-428, 2006.
[24] "羽球比賽賽制介紹：循環制," [Online]. Available: https://www.victorsport.com.tw/badmintonaz/8267/Tournament-System-Introduction-Round-Robin. [Accessed 02 06 2020].
[25] "羽球比賽賽制介紹－單淘汰," [Online]. Available: https://www.victorsport.com.tw/badmintonaz/8323/Tournament-System-Introduction-Single-Elimination. [Accessed 02 06 2020].
[26] "羽球比賽賽制介紹－混合制," [Online]. Available: https://www.victorsport.com.tw/badmintonaz/8504/Tournament-System-Introduction-Mixed-System. [Accessed 02 06 2020].
[27] V. A. Circirello, "Non-wrapping order crossover: An order preserving crossover operator that respects absolute position," in Genetic and Evolutionary Computation Conference, 2006.
[28] "貝名頓盃賽程總表," [Online]. Available: https://drive.google.com/file/d/1sIWx5eJ6eZKv5fOrE1QeiWOQKMroM8l4/view. [Accessed 25 06 2020].
[29] "靜宜大學108學年度全校新生盃羽球錦標賽--比賽成績," [Online]. Available: http://www.phyed.pu.edu.tw/games/108-1game-contents/message/108-1s-badminton-news.xlsx. [Accessed 25 06 2020].
[30] "2018第十屆天梭盃全國羽球錦標賽_秩序冊," [Online]. Available: http://air520.ef-info.com/2018第十屆天梭盃全國羽球錦標賽_秩序冊0512.pdf. [Accessed 02 06 2020].
[31] "108年全國壯年羽球錦標賽賽程表," [Online]. Available: http://www.ctb.org.tw/download/file/108年全國壯年羽球錦標賽賽程表.pdf. [Accessed 25 06 2020].
[32] "第一屆iwater盃全國羽球錦標賽_場次表0626," [Online]. Available: http://iwater.ef-info.com/第一屆iwater盃全國羽球錦標賽_場次表0626.pdf. [Accessed 25 06 2020].
[33] "108 年新竹縣『主委盃』全國羽球錦標賽_場次時間表," [Online]. Available: http://hccba.ef-info.com/108 20年新竹縣『主委盃』全國羽球錦標賽_場次時間表_v3.pdf. [Accessed 02 06 2020].
[34] "108年豐原區主委盃全國羽球錦標賽," [Online]. Available: http://tcfy.ef-info.com/108年豐原區主委盃全國羽球錦標賽_1016-v3.pdf. [Accessed 02 06 2020].
[35] "Convensports - 2018 世界清晨盃暨吳文達紀念盃," [Online]. Available: https://www.convensports.com/event/5_2018-世界清晨盃暨吳文達紀念盃. [Accessed 02 06 2020].
[36] "2019清晨盃賽程-YCM-秩序冊版," [Online]. Available: https://drive.google.com/file/d/1bTr2lFOIG6ZjNNje3UNTm-CyblfD1zPo/view. [Accessed 02 06 2020].
[37] 蘇木春、張孝德, 機器學習：類神經網路、模糊系統以及基因演算法則, 全華科技圖書股份有限公司, 2004.
[38] N. Soni and T. Kumar, "Study of Various Mutation Operators in Genetic Algorithm," International Journal of Computer Science and Information Technologies, pp. 4519-4521, 2014.
[39] "League & Tournament Schedule Generator | LeagueLobster," [Online]. Available: https://scheduler.leaguelobster.com. [Accessed 01 06 2020].

指導教授

蘇木春(Mu-Chun Su)

審核日期

2020-8-18

推文