BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC VINH

PHAN VĂN THẾ

ĐỀ CƯƠNG LUẬN VĂN THẠC SỸ
Chuyên ngành: CÔNG NGHỆ THÔNG TIN
Mã ngành: 60.48.02.01

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 THPT

Người hướng dẫn: TS.VŨ CHÍ CƯỜNG

1


Vinh, tháng 9/2017

2


NHẬN XÉT CỦA GIÁO VIÊN HƯỚNG DẪN
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..

……………………………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..
……………………………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..
……………………………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..
……………………………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..
……………………………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..
Kết luận: Đồng ý cho bảo vệ Đề cương CHTS đợt tháng 12/2017

Vinh, ngày …… tháng …… năm 2017
GIÁO VIÊN HƯỚNG DẪN

3



4


NHẬN XÉT CỦA HỘI ĐỒNG XÉT DUYỆT
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..
……………………………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..
……………………………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..
……………………………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..
……………………………………………………………………….
……………………………..……………………………………………………….
……………………………..……………………………………………………….
……………………………..…………………………………………………………..
……………………………………………………….……………………………..

……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..
……………………………………………………….……………………………..

Kết luận: Đồng ý/ không đồng ý cho tiếp tục triển khai đề tài CHTS để bảo vệ đợt
tháng 5/2018

HỘI ĐỒNG XÉT DUYỆT

Vinh, ngày …… tháng …… năm 2017
THƯ KÝ
5


6


MỤC LỤC
MỞ ĐẦU .............................................................................................................................................. 9
1. Sự cần thiết của vấn đề nghiên cứu ........................................................................................... 9
2. Mục tiêu nghiên cứu ................................................................................................................. 10
3. Đối tượng và phạm vi nghiên cứu ............................................................................................ 10
4. Ý nghĩa khoa học và thực tiễn của đề tài ................................................................................. 10
4.1. Ý nghĩa khoa học ..................................................................................................................... 10

4.2. Ý nghĩa thực tiễn ...................................................................................................................... 10
5. Kết cấu của luận văn (Giới thiệu tên các chương của luận văn) ........................................... 10
Chương I - GIẢI THUẬT DI TRUYỀN ........................................................................................... 11
1.1. Tổng quan về thuật toán di truyền ....................................................................................... 14
1.1.1. Giới thiệu .............................................................................................................................. 15
1.1.2. Sự khác biệt của thuật toán di truyền và thuật toán khác ...................................................15
1.1.3. Các tính chất của thuật toán di truyền ................................................................................ 16
1.2. Các thành phần trong thuật toán di truyền ......................................................................... 17
1.2.1. Biểu diễn nhiễm sắc thể ....................................................................................................... 17
1.2.1.1. Biểu diễn nhị phân .................................................................................................... 18
1.2.1.2. Biểu diễn số thực ...................................................................................................... 18
1.2.2. Khởi tạo quần thể ban đầu ................................................................................................... 18
1.2.3. Đánh giá cá thể .................................................................................................................... 18
1.2.4. Các phép toán di truyền ....................................................................................................... 19
1.2.4.1. Phương pháp chọn lọc ................................................................................................. 19
1.2.4.2. Phương pháp lai ghép .................................................................................................. 19
1.2.4.3. Phương pháp đột biến .................................................................................................. 20
1.2.5. Điều kiện dừng của thuật toán ............................................................................................. 20
1.2.6. Các tham số của thuật toán di truyền .................................................................................. 20
1.3. Ví dụ minh họa ....................................................................................................................... 21
Chương II – BÀI TOÁN SẮP XẾP THỜI KHÓA BIỂU ................................................................ 11
2.1. Tổng quan về bài toán lập lịch .............................................................................................. 11
2.1.1. Bài toán ................................................................................................................................. 11
2.1.2. Các thuộc tính ...................................................................................................................... 12
2.1.3. Một số bài toán lập lịch cơ bản ........................................................................................... 12
2.2. Bài toán xếp thời khóa biểu ................................................................................................... 12
2.2.1. Bài toán ................................................................................................................................ 12
2.2.2. Dữ liệu đầu vào .................................................................................................................... 13
2.2.3. Các ràng buộc ...................................................................................................................... 13
Chương III ......................................................................................................................................... 22

