DƢƠNG CHÍ BẰNG

BỘ GIÁO DỤC VÀ ĐÀO TẠO
VIỆN ĐẠI HỌC MỞ HÀ NỘI

CÔNG NGHỆ THÔNG TIN

LUẬN VĂN THẠC SĨ
CHUYÊN NGÀNH: CÔNG NGHỆ THÔNG TIN

PHƢƠNG PHÁP ỨNG DỤNG GIẢI THUẬT DI TRUYỀN
CHO BÀI TOÁN XẾP THỜI KHÓA BIỂU TÍN CHỈ

DƢƠNG CHÍ BẰNG
2013-2015

HÀ NỘI – 2015


BỘ GIÁO DỤC VÀ ĐÀO TẠO
VIỆN ĐẠI HỌC MỞ HÀ NỘI

LUẬN VĂN THẠC SĨ

PHƢƠNG PHÁP ỨNG DỤNG GIẢI THUẬT DI
TRUYỀN CHO BÀI TOÁN XẾP THỜI KHÓA BIỂU
TÍN CHỈ

DƢƠNG CHÍ BẰNG
CHUYÊN NGÀNH:


hƣớng dẫn và giúp đỡ em để hoàn thành đề tài luận văn.
Em cũng xin gửi cảm ơn chân thành nhất tới các thầy cô giáo ở khoa Sau đại
học và khoa Công nghệ thông tin – Viện đại học Mở Hà Nội đã cho em những kiến
thức quý báu và tạo điều kiện tốt nhất cho em trong quá trình học tập cũng nhƣ
hoàn thành luận văn
Em xin chân thành cảm ơn gia đình, ngƣời thân và bạn bè đã động viên, giúp
đỡ em trong quá trình học tập và thực hiện luận văn này.
Trong quá trình thực hiện luận văn, mặc dù em đã rất nỗ lực và cố gắng
nhƣng chắc chắn khó tránh đƣợc những sai sót, rất mong đƣợc sự thông cảm và chỉ
bảo của các thầy, cô và các bạn để luận văn này đƣợc hoàn thiện hơn.
Cuối cùng em xin kính chúc các thầy, cô sức khỏe, thành công và hạnh phúc.
Chân thành cảm ơn!

ii


MỤC LỤC
LỜI CAM ĐOAN ......................................................................................................1
LỜI CẢM ƠN .......................................................................................................... II
MỤC LỤC ............................................................................................................... III
DANH MỤC CÁC TỪ VIẾT TẮT ......................................................................... V
DANH MỤC CÁC BẢNG BIỂU .......................................................................... VI
DANH MỤC CÁC HÌNH VẼ...............................................................................VII
MỞ ĐẦU ....................................................................................................................1
1.1. Tính cấp thiết của đề tài ....................................................................................1
1.2. Mục tiêu nghiên cứu...........................................................................................1
1.3. Đối tƣợng và phƣơng pháp nghiên cứu............................................................2
1.3.1. Đối tƣợng nghiên cứu ....................................................................................2
1.3.2. Phƣơng pháp nghiên cứu ...............................................................................2
CHƢƠNG 1. GIỚI THIỆU BÀI TOÁN XẾP LỊCH .............................................3

3.2.3.3. Phép đột biến (mutation): ......................................................................42
3.2.3.4. Phép thay thế (replacement) ..................................................................43
3.2.3.5. Điều kiện dừng thuật toán .....................................................................43
CHƢƠNG 4. XÂY DỰNG ỨNG DỤNG VÀ THỬ NGHIỆM ............................44
4.1. Chƣơng trình thử nghiệm ...............................................................................44
4.2. Thử nghiệm với bài toán ví dụ mẫu ...............................................................46
4.3. Thử nghiệm với bài toán thực thế ..................................................................50
KẾT LUẬN ..............................................................................................................60
5.1. Kết quả đạt đƣợc ..............................................................................................60
5.2. Hạn chế và định hƣớng phát triển ..................................................................60
TÀI LIỆU THAM KHẢO ......................................................................................61

iv


DANH MỤC CÁC TỪ VIẾT TẮT
Viết tắt

Tiếng Anh

Tiếng Việt

GA

Genetic Algorithm

