Luận Văn Thạc Sĩ: Phương Pháp ACO và Bài Toán Lập Thời Khóa Biểu Cho Trường Đại Học

Luận văn thạc sĩ toán học phân tích vnu uet phương pháp aco và bài toán thời khóa biểu cho trường đại học, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi cho thực

• Tác giả: Nguyễn Văn Tuân
• Người hướng dẫn: PGS.TS Hoàng Xuân Huấn
• Trường học: Đại Học Quốc Gia Hà Nội Trường Đại Học Công Nghệ
• Chuyên ngành: Công Nghệ Thông Tin
• Đề tài: Phương Pháp ACO và Bài Toán Thời Khoá Biểu Cho Trường Đại Học
• Loại tài liệu: Luận Văn Thạc Sĩ
• Năm xuất bản: 2015
• Địa điểm: Hà Nội

Mục lục chi tiết

• LỜI CẢM ƠN
• TÓM TẮT
• LỜI CAM ĐOAN
• MỤC LỤC
• DANH SÁCH CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT
• DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ
• DANH SÁCH BẢNG BIỂU
• MỞ ĐẦU
• 1. CHƯƠNG 1: GIỚI THIỆU BÀI TOÁN LẬP THỜI KHÓA BIỂU
• 1.1. Bài toán lập thời khóa biểu cho trường phổ thông
• 1.2. Bài toán xếp lịch thi
• 1.3. Bài toán lập thời khóa biểu cho trường đại học
• 1.4. Các cách tiếp cận hiện nay
• 2. CHƯƠNG 2: PHƯƠNG PHÁP TỐI ƯU HÓA ĐÀN KIẾN
• 3. CHƯƠNG 3: ÁP DỤNG TỐI ƯU HÓA ĐÀN KIẾN CHO BÀI TOÁN UCTP
• 4. CHƯƠNG 4: BỘ DỮ LIỆU CHUẨN VÀ KẾT QUẢ THỰC NGHIỆM
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Tổng Quan Về Phương Pháp ACO Trong Lập Thời Khóa Biểu Đại Học

Phương pháp ACO (Tối ưu hóa đàn kiến) đã trở thành một trong những giải pháp hiệu quả cho bài toán lập thời khóa biểu trong các trường đại học. Bài toán này không chỉ phức tạp mà còn đòi hỏi sự tối ưu hóa cao để đáp ứng nhu cầu học tập của sinh viên và giảng viên. ACO sử dụng các nguyên tắc của tự nhiên để tìm ra giải pháp tối ưu cho bài toán này.

1.1. Khái Niệm Về Phương Pháp ACO

Phương pháp ACO là một thuật toán tối ưu hóa dựa trên hành vi của đàn kiến trong tự nhiên. Đàn kiến tìm kiếm thức ăn và để lại dấu mùi, từ đó giúp các con kiến khác tìm ra đường đi ngắn nhất. Tương tự, ACO áp dụng nguyên tắc này để giải quyết các bài toán tối ưu, trong đó có bài toán lập thời khóa biểu.

1.2. Lợi Ích Của Việc Sử Dụng ACO

Việc áp dụng ACO trong lập thời khóa biểu mang lại nhiều lợi ích như: giảm thiểu xung đột giữa các môn học, tối ưu hóa thời gian học tập cho sinh viên, và nâng cao hiệu quả quản lý thời gian cho giảng viên. ACO giúp tìm ra các giải pháp tối ưu hơn so với các phương pháp truyền thống.

II. Thách Thức Trong Lập Thời Khóa Biểu Đại Học

Bài toán lập thời khóa biểu cho các trường đại học thường gặp nhiều thách thức do sự phức tạp của các ràng buộc. Các yếu tố như số lượng môn học, số lượng giảng viên, và yêu cầu của sinh viên tạo ra một không gian tìm kiếm rất lớn. Điều này khiến cho việc tìm kiếm giải pháp tối ưu trở nên khó khăn.