ỨNG DỤNG GIẢI THUẬT DI TRUYỀN CHO BÀI TOÁN LẬP THỜI KHÓA BIỂU 22
3.1. Phát biểu bài toán .................................................................................................................. 22
3.1.1. Biểu diễn nhiễm sắc thể ....................................................................................................... 22
3.1.2. Khởi tạo quần thể ................................................................................................................. 22
3.1.3. Các phép toán di truyền ....................................................................................................... 23
3.1.3.1. Lai ghép và Đột biến .................................................................................................... 23
3.1.3.2. Chọn lọc ........................................................................................................................ 23
3.1.3.3. Hàm đánh giá độ thích nghi ......................................................................................... 23
3.2. Phân tích và thiết kế chương trình ....................................................................................... 23
3.2.1 Phân tích và Mô tả dữ liệu đầu vào ...................................................................................... 23
3.2.2. Thiết kế chương trình ........................................................................................................... 23
3.3. Thử nghiệm và đánh giá kết quả .......................................................................................... 23
3.3.1.
Số liệu thử nghiệm ......................................................................................................... 23
3.3.2.
Kết quả đánh giá ........................................................................................................... 23

7


DANH MỤC CÁC TỪ VIẾT TẮT
GA: Genetic Algorithms
NST: Nhiễm sắc thể
DANH MỤC CÁC BẢNG
DANH MỤC CÁC HÌNH
Hình 1.1. Thuật toán di truyền
TÊ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 THPT
Quỳ Châu


8


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 THPT
MỞ ĐẦU
1. Sự cần thiết của vấn đề nghiên cứ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, chủ động 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 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ả 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 gần ba thập niên 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 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, 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. Ở Quỳ
Châu, 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 “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 khóa luận
tốt nghiệp. Khóa luậ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 xây dựng phần mềm, xem như một
9


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. Mục tiêu nghiên cứu
Nghiên cứu, tìm hiểu thuật toán di truyền, trên cơ sở đó tiếp cận để giải bài toán
thời khóa biểu cho Trường THPT.
3. Đối tượng và phạm vi nghiên cứu
Tìm hiểu bài toán lập lịch và các hướng giải quyết truyền thống.
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
4. Ý nghĩa khoa học và thực tiễn của đề tài
4.1. Ý nghĩa khoa học
Thông qua đề tài tác giả sẽ hiểu rõ hơn về bài toán lập lịch, các phuơng pháp tiếp
cận giải bài toán lập lịch, qua đó có sự so sánh và đánh giá các thuật toán.
Tìm hiểu sâu về thuật toán di truyền và ứng dụng vào bài toán thời khóa biểu
Trường THPT nhằm có những cải tiến trong các buớc của thuật toán di truyền với bài
toán cụ thể như việc biểu diễn bài toán, cách chọn cá thể tốt, cách xây dựng hàm đánh
giá, ...
4.2. Ý nghĩa thực tiễn

Bài toán lập thời khóa biểu là một bài toán có nhiều ứng dụng trong thực tế, đặc
biệt là các truờng học. Ứng dụng thuật toán di truyền để giải bài toán thời khóa biểu là
một hướng hy vọng giải quyết đuợc bài toán thời khóa biểu.
Qua đề tài, tác giả có thể xây dựng một ứng dụng thực tế góp phần giảm thiểu
thời gian và nguồn lực cho việc lập thời khóa biểu cho một Trường học.
5. Kết cấu của luận văn (Giới thiệu tên các chương của luận văn)

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. Bài toán xếp thời khóa
biểu trường học 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.
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
11


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ịnh 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
- 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 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.
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. Trước khi học kỳ mới bắt đầu, nội dung các môn học và
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ụ trach 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
12


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 vấn đề cần sắp xếp thời khoá biếu cho một trường THPT là
sự sắp xếp lịch học cho các lớp 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 khoá học
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
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.
Một giáo viên không dạy quá 5 tiết/buổi
Ràng buộc mềm:
Tất cả các bài học của một môn nào đó dạy tại một lớp phải được dạy
bởi cùng một giáo viên.
Mỗi lớp chỉ học 1 môn tại 1 thời điểm
Một lớp có thể có cùng một môn nhiều lần trong một ngày
Tất cả các giáo viên có cùng số lượng giờ dạy như nhau.
1.3. Một số Phần mềm xếp tời khóa biểu
1.2.1. Phần mềm xếp thừi khóa biểu SmartScheduler
1.2.2. Phần mềm xếp thừi khóa biểu của công ty SchoolNet