Giải thuật di truyền

SA


L

Lecture

Giảng viên

S

Student

Sinh viên

T

Timeslot

Khe thời gian cho xếp lịch

LT

Lecture-Time

Ma trận giảng viên và thời gian

CC

Course-Course

Ma trận ràng buộc giữa các lớp môn
học


Bảng 4. 1: Các tham số của dữ liệu ví dụ thử nghiệm

46

Bảng 4. 2: Xác định giảng viên vào giảng các lớp tín chỉ

46

Bảng 4. 3: Ràng buộc giữa lớp tín chỉ và phòng học (CR)

46

Bảng 4. 4: Ràng buộc giữa giảng viên và thời gian (LT)

47

Bảng 4. 5: Ràng buộc giữa sinh viên và các lớp tín chỉ (S×C)

47

Bảng 4. 6: Các tham số chạy thuật toán xếp lịch

48

Bảng 4. 7: Kết quả lịch đƣợc xếp theo thuật toán

49

Bảng 4. 8: Kết quả lịch theo trọng số hàm fitness (w 1=0.9, w2=0.01, w4=0.09) 49


13

Hình 2. 2. Minh họa kiểu mã hóa nhị phân của hai chuỗi gen

15

Hình 2. 3. Minh họa phƣơng pháp mã hóa hoán vị

15

Hình 2. 4. Minh họa phƣơng pháp mã hóa giá trị

16

Hình 2. 5. Minh họa phƣơng pháp mã hóa dạng cây

16

Hình 2. 6. Minh họa sơ đồ chọn theo bánh xe Roulette

19

Hình 2. 7. Sơ đồ minh họa phép chọn lọc xếp hạng

20

Hình 2. 8. Minh họa lai ghép một điểm cắt trên chuỗi nhị phân

22

Hình 4. 1. Sơ đồ lớp thiết kế trong chƣơng trình

45

Hình 4. 2: Biểu đồ sự biến đổi độ phù hợp cá thể (fitness) qua các lần tiến hóa 59
Hình 4. 3: Biểu đồ sự biến đổi số vi phạm ràng buộc cứng qua các lần tiến hóa 59

vii


MỞ ĐẦU
1.1. Tính cấp thiết của đề tài
Bài toán xếp lịch là một bài toán kinh điển và là một trong những bài toán rất
có ý nghĩa trong thực tiễn hiện nay. Tuy nhiên đây là một bài toán khó với nhiều
loại đầu vào khác nhau, các ràng buộc giữa các yếu tố và thƣờng có nhiều mục tiêu,
yêu cầu đặt ra. Hiện nay, trong các cơ sở đào tạo và đặc biệt là đào tạo đại học, cao
đẳng công tác xếp lịch còn gặp nhiều khó khăn, đôi khi chúng ta rất khó để kiểm
soát hết các trƣờng hợp của bài toán, vì thế hiệu quả mang mại chƣa cao. Bên cạnh
đó, đã có nhiều tác giả nghiên cứu và đƣa ra các phƣơng pháp để giải quyết vấn đề
này và trong đó, phƣơng pháp tìm kiếm tối ƣu dựa trên giải thuật di truyền đã chứng
tỏ đƣợc hiệu quả tốt hơn.
Xếp lịch học theo tín chỉ trong trƣờng đại học có rất nhiều yếu tố phức tạp
hơn so với dạng bài toán lập lịch thông thƣờng, nhƣ giáo viên, sinh viên, thời gian,
phòng học, các lớp tín chỉ và đặc biệt là các ràng buộc giữa các yếu tố này. Tổng
quát hơn, bài toán xếp lịch học gồm nhiều yếu tố đƣợc xem xét liên quan, chẳng hạn
nhƣ việc thi cử, thực hành, giảng đƣờng, vv….Thông thƣờng, bài toán lập lịch đƣợc
tiến hành theo cách truyền thống, bằng trực quan và tính toán trực tiếp của con
ngƣời. Nhƣng hiện nay, do sự đa dạng và nhiều thay đổi của các ràng buộc giữa các
yếu tố, đó là những hạn chế về nguồn lực và sự phức tạp của các yếu tố, giải bài
toán lập lịch thƣờng mất rất nhiều thời gian và nhân lực, kết quả do đó dẫn đến các

