ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CễNG NGHỆ
TRẦN QUỐC HƯNG TÍNH TOÁN TIẾN HÓA
VÀ ỨNG DỤNG LẬP THỜI KHÓA BIỂU
TRƯỜNG TRUNG HỌC PHỔ THÔNG
Chuyên ngành: CÔNG NGHỆ THÔNG TIN
Mã số: 1.01.1 LUẬN VĂN THẠC SĨ Hà Nội – Năm 2004
ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CÔNG NGHỆ
TRẦN QUỐC HƯNG

1.1.1. Lược sử 8
1.1.2. í tưởng 10
1.1.3. Đặc thù của GA cổ điển 10
1.1.4. Cấu trúc của GA cổ điển 11
1.1.4.1. Cấu trỳc nhiễm sắc thể và kiểu gene 12
1.1.4.2. Thủ tục GA 13
1.1.4.3. Phương pháp mó húa và giải mó 15
1.1.4.4 Thủ tục chọn lọc (Selection) 17
1.1.4.5. Quỏ trỡnh tỏi tạo 18
1.1.4.5.1. Cỏc toỏn tử di truyền 18
1.1.4.5.2. Quỏ trỡnh tỏi tạo 20
1.1.4.6. Điều kiện kết thỳc 20
1.1.5. Sự hội tụ của GA 20
1.1.6. Biểu diễn bằng vector số thực 25
1.2. Tớnh toỏn tiến húa 26
1.2.1 Các chiến lược tiến hóa (Evolution Strategies – ES) 28
1.2.1.1 Chiến lược tiến hóa hai thành viên 28
1.2.1.2 Chiến lược tiến hóa đa thành viờn: ký hiệu ( +1) ES 30
1.2.1.3 Chiến lược tiến hóa đa thành viên cải tiến 31
1.2.2 Lập trỡnh tiến húa (Evolutionary Programming EP) 32
1.2.2.1. í tưởng 32

Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
2
1.2.2.2. Biểu diễn nhiễm sắc thể 32
1.2.3 Lập trỡnh di truyền (Genetic Programming – GP) 34
1.2.3.1. í tưởng của GP 34
1.2.3.2. Biểu diễn nhiễm sắc thể 34
1.2.4 Chương trỡnh tiến húa (Evolution Programmes – EPs) 36

3.4.2. Cỏc toỏn tử lai ghộp 60
3.5. Quỏ trỡnh chọn lọc 61
3.6 Thủ tục tiến húa 62

Chƣơng IV: Xây dựng phần mềm 64
4.1 Tổ chức dữ liệu 64
4.2. Sơ đồ phân ró chức năng 65
4.3. Một số chức năng và giao diện của phần mềm 67
4.3.1. Chức năng “Nhập dữ liệu” 67
4.3.1.1. Chức năng “Bảng phõn cụng Giảng dạy” 67
4.3.1.2 Chức năng “Bảng đăng ký tiết dạy bằng tay” 68
4.3.2. Chức năng Hiển thị TKB 69
4.3.2.1 Chức năng “Xem/In Thời khóa biểu Giáo viên” 69
4.3.2.2 Chức năng “In Thời khóa biểu Giáo viên” 70
4.3.2.3 Chức năng “Xem/In thời khóa biểu Lớp” 73
4.3.2.4 Chức năng “In thời khóa biểu các lớp” 74
4.4. Thử nghiệm phần mềm 75
4.4.1. Kết quả đạt được của phần mềm 75
4.4.2. Bảng kết quả thử nghiệm 76
Kết luận 77
Tài liệu tham khảo 78

Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
4
MỞ ĐẦU

Thời khóa biểu của trườ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 khi học tập.

