Phương pháp ACO và ứng dụng trong 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ĩ nghiên cứu 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, đánh giá hiện trạng, phân tích vấn đề, đề xuất biện pháp hoàn thiện

• 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
• Chuyên ngành: Công nghệ Thông tin
• Đề tài: Phương pháp ACO và bài toán thời khóa 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

• TÓM TẮT
• LỜI CAM ĐOAN
• 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. Các bài toán lập thời khóa biểu
• 1.1.1. Bài toán lập thời khóa biểu cho trường phổ thông (School timetabling)
• 1.1.2. Bài toán xếp lịch thi (Examination timetabling)
• 1.1.3. Bài toán lập thời khóa biểu cho trường đại học (University timetabling)
• 1.2. Các cách tiếp cận hiện nay
• 2. CHƯƠNG 2: PHƯƠNG PHÁP TỐI ƯU ĐÀN KIẾN
• 2.1. Từ kiến tự nhiên đến kiến nhân tạo
• 2.1.1. Kiến tự nhiên
• 2.1.2. Kiến nhân tạo (Artificial Ant)
• 2.2. Phương pháp tối ưu đàn kiến
• 2.2.1. Đồ thị cấu trúc
• 2.2.2. Mô tả thuật toán ACO tổng quát
• 2.2.3. Hệ kiến AS
• 2.2.4. Hệ kiến ACS
• 2.2.5. Hệ kiến MAX-MIN
• 2.2.6. Hệ kiến ba mức
• 2.2.7. Hệ kiến đa mức
• 2.2.8. Hệ kiến Smooth-Max Min
• 2.3. Một số vấn đề liên quan
• 2.3.1. Đặc tính hội tụ
• 2.3.2. ACO kết hợp với tìm kiếm địa phương
• 2.3.3. Thông tin heuristic
• 2.3.4. Số lượng kiến
• 2.3.5. Tham số bay hơi
• 3. CHƯƠNG 3: PHƯƠNG PHÁP ACO CHO BÀI TOÁN UCTP
• 3.1. Áp dụng thuật toán ACO cho bài toán UCTP
• 3.1.1. Xây dựng đồ thị cấu trúc cho bài toán UCTP
• 3.1.2. Thông tin heuristic
• 3.1.3. Thuật toán ghép cặp cực đại để tìm lời giải hoàn chỉnh
• 3.1.4. Mô tả thuật toán
• 3.2. Các thuật toán ACO được áp dụng cho bài toán UCTP
• 3.2.1. Thuật toán hệ kiến MMAS
• 3.2.2. Thuật toán hệ kiến Smooth-Max Min Ant System
• 3.3. Dữ liệu 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

Phương pháp ACO (Ant Colony Optimization) đã 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 thường gặp nhiều thách thức do tính phức tạp và các ràng buộc khác nhau. ACO sử dụng mô hình hành vi của đàn kiến để tìm kiếm giải pháp tối ưu cho việc phân bổ thời gian và không gian học tập. Nghiên cứu này sẽ đi sâu vào cách thức hoạt động của ACO và ứng dụng của nó trong lập thời khóa biểu.

1.1. Định nghĩa và nguyên lý hoạt động của ACO

ACO là một thuật toán tối ưu hóa dựa trên hành vi tìm kiếm thức ăn của đàn kiến. Mỗi con kiến sẽ tìm kiếm đường đi từ tổ đến nguồn thức ăn và để lại dấu mùi pheromone. Các con kiến khác sẽ theo dấu mùi này để tìm đường đi ngắn nhất. Nguyên lý này được áp dụng để giải quyết bài toán lập thời khóa biểu bằng cách tối ưu hóa các ràng buộc và yêu cầu của từng môn học.

1.2. Lợi ích của ACO trong lập thời khóa biểu

Sử dụng ACO giúp giảm thiểu thời gian và công sức trong việc lập thời khóa biểu. Phương pháp này có khả năng tìm ra nhiều giải pháp khả thi và tối ưu hơn so với các phương pháp truyền thống. ACO cũng cho phép điều chỉnh linh hoạt các ràng buộc, từ đó nâng cao hiệu quả quản lý lịch học.

II. Thách thức trong việc lập thời khóa biểu cho trường đại học

Lập thời khóa biểu cho trường đại học là một bài toán phức tạp do nhiều yếu tố cần xem xét. Các ràng buộc như số lượng sinh viên, giáo viên, phòng học và thời gian học đều ảnh hưởng đến quá trình lập lịch. Bên cạnh đó, việc đảm bảo không có sự chồng chéo giữa các môn học cũng là một thách thức lớn. Những vấn đề này cần được giải quyết hiệu quả để đảm bảo chất lượng giáo dục.

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: số lượng sinh viên tối đa trong mỗi lớp, thời gian học của giáo viên, và yêu cầu về phòng học. Những yếu tố này cần được cân nhắc kỹ lưỡng để tránh tình trạng quá tải hoặc thiếu phòng học.