ứng dụng giải thuật di truyền cho bài toán lập lịch.
Nghiên cứu các mô hình lý thuyết, các thuật toán kết hợp lập trình thử
nghiệm trên máy tính. Đƣa vào ứng dụng trong thực tế để so sánh và đánh giá hiệu
quả của phƣơng pháp.

2


CHƢƠNG 1. GIỚI THIỆU BÀI TOÁN XẾP LỊCH
1.1. Bài toán xếp lịch học tín chỉ
Bài toán lập lịch nói chung trong các trƣờng đại học, cao đẳng (course
timetabling problem - CTP) bao gồm việc tìm kiếm việc phân bổ thời gian chính
xác trong một khoảng thời gian giới hạn cho một số sự kiện (nhƣ lớp tín chỉ, thi học
kỳ) và gán chúng vào một số tài nguyên (giáo viên, sinh viên và phòng học) để đảm
bảo rằng các ràng buộc đƣợc thỏa mãn. Tuy nhiên, trong đào tạo tín chỉ, tùy theo
đặc thù của từng trƣờng, bài toán xếp lịch đƣợc triển khai có sự khác nhau nhất
định. Trong luận văn này, tôi sử dụng tài nguyên gồm các giảng viên và phòng học.
Còn yếu tố sinh viên sẽ tham gia trong tính toán hàm mục tiêu (đƣợc đề cập ở phần
sau). Điều này sẽ thích hợp cho trƣờng hợp lịch tín chỉ sẽ đƣợc triển khai trƣớc khi
sinh viên đăng ký học.
Theo đặc thù của từng trƣờng đại học, cao đẳng và công tác tổ chức đào tạo
tín chỉ, để cho thuận tiện trong việc thiết kế thuật toán, trong luận văn này tôi giả
định cách thức tổ chức nhƣ sau: đầu mỗi học kỳ dựa vào khả năng đăng ký học tập
của sinh viên, chúng ta dự kiến các lớp tín chỉ để lập lịch và công bố cho sinh viên
đăng ký. Mỗi lớp tín chỉ gồm ký hiệu lớp, môn học, phân loại (lớp học phòng lý
thuyết nhỏ hoặc phòng hội trƣờng hoặc thực hành phòng máy). Bài toán lập lịch bây
giờ sẽ trở thành công việc phân công giảng viên, thời gian, phòng học cho mỗi lớp
tín chỉ đã dự kiến này sao cho thỏa mãn các yêu cầu, ràng buộc đặt ra.
Trong thực tế hiện nay đã có rất nhiều bài toán lập lịch đã đƣợc xây dựng và
đƣa vào ứng dụng thực tiễn:

thuộc lớp NP-khó nhƣ vậy tƣơng ứng với thời gian để giải sẽ tăng lên theo kích
thƣớc của bài toán. Trong những thời gian gần đây để giải quyết bài toán, các nhà
nghiên cứu đã đƣa ra một số phƣơng pháp giải quyết nhƣ sau:
(i) Phƣơng pháp tìm kiếm cục bộ:là phƣơng pháp tìm kiếm sẽ duyệt qua các
lời giải trong không tin tìm kiếm cho đến khi tìm ra lời giải đƣợc cho là tối ƣu hoặc

5


