1

LỜI CẢM ƠN
Trải qua thời gian 02 năm học tập và nghiên cứu tại Trường Đại học
Vinh, kết quả nghiên cứu là luận văn thạc sĩ với đề tài “Nghiên cứu giải thuật
di truyền cho bài toán xếp thời khóa biểu ở Trường THPT”. Đây là kết quả
của quá trình cố gắng không ngừng của bản thân và được sự giúp đỡ, động
viên khích lệ của thầy cô, bạn bè, đồng nghiệp và người thân. Qua trang viết
này, tôi xin gửi lời cảm ơn tới những người đã giúp đỡ tôi trong thời gian học
tập và hoàn thành luận văn.
Xin chân thành cảm ơn Lãnh đạo Trường Đại học Vinh, Viện Kỹ thuật
và Công nghệ đã giúp đỡ, hỗ trợ để tôi hoàn thành tốt công việc học tập và
nghiên cứu khoa học. Tôi cũng xin cảm ơn Lãnh đạo Trường THPT Quỳ
Châu đã tạo điều kiện về thời gian, công việc để tôi có thể theo học và hoàn
thành khóa học của mình.
Đặc biệt em xin tỏ lòng kính trọng và biết ơn sâu sắc đối với thầy giáo
TS. Vũ Chí Cường đã trực tiếp tận tình hướng dẫn, đưa ra những gợi ý, góp ý,
chỉnh sửa cũng như cung cấp tài liệu thông tin khoa học cần thiết cho luận
văn này.
Cuối cùng tôi xin chân thành cảm ơn đồng nghiệp, gia đình và bạn bè
đã động viên, giúp đỡ tôi trong quá trình học tập và thực hiện luận văn.
Nghệ An, ngày 10 tháng 7 năm 2018
TÁC GIẢ

Phan Văn Thế


2

MỤC LỤC
DANH MỤC CÁC BẢNG VÀ CÁC HÌNH......................................................................................................... 4

1. Lý do chọn đề tài..............................................................................................5
4. Mục đích, nhiệm vụ nghiên cứu................................................................................................... 7
5. Phương pháp nghiên cứu............................................................................................................ 8
6. Đóng góp của luận văn................................................................................................................ 8
7. Cấu trúc của luận văn.................................................................................................................. 9

1.3. Một số phần mềm xếp thời khóa biểu THPT............................................14
Hiện nay có 2 phần mềm sắp xếp thời khóa biểu THPT được nhiều người
biết đến, đó là Phần mềm xếp thời khóa biểu SmartScheduler của công ty
Hoàng Gia và Phần mềm xếp thời khóa biểu của công ty SchoolNet............14
Phần mềm xếp thời khóa biểu SmartScheduler là sản phẩm dự thi Trí tuệ
Việt Nam 2001 của hai kỹ sư tin học Lê Hữu Sơn và Hoàng Cường. Theo các
tác giả, phần mềm có khả năng tự động sắp xếp thời khoá biểu rất nhanh,
phần mềm cũng cung cấp khả năng soạn thảo thời khoá biểu bằng tay nhằm
đáp ứng các yêu cầu tế nhị, sát hợp với đặc thù của mỗi trường học............14
Phần mềm xếp thời khóa biểu của công ty SchoolNet ra đời năm 1989, cho
đến nay đã có hơn 25 năm liên tục phát triển. Phần mềm có khá nhiều tính
năng phù hợp như hỗ trợ hoàn toàn các bảng mã và phông chữ tiếng Việt, hỗ
trợ các mô hình thời khóa biểu, hỗ trợ các ràng buộc cứng và ràng buộc
mềm, …..............................................................................................................14
Theo đánh giá chung thì hai phần mềm là có hiệu quả khi sử dụng để xếp
thời khóa biểu cho các trường THPT. Tuy nhiên, đây là những phần mềm có
phí và là phần mềm đóng mã nguồn nên không thể tìm hiểu hay cải tiến cho
phù hợp với đặc điểm riêng của nhà trường...................................................15
............................................................................................................................. 15
3.2.3.1. Menu chính của chương trình.......................................................................................... 54
...................................................................................................................................................... 54
3.2.3.1. Các Form nhập dữ liệu..................................................................................................... 54
3.3.2.1. Thời khóa biểu lớp........................................................................................................... 58


Thực hiện từ ngày 19 tháng 12 năm 2017........................................................58
3.3.2.2. Thời khóa biểu giáo viên.................................................................................................. 59

Thực hiện từ ngày 19 tháng 12 năm 2017........................................................59


3

Bảng 3.11. Thời khóa biểu Giáo viên................................................................60
KÉT LUẬN........................................................................................................61
1. Kết quả đạt được...........................................................................................61
2. Hạn chế, hướng phát triển............................................................................61


4

DANH MỤC CÁC BẢNG VÀ CÁC HÌNH
Hình 1.1. Quy trình xếp thời khóa biểu
Hình 2.1: Thuật toán di truyền
Hình 2.2. Minh họa cho kỹ thuật chọn lọc theo kiểu quay bánh xe
Hình 3.1. Cấu trúc Nhiễm sắc thể
Hình 3.2. Bảng CSDL Môn học
Hình 3.3. Bảng CSDL Lớp học
Hình 3.4. Bảng CSDL Giáo viên
Hình 3.5. Bảng CSDL Phân công giảng dạy
Hình 3.6. Form chính chương trình xếp TKB
Hình 3.7. Form nhập liệu Giáo viên
Hình 3.8. Form nhập liệu Lớp học
Hình 3.9. Form nhập liệu Phân công giảng dạy