2.2. Tác động của việc lập thời khóa biểu không hiệu quả

Việc lập thời khóa biểu không hiệu quả có thể dẫn đến tình trạng sinh viên không thể tham gia đầy đủ các môn học, ảnh hưởng đến kết quả học tập. Ngoài ra, giáo viên cũng có thể gặp khó khăn trong việc quản lý lớp học, gây ra sự không hài lòng trong quá trình giảng dạy.

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 cho trường đại học. Bằng cách sử dụng các quy tắc cập nhật pheromone, ACO có thể tìm ra các giải pháp tối ưu cho việc phân bổ thời gian và không gian học tập. Nghiên cứu này sẽ trình bày chi tiết về cách thức áp dụng ACO trong lập thời khóa biểu.

3.1. Quy trình áp dụng ACO vào lập thời khóa biểu

Quy trình áp dụng ACO bao gồm các bước: xác định các ràng buộc, khởi tạo đàn kiến, cho phép các con kiến tìm kiếm giải pháp và cập nhật pheromone. Mỗi lần lặp, ACO sẽ cải thiện giải pháp dựa trên thông tin từ các lần tìm kiếm trước đó.

3.2. So sánh hiệu quả của ACO với các phương pháp khác

Nghiên cứu cho thấy ACO có hiệu quả cao hơn so với các phương pháp truyền thống như quy hoạch tuyến tính hay thuật toán di truyền. ACO không chỉ tìm ra giải pháp tối ưu mà còn giảm thiểu thời gian tính toán, giúp tiết kiệm nguồn lực cho các trường đại học.

IV. Ứng dụng thực tiễn của ACO trong lập thời khóa biểu

Phương pháp ACO đã được áp dụng thành công tại nhiều trường đại học, giúp cải thiện quy trình lập thời khóa biểu. Các trường đã ghi nhận sự tăng cường trong việc quản lý lịch học và sự hài lòng của sinh viên. Nghiên cứu này sẽ trình bày một số ví dụ cụ thể về ứng dụng ACO trong thực tiễn.

4.1. Các trường đại học áp dụng ACO

Nhiều trường đại học trên thế giới đã áp dụng ACO để lập thời khóa biểu, từ đó cải thiện hiệu quả quản lý lịch học. Các trường này đã ghi nhận sự giảm thiểu xung đột trong lịch học và tăng cường sự hài lòng của sinh viên.

4.2. Kết quả nghiên cứu về hiệu quả của ACO

Kết quả nghiên cứu cho thấy ACO không chỉ giúp lập thời khóa biểu hiệu quả mà còn giảm thiểu thời gian và công sức cần thiết. Các trường đã có thể tối ưu hóa lịch học, từ đó nâng cao chất lượng giáo dục.

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 lập thời khóa biểu cho trường đại học. 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ông nghệ và thuật toán. Nghiên cứu này sẽ đề xuất một số hướng đi mới cho việc áp dụng ACO trong các lĩnh vực khác.

5.1. Hướng phát triển của ACO trong giáo dục

ACO có thể được áp dụng không chỉ trong lập thời khóa biểu mà còn trong nhiều lĩnh vực khác của giáo dục như quản lý khóa học và phân bổ tài nguyên. Điều này sẽ giúp tối ưu hóa quy trình giáo dục và nâng cao chất lượng học tập.

5.2. Tiềm năng mở rộng của ACO ra ngoài giáo dục

Phương pháp ACO có thể được mở rộng ra nhiều lĩnh vực khác như logistics, quản lý sản xuất và quy hoạch đô thị. Sự linh hoạt và hiệu quả của ACO sẽ giúp giải quyết nhiều bài toán phức tạp trong các lĩnh vực này.

Nội dung chính

Tổng quan nghiên cứu

Bài toán lập thời khóa biểu cho trường đại học theo học chế tín chỉ là một thách thức quản lý phức tạp thuộc lớp bài toán tối ưu tổ hợp NP-khó. Trong thực tế quản lý giáo dục, việc phân bổ lịch học thủ công thường dẫn đến xung đột tài nguyên nghiêm trọng. Khi quy mô trường học mở rộng lên 40 lớp học với 8 môn học mỗi lớp trong 25 tiết học mỗi tuần, không gian tìm kiếm trạng thái bùng nổ lên đến con số xấp xỉ 8 mũ 1000 trường hợp, khiến các thuật toán duyệt toàn bộ hoàn toàn bất khả thi về mặt thời gian và bộ nhớ tính toán.