vƣợt quá thời gian tìm kiếm cho phép. Thuật toán có thể đƣợc sử dụng cho bài toán
tìm kiếm lời giải gần đúng tối ƣu trong một loạt các lời giải ứng viên. Gọi P là một
bài toán tối ƣu tổ hợp cần giải, và s là lời giải hiện hành giả sử là một lời giải khả
thi của P, và có hàm chi phí f(s). Miền lân cận N(s) đƣợc định nghĩa cho s là tập
những lời giải láng giềng khả thi s’ của s sao cho từ s ta có thể đạt tới s’ nhờ vào
một bƣớc chuyển m. Thao tác biến đổi này đƣợc lặp cho đến khi hội tụ về một lời
giải tốt. Lời giải này là lời giải cận tối ƣu, mà trong một số bài toán thực tế không
sai biệt gì nhiều với lời giải tối ƣu. Tìm kiếm cục bộ thƣờng đƣợc sử dụng cho
những bài toán tối ƣu hóa tổ hợp hoặc tối ƣu hóa rời rạc, tức là những bài toán trong
đó cần tìm trạng thái tối ƣu hoặc tổ hợp tối ƣu trong không gian rời rạc các trạng
thái, và không quan tâm tới đƣờng đi dẫn tới trạng thái đó.
(ii) Phƣơng pháp dùng thuật giải mô phỏng luyện kim (simulated annealing):
là một kỹ thuật tìm kiếm ngẫu nhiên mà tỏ ra rất hữu kiệu cho các bài toán tối ƣu
hóa quy mô lớn. Trong kỹ thuật này, ta sử dụng tham số nhiệt độ để điều khiển tốc
độ hội tụ trong giải thuật. Khi khởi tạo tham số nhiệt cho ở mức cao và nhiệt độ sẽ
giảm dần trong quá trình tìm kiếm lời giải, tại những mức nhiệt độ cao, các bƣớc
chuyển đƣợc chấp nhận một cách ngẫu nhiên (bất luận là bƣớc chuyển có cải thiện
đƣợc hàm chi phí của lời giải hay không), khi nhiệt độ đƣợc giảm xuống thì xác
suất để chấp nhận một lời giải có cải thiện sẽ đƣợc tăng lên và xác suất chấp nhận
một lời giải không cải thiện đƣợc giảm xuống.
(iii) Phƣơng pháp tìm kiếm Tabu: đƣợc đề xuất bởi Glover năm 1986, là

nghiên cứu và trình bày ở phần sau.

7


1.3. Ràng buộc trong bài toán
Bài toán xếp thời khóa biểu tín chỉ là việc phân công giảng viên, thời gian,
phòng học cho mỗi lớp tín chỉ đã dự kiến sao cho thỏa mãn các yêu cầu, ràng buộc
đã đặt ra.
Thông thƣờng, các ràng buộc của bài toán cần thỏa mãn đƣợc chia thành hai
loại: ràng buộc cứng và ràng buộc mềm. Những ràng buộc cứng phải chắc chắn
đƣợc đáp ứng và thỏa mãn. Những ràng buộc cứng này bao gồm những yêu cầu sau
đây:
- (H1) Không đƣợc phép phân bổ một tài nguyên (giảng viên, phòng học)
cho các sự kiện khác nhau (lớp tín chỉ) trong cùng một thời điểm.
Ví dụ:
Một giáo viên không thể dạy hai lớp môn cùng một thời điểm.
Hay cùng một thời điểm không thể xếp hai lớp môn vào cùng một phòng học
đƣợc.
- (H2) Các phòng học đƣợc gán cho một sự kiện (lớp tín chỉ) phải nằm trong
bộ nguồn tài nguyên phù hợp dành cho sự kiện đó. Theo đó, một sự kiện đƣợc tổ
chức trong một phòng phải có cơ sở hạ tầng phù hợp để có thể tổ chức sự kiện, ví
dụ lớp học phòng máy, lớp học hội trƣờng, v.v.
Ví dụ:
Chúng ta không thể xếp một lớp học lý thuyết 100 sinh viên vào trong phòng
học thực hành máy tính ngồi đƣợc 35 sinh viên.
- (H3) Một sự kiện (lớp tín chỉ) chỉ đƣợc phân công một giảng viên nếu
ngƣời đó có đủ kiến thức và năng lực đáp ứng cho việc giảng dạy chuyên môn của
lớp đó.
Ví dụ:

- (S4) Nên ƣu tiên xếp các lớp tín chỉ có ràng buộc tiên quyết về chuyên môn
vào cùng một khe thời gian. Điều này nhằm làm tăng khả năng đăng ký cho nhiều
sinh viên đối với lịch đƣợc xếp.
Ví dụ:
Chúng ta nên xếp ƣu tiên cho môn cơ sở lập trình và môn lập trình hƣớng đối
tƣợng vào cùng ca học, vì môn cơ sở lập trình là điều kiện tiên quyết để học môn
lập trình hƣớng đối tƣợng (để đảm bảo cho sinh viên đăng ký học đƣợc nhiều nhất).

9


