Cải tiến thuật toán Ant Colony giải quyết bài toán người bán hàng (TSP)

0 Người đánh giá. Xếp hạng trung bình 0

Tác giả: Thị Ngọc Vân Lê, Dũng Nguyễn, Huệ Chi Trần

Ngôn ngữ: Vie

Ký hiệu phân loại:

Thông tin xuất bản: Tạp chí Khoa học & Công nghệ Đại Học Duy Tân 2020

Mô tả vật lý: 45613

Bộ sưu tập: Metadata

ID: 392669

Thêm vào giỏ Liên kết toàn văn

Bài báo đề xuất cách cải tiến thuật toán Ant Colony để hỗ trợ tìm ra đường đi ngắn hơn cho bài toán người bán hàng. Bài toán người bán hàng yêu cầu tìm ra đường đi ngắn nhất cho người bán hàng đi qua các thành phố và cuối cùng quay về lại thành phố xuất phát, mỗi thành phố chỉ được ghé thăm một lần, biết rằng tất cả các thành phố đều có đường đi đến với nhau và khoảng cách giữa các thành phố là biết trước. Có rất nhiều thuật toán giải quyết được bài toán này. Một trong những thuật toán được nghiên cứu nhiều và giải quyết khá hiệu quả cho bài toán này là thuật toán Ant Colony (thuật toán đàn kiến). Thuật toán Ant Colony có những hỗ trợ tìm kiếm rất mạnh mẽ và tỏ ra khá thích hợp với những bài toán có không gian tìm kiếm cực lớn. Tuy nhiên khi áp dụng thuật toán Ant Colony cho bài toán người bán hàng thì chi phí vẫn còn khá cao. Vì vậy nhóm chúng tôi thiết kế giải thuật cải tiến thuật toán Ant Colony để tìm lời giải tối ưu hơn cho bài toán người bán hàng. Chúng tôi đã tiến hành xây dựng thử nghiệm với nhiều bộ dữ liệu đầu vào để so sánh giữa thuật toán cải tiến với thuật toán Ant Colony nhằm đánh giá một cách chính xác và khách quan nhất. Kết quả cho thấy thuật toán cải tiến của nhóm chúng tôi đề xuất đã có cải thiện đáng kể về chi phí so với thuật toán Ant Colony.

1. Đọc trực tuyến

1. Đọc trực tuyến

Tạo bộ sưu tập với mã QR