2.1. Các Ràng Buộc Trong Lập Thời Khóa Biểu

Các ràng buộc trong lập thời khóa biểu bao gồm: không để sinh viên tham gia nhiều môn học cùng một lúc, đảm bảo phòng học đủ lớn cho số lượng sinh viên, và không tổ chức nhiều môn học trong cùng một phòng học tại một thời điểm. Những ràng buộc này làm cho bài toán trở nên phức tạp hơn.

2.2. Tác Động Của Các Yếu Tố Bên Ngoài

Ngoài các ràng buộc nội tại, còn có nhiều yếu tố bên ngoài ảnh hưởng đến việc lập thời khóa biểu như: thay đổi trong số lượng sinh viên, sự thay đổi trong lịch giảng dạy của giảng viên, và các sự kiện đặc biệt trong trường. Những yếu tố này cần được xem xét để đảm bảo tính khả thi của thời khóa biểu.

III. Phương Pháp ACO Trong Giải Quyết Bài Toán Lập Thời Khóa Biểu

Phương pháp ACO đã được áp dụng thành công trong việc giải quyết bài toán lập thời khóa biểu. Các thuật toán như Max-Min Ant System (MMAS) và Smooth-Max Min Ant System (SMMAS) đã cho thấy hiệu quả cao trong việc tìm kiếm giải pháp tối ưu.

3.1. Thuật Toán Max Min Ant System MMAS

MMAS là một trong những thuật toán ACO đầu tiên được áp dụng cho bài toán lập thời khóa biểu. Thuật toán này sử dụng quy tắc cập nhật mùi để cải thiện khả năng tìm kiếm giải pháp tối ưu. Kết quả cho thấy MMAS có thể tìm ra các giải pháp tốt hơn so với các phương pháp truyền thống.

3.2. Thuật Toán Smooth Max Min Ant System SMMAS

SMMAS là một cải tiến của MMAS, được phát triển để tăng cường khả năng tìm kiếm và giảm thiểu xung đột trong lập thời khóa biểu. Thuật toán này đã chứng minh được hiệu quả vượt trội trong việc tìm kiếm giải pháp tối ưu cho bài toán lập thời khóa biểu.

IV. Ứng Dụng Thực Tiễn Của Phương Pháp ACO

Phương pháp ACO đã được áp dụng trong nhiều trường đại học để giải quyết bài toán lập thời khóa biểu. Kết quả thực nghiệm cho thấy ACO không chỉ giúp tối ưu hóa thời gian học tập mà còn nâng cao sự hài lòng của sinh viên và giảng viên.

4.1. Kết Quả Nghiên Cứu Tại Các Trường Đại Học

Nhiều nghiên cứu đã chỉ ra rằng việc áp dụng ACO trong lập thời khóa biểu đã giúp giảm thiểu xung đột giữa các môn học và tối ưu hóa thời gian học tập cho sinh viên. Các trường đại học đã ghi nhận sự cải thiện rõ rệt trong hiệu quả quản lý thời gian.

4.2. Phản Hồi Từ Sinh Viên Và Giảng Viên

Phản hồi từ sinh viên và giảng viên cho thấy họ hài lòng hơn với thời khóa biểu được lập bằng phương pháp ACO. Sự linh hoạt và khả năng đáp ứng nhu cầu học tập đã được cải thiện đáng kể, tạo điều kiện thuận lợi cho việc học tập và giảng dạy.

V. Kết Luận Và Tương Lai Của Phương Pháp ACO Trong Lập Thời Khóa Biểu

Phương pháp ACO đã chứng minh được tính hiệu quả trong việc giải quyết bài toán lập thời khóa biểu. Tương lai của phương pháp này hứa hẹn sẽ còn phát triển hơn nữa với sự cải tiến trong các thuật toán và ứng dụng công nghệ mới.