13


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. Trong nội dung của chương này, tôi
trình bày những đặc điểm cơ bản nhất của thuật toán di truyền.
Nhà bác học Charles Darwin đã nêu ra lý thuyết về sự tiến hóa tự nhiên của các
loài vật. Qua nhiều thế hệ, sinh vật phát triển dựa trên nguyên lý của sự chọn lọc tự
nhiên “loài nào thích nghi thì sẽ tồn tại”. Như ta thấy trong tự nhiên các loài vật sẽ
cạnh tranh nhau về nơi trú ẩn, thực phẩm,... Các cá thể cùng loài còn cạnh tranh nhau

để thu hút bạn tình trong mùa sinh sản. Do đó những cá thể nào ít thích nghi thì ít có
cơ hội tồn tại hơn và những cá thể thích nghi được thì sẽ phát triển và cho ra nhiều con
cái. Trong quá trình sinh sản sẽ tổ hợp các đặc tính tốt từ tổ tiên, sau một vài thế hệ
những loài tiến hóa tự nhiên sẽ thích nghi hơn trong môi trường phát triển.
Dựa trên nền tảng lý thuyết tiến hóa tự nhiên, năm 1975 Holland đã phát triển ý
tưởng này vào hệ thống nhân tạo, ông áp dụng nó để tối ưu hóa các vấn đề và xây
dựng thuật toán di truyền. Hiện nay thuật toán di truyền được xem như một công cụ
mạnh mẽ để giải quyết các vấn đề về tìm kiếm và tối ưu hóa phức tạp như thời gian
biểu, lập kế hoạch mua sắm.
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ó
14


đã 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ó 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 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 phuong 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.
15


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 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 để nguời sử dụng lụa chọn [.....].
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 sắc thể (NST)
mà để giới hạn trong thuật toán di truyền, ta quan niệm một cá thể có một NST. Do đó,
khái niệm cá thể và NST trong thuật toán di truyền coi như là tương đương.

Một NST đượ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 NST.
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.

16


Hình 1.1: Thuật toán di truyền
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.
17


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 INTEGER. 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
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
roulette wheel, chọn lọc xếp hàng, chọn lọc cạnh tranh, v.v…
+ Chọc lọc Roulette wheel
+ Chọn lọc xếp hạng (Rank Selection)
18


+ Chọn lọc cạnh tranh (Tournament Selection)
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 TKB

2.2.4.1. Phương pháp chọn lọc
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.
Giả sử thế hệ hiện thời là P(t) gồm n cá thể {x[1], x[2], ..., x[n]}. Số n được gọi
là cỡ của quần thể. Với cá thể x[*], ta tính độ thích nghi f(x[*]). Tính tổng độ thích
nghi của toàn bộ quần thể: F = f(x[1]) + f(x[2]) +... + f(x[n])
Mỗi lần chọn lọc, ta thực hiện hai bước sau:
Bước 1: Sinh một giá trị thích nghi ngẫu nhiên là một số thực q trong khoảng
(0, F);
Bước 2: x[k] là cá thể được chọn nếu k là số nhỏ nhất sao cho tổng độ thích
nghi của k cá thể đầu tiên không nhỏ hơn q, tức là f(x[1])+f(x[2])+... +f(x[k]) >=q.
Rõ ràng với cách chọn này, các cá thể có độ thích nghi càng cao (gây ra tổng
lớn hơn q) thì càng được chọn. Các cá thể có độ thích nghi cao có thể có một hay
nhiều bản sao, các cá thể có độ thích nghi thấp có thể không có mặt trong thế hệ sau
(nó bị chết đi).
2.2.4.2. Phương pháp lai ghép
Trên các cá thể được chọn lọc (sau khi thực hiện xong phương pháp chọn lọc),
ta tiến hành lai ghép. Với cỡ của quần thể là n, ta đưa ra một xác suất lai ghép là pc.
Xác suất này đưa ra hy vọng là có n*pc cá thể được lai ghép.
Với mỗi cá thể, ta thực hiện hai bước sau đây:
Bước 1: Sinh ra một xác suất lai ghép là số thực r nào đó trong đoạn [0,1]
Bước 2: Nếu r < pc thì cá thể đó được chọn để lai ghép Từ các cá thể được chọn
để lại ghép, ta cặp đôi chúng một cách ngẫu nhiên. Trong trường hợp nhiễm sắc thể là
các chuỗi nhị phân có độ dài cố định, giả sử là m, ta có thể thực hiện phép lai ghép như
sau:

