ĐẠ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

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Ĩ

NGƯỜI HƯỚNG DẪN KHOA HỌC:
Tiến Sĩ HOÀNG XUÂN HUẤN



Hà Nội – Năm 2004

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
1
MỤC LỤC

Mở đầu 4
Cấu trúc của luận văn 6
Chƣơng I: Giải thuật di truyền và Tính toán tiến hóa 8
1.1. Giải thuật di truyền 8

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

1.2.4.1. í tưởng 36
1.2.4.2. So sánh GA cổ điển và các chương trỡnh tiến húa 36
1.2.5. Các bước xây dựng một chương trỡnh tiến húa 39

Chƣơng II: Tổng quan bài toán thời khóa biểu và các phương pháp tiếp cận
41
2.1 Tổng quan: 41
2.2. Cỏc bài toỏn thời khúa biểu 43
2.2.1. Thời khúa biểu Tiểu học 43
2.2.2. Thời khóa biểu Trung học cơ sở, Trung học phổ thông 43
2.2.3. Thời khóa biểu Cao đẳng-Đại học 45
2.3. Các phương pháp tiếp cận hiện nay 48

Chƣơng III: Mô hỡnh tiến húa cho bài toỏn thời khúa biểu THPT 51
3.1. Biểu diễn nhiễm sắc thể và kiểu gene 51
3.2. Khởi tạo quần thể ban đầu 53
3.2.1. Phõn bố số tiết học trong mỗi ngày cho từng khối lớp 53
3.2.2. Thủ tục tạo ngẫu nhiờn 1 nhiễm sắc thể 53
3.3. Xác định hàm thích nghi 56
3.4. Cỏc toỏn tử di truyền 57
3.4.1 Cỏc toỏn tử biến dị 57
3.4.1.1 Toán tử đổi chỗ tiết học trong một lớp (khử tiết cụm) 57

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
3
3.4.1.2 Toán tử đổi chỗ giỏo viờn trong một lớp (khử tiết trựng) 58
3.4.1.3 Toỏn tử chuyển dịch mụn học trong một ngày (khử tiết cỏch) 59
3.4.1.4 Toỏn tử dồn tiết của một mụn học của một lớp (khử tiết phõn tỏn) 59
3.4.1.5 Toán tử thay đổi toàn bộ lớp 60

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.

Đó từ lõu, việc lập thời khúa biểu là vấn đề quan trọng của nhà trường và
phải luôn luôn hoàn thành trước khi triển khai giảng dạy. Lập thời khóa biểu
bằng phương pháp thủ công là công việc rất nặng nề, tốn nhiều thời gian và
dễ vị phạm các ràng buộc về nghiệp vụ. Do vậy, khi áp dụng phải trải qua
điều chỉnh vài lần mới có thể đạt được yêu cầu cơ bản.
Lập thời khóa biểu là vấn đề của tất cả các hệ thống trường học từ bậc
phổ thông đến cao đẳng đại học phải thường xuyên đối mặt trong việc tỡm
ra một giải phỏp tối ưu hoặc chấp nhận được.
Các bài toán thời khóa biểu rất phong phú và đa dạng bởi những ràng
buộc và yêu cầu đặc trưng của từng hệ đào tạo, thậm chí từng trường học.
Bài toỏn thời khúa biểu thuộc lớp bài toỏn NP khú [12] nên các giải thuật
truyền thống khó giải quyết được trọn vẹn các yêu cầu nghiệp vụ và yêu cầu
về thời gian thực hiện.