- (S5) Khả năng đăng ký học của mỗi sinh viên đối với lịch đƣợc xếp là cao
nhất có thể. Điều này đặc biệt đáp ứng cho việc tổ chức đào tạo tín chỉ, lịch học các
lớp tín chỉ đƣợc sắp xếp trƣớc, sau đó sinh viên sẽ đăng ký tham gia học, thay vì
cách xếp lịch theo niên chế là dành cho từng lớp hành chính gồm các sinh viên cố
định.

10


CHƢƠNG 2. KIẾN THỨC CƠ SỞ
2.1. Giải thuật di truyền (GA)
2.1.1. Giới thiệu giải thuật di truyền
Giải thuật di truyền (Gennetic Algorithims – GA) là một kỹ thuật trong tính
toán mềm giúp giải quyết bài toán bằng cách mô phỏng sự tiến hóa tự nhiên của con
ngƣời hay của sinh vật nói chung trong điều kiện quy định sẵn của môi trƣờng.
Giải thuật di truyền cũng nhƣ các giải thuật tiến hóa nói chung hình thành
dựa trên quan niệm cho rằng quá trình tiến hóa tự nhiên là quá trình hoàn hảo nhất,
hợp lý nhất và tự nó đã mang tính tối ƣu. Quá trình tiến hóa thể hiện tính tối ƣu ở
chỗ, thế hệ sau bao giờ cũng tốt hơn (phát triển và hoàn thiện hơn) thế hệ trƣớc.

mạnh riêng và một số tác giả đã kết hợp hai thuật toán trên làm tăng sức mạnh tìm
kiếm. Trong nhiều nghiên cứu, các tác giả đã nhúng tham số nhiệt độ T mô phỏng
nhiệt tôi luyện trong SA để điều khiển các phép toán gen của GA. Trong đó, các
tham số xác suất để chọn lọc, lai ghép và đột biến đƣợc thay đổi qua từng thế hệ di
truyền, chúng đƣợc tính dựa trên tham số nhiệt độ của thế hệ hiện tại. Tham số nhiệt
ban đầu đƣợc tính dựa trên số thế hệ tiến hóa (thƣờng khá lớn đảm bảo tính đa dạng
của quần thể), sau mỗi thế hệ tham số nhiệt giảm dần để đảm bảo tính hội tụ và tính
ổn định. Kết hợp này phù hợp với các chiến lƣợc thay đổi tham số trong GA, làm
tăng tốc độ hội tụ tìm kiếm và hiệu quả của thuật toán, ta gọi đây là thuật toán di
truyền lai (SGA).
Theo 0, giải thuật di truyền (hay giải thuật tiến hóa nói chung) là một trong
những phát triển quan trọng của những nhà nghiên cứu về tính toán ứng dụng cuối
thế kỷ trƣớc trong việc giải xấp xỉ các bài toán tối ƣu toàn cục. Việc khai thác
nguyên lí tiến hóa nhƣ là một định hƣớng heuristics đã giúp cho giải thuật di truyền
giải quyết hiệu quả các bài toán tối ƣu (với các lời giải chấp nhận đƣợc) mà không
cần sử dụng các điều kiện truyền thống (liên tục hay khả vi) nhƣ là điều kiện tiên
quyết. Một trong những đặc tính quan trọng của giải thuật di truyền là làm việc theo
quần thể các giải pháp. Việc tìm kiếm bây giờ đƣợc thực hiện song song trên nhiều
điểm (multipoints). Tuy nhiên, đây không phải là thuật toán tìm kiếm đa điểm đơn
thuần vì các điểm có tƣơng tác với nhau theo nguyên lí tiến hóa tự nhiên. Trong ngữ
cảnh sử dụng giải thuật di truyền, ngƣời ta có thể dùng khái niệm ―cá thể‖ tƣơng
đƣơng với khái niệm ―giải pháp‖.
Sơ đồ tổng thể của thuật toán di truyền nói chung đƣợc mô tả nhƣ sau:
12


Begin

Nhận các tham số đầu vào của bài toán


quần thể).
• Bƣớc 3: Tính giá trị thích nghi hay còn gọi là hàm mục tiêu (fitness) của
các cá thể trong P(t).