Xuất phát từ những vấn đề trên, đề tài “Tính toán tiến hóa và áp dụng lập
thời khóa biểu trường Trung học phổ thông”, khúa luận tập trung nghiờn cứu
giải thuật di truyền và phương pháp tính toán tiến hóa đồng thời giải quyết bài
toán thời khóa biểu về mặt lý thuyết lẫn xõy dựng phần mềm, xem như một
thử nghiệm đầu tiên ở vùng Tây Nguyên xa xôi.
Do khả năng và thời gian hạn chế, tác giả chỉ mới hoàn thành phần mềm ở
mức cơ bản nhất, chỉ tạm sử dụng nội bộ trong trường nơi tác giả công tác.
Hy vọng trong thời gian tới, tác giả sẽ bổ sung thêm chức năng cho phần mềm
và hoàn chỉnh thành sản phẩm sử dụng được trong ngành giáo dục Đăk Lăk.

Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
6
Cấu trúc của luận văn như sau:
Chƣơng I: Giải thuật di truyền và Tính toán tiến hóa
Giới thiệu tóm lược về lịch sử, sự phát triển và các kết quả đạt được
của giải thuật di truyền cổ điển trong việc giải quyết bài toán tối ưu hàm số
nhiều biến. Các phần tiếp theo trỡnh bày cỏc khỏi niệm, các đặc trưng, cấu
trúc và cơ chế hoạt động của giải thuật di truyền. Minh họa việc tỡm giỏ trị
cực đại hàm số nhiều biến bằng giải thuật di truyền cổ điển.
Giới thiệu sự phỏt triển và cỏc cải tiến của giải thuật di truyền với tờn
gọi chung là tớnh toỏn tiến hóa. Nêu đặc trưng trong việc thay đổi cách
biểu diễn nhiễm sắc thể và các toán tử di truyền cho phù hợp với từng bài
toán cụ thể. Các hướng tiếp cận chính của phương pháp tính toán tiến hóa.
Nêu cấu trúc và các bước cơ bản để xây dựng một chương trỡnh tiến húa.
Chƣơng II: Tổng quan các bài toán thời khóa biểu
Phát biểu sơ bộ các loại thời khóa biểu, chủ yếu là bài toán thời khóa
biểu trường Trung Học Phổ Thông. Nêu các đặc trưng nghiệp vụ, các ràng
buộc của từng loại thời khóa biểu.
Chƣơng III: Mô hỡnh tiến húa cho bài toỏn cho bài toỏn thời khúa
1.1. GIẢI THUẬT DI TRUYỀN:
1.1.1. Lƣợc sử
í tưởng giải thuật di truyền được nêu ra từ những năm 1950-1960 bởi các
nhà sinh học nhằm giải quyết các bài toán di truyền trong sinh học. Khi đó,
giải thuật di truyền chưa trở thành một phương pháp luận mà chỉ ở mức độ
giải quyết các bài toán sinh học riêng lẻ.
A.S Fraser là người tiên phong nêu lên sự tương đồng giữa sự tiến hóa của
sinh vật trong tự nhiên và chương trỡnh tin học giả tưởng về giải thuật di
truyền cổ điển (GA-Genetic Algorithm).
Thực tế, John Henry Holland mới là người đầu tiên triển khai ý tưởng và
phương thức giải quyết các bài toán tối ưu dựa theo sự tiến hóa tự nhiên của
sinh vật. Năm 1975, John Henry Holland và các đồng nghiệp của ông ở
trường Đại học Michigan – Hoa Kỳ công bố Giải thuật di truyền và ông được
xem là người đề xướng giải thuật này. Ông đó đúc kết các bài giảng và các
bài báo thành sách với tựa đề Adaptation in Nature and Artificial Systems –
Sự mụ phỏng theo tự nhiờn và cỏc hệ thống nhõn tạo. Trong sách, J.H.
Holland đó trỡnh bày rất hệ thống phương pháp giải quyết các bài toán tối ưu
hàm nhiều biến nhờ một kiểu gene nhị phân và nhiều công trỡnh nghiờn cứu
về giải thuật di truyền, gọi tắt là GA.

Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
9
Sau Holland, nhiều đồng nghiệp của ông như Kenneth De Jong, David E.
Goldberg đó dần tạo nờn nền tảng lý thuyết vững chắc cho GA và thực hiện
cỏc ỏp dụng của GA để giải quyết các bài toán phức tạp trong thực tế. Kể từ
đó, nhiều công trỡnh nghiờn cứu về GA đó được công bố ở nhiều nơi trên thế
giới.