19



Với mỗi cặp, sinh ra một vị trí ngẫu nhiên làm điểm bắt đầu ghép là một số
nguyên p trong đoạn [0, m-1].
Tổng quát, giả sử có hai cặp nhiễm sắc thể của hai cá thể được chọn lai
ghép: a = (a[1 ],..., a[p], a[p+1],..., a[m]) và b = (b[1 ],..., b[p], b[p+1],..., b[m])
Cặp này được thay thế bởi hai đoạn con của nhau từ vị trí thứ p+1:
a’ = (a[1 ],..., a[p], b[p+1],..., b[m]) và b’ = (b[1],..., b[p], a[p+1],..., a[m])
2.2.4.3. Phương pháp đột biến
Ta thực hiện đột biến trên các cá thể sau khi đã lai ghép. Đột biến là thay đổi
trạng thái của một số gen nào đó trong nhiễm sắc thể. Một gen chịu một xác suất đột
biến là pm. Xác suất đột biến pm do ta xác định và là xác suất thấp.
Tổng quát, với nhiễm sắc thể là chuỗi nhị phân. Với mỗi vị trí i trong nhiễm sắc
thể: a = (a[1 ],..., a[p], a[p+1],..., a[m])
Ta sinh ra một số thực ngẫu nhiên pi trong đoạn [0,1]. Đột biến a được biến
thành a’ như sau:
a' = [a’[1],..., a’[*],..., a’[m]), trong đó:
a’[*] = a[*] nếu pi >= pm và a’[*] = 1 - a[*] nếu pi < pm.
Sau quá trình chọn lọc, lai ghép, đột biến, một thế hệ mới được sinh ra. Công
việc còn lại của thuật toán là chỉ việc lặp lại các bước trên.
2.2.5. Điều kiện dừng của thuật toán
Một số điều kiện dừng của thuật toán:
Kết thúc theo kết quả, tức khi giá trị thích nghi của cá thể trong quần thể có giá
trị sai số nhỏ hơn một giá trị £ cho truớc, thì dừng thuật toán.
Kết thúc dựa trên số thế hệ, một số vấn đề dựa vào số thế hệ trong quần thể.
Khi số luợng tiến hoá của quần thể đến một giới hạn cho phép thì thuật toán sẽ dừng,
mà trong khi không quan tâm đến chất lượng của cá thể trong quần thể như thế nào.
Tính theo thời gian, phụ thuộc vào thời gian chạy chương trình được quy định
trước và thuật toán dừng.
Kết hợp nhiều phương pháp khác nhau, thuật toán cũng có thể sử dụng kết hợp
nhiều phương pháp khác nhau để giải quyết vấn đề

2.2.6. Các tham số của thuật toán di truyền
- Kích thước quần thể: PopSize, là số cá thể duy trì qua mỗi thế hệ tiến hóa của
thuật toán di truyền.
20