Trong gần ba thập niên qua, giải thuật di truyền và các cải tiến-phát triển
của nó gọi chung là tính toán tiến hóa [7] đó thực sự tạo ra cỏc kết quả rất khả
quan khi ỏp dụng giải quyết cỏc bài toỏn tối ưu. Giải thuật di truyền và tính
toán tiến hóa mô phỏng sự tiến hóa của tự nhiên của sinh học và gần đây nhất
là phương pháp tối ưu hóa đàn kiến do Dorigo đề xuất là hướng tiếp cận hiện
đại nhất. Cả hai loại giải thuật trên đó tỏ ra rất hiệu quả trong việc ỏp dụng

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
5
giải quyết cỏc bài toỏn tối ưu trong thực tế, tiêu biểu là bài toán lập thời khóa
biểu trường học, là một bài toán thú vị và có tính thực tiễn cao.
Ở Việt Nam đó cú một vài phần mềm lập thời khúa biểu khỏ tốt, nhưng
chưa đáp ứng hết các yêu cầu thực tế cũng như cách tổ chức giảng dạy của
từng trường. Ở Đăk Lăk, chưa có phần mềm lập thời khóa biểu riêng đáp ứng
các điều kiện cụ thể của miền núi.

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

biểu Trung Học Phổ Thụng
Đây là nội dung chính của luận văn. Các vấn đề được trỡnh bày là phỏt
biểu đầy đủ các ràng buộc của bài toán thời khóa biểu Trung học phổ
thông, giới thiệu cách biểu diễn nhiễm sắc thể và các toán tử di truyền để
giải quyết bài toán bằng phương pháp tính toán tiến hóa.
Chƣơng IV: Xây dựng phần mềm lập thời khóa biểu THPT
Giới thiệu các chức năng cơ bản của phần mềm minh họa bài toán lập
thời khóa biểu Trung Học Phổ Thông theo phương pháp tính toán tiến hóa,

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
7
một số giao diện của phần mềm. Phần mềm được xây dựng bằng Access
2000.
Kết quả thử nghiệm của phần mềm trên bộ dữ liệu thực của trường
Trung Học Phổ Thông Buôn Ma Thuột. Đánh giá hiệu quả và tính khả
dụng của phần mềm.






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
8
Chƣơng I
GIẢI THUẬT DI TRUYỀN
VÀ TÍNH TOÁN TIẾN HểA
(Genetic Algorithm and Evolutionary Computation)



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.

Hai đồng nghiệp xuất sắc của ông là Kenneth De Jong và David E.
Goldberg đó cú nhiều cụng trỡnh nghiờn cứu về GA cổ điển và những phát
triển của nó trong nhiều lĩnh vực khác nhau. Đặc biệt, David E. Golberg đưa
ra “Thuật toán di truyền hỗn hợp” vào năm 1993, được xem là một cải tiến
quan trọng trong GA cổ điển. Các nhà nghiên cứu về GA cổ điển lại tiếp tục
đưa ra nhiều cải tiến vô cùng phong phú cho GA cổ điển và được gọi chung là
Tính toán tiến hóa – Evolutionary Computation [7].
GA đó kết hợp với cỏc kỹ thuật thuộc lĩnh vực trớ tuệ nhõn tạo như Hệ
chuyên gia (Expert System), Mạng Neuron nhân tạo (Artificial Neural
Network), Logic mờ (Fuzzy Logic) nhằm tỡm giải phỏp tối ưu cho những vấn
đề phức tạp mà các giải thuật cổ điển truyền thống đó khụng giải quyết được
thỏa đáng [3].
GA ứng dụng được nhiều trong các lĩnh vực khác nhau, từ khoa học tự
nhiên đến khoa học nhân văn, từ kỹ thuật sang thương vụ và kinh tế tài
chớnh. Những ứng dụng này cú thể chia làm ba nhúm chớnh:
Tỡm mụ hỡnh tối ưu cho vấn đề. Tỡm kiếm và tối ưu hóa giải pháp là
đề tài thích hợp nhất của GA
Hoạch định quy trỡnh sản xuất, lộ trỡnh vận chuyển, cỏch bố trớ cỏc
bộ phận trong mụi trường.
Chọn lựa cỏc nhúm hay thành phần trong một tổ chức

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
10
1.1.2. í tƣởng
í tưởng của GA là mô phỏng theo quá trỡnh tiến húa tự nhiờn của sinh vật
theo thuyết Darwin. Trong quỏ trỡnh tiến húa, mỗi cỏ thể đều phải tự tỡm
cỏch thớch nghi tốt nhất với mụi trường sống rất phức tạp và luôn luôn thay
đổi. Cá thể nào có khả năng thích nghi với môi trường cao hơn thỡ sẽ cú khả
năng tồn tại, phát triển và sinh sản cao hơn, ngược lại cá thể nào có khả năng

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