Hình 3.10. Form nhập liệu Các ràng buộc mềm
Hình 3.11. Form các tham số di truyền
Hình 3.12. Form thao tác xếp TKB
Hình 3.13. Biểu đồ so sánh giá trị thích nghi
Bảng 1.1. Nội dung công việc xếp thời khóa biểu
Bảng 3.1. Danh sách lớp học
Bảng 3.2. Danh sách môn học
Bảng 3.3. Danh sách Giáo viên
Bảng 3.4. Bảng phân công giảng dạy
Bảng 3.5. Ví dụ về danh sách các tiết học
Bảng 3.6. Ví dụ về phân phối các tiết học
Bảng 3.7. Ví dụ về các tiết cố định
Bảng 3.8. Ví dụ về thời khóa biểu 1 lớp
Bảng 3.9. Quy định tiết được học trong thời khóa biếu
Bảng 3.10. Thời khóa biểu lớp học
Bảng 3.11. Thời khóa biểu Giáo viên


5

MỞ ĐẦU
1. Lý do chọn đề tài
Thời khóa biểu của trường học là một 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, chủ động khi lên lớp và giúp học sinh thoải mái khi học tập.
Việc lập hay xếp thời khóa biểu là hoạt động quan trọng của mỗi một
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ễ vi phạm các ràng buộc về nghiệp vụ. Do vậy, khi áp dụng phải
trải qua một vài lần điều chỉnh mới có thể đạt được yêu cầu cơ bản.

Đã từ lâu, việc lập thời khóa biểu cho các trường học đã được tổng quát
hóa thành bài toán, các nhà nghiên cứu đã và đang tìm các phương pháp giải
nó bằng các công cụ, thuật toán tin học. Các bài toán xếp 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
trường học, thậm chí từng môn học. Bởi vậy lời giải của bài toán xếp thời
khóa biểu thường là những giải pháp chấp nhận được, hay nói cách khác bài
toán xếp thời khóa biểu là một bài toán tối ưu.
Trong khoảng 50 năm qua, thuật toán di truyền và các cải tiến - phát
triển của nó gọi chung là thuật toán tiến hóa đã 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. Thuật toán di truyền mô
phỏng sự tiến hóa tự nhiên của sinh học với quan niệm sự tiến hóa tự nhiên
của sinh học là một quá trình tối ưu. Thuật toán trên tỏ ra rất hiệu quả trong


6

việc áp dụng 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.
Ở 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. Trường THPT Quỳ Châu, nơi tôi đang giảng dạy, 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 nhà trường.
Xuất phát từ những vấn đề trên, đề tài “Nghiên cứu thuật toán di
truyền cho bài toán xếp thời khóa biểu ở Trường trung học phổ thông” được
tôi lựa chọn làm luận văn tốt nghiệp. Luận văn tập trung nghiên cứu về thuật
toán di truyền và đồ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 thực hành, xem như là một thử nghiệm đầu tiên.
Do khả năng và thời gian hạn chế, tôi 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ôi công tác. Hy
vọng trong thời gian tới, tôi 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 nói chung.
2. Lịch sử vấn đề
Thuật toán di truyền (tên tiếng Anh là Genetic Algorithms, viết tắt là
GA) đã được giáo sư J.H. Holland công bố lần đầu tiên vào năm 1962. Thuật
toán di truyền được hình thành dựa trên quan niệm rằng “quá trình tiến hóa tự
nhiên là một quá trình hoàn hảo và hợp lý nhất, tự quá trình này đã mang tính
tối ưu”. Từ khi ra đời cho đến nay, thuật toán di truyền đã được nhiều nhà
toán học, nhà tin học nghiên cứu các vấn đề về lý thuyết và ứng dụng.
Thuật toán di truyền là một nhánh lớn trong lĩnh vực nghiên cứu về
thuật toán tiến hóa (tên tiếng Anh là Evolutionary Algorithms, viết tắt là EAs).
Thuật toán di truyền nói riêng và EAs nói chung có thế mạnh thật sự trong
việc giải quyết các bài toán khó, bài toán tối ưu số và tối ưu tổ hợp. Một trong
các ứng dụng kinh điển của Thuật toán di truyền là bài toán sắp xếp thời khóa


7

biểu.
Ở nước ta, thuật toán di truyền và ứng dụng nhận được sự quan tâm
của nhiều nhà khoa học. Đối với bài toán ứng dụng thuật toán di truyền để sắp
xếp thời khóa biểu, đã có một số tác giả nghiên cứu và triển khai trong các
luận văn tốt nghiệp cao học thạc sĩ ngành công nghệ thông tin. Tiêu biểu trong
số này có thể kể đến:
- 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 của ThS. Trần Quốc Hưng tại Trường Đại học Công nghệ - Đại học
Quốc gia Hà Nội năm 2004 (xem [8]).
- Ứng dụng giải thuật di truyền để xếp thời khóa biểu hệ tín chỉ cho

trường đại học của ThS. Phạm Anh Tuấn tại Trường Đại học Đà Nẵng năm
2012 (xem [7]).

- Giải thuật di truyền và bài toán lập thời khóa biểu của ThS. Đồng