- Xác xuất đột biến: pm là xác suất đột biến của gen.
- Xác suất lai ghép: pc là xác suất một cá thể được chọn cho phép lai ghép
2.3. Ví dụ minh họa
2.3.1. Biểu diễn nhiễm sắc thể.
2.3.2. Hàm thích nghi
2.3.3. Khởi tạo quần thể
2.3.4. Chọn lọc cá thể
2.3.5. Phương pháp lai ghép
2.3.6. Phương pháp đột biến
2.3.7. Các tham số sử dụng trong ví dụ và điều kiện dừng

21


Chương III
ỨNG DỤNG THUẬT TOÁN DI TRUYỀN
CHO BÀI TOÁN LẬP THỜI KHÓA BIỂU
3.1. Phát biểu bài toán
Có một danh sách các giáo viên, một danh sách các khoảng thời gian, một danh
sách các lớp. Bài toán cần tìm thời khóa biểu tối ưu (giáo viên - thời gian - lớp); hàm
mục tiêu phải thỏa những mục tiêu này (các ràng buộc mềm) gồm: Có một số giờ được
xác định trước cho mỗi giáo viên và mỗi lớp; Chỉ một giáo viên trong một lớp vào một
giờ nhất định; Một giáo viên không thể dạy hai lớp cùng lúc; Đối với mỗi lớp được
xếp thời khóa biểu vào một khoảng thời gian, phải có một giáo viên... Ngoài ra còn có

các mục tiêu sư phạm như trải một số lớp ra nguyên tuần, những mục tiêu thuộc cá
nhân như những giáo viên hợp đồng không phải dạy buổi chiều, và các mục tiêu về tổ
chức như mỗi giờ có một giáo viên bổ sung sẵn sàng chỗ dạy tạm thời.
3.1.1. Biểu diễn nhiễm sắc thể
Biểu diễn nhiễm sắc thể tự nhiên nhất cho bài toán này là biểu diễn ma trận:
một ma trận, ở đây mỗi hàng tương ứng với một giáo viên, mỗi cột tương ứng với một
giờ, các phần tử của ma trận R là các lớp. Các ràng buộc chủ yếu được xử lý bởi các
toán tử di truyền và thuật toán được sử dụng để loại bỏ những trường hợp mà có nhiều
hơn một giáo viên xuất hiện trong cùng một lớp vào cùng một giờ.
Lịch học của một lớp gồm 3 thành phần chính, bao gồm: giáo viên, môn học,
tiết học trong tuần. Việc đặt ngẫu nhiên các môn học, giáo viên giảng dạy vào các tiết
học sẽ tạo thành thời khóa biểu của từng lớp. Như vậy một lớp học tương ứng sẽ có
nhiều lịch học khác nhau, do đó ta chọn mỗi lịch học làm cá thể trong thuật toán di
truyền.
3.1.2. Khởi tạo quần thể
Trước khi tạo quần thể ban đầu trong phần này, chúng ta phải chuẩn bị sẵn về
dữ liệu cho quá trình thực thi, từ lúc khởi tạo đến khi cho ra kết quả, bao gồm đầy đủ
thông tin của một lớp đang được chọn. Tất cả như sau :
Các ràng buộc lớp, giáo viên được phân công dạy.
Các môn học
Tính toán số tiết học tương ứng các môn.
22


Chọn qui định đọc và ghi nhận nhiễm sắc thể.
...
Giống như cá thể được mô tả ở trên, hàng loạt các cá thể được tạo ra và được
xem như quần thể ban đầu trong mô hình thuật toán di truyền của phần xếp lịch lớp.
Sau khi quần thể có đủ số lượng, bước tiếp theo là đánh giá quần thể, kiểm tra xem độ
thích nghi tốt nhất hiện đang tồn tại của quần thể.

3.1.3. Các phép toán di truyền
3.1.3.1. Lai ghép và Đột biến
3.1.3.2. Chọn lọc
3.1.3.3. Hàm đánh giá độ thích nghi
3.2. Phân tích và thiết kế chương trình
3.2.1 Phân tích và Mô tả dữ liệu đầu vào
Năm học
Danh sách môn học và lớp học trong học kỳ
Danh sách lớp học
Danh sách giáo viên
Danh sách môn học và số tiết
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
3.2.2. Thiết kế chương trình
Phần này sẽ dùng ngôn ngữ phân tích UML và Ngôn ngữ lập trình VB.Net để
thiết kế chương trình minh họa, thử nghiệm
3.3. Thử nghiệm và đánh giá kết quả
3.3.1. Số liệu thử nghiệm
Phần này sẽ trình bày các bảng số liệu thử nghiệm của chương trình với các số
liệu khởi tạo khác nhau, ràng buộc khác nhau.
3.3.2. Kết quả đánh giá

23


KẾT LUẬN
TÀI LIỆU THAM KHẢO
Tiếng Việt


1. Bùi Việt Hà (2004), “Mô hình bài toán Thời khóa biểu Đại học, Cao đẳng và
Trung học chuyên nghiệp”, Tin học & Nhà trường Số 4(55)- 2004, tr. 23-26.

2. Hoàng Xuân Huấn, Nguyễn Việt Thắng (2001), “Một giải pháp tiến hóa cho
bài toán thời khóa biểu", Bài gửi đăng tạp chí Tin học và Điều khiển học T.17
số 2 năm 2001, tr. 87-96.

3. Hoàng Kiếm, Lê Hoàng Thới, Thuật toán di truyền (2000), “Cách giải tự
nhiên các bài toán trên máy tính”, NXB Giáo dục.

4. Nguyễn Hữu Mùi (2000), “Phương pháp tính toán tiến hóa và ứng dụng để
giải đa thức”, Luận văn Thạc sĩ Khoa học ĐHQG Hà Nội.

5. Nguyễn Đình Thúc (2001), Lập trình tiến hóa, NXB Giáo dục .
6. ĐHBK, ĐHDLHV Tp. Hồ Chí Minh, ĐHQG Hà Nội (1999-2004), Một số luận
văn về thuật toán di truyền
Tiếng Anh

7. Jener Carr. (May 30 2014), An Introduction to Genetic Algrithems.
8. Ceft R., A new genetic algorithm, Analysis of Applied Probability 6 (3) (1996)
pp. 778-817.

9. Colorny A., Dorigo M., and Manieggo V. (1991), Genetic Algorithm and
Highly Constrained Problems, the Timetable Case, Problem Solving from
Nature, Springer-Velag, Lecture Notes in Computer Science, Vol. 496, pp.5559.

10. Davis L. and Comombs S., Genetic Algorithms and Communication Link
Speed Design Constraints and Operators, in [130]. pp 257-260.

11. Davis L. and Comombs S., Genetic Algorithms Communication Link Speed

Design Theorical Considerations, in [130], pp. 252-256.
Mạng Internet



24


PHỤ LỤC
TIẾN ĐỘ THỰC HIỆN ĐỀ TÀI
TT
1.

2.

3.

4.

5.
6.

Các nội dung, công việc
thực hiện
Xây dựng đề cương luận văn
Tìm hiểu thuật toán di truyền:
+ Biểu diễn NST cho bài toán
+ Khởi tạo quần thể ban đầu
+ Các phép toán di truyền:
chọn lọc, lai ghép, đột biến

+ Các tham số: kích thước
quần thể (PopSize), xác suất lai
Pc, tốc độ đột biến Pm
+ Hàm đánh giá độ thích
nghi
Nghiên cứu tổng quan bài toán
thời khóa biểu và các phương
pháp tiếp cận.
Nghiên cứu áp dụng thuật toán
di truyền vào bài toán thời
khóa biểu trường THPT Quỳ
Châu
Cài đặt bài toán thời khóa biểu
bằng ngôn ngữ VB.NET
Hoàn thiện Luận văn

Thời gian
(bắt đầu-kết thúc)
10/2017- 11/2017

Kết quả dự kiến
Đề cương luận văn

11/2017-12/2017

Chương 1 của luận
văn

12/2017 - 01/2018


Chương 2 của luận
văn

01/2018 – 2/2018
Chương 3 của luận
văn
02/2018 – 03/2018
03/2018 – 04/2018

Luận văn tốt nghiệp

25