thích nghi thấp sẽ có nhiều nguy cơ bị tiêu vong hoặc phát triển chậm. Sự
thích nghi đó được đúc kết và ghi lại trong cấu trỳc của nhiễm sắc thể của
chỳng.
Việc giải bài toỏn thực tế cú thể xem là việc tỡm kiếm trong một khụng
gian cỏc lời giải tiềm năng nhằm tỡm ra lời giải tốt nhất hoặc chấp nhận được
mà ta có thể gọi là quá trỡnh tối ưu hóa.
Đối với không gian tỡm kiếm nhỏ, đơn giản nhất là dùng kỹ thuật “vét
cạn”, nghĩa là liệt kê toàn bộ lời giải tiềm năng, sau đó chọn ra lời giải. Đối
với không gian tỡm kiếm khỏ lớn thỡ kỹ thuật vột cạn cú độ phức tạp rất lớn,
khó chấp nhận được. Khi đó, giải thuật di truyền tỏ ra rất thớch hợp cho việc
giải quyết bài toỏn tỡm kiếm lời giải tối ưu.
GA không chú trọng đến giải pháp duy nhất và chính xác như các phương
thức cổ điển, trái lại GA xét đến toàn bộ các giải pháp và chọn lấy giải pháp
tương đối tốt nhất.
GA dựa trờn tớnh ngẫu nhiên như trong thế giới tự nhiên của sinh vật,
nhưng được hướng dẫn bởi hàm thích nghi (Fitness Function), hơn nữa GA
cũn cú nền tảng lý thuyết vững chắc là lý thuyết sơ đồ (Schema theorem)
[20].
1.1.3. Đặc thù của GA cổ điển

Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
11
GA lập luận ngẫu nhiờn thay vỡ xỏc định.
GA duyệt toàn bộ các giải pháp, sau đó chọn lấy giải pháp tương đối
tốt nhất dựa trên hệ số thích nghi.
GA không để ý đến chi tiết vấn đề mà chỉ chỳ ý đến giải pháp, đặc
biệt là dóy số tượng trưng cho giải pháp.
Goldberg và Zbiniev Michalewicz nêu ra đặc trưng của GA như sau:
GA làm việc với một mó húa của tập hợp tham số mà khụng phải

dần.
GA là kỹ thuật tối ưu dựa trên khái niệm chọn lọc tự nhiên và di truyền.
Do vậy, lời giải của bài toán được trỡnh bày như các gene trong nhiễm sắc
thể. GA mô tả một nhóm các lời giải tiềm năng được đề cử, qua tiến hóa và
chọn lọc tự nhiên các nhiễm sắc thể với độ thích nghi tốt hơn sẽ xuất hiện.
Chọn lọc tự nhiên đảm bảo cho cá thể có độ thích nghi tốt nhất sẽ được
truyền lại cho các thế hệ con cháu (các quần thể tương lai). Phép lai ghép
(Crossover) kết hợp các gene từ hai cá thể bố mẹ để tạo thành hai cá thể con
mới (Offspring) với độ thích nghi có chiều hướng cao hơn bố mẹ. Phép biến
dị (Mutation) cho phép tạo ra chất liệu di truyền mới, tạo ra những đột phá
trong tỡm kiếm.
GA cung cấp sự cải tiến thế hệ về độ thích nghi của các cá thể và sau
nhiều thế hệ sẽ tạo ra các cá thể chứa những thiết lập biến đổi đó được tối ưu.
Mỗi cá thể (Individual) trong GA thường chỉ gồm một nhiễm sắc thể. Do
vậy thuật ngữ cá thể và nhiễm sắc thể được dùng không phân biệt ngữ nghĩa.
1.1.4.1. Cấu trỳc nhiễm sắc thể và kiểu gene
Trong GA cổ điển, mỗi cá thể (hay nhiễm sắc thể) được mó húa bởi cỏc
chuỗi nhị phõn.

Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
13
Vớ dụ: một nhiễm sắc thể gồm 8 gene như sau:
1
0
0
1
0
1
1