Văn Tuấn tại Trường Đại học Công nghệ thông tin và Truyền thông - Đại học
Thái Nguyên năm 2014 (xem [4]).
Trong các công trình này, bài toán sắp xếp thời khóa biểu được nghiên
cứu và giải quyết. Tuy nhiên chỉ dừng lại ở các bài toán rất cụ thể của từng
đơn vị, từng trường mà chưa thể mở rộng một cách tổng quát.
3. Đối tượng và phạm vi nghiên cứu
Tìm hiểu bài toán lập lịch.
Tìm hiểu thuật toán di truyền, ứng dụng thuật toán di truyền vào bài toán
lập thời khóa biểu.
Xây dựng ứng dụng lập thời khóa biểu cho trường THPT nói chung và
Trường THPT Quỳ Châu nói riêng.
4. Mục đích, nhiệm vụ nghiên cứu
Xây dựng được phần mềm sắp xếp thời khóa biểu của Trường THPT
Quỳ Châu thích nghi, linh hoạt, đáp ứng các yêu cầu ràng buộc của bài toán


8

và thực tế của nhà trường. Phần mềm hướng tới có thể đáp ứng các yêu cầu
ràng buộc của trường THPT nói chung.
5. Phương pháp nghiên cứu
-

Nghiên cứu, tìm hiểu các tài liệu liên quan;

-

Phân tích và thiết kế phần mềm;


-

Viết chương trình;

-

Thử nghiệm và phân tích kết quả.

6. Đóng góp của luận văn
Luận văn bổ sung thêm một tài liệu tham khảo lý thuyết và thực
nghiệm về giải thuật di truyền. Các kết quả nghiên cứu trong luận văn một lần
nữa khẳng định tính ứng dụng hiệu quả của thuật toán di truyền đối với các
bài toán tối ưu khó nói chung và bài toán thời khóa biểu nói riêng.
Phần mềm sắp xếp thời khóa biểu được nghiên cứu, xây dựng trong
luận văn thỏa mãn các điều kiện ràng buộc chung của bài toán xếp thời khóa
biểu, phần mềm còn cho phép các trường THPT nói chung và Trường THPT
Quỳ Châu nói riêng có thể linh hoạt và chủ động các phương án khác nhau
trong việc sắp xếp thời khóa biểu năm học:
-

Cho phép khai báo tiết cố định của môn học

-

Cho phép khai báo thời gian bận của các giáo viên.

-

Cho phép giảm thiểu số tiết trống.


-

Cho phép đặt các ràng buộc mềm như

0 + Môn Toán, môn Văn có 1 cặp tiết xếp liền
1 + Môn Thể dục, Quốc phòng không dạy tiết 5 và tiết 6
2 + Môn được phân 2 tiết trên 1 buổi thì không rời nhau
3 + Không phân 3 tiết 1 môn trên 1 buổi
4 + Hạn chế giáo viên không dạy 5 tiết trong 1 buổi.
5


9

7. Cấu trúc của luận văn
Báo cáo luận văn được cấu trúc trong 03 chương.
Chương 1. Bài toán sắp xếp thời khóa biểu. Mô tả chung về bài toán
thời khóa biểu và một số phần mềm xếp thời khóa biểu dành cho trường
THPT hiện nay.
Chương 2. Giải thuật di truyền. Mô tả các lý thuyết về giải thuật di
truyền, trình bày một số lĩnh vực ứng dụng của giải thuật di truyền.
Chương 3. Ứng dụng giải thuật di truyền cho bài toán thời khóa
biểu Trường THPT. Là nội dung chính của luận văn và được chia làm 3
phần. Phần thứ nhất trình bày các thành phần cơ bản của thuật toán di truyền
được mã hóa và mô tả một cách cụ thể bài toán và các yêu cầu của bài toán
xếp thời khóa biểu của trường THPT. Phần thứ 2 là phân tích và thiết kế
chương trình. Phần thứ ba là các kết quả thực nghiệm và đánh giá.



10

Chương I.
BÀI TOÁN SẮP XẾP THỜI KHÓA BIỂU
Bài toán xếp Thời khóa biểu thuộc lớp Bài toán lập lịch, là một trong
những bài toán thú vị nhất trong lớp các bài toán tối ưu vì tính chất đa dạng về
mô hình thời khóa biểu, có nhiều ràng buộc phức tạp và tính chất thực tiễn
của nó.
Bài toán thời khóa biểu thuộc loại bài toán NP-khó, là trường hợp riêng
của bài toán lập lịch, trong đó đưa ra một chuỗi các sự kiện (các môn học, bài
giảng hoặc môn thi) và bao gồm các giáo viên và học sinh trong một khoảng
thời gian định trước, và một tập các ràng buộc phải thỏa mãn của từng loại
thời khóa biểu khác nhau. Tập ràng buộc bao gồm khả năng tham dự của học
sinh, khả năng làm việc của giáo viên, số lượng và sức chứa của phòng học và
các yêu cầu của các sự kiện.
1.1. Tổng quan về bài toán lập lịch
Bài toán lập lịch là chọn một chuỗi các thao tác, đồng thời chỉ định về
thời gian bắt đầu/ kết thúc và các tài nguyên cần thiết cho mỗi thao tác. Điều
cần quan tâm chính yếu là chi phí thời gian máy rỗi, năng lực lao động và các
đơn đặt hàng cần hoàn thành đúng hạn. Ý tưởng chính trong phương pháp là
mã hóa biểu diễn của lịch phân công là các toán tử di truyền phải thực hiện
theo cách có ý nghĩa, và một bộ giải mã phải luôn tạo ra một lời giải hợp lệ
cho bài toán. Thủ tục giải mã mô phỏng các thao tác của công việc theo cách
mà khi một máy tính sẵn sàng chọn lựa, thì thao tác cho phép đầu tiên từ danh
sách ưu tiên được lấy ra.


