SO SÁNH HIỆU QUẢ CỦA GIẢI THUẬT DI TRUYỀN VÀ GIẢI THUẬT TỐI ƯU HÓA ĐÀN KIẾN CHO BÀI TOÁN NGƯỜI DU LỊCH

Tóm tắt

Trong bài báo này, chúng tôi nghiên cứu áp dụng giải thuật di truyền và giải thuật tối ưu hóa đàn kiến, là các giải thuật thuộc lớp giải thuật tìm kiếm meta-heuristics, cho bài toán người du lịch. Chúng tôi thực hiện các thực nghiệm để đánh giá giải thuật nào giải bài toán hiệu quả hơn theo nghĩa đạt được chất lượng nghiệm và thời gian tìm kiếm nghiệm tốt nhất. Kết quả thử nghiệm chỉ ra rằng giải thuật tối ưu hóa đàn kiến là giải thuật hiệu quả trong việc tìm chu trình ngắn nhất, ngược lại giải thuật di truyền là giải thuật hiệu quả về thời gian khi số đỉnh của đồ thị lớn