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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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.
GIẢI THUẬT DI TRUYỀN: 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ẻ.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. 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.
í 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.