một tham số.
GA tỡm kiếm từ một quần thể cỏc điểm chứ không phải một điểm
hoặc một vài điểm như phương pháp tỡm kiếm leo đồi (Hill
Climbing).
GA đánh giá thông tin với hàm mục tiêu mà không đưa vào đạo
hàm hay thông tin bổ sung khác.
GA sử dụng các luật biến đổi theo xác suất mà không sử dụng luật
quyết định.
1.1.4. Cấu trúc của giải thuật di truyền cổ điển
GA cổ điển sử dụng ý tưởng và các thuật ngữ trong di truyền học như
được trỡnh bày sau đây.
Trong tự nhiên, mỗi cá thể có một tập hợp các tính chất và đặc điểm riêng
biệt được thể hiện ra ngoài môi trường gọi là kiểu hỡnh (phenotype). Kiểu
hỡnh này được quyết định bởi cấu trúc gene trong cơ thể, gọi là kiểu gene
(genotype). Các gene tạo thành các nhiễm sắc thể, mỗi tế bào có tập hợp các
nhiễm sắc thể như nhau. Các nhiễm sắc thể là các chuỗi DNA
(DeoxyriboNucleotic Acid) hoạt động như một mô hỡnh cho toàn bộ cơ thể.
Sự đa dạng về kiểu gene của các cá thể dẫn đến sự đa dạng về kiểu hỡnh của

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
12
một quần thể sinh học. Quỏ trỡnh phỏt triển của mỗi quần thể tuõn theo quy
luật chọn lọc của tự nhiờn mà tiến húa qua cỏc thế hệ nối tiếp nhau. Trong
đó, các hậu duệ được sinh ra từ thế hệ trước thông qua quá trỡnh sinh sản (di
truyền và biến dị) cạnh tranh tự nhiờn với nhau, cỏ thể nào cú kiểu hỡnh (và
do đó là kiểu gene) thích nghi cao hơn trong môi trường phát triển thỡ sẽ cú
khả năng cao hơn trong tồn tại và sinh sản con cháu. Do đó, kiểu gene này sẽ
tiến hóa và hoàn thiện. Quỏ trỡnh tiến húa này được lặp đi lặp lại, các cá thể
có kiểu gene phù hợp sẽ sống sót và phát triển, các cá thể yếu sẽ bị loại bỏ

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

0

Mỗi kiểu gene (một nhiễm sắc thể cụ thể) biểu thị một lời giải tiềm năng
của bài toán. Một quá trỡnh tiến húa được thực hiện trên một quần thể (một
tập hợp các cá thể) tương đương với sự tỡm kiếm trong một khụng gian cỏc
lời giải tiềm năng (Potential solution). Sự tỡm kiếm này đũi hỏ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.
GA cổ điển thực hiện việc tỡm kiếm theo nhiều hướng bằng cách duy trỡ
một tập lời giải tiềm năng, khuyến khích sự hỡnh thành và trao đổi thông tin
giữa các hướng. Tập lời giải trải qua quá trỡnh tiến húa và cuối cựng cho ta
một lời giải đủ tốt theo yêu cầu. Tại mỗi thế hệ, các lời giải tương đối tốt
được tái sinh, và các lời giải tương đối xấu bị loại bỏ dần. Để đánh giá mức
độ tốt xấu của từng lời giải, người ta xây dựng hàm thích nghi (Fitness
Function), hàm này đóng vai trũ như môi trường sống trong thuyết tiến hóa
của Darwin.

