tailieunhanh - Cải tiến thuật toán Ant Colony giải quyết bài toán người bán hàng (TSP)

Bài viết đề xuất cách cải tiến thuật toán Ant Colony để hỗ trợ tìm ra đường đi ngắn hơn cho bài toán người bán hàng. Bài toán người bán hàng yêu cầu tìm ra đường đi ngắn nhất cho người bán hàng đi qua các thành phố và cuối cùng quay về lại thành phố xuất phát, mỗi thành phố chỉ được ghé thăm một lần, biết rằng tất cả các thành phố đều có đường đi đến với nhau và khoảng cách giữa các thành phố là biết trước. | Nội dung Text Cải tiến thuật toán Ant Colony giải quyết bài toán người bán hàng TSP TRƯỜNG ĐẠI HỌC DUY TÂN DTU Journal of Science and Technology 07 38 2020 . Cải tiến thuật toán Ant Colony giải quyết bài toán người bán hàng TSP Improve the Ant Colony algorithm to solve travelling salesman problem Lê Thị Ngọc Vân Nguyễn Dũng Trần Huệ Chi Thi Ngoc Van Le Dung Nguyen Hue Chi Tran Khoa Công nghệ Thông tin Trường Đại học Duy Tân Đà Nẵng Việt Nam Faculty of Information Technology Duy Tan University Da Nang Vietnam Ngày nhận bài 09 09 2019 ngày phản biện xong 03 12 2019 ngày chấp nhận đăng 20 12 2019 Tóm tắt Bài báo đề xuất cách cải tiến thuật toán Ant Colony để hỗ trợ tìm ra đường đi ngắn hơn cho bài toán người bán hàng. Bài toán người bán hàng yêu cầu tìm ra đường đi ngắn nhất cho người bán hàng đi qua các thành phố và cuối cùng quay về lại thành phố xuất phát mỗi thành phố chỉ được ghé thăm một lần biết rằng tất cả các thành phố đều có đường đi đến với nhau và khoảng cách giữa các thành phố là biết trước. Có rất nhiều thuật toán giải quyết được bài toán này. Một trong những thuật toán được nghiên cứu nhiều và giải quyết khá hiệu quả cho bài toán này là thuật toán Ant Colony thuật toán đàn kiến . Thuật toán Ant Colony có những hỗ trợ tìm kiếm rất mạnh mẽ và tỏ ra khá thích hợp với những bài toán có không gian tìm kiếm cực lớn. Tuy nhiên khi áp dụng thuật toán Ant Colony cho bài toán người bán hàng thì chi phí vẫn còn khá cao. Vì vậy nhóm chúng tôi thiết kế giải thuật cải tiến thuật toán Ant Colony để tìm lời giải tối ưu hơn cho bài toán người bán hàng. Chúng tôi đã tiến hành xây dựng thử nghiệm với nhiều bộ dữ liệu đầu vào để so sánh giữa thuật toán cải tiến với thuật toán Ant Colony nhằm đánh giá một cách chính xác và khách quan nhất. Kết quả cho thấy thuật toán cải tiến của nhóm chúng tôi đề xuất đã có cải thiện đáng kể về chi phí so với thuật toán Ant Colony. Từ khóa Ant Colony thuật toán cải tiến Ant Colony bài toán người bán hàng. Abstract This article proposes a