Nghiên cứu phương pháp ACO cho bài toán thời khóa biểu tại trường đại học

Luận văn thạc sĩ nghiên cứu phương pháp aco và bài toán thời khóa 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 trong lĩnh vực toá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 Trong Tối Ưu Hóa Thời Khóa Biểu Đạ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
• LỜI CAM ĐOAN
• 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.2. Bài toán lập thời khóa biểu cho trường phổ thông (School timetabling)
• 1.3. Bài toán xếp lịch thi (Examination timetabling)
• 1.4. Bài toán lập thời khóa biểu cho trường đại học (University timetabling)
• 1.5. 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
• 2.1. Lịch sử phát triển
• 2.2. Các thuật toán ACO
• 2.3. Một số nguyên tắc ứng dụng ACO
• 3. CHƯƠNG 3: ÁP DỤNG TỐI ƯU ĐÀN KIẾN CHO BÀI TOÁN UCTP
• 3.1. Cách thức chung để áp dụng tối ưu đàn kiến giải bài toán UCTP
• 3.2. 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
• 4. CHƯƠNG 4: DỮ LIỆU THỰC NGHIỆM VÀ ĐÁNH GIÁ
• 4.1. Bộ dữ liệu chuẩn cho bài toán UCTP
• 4.2. Kết quả thực nghiệm
• 4.3. Đá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
• TÀI LIỆU THAM KHẢO

Tóm tắt

I. Giới thiệu về bài toán tối ưu hóa thời khóa biểu

Bài toán lập thời khóa biểu là một trong những thách thức lớn trong quản lý giáo dục. Tối ưu hóa thời khóa biểu không chỉ đơn thuần là việc sắp xếp các môn học mà còn phải đảm bảo rằng tất cả các ràng buộc như thời gian, phòng học, và giáo viên đều được thỏa mãn. Bài toán này thuộc lớp NP-khó, điều này có nghĩa là không có giải pháp tối ưu nào có thể tìm thấy trong thời gian hợp lý bằng các phương pháp truyền thống. Do đó, việc áp dụng các phương pháp tối ưu hóa hiện đại như phương pháp ACO trở nên cần thiết. Quản lý thời gian và lập lịch học là những yếu tố quan trọng trong việc nâng cao chất lượng giáo dục. Việc sử dụng thuật toán ACO cho phép tìm ra các giải pháp gần tối ưu cho bài toán này, giúp tiết kiệm thời gian và nguồn lực cho các cơ sở giáo dục.

II. Phương pháp ACO và các thuật toán liên quan

Phương pháp tối ưu hóa đàn kiến (ACO) được phát triển bởi Marco Dorigo vào những năm 1990. ACO là một thuật toán mô phỏng hành vi của đàn kiến trong tự nhiên, nơi các con kiến tìm kiếm thức ăn và giao tiếp thông qua pheromone. Thuật toán ACO sử dụng các quy tắc cập nhật pheromone để hướng dẫn quá trình tìm kiếm. Trong bối cảnh tối ưu hóa lịch học, ACO có thể được áp dụng để giải quyết bài toán lập lịch học cho các trường đại học. Các hệ kiến như Max-Min Ant System (MMAS) và Smooth-Max Min Ant System (SMMAS) đã được nghiên cứu và áp dụng để cải thiện hiệu suất của thuật toán. Kết quả thực nghiệm cho thấy rằng SMMAS có hiệu quả hơn MMAS trong việc tìm kiếm giải pháp cho bài toán tối ưu hóa lịch trình.

III. Ứng dụng của ACO trong bài toán lập thời khóa biểu đại học

Việc áp dụng phương pháp ACO vào bài toán lập thời khóa biểu đại học đã cho thấy những kết quả khả quan. Bằng cách xây dựng đồ thị cấu trúc cho bài toán University Course Timetabling Problem (UCTP), 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à phòng học cho các môn học. Các ràng buộc như số lượng sinh viên, phòng học, và thời gian học đều được xem xét kỹ lưỡng. Kết quả thực nghiệm cho thấy rằng ACO không chỉ giúp giảm thiểu số vi phạm các ràng buộc mềm mà còn tối ưu hóa việc sử dụng nguồn lực. Điều này chứng tỏ rằng tối ưu hóa nguồn lực là một trong những lợi ích lớn nhất của việc áp dụng ACO trong giáo dục.

IV. Đánh giá và triển vọng của phương pháp ACO

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 tối ưu hóa thời khóa biểu. Tuy nhiên, vẫn còn nhiều thách thức cần phải vượt qua. Việc cải tiến các thuật toán ACO để xử lý các bài toán phức tạp hơn là một trong những hướng nghiên cứu tiềm năng. Các nghiên cứu tiếp theo có thể tập trung vào việc phát triển các thuật toán lai kết hợp ACO với các phương pháp tối ưu hóa khác như thuật toán di truyền hay thuật toán tìm kiếm địa phương. Điều này không chỉ giúp cải thiện hiệu suất mà còn mở rộng khả năng ứng dụng của ACO trong nhiều lĩnh vực khác nhau, từ giáo dục đến sản xuất và logistics.

Nội dung chính

Tổng quan nghiên cứu

Bài toán lập thời khóa biểu (TKB) là một trong những vấn đề tối ưu tổ hợp phức tạp, thuộc lớp NP-khó, được nhiều tổ chức giáo dục trên thế giới quan tâm do tính ứng dụng cao và độ khó trong việc đáp ứng các ràng buộc đa dạng. Ở Việt Nam, đặc biệt với mô hình đào tạo đại học theo hệ tín chỉ, bài toán này càng trở nên cấp thiết nhưng chưa được nghiên cứu sâu và chưa có phần mềm ứng dụng hiệu quả. Mục tiêu của luận văn là nghiên cứu và áp dụng phương pháp tối ưu hóa đàn kiến (Ant Colony Optimization - ACO) với quy tắc cập nhật mùi Smooth-Max Min Ant System (SMMAS) để giải bài toán lập thời khóa biểu cho trường đại học theo hệ tín chỉ. Phạm vi nghiên cứu tập trung vào bài toán mẫu chuẩn UCTP (University Course Timetabling Problem) với dữ liệu thực nghiệm từ các bộ dữ liệu chuẩn trên internet, thực hiện tại Trường Đại học Công nghệ, Đại học Quốc gia Hà Nội trong năm 2015. Ý nghĩa nghiên cứu thể hiện qua việc cải thiện hiệu quả giải bài toán TKB, giảm số vi phạm ràng buộc mềm và tăng khả năng tìm kiếm lời giải tối ưu so với các phương pháp truyền thống và các thuật toán ACO trước đó như Max-Min Ant System (MMAS). Kết quả thực nghiệm cho thấy SMMAS vượt trội hơn MMAS về chất lượng lời giải và thời gian chạy, mở ra hướng phát triển phần mềm ứng dụng cho các trường đại học tại Việt Nam.

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

Khung lý thuyết áp dụng

Luận văn dựa trên hai lý thuyết chính:

1. Bài toán lập thời khóa biểu (UCTP): Là bài toán tối ưu tổ hợp, yêu cầu phân bổ các môn học vào các tiết học và phòng học sao cho thỏa mãn các ràng buộc cứng (không trùng lịch, phòng đủ sức chứa, điều kiện phòng học) và tối ưu hóa các ràng buộc mềm (giảm số sinh viên học tiết cuối cùng, hạn chế học nhiều môn liên tiếp).
2. Phương pháp tối ưu hóa đàn kiến (ACO): Thuật toán metaheuristic mô phỏng hành vi tìm đường của đàn kiến tự nhiên dựa trên vết mùi pheromone, kết hợp thông tin heuristic và học tăng cường để tìm lời giải gần tối ưu cho các bài toán NP-khó.
   Các khái niệm chuyên ngành quan trọng bao gồm:

• Vết mùi (pheromone trail): Thông tin tích lũy trên các cạnh đồ thị, ảnh hưởng đến xác suất lựa chọn đường đi.
• Quy tắc cập nhật mùi: Chiến lược điều chỉnh lượng pheromone, quyết định hiệu quả và khả năng hội tụ của thuật toán.
• Hệ kiến MMAS (Max-Min Ant System): Quy tắc cập nhật mùi giới hạn trong khoảng [min, max], tập trung khai thác lời giải tốt nhất.
• Hệ kiến SMMAS (Smooth-Max Min Ant System): Quy tắc cập nhật mùi trơn, giảm tốc độ bay hơi pheromone trên các cạnh không thuộc lời giải tốt, tăng khả năng khám phá không gian tìm kiếm.
• Tìm kiếm địa phương (Local Search): Phương pháp cải tiến lời giải bằng các phép dịch chuyển và tráo đổi trong không gian lân cận.

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

Nguồn dữ liệu sử dụng là các bộ dữ liệu chuẩn UCTP lấy từ trang web quốc tế, bao gồm các thông tin về số môn học, số phòng, số sinh viên, ma trận tham dự sinh viên và ma trận chức năng phòng học. Các bộ dữ liệu được phân loại theo kích cỡ nhỏ, vừa và lớn với số môn học từ 100 đến 400, số phòng từ 5 đến 10, số tiết học 45 tiết/tuần.

Phương pháp phân tích bao gồm:

• Xây dựng đồ thị cấu trúc bài toán UCTP, ánh xạ các môn học vào các tiết học và phòng học.
• Cài đặt thuật toán ACO với hai quy tắc cập nhật mùi MMAS và SMMAS.
• Áp dụng thuật toán ghép cặp cực đại để phân bổ phòng học cho các môn học trong từng tiết học.
• Kết hợp tìm kiếm địa phương để cải tiến lời giải, giảm số vi phạm ràng buộc.
• Thực hiện chạy thực nghiệm trên máy tính cấu hình Intel Pentium B940 2.00GHz, RAM 4GB, sử dụng ngôn ngữ C++.
• So sánh kết quả về số vi phạm ràng buộc mềm trung bình và tốt nhất, cũng như thời gian chạy giữa hai thuật toán MMAS và SMMAS.
  Timeline nghiên cứu kéo dài trong năm 2015, tập trung vào việc phát triển thuật toán, thực nghiệm và phân tích kết quả.

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

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

1. Hiệu quả của quy tắc cập nhật mùi SMMAS vượt trội so với MMAS:

   • Trên bộ dữ liệu nhỏ, SMMAS đạt số vi phạm ràng buộc mềm thấp nhất là 4, trung bình 13.6, trong khi MMAS có số vi phạm cao hơn và không ổn định.
   • Trên bộ dữ liệu lớn, MMAS không tìm được lời giải chấp nhận được, trong khi SMMAS đạt số vi phạm trung bình khoảng 925, chứng tỏ khả năng mở rộng và ổn định của SMMAS.

2. Thời gian chạy của SMMAS nhanh hơn MMAS với cùng số vòng lặp:

   • Do quy tắc cập nhật mùi trơn của SMMAS không cần tính toán hàm mục tiêu lượng mùi cập nhật và không cần giới hạn giá trị pheromone trong khoảng [min, max], giảm thiểu chi phí tính toán.

3. Tìm kiếm địa phương cải thiện đáng kể chất lượng lời giải:

   • Việc áp dụng các phép dịch chuyển và tráo đổi trong không gian lân cận giúp giảm số vi phạm ràng buộc cứng và mềm, nâng cao chất lượng thời khóa biểu.

4. Thông tin heuristic trong bài toán UCTP rất đặc biệt và khó sử dụng hiệu quả:

   • Do tính đa dạng và phức tạp của các ràng buộc, việc điều chỉnh vết mùi đóng vai trò quan trọng hơn trong việc hướng dẫn tìm kiếm lời giải tốt.

Thảo luận kết quả

Nguyên nhân chính khiến SMMAS vượt trội là do quy tắc cập nhật mùi trơn giúp duy trì lượng pheromone trên các cạnh không thuộc lời giải tốt ở mức cao hơn, từ đó tăng khả năng khám phá không gian tìm kiếm và tránh tắc nghẽn vào các lời giải cục bộ kém chất lượng. Kết quả này phù hợp với các nghiên cứu trước đây về hiệu quả của SMMAS trên bài toán TSP.

So với các thuật toán truyền thống như tìm kiếm theo bề rộng, tìm kiếm theo độ sâu hay các thuật toán metaheuristic khác như di truyền, luyện kim, ACO đặc biệt là SMMAS cho thấy ưu thế vượt trội về khả năng tìm lời giải gần tối ưu trong thời gian hợp lý.

Việc kết hợp tìm kiếm địa phương với ACO cũng được chứng minh là một chiến lược hiệu quả, giúp cải thiện chất lượng lời giải bằng cách khai thác sâu hơn các vùng không gian tìm kiếm có tiềm năng.

Dữ liệu có thể được trình bày qua bảng so sánh số vi phạm ràng buộc mềm trung bình và tốt nhất giữa MMAS và SMMAS trên các bộ dữ liệu kích cỡ khác nhau, cùng biểu đồ thời gian chạy để minh họa hiệu quả tính toán.

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

1. Phát triển phần mềm ứng dụng cho bài toán lập thời khóa biểu hệ tín chỉ tại các trường đại học Việt Nam

   • Tập trung vào tích hợp thuật toán SMMAS với giao diện thân thiện, hỗ trợ nhập dữ liệu thực tế và xuất thời khóa biểu hoàn chỉnh.
   • Thời gian thực hiện: 12-18 tháng.
   • Chủ thể thực hiện: Các nhóm nghiên cứu công nghệ thông tin, các trung tâm công nghệ giáo dục.

2. Mở rộng nghiên cứu áp dụng SMMAS cho các bài toán lập lịch khác trong giáo dục

   • Ví dụ: lập lịch thi, phân công giảng viên, quản lý phòng học đa năng.
   • Thời gian: 6-12 tháng.
   • Chủ thể: Các nhà nghiên cứu và sinh viên ngành công nghệ thông tin, quản lý giáo dục.

3. Tối ưu hóa tham số thuật toán và kết hợp các phương pháp metaheuristic khác

   • Nghiên cứu điều chỉnh tham số bay hơi, số lượng kiến, tỷ lệ cập nhật mùi để nâng cao hiệu quả.
   • Kết hợp với thuật toán di truyền, tìm kiếm địa phương nâng cao.
   • Thời gian: 6 tháng.
   • Chủ thể: Các nhà khoa học máy tính, kỹ sư phần mềm.

4. Xây dựng cơ sở dữ liệu chuẩn và công cụ đánh giá chất lượng thời khóa biểu

   • Thiết lập bộ dữ liệu thực tế của các trường đại học Việt Nam để thử nghiệm và so sánh.
   • Phát triển bộ tiêu chí đánh giá khách quan về chất lượng thời khóa biểu.
   • Thời gian: 12 tháng.
   • Chủ thể: Các tổ chức giáo dục, viện nghiên cứu.

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

1. Nhà quản lý giáo dục và cán bộ phụ trách đào tạo

   • Lợi ích: Hiểu rõ các phương pháp tối ưu hóa thời khóa biểu, áp dụng công nghệ để nâng cao hiệu quả quản lý lịch học.
   • Use case: Lập kế hoạch đào tạo, phân bổ nguồn lực giảng dạy.

2. Giảng viên và nghiên cứu sinh ngành Công nghệ Thông tin, Hệ thống Thông tin

   • Lợi ích: Nắm bắt kiến thức về thuật toán ACO, các kỹ thuật tối ưu tổ hợp và ứng dụng thực tế.
   • Use case: Phát triển đề tài nghiên cứu, ứng dụng thuật toán metaheuristic.

3. Nhà phát triển phần mềm giáo dục

   • Lợi ích: Có cơ sở khoa học để xây dựng phần mềm lập thời khóa biểu thông minh, hiệu quả.
   • Use case: Thiết kế, triển khai hệ thống quản lý đào tạo tự động.

4. Các tổ chức nghiên cứu và phát triển công nghệ giáo dục

   • Lợi ích: Đánh giá và áp dụng các giải pháp tối ưu hóa trong quản lý giáo dục hiện đại.
   • Use case: Nghiên cứu phát triển công nghệ hỗ trợ quản lý đào tạo đại học.

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

1. Phương pháp ACO là gì và tại sao lại phù hợp với bài toán lập thời khóa biểu?
   ACO là thuật toán metaheuristic mô phỏng hành vi tìm đường của đàn kiến tự nhiên, sử dụng vết mùi để hướng dẫn tìm kiếm lời giải tối ưu. Phương pháp này phù hợp với bài toán lập thời khóa biểu do khả năng xử lý các bài toán tổ hợp phức tạp, đa ràng buộc và không gian tìm kiếm rộng lớn, giúp tìm lời giải gần tối ưu hiệu quả hơn các thuật toán truyền thống.

2. Sự khác biệt chính giữa MMAS và SMMAS là gì?
   MMAS giới hạn lượng pheromone trong khoảng [min, max] và tập trung khai thác lời giải tốt nhất, dễ dẫn đến tắc nghẽn tìm kiếm. SMMAS sử dụng quy tắc cập nhật mùi trơn, giảm tốc độ bay hơi pheromone trên các cạnh không thuộc lời giải tốt, tăng khả năng khám phá không gian tìm kiếm, từ đó cải thiện chất lượng lời giải và tốc độ hội tụ.

3. Tại sao tìm kiếm địa phương lại quan trọng trong giải bài toán lập thời khóa biểu?
   Tìm kiếm địa phương giúp cải tiến lời giải bằng cách thực hiện các phép dịch chuyển và tráo đổi nhỏ trong không gian lân cận, giảm số vi phạm ràng buộc cứng và mềm. Điều này giúp thuật toán tránh bị kẹt ở các cực trị địa phương và nâng cao chất lượng thời khóa biểu cuối cùng.

4. Bộ dữ liệu thực nghiệm được sử dụng như thế nào trong nghiên cứu?
   Bộ dữ liệu chuẩn UCTP được lấy từ các nguồn quốc tế, bao gồm thông tin về số môn học, phòng học, sinh viên và các ràng buộc liên quan. Dữ liệu này được sử dụng để đánh giá hiệu quả của các thuật toán ACO (MMAS và SMMAS) qua các chỉ số số vi phạm ràng buộc và thời gian chạy, đảm bảo tính khách quan và khả năng so sánh.

5. Có thể áp dụng kết quả nghiên cứu này cho các trường đại học khác không?
   Có thể. Mô hình và thuật toán được thiết kế linh hoạt, có thể điều chỉnh tham số và dữ liệu đầu vào phù hợp với đặc thù từng trường. Việc phát triển phần mềm ứng dụng dựa trên nghiên cứu này sẽ hỗ trợ các trường đại học khác trong việc lập thời khóa biểu hiệu quả, tiết kiệm thời gian và nguồn lực.

Kết luận

• Luận văn đã nghiên cứu và áp dụng thành công phương pháp tối ưu hóa đàn kiến với quy tắc cập nhật mùi Smooth-Max Min Ant System (SMMAS) cho bài toán lập thời khóa biểu trường đại học theo hệ tín chỉ.
• Kết quả thực nghiệm trên các bộ dữ liệu chuẩn cho thấy SMMAS vượt trội hơn MMAS về chất lượng lời giải và thời gian chạy, đặc biệt với các bài toán kích thước lớn.
• Việc kết hợp tìm kiếm địa phương giúp cải thiện đáng kể chất lượng thời khóa biểu, giảm số vi phạm ràng buộc cứng và mềm.
• Nghiên cứu mở ra hướng phát triển phần mềm ứng dụng thực tế cho các trường đại học tại Việt Nam, góp phần nâng cao hiệu quả quản lý đào tạo.
• Các bước tiếp theo bao gồm phát triển phần mềm, mở rộng nghiên cứu cho các bài toán lập lịch khác và tối ưu hóa tham số thuật toán nhằm nâng cao hiệu quả và tính ứng dụng rộng rãi.

Hành động khuyến nghị: Các nhà nghiên cứu và quản lý giáo dục nên tiếp cận và ứng dụng phương pháp ACO với quy tắc SMMAS để giải quyết các bài toán lập thời khóa biểu phức tạp, đồng thời phát triển các công cụ hỗ trợ tự động hóa trong quản lý đào tạo đại học.

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 z 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 z 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 z 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 z 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.