11

1.1.1. Bài toán

Lập lịch có thể được định nghĩa là một bài toán tìm kiếm chuỗi tối ưu
để thực hiện một tập các hoạt động chịu tác động của một tập các ràng buộc
cần phải được thỏa mãn. Người lập lịch thường cố gắng thử đến mức tối đa sự
sử dụng các cá thể, máy móc và tối thiểu thời gian đòi hỏi để hoàn thành toàn
bộ quá trình nhằm sắp xếp lịch. Vì thế bài toán lập lịch là một vấn đề rất khó
để giải quyết. Hiện nay có nhiều khả năng để phát triển các kỹ thuật hiện tại
để giải quyết bài toán này. Những kỹ thuật đó bao gồm: các tiếp cận Trí tuệ
nhân tạo như hệ thống tri thức cơ sở (knowledge-based systems), bài toán
thoả mãn ràng buộc, hệ chuyên gia, mạng Nơron và các tiếp cận của các
nghiên cứu hoạt động: lập trình tính toán, lập trình động, tìm kiếm nhánh và
đường biên, kỹ thuật mô phỏng, tìm kiếm Tabu và phương pháp nút cổ chai,
…
1.1.2. Các thuộc tính
Tài nguyên: đó là các nguồn dữ liệu đầu vào của bài toán. Các tài
nguyên này có thể phục hồi hoặc không.
Tác vụ: được đánh giá qua các tiêu chuẩn thực hiện như thời gian thực
hiện, chi phí, mức tiêu thụ nguồn tài nguyên.
Ràng buộc: đây là những điều kiện cần thỏa mãn để bài toán có thể đưa
ra lời giải tốt nhất.
Mục tiêu: đánh giá độ tối ưu của lịch trình lời giải của bài toán. Khi các
mục tiêu được thỏa mãn thì các ràng buộc cũng phải được thỏa mãn.
1.1.3. Một số bài toán lập lịch cơ bản
- Bài toán lập lịch Job Shop;
- Bài toán gia công;
- Bài toán lịch trực;
- Lập lịch ưu tiên đúng hạn;


12


- Bài toán xếp thời khóa biểu trường học,…
1.2. Bài toán xếp thời khóa biểu
1.2.1. Bài toán
Bài toán sắp xếp thời khóa biểu ở trường học nói chung và sắp xếp thời
khóa biểu ở trường trung học phổ thông nói riêng là một bài toán khó. Sự
phức tạp của bài toán không chỉ ở vấn đề tìm ra môt thời khóa biểu cho
trường học thỏa mãn các ràng buộc về thời gian, ràng buộc chuyên môn, quy
định của Bộ Giáo dục và Đào tạo mà còn một vấn đề khó khăn hơn là ta phải
tìm được một thời khóa biểu tốt thích hợp cho tất cả các giáo viên, phải thỏa
mãn các điều kiện, yêu cầu về thời gian, hạn chế số tiết trống trong một ngày
và số ngày lên lớp của giáo viên trong thời khóa biểu.
Quy trình để xếp thời khóa biểu có thể biểu diễn như sau:
Chia lớp và ổn định
lớp học

Danh sách giáo viên

Môn học
của lớp
và môn
dạy của
giáo viên

XẾP
TKB
Danh sách lớp học

Danh sách giáo viên

Yêu cầu

ràng
buộc của
Giáo
viên và
của Lớp

TKB của
lớp và
TKB của
giáo viên

Các ràng
buộc mềm

Hình 1.1. Quy trình xếp thời khóa biểu

Việc sắp xếp thời khóa biểu của các trường phổ thông luôn luôn phải
thực hiên trước khi học kỳ mới bắt đầu. Theo đó, nội dung các môn học và


13

giáo viên phụ trách môn học của từng lớp phải được xác định thông qua cuộc
họp chuyên môn, kết quả của cuộc họp này được gửi cho Ban giám hiệu nhà
trường và việc lên lịch cho toàn bộ trường do Phó hiệu trưởng phụ trách
chuyên môn hoặc Thư kí Hội đồng trường đảm nhiệm. Hiện nay, việc sắp thời
khóa biểu này ở hầu hết các trường phổ thông đều được thực hiện một cách
thủ công và hầu như phải dựa vào kinh nghiệm thực tế mới có thể làm được.
Thông thường việc sắp xếp thời khóa biểu này phải mất trung bình một tuần.
Vậy bài toán đặt ra là cần phải sắp xếp thời khoá biểu cho một trường