13


• Bƣớc 4: Kiểm tra điều kiện dừng thuật toán, có thể đạt đƣợc cá thể tốt nhất
cần tìm kiếm hoặc đạt đến thế cuối cùng đƣợc thiết lập. Trƣờng hợp chƣa đạt, thuật
toán chuyển sang bƣớc tiếp ở sau để thực hiện tiến hóa.
• Bƣớc 5: Chọn lọc các cá thể từ quần thể hiện tại để tạo bể lai ghép MP =
se{P(t)} gồm các thể đóng vai trò là bố mẹ, với se là toán tử lựa chọn.
• Bƣớc 6: Thực hiện lại ghép để tạo quần thể P’(t) = cr{MP} gồm các thể
con, với cr là toán tử lai ghép.
• Bƣớc 7: Thực hiện đột biến các cá thể trong P’(t) để tạo quần thể mới P‖(t)
= mu{P’(t)} gồm các cá thể con sau khi áp dụng phép đột biến, với mu là toán tử
đột biến.
• Bƣớc 8: Xác định P(t+1) = P‖(t), đặt t = t+1 và quay lại Bƣớc 3.

2.1.2. Các vấn đề trong giải thuật di truyền
2.1.2.1. Biểu diễn cá thể
Biểu diễn cá thể hay còn gọi là mã hóa cá thể (chromosome encoding).
Trong giải thuật di truyền cách mã hóa cá thể rất quan trọng, nó không chỉ quyết
định đến hiệu quả của thuật toán mà còn ảnh hƣớng đến việc áp dụng các toán tử
tiến hóa trong các bƣớc lai ghép và đột biến. Với đặc trƣng của mỗi bài toán khác
nhau chúng ta có thể có nhiều cách biểu diễn cá thể.
Một trong những cách biểu diễn truyền thống của GA là biểu diễn nhị phân.
Với phép biểu diễn này, lời giải cho bài toán đƣợc biểu diễn nhƣ là một véc-tơ gồm
các chữ số nhị phân, trong đó chia thành các đoạn gọi là nhiễm sắc thể
(chromosome). Mỗi nhiễm sắc thể bao gồm nhiều gen, trong đó một gen đại diện

nhiễm sắc thể là một chuỗi các giá trị và kiểu mã hóa này đƣợc sử dụng một khi
nhiều các giá trị phức hợp đƣợc yêu cầu. Nó có thể đƣợc thể hiện nhƣ thể hiện trong
hình 2.4.

15


Hình 2. 4.Minh họa phƣơng pháp mã hóa giá trị

d) Mã hóa dạng cây
Là phƣơng pháp phù hợp cho việc tiến hóa các biểu thức hoặc tiến hóa các
chƣơng trình, chẳng hạn lập trình tiến hóa. Trong mã hóa dạng cây, mỗi nhiễm sắc
thể là một cây các đối tƣợng, hàm hoặc các lệnh trong ngôn ngữ lập trình.
Ngôn ngữ lập trình LISP (Locator/identifier separation protocol) đƣợc sử
dụng cho kiểu mã hóa này. Chƣơng trình LISP có thể đƣợc biểu diễn trong một cấu
trúc cây với hai phép lai ghép và đột biến. Trong mã hóa dạng cây, các nhiễm sắc
thể đƣợc biểu diễn nhƣ thể hiện trong hình 2.5.

Hình 2. 5. Minh họa phƣơng pháp mã hóa dạng cây

Một điều đáng quan tâm là các phƣơng pháp mã hóa ở trên có thể biểu diễn
trực tiếp lời giải của bài toán, tức là các tham số trong lời giải đƣợc thể hiện rõ
trong cách mã hóa. Tuy nhiên, trong một số bài toán hoặc các trƣờng hợp đặc biệt,
lời giải bài toán khó để biểu diễn trực tiếp và do đó cần phải áp dụng việc biểu diễn
gián tiếp lời giải cho cá thể của GA. Theo cách này, chúng ta cần một công cụ để
sinh đầy đủ lời giải của bài toán từ cá thể đƣợc mã hóa và thƣờng đƣợc xây dựng
bởi một đơn vị hàm hoặc đơn vị chƣơng trình.

16