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

NCUIR > College of Electrical Engineering & Computer Science > Graduate Institute of Computer Science and Information Engineering > Electronic Thesis & Dissertation > Item 987654321/84115

Please use this identifier to cite or link to this item: http://ir.lib.ncu.edu.tw/handle/987654321/84115

Title:	以基因演算法應用於賽事時程表之最佳化問題;The Application of the Genetic Algorithm in Solving the Tournament Scheduling Problem
Authors:	張哲軒;Chang, Che-Hsuan
Contributors:	資訊工程學系
Keywords:	賽事時程表;賽程編排;最佳化演算法;基因演算法;tournament scheduling problem;game scheduling;genetic algorithm
Date:	2020-08-18
Issue Date:	2020-09-02 18:06:25 (UTC+8)
Publisher:	國立中央大學
Abstract:	要舉辦一場賽事除了主辦單位、參賽選手和比賽場地之外，賽事時程表也是不可或缺的一環。賽事時程表規劃每場比賽的開始時間、結束時間和進行的場館與場地資訊。而編排一個賽事時程表需要考慮許多限制條件，如：賽事進行的日期、比賽時間及可用場地總數，且為了比賽的公平性，參賽選手於比賽間需要有充足的休息時間。本論文針對賽事時程表的編排問題，參考實際賽事的編排結果及編排人員的編排方式，設計一套能編排各種規模賽事時程表的最佳化演算法。以賽程中的輪次為單位，透過編排賽程輪次進行的順序，接著利用編碼的方式決定每場比賽進行的時間與場地，降低編排賽事時程表的複雜度。利用基因演算法（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.
Appears in Collections:	[Graduate Institute of Computer Science and Information Engineering] Electronic Thesis & Dissertation

Files in This Item:

File	Description	Size	Format
index.html		0Kb	HTML	236	View/Open

社群 sharing

Loading...