THPT hay sắp xếp lịch học của các lớp học sao cho vừa phù hợp lại vừa tiện
dụng nhất.
1.2.2. Dữ liệu đầu vào
- Danh sách môn học;
- Danh sách lớp học;
- Danh sách giáo viên;
- Bảng phân công giáo viên giáo dạy tại các lớp;
- Bảng yêu cầu ràng buộc của giáo viên với lịch dạy;
- Bảng yêu cầu ràng buộc của lớp với lịch học.
1.2.3. Các ràng buộc
Ràng buộc cứng:
- Một giáo viên chỉ dạy được một lớp trong cùng một tiết;
- Mỗi lớp chỉ học 1 môn tại 1 thời điểm;
- Các lớp chỉ có một môn học trong cùng một tiết;
- Một giáo viên không thể dạy quá 30 tiết mỗi tuần.
Ràng buộc mềm:
- Một giáo viên không dạy quá 5 tiết/buổi;
- Môn Toán, Văn có 1 cặp 2 tiết liền nhau;
- Một môn học không quá 3 tiết trong 1 buổi;


14

- Hai tiết của 1 môn trong 1 buổi thì liên nhau;
- Một lớp có thể có cùng một môn nhiều lần trong một ngày;
…
STT
1
2


Tên công việc

Thực hiện
Phó HT phụ trách

Lập danh sách lớp
Lập danh sách giáo viên dự Phó
CM HT phụ trách
CM

3

kiến
Lập danh sách môn học

4

Phân công chuyên môn

Phó HT phụ trách

5

CM HT phụ trách
Các yêu cầu ràng buộc mềm Phó
Các yêu cầu cố định tiết dạy Giáo
CM viên, Phó HT

6


Dữ liệu
Danh sách lớp
Danh sách giáo viên
Danh sách môn học
Bảng phân công
Giảng dạy
Bảng dữ liệu bận/rỗi

(lịch bận/rỗi)
phụ trách CM
Bảng 1.1. Nội dung công việc xếp thời khóa biểu
1.3. Một số phần mềm xếp thời khóa biểu THPT
Hiện nay có 2 phần mềm sắp xếp thời khóa biểu THPT được nhiều
người biết đến, đó là Phần mềm xếp thời khóa biểu SmartScheduler của
công ty Hoàng Gia và Phần mềm xếp thời khóa biểu của công ty
SchoolNet.
Phần mềm xếp thời khóa biểu SmartScheduler là sản phẩm dự thi Trí tuệ
Việt Nam 2001 của hai kỹ sư tin học Lê Hữu Sơn và Hoàng Cường.
Theo các tác giả, phần mềm có khả năng tự động sắp xếp thời khoá biểu
rất nhanh, phần mềm cũng cung cấp khả năng soạn thảo thời khoá biểu
bằng tay nhằm đáp ứng các yêu cầu tế nhị, sát hợp với đặc thù của mỗi
trường học.
Phần mềm xếp thời khóa biểu của công ty SchoolNet ra đời năm 1989,
cho đến nay đã có hơn 25 năm liên tục phát triển. Phần mềm có khá
nhiều tính năng phù hợp như hỗ trợ hoàn toàn các bảng mã và phông chữ


15

tiếng Việt, hỗ trợ các mô hình thời khóa biểu, hỗ trợ các ràng buộc cứng

và ràng buộc mềm, …
Theo đánh giá chung thì hai phần mềm là có hiệu quả khi sử dụng để xếp
thời khóa biểu cho các trường THPT. Tuy nhiên, đây là những phần mềm
có phí và là phần mềm đóng mã nguồn nên không thể tìm hiểu hay cải
tiến cho phù hợp với đặc điểm riêng của nhà trường.


16

Chương II
THUẬT TOÁN DI TRUYỀN
Thuật toán di truyền trong lĩnh vực tin học là một trong những thuật
toán thú vị, bởi vì nó mô phỏng qui luật đấu tranh sinh tồn của tự nhiên và
cũng là một thuật toán vô cùng hiệu quả đối với các loại bài toán tối ưu.
2.1. Tổng quan về thuật toán di truyền
Thuật toán di truyền là một kỹ thuật của khoa học máy tính nhằm tìm
kiếm giải pháp thích hợp cho các bài toán tối ưu tổ hợp (combinatorial
optimization), là một phân ngành của thuật toán tiến hóa, vận dụng các
nguyên lý của tiến hóa như: di truyền, đột biến, chọn lọc tự nhiên, và trao đổi
chéo (lai ghép). Nó sử dụng ngôn ngữ máy tính để mô phỏng quá trình tiến
hoá của một tập hợp những đại diện trừu tượng (gọi là những nhiễm sắc thể),
của các giải pháp có thể (gọi là những cá thể) cho bài toán tối ưu hóa vấn đề.
Tập hợp này sẽ tiến triển theo hướng chọn lọc những giải pháp tốt hơn.
Thuật toán di truyền cũng như các thuật toán tiến hoá, đều được hình
thành dựa trên một quan niệm được coi là một tiên đề phù hợp với thực tế
khách quan. Đó là quan niệm “Quá trình tiến hoá 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 hoá thể
hiện tính tối ưu ở chỗ thế hệ sau bao giờ cũng tốt hơn thế hệ trước.
2.1.1. Giới thiệu
Trong thuật toán di truyền, người ta dùng thuật ngữ vay mượn của di

truyền học như: cá thể, nhiễm sắc thể, gen, quần thể, độ thích nghi, chọn lọc,
lai ghép, đột biến, v.v... Trong đó cá thể biểu diễn một lời giải, giải pháp của
bài toán. Không giống như trong tự nhiên, một cá thể có thể có nhiều nhiễm
sắc thể, ở đây chúng ta quy ước mỗi cá thể chỉ có một nhiễm sắc thể. Các
nhiễm sắc thể là một cá thể, là một chuỗi tuyến tính. Trong nhiễm sắc thể có