Mỗi x trong M, được mó húa bởi một chuỗi nhị phõn z = (x
1
, x
2
, … x
m
),
với m là độ dài của chuỗi. Chuỗi này gọi là nhiễm sắc thể hay cá thể, mỗi x
i

gọi là một gene. Người ta xây dựng các thủ tục mó húa và giải mó tương ứng.
Xây dựng hàm eval trên tập nhiễm sắc thể để đánh giá độ thích nghi của
mỗi cá thể: eval(z) = f(x), trong đó x là vector tương ứng với z.
Tương ứng với t = 0, là điểm xuất phát thủ tục GA hay thế hệ ban đầu, ta
khởi tạo ngẫu nhiên quần thể ban đầu P(0) gồm N cá thể.
Sau đó tiến hành đánh giá độ thích nghi của quần thể. Quá trỡnh tiến húa
được diễn ra thông qua quá trỡnh chọn lọc cỏc cỏ thể tốt, biến đổi các cá thể
bởi các toán tử di truyền, rồi lại đánh giá độ tốt của quần thể cho đến khi chọn
được các cá thể đủ tốt.
Cấu trúc của GA cổ điển như sau:
Procedure GA
Begin
t  0;
Khởi tạo P(t);
Đánh giá P(t);
Repeat
t

t + 1;
Chọn Q(t) từ P(t-1); // bởi bỏnh xe xổ số

1.1.4.3. Phương pháp mó húa và giải mó
Biểu diễn mó nhị phõn và giải mó của mỗi lời giải tiềm năng thực hiện
như sau:
Mó húa: Giả sử ta cần tỡm cực đại của hàm số n biến f(x
1
, x
2
, … x
n
)
với sai số mỗi biến x
i
là 10
-p

(sai số đến p chữ số thập phân).
Ta chia mỗi đoạn [a
i
, b
i
] thành (b
i
a
i
) x 10
p
đoạn bằng nhau. Ký hiệu m
i
là
số tự nhiờn nhỏ nhất thỏa món:

i
m
j
j
j
bk
sẽ thỏa món yờu cầu về độ chính xác và x được biểu diễn bởi chuỗi nhị phân
có độ dài
n
j
j
mm Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
16
m
1
bits đầu tiên của chuỗi ứng với một giá trị x
1
[a
1
, b
1
], m
2
bits tiếp
theo ứng với một giỏ trị x
2

2
5 với sai
số cỏc biến là 10
-2
Vỡ b
1
– a
1
= 3 – (-1) = 4; 4x10
2
= 400 và 2
8
< 400 < 2
9
nên cần 9 gene để
biểu diễn x
1

Tương tự, b
2 –
a
2
= 5 – 3 = 2; 2x10
2
= 200 và 2
7
< 200 < 2
8
nên cần 8 gene
để biểu diễn x

iii
ab
kax

