Đề tài Đề xuất ý tưởng bài toán IDPC-DU trên cạnh

GV hướng dẫn: ThS. Đỗ Tuấn Anh Đề xuất ý tưởng bài toán IDPC-DU trên cạnh Sinh viên: Trần Văn Điệp – 20183496 Vũ Văn Thái – 20183626 ACO Algorithm Genetic Algorithm Tổng quan Nội Dung Phát biểu bài toán Đề xuất GA + ACO Các phương án cải tiến Kết quả thực nghiệm ACO Algorithm Genetic Algorithm Phát biểu bài toán Đầu vào: Đầu ra: ACO Algorithm Genetic Algorithm Phát biểu bài toán Nghiên cứu liê n quan Adewole, Philip & Taofiki, Akinwale & Otunbanowo, Kehinde. (2011). A Genetic Algorithm for Solving Travelling Salesman Problem . International Journal of Advanced Computer Sciences and Applications. 2. 10.14569/IJACSA.2011.020104. H. T. T. Binh, T. B. Thangy, 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 ACO Algorithm Genetic Algorithm Phát biểu bài toán ACO Algorithm Genetic Algorithm Phát biểu bài toán Genetic Algorithm ACO Algorithm Đề xuất GA + ACO Genetic Algorithm Sinh quần thể mới Chọn lọc Kiểm tra điều kiện dừng Kết thúc Khởi tạo quần thể Đánh giá độ thích nghi ACO Algorithm Đề xuất GA + ACO Genetic Algorithm Khởi tạo quần thể Đề xuất GA + ACO Genetic Algorithm Sinh quần thể mới Chọn lọc Kiểm tra điều kiện dừng Kết thúc Khởi tạo quần thể Đánh giá độ thích nghi ACO Algorithm Đề xuất GA + ACO Genetic Algorithm Đánh giá độ thích nghi ACO Algorithm Khởi tạo pheromone Xây dựng đường đi cho đàn kiến Cập nhật pheromone& lời giải tốt nhất Kết thúc Đề xuất GA + ACO Genetic Algorithm Khởi tạo pheromone ACO Algorithm Đánh giá độ thích nghi Xây dựng đường đi cho đàn kiến Cập nhật pheromone& lời giải tốt nhất Kết thúc Đề xuất GA + ACO Genetic Algorithm Khởi tạo pheromone ACO Algorithm Đánh giá độ thích nghi Xây dựng đường đi cho đàn kiến Cập nhật pheromone& lời giải tốt nhất Kết thúc là pheromone trên cạnh (i,j) là mức độ thu hút cạnh (i,j) là độ ưu tiên miền của cạnh (i,j) là tập các cạnh hàng xóm của thoả mãn DU mà k chưa đi qua và và là tham số thuật toán Đề xuất GA + ACO Genetic Algorithm Khởi tạo pheromone ACO Algorithm Đánh giá độ thích nghi Xây dựng đường đi cho đàn kiến Cập nhật pheromone& lời giải tốt nhất Kết thúc Quá trình của cá thể kiến thứ k tiếp tục cho đến khi tìm được đường đi hoàn chỉnh hoặc không thể tiếp tục Đề xuất GA + ACO Genetic Algorithm Khởi tạo pheromone ACO Algorithm Đánh giá độ thích nghi Xây dựng đường đi cho đàn kiến Cập nhật pheromone& lời giải tốt nhất Kết thúc Trả về chi phí đường đi tốt nhất của đàn kiến Cập nhật độ thích nghi cho cá thể của mức GA Đề xuất GA + ACO Genetic Algorithm Đánh giá độ thích nghi ACO Algorithm Khởi tạo pheromone Xây dựng đường đi cho đàn kiến Cập nhật pheromone& lời giải tốt nhất Kết thúc Đề xuất GA + ACO Genetic Algorithm Sinh quần thể mới Chọn lọc Kiểm tra điều kiện dừng Kết thúc Khởi tạo quần thể Đánh giá độ thích nghi ACO Algorithm Đề xuất GA + ACO Genetic Algorithm Sinh quần thể mới Chéo hoá nhị phân - SBX Đột biến đa thức Roulette Wheel Đề xuất GA + ACO Genetic Algorithm Chọn lọc Giữ lại các cá thể ưu tú n : Trộn quần thể cha mẹ với quần thể con Sắp xếp quần thể theo thứ tự Fitness giảm dần Loại bỏ những cá thể có Fitness thấp Đề xuất GA + ACO Genetic Algorithm Sinh quần thể mới Chọn lọc Kiểm tra điều kiện dừng Kết thúc Khởi tạo quần thể Đánh giá độ thích nghi Đề xuất GA + ACO Các bước thực hiện Tập ứng cử viên Các bước thực hiện Tập ứng cử viên Tập ứng cử viên Các bước thực hiện Tập ứng cử viên Các bước thực hiện Tập ứng cử viên Các bước thực hiện Phương án cải tiến Giải pháp: Blacklist Xây dựng nhật ký lộ trình miền: “1_2_3” – “đen - đỏ - xanh” Phương án cải tiến Giải pháp: Blacklist Loại bỏ ứng cử viên sẽ xây dựng lộ trình miền chứa thông tin lộ trình miền gây tắc: "1_2_3" và "2_1_3" Đề xuất ACO Tập ứng cử viên Phương án cải tiến Giải pháp: CheckSum Phương án cải tiến Giải pháp: CheckSum Kết quả thực nghiệm Kết quả thực nghiệm Kết quả thực nghiệm Kết quả thực nghiệm Kết quả thực nghiệm Kết quả thực nghiệm Thanks for your attention!