tailieunhanh - Tóm tắt luận văn Thạc sĩ Kỹ thuật: Nghiên cứu ứng dụng giải thuật đàn kiến để giải quyết bài toán người du lịch

Mục đích nghiên cứu luận văn nhằm tìm hiểu về bài toán người du lịch, tìm hiểu các thuật toán truyền thống và thuật toán di truyền cho bài toán người du lịch, tìm hiểu thuật toán tối ưu đàn kiến ACO, áp dụng thuật toán ACO vào bài toán người du lịch, đánh giá hiệu quả của thuật toán tối ưu đàn kiến ACO so với thuật toán di truyền trong việc giải bài toán người du lịch, xây dựng chương trình giải quyết bài toán người du lịch với số lượng dữ liệu lớn. | BỘ GIÁO DỤC VÀ ĐÀO TẠO ĐẠI HỌC ĐÀ NẴNG ĐẶNG QUÝ LINH NGHIÊN CỨU ỨNG DỤNG GIẢI THUẬT ĐÀN KIẾN ĐỂ GIẢI QUYẾT BÀI TOÁN NGƯỜI DU LỊCH Chuyên ngành Khoa học máy tính Mã số 60 48 01 TÓM TẮT LUẬN VĂN THẠC SĨ KỸ THUẬT Đà Nắng - Năm 2013 Công trình được hoàn thành tại ĐẠI HỌC ĐÀ NẴNG Người hướng dẫn khoa học TS. Nguyễn Tấn Khôi Phản biện 1 Nguyễn Văn Hiệu Phản biện 2 Nguyễn Mậu Hân Luận văn sẽ được bảo vệ trước Hội đồng chấm Luận văn tốt nghiệp thạc sĩ khoa học máy tính họp tại Đại học Đà Nằng vào ngày 16 tháng 11 năm 2013 Có thể tìm hiểu luận văn tại - Trung tâm Thông tin - Học liệu Đại học Đà Nằng - Trung tâm Học liệu Đại học Đà Nằng 1 MỞ ĐẦU 1. Lý do chọn đề tài Bài toán Người du lịch Travelling Salesman Problem - TSP là một trong những bài toán kinh điển và khó trong tin học 1 2 3 4 5 6 . Bài toán có phát biểu rất đơn giản nhưng rất khó giải trong trường hợp tổng quát với không gian tìm kiếm rộng lớn khó bởi các thuật toán hiệu quả nhất đã được biết đến có thời gian giải quyết bài toán này tăng dần theo cấp số nhân của n hay độ phức tạp thuật toán tăng theo hàm số mũ 14 . Có rất nhiều cách tiếp cận giải bài toán này ngay từ khi nó mới ra đời như sử dụng quy hoạch tuyến tính thuật toán vét cạn thuật toán người láng giềng gần nhất kỹ thuật nhánh và cận nhưng mới chỉ dừng lại ở các bộ dữ liệu nhỏ. Gần đây có nhiều thuật toán ra đời theo hướng tiếp cận về tiến hóa như thuật toán di truyền Genetic Algorithm hay cách mô phỏng hành vi của đàn kiến như thuật toán đàn kiến được áp dụng cho kết quả tốt hơn rất nhiều. Thuật toán đàn kiến do Thomas Stutzle và Marco Dorigo đề xuất là một thuật toán độc đáo và có thể áp dụng cho nhiều bài toán tối ưu tổ hợp với một bộ dữ liệu lớn. Thuật toán kiến mô phỏng hành vi của đàn kiến trong tự nhiên nhằm tìm kiếm đường đi ngắn nhất giữa tổ kiến và nguồn thức ăn dựa trên mật độ mùi pheromone mà các con kiến để lại trên đường đi 1 3 4 5 . Người ta đã áp dụng rất thành công các thuật toán đàn kiến trong các bài toán tối ưu như bài toán người đưa