17

thể có các đơn vị nhỏ hơn đó là gen. Mỗi gen đại diện một thuộc tính, tính
chất và có vị trí nhất định trong nhiễm sắc thể. Quần thể là một tập hợp hữu
hạn xác định các cá thể. Trong thuật toán di truyền, quần thể là một tập các cá
thể biểu diễn một tập các lời giải. Các phép toán di truyền như chọn lọc, lai
ghép, đột biến được thực hiện trên quần thể để tạo ra một quần thể mới.
Một bài toán được giải bằng thuật toán di truyền thường phải qua các
bước sau:
>

Biểu diễn lời giải của bài toán (hay nhiễm sắc thể) bằng chuỗi
nhị phân, chuỗi ký tự, số thập phân, ...

>

Khởi tạo quần thể ban đầu gồm N cá thể một cách ngẫu nhiên.

>

Xây dựng hàm thích nghi làm tiêu chuẩn đánh giá các cá thể
theo độ thích nghi của chúng.


>

Xác định xác suất lai ghép, xác suất đột biến, ...

>

Xây dựng các phương pháp lai ghép, chọn lọc, đột biến.

2.1.2. Sự khác biệt của thuật toán di truyền và thuật toán khác
Khi dùng phương pháp truyền thống có một số cách giải sau:
- Phương pháp liệt kê
- Phương pháp giải tích
- Phương pháp tìm kiếm ngẫu nhiên
Đặc trưng của thuật toán di truyền so với các phương pháp truyền thống:
- Thuật toán di truyền làm việc với sự mã hoá của tập thông số chứ

không làm việc với các giá trị của các thông số.
- Thuật toán di truyền tìm kiếm từ một quần thể các điểm chứ không phải

từ một điểm.
- Thuật toán di truyền chỉ sử dụng thông tin về các tiêu chuẩn tối ưu của

hàm mục tiêu chứ không dùng các thông tin hỗ trợ nào khác.
- Thuật toán di truyền sử dụng các luật chuyển đổi mang tính xác suất


18

chứ không phải là các luật chuyển đổi mang tính xác định.
- Thuật toán di truyền thường khó cài đặt, áp dụng. Tuy nhiên không

phải lúc nào cũng cho lời giải chính xác. Một số thuật toán di truyền có thể
cung cấp lời giải tiềm năng cho một bài toán xác định để người sử dụng lựa
chọn.
* Ưu điểm
- Ưu điểm chính là khả năng song song của thuật toán.
- Thuật toán di truyền duyệt qua không gian tìm kiếm sử dụng nhiều cá
thể (and with genotype rather than phenotype) và ít mắc phải cực trị địa
phương như các thuật toán khác.
- Dễ thể hiện.
- Khi đã có thuật toán gen cơ bản, chỉ cần viết một NST mới (just one
object) để xử lý bài toán khác.
- Với cùng cách mã hóa bạn có thể thay đổi hàm thích nghi.
Mặc dù vậy, trong một số trường hợp chọn và thể hiện mã hóa sẽ gặp
khó khăn.
* Nhược điểm
- Nhược điểm chính của thuật toán di truyền là thời gian tính toán.
- Thuật toán di truyền có thể chậm hơn các thuật toán khác.
- Có thể kết thúc tính toán bất cứ lúc nào.
2.1.3. Các tính chất của thuật toán di truyền
Thuật toán di truyền là kỹ thuật chung, giúp giải quyết vấn đề bằng cách
mô phỏng sự tiến hóa của con người hay của sinh vật nói chung trong điều
kiện qui định sẵn của môi trường. Mục tiêu của thuật toán di truyền không
nhằm đưa ra lời giải chính xác tối ưu mà là đưa ra lời giải tương đối tối ưu.
Một cá thể trong thuật toán di truyền sẽ biểu diễn một giải pháp của bài
toán. Tuy nhiên, không giống với trong tự nhiên là một cá thể có nhiều nhiễm


19

sắc thể mà để giới hạn trong thuật toán di truyền, ta quan niệm một cá thể có

một nhiễm sắc thể. Do đó, khái niệm cá thể và nhiễm sắc thể trong thuật toán
di truyền coi như là tương đương.
Một nhiễm sắc thể được tạo thành từ nhiều gen, mỗi gen có thể có các
giá trị khác nhau để quy định một tình trạng nào đó. Trong thuật toán di
truyền, một gen được coi như một phần tử trong chuỗi nhiễm sắc thể.
Một tập hợp các cá thể có cùng một số đặc điểm nào đấy được gọi là
quần thể. Trong thuật toán di truyền, ta quan niệm quần thể là một tập các lời
giải của một bài toán.
2.1.4. Sơ đồ và cấu trúc thuật toán di truyền


20

Hình 2.1: Thuật toán di truyền
Cấu trúc thuật toán:
Begin
t =0;
Khởi tạo P(t);
Tính độ thích nghi cho các cá thể trong P(t);
While (điều kiện dừng chưa thỏa mãn) do
Begin
t = t + 1;
Chọn lọc P(t)
Lai P(t)


21

Đột biến P(t)
Tính độ thích nghi cho các cá thể trong P(t)

