(3.238.173.209) 您好!臺灣時間:2021/05/17 11:40
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果

詳目顯示:::

: 
twitterline
研究生:張哲軒
研究生(外文):Che-Hsuan Chang
論文名稱:以基因演算法應用於賽事時程表之最佳化問題
論文名稱(外文):The Application of the Genetic Algorithm in Solving the Tournament Scheduling Problem
指導教授:蘇木春蘇木春引用關係
指導教授(外文):Mu-Chun Su
學位類別:碩士
校院名稱:國立中央大學
系所名稱:資訊工程學系
學門:工程學門
學類:電資工程學類
論文出版年:2020
畢業學年度:108
語文別:中文
論文頁數:76
中文關鍵詞:賽事時程表賽程編排最佳化演算法基因演算法
外文關鍵詞:tournament scheduling problemgame schedulinggenetic algorithm
相關次數:
  • 被引用被引用:0
  • 點閱點閱:108
  • 評分評分:
  • 下載下載:44
  • 收藏至我的研究室書目清單書目收藏:0
要舉辦一場賽事除了主辦單位、參賽選手和比賽場地之外,賽事時程表也是不可或缺的一環。賽事時程表規劃每場比賽的開始時間、結束時間和進行的場館與場地資訊。而編排一個賽事時程表需要考慮許多限制條件,如:賽事進行的日期、比賽時間及可用場地總數,且為了比賽的公平性,參賽選手於比賽間需要有充足的休息時間。
本論文針對賽事時程表的編排問題,參考實際賽事的編排結果及編排人員的編排方式,設計一套能編排各種規模賽事時程表的最佳化演算法。以賽程中的輪次為單位,透過編排賽程輪次進行的順序,接著利用編碼的方式決定每場比賽進行的時間與場地,降低編排賽事時程表的複雜度。利用基因演算法(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.
摘要 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].
連結至畢業學校之論文網頁點我開啟連結
註: 此連結為研究生畢業學校所提供,不一定有電子全文可供下載,若連結有誤,請點選上方之〝勘誤回報〞功能,我們會盡快修正,謝謝!
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top