Thạc Sĩ Thuật giải di truyền và ứng dụng lập thời khóa biều theo học chế tín chỉ cho trường đại học

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.

Thuật giải 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.

Thuật giải 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, thuật giải 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 thuật giải 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.

2. Mục đích nghiên cứu
Nghiên cứu, tìm hiểu thuật giải di truyền và ứng dụng thuật giải để 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.

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 giải di truyền.
Ứng dụng thuật giải 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.

4. 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ế.

5. Ý nghĩa khoa học và thực tiễn của đề tài
5.1. Ý 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ề thuật giải 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 thuật giải 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.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 trường đại học, cao đẳng đào tạo theo học chế tín chỉ. Ứng dụng thuật giải 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.
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ở.

6. 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 1 - TỔNG QUAN BÀI TOÁN LẬP LỊCH
Giới thiệu bài toán lập lịch, trong chương, 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 2 - THUẬT GIẢI DI TRUYỀN
Trong chương, trình bày các khái niệm liên quan đến thuật giải di truyền cá thể, quần thể, các phép toán trong thuật giải: 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 thuật giải. Ví dụ minh hoạ cụ thể sự hoạt động của thuật giải di truyền
Chương 3 - ỨNG DỤNG GIẢI THUẬT DI TRUYỀN VÀO BÀI TOÁN XẾ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.