hay là:
1
0
10
12
)(
.)2.(
i
i
m
j
m
ii
j
jii
ab
bax
Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
17
1.1.4.4 Thủ tục chọn lọc (Selection)
Các cá thể được chọn lọc theo độ thích nghi của chúng để tham gia vào
pha tiếp theo của quá trỡnh tiến húa. Cỏ thể cú độ thích nghi cao hơn có cơ

p
i
i
)(

Tớnh xỏc suất tớch lũy q
i
cho mỗi cỏ thể v
i
:
i
j
ji
pq
1
, i = 1, 2, … N
Quỏ trỡnh chọn lọc
Quỏ trỡnh chọn lọc quần thể Q(t) từ P(t – 1) dựa vào bỏnh xe xổ số được
thực hiện như sau:

Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
18
Đối với mỗi số tự nhiên k = 1, 2, , N, phát sinh một số thực ngẫu nhiên r
k

[0, 1]
Nếu r
k
q

a. Phép lai hay trao đổi chéo (Crossover Operator): Kết hợp các đặc tính
trên nhiễm sắc thể của bố và mẹ để tạo thành hai cá thể con mới, bằng
cách hoán đổi các đoạn gene tương ứng trên các nhiễm sắc thể của bố và

10%
30%
20%
25%
15%
1
2
3
4
5

Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
19
mẹ. Phép lai nhằm nâng cao chất lượng cá thể, do vậy sẽ ảnh hưởng đến
tốc độ hội tụ của quá trỡnh tiến húa.
Với hai nhiễm sắc thể tựy ý:
x = (x
1
, x
2
, …, x
m
)
y = (y
1

1
1
0
0
1
0
1
Parent 2
1
1
0
0
0
1
0
1
1
0
Nếu thực hiện lai ghép sau gene thứ 5, sẽ tạo ra hai con như sau:
Child 1
0
1
0
1
1
1
0
1
1
0

i
, i = k
Vớ dụ:
Parent
0
1
0
1
1
0
0
1
0
1
Sau khi biến dị tại vị trớ 6:
Child
0
1
0
1
1
1
0
1
0
1
1.1.4.5.2. Quỏ trỡnh tỏi tạo
Cho trước xác suất lai p
c
và xỏc suất biến dị p

Tổ hợp nhiều cách: dùng nhiều phương án khác nhau cho vấn đề.
Chẳng hạn: chạy theo số thế hệ, đánh giá và cho chạy tiếp theo kết
quả…
1.1.5. Sự hội tụ của GA
Các kết quả nghiên cứu, đánh giá về sự hội tụ của GA cũn rất nghốo [7] ,
[8], [20], chỉ mới chứng minh sự hội tụ theo xỏc suất tới lời giải tối ưu của bài
toán. Tuy nhiên, về mặt thực hành, giải thuật di truyền vẫn là một giải thuật
được ưa thich để giải các bài toán khó trong thực tế và cho lời giải đủ tốt. Đặc
biệt, GA tỏ ra rất hiệu quả đối với các bài toán mà hàm mục tiêu phức tạp, có
nhiều cực trị địa phương và không trơn. Đối với các bài toán đó cú phương
pháp giải tốt bằng phương pháp truyền thống thỡ GA vẫn tỏ ra kộm hiệu quả
hơn.
Một vớ dụ minh họa
Tỡm giỏ trị cực đại của hàm hai biến:
f(x
1
, x
2
) = 10 + x
1
sinx
1
+ x
2
sinx
2
trờn miền –1 x
1
3; 3 x
2

để biểu diễn x
2

Do vậy, m = 17 là độ dài của chuỗi nhị phõn
+ Khởi tạo:
Giả sử ta khởi tạo ngẫu nhiên 10 cá thể như sau:

Phương pháp Tính toán tiến hóa
Và ỏp dụng lập Thời khúa biểu Trung học Phổ thụng
22
v
1
= (10011010000000111) tương ứng với x
1
= 1.41; x
2
= 3.15;
eval(v
1
)= 12.68;
v
2
= (11100010010011011) tương ứng với x
1
= 2.54; x
2
= 4.22;
eval(v
1
)= 14.78;

v
6
= (00010100001001010) tương ứng với x
1
= -0.69 x
2
= 3.58;
eval(v
1
)= 7.53;
v
7
= (00100010000011010) tương ứng với x
1
= -0.47; x
2
= 3.20;
eval(v
1
)= 9.23;
v
8
= (10000110000111010) tương ứng với x
1
= 1.01; x
2
= 3.45;
eval(v
1
)= 7.52;

+ Chọn lọc: giả sử cỏc r
i
ngẫu nhiên như sau:
r
1
= 0.52; r
2
= 0.17;
r
3
= 0.70; r
4
= 0.01;
r
5
= 0.78; r
6
= 0.31;
r
7
= 0.42; r
8
= 0.28;
r
9
= 0.64; r
10
= 0.95;
Ta chọn lọc được quần thể Q(1) như sau:
Stt

0.17
v
2
= (11100010010011011)
u
2

3.
0.11
0.40
0.70
v
7
= (00100010000011010)
u
3

4.
0.11
0.51
0.78
v
1
= (10011010000000111)
u
4

5.
0.08
0.59

0.28
v
2
= (11100010010011011)
u
8

9.
0.06
0.90
0.64
v
6
= (00010100001001010)
u
9

10.
0.10
1.00
0.95
v
6
= (00010100001001010)
u
10+ Phộp lai
Với xỏc xuất lai p