Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp ACO và bài toán thời khoá biểu cho trường Đại học

Nội dung của luân văn được trình bày trong 4 chương như sau Chương 1: Trong chương này luận văn giới thiệu về các mô hình thời khóa biểu cho các trường học bao gồm cả trường phổ thông và đại học trên thế giới và bài toán chuẩn UCTP ( niversity ourse TimeTabling Problem), đồng thời giới thiệu qua về một số cách tiếp cận hiện nay cho bài toán lập thời khóa biểu. Chương 2: Giới thiệu phương pháp tối ưu hóa đàn kiến lịch sử phát triển, các thuật toán ACO, và một số nguyên tắc ứng dụng ACO Chương 3: Trình bày về cách thức chung để áp dụng tối ưu đàn kiến giải bài toán UCTP. (Đồng thời trong chương này chúng tôi trình bày các cải tiến cụ thể trong áp d ng tối ưu hóa đàn kiến với bài toán UCTP) Chương 4: Chương này giới thiệu về bộ dữ liệu chuẩn cho bài toán TP, các kết quả thực nghiệm và đánh giá trên thuật toán tối ưu đàn kiến sử dụng các quy tắc cập nhật mùi SMMAS và MMAS.
Nội dung trích xuất từ tài liệu:
Luận văn Thạc sĩ Công nghệ thông tin: Phương pháp ACO và bài toán thời khoá biểu cho trường Đại học ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN VĂN TUÂN PHƯƠNG PHÁP ACO VÀ BÀI TOÁN THỜI KHOÁ BIỂU CHO TRƯỜNG ĐẠI HỌCLUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Hà Nội - 2015 ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ NGUYỄN VĂN TUÂN PHƯƠNG PHÁP ACO VÀ BÀI TOÁN THỜI KHOÁ BIỂU CHO TRƯỜNG ĐẠI HỌC Ngành: Công nghệ Thông tin Chuyên ngành: Hệ thống Thông tin Mã số: 60.48.01.04 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TINNGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS HOÀNG XUÂN HUẤN Hà Nội - 2015 LỜI CẢM ƠN Tôi xin gửi lời cảm ơn chân thành nhất tới PGS.TS. Hoàng Xuân Huấn, ngườithầy đáng kính đã tận tình chỉ bảo, hướng dẫn tôi trong suốt quá trình tìm hiểu, nghiêncứu và hoàn thiện luận văn. Với kiến thức sâu rộng, nhiều năm nghiên cứu trong lĩnhvực tối ưu hóa cũng như phương pháp tối ưu hệ kiến của thầy đã giúp tôi hiểu rõ, sâusắc nhiều bài toán khó khăn gặp phải trong quá trình nghiên cứu. Thầy cũng đưa ranhững góp ý chi tiết, tỉ mỉ hết sức quý báu giúp cho tôi có thể hoàn thành quyển luậnvăn này. Tôi cũng xin được gửi lời cảm ơn sâu sắc tới Tiến Sĩ Đỗ Đức Đông và Thạc sĩTrần Ngọc Hà, những người đã giúp đỡ tôi giải quyết những khúc mắc trong quá trìnhviết chương trình để chạy thực nghiệm. Do thời gian và kiến thức có hạn nên luận văn chắc không tránh khỏi nhữngthiếu sót nhất định. Tôi rất mong nhận được những sự góp ý quý báu của thầy cô vàcác bạn. Hà Nội, tháng 01 năm 2015 Nguyễn Văn Tuân TÓM TẮT ài toán lập thời khóa biểu là một trong những lĩnh vực được nhiều người uantâm vì tính ứng ng cao của nó trong các t chức giáo c, trường học trên thế giới,là vấn đề đau đầu mà hàng năm bất k hệ thống trường học nào trên thế giới cũng phảiđối mặt. ác bài toán lập thời khóa biểu rất phong phú và đa ạng b i các ràng buộcvà yêu cầu của t ng t chức. Bài toán thời khóa biểu thuộc lớp NP khó [12] nên khó giải bằng các thuật toántruyền thống. Đến nay các thuật toán mô phỏng tự nhiên tỏ ra là phương pháp hữu hiệunhất để giải các bài toán này. Thuật toán i truyền là một trong những thuật toán môphỏng tự nhiên đầu tiên dựa vào sự tiến hóa và phát triển của ngành di truyền học. Gầnđây phương pháp tối ưu hóa đàn kiến o Dorigo đề xuất là một trong số các cách tiếpcận mới nhất. Đây là hai thuật toán tiêu biểu cho lớp thuật toán mô phỏng tự nhiên đểgiải uyết các bài toán tối ưu khó nói chung và bài toán thời khóa biểu nói riêng. M ctiêu luận văn “Phương pháp ACO và bài toán thời khoá biểu cho trường Đại học” lànghiên cứu và áp d ng phương pháp A O vào bài toán thời khoá biểu. Phương phápACO sử d ng quy tắc cập nhật mùi Max-Min Ant System (MMAS) đã được áp d ngcho bài toán thời khoá biểu và đã có kết quả khá tốt so với các phương pháp khác.Luận văn sẽ xem xét áp d ng thuật toán cập nhật mùi Smooth-Max Min AntSystem(SMMAS) cho bài toán thời khoá biểu. Smooth-Max Min Ant System là quytắc cập nhật mùi mới được PGS.TS Hoàng Xuân Huấn và đồng nghiệp đề xuất năm2011. Hệ kiến SMMAS đã được áp d ng vào bài toán TSP và chứng tỏ được hiệu quảcủa nó hơn hẳn hệ kiến MMAS (một hệ kiến được áp dùng nhiều nhất hiện nay).Trong luận văn này chúng tối tiến hành cài đặt mới thuật toán ACO theo quy tắc cậpnhật mùi SMMAS và chạy thực nghiệm so sánh với hai quy tắc cập nhật mùi MMAS,kết quả cho thấy hai thuật toán SMMAS có kết quả tốt hơn hẳn so với MMAS. i LỜI CAM ĐOAN Tôi xin cam đoan rằng đây là công trình nghiên cứu của cá nhân tôi ưới sựhướng dẫn giúp đỡ của PGS.TS. Hoàng Xuân Huấn. Các kết quả được viết chung vớicác tác giả khác đều được sự đồng ý của tác giả trước khi đưa vào luận văn. Trongtoàn bộ nội dung nghiên cứu của luận văn, các vấn đề được trình bày đều là những tìmhiểu và nghiên cứu của chính cá nhân tôi hoặc là được trích dẫn t các nguồn tài liệucó ghi tham khảo rõ ràng, hợp pháp. Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả đượcliệt kê tại m c tài liệu tham khảo Hà nội, tháng 01 năm 2016 Nguyễn Văn Tuân ii MỤC LỤCTÓM TẮT.........................................................................................................................iLỜI AM ĐOAN .................................................................... ...