Đề tài Áp dụng giải thuật aco cho bài toán tìm đường đi tối ưu trên đồ thị đa miền trên đỉnh

ÁP DỤNG GIẢI THUẬT ACO CHO BÀI TOÁN TÌM ĐƯỜNG ĐI TỐI ƯU TRÊN ĐỒ THỊ ĐA MIỀN TRÊN ĐỈNH GVHD: ThS. Đỗ Tuấn Anh Trần Quang Minh – 20183594 Nguyễn Danh Phúc – 20183607 2 NỘI DUNG TRÌNH BÀY Giới thiệu đề tài Các nghiên cứu liên quan Phát biểu bài toán Mô hình bài toán Giải thuật áp dụng Phương pháp cải tiến Kết quả thực nghiệm Kết luận và hướng phát triển 3 GIỚI THIỆU ĐỀ TÀI Là mở rộng của bài toán đường đi ngắn nhất trên đồ thị Là trường hợp đơn giản hóa của bài toán tìm đường đi tối ưu trên đồ thị đa miền trên cạnh (IDPC-DU) Là bài toán NP-khó Ứng dụng: Trong quân sự Trong vận chuyển hàng hóa Trong truyền tin 4 CÁC NGHIÊN CỨU LIÊN QUAN H. T. T. Binh, T. B. Thang, N. B. Long, N. V. Hoang and P. D. Thanh Multifactorial Evolutionary Algorithm for Inter-Domain Path Computation under Domain Uniqueness Constraint,"  2020 IEEE Congress on Evolutionary Computation (CEC) , 2020, pp. 1-8, doi: 10.1109/CEC48606.2020.9185701. Tuan, A.D., Hoang, L., Bao, T.T., Binh, H.T., & Su, S. (2021). A two-level strategy based on evolutionary algorithm to solve the inter-domain path computation under node-defined domain uniqueness constraint. 5 PHÁT BIỂU BÀI TOÁN Cho một đồ thị có hướng đa miền trên các đỉnh, có trọng số cùng với đỉnh nguồn và đỉnh đích cho trước Mục tiêu: tìm đường đi ngắn nhất từ đỉnh nguồn đến đỉnh đích Điều kiện: không được lặp lại miền mà đã đi qua trước đó 6 MÔ HÌNH BÀI TOÁN Cho đồ thị có hướng, có trọng số , cùng với hai đỉnh trong đó: là tập các đỉnh là tập các cạnh có hướng, có trọng số tương ứng độ dài cạnh nối đỉnh với đỉnh được chia thành các tập con rời nhau tương ứng với các miền là đỉnh bắt đầu, là đỉnh đích Mục tiêu: tìm đường đi ngắn nhất từ đến sao cho không có miền nào được đi 2 lần 7 MÔ HÌNH BÀI TOÁN Đường đi không thỏa mãn bài toán 8 MÔ HÌNH BÀI TOÁN Đường đi thỏa mãn bài toán 9 GIẢI THUẬT ÁP DỤNG Tiền xử lý Giải thuật ACO Cải tiến Lời giải Tổng quan các bước xử lý 10 GIẢI THUẬT ÁP DỤNG Tiền xử lý: Loại bỏ đi các cạnh cùng nguồn và đích, chọn ra cạnh có trọng số nhỏ nhất 11 GIẢI THUẬT ÁP DỤNG Ant Colony Optimization (ACO): Được giới thiệu bởi Marco Dorigo ở đầu những năm 1990s Thuộc lớp các thuật toán tối ưu sử dụng Trí thông minh bầy đàn Lấy cảm hứng từ tập tính xã hội trong việc tìm kiếm thức ăn của đàn kiến trong tự nhiên Thuật toán dựa trên quần thể Đối tượng áp dụng: các bài toán tối ưu rời rạc (bài toán tìm đường đi). 12 GIẢI THUẬT ÁP DỤNG Ban đầu, các cá thể đi theo các đường đi ngẫu nhiên để tìm kiếm thức ăn chính là điểm đích Nếu tìm thấy đích, kiến quay về điểm xuất phát và để lại một chất gọi là pheromone trên đường quay lại Pheromone trên các đường đi sẽ giảm dần theo thời gian Đường đi có pheromone càng cao thì khả năng lựa chọn đi theo đường đi đó càng lớn Càng nhiều kiến tìm thấy thức ăn trên một đường đi thì pheromone của đường đi đó càng cao Sau một thời gian, các kiến chỉ đi theo một đường 13 GIẢI THUẬT ÁP DỤNG 14 GIẢI THUẬT ÁP DỤNG Xây dựng đường đi cho cá thể kiến: Xét cá thể kiến đang ở nút : Xác suất đi từ đến nút là: Với là pheromone trên cạnh là mức độ thu hút của cạnh là tập các nút hang xóm của mà chưa đi qua, cũng như thỏa mãn ràng buộc về miền và là tham số thuật toán 15 GIẢI THUẬT ÁP DỤNG Nút được chọn cho kiến theo phương pháp bánh xe Roulete Quá trình được thực hiện cho đến khi kiến đến được đỉnh tương ứng với một lời giải hợp lệ, ngược lại, nếu kiến không thể tiếp tục thì loại bỏ 16 GIẢI THUẬT ÁP DỤNG Cập nhật pheromone: Pheromone trên mỗi cạnh được cập nhật theo công thức Với là tốc độ bay hơi của pheromone là tổng các pheromone mới mà kiến để lại trên đường đi của chúng 17 GIẢI THUẬT ÁP DỤNG Giá trị của pheromone để lại bởi kiến k trên đường đi của chúng Với là hành trình của kiến là tổng chiều dài của hành trình là hằng số kinh nghiệm 18 GIẢI THUẬT ÁP DỤNG Giá trị các tham số: Số thế hệ: 100 Số kiến trong 1 thế hệ: 500 khởi tạo: khởi tạo: 0.02 : 1 : 2 : 0.05 : 5 19 PHƯƠNG PHÁP CẢI TIẾN Vấn đề của ACO trong bài toán: Nhiều kiến bị tắc không tìm được đường đi hợp lệ do ràng buộc về miền Phương pháp cải tiến: Sử dụng tham số pheromone trên miền Sử dụng phương pháp Checksum Sử dụng phương pháp BlackList 20 PHƯƠNG PHÁP CẢI TIẾN Sử dụng tham số pheromone trên miền Tăng xác suất kiến đi vào đỉnh tương ứng với miền trước đó đã có đường đi hợp lệ Giảm khả năng kiến bị tắc không tìm được đường đi 21 PHƯƠNG PHÁP CẢI TIẾN Xác suất đi từ đến nút là: Trong đó với là mùi của miền, là hệ số Cập nhật pheromone miền tương tự như pheromone cạnh 22 PHƯƠNG PHÁP CẢI TIẾN Sử dụng phương pháp Checksum: Khi chọn cạnh tiếp theo, loại bỏ đi các cạnh có độ dài cộng với tổng quãng đường đã đi trước đó lớn hơn lời giải tốt nhất đã thu được Các kiến sẽ có xu hướng đi theo các đường đi tối ưu hơn theo các thế hệ Tương tự như phương pháp cắt tỉa alpha-beta 23 PHƯƠNG PHÁP CẢI TIẾN Đỉnh nguồn: 1, đỉnh đích: 16 Lời giải tốt nhất của thế hệ trước: 1, 2, 5, 10, 12, 16 Chi phí: 15 24 PHƯƠNG PHÁP CẢI TIẾN Đỉnh nguồn: 1, đỉnh đích: 16 Cá thể kiến hiện tại: 1, 2, 5, 3 Chi phí hiện tại: 9 Ứng viên: 6, 7, 4 25 PHƯƠNG PHÁP CẢI TIẾN Đỉnh nguồn: 1, đỉnh đích: 16 Xét đỉnh 6: khi đó chi phí nếu đi qua đỉnh này là 15 Chi phí không tốt hơn thế hệ trước đó => Loại bỏ đỉnh 6 ra khỏi tập ứng viên 26 PHƯƠNG PHÁP CẢI TIẾN Sử dụng phương pháp Blacklist: Xây dựng lộ trình các miền cho từng kiến Lưu lộ trình miền tại đỉnh mà kiến không thể tìm được đường đi tiếp theo Các cá thể kiến sau đó sẽ loại bỏ đi các đỉnh gây tắc mà có lộ trình miền tương tự với lộ trình miền mà kiến đang xét đã đi qua Các cá thể kiến sẽ có khả năng tìm được đường đi thỏa mãn lớn hơn 27 PHƯƠNG PHÁP CẢI TIẾN Đỉnh nguồn: 1, đỉnh đích: 16 Đường đi gây tắc: 1, 4, 9 Lưu lại lộ trình miền gây tắc tại điểm 9: Đỏ, Xanh 28 PHƯƠNG PHÁP CẢI TIẾN Đỉnh nguồn: 1, đỉnh đích: 16 Xét kiến đang đi theo đường: 1, 2, 5, 3, 4 Lộ trình miền: Đỏ Các ứng viên: 9, 15 29 PHƯƠNG PHÁP CẢI TIẾN Đỉnh nguồn: 1, đỉnh đích: 16 Khi xét đến điểm 9: Lộ trình miền nếu đi tại điểm 9 là Đỏ, Xanh So sánh với lộ trình miền gây tắc đã lưu tại điểm 9: Đỏ, Xanh => Loại 9 ra khỏi tập ứng viên 30 KẾT QUẢ THỰC NGHIỆM 31 KẾT QUẢ THỰC NGHIỆM 32 KẾT LUẬN VÀ HƯỚNG PHÁT TRIỂN Kết luận Thời gian chạy tương đối nhanh Kết quả khá tốt với những bộ dữ liệu nhỏ Chưa tốt với những bộ dữ liệu lớn với những nhiều đỉnh, cạnh và miền hơn Hội tụ tương đối nhanh Hướng phát triển Sử dụng phương pháp mã hóa mới để áp dụng thuật toán GA Áp dụng thêm một số kỹ thuật khác để cải tiến độ hiểu quả 33 THANK YOU !