5.1. Triển Vọng Phát Triển Của ACO

Với sự phát triển của công nghệ và các thuật toán mới, ACO có thể được cải tiến để giải quyết các bài toán phức tạp hơn trong tương lai. Các nghiên cứu tiếp theo sẽ tập trung vào việc tối ưu hóa hơn nữa quy trình lập thời khóa biểu.

5.2. Ứng Dụng Công Nghệ Mới

Công nghệ mới như trí tuệ nhân tạo và học máy có thể được tích hợp vào phương pháp ACO để nâng cao khả năng tìm kiếm và tối ưu hóa. Điều này sẽ mở ra nhiều cơ hội mới cho việc lập thời khóa biểu trong các trường đại học.

Trích đoạn nội dung tài liệu

ĐẠ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 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN Hà Nội - 2015 LUAN VAN CHAT LUONG download : add [e-mail] ĐẠ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.04 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN NGƯỜI HƯỚNG DẪN KHOA HỌC: PGS.TS HOÀNG XUÂN HUẤN Hà Nội - 2015 LUAN VAN CHAT LUONG download : add [e-mail] LỜI CẢM ƠN Tôi xin gửi lời cảm ơn chân thành nhất tới PGS. Hoàng Xuân Huấn, người thầ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ên cứ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ĩnh vự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âu sắ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 ra nhữ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ận vă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ình viế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ững thiế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 LUAN VAN CHAT LUONG download : add [e-mail] 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 uan tâ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ộc và 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án truyề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ệu nhấ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ếp cậ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 c tiê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áp ACO sử d ng quy tắc cập nhật mùi Max-Min Ant System (MMAS) đã được áp d ng cho 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 Ant System(SMMAS) cho bài toán thời khoá biểu. Smooth-Max Min Ant System là quy tắ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ăm 2011. 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ập nhậ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 LUAN VAN CHAT LUONG download : add [e-mail] 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. Hoàng Xuân Huấn. Các kết quả được viết chung với cá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. Trong toà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ìm hiể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ệu có 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ả được liệ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 LUAN VAN CHAT LUONG download : add [e-mail] MỤC LỤC TÓM TẮT.i LỜI AM ĐOAN . ii MỤC LỤC . iii DANH SÁCH CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT . v DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ .vi DANH SÁCH BẢNG BIỂU .vi MỞ ĐẦU . GIỚI THIỆ I TO N P T ỜI A IỂ . ác bài toán lập thời khóa biểu . ài toán lập thời khóa biểu cho trường ph thông (School timetabling) . Bài toán xếp lịch thi (Examination timetabling) . ài toán lập thời khóa biểu cho trường đại học ( niversity timetabling) . Các cách tiếp cận hiện nay . P ƯƠNG P P TỐI Ư Đ N IẾN . T kiến tự nhiên đến kiến nhân tạo . Kiến tự nhiên . Kiến nhân tạo (Artificial Ant) . Phương pháp tối ưu đàn kiến . Đồ thị cấu trúc . Mô tả thuật toán ACO t ng quát . Hệ kiến AS . Hệ kiến ACS . Hệ kiến MAX-MIN . Hệ kiến ba mức . Hệ kiến đa mức . Hệ kiến Smooth-Max Min . Một số vấn đề liên quan. Đặc tính hội t . ACO kết hợp với tìm kiếm địa phương . Thông tin heuristic . Số lượng kiến . 26 iii LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Tham số bay hơi . P ƯƠNG P P A O CHO BÀI TOÁN UTCP . Áp d ng thuật toán ACO cho bài toán UCTP . ây ựng đồ thị cấu trúc cho bài toán TP . Thông tin heuristic . Thuật toán ghép cặp cực đại để tìm lời giải hoàn chỉnh . Mô tả thuật toán . Các thuật toán ACO được áp d ng cho bài toán UCTP . Thuật toán hệ kiến MMAS . Thuật toán hệ kiến Smooth-Max Min Ant System. Dữ liệu thực nghiệm . 42 TÀI LIỆU THAM KHẢO . 43 iv LUAN VAN CHAT LUONG download : add [e-mail] DANH SÁCH CÁC KÝ HIỆU VÀ CHỮ VIẾT TẮT STT Từ viết tắt Từ hoặc cụm từ Ant Colony Optimization 1 ACO (Tối ưu hóa đàn kiến) Ant System 2 AS (Hệ kiến AS) Ant Colony System 3 ACS (Hệ kiến ACS) Max-Min Ant System 4 MMAS (Hệ kiến MMAS) Smooth-Max Min Ant System 5 SMMAS (Hệ kiến MMAS trơn) Multi-level Ant System 6 MLAS (Hệ kiến đa mức MLAS) 7 Opt Optimization 8 Avg Average Travelling Salesman Problem 9 TSP ( ài toán người chào hàng) 10 g-best global-best 11 i-best iteration-best University Course Timetabling Problem 12 UCTP (bài toán xếp thời khoá biểu) v LUAN VAN CHAT LUONG download : add [e-mail] DANH MỤC CÁC HÌNH VẼ, ĐỒ THỊ Hình 2. Thể hiện hành vi của mỗi con kiến trong tự nhiên .2: Thực nghiệm cây cầu đôi . Thí nghiệm b xung. Đồ thị cấu trúc t ng quát cho bài toán cực trị hàm . Lựa chọn đỉnh đi tiếp theo . Đặc tả thuật toán ACO . Đồ thị cấu trúc cho bài toán UCTP . 27 DANH SÁCH BẢNG BIỂU ảng 4. Giá trị các tham số đầu vào cho ba loại bộ dữ liệu . ác tham số tĩnh sử d ng cho bài toán UCTP các thuật toán đàn kiến . So sánh thuật toán hệ kiến SMMAS, đa mức và hệ kiến Max-Min với các bộ dữ liệu điển hình . 41 vi LUAN VAN CHAT LUONG download : add [e-mail] MỞ ĐẦU à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 uan tâ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ộc và 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án truyề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ệu nhấ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ếp cậ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. Trong nước ta, mô hình đào tạo đại học theo niên chỉ đang chuyển sang đào tạo hệ tín chỉ nhưng bài toán này chưa được nghiên cứu nhiều và trong thực tế chưa có phần mềm nào sử d ng được. Với đề tài “Phương pháp ACO và bài toán thời khoá biểu cho trường Đại Học”, luận văn mạnh ạn nghiên cứu phương pháp giải cho bài toán lập thời khóa biểu trường đại học hệ tín chỉ theo mẫu của một bài toán chu n trên internet (www.org) và thực hiện thực nghiệm trên thuật toán tối ưu đàn kiến. Đối với thuật toán tối ưu đàn kiến chúng tôi tìm hiểm các hệ kiến đã áp ng cho bài toán thời khoá biểu hiện nay bao gồm hệ kiến ACS, hệ kiến Max-Min Ant System(MMAS) đồng thời sử d ng qui tắc cập nhật mùi Smooth-Max Min Ant System(SMMAS) mới áp d ng cho bào toán này. iệu uả của thuật toán áp d ng quy tắc cập nhật mùi Smooth-Max Min Ant System so với MMAS được so sánh bằng thực nghiệm dựa trên các test chu n trên mạng (http://iridia.be/~msampels/tt. Kết quả thực nghiệm cho thấy hiệu quả của thuật toán Smooth-Max Min tốt hơn Max- Min. Vì thời gian làm luận văn ngắn, nên chúng tôi chưa đưa ra được phần mềm sử ng được của bài toán này, hi vọng trong thời gian tới có thể phát triển mô hình này áp ng cho các bài toán lập thời khóa biểu cho một số trường đại học thực tế Việt Nam.