1.1.4.2. Thủ tục GA
GA cổ điển do J.H Holland đề xướng [16], [20] nhằm giải bài toỏn tối ưu
sau đây:
Max{(f(x) / x M R
n
}
Trong đó M là hỡnh hộp trong khụng gian số thực n-chiều R
n
, f(x) > 0 với
x M

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
14

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ố

Tỏi tạoP(t) từ Q(t); // bởi cỏc toỏn tử di truyền
Đánh giá P(t) và chọn cá thể tốt nhất
Until điều_kiện_kết_thúc;
Biểu diễn lời giải;
End;


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
15
Trong đó P(t) là quần thể tại thế hệ thứ t
Quỏ trỡnh tiến húa được diễn ra trong vũng lặp While, tại thế hệ thứ t,
giải thuật duy trỡ một tập lời giải
} ,,,{x)(
2
t
1
t
n
t
xxtP
. Mỗi lời giải
t
i
x
được đánh giá độ thích nghi. Một tập lời giải mới được xây dựng (vũng lặp
t+1) bằng cỏch chọn lọc cỏc cỏ thể cú độ thích nghi cao hơn, ta được tập lời
giải trung gian. Tiếp theo, một số cá thể trong tập lời giải đó được chọn này
được biến đổi bằng các toán tử di truyền là “lai ghép” và “biến dị” để tạo
thành một lời giải mới cho thế hệ thứ t+1.

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:

1210).(
i
m
p
ii
ab

Khi đó, nếu x = (x
1
, x
2
, …x
n
) và x
i
thuộc đoạn thứ k thỡ x
i
được mó húa
bởi chuỗi nhị phõn cú độ dài m
i
cú dạng
), ,(
01
bb
i
m
sao cho
1
0
2.

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

[a
2
, b
2
], …, m
k
bits cuối cựng của chuỗi ứng với
một giỏ trị x
k
[a
k
, b
k
]
Vớ dụ: Tỡm giỏ trị cực đại của hàm số 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
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

2

Do vậy, m = 17 là độ dài của chuỗi.
Giải mó: Chuyển đổi các chuỗi nhị phân về dạng số thập phân. Với mỗi
đoạn gene
), ,(
01
bb
i
m
ta xác định k
i
theo cơ số 10:
1
0
10
)2.(
i
m
j
j
ji
bk

và cú:
12
.
i
m
ii

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ơ

hội được chọn nhiều hơn, nghĩa là có nhiều con cháu trong các thế hệ tiếp
theo.
Phép chọn lọc các cá thể trong mỗi quần thể được thực hiện nhờ bánh xe
xổ số (Roulette Wheel tờn một trũ đánh bạc của Châu Âu).
Với mỗi quần thể P(t –1) gồm N nhiễm sắc thể: P(t – 1) = {v
1,
v
2, …,
v
n
} ta
xây dựng bánh xe xổ số như sau:

Bỏnh xe xổ số
Đánh giá độ phù hợp toàn phần, cũn gọi là tổng độ thích nghi của quần
thể.
N
i
i
vevalF
1
)(

Tớnh xỏc suất chọn lọc p
i
của mỗi cỏ thể v
i
:
F
veval

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

1
thỡ chọn cỏ thể v
1
, ngược lại, chọn cá thể v
i
sao cho q
i-1
< r
k

q
i
, 2 i N
Với cách thực hiện như thế, một số cá thể có thể được chọn nhiều lần và
Q(t) vẫn được xem là có N phần tử. Các cá thể tốt được chọn nhiều lần, các cá
thể trung bỡnh thỡ bỡnh ổn và cỏc cỏ thể xấu bị giảm dần.
Minh hoạ bỏnh xe xổ số với quần thể cú 5 cỏ thể:







Cá thể 1 có xác suất chọn lọc là 20%, nghĩa là mỗi lần quay bánh xe xổ
số, nó có khả năng được chọn là 0.2. Tương tự như vậy cho các các thể thứ 2,
3, 4, 5.
1.1.4.5. Quỏ trỡnh tỏi tạo
Quỏ trỡnh tỏi tạo dựa trờn cỏc toỏn tử di truyền là phộp lai và biến dị.
1.1.4.5.1. Cỏc toỏn tử di truyền

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

, y
2
, …, y
m
)
Chọn điểm lai k [1, m – 1] (k chọn trước hoặc ngẫu nhiên), ta sẽ sinh
được hai cá thể mới:
x’ = (x
1
, …, x
k
, y
k+1
, …, y
m
)
y’ = (y
1
, …, y
k
, x
k+1,
…, x
m
)
Vớ dụ:
Parent 1
0
1
0

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

