ĈҤI HӐC QUӔC GIA TP. HCM
75ѬӠ1*ĈҤI HӐC BÁCH KHOA TPHCM
/Ç3+ѬѪ1*'81*
NGHIÊN CӬU SӰ DӨNG GIҦI THUҰT DI TRUYӄN
LҰP THӠI KHÓA BIӄ8&+275ѬӠNG TRUNG HӐC PHӘ
THÔNG
Chuyên ngành: Kӻ thuұt công nghiӋp
Mã sӕ: 8520117
LUҰ19Ă1THҤ&6Ƭ
TP. HӖ CHÍ MINH, tháng 01 QăP
Công trìQKÿѭӧc hoàn thành tҥi: 7UѭӡQJĈҥi hӑc Bách Khoa ± Ĉ+4*- HCM
Cán bӝ Kѭӟng dүn khoa hӑc: 3*676Ĉӛ Ngӑc HiӅn,
............................................................................................................................
TS. NguyӉQ9ăQ7KjQK
............................................................................................................................
Cán bӝ chҩm nhұn xét 1: TS. NguyӉn Vҥng Phúc Nguyên
............................................................................................................................
Cán bӝ chҩm nhұn xét 2: TS. NguyӉn Hӳu Thӑ
............................................................................................................................
LuұQYăn thҥFVƭÿѭӧc bҧo vӋ tҥi 7Uѭӡng Ĉҥi hӑc Bách Khoa - Ĉ+4*73. HCM ngày
WKiQJQăP
Thành phҫn Hӝi ÿӗQJÿiQKJLiOXұQYăn thҥFVƭJӗm:
(Ghi rõ hӑ, tên, hӑc hàm, hӑc vӏ cùa hӝi ÿӗng chҩm bҧo vӋ luұQYăn thҥFVƭ
1. Chӫ tӏch: TS. Lê Song Thanh QuǤnh
2. 7KѭNê 76'ѭѫQJ4Xӕc Bӱu
3. Ӫy viên: 3*676Ĉӛ Ngӑc HiӅn
4. Phҧn biӋn 1: TS. NguyӉn Vҥng Phúc Nguyên
5. Phҧn biӋn 2: TS. NguyӉn Hӳu Thӑ
Xác nhұn cùa Chӫ tӏch HӝLÿӗQJÿánh giá LV Yj7Uѭӣng khoa quҧn lý chuyên ngành
sau khi luұQYăQÿm ÿѭӧc sӱa chӳa (nӃu có).
CHӪ TӎCH HӜ,ĈӖNG
TS. Lê Song Thanh QuǤnh
75ѬӢ1*.+2$&Ѫ.+Ë
i
ĈҤ,+Ӑ&48Ӕ&*,$73+&0
75ѬӠ1*ĈҤ,+Ӑ&%È&+.+2$
&Ӝ1*+Ñ$;+Ӝ,&+Ӫ1*+Ƭ$9,ӊ71$0
ĈӝFOұS- 7ӵGR- +ҥQKSK~F
NHIӊM VӨ LUҰ19Ă17+Ҥ&6Ƭ
Hӑ tên hӑc viên: /Ç3+ѬѪ1*'81* .......................... MSHV: 1970613 .....................
1Jj\WKiQJQăPVLQK 07/10/1996 ................................. 1ѫLVLQK %uQKĈӏnh ................
Chuyên ngành: Kӻ thuұt Công nghiӋp ............................ Mã sӕ : 8520117 ...................
I. 7Ç1Ĉӄ TÀI
Nghiên cӭu sӱ dөng giҧi thuұt di truyӅn lұp thӡi khóa biӇXFKRWUѭӡng trung hӑc
phә thông.
Study of genetic algorithms for solving a high school timetabling problem.
NHIӊM VӨ VÀ NӜI DUNG : Mөc tiêu chính cӫDÿӅ tài là tìm hiӇu giҧi thuұt di
truyӅn và ӭng dөng cӫD Qy ÿӇ xây dӵng hӋ thӕng xӃp thӡi khóa biӇu (TKB) cho
WUѭӡng trung hӑc phә thông (THPT). Lҩy mӝWWUѭӡng hӧp cө thӇ tҥi mӝWWUѭӡng THPT
WUrQÿӏa bàn quұn Bình Tân, TP HCM ÿӇ khҧo sát, phân tích các vҩQÿӅ NKyNKăQ
trong công tác giáo vө NKLFKѭDFyPӝt hӋ thӕng lұp lӏch hoàn chӍnh, tӯ ÿyÿӅ xuҩt
mӝt giҧi thuұWPHWDKHXULVWLFÿӇ giҧi bài toán xӃp TKB. ĈӇ thӵc hiӋn mөc tiêu này,
nhiӋm vө ÿһt ra là: NV1- Nghiên cӭXÿһFÿLӇm cӫa bài toán xӃp TKB WUѭӡng THPT,
tӯ ÿyÿӅ ra các giҧi pháp trong viӋc xây dӵng và triӇn khai hӋ thӕng; NV2- Ӭng dөng
giҧi thuұt di truyӅn vào bài toán xӃp TKB WUѭӡng THPT; NV3- TriӇn khai thӵc
nghiӋm vӟi bӝ dӳ liӋu xӃp TKB tҥL7+37%uQK+ѭQJ+zD%uQK7kQTP HCM.
II.
NGÀY GIAO NHIӊM VӨ: 15/08/2021
III.
NGÀY HOÀN THÀNH NHIӊM VӨ: 30/12/2021
IV.
CÁN BӜ +ѬӞNG DҮN: 3*676Ĉӛ Ngӑc HiӅn, TS. NguyӉQ9ăQ7KjQK
Tp. HCM, ngày .... tháng ...QăP21
&È1%Ӝ+ѬӞ1*'Ү1
3*676Ĉӛ Ngӑc HiӅn
&+Ӫ1+,ӊ0%Ӝ0Ð1Ĉ¬27Ҥ2
TS NguyӉQ9ăQ7KjQK
75ѬӢNG KHOA &Ѫ.+Ë
ii
LӠI CҦ0Ѫ1
----------------------------------Tôi gӱi lӡi cҧPѫQFKkQWKjQKÿӃn các thҫy cô thuӝc bӝ môn Kӻ thuұt HӋ Thӕng Công
NghiӋp - .KRD&ѫ.Kt- 7UѭӡQJĈҥi hӑc Bách Khoa - Ĉҥi hӑc Quӕc gia TP.HCM vӟi
các bài giҧng, giáo trình, bài báo, tài liӋu tham khҧo do Thҫy Cô cung cҩSĈһc biӋt là
sӵ truyӅQÿҥt kinh nghiӋm quý báu cӫa Thҫy Cô bӝ môn trong suӕt quá trình hӑc tұp ÿm
giúp tôi tìm hiӇu và giҧi quyӃt vҩQÿӅ ÿѭӧc thuұn lӧi, QKDQKFKyQJKѫQ
7{LFNJQJ[LQFҧPѫQThҫ\Ĉӛ Ngӑc HiӅn - Bӝ Môn Kӻ thuұt HӋ Thӕng Công NghiӋp .KRD&ѫ.Kt± 7Uѭӡng Ĉҥi hӑc Bách Khoa - Ĉҥi hӑc QuӕFJLD73+&0ÿmWұn tình
JL~Sÿӥ và Kѭӟng dүn trong suӕt quá trình thӵc hiӋQÿӅ tài, FNJQJQKѭVӵ quan tâm tҥo
ÿLӅu kiӋn thuұn lӧi cӫa Thҫy ÿmJL~SW{L hoàn thành luұQYăQtӕt nghiӋp.
Tôi xin gӱi lӡi cҧP ѫQ ÿӃn bҥn NguyӉQ 7KDQK ĈăQJ - Khoa Công nghӋ thông tin 7UѭӡQJĈҥi hӑc Công nghӋ 73+&0ÿã cung cҩp nhӳng kiӃn thӭc nӅn tҧQJFѫEҧn nhҭt
vӅ kӻ thuұt lұp trình, ÿӇ tôi tham khҧo thӵc hiӋn bài luұQYăQQjy.
7{LFNJQJ[LQJӱi lӡi cҧPѫQEDQOmQKÿҥRWUѭӡQJ7+37%uQK+ѭQJ+zDÿmWҥRÿLӅu kiӋn
cho tôi khҧo sát phӓng vҩn, cung cҩp thông tin cҫn thiӃWOLrQTXDQÿӃQÿӅ tài và hӛ trӧ
tôi trong quá trình thu thұp dӳ liӋu giúp tôi có thӇ hoàn thành luұQYăQWӕt nghiӋp.
Sau cùng, tôi xin gӱi lӡi cҧPѫQ ÿӃQJLDÿuQKQJѭӡi thân và bҥQEqÿmOX{Qÿӝng viên
và ӫng hӝ tôi cҧ vӅ vұt chҩt lүn tinh thҫn giúp tôi có thӇ hoàn thành tӕWTXmQJÿѭӡng hӑc
tұp và rèn luyӋn tҥLWUѭӡng Ĉҥi hӑc Bách Khoa TP.HCM.
Mӝt lҫn nӳa xin trân trӑng cҧPѫQ
Tp. HCM, ngày 09 tháng 01 QăP22
Hӑc viên
/r3KѭѫQJ'XQJ
iii
TÓM TҲT LUҰ19Ă17+Ҥ&6Ƭ
Ngày nay, công nghӋ WK{QJWLQÿmYjÿDQJÿyQJYDLWUzTXDQWUӑQJWURQJÿӡi sӕng kinh
tӃ, xã hӝi cӫa nhiӅu quӕc gia trên thӃ giӟi, là mӝt phҫn không thӇ thiӃu trong xã hӝLÿDQJ
ngày càng hiӋQÿҥi hóa. Vì vұy, viӋc tin hӑc hóa vào mӝt sӕ OƭQKYӵc ӭng dөng là hoàn
toàn phù hӧp vӟL[XKѭӟng hiӋn nay.
Xuҩt phát tӯ nhu cҫu ÿyYLӋc xây dӵng mӝWFKѭѫQJWUuQKVҳp thӡi khóa biӇu hӧp lý là
rҩt cҫn thiӃWYuÿѭӧc ӭng dөng trong thӵc tӃ, mөFÿtFKQKҵm thay thӃ mӝt sӕ công viӋc
PjWUѭӟFÿySKҧi thao tác bҵQJWD\GRÿyNK{QJÿҥWÿѭӧc hiӋu quҧ cao, tӕn công sӭc và
mҩt nhiӅu thӡi gian.
Bài toán xӃp thӡi khóa biӇXÿѭӧc phân loҥi là thuӝc lӟp NP-FRPSOHWHYjÿmÿѭӧc công
bӕ nghiên cӭu rӝng rãi trong nhiӅXQăPTXDYӟLFiFKѭӟng tiӃp cұQQKѭTX\KRҥch toán
hӑc, tӕL ѭX Gӵa trên ràng buӝc, tӕL ѭX ÿD Pөc tiêu, giҧi thuұt tham lam, giҧi thuұt
metaheuristic.v.v. LuұQ YăQ Qj\ Wұp trXQJ WKHR Kѭӟng tiӃp cұn metaheuristic bӡi vì
Kѭӟng tiӃp cұn này là rҩt thông dөQJÿӇ giҧi quyӃt các bài toán xӃp thӡi khóa biӃu, cө
thӇ ӣ ÿk\WiFJLҧ ÿӅ xuҩt sӱ dөng giҧi thuұt di truyӅn giҧi quyӃt bài toán xӃp thӡi khóa
biӇu dӵa trên bӝ dӳ liӋXPDQJÿһc tUѭQJULrQJFӫDFiFWUѭӡng trung hӑc phә thông tҥi
ViӋt Nam.
Thách thӭc cӫa bài toán xӃp thӡi khóa biӇX FKR WUѭӡng hӑc hiӋQ QD\ WUrQ ÿӏa bàn
TP.HCM là sӵ bùng nә tә hӧp do sӕ Oѭӧng lӡi giҧi quá lӟn, không gian tìm kiӃm lӟn,
WURQJNKLÿyWKӡi gian yêu cҫXÿӇ thuұt tìm kiӃm chҥy ra lӡi giҧi phҧi nҵm trong khoҧng
chҩp nhұQÿѭӧc.
Ӣ ViӋW1DPÿmFyPӝt vài phҫn mӅm lұp thӡi khóa biӇu khá tӕWQKѭQJFKѭDÿiSӭng
hӃt các yêu cҫu thӵc tӃ FNJQJQKѭFiFKWә chӭc giҧng dҥy cӫa tӯQJWUѭӡng. Nghiên cӭu
ÿm[k\Gӵng và thӵc nghiӋPÿӅ xuҩt trên mӝt sӕ bӝ dӳ liӋu thӵc tӃ. KӃt quҧ thӵc nghiӋm
cho thҩy giҧi thuұWÿӅ xuҩt cho kӃt quҧ tӕWKѫQPӝt sӕ phҫn mӅm hӛ trӧ xӃp thӡi khóa
biӇXFKRFiFWUѭӡng phә thông hiӋn nay trên dӵa trên mӝt sӕ ràng buӝc cӫa bài toán.
iv
ABSTRACT
Nowadays, information technology has been playing an important role in the economic
and social life of many countries around the world, and is an indispensable part of an
increasingly modernized society. Therefore, the computerization of some application
areas is completely consistent with the current trend.
Stemming from that need, it is very necessary to build a program that arranges a
reasonable schedule because it is applied in practice, the purpose is to replace some jobs
that previously had to be manipulated by hand. 7KDW¶VQRWefficient, labor-intensive and
time-consuming.
The scheduling problem is classified as NP-complete and has been widely researched
for many years with approaches such as mathematical programming, constraint-based
optimization,
and
multi-objective
objective
optimization,
greedy
algorithm,
metaheuristic algorithm, etc. This thesis focuses on the metaheuristic approach because
this approach is very common to solve timed sorting problems, specifically the author
proposes to use a genetic algorithm to solve the sorting problem. The timetable is based
on a data set that is unique to high schools in Vietnam.
The challenge of the current school scheduling problem in Ho Chi Minh City is the
explosion of combinations due to the large number of solutions, the large search space,
and the time required for the search algorithm. The search results must be within the
acceptable range.
In Vietnam, there are some good scheduling software, but they have not met all the actual
requirements as well as the teaching organization of each school. The research has built
and tested the proposal on a number of real data sets. Experimental results show that the
proposed algorithm gives better results than some current software that supports
scheduling for high schools based on some constraints of the problem.
v
LӠ,&$0Ĉ2$1
7{L[LQFDPÿRDQÿk\UDF{QJWUuQKQJKLrQFͱu cͯa riêng tôi. Các s͙ li͏u và k͇t qu̫
nghiên cͱu trong lu̵QYăQQj\OjWUXQJWKFYjFK˱DWͳQJÿ˱ͫc công b͙ trong b̭t kǤ
công trình nào khác. M͕i s JL~Sÿͩ cho vi͏c thc hi͏n cho lu̵QYăQQj\ÿm ÿ˱ͫc c̫m
˯QYjFiFWK{QJWLQWUtFKG̳n trong lu̵QYăQÿmÿ˱ͫc ch͑ rõ ngu͛n g͙FU}UjQJÿ˱ͫc
công b͙ và cho phép s͵ dͭng.
TP+&0QJj\ WKiQJQăP
Hӑc viên thӵc hiӋn
/r3KѭѫQJ'XQJ
vi
MӨC LӨC
NHIӊM VӨ LUҰ19Ă17+Ҥ&6Ƭ .............................................................................. i
LӠI CҦ0Ѫ1 ................................................................................................................ ii
TÓM TҲT LUҰ19Ă17+Ҥ&6Ƭ .............................................................................. iii
ABSTRACT .................................................................................................................. iv
LӠ,&$0Ĉ2$1 .......................................................................................................... v
DANH MӨC HÌNH ҦNH .......................................................................................... viii
DANH MӨC BҦNG BIӆU ........................................................................................... x
DANH MӨC TӮ VIӂT TҲT/THUҰT NGӲ ............................................................. xi
GIӞI THIӊU TӘNG QUAN Vӄ Ĉӄ TÀI .......................................... 1
Giӟi thiӋu chung .................................................................................................1
;iFÿӏnh vҩQÿӅ nghiên cӭu...............................................................................2
Mөc tiêu nghiên cӭu ....................................................................................... 2
ĈӕLWѭӧng và phҥm vi nghiên cӭu .................................................................. 3
Cҩu trúc luұQYăQ ...............................................................................................4
&Ѫ6Ӣ LÝ THUYӂT VÀ PHѬѪ1*3+È3/8ҰN NGHIÊN CӬU
......................................................................................................................................... 5
&iFFѫVӣ lý thuyӃt và nghiên cӭu liên quan. ....................................................5
Giҧi thuұt di truyӅn ............................................................................................7
Các nghiên cӭu liên quan .................................................................................15
3KѭѫQJSKiSOXұn nghiên cӭu..........................................................................19
PHÂN TÍCH VÀ THIӂT Kӂ Hӊ THӔ1*&+ѬѪ1*75Î1+ .... 22
ĈӕLWѭӧng nghiên cӭu ......................................................................................22
Thӵc trҥng ........................................................................................................22
Dӳ liӋXÿҫu vào cӫa bài toán............................................................................25
ThiӃt kӃ hӋ thӕng xӃp thӡi khóa biӇu...............................................................33
BiӇu diӉn cҩu trúc NST ................................................................................ 35
Khӣi tҥo quҫn thӇ EDQÿҫu ............................................................................ 36
Ĉӝ thích nghi cӫa cá thӇ ............................................................................... 40
Phép lai ghép ................................................................................................ 41
3KpSÿӝt biӃn ................................................................................................ 43
Phép chӑn lӑc................................................................................................ 49
ĈLӅu kiӋn dӯng quá trình tiӃn hóa ................................................................ 49
vii
XÂY DӴ1* &+ѬѪ1* 75Î1+ ;ӂP THӠI KHÓA BIӆU CHO
75ѬӠNG TRUNG HӐC PHӘ THÔNG .................................................................. 50
0{LWUѭӡng thӵc nghiӋm ..................................................................................50
Dӳ liӋu thӵc nghiӋm ........................................................................................50
BiӇXÿӗ chӭFQăQJ............................................................................................50
BiӇXÿӗ phân rã chӭFQăQJ ........................................................................... 50
6ѫÿӗ luӗng dӳ liӋu (DFD) ........................................................................... 51
KӃt quҧ thӵc nghiӋPFKѭѫQJWUuQK ..................................................................52
Tәng quan vӅ FKѭѫQJWUuQK........................................................................... 52
ChӭFQăQJYjJLDRGLӋQFKѭѫQJWUuQK........................................................... 53
Thӱ nghiӋm FKѭѫQJWUuQK ............................................................................. 59
KӂT LUҰN VÀ KIӂN NGHӎ ............................................................ 61
KӃt quҧ ÿӅ tài ...................................................................................................61
+ѭӟng phát triӇn, kiӃn nghӏ .............................................................................62
TÀI LIӊU THAM KHҦO........................................................................................... 63
PHӨ LӨC ..................................................................................................................... 66
viii
DANH MӨC HÌNH ҦNH
Hình 2.1 Mô tҧ FiFEѭӟc tiӃn hành cӫa giҧi thuұt di truyӅn ....................................... 9
Hình 2.2. Sӵ lӵa chӑn NST tӕt nhҩt cӫDTXiWUuQKÿӝt biӃn ...................................... 10
Hình 2.3. 6ѫÿӗ quy trình cӫa thuұt toán di truyӅn vӟLFiFEѭӟc tӯ ÿҫXFKRÿӃn khi
ÿiSӭQJÿLӅu kiӋn kӃt thúc ............................................................................................. 13
Hình 2.4. 6ѫÿӗ tәng thӇ các Eѭӟc thӵc hiӋn giҧi quyӃt bài toán ............................. 20
Hình 3.1. Thӡi khóa biӇu lӟp 10C1 .......................................................................... 23
Hình 3.2. Thӡi khóa biӇu lӟp 11B1 .......................................................................... 24
Hình 3.3. Thӡi khóa biӇu lӟp 12A1 .......................................................................... 24
Hình 3.4 Thuұt toán di truyӅn sҳp xӃp thӡi khóa biӇu .............................................. 34
Hình 3.5 Cҩu trúc 3D cӫa mӝt NST rӛng ................................................................. 36
+uQK&iFEѭӟc cӫa thuұt toán khӣi tҥo quҫn thӇ EDQÿҫu.................................. 39
Hình 3.7. 4X\ÿӏnh vӅ tiӃWÿѭӧc hӑc trong mӝt tuҫn cө thӇ cho tӯng khӕi 10, 11, 12
....................................................................................................................................... 40
Hình 3.8. Quá trình phép lai ghép mӝWÿLӇPKDLÿLӇPYjÿӗng nhҩt cӫa các NST.. 42
+uQK &iFEѭӟc thӵc hiӋn thuұt toán lai ghép mӝWÿLӇPKDLÿLӇPYjÿӗng nhҩt
cӫa các NST ................................................................................................................... 43
Hình 3.10. Ví dө vӅ toán tӱ ÿӝt biӃQ ÿәi chӛ giáo viên) ......................................... 44
+uQK&iFEѭӟc thӵc hiӋn thuұWWRiQKRiQÿәi gen xӱ lý vi phҥm trùng lӏch ... 45
Hình 3.12. Ví dө vӅ toán tӱ ÿӝt biӃQ KRiQÿәi vӏ trí tiӃt hӑc).................................. 46
Hình 3.13. Ví dө khác vӅ toán tӱ ÿӝt biӃQ KRiQÿәi vӏ trí tiӃt hӑc) ......................... 46
+uQK&iFEѭӟc thӵc hiӋn thuұWWRiQKRiQÿәi gen xӱ lý vi phҥm vӅ sӕ buәi hӑc
....................................................................................................................................... 47
+uQK&iFEѭӟc thӵc hiӋn thuұWWRiQKRiQÿәi gen cân bҵng sӕ tiӃt dҥy cӫa giáo
viên ................................................................................................................................ 48
Hình 4.1 BiӇXÿӗ phân rã chӭFQăQJFӫa hӋ thӕng thӡi khóa biӃu sӁ xây dӵng ....... 50
+uQK6ѫÿӗ ngӳ cҧnh hӋ thӕng thӡi khóa biӇu .................................................... 51
ix
+uQK6ѫÿӗ mӭc 0 hӋ thӕng thӡi khóa biӇu ........................................................ 51
Hình 4.4 Các chӭFQăQJWUrQJLDRGLӋn chính ........................................................... 52
Hình 4.5 ChӭFQăQJQKұp thông tin giáo viên .......................................................... 53
Hình 4.6 ChӭFQăQJQKұp thông tin lӟp hӑc ............................................................. 54
Hình 4.7 ChӭFQăng nhұp thông tin môn hӑc ........................................................... 55
Hình 4.8 Khӣi tҥo quҫn thӇ EDQÿҫu vӟi hӋ sӕ WKtFKQJKLÿѭӧc thӇ hiӋn .................. 56
Hình 4.9 BiӇXÿӗ hӋ sӕ thích nghi cӫa quҫn thӇ khi tiӃQKyDÿѭӧc 100 thӃ hӋ ......... 57
Hình 4.10 KӃt thúc quá trình tiӃn hóa vӟi lӡi giҧi tӕLѭXFy KӋ sӕ thích nghi bҵng
100.00 ............................................................................................................................ 57
Hình 4.11 Giao diӋn xem thӡi khóa biӇu theo lӟp .................................................... 58
Hình 4.12 Giao diӋn xem lӏch day cӫa giáo viên ...................................................... 59
x
DANH MӨC BҦNG BIӆU
Bҧng 3.1 Danh sách môn hӑc và sӕ tiӃt, buәi hӑc cӫa tӯng môn trong tuҫn ............ 26
Bҧng 3.2 Danh sách lӟp hӑFWURQJQăP .................................................................... 27
Bҧng 3.3 Danh sách giáo viên, mã giáo viên và phân công lӟp dҥy......................... 33
xi
DANH MӨC TӮ VIӂT TҲT/THUҰT NGӲ
Tӯ viӃt tҳt
DiӉn giҧi
GA
Giҧi thuұt di truyӅn
NST
NhiӉm sҳc thӇ
THPT
Trung hӑc phә thông
TKB
Thӡi khóa biӇu
CSDL
&ѫVӣ dӳ liӋu
1
GIӞI THIӊU TӘNG QUAN Vӄ Ĉӄ TÀI
Giӟi thiӋu chung
Trong cuӝc sӕQJFK~QJWDWKѭӡng gһp phҧi nhӳng vҩQÿӅ OLrQTXDQÿӃn viӋc lұp
lӏFKÿLӅXÿӝ công viӋFQKѭOұp lӏch vұn hành máy móc, lұp lӏch thӵc hiӋn dӵ án,
lұp lӏch làm viӋc, lұp lӏFKWKLÿҩu thӇ thao,..Ĉӕi vӟi các khóa hӑFQKѭYұy, cҫn
phҧi tìm mӝt giҧi pháp lұp lӏch trình thӓa mãn tҩt cҧ FiFÿLӅu kiӋn. Hҥn chӃ và sӱ
dөng hiӋu quҧ các nguӗn lӵc sҹQFyÿӇ giҧm thӡi gian và chi phí thӵc hiӋn.
Thӡi khóa biӇu cӫDWUѭӡng hӑc là kӃ hoҥch giҧng dҥy cӫa giáo viên và hӑc tұp cӫa
hӑc sinh. Mӝt bҧng thӡi khóa biӇu hӧp lý giúp giáo viên thuұn lӧi, thoҧi mái khi
lên lӟp và giúp hӑc sinh thoҧi mái trong quá trình hӑc tұSĈmWӯ lâu, viӋc lұp thӡi
khóa biӇu cho các lӟp hӑc là vҩQÿӅ quan trӑng cӫa ban giám hiӋXQKjWUѭӡng và
phҧLOX{QOX{QKRjQWKjQKWUѭӟc khi triӇQNKDLQăPKӑc mӟi. Lұp thӡi khóa biӇu
bҵQJSKѭѫQJSKiSWKӫ công là công viӋc rҩt nһng nӅ, tӕn nhiӅu thӡi gian và dӉ vi
phҥm các ràng buӝc vӅ nghiӋp vө. Do vұy, khi áp dөng phҧi trҧLTXDÿLӅu chӍnh vài
lҫn mӟi có thӇ ÿҥWÿѭӧc yêu cҫXFѫEҧn.
Bài toán xӃp thӡi khóa biӇXWURQJWUѭӡng hӑFQyLFKXQJYjWURQJWUѭӡng trung hӑc
phә thông nói riêng là mӝt trong nhӳng bài toán có tính ӭng dung thӵc tiӉn cao
nhҩt, thiӃt thӵc nhҩt. Có rҩt nhiӅu các ràng buӝFÿѭӧFÿһWUDWURQJEjLWRiQQj\QKѭ
ràng buӝc vӅ ÿӕLWѭӧng tham gia (giáo viên, lӟp hӑc, hӑc sinh), ràng buӝc vӅ tài
nguyên phөc vө giҧng dҥy (phòng hӑc lý thuyӃt, phòng thӵFKjQK« UjQJEXӝc
vӅ thӡi gian (sӕ tiӃt hӑc, sӕ lҫn hӑc, sӕ tiӃt mӛi lҫn), ràng buӝc chuyên môn và rҩt
nhiӅu các ràng buӝc khác tùy thuӝc vào tӯQJWUѭӡng. VҩQÿӅ ÿһt ra là cҫn xây dӵng
mӝt thӡi khóa biӇu thӓa mãn tҩt cҧ các ràng buӝFWUrQÿӗng thӡi khai thác hiӋu quҧ
các nguӗn tài nguyên phөc vө giҧng dҥy.
Bài toán xӃp thӡi khóa biӇu thuӝc lӟp các bài toán NP-complete vì vұy có thӇ
NK{QJWuPUDÿѭӧc lӡi giҧi tӕLѭX [1]Ĉk\OjPӝt bài toán không mӟLYjÿmFyQKLӅu
giҧi thuұWÿѭӧFÿѭDUDÿӇ giҧi quyӃWQKѭJLҧi thuұt tham lam [2], giҧi thuұWOHRÿӗi,
giҧi thuұt luyӋn thép, giҧi thuұWW{PjXÿӗ thӏ, giҧi thuұWÿjQRQJ«[3],[4]. Tuy
2
nhiên các giҧi thuұWQj\WKѭӡng không có tính tәng quát và chӍ áp dөng hiӋu quҧ
ÿӕi vӟLFiFWUѭӡng hӑc có quy mô nhӓ, ít ràng buӝc vӅ mһt dӳ liӋu.
Các bài toán thӡi khóa biӇu rҩWSKRQJSK~YjÿDGҥng bӣi nhӳng ràng buӝc và yêu
cҫXÿһFWUѭQJFӫa tӯng hӋ ÿjRWҥo, thұm chí tӯQJWUѭӡng hӑc. Trong nhiӅXQăP
qua, có nhiӅu giҧi thuұWÿѭӧc xây dӵng và cҧi tiӃQÿӇ giҧi các bài toán vӅ lұp lӏch
ÿѭӧc tӕLѭX*Lҧi thuұt di truyӅn và tính tiӃn hóa mô phӓng sӵ tiӃn hóa cӫa tӵ nhiên
cӫa sinh hӑc và gҫQÿk\QKҩWOjSKѭѫQJSKiSWӕLѭXKyDÿjQNLӃQGR'RULJRÿӅ
xuҩWOjKѭӟng tiӃp cұn hiӋQÿҥi nhҩt. Cҧ hai loҥi giҧi thuұWWUrQÿmWӓ ra rҩt hiӋu quҧ
trong viӋc áp dөng giҧi quyӃt các bài toán tӕLѭXWURQJWKӵc tӃ, tiêu biӇu là bài toán
lұp thӡi khóa biӇXWUѭӡng hӑc, là mӝt bài toán thú vӏ và có tính thӵc tiӉn cao.
Trong nhӳQJQăPJҫQÿk\SKѭѫQg pháp tiӃp cұn di truyӅQÿmWKXK~WUҩt nhiӅu sӵ
FK~êWURQJFiFOƭQKYӵc nghiên cӭu khác nhau [5]. Lӟp giҧi thuұWQj\ÿmÿѭӧc
chӭng minh là có nhiӅXѭXÿLӇm Yѭӧt trӝi so vӟi các loҥi thuұWWRiQNKiFÿһc biӋt
khi áp dөng chúng vào lӟp bài toán tӕLѭX- mӝt lӟp bài toán khó và có nhiӅu ӭng
dөQJWURQJÿӡi sӕng thӵc tiӉn. 3KѭѫQJSKiSQj\FyQKLӅXÿһFÿLӇm nәi trӝLQKѭ
NK{QJÿzLKӓi tri thӭc, tránh tӕLѭXFөc bӝ, thӵc hiӋn tӕt vӟi các bài toán có không
gian lӡi giҧi lӟn và có thӇ áp dөng cho nhiӅu loҥi bài toán tӕLѭXNKiFQKDX7UrQ
thӃ giӟi hiӋn nay, giҧi thuұt di truyӅn kӃt hӧp vӟi tin hӑFÿѭӧc ӭng dөng ÿӇ giҧi
quyӃt nhӳng bài toán tӕLѭXPӝt cách rҩt hiӋu quҧ.
Vì vұy, viӋc nghiên cӭu và ӭng dөng giҧi thuұt di truyӅn (Genetic Algorithm - GA)
ÿӇ giҧi quyӃt hiӋu quҧ bài toán xӃp thӡi khóa biӇu nói trên là thұt sӵ cҫn thiӃt.
;iFÿӏnh vҩQÿӅ nghiên cӭu
Mөc tiêu nghiên cӭu
MөFÿtFKFӫDÿӅ tài luұQYăQQj\QKҵm xây dӵng mӝt hӋ thӕng hӛ trӧ FKRQJѭӡi
quҧn lý hӑc vө cӫDWUѭӡng trung hӑc phә thông sҳp xӃp lӏch dҥy hӑc, có thӇ giúp
tìm ra ÿѭӧc lӡi giҧi vӟi chi phí quҧn lý thҩp nhҩt, bên cҥQKÿyFzQFyWKӇ WѭYҩn
cho nhà quҧn lý hӑc vө mӝt cách sҳp xӃp giáo viên vӟi tiêu chí giúp làm hài hòa
giӳa chi phí giҧng dҥy và chҩWOѭӧng giáo viên phù hӧp.
3
ĈӅ tài tұp trung nghiên cӭu và ӭng dөng giҧi thuұt di truyӅn vào bài toán xӃp thӡi
khóa biӇu cho trung hӑc phә thông nhҵm ÿѭDUDSKѭѫQJiQ[Ӄp thӡi khóa biӇu thӓa
mãn tҩt cҧ các ràng buӝFÿһWUDÿӗng thӡi khai thác hiӋu quҧ các nguӗn lӵFÿjRWҥo
cӫDQKjWUѭӡng vӟi thӡi gian ngҳn.
ĈӇ ÿҥWÿѭӧc các mөFWLrXWUrQÿӅ tài tұp trung vào các nhiӋm vө cө thӇ sau:
3KkQWtFKÿһFÿLӇm cӫa bài toán xӃp thӡi khóa biӇXWURQJWUѭӡng trung hӑc phә
thông ÿӇ tӯ ÿyÿӅ ra các giҧi pháp hӧp lý trong viӋc xây dӵng và triӇn khai hӋ
thӕng.
Tìm hiӇu giҧi thuұt di truyӅn và ӭng dөng cӫa nó trong viӋc giҧi quyӃt hiӋu quҧ
các bài toán tӕLѭX
Ӭng dөng giҧi thuұt di truyӅn vào bài toán xӃp thӡi khóa biӇX WURQJ WUѭӡng
trung hӑc phә thông.
Phân tích và ÿiQKJLiNӃt quҧ ÿҥWÿѭӧc khi thӵc hiӋn hӋ thӕQJÿӕi vӟi các bӝ
dӳ liӋu thӱ ÿѫQJLҧn.
TriӇn khai thӵc nghiӋm vӟi bӝ dӳ liӋu xӃp thӡi khóa biӇu tҥL7Uѭӡng THPT
%uQK+ѭQJ+zD%uQK7kQ7KjQKSKӕ Hӗ Chí Minh.
ĈӕLWѭӧng và phҥm vi nghiên cӭu
ĈӅ tài tұp trung nghiên cӭXFiFÿһFÿLӇPÿһFWUѭQJ, nhӳQJѭXÿLӇm cӫa giҧi thuұt
di truyӅn, các thành phҫQFѫEҧn cӫa giҧi thuұt di truyӅQQKѭNKӣLÿӝng quҫn thӇ
ban ÿҫu, ÿiQKJLi ÿӝ thích nghi cӫa cá thӇ, các toán tӱ di truyӅn (chӑn lӑc, lai ghép,
ÿӝt biӃn), ÿLӅu kiӋn dӯng.
Giͣi h̩n và ph̩m vi nghiên cͱu:
Trong bài toán này, tác giҧ thӵc hiӋn phân tích hiӋn trҥng, tìm hiӇu vҩQÿӅ khó
NKăQWURQJYұn hành hӋ thӕng giáo dөc QKjWUѭӡng khi không có mӝt hӋ thӕng xӃp
thӡi khóa biӇu tӕLѭXWӯ ÿyÿӅ xuҩt mӝt giҧi thuұt metaheuristic dҥng quҫn thӇ là
giҧi thuұt di truyӅQÿӇ giҧi bài toán xӃp thӡi khóa biӇu tҥi WUѭӡng trung hӑc phә
4
WK{QJ%uQK+ѭQJ+zD%uQK7kQ7KjQKSKӕ Hӗ Chí Minh vӟi các ràng buӝc và
nhӳng yêu cҫu ÿѭӧFÿӅ ra.
Cҩu trúc luұQYăQ
&KѭѫQJ1: Giӟi thiӋu tәng quan vӅ ÿӅ tài&KѭѫQJQj\JLӟi thiӋu lý do hình thành
êWѭӣQJÿӅ tài, mөc tiêu nghiên cӭu, nhiӋm vө, phҥm vi và giӟi hҥn cӫDÿӅ tài.
&KѭѫQJ &ѫVӣ lý thuyӃt YjSKѭѫQJSKiSOXұn nghiên cӭu. NӝLGXQJFKѭѫQJQj\
WUuQKEj\SKѭѫQJSKiSOXұQÿӇ thӵc hiӋQÿӅ tài, các nӅn tҧng lý thuyӃt chính yӃu
ÿѭӧc tác giҧ sӱ dөQJWURQJÿӅ tài.
&KѭѫQJ 3hân tích và thiӃt kӃ hӋ thӕQJFKѭѫQJWUuQK Phҫn này giӟi thiӋu vӅ ÿӕi
Wѭӧng nghiên cӭXOjWUѭӡQJ7+37%uQK+ѭQJ+zD, nêu ra vҩQÿӅ PjÿӕLWѭӧng
này gһp phҧi khi sӱ dөQJSKѭѫQJSKiSOұp lӏch lӛi thӡi; tӯ ÿyWLӃn hành phân tích
dӳ liӋX ÿҫu vào và xây dӵng bài toán xӃp thӡi khóa biӇu dӵa trên giҧi thuұt di
truyӅn.
&KѭѫQJ ;ây dӵng ӭng dөng xӃp thӡi khóa biӇXFKRWUѭӡng trung hӑc phә thông.
&KѭѫQJ Qj\ P{ Wҧ FKѭѫQJ WUuQK WKӵc tӃ dӵa trên trình tӵ xây dӵng bài toán ӣ
FKѭѫQJWUѭӟc. Áp dөng thành công giҧi thuұt di truyӅQÿӇ xӃp thӡi khóa biӇu cho
WUѭӡQJ7+37%uQK+ѭQJ+zDEҵng ngôn ngӳ C#.
&KѭѫQJ .Ӄt luұn và kiӃn nghӏĈk\OjFKѭѫQJFXӕi cùng cӫDÿӅ tài luұQYăQ
Phҫn này tәng kӃWÿiQKJLiFiFQӝLGXQJÿmWUuQKEj\ÿӗng thӡLÿѭDUDFiFKѭӟng
mӣ rӝng, kiӃn nghӏ FKRÿӅ tài.
5
&Ѫ6Ӣ/é7+8<ӂ79¬3+ѬѪ1*3+È3/8Ұ1 NGHIÊN
&Ӭ8
&iFFѫVӣ lý thuyӃt và nghiên cӭu liên quan.
&iFSKѭѫQJSKiSWLӃp cұn truyӅn thӕQJÿӇ giҧi bài toán lұp thӡi khóa biӇu:
Giҧi thuұt vét cҥn (tìm kiӃm theo chiӅu rӝng hoһc chiӅu sâu) vӅ mһt nguyên
tҳFOX{QWuPÿѭӧc nghiӋm nӃu bài toán có nghiӋP1KѭQJWUrQWKӵc tӃ, các
bài toán thӡi khóa biӇu không nên áp dөQJSKѭѫQJSKiSQj\YuWDSKҧi
phát triӇn mӝt không gian trҥng thái cӵc lӟQWUѭӟFNKLÿLÿӃn trҥng thái
ÿtFK'RFiFKҥn chӃ vӅ thӡLJLDQWtQKWRiQYjGXQJOѭӧng bӝ nhӟ, không
cho phép ta thӵc hiӋQÿѭӧc.
Chҷng hҥn, vӟi bài toán thӡi khóa biӇu cho 45 lӟp hӑc, mӛi lӟp có 13
môn hӑc, mӛi lӟp có 45 tiӃt mӛi tuҫn thì không gian tìm kiӃm rҩt lӟn là
45*13*45 WUѭӡng hӧp. DӉ nhұn thҩy rҵng, nӃXGQJSKѭѫQJSKiSYpWFҥn
thì thӡi gian chҥy ÿӇ tìm lӡi giҧi tӕLѭXrҩt lӟn, khó chҩp nhұQÿѭӧc.
Giҧi thuұWOHRÿӗi (Hill Climbing) sӱ dөng kӻ thuұt nâng cҩp lһp, áp dөng
cho mӝt sӕ ÿLӇPÿѫQ ÿLӇm hiӋn hành) trong không gian tìm kiӃm. Mӛi lҫn
nâng cҩp, mӝWÿLӇm trong lân cұn cӫDÿLӇm hiӋQKjQKÿѭӧc chӑQOjPÿLӇm
kӃ tiӃp, nӃu nó cho kӃt quҧ tӕWKѫQFӫa hàm mөc tiêu. ViӋc tìm kiӃm kӃt
thúc khi không thӇ nâng cҩSÿѭӧc nӳa. Rõ ràng, giҧi thuұWOHRÿӗi chӍ cho
kӃt quҧ tӕLѭXFөc bӝ, kӃt quҧ này phө thuӝc vào sӵ chӑn lӵDÿLӇm xuҩt
phát, mһWNKiFWDNK{QJFyÿѭӧc thông tin vӅ sai sӕ giӳa tӕLѭXFөc bӝ tìm
ÿѭӧc và tӕLѭXWRjQFөc. MһFGÿmFҧi tiӃn bҵQJFiFKWăQJVӕ OѭӧQJÿLӇm
xuҩt phát (chӑn ngүu nhiên hoһc chӑn theo kӃt quҧ cӫa lҫn chҥ\WUѭӟc),
QKѭQJNKLFyQKLӅu cӵc trӏ lân cұn thì khҧ QăQJWuPÿѭӧc kӃt quҧ tӕLѭX
toàn cөc cӫa giҧi thuұWOHRÿӗi còn rҩt thҩp.
6
&iFSKѭѫQJSKiSWLӃp cұn hiӋQQD\ÿӇ giҧi bài toán lұp thӡi khóa biӇu:
ĈmFyQKLӅu giҧi thuұWÿѭӧFÿӅ xuҩWÿӇ giҧi các bài toán thӡi khóa biӇu. Các
giҧi thuұWQj\WuPÿѭӧc lӡi giҧi gҫn tӕLѭXYjOjPӝt trong các xu thӃ phát triӇn
hiӋQQD\ÿӕi vӟLFiFEjLWRiQFKѭDWKӇ WuPÿѭӧc lӡi giҧi tӕLѭXWKӵc sӵ. Các
giҧi thuұWQj\ÿӅu mô phӓng theo tӵ QKLrQQKѭJLҧi thuұt luyӋn kim, giҧi thuұt
di truyӅn, giҧi thuұt Tabu-search, giҧi thuұt hӋ kiӃQ«WURQJÿyJLҧi thuұt di
truyӅn và tӕLѭXKyDÿjQNLӃQÿѭӧc xem là nhӳQJSKѭѫQJSKiSFKRKLӋu quҧ
cao nhҩt.
Giҧi thuұt Tabu-search: là mӝt trong nhӳQJPHWDKHXULVWLFÿѭӧc áp dөng
nhiӅu nhҩt cho các bài toán tӕLѭXWә hӧp khó. Bҳt nguӗn tӯ mӝt lӡi giҧi
EDQÿҫu, thuұt giҧi Tabu Search sӁ lһSÿLOһp lҥi viӋc tìm kiӃm trong miӅn
không gian tìm kiӃm cӫa bài toán nhҵm mөFÿtFKWuPUDOӡi giҧi tӕLѭX
Tҥi mӛLEѭӟc lһp cӫa mình, thuұt giҧi Tabu Search sӁ tìm kiӃm và chӍ lӵa
ra mӝt lӡi giҧi duy nhҩWÿӇ OjPFѫVӣ FKREѭӟc lһp tiӃp theo. ĈӇ tránh viӋc
duyӋt trӣ lҥi nhӳng lӡi giҧLÿmÿѭӧc duyӋt, thuұt giҧi Tabu Search sӱ dөng
Tabu-list. Danh sách này chӭa nhӳng lӡi giҧi ÿmÿѭӧc thӵc hiӋn trong các
Eѭӟc lһp WUѭӟc, chúng sӁ bӏ cҩm sӱ dөng lҥi chӯng nào nó còn nҵm trong
Tabu-list. [6]
Trong giҧi thuұt luyӋQNLP $QQHDOLQJ$OJRULWKP QJѭӡi ta dùng kӻ thuұt
WKD\ÿәi entropy cӫa hӋ YjÿLӅu khiӇn tӕFÿӝ hӝi tө cӫa quҫn thӇ bҵng cách
biӃQÿәi nhiӋWÿӝng hӑc vӟi mӝt tham sӕ nhiӋWÿӝ T toàn cөc [7]ĈӇ hҥn
chӃ sӵ tӕLѭXFөc bӝ YjWăQJNKҧ QăQJNKiPSKiNK{QJJLDQWuPNLӃm,
QJѭӡi ta dùng thӫ thuұt giҧm tӯQJEѭӟc nhiӋWÿӝ 7 ÿӃn mӝt mӭFQjRÿy
Tuy nhiên, do T chӍ giҧPÿӃn mӝt mӭc nhҩWÿӏnh, nên kӻ thuұt luyӋn kim
không tránh khӓi hҥn chӃ trong viӋc khám phá không gian tìm kiӃm và sӵ
hӝi tө lân cұn.
Giҧi thuұt di truyӅn là sӵ kӃt hӧSêWѭӣng cӫa giҧi thuұWOHRÿӗi và luyӋn
NLPĈһFWUѭQJFӫa giҧi thuұt này là duy trì mӝt tұp các lӡi giҧi tiӅPQăQJ
(gӑi là tұp các cá thӇ hay quҭn thӇ), khuyӃn khích viӋc hình thành và trao
7
ÿәi thông tin giӳa các cá thӇ trong quҫn thӇ thông qua phép lai và phép
biӃn dӏ. Mӝt quá trình tiӃQKyDÿѭӧc thӵc hiӋn trên mӝt quҫn thӇ thӵc chҩt
là sӵ tìm kiӃm trong mӝt không gian các lӡi giҧi tiӅPQăQJ6ӵ tìm kiӃm
Qj\ÿzLKӓi sӵ cân bҵng giӳa hai mөc tiêu: tìm lӡi giҧi tӕt nhҩt và khám
phá không gian tìm kiӃm mӟi.
Giҧi thuұt tӕLѭXÿjQNLӃn (ACO ± Ant Colony Optimization) do Dorigo
ÿӅ xuҩWOjSKѭѫQJSKiSWLӃp cұn hiӋQÿҥi nhҩt. Mӝt thành phҫn ngүu nhiên
trong ACO cho phép các con kiӃn xây dӵQJÿѭӧc mӝWOѭӧng lӟn các lӡi
giҧLNKiFQKDXKѫQFiFSKѭѫQJSKiSNKiF7ҥi cùng mӝt thӡi gian, viӋc
sӱ dөng các thông tin kinh nghiӋm sӁ Kѭӟng dүn các con kiӃn tìm kiӃm
ÿѭӧc các lӡi giҧi hӭa hҽn. Quan trӑQJKѫQNLQKQJKLӋm tìm kiӃm cӫa con
kiӃn sӁ ÿѭӧc sӱ dөQJÿӇ hӑFWăQJFѭӡng trong quá trình lһp xây dӵng giҧi
thuұW7KrPYjRÿyYLӋc tham gia cӫDÿjQNLӃn kiӃn làm cho giҧi thuұt
$&2Fyÿѭӧc mӝt tұp hӧp các tác nhân lһp hiӋu quҧ ÿӅ giҧi quyӃt bài toán.
Tuy nhiên, giҧi thuұt tӕLѭXÿjQNLӃn phӭc tҥSKѫQSKѭѫQJSKiSWtQKWRiQ
tiӃn hóa nhiӅu.
HiӋn nay giҧi thuұt di truyӅn và giҧi thuұt tӕLѭXÿjQNLӃQOjKDLSKѭѫQJSKiS
ÿѭӧc sӱ dөng nhiӅu nhҩWÿӇ giҧi quyӃt bài toán lұp thӡi khóa biӇu. Xét vӅ thӡi
gian thӵc hiӋn, chi phí thӵc hiӋn thì giҧi thuұt tӕi ѭXÿjQNLӃn tӕWKѫQQKѭQJ
FNJQJSKӭc tҥSKѫQJLҧi thuұt di truyӅn. Trên thӵc tӃ viӋc lұp thӡi khóa biӇu chӍ
diӉn ra khoҧng bӕn ÿӃn QăP lҫn trong mӝWQăPSKө thuӝFYjRFKѭѫQJWUuQK
ÿjRWҥo cӫDWUѭӡng qua tӯQJQăP. Vì vұy ÿӇ ÿѫQJLҧn, luұQYăQnày sӱ dөng
giҧi thuұt di truyӅQÿӇ tiӃp cұn bài toán lұp thӡi khóa biӇu cho WUѭӡng hӑc do
thӡi gian và chi phí cho viӋc lұp thӡi khóa biӇu nҵm trong khoҧng chҩp nhұn
ÿѭӧc.
Giҧi thuұt di truyӅn
Thuұt toán di truyӅn là mӝt mô phӓng quá trình tiӃn hóa tӵ nhiên cӫa các sinh
vұt dӵa trên hӑc thuyӃt Darwin. Trong quá trình tiӃn hóa, mӛi cá thӇ phҧi tìm
ra cách tӕt nhҩWÿӇ thích nghi vӟi mӝWP{LWUѭӡng rҩt phӭc tҥp và liên tөc thay
- Xem thêm -
.PDF 
85 
1 
107 