Luận văn thạc sĩ chuyên ngành Hệ thống Thông tin của tác giả Nguyễn Văn Tuân, dưới sự hướng dẫn khoa học của PGS.TS Hoàng Xuân Huấn tại Trường Đại học Công nghệ – Đại học Quốc gia Hà Nội hoàn thành vào năm 2015, tập trung nghiên cứu ứng dụng phương pháp tối ưu đàn kiến vào bài toán thời khóa biểu đại học. Mục tiêu trọng tâm của đề tài là xây dựng mô hình thuật toán tối ưu hóa bầy đàn cải tiến, giải quyết triệt để bài toán xếp lịch học thỏa mãn toàn bộ các ràng buộc ngặt về phòng học và giảng viên, đồng thời tối thiểu hóa các ràng buộc mềm trong khung thời gian 45 tiết học chuẩn mỗi tuần.

Nghiên cứu sử dụng tập dữ liệu kiểm chuẩn quốc tế được công bố rộng rãi trên hệ thống nghiên cứu tối ưu hóa trường đại học để đánh giá thực nghiệm. Ý nghĩa khoa học và thực tiễn của công trình thể hiện ở việc nâng cao năng lực tự động hóa quy trình quản lý giáo dục, giảm thiểu trên 75% các vi phạm ràng buộc mềm về phân bố lịch học cho sinh viên, tạo tiền đề vững chắc cho việc phát triển các phần mềm xếp khóa học thông minh tại các cơ sở giáo dục đại học ở Việt Nam.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Nghiên cứu được xây dựng dựa trên nền tảng lý thuyết tối ưu hóa bầy đàn metaheuristic do Marco Dorigo khởi xướng từ năm 1991, mô phỏng cơ chế tìm đường đi ngắn nhất của đàn kiến tự nhiên thông qua giao tiếp gián tiếp bằng nồng độ vết mùi pheromone. Trong mô hình này, mỗi con kiến nhân tạo đóng vai trò một tác tử độc lập, từng bước xây dựng giải pháp dựa trên sự kết hợp giữa nồng độ vết mùi tích lũy và thông tin heuristic cục bộ.

Khung lý thuyết của luận văn phân tích sâu các biến thể thuật toán đàn kiến tiêu biểu, bao gồm Hệ thống đàn kiến cơ bản, Hệ kiến Ant Colony System và đặc biệt là Hệ kiến Max-Min do Stützle và Hoos đề xuất năm 2000. Để khắc phục hiện tượng suy giảm khả năng khám phá không gian nghiệm khi nồng độ mùi bị giới hạn quá chặt, nghiên cứu áp dụng quy tắc cập nhật mùi Hệ kiến Max-Min trơn do PGS.TS Hoàng Xuân Huấn và cộng sự đề xuất năm 2011. Khái niệm cốt lõi bao gồm ma trận nồng độ mùi gắn trên không gian kết hợp giữa tập hợp môn học và tập hợp tiết học, xác suất chuyển trạng thái ngẫu nhiên theo tỷ lệ, và hệ số bay hơi mùi với giá trị chuẩn 0.30 nhằm kiểm soát cân bằng giữa khai thác nghiệm tốt và khám phá vùng tìm kiếm mới.

Phương pháp nghiên cứu

Nghiên cứu sử dụng nguồn dữ liệu kiểm chuẩn quốc tế chuẩn hóa cho bài toán thời khóa biểu đại học từ viện nghiên cứu IRIDIA, được phân chia thành 3 nhóm kích cỡ mẫu thử nghiệm điển hình: bộ dữ liệu nhỏ gồm 100 môn học và 80 sinh viên; bộ dữ liệu vừa gồm 400 môn học và 200 sinh viên; bộ dữ liệu lớn gồm 400 môn học, 400 sinh viên cùng 10 đặc trưng phòng học chuyên dụng. Phương pháp chọn mẫu tập trung vào các trường hợp kiểm thử chuẩn hóa có tính cạnh tranh cao nhằm đảm bảo tính khách quan và khả năng so sánh quốc tế.

Lý do lựa chọn phương pháp phân tích thực nghiệm mô phỏng là vì bài toán có tính chất NP-khó, không thể giải chính xác bằng phương pháp giải tích truyền thống. Quy trình phân tích kết hợp cấu trúc đồ thị hai phía với thuật toán ghép cặp cực đại để gán phòng học tối ưu cho từng tiết học, đồng thời tích hợp thủ tục tìm kiếm cục bộ dựa trên 2 phép dịch chuyển cơ bản: chuyển môn học sang tiết khác và hoán đổi tiết học giữa hai môn. Toàn bộ chương trình được lập trình bằng ngôn ngữ C++ và tiến hành đo lường độc lập qua 10 lần chạy trên cùng một cấu hình phần cứng máy tính để thu thập dữ liệu thống kê về độ hội tụ và số lượng vi phạm.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

Thực nghiệm so sánh giữa thuật toán Hệ kiến Max-Min trơn và Hệ kiến Max-Min truyền thống trên các bộ dữ liệu chuẩn đã ghi nhận 3 phát hiện khoa học quan trọng:

Thứ nhất, đối với bộ dữ liệu kích cỡ nhỏ gồm 100 môn học và 5 phòng học qua 500 bước lặp, thuật toán Hệ kiến Max-Min trơn đạt chất lượng vượt trội khi tìm ra phương án tối ưu với chỉ 1 vi phạm ràng buộc mềm và giá trị trung bình qua 10 lần chạy là 3.2 vi phạm. Trong khi đó, thuật toán Hệ kiến Max-Min truyền thống chỉ đạt kết quả tốt nhất là 4 vi phạm và giá trị trung bình lên tới 13.6 vi phạm, tương ứng mức giảm vi phạm trung bình của thuật toán cải tiến lên đến 76.47%.

Thứ hai, ở bộ dữ liệu kích cỡ lớn với 400 môn học, 10 phòng học và 400 sinh viên qua 10000 bước lặp, thuật toán Hệ kiến Max-Min truyền thống hoàn toàn thất bại trong việc tìm kiếm lời giải hợp lệ, đạt tỷ lệ 0% lời giải khả thi do vi phạm các ràng buộc ngặt. Ngược lại, thuật toán Hệ kiến Max-Min trơn giải quyết thành công 100% các ràng buộc ngặt, đạt lời giải tốt nhất với 917 vi phạm mềm và giá trị trung bình ổn định ở mức 925 vi phạm qua 10 lần chạy thử nghiệm.

Thứ ba, việc thiết lập tỷ lệ nồng độ mùi tối đa gấp 1000 lần nồng độ mùi tối thiểu trong Hệ kiến Max-Min trơn đã loại bỏ hoàn toàn các phép toán cắt ngưỡng phức tạp, giúp tốc độ thực thi của thuật toán nhanh hơn và không bị sa lầy vào các cực trị địa phương.

Thảo luận kết quả

Nguyên nhân chính dẫn đến sự vượt trội của Hệ kiến Max-Min trơn là cơ chế giảm dần đều nồng độ vết mùi trên các cạnh không thuộc phương án tốt nhất về ngưỡng tối thiểu, thay vì hạ đột ngột như Hệ kiến Max-Min truyền thống. Điều này giúp đàn kiến duy trì khả năng khám phá các phương án tiềm năng mới trong suốt quá trình tiến hóa. Khi kết hợp với thủ tục tìm kiếm cục bộ, thuật toán nhanh chóng tối ưu hóa lịch học mà không làm mất đi tính đa dạng của quần thể nghiệm.

Các phát hiện này hoàn toàn tương đồng với các kết luận lý thuyết của nhiều công trình nghiên cứu metaheuristic quốc tế khi ứng dụng trên bài toán người chào hàng. Về mặt trình bày dữ liệu, các kết quả so sánh qua 10 lần lặp có thể được biểu diễn trực quan qua bảng tổng hợp phương sai và biểu đồ đường thể hiện tốc độ hội tụ qua từng bước lặp từ 500 đến 10000 thế hệ, minh họa rõ nét độ dốc suy giảm vi phạm của thuật toán cải tiến so với đường đi ngang bế tắc của thuật toán truyền thống trên các tập dữ liệu lớn.

Đề xuất và khuyến nghị

Dựa trên kết quả nghiên cứu thực nghiệm, luận văn đề xuất 4 giải pháp cụ thể nhằm ứng dụng hiệu quả thuật toán tối ưu đàn kiến vào thực tiễn quản lý giáo dục:

Thứ nhất, chuẩn hóa toàn diện cơ sở dữ liệu học phần và phòng học: Phòng Đào tạo tại các trường đại học cần chủ trì rà soát, số hóa 100% dữ liệu về sức chứa phòng, trang thiết bị chuyên dụng và danh sách sinh viên đăng ký theo từng học kỳ. Mục tiêu hoàn thành trong 3 tháng đầu của năm học, giúp loại bỏ 95% các lỗi xung đột dữ liệu đầu vào.

Thứ hai, tích hợp module thuật toán Hệ kiến Max-Min trơn vào phần mềm quản lý đào tạo: Trung tâm Công nghệ Thông tin triển khai đóng gói thuật toán thành dịch vụ web hoặc module tích hợp trong thời gian 6 tháng, đặt mục tiêu rút ngắn thời gian xếp thời khóa biểu toàn trường từ 14 ngày làm việc xuống dưới 2 giờ chạy máy tự động.

Thứ ba, thiết lập ma trận trọng số linh hoạt cho các ràng buộc mềm: Ban Giám hiệu phối hợp với các Khoa chuyên môn định kỳ cập nhật bộ quy tắc ưu tiên lịch học mỗi học kỳ, hướng tới giảm thiểu tỷ lệ sinh viên phải học 1 môn đơn lẻ trong ngày hoặc học 3 ca liên tiếp xuống mức dưới 2% tổng số sinh viên toàn trường.

Thứ tư, nâng cấp hạ tầng tính toán song song: Đơn vị phụ trách hạ tầng kỹ thuật thực hiện phân bổ máy chủ tính toán đa luồng trong vòng 12 tháng, đảm bảo khả năng mở rộng thuật toán xử lý trơn tru quy mô trên 10000 sinh viên và hơn 1500 lớp học phần mà không xảy ra nghẽn tài nguyên bộ nhớ.

Đối tượng nên tham khảo luận văn

Luận văn mang lại giá trị thực tiễn và học thuật sâu sắc cho 4 nhóm đối tượng chính:

Nhóm thứ nhất là cán bộ quản lý đào tạo và chuyên viên khảo thí tại các trường đại học, cao đẳng: Nghiên cứu cung cấp góc nhìn toàn diện về cách mô hình hóa các ràng buộc phức tạp của hệ thống tín chỉ, giúp xây dựng quy trình xếp lịch khoa học cho hơn 500 lớp học phần mỗi học kỳ.

Nhóm thứ hai là kỹ sư phần mềm và các doanh nghiệp công nghệ giáo dục: Tài liệu đóng vai trò bản đặc tả kỹ thuật chi tiết về cấu trúc đồ thị và thuật toán ghép cặp cực đại, làm cơ sở xây dựng các tính năng tự động hóa xếp lịch trong các hệ thống phần mềm quản trị đại học.

Nhóm thứ ba là học viên cao học và nghiên cứu sinh chuyên ngành Khoa học Máy tính, Hệ thống Thông tin: Luận văn cung cấp khung phương pháp luận chuẩn mực về tối ưu hóa tổ hợp, kỹ thuật xử lý bài toán NP-khó và cách thức tổ chức thực nghiệm đánh giá thuật toán.

Nhóm thứ tư là giảng viên và nhà nghiên cứu trong lĩnh vực Trí tuệ Nhân tạo: Công trình là tài liệu tham khảo giá trị cho các bài giảng chuyên đề về thuật toán mô phỏng tự nhiên, giải thuật bầy đàn và phương pháp tối ưu hóa metaheuristic.

Câu hỏi thường gặp

Bài toán thời khóa biểu đại học theo tín chỉ khác bài toán phổ thông ở điểm nào?

Điểm khác biệt cốt lõi nằm ở tính cá nhân hóa lịch học của sinh viên. Ở bậc đại học, sinh viên tự do đăng ký các môn học khác nhau dẫn đến nguy cơ trùng lịch học rất cao, trong khi học sinh phổ thông học theo lớp cố định. Ngoài ra, bài toán đại học phải tối ưu hóa việc phân bổ phòng học theo 10 đặc trưng chuyên dụng và sức chứa cụ thể, khiến độ phức tạp tính toán tăng vọt.

Vì sao thuật toán Hệ kiến Max-Min trơn lại vượt trội hơn Hệ kiến Max-Min truyền thống trên dữ liệu lớn?

Trên tập dữ liệu lớn với 400 môn học, Hệ kiến Max-Min truyền thống dễ bị tắc nghẽn do nồng độ vết mùi trên các cạnh không tốt giảm quá nhanh về cận dưới. Thuật toán Hệ kiến Max-Min trơn duy trì tốc độ suy giảm mùi chậm và mượt mà hơn, giúp đàn kiến bảo tồn khả năng khám phá không gian nghiệm mới và tránh bị bẫy tại các cực trị địa phương.

Thuật toán ghép cặp cực đại đóng vai trò gì trong mô hình nghiên cứu?

Thuật toán đàn kiến chịu trách nhiệm phân bổ các môn học vào 45 tiết học trong tuần. Sau đó, thuật toán ghép cặp cực đại trên đồ thị hai phía được kích hoạt để gán chính xác từng môn học trong cùng một tiết vào các phòng học đáp ứng đầy đủ yêu cầu về sức chứa và tính năng chuyên dụng, đảm bảo tính khả thi tuyệt đối của lịch học.

Cần cấu hình phần cứng như thế nào để triển khai thuật toán này trong thực tế?

Thực nghiệm cho thấy thuật toán hoạt động hiệu quả ngay trên cấu hình máy tính cá nhân tiêu chuẩn với chip vi xử lý 2.00GHz và bộ nhớ trong 4GB RAM. Khi triển khai thực tế cho quy mô toàn trường đại học, hệ thống chỉ cần máy chủ tầm trung hỗ trợ xử lý đa luồng là có thể hoàn tất tính toán trong vài chục phút.

Việc thiết lập tỷ lệ nồng độ mùi ảnh hưởng như thế nào đến kết quả thuật toán?

Quy tắc Hệ kiến Max-Min trơn thiết lập nồng độ mùi tối đa bằng 1000 lần nồng độ mùi tối thiểu. Tỷ lệ này tạo ra độ chênh lệch vừa đủ để định hướng đàn kiến tập trung vào các lộ trình chất lượng cao, đồng thời vẫn giữ lại xác suất nhất định để kiến thử nghiệm các nhánh phân bổ mới, đảm bảo tính cân bằng tối ưu trong suốt quá trình tìm kiếm.

Kết luận

• Đóng góp lý thuyết: Nghiên cứu đã hệ thống hóa toàn diện phương pháp tối ưu hóa đàn kiến và ứng dụng thành công quy tắc cập nhật mùi Hệ kiến Max-Min trơn vào việc giải quyết bài toán thời khóa biểu đại học hệ tín chỉ.

• Đóng góp thực nghiệm: Đã chứng minh bằng thực nghiệm sự vượt trội của Hệ kiến Max-Min trơn so với Hệ kiến Max-Min truyền thống, đặc biệt giải quyết thành công bộ dữ liệu lớn gồm 400 môn học và 400 sinh viên nơi thuật toán cũ hoàn toàn thất bại.

• Đóng góp giải pháp kỹ thuật: Xây dựng hoàn chỉnh mô hình phối hợp giữa đồ thị không gian trạng thái, thuật toán ghép cặp cực đại cho phân bổ phòng học và thủ tục tìm kiếm cục bộ 2 phép dịch chuyển.

• Tối ưu hóa tham số: Xác định cấu hình tham số thực nghiệm chuẩn xác với hệ số bay hơi 0.30 và tỷ lệ nồng độ mùi 1000 lần, tạo cơ sở tham chiếu tin cậy cho các nghiên cứu tiếp theo.

• Kế hoạch phát triển: Định hướng trong 12 tháng tới tiếp tục hoàn thiện mã nguồn, phát triển giao diện người dùng trực quan để chuyển giao thành công cụ xếp lịch thực tế cho các trường đại học tại Việt Nam.

Các nhà quản lý giáo dục, kỹ sư phần mềm và nhà nghiên cứu quan tâm có thể khai thác trực tiếp mô hình thuật toán này để nâng cao hiệu quả quản trị đào tạo và tự động hóa quy trình vận hành học thuật ngay hôm nay.

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

chương 1 luận văn đã được tìm hiểu về bài toán UCTP và một số cách tiếp cận để giải bài toán, chương này luận văn sẽ tìm hiểu phương pháp tối ưu đàn kiến để giải bài toán trên. Từ kiến tự nh ên ến kiến nhân t o Những hình ảnh nhận thức đặc biệt của đàn kiến chỉ đơn giản là sự phát triển và hoàn toàn mò mẫm. Trong thực tế, một điều quan trọng trong nghiên cứu về loài kiến là hành vi liên lạc giữa các con kiến hoặc giữa các cá nhân với môi trường, được dựa trên việc sử d ng các sản ph m hóa chất của các loài kiến. Các hóa chất đó được gọi là mùi (vết mùi).

Kiến tự nhiên hi tìm đường đi, đàn kiến trao đ i thông tin gián tiếp và hoạt động theo phương thức tự t chức. Phương thức này tuy đơn giản nhưng đã giúp cho đàn kiến có thể thực hiện được những công việc phức tạp vượt xa khả năng của t ng con kiến, đặc biệt là khả năng tìm đường đi ngắn nhất t t đến nguồn thức ăn (xem hình 2. iến chịu ảnh hư ng của các vết mùi của các con kiến khác chính là ý tư ng thiết kế thuật toán ACO. Thể hiện hành vi của mỗi con kiến trong tự nhiên Để làm được điều đó, trên đường đi, mỗi con kiến để lại vết m i ng để đánh dấu đường đi.

ằng cách cảm nhận vết mùi, con kiến có thể lần theo đường đi đến 8 nguồn thức ăn được các con kiến khác khám phá theo phương thức chọn ngẫu nhiên, có định hướng theo nồng độ vết mùi. Con kiến chịu ảnh hư ng của các vết mùi của các con kiến khác, đây là ý tư ng chính để thiết kế thuật toán ACO. Thí nghiệm trên cây cầu : Có nhiều thực nghiệm nghiên cứu về hành vi để lại vết m i và đi theo vết mùi của loài kiến. Thực nghiệm, được thiết kế b i Deneubourg và các đồng nghiệp [15] dùng một chiếc cầu đôi nối t t kiến tới nguồn thức ăn, như minh họa trong hình 2.

Họ đã thực nghiệm với tỉ lệ độ ài đường giữa hai nhánh khác nhau của chiếc cầu đôi, trong đó là độ dài của nhánh dài còn là độ dài của nhánh ngắn. Trong thực nghiệm thứ nhất, chiếc cầu đôi có hai nhánh bằng nhau ( hình 2. an đầu, kiến lựa chọn đường đi một cách tự o đi t t đến nguồn thức ăn, cả hai nhánh đều có kiến đi, nhưng sau một thời gian các con kiến này tập trung đi theo cùng một nhánh. Kết quả có thể được giải thích như sau an đầu không có vết mùi nào trên cả hai nhánh, o đó kiến lựa chọn nhánh bất k với xác suất như nhau.

Một cách ngẫu nhiên, sẽ có một nhánh có số lượng kiến lựa chọn nhiều hơn nhánh kia. Do kiến để lại vết mùi trong quá trình di chuyển, nhánh có nhiều kiến lựa chọn sẽ có nồng độ mùi lớn hơn nồng độ mùi của nhánhcòn lại. Nồng độ mùi trên cạnh lớn hơn sẽ ngày càng lớn hơn vì ngày càng có nhiều kiến lựa chọn. Cuối cùng, hầu như tất cả các kiến sẽ tập trung trên cùng một nhánh.Thực nghiệm này cho thấylà sự tương tác c c bộ giữa các con kiến với thông tin gián tiếp là vết m i để lại cho ph p điều chỉnh hoạt động vĩ mô của đàn kiến.2: Thực nghiệm cây cầu đôi (a) ai nhánh có độ dài bằng nhau.

(b) Hai nhánh có độ dài khác nhau. 9 Trong thực nghiệm thứ hai (xem hình 2.2 b), độ dài của nhánh dài gấp đôi độ dài nhánh ngắn (tỉ lệ ). Trong trường hợp này, sau một thời gian tất cả các con kiến đều chọn đoạn đường ngắn hơn. ũng như trong thực nghiệm thứ nhất, ban đầu đàn kiến lựa chọn hai nhánh đi như nhau, một nửa số kiến đi theo nhánh ngắn và một nửa đi theo nhánh ài (mặc dù trên thực tế, do tính ngẫu nhiên có thể một nhánh nào đó được nhiều kiến lựa chọn hơn nhánh kia).

Nhưng thực nghiệm này có điểm khác biệt quan trọng với thực nghiệm thứ nhất: Những kiến lựa chọn đi theo nhánh ngắn sẽ nhanh chóng quay tr lại t và khi phải lựa chọn giữa nhánh ngắn và nhánh dài, kiến sẽ thấy nồng độ mùi trên nhánh ngắn cao hơn nồng độ m i trên nhánh ài, o đó sẽ ưu tiên lựa chọn đi theo nhánh ngắn hơn. Tuy nhiên, trong thời gian đầu không phải tất cả các kiến đều đi theo nhánh ngắn hơn.Phải mất một khoảng thời gian tiếp theo nữa bầy kiến mới lựa chọn đi theo nhánh ngắn. Điều này minh chứng bầy kiến đã sử d ng phương thức thăm , tìm đường mới. Một điểm thú vị nữa là quan sát xem sẽ xảy ra điều gì khi quá trình tìm kiếm đang hội t , lại xuất hiện một đường mới t t đến nguồn thức ăn.

Việc này được thực nghiệm như sau an đầu t t đến nguồn thức ăn chỉ có một nhánh dài và sau 30 phút, thêm một nhánh ngắn (xem hình 2. Trong trường hợp này, nhánh ngắn thường không được kiến chọn mà chúng tập trung đi trên nhánh ài. Điều này có thể giải thích như sau nồng độ vết mùi trên cạnh dài cao và sự bay hơi của vết mùi diễn ra chậm nên đại đa số các con kiến vẫn lựa chọn nhánh dài (có nồng độ vết mùi cao).Hành vi này tiếp t c được củng cố kiến chọn đi theo nhánh ài, ngay cả khi có một nhánh ngắn xuất hiện. Việc bay hơi vết m i là cơ chế tiện lợi cho việc tìm đường mới, nghĩa là việc bay hơi có thể giúp kiến uên đi đường đi tối ưu địa phương đã được tìm thấy trước đây để tìm khám phá đường đi mới, tốt hơn.

Thí nghiệm b xung ( an đầu chỉ có một nhánh và sau 30 phút thêm nhánh ngắn hơn) 10 2. Kiến nhân t o (Artificial Ant) Thực nghiệm cây cầu đôi cho thấy đàn kiến tự nhiên có thể sử d ng luật di chuyển theo xác suất, dựa trên thông tin địa phương để tìm được đường đi ngắn nhất giữa hai địa điểm. Vết mùi của đàn kiến cho ph p liên tư ng tới cách học tăng cường (reinforcement learning) trong bài toán chọn tác động tối ưu[2], gợi m mô hình mô phỏng cho bài toán tìm đường đi ngắn nhất giữa hai nút (tương ứng là t và nguồn thức ăn) trên đồ thị, trong đó các tác tử (agent) là đàn kiến nhân tạo. Tuy nhiên, trong các bài toán ứng d ng các đồ thị thường phức tạp hơn.T mỗi đỉnh có thể có nhiều cạnh, nên nếu mô phỏng thực sự hành vi của đàn kiến tự nhiên nhiều con kiến sẽ đi lu n qu n và o đó hiệu quả thuật toán sẽ rất kém.

Vì vậy, người ta dùng kỹ thuật đa tác tử (multiagent) mô phỏng đàn kiến nhân tạo, trong đó mỗi con kiến nhân tạo có khả năng nhiều hơn so với kiến tự nhiên. Kiến nhân tạo (về sau trong luận án ta sẽ gọi đơn giản là kiến) có bộ nhớ riêng, có khả năng ghi nhớ các đỉnh đã thăm trong hành trình và tính được độ ài đường đi nó chọn. Ngoài ra, kiến có thể trao đ i thông tin với nhau, thực hiện tính toán cần thiết, cập nhật m i… Sử d ng mô hình kiến nhân tạo này, Dorigo (1991) [15] đã xây ựng thuật toán Hệ kiến (AS) giải bài toán người chào hàng. Hiệu quả của thuật toán so với các phương pháp mô phỏng tự nhiên khác như SA và GA đã được kiểm chứng bằng thực nghiệm.

Thuật toán này về sau được phát triển và có nhiều ứng d ng phong phú, được gọi chung làphương pháp A O. Phương h ố ưu n ến Tối ưu đàn kiến (Ant Colony Optimization - ACO) là một phương pháp metaheuristic được đề xuất b i Dorigo vào năm 1991[14] dựa trên ý tư ng mô phỏng cách tìm đường đi t t tới nguồn thức ăn và ngược lại của các con kiến tự nhiên để giải gần đúng bài toán TƯT NP-khó. Trên đường đi của mình các con kiến thực để lại một vết hóa chất được gọi là vết mùi (pheromone trail), đặc điểm sinh hóa học của vết mùi này là có khả năng ứ đọng, bay hơi và là phương tiện giao tiếp báo cho các con kiến khác thông tin về đường đi đó một cách gián tiếp. Các con kiến sẽ lựa chọn đường đi nào tồn đọng lượng m i hay có cường độ vết m i lớn nhất tại thời điểm lựa chọn để đi, nhờ cách giao tiếp mang tính gián tiếp và cộng đồng này mà đàn kiến trong tự nhiên tìm được đường đi ngắn nhất trong uá trình tìm thức ăn mang về t và ngược lại.

Sử d ng mô hình kiến nhân tạo này Dorigo (1991) [4] đã xây ựng thuật toán hệ kiến (AS) giải bài toán người chào hàng. Thuật toán này đã được chứng minh tính hiệu quả thông qua thực nghiệm so với 11 các mô phỏng tự nhiên khác như SA (mô phỏng luyện kim) và GA (giải thuật di truyền). Thuật toán này về sau được phát triển và có nhiều áp d ng phong phú trong thực tế, được gọi chung là phương pháp A O. Theo ý tư ng này, các thuật toán ACO sử d ng thông tin heuristic kết hợp thông tin học tăng cường qua các vết mùi của các con kiến nhân tạo (artificial ant) để giải các bài toán tối ưu t hợp khó bằng cách đưa về bài toán tìm đường đi tối ưu trên đồ thị cấu trúc tương ứng được xây dựng t đặc điểm của t ng bài toán c thể.

Thuật toán A O đầu tiên là hệ kiến (Ant System - AS) giải bài toán Người chào hàng TSP, đến nay các thuật toán A O đã áp ng một cách phong phú để giải nhiều bài toán tối ưu t hợp khác nhau và hiệu uả n i trội của nó đã được chứng tỏ bằng thực nghiệm. Nhờ những thành uả to lớn trong việc ứng ng phương pháp tối ưu đàn kiến vào giải các bài toán tối ưu t hợp khó m ra một lĩnh vực nghiên cứu và ứng ng mới thu hút được sự uan tâm của đông đảo các nhà khoa học trên thế giới, Dorigo đã được ội đồng châu u trao giải thư ng đặc biệt Marie urie (Marie Curie Excellence Award) trao hai năm một lần giành cho năm nhà khoa học có nhiều đóng góp cho nền khoa học và công nghệ châu u vào ngày 05 11 2003.