Child 2
1
1
0
0
0
0
0
1
0
1

b. Phộp biến dị hay biến dị (Mutation operater): là sự biến đổi một hoặc
một vài gene của một nhiễm sắc thể. Toán tử biến dị làm tăng nhanh quá
trỡnh hội tụ, nhưng có thể làm tăng đột ngột và không gây tác dụng gỡ
hoặc làm hội tụ sớm đến một lời giải dưới tối ưu. Trong GA, mỗi cá thể
biểu diễn bởi một chuỗi nhị phân, nên biến dị tại một vị trí nào đó là sự
đảo bit tại vị trí đó.
X
i
, i k
'
i
x


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
20
1 – x

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

m

Với mỗi cỏ thể v
i
thuộc Q(t), i = 1, 2, N, phỏt sinh một số ngẫu
nhiờn r [0, 1]. Nếu r < p
c
thỡ v
i
được đưa vào tập lai. Tập này chia
thành cặp, nếu lẻ thỡ thờm hoặc bớt ngẫu nhiờn một cỏ thể khỏc và ỏp
dụng phộp lai để tạo hậu duệ thay thế cho chúng.
Sau khi lai ghép, đối với mỗi gene của cá thể, phát sinh một số ngẫu
nhiờn r [0, 1]. Nếu r < p
m
thỡ gene đó được biến dị.
Quỏ trỡnh trờn cho ta quần thể P(t) của thế hệ t và được đánh giá để chọn
cá thể có giá trị thích nghi tốt nhất.
1.1.4.6. Điều kiện kết thúc: là điều kiện để kết thúc quá trỡnh tiến húa của
quần thể. Tùy theo bài toán mà chọn cách kết thúc khác nhau. Người ta
thường dùng một trong các cách sau:
Kết thúc theo kết quả: Khi đạt đến mức giá trị yêu cầu thỡ dừng.
Kết thúc dựa vào số thế hệ: xác định trước số thế hệ cần tiến hóa, khi
trải qua đủ số thế hệ thỡ dừng, không cần biết kết quả như thế nào.
Tớnh theo thời gian: Quỏ trỡnh kết thức sau 1 khoảng thời gian quy
định trước, không cần biết số thế hệ đó trải qua cũng như kết quả.

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
21

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

5 với sai
số cỏc biến là 10
-2

+ Biểu diễn nhiễm sắc thể
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
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
3
= (00001000001100100) tương ứng với x
1
= 0.87; x
2
= 3.78;
eval(v
1
)= 10.94;
v
4
= (10001100010110100) tương ứng với x
1
= 1.19; x
2
= 4.41;
eval(v
1
)= 10.81;
v
5
= (00011101100101001) tương ứng với x
1
= -0.54; x
2
= 3.32;
eval(v
1
)= 7.67;

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;

v
9
= (01000000011010001) tương ứng với x
1
= 0.00; x
2
= 4.64;
eval(v
1
)= 5.67;
v
10
= (00010100001001010) tương ứng với x
1
= 0.88; x
2
= 3.19;
eval(v
1
)= 9.94;
Cỏ thể v
2
là tốt nhất với eval(v
2
) = 14.8 và có độ thích nghi toàn phần là
F = 96.77

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
23

+ 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

Xỏc suất
chọn lọc
p
i

Xỏc suất
tớnh lũy
q
i

Số
ngẫu nhiờn
r
i

Cá thể được chọn
Đánh số lại
1.
0.13
0.13
0.52
v
5
= (00011101100101001)
u
1

2.
0.15
0.28

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.42
v
8
= (10000110000111010)
u
5

6.
0.08
0.67
0.31
v
3
= (00001000001100100)
u
6

7.
0.10
0.76
0.42
v
4
= (10001100010110100)
u
7

8.
0.08
0.84

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

c
= 0.25, ta chọn được cặp lai là:
u
3
= (00100010000011010)