End
End.
[Bắt đầu ] Nhận các tham số cho thuật toán.
[Khởi tạo quần thể] Sinh ngẫu nhiên một quần thể gồm n cá thể (là n
lời giải cho bài toán)
[Quần thể mới] Tạo quần thể mới bằng cách lặp lại các bước sau cho
đến khi quần thể mới hoàn thành
a.[Thích nghi] Ước lượng độ thích nghi eval(x) của mỗi cá thể.
b.[Kiểm tra ] Kiểm tra điều kiện kết thúc giải thuật.
c.[Chọn lọc] Chọn hai cá thể bố mẹ từ quần thể cũ theo độ thích
nghi của chúng (cá thể có độ thích nghi càng cao thì càng có nhiều khả năng
được chọn)
d.[Lai ghép] Với một xác suất lai ghép được chọn, lai ghép hai
cá thể bố mẹ để tạo ra một cá thể mới.
e.[Đột biến] Với một xác suất đột biến được chọn, biến đổi cá
thể mới
[Chọn kết quả] Nếu điều kiện dừng được thỏa mãn thì thuật toán kết
thúc và trả về lời giải tốt nhất trong quần thể hiện tại
2.2. Các thành phần trong thuật toán di truyền
2.2.1. Biểu diễn nhiễm sắc thể
Để áp dụng giải một bài toán bằng thuật toán di truyền, thao tác quan
trọng nhất là phải biết chọn cấu trúc dữ liệu phù hợp. Để giải bài toán trong
thuật toán di truyền, ta thường chọn sử dụng một trong 3 loại cấu trúc dữ liệu
sau: Biểu diễn nhị phân, biểu diễn số thực và cấu trúc cây. Trong đó biểu diễn
nhị phân và biểu diễn số thực thường được sử dụng nhiều hơn.


22

2.2.1.1. Biểu diễn nhị phân

Quy tắc biểu diễn gen qua chuỗi nhị phân: Chọn chuỗi nhị phân ngắn
nhất nhưng đủ thể hiện được tất cả kiểu gen. Để biểu diễn chuỗi nhị phân, ta
thường dùng các cách sau: Mảng byte, mảng bit biểu diễn bằng mảng byte,
mảng bit biểu diễn bằng mảng interger. Mảng byte và mảng bit bây giờ ít sử
dụng. Đối với máy tính ngày nay, người ta thường dùng mảng integer để tối
ưu truy xuất. Vì vậy ở đây tôi chỉ giới thiệu về mảng integer.
VD: Nhiễm sắc thể x ta biểu diễn bằng 1 chuỗi 15 bit
X=(010100110010101)2
2.2.1.2. Biểu diễn số thực
Sau khi thuật toán di truyền cổ điển được Holland công bố, nó chứng tỏ
là phương pháp tốt để giải các bài toán tối ưu khó và nó được cải tiến phong
phú để tăng hiệu quả ứng dụng.
Đối với các bài toán khó có miền chấp nhận lớn và đòi hỏi sai số nhỏ
thì độ dài của mỗi nhiễm sắc thể theo phương pháp thuật toán di truyền cổ
điển rất lớn, nên việc áp dụng thuật toán di truyền rất khó khăn. Do vậy,
người ta cải tiến cách biểu diễn nhiễm sắc thể bằng vector số thực để giải bài
toán. Trong cách biểu diễn này, người ta dùng các vector số thực trong miền
chấp nhận được (thuộc tập M) làm nhiễm sắc thể và thiết kế các nhóm
phương pháp di truyền cho thích hợp với cách biểu diễn này mà vẫn giữ
nguyên thủ tục thuật toán di truyền đã đặc tả ở trên.
2.2.2. Khởi tạo quần thể ban đầu
Tạo quần thể đầu tiên trong thuật toán, là nơi xuất phát quá trình tiến
hóa, bao gồm tất cả các giá trị thô ban đầu. Tùy theo vấn đề của bài toán mà
có cách khởi tạo khác nhau.
Quần thể là một tập hợp các cá thể có cùng một số đặc điểm nào đấy.
Trong giải thuật di truyền ta quan niệm quần thể là một tập các lời giải của


23


một bài toán.
Quần thể ban đầu ảnh hưởng khá nhiều đến hiệu quả giải thuật, tuy
nhiên trong nhiều bài toán thì quần thể ban đầu thường được lựa chọn ngẫu
nhiên. Thường phụ thuộc vào kích thước chuỗi mã hóa. VD: Nếu có NST 32
bits, thì kích thước quần thể nên cao hơn 16
Kích thước quần thể cho biết có bao nhiêu cá thể trong một quần thể
trong mỗi thế hệ. Các nghiên cứu và các thử nghiệm đã cho thấy kích thước
quần thể không nên quá bé cũng như không quá lớn. Nếu có quá ít cá thể thì
sẽ làm giảm không gian tìm kiếm của giải thuật và dễ rơi vào các cục bộ địa
phương, như vậy sẽ dễ xảy ra trường hợp bỏ qua các lời giải tốt. Tuy nhiên
nếu có quá nhiều cá thể cũng sẽ làm cho giải thuật chạy chậm đi, ảnh hưởng
đến hiệu quả tính toán của giải thuật. Các nghiên cứu cũng đã chỉ ra không có
lợi khi tăng kích thước quần thể lên quá một giới hạn cho phép.
2.2.3. Đánh giá cá thể
Chắc chắn rằng việc chọn cá thể sẽ thông qua kết quả, hay mục đích
của vấn đề. Các cá thể tốt được chọn lọc để đưa vào thế hệ sau. Sự lựa chọn
này được thực hiện dựa vào độ thích nghi với môi trường của mỗi cá thể.
Có nhiều phương pháp để chọn các nhiễm sắc thể tốt nhất, ví dụ: chọn
lọc Quay bánh xe, chọn lọc Xếp hàng, chọn lọc Cạnh tranh, chọn lọc theo cơ
chế lấy mẫu ngẫu nhiên, chọn lọc tranh đấu, vv…
2.2.4. Các phép toán di truyền
Ở phần này, chúng ta sẽ tìm hiểu về các phép toán di truyền phục vụ
cho bài toán sắp xếp thời khóa biểu.
2.2.4.1. Phương pháp chọn lọc
Trong tự nhiên, quá trình chọn lọc và đấu tranh sinh tồn đã làm thay đổi
các cá thể trong quần thể. Những cá thể tốt, thích nghi được với điều kiện
sống thì có khả năng đấu tranh lớn hơn, do đó có thể tồn tại và sinh sản. Các


24


cá thể không thích nghi được với điều kiện sống thì dần mất đi. Dựa vào
nguyên lý của quá trình chọn lọc và đấu tranh sinh tồn trong tự nhiên, chọn
lựa các cá thể trong thuật toán di truyền chính là cách chọn các cá thể có độ
thích nghi tốt để đưa vào thế hệ tiếp theo hoặc để cho lai ghép, với mục đích
là sinh ra các cá thể mới tốt hơn. Có nhiều cách để lựa chọn nhưng cuối cùng
đều nhằm đáp ứng mục tiêu là các cá thể tốt sẽ có khả năng được chọn cao
hơn.
Việc chọn lọc các cá thể từ một quần thể dựa vào độ thích nghi của mỗi
cá thể. Các cá thể có độ thích nghi cao có nhiều khả năng được chọn lựa
(những cá thể khỏe mạnh có nhiều khả năng được phối giống). Hàm thích
nghi chỉ cần là một hàm thực dương, nó có thể không tuyến tính, không liên
tục, không khả vi.
Cơ chế lựa chọn được áp dụng khi quần thể P(t+1) được tạo ra từ việc
chọn các cá thể từ quần thể P(t) để thực hiện việc lai ghép và đột biến. Có
nhiều cách để lựa chọn các cá thể từ một quần thể. Sau đây sẽ giới thiệu một
số cơ chế hay áp dụng.
Để tiện mô tả các cơ chế lựa chọn ta đưa ra một số kí hiệu sau:
- Cách biểu diễn các nhiễm sắc thể thứ i là vi.
- Hàm tính độ thích nghi của nhiễm sắc thể vi là f(vi).
- Kích thước quần thể là pop_size.
- Số nhiễm sắc thể cần chọn là N.
* Chọn lọc tỷ lệ (bánh xe Roulet)
Trước khi lựa chọn thì tính các giá trị sau :
- Tính tổng độ thích nghi của cả quần thể: F =

pop _ size

∑ f (v )
i =1


i

- Tính xác suất chọn pi cho mỗi nhiễm sắc thể vi : pi = f(vi)/F


25
i

- Tính vị trí xác suất qi của mỗi nhiễm sắc thể : qi = ∑ Pj
j =1

Cơ chế lựa chọn theo bánh xe Roulet được thực hiện bằng cách quay
bánh xe Roulet N lần. Mỗi lần chọn một nhiễm sắc thể từ quần thể hiện hành
vào quần thể mới bằng cách sau :
- Phát sinh ngẫu nhiên một số r trong khoảng [0,1].
- Nếu r < q1 (tức là r<1)thì chọn nhiễm sắc thể v1; ngược lại thì chọn
nhiễm sắc thể thứ i ( 2 ≤ i ≤ pop_size=M ) sao cho qi-1 ≤ r ≤ qi
Việc chọn lọc theo cách trên có thể minh
họa như sau: Ta có một bánh xe được chia thành n
phần, mỗi phần ứng với độ thích nghi của một cá
thể. Một mũi tên chỉ vào bánh xe. Quay bánh xe,
khi bánh xe dừng, mũi tên chỉ vào phần nào thì có thể ứng với phần đó được
chọn
Với cơ chế lựa chọn như thế này thì có một

Hình 2.2. Minh họa cho
kỹ thuật chọn lọc theo
kiểu quay bánh xe


số nhiếm sắc thể sẽ được chọn nhiều lần. Điều này
phù hợp với lý thuyết lược đồ: Các nhiễm sắc thể tốt nhất thì có nhiều bản
sao, nhiễm sắc thể trung bình thì không đổi, nhiễm sắc thể kém thì chết đi.
* Chọn lọc xếp hạng
Cơ chế lựa chọn xếp hạng được mô tả như sau:
- Sắp xếp các nhiễm sắc thể trong quần thể theo độ thích nghi từ thấp
đến cao.
- Đặt lại độ thích nghi cho quần thể đã sắp xếp theo kiểu: nhiễm sắc thể
thứ nhất có độ thích nghi là 1, nhiễm sắc thể thứ hai có độ thích nghi là 2, .v.v.,
nhiễm sắc thể thứ pop_size có độ thích nghi là pop_size.

Theo phương pháp này việc một nhiễm sắc thể được chọn nhiều lần như
trong lựa chọn theo kiểu bánh xe Roulet đã giảm đi. Nhưng nó có thể dẫn đến