Bài báo: “Self-Adaptive Ant System with Hierarchical Clustering for the Thief Orienteering Problem”
Sinh viên thực hiện:
Lê Thế Việt – 20520093 – KHTN2020 – Tác giả chính.
Huỳnh Hoàng Vũ – 20520864 – KHTN2020 – Tác giả chính.
Giảng viên hướng dẫn:
TS. Lương Ngọc Hoàng.
Tóm tắt bài báo:
Các bài toán tối ưu đa thành phần là các bài toán bao gồm nhiều thành phần tương tác với nhau và là dạng bài toán phổ biến trong đời sống hằng ngày. Ví dụ cho các bài toán đa thành phần như định tuyến cho xe có hạn chế tải trọng hoặc tối ưu hóa việc sử dụng vật liệu trong lịch trình sản xuất. Các bài toán này có tính thách thức do sự phụ thuộc lẫn nhau giữa các thành phần khác nhau và thường liên quan đến các nhiệm vbài toán tối ưu hóa NP-Hard như bài toán ba lô, bài toán lập lịch và bài toán tìm đường đi.
Trong bài báo này, chúng em giải quyết bài toán Điều Hương Thu thập (Thief Orienteering Problem, ThOP), một bài toán tối ưu đa thành phần. ThOP kết hợp bài toán Điều Hướng (Orienteering Problem, OP) và bài toán Ba Lô (Knapsack Problem, KP). Mục tiêu là tìm một tuyến đường từ thành phố bắt đầu đến thành phố kết thúc (thành phần OP) sao cho tổng lợi nhuận của các vật phẩm thu thập được tối đa hóa (thành phần KP) trong khi vẫn đảm bảo giới hạn sức chứa ba lô và thời gian di chuyển.
Các công trình trước đây đã đề xuất nhiều thuật toán khác nhau cho ThOP và tiêu biểu nhất là thuật toán Max-min ant colony optimization (ACO++). Tác giả của thuật toán đã chỉ ra rằng ACO++ hoạt động tốt hơn các thuật toán khác trong hơn 90% trong thang đo của ThOP. Để đạt được kết quả vượt trội này, ACO++ đã trải qua một quá trình điều chỉnh tốn kém để tìm ra cấu hình siêu tham số phù hợp cho từng nhóm testcase trong thang đo của ThOP.
Trong bài báo này, chúng em giới thiệu một thuật toán được cải thiện dựa trên ACO++. Thuật toán của chúng em kết hợp hai cơ chế tự kiểm soát tham số để cải thiện khả năng thích nghi. Nó cũng bao gồm hai kỹ thuật để giảm độ phức tạp về thời gian, phân cụm cấp bậc và bay hơi lười biếng. Sự cải tiến này đã mang lại khả năng điều chỉnh động các tham số của nó theo các đặc trưng của từng trường hợp trong suốt quá trình tìm kiếm đồng thời thể hiện hiệu suất vượt trội.
"Chúng em xin gửi lời cảm ơn đến thầy Lương Ngọc Hoàng đã đồng hành và hướng dẫn nhóm chúng em trong quá trình nghiên cứu và công bố bài báo khoa học quốc tế này. Chúng em xin cảm ơn trường đã tài trợ cho nghiên cứu này"
SOICT (Symposium on Information and Communication Technology) là hội thảo quốc tế về các lĩnh vực nghiên cứu quan trọng như: trí tuệ nhân tạo, dữ liệu lớn, truyền thông và bảo mật mạng, xử lý ngôn ngữ tự nhiên, xử lý ảnh, kỹ thuật phần mềm, công nghệ Blockchain, và vận trù học. Nối tiếp sự thành công của hội thảo SOICT 2022 đã nhận được các bài báo từ 14 quốc gia, hội thảo SOICT 2023 sẽ được tổ chức tại thành phố Hồ Chí Minh vào ngày 7, 8 tháng 12 năm 2023. Mục tiêu của hội thảo là cung cấp diễn đàn học thuật cho các nhà nghiên cứu và sinh viên sau để chia sẻ những kết quả nghiên cứu mới nhất và xác định những thử thách của lĩnh vực khoa máy tính trong tương lai.
Hội thảo SOICT 2023 được tổ chức bởi Trường Công nghệ Thông tin và Truyền thông - Đại học Bách khoa Hà Nội, Trường Đại học Khoa học Tự nhiên Thành phố Hồ Chí Minh, Phòng thí nghiệm LIMOS (Laboratory Informatics, Modelling and Optimisation System), Trung tâm Nghiên cứu Khoa học Quốc gia Pháp (The French National Centre for Scientific Research, CNRS) và Viện Nghiên cứu Toán học Cao cấp Việt Nam. SOICT 2023 được tổ chức kết hợp với Hội nghị Mạng lưới Vận trù học Việt Nam lần thứ ba (VORN 2023).
Thông tin chi tiết: https://www.facebook.com/UIT.Fanpage/posts/pfbid0bfUhmWW822B3V78XjDzvJix5ge6BtcZA91aD6wprWkuigqFiL5n2bDGdLYkSK3Pel
Hải Băng - Cộng tác viên Truyền thông trường Đại học Công nghệ Thông tin
