I. Giới thiệu về Luận Văn Thạc Sĩ
Luận văn thạc sĩ này tập trung vào việc áp dụng giải thuật di truyền để sắp xếp thời khóa biểu cho các trường đại học, sử dụng bộ đồng xử lý Intel Xeon Phi. Mục tiêu chính là tối ưu hóa quá trình sắp xếp thời khóa biểu, đảm bảo các ràng buộc cứng và mềm được thỏa mãn, đồng thời giảm thiểu thời gian thực thi. Giải thuật di truyền được chọn vì khả năng giải quyết các bài toán tối ưu phức tạp, đặc biệt trong lĩnh vực khoa học máy tính và công nghệ thông tin.
1.1. Lý do chọn đề tài
Việc sắp xếp thời khóa biểu là một bài toán phức tạp, đòi hỏi sự tối ưu hóa cao để đáp ứng các yêu cầu của trường đại học. Các phương pháp truyền thống thường tốn nhiều thời gian và không hiệu quả. Giải thuật di truyền kết hợp với xử lý song song trên Intel Xeon Phi được đề xuất để giải quyết vấn đề này, giúp rút ngắn thời gian thực thi và nâng cao hiệu suất.
1.2. Mục tiêu đề tài
Mục tiêu của luận văn là phát triển một giải pháp sắp xếp thời khóa biểu hiệu quả, sử dụng giải thuật di truyền và Intel Xeon Phi. Các kết quả thực nghiệm cho thấy thời gian thực thi giảm đáng kể so với các phương pháp truyền thống, đặc biệt với các tập dữ liệu lớn.
II. Cơ sở lý thuyết và phương pháp
Luận văn dựa trên các lý thuyết nền tảng về giải thuật di truyền, xử lý song song, và kiến trúc của Intel Xeon Phi. Giải thuật di truyền mô phỏng quá trình tiến hóa tự nhiên, bao gồm các bước khởi tạo quần thể, chọn lọc, lai ghép, và đột biến. Xử lý song song được áp dụng để tối ưu hóa hiệu suất tính toán, đặc biệt với các bài toán có không gian tìm kiếm lớn.
2.1. Giải thuật di truyền
Giải thuật di truyền là một phương pháp tối ưu hóa dựa trên nguyên lý tiến hóa tự nhiên. Quá trình bao gồm khởi tạo quần thể, chọn lọc cá thể, lai ghép, và đột biến. Phương pháp này được áp dụng rộng rãi trong các bài toán tối ưu hóa và lập trình.
2.2. Xử lý song song trên Intel Xeon Phi
Intel Xeon Phi là bộ đồng xử lý được thiết kế cho các hệ thống hiệu suất tính toán cao. Luận văn sử dụng các mô hình xử lý song song như Master-Slave, Fine-Grained, và Coarse-Grained để tối ưu hóa hiệu suất của giải thuật di truyền.
III. Phương pháp giải bài toán sắp xếp thời khóa biểu
Luận văn đề xuất một phương pháp sắp xếp thời khóa biểu dựa trên giải thuật di truyền và Intel Xeon Phi. Quá trình bao gồm khởi tạo quần thể, đánh giá hàm lượng giá, và áp dụng các phép lai ghép và đột biến. Các ràng buộc cứng và mềm được xem xét để đảm bảo tính khả thi và tối ưu của thời khóa biểu.
3.1. Khởi tạo quần thể và hàm lượng giá
Quần thể được khởi tạo ngẫu nhiên, sau đó được đánh giá bằng hàm lượng giá để xác định mức độ phù hợp với các ràng buộc. Hàm lượng giá được thiết kế để đánh giá cả ràng buộc cứng và mềm.
3.2. Phép lai ghép và đột biến
Các phép lai ghép và đột biến được áp dụng để tạo ra các cá thể mới, giúp tìm kiếm các giải pháp tối ưu hơn. Phương pháp này được thực hiện song song trên Intel Xeon Phi để tăng tốc độ tính toán.
IV. Kết quả và đánh giá
Kết quả thực nghiệm cho thấy giải thuật di truyền kết hợp với Intel Xeon Phi giúp giảm thời gian thực thi đáng kể. Với các tập dữ liệu nhỏ, thời gian thực thi giảm 20 lần so với phương pháp truyền thống. Với các tập dữ liệu lớn, thời gian thực thi giảm 4 lần. Điều này chứng tỏ hiệu quả của phương pháp được đề xuất.
4.1. So sánh với các phương pháp khác
Luận văn so sánh kết quả với các phương pháp khác như mô phỏng luyện kim và tìm kiếm Tabu. Kết quả cho thấy giải thuật di truyền kết hợp với Intel Xeon Phi vượt trội về hiệu suất và thời gian thực thi.
4.2. Đánh giá hiệu suất
Hiệu suất của giải thuật di truyền được đánh giá dựa trên thời gian thực thi và chất lượng của thời khóa biểu. Kết quả cho thấy phương pháp này đáp ứng được các yêu cầu của bài toán sắp xếp thời khóa biểu.
V. Kết luận và hướng phát triển
Luận văn đã chứng minh hiệu quả của giải thuật di truyền kết hợp với Intel Xeon Phi trong việc sắp xếp thời khóa biểu. Phương pháp này không chỉ giảm thời gian thực thi mà còn đảm bảo tính tối ưu của thời khóa biểu. Hướng phát triển trong tương lai bao gồm cải tiến giải thuật di truyền và áp dụng các công nghệ xử lý song song tiên tiến hơn.
5.1. Đóng góp của luận văn
Luận văn đã đóng góp một phương pháp hiệu quả để sắp xếp thời khóa biểu, giúp các trường đại học tiết kiệm thời gian và nâng cao chất lượng thời khóa biểu.
5.2. Hướng phát triển
Hướng phát triển bao gồm cải tiến giải thuật di truyền, tích hợp thêm các ràng buộc phức tạp, và áp dụng các công nghệ xử lý song song mới để nâng cao hiệu suất.
