MỞ ĐẦU 1. Lý do chọn đề tài Trong xu hướng phát triển của xã hội ngày nay, có rất nhiều ngành khoa học mới ra đời. Trong đó có một số ngành khoa học ra đời trên cơ sở phân lập từ các ngành khoa học cổ điển, và một số ngành do sự tích hợp giữa các ngành khoa học khác. Giải thuật di truyền (GA) là một trong những ngành khoa học ra đời từ sự tích hợp giữa sinh học và máy tính.
Giải thuật di truyền lấy ý tưởng từ quá trình tiến hoá tự nhiên, xuất phát từ một lớp các lời giải tiềm năng ban đầu, giải thuật di truyền tiến hành tìm kiếm trên không gian lời giải bằng cách xây dựng lớp lời giải mới tương đối tốt, cũng có thể là tốt nhất. Quá trình xây dựng lớp lời giải mới được tiến hành dựa trên việc chọn lọc, lai ghép, đột biến từ lớp lời giải ban đầu. Quần thể lời giải trải qua quá trình tiến hoá: ở mỗi thế hệ lại tái sinh các lời giải tương đối tốt hơn các thế hệ lời giải ban đầu, trong khi các lời giải “xấu” thì chết đi. 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 tối ưu nhất. 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 phương pháp tiếp cận để giải quyết bài toán này, như: trí tuệ nhân tạo, hệ chuyên gia, mạng Nơron, 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,… Nhưng trong đề tài này sẽ tìm hiểu và tiếp cận giải thuật di truyền cho lớp bài toán lập lịch và cụ thể là bài toán lập thời khóa biểu học theo hệ tín chỉ cho trường đại học. 1 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.
Mục đích nghiên cứu Nghiên cứu, tìm hiểu giải thuật di truyền và ứng dụng giải thuật để giải quyết một số bài toán lập lịch, trên cơ sở đó tiếp cận để giải bài toán thời khóa biểu theo hệ tín chỉ và xây dựng ứng dụng hiệu quả và thiết thực. Đố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 giải thuật di truyền. Ứng dụng giải thuật 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 theo học chế tín chỉ cho trường đại học, cao đẳng.
Phƣơng pháp nghiên cứu Dựa trên các tài liệu thu thập từ nhiều nguồn (sách, báo, Internet,… ) tổng hợp, phân tích và trình bày lại theo sự hiểu biết của bản thân. Mở rộng cách tiếp cận trước đây trên cơ sở phân tích đặc thù bài toán cần giải quyết để có những cải tiến hợp lý. Nghiên cứu ứng dụng những kết quả nghiên cứu vào thực tế. ọc và thực tiễn của đề tài 5.
Ý nghĩa khoa học Thông qua đề tài sẽ hiểu rõ hơn về bài toán lập lịch các các phươ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ề giải thuật di truyền và ứng dụng vào bài toán thời khóa biểu nhằm có những cải tiến trong các bước của giải thuật 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á, … 5. Ý 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 trường đại học, cao đẳng đào tạo theo học chế tín chỉ. Ứng dụng giải thuật 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 được bài toán thời khóa biểu.
2 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ Qua đề tài có thể xây dựng ứ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 cơ sở. Cấu trúc luận văn Luận văn gồm các chương có nội dung như sau: CHƢƠNG I - TỔNG QUAN BÀI TOÁN LẬP LỊCH Giới thiệu bài toán lập lịch, trình bày các khái niệm, định nghĩa liên quan đến lớp bài toán lập lịch. Tìm hiểu các loại bài toán lập lịch và qua đó định nghĩa các thành phần liên quan đến bài toán thời khoá biểu. Và một số thuật toán giải bài toán lập lịch.
CHƢƠNG II - GIẢI THUẬT DI TRUYỀN Trong chương, trình bày các khái niệm liên quan đến giải thuật di truyền cá thể, quần thể, các phép toán trong giải thuật: các phương pháp lai ghép, đột biến, các tham số và điều kiện dừng của giải thuật. Ví dụ minh hoạ cụ thể sự hoạt động của giải thuật di truyền CHƢƠNG III - ỨNG DỤNG GIẢI THUẬT DI TRUYỀN VÀO BÀI TOÁN LẬP THỜI KHÓA BIỂU Định nghĩa bài toán thời khoá biểu theo hướng tiếp cận di truyền, đưa ra thuật toán lai ghép, đột biến cho bài toán. Đánh giá các ràng buộc phải thoả mãn, xây dựng hàm thích nghi bằng cách cho điểm phạt. 3 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ CHƢƠNG I – TỔNG QUAN BÀI TOÁN LẬP LỊCH 1.
Giới thiệu bài toán lập lịch 1. Tìm hiểu chung Việc lập lịch đã được hình thành từ khi con người bắt đầu có sự phân công công việc trong xã hội và hiện nay vẫn tiếp tục tồn tại và phát triển cùng với sự tiến bộ của khoa học kỹ thuật. Một lịch biểu tốt sẽ giúp cho tiến trình thực hiện công việc ngắn lại, tiết kiệm được thời gian, nguồn lực, tài nguyên và nâng cao chất lượng trong sản xuất hay quản lý. Vì thế đã trải qua nhiều thập kỷ người ta không ngừng tìm hiểu, nghiên cứu và phát triển các phương pháp lập lịch để tìm kiếm lời giải tốt nhất cho các bài toán.
Bài toán lập lịch có thể được định nghĩa một cách chung nhất là bài toán cấp phát nguồn lực, tài nguyên để thực hiện tập hợp các công việc trong một chuỗi các tiến trình trên cơ sở thời gian, tài nguyên và các ràng buộc đã được định sẵn. Vì vậy việc lập lịch được xem như tìm kiếm một giải pháp tối ưu trong các điều kiện hạn chế. Người lập lịch cố gắng thử đến mức tối đa sự sử dụng các cá thể, máy móc, nguồn lực, tối thiểu thời gian để hoàn thành toàn bộ quá trình sắp xếp lịch. Như vậy khi giải quyết bài toán lập lịch đưa đến phải trả lời hai câu hỏi: - Tài nguyên nào sẽ được phân phối cho từng nhiệm vụ.
- Khi nào thì nhiệm vụ sẽ được giải quyết. Trong bài toán lập lịch bao hàm hai khía cạnh lý thuyết và thực tế, về lý thuyết thể hiện cố gắng giải quyết vấn đề về mô hình toán học. Khía cạnh thực tế là việc xây dựng các ứng dụng phù hợp với tập các ràng buộc trong thực tế. Hiệu quả của việc giải bài toán lập lịch luôn được gắn với việc lựa chọn các quyết định trong không gian quyết định (decision making)[8].
Trong thực tế việc đưa ra quyết định thường được xem xét trên cơ sở: - Hiệu quả sử dụng tài nguyên (resource). - Đáp ứng yêu cầu nhanh chóng. 4 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ - Giải quyết có trọng tâm. Tất cả các bài toán lập lịch cụ thể đều xuất phát từ nhu cầu ứng dụng trong thực tiễn để phục vụ mục đích của nhà quản lý.
Vì vậy vấn đề tối ưu các chi phí luôn luôn được xem xét như là một trong những ưu tiên hàng đầu của bộ lịch. Việc mô hình hoá và giải về mặt lý thuyết cho đến hiện nay thường dùng quy hoạch động. Tuy nhiên khi thực hiện khi giải bài toán trên máy tính thì không lúc nào cũng khả thi do tính phức tạp của nhiều bài toán dẫn đến một loạt các chi phí khác phát sinh, trong đó chi phí về thời gian là quan trọng nhất. Trong trường hợp nếu máy tính đủ khả năng (về cấu hình) để giải tối ưu thì trong hầu hết các trường hợp, người sử dụng cũng khó chấp nhận về mặt thời gian chờ đợi kết quả, đặc biệt với các bài toán lớn lượng biến sinh ra rất nhiều.
Chính vì vậy các ứng dụng thành công trên thực tế điều có sử dụng Heuristic (một phần hay toàn bộ) để kết quả thu được gần tối ưu có hiệu quả và được người dùng chấp nhận. Nhưng nhu cầu thực tế về kết quả cho từng bài toán cụ thể lại có thể rất khác nhau, chúng có thể cần “sắp xếp được” cho đến “sắp xếp gần tối ưu” và “sắp xếp tối ưu”. Vì vậy, cách giải trong từng bài toán phụ thuộc vào từng mô hình cụ thể của từng bài toán và từng thuật toán. Một số điểm mấu chốt khi tiếp cận giải bài toán lập lịch: Xác định nhu cầu, mục tiêu, giới hạn, độ phức tạp.
Xác định các loại ràng buộc. Xây dựng mô hình. Xây dựng giải thuật, các hướng giải quyết. Cài đặt chương trình.
Thật dễ thấy rằng, bài toán lập lịch là những bài toán rất quan trọng trong thực tế và chúng xuất hiện hầu hết mọi nơi trong cuộc sống hằng ngày như: lập lịch cho các chuyến bay của hãng hàng không, lập lịch phát sóng cho các tiết mục trong đài truyền hình, lập lịch thi, lập thời khoá biểu học tập,. Và hiện nay bài toán đã và 5 Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.vn/ đang có nhiều nhà nghiên cứu, chuyên gia tìm kiếm các phương pháp tiếp cận để giải quyết bài toán như: trí tuệ nhân tạo, hệ chuyên gia, mạng Noron, lập trình tính toán, tìm kiếm nhánh và đường biên, kỹ thuật mô phỏng luyện kim, tìm kiếm Tabu, …. Các thuộc tính của bài toán lập lịch Tài nguyên: Là 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 tốn nguồn tài nguyên.
Ràng buộc: Là những điều kiện cần được thoả mãn để bài toán có thể đưa ra lời giải tốt nhất. Mục tiêu: Đánh giá độ mức độ tối ưu của lời giải của bài toán. Khi các mục tiêu được thoả mãn thì các ràng buộc